Элементарная конъюнкция и элементарная дизъюнкция.
Дизъюнктивная нормальная форма (ДНФ). Алгоритм приведения булевой функции к ДНФ. Теорема о дизъюнктивном разложении булевой функции.
Совершенная дизъюнктивная нормальная форма (СДНФ). Алгоритмы приведения булевой функции к СДНФ.
Конъюнктивная нормальная форма (КНФ). Алгоритм приведения булевой функции к КНФ. Теорема о конъюнктивном разложении булевой функции.
Совершенная конъюнктивная нормальная форма (СКНФ). Алгоритмы приведения булевой функции к СКНФ.
Полиномы Жегалкина. Алгоритмы приведения булевой функции к полиному Жегалкина.
Двойственность. Принцип двойственности.
Полные системы логических связок. Теорема Поста о функциональной полноте. Проблемы полноты и разрешимости.
Релейно-контактные схемы, их математическое описание и методы построения.
Кванторные операции как обобщения операций конъюнкции и дизъюнкции. Предикаты. Синтаксис и семантика языка логики предикатов. Формулы логики предикатов. Свободные и связанные переменные.
Формальная аксиоматическая теория, её задание и компоненты. Основные понятия теории доказательств. Аксиоматическая теория исчисления высказываний. Теорема дедукции.
Теоремы теории исчисления высказываний. Теории исчисления высказываний Клини, Гильберта-Аккермана, Россера, интуиционистская.
Аксиоматическая теория исчисления предикатов первого порядка. Правила вывода теории исчисления предикатов. Теорема дедукции.
Теоремы теории исчисления предикатов. Примеры теорий первого порядка.
Метод резолюций в логике предикатов.
Метаязык и метатеория. Проблемы разрешимости, полноты и непротиворечивости формальных аксиоматических теорий. Теоремы о полноте и непротиворечивости теории исчисления высказываний.
Непротиворечивость теорий первого порядка. Теорема Гёделя о полноте.
Эффективная вычислимость функции. Уточнение понятия алгоритма. Разрешимые и перечислимые множества. Примитивная рекурсия. Примитивно-рекурсивные функции. Примитивная рекурсивность некоторых арифметических функций.
studopedia.org - Студопедия.Орг - 2014-2025 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования(0.008 с)...