- Булевы функции. Существенные булевы функции одного и двух аргументов. Теорема о функциональной полноте конъюнкции, дизъюнкции и отрицания.
- Полиномы Жегалкина. Теорема о представимости любой булевой функции единственным полиномом Жегалкина.
- Исчисление высказываний. Общезначимость выводимых формул.
- Теорема о дедукции в исчислениях высказываний и предикатов.
- Правила введения и удаления в исчислении высказываний.
- Теорема о полноте исчисления высказываний (построение вывода общезначимой формулы с использованием закона исключенного третьего).
- Язык логики предикатов. Модели и оценки. Истинностные значения формул. Свободные и связанные вхождения переменных. Конгруэнтные формулы.
- Исчисление предикатов. Общезначимость схем аксиом для квантора существования и всеобщности. Общезначимость выводимых в исчислении предикатов формул.
- Правило обобщения. Законы коммутативности. Законы де Моргана для кванторов. Лемма о замене подформулы.
- Законы пронесения кванторов: всеобщности через конъюнкцию, существования через дизъюнкцию и законы пронесения кванторов в общем случае
- Корректное переименование связанных переменных. Представимость любой формулы исчисления предикатов в пренексной нормальной форме.
- Непротиворечивость теории, имеющей модель. Вывод теоремы Гёделя о полноте исчисления предикатов из предположения, что любая теория, имеющая модель, непротиворечива.
- Лемма Линденбаума.
- Теорема о существовании модели у всякой непротиворечивой теории.
- Язык первого порядка теории множеств, отношения «принадлежать» и «быть подмножеством». Аксиома экстенсиональности и отношение равенства.
- Система аксиом Цермело–Френкеля и простейшие следствия из аксиом.
- Понятие коллективизирующего соотношения. Термы вида {x | A} и операции над множествами, которые могут быть построены на их основе.
- Упорядоченная пара по Куратовскому, декартово произведение и проекции множеств.
- Множество натуральных чисел по фон Нейману. Возможные способы построения множеств целых, рациональных и действительных чисел с арифметическими операциями.
- Теоремы о счётной индукции и рекурсии. Примеры построения множеств с помощью счётной рекурсии.
- Бинарные отношения на двух множествах, их разновидности и основные свойства. Прообразы, обратные отношения, композиции отношений.
- Теорема Кантора–Шрёдера–Бернштейна.
- Сравнение множеств по мощности. Арифметические операции над мощностями и их основные свойства.
- Теорема Кантора. Парадокс Кантора «наивной» теории множеств.
- Конечные и бесконечные множества. Критерий Дедекинда бесконечности множества.
- Бинарные отношения на одном множестве, их разновидности и основные свойства. Теорема о классах эквивалентности.
- Минимальные/наименьшие, максимальные/наибольшие элементы и грани частично упорядоченных множеств.
- Изоморфизмы порядков. Изоморфные и не изоморфные частично упорядоченные множества.
- Ординалы: определение и основные свойства.
- Теорема о трансфинитной индукции. Сравнимость любых двух ординалов по отношению принадлежности.
- Несуществование множества всех ординалов (парадокс Бурали–Форти).
- Предельные и последующие ординалы. Представимость любого ординала в виде суммы предельного ординала и натурального числа.
- Теорема о трансфинитной рекурсии.
- Изоморфность любого вполне упорядоченного множества единственному ординалу.
- Теорема Цермело о вполне упорядочении произвольного множества в теории ZF с аксиомой выбора. Её следствие о сравнимости любых двух
множеств по мощности. - Лемма Цорна.
- Теорема о квадрате. Соотношения |a| + |b| = |a||b| = max(|a|, |b|) для бесконечных множеств.
- Схема конструкции ступени, ступень, шкала множеств, характер типизированных элементов.
- Канонические распространения отображений при типизации, перенос, биективная переносимость термов и соотношений.
- Условия биективной переносимости термов и соотношений. Формальный язык родов структур.
- Биективно переносимые операции над множествами. Вычисление результирующей типизации.
- Определение рода структуры, сигма-объекта, изоморфизма сигма-объектов.
- Теоремы родов структур. Критерий непротиворечивости рода структуры.
- Основные примеры построения родов структур.
- Операция порождения множества структур данного рода. Операция синтеза родов структур.