Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов».
Логика высказываний.
-
Понятие высказывания и его структура: атомарные высказывания и составные высказывания. Логические союзы: дизъюнкция, конъюнкция, импликация, эквивалентность, отрицание. Символическая запись составных высказываний и формализация предложений естественного языка.
-
Алфавит и слова в алфавите. Формальные языки.
-
Алфавит языка логики высказываний. Индуктивное определение пропозициональной формулы. Понятие подформулы пропозициональной формулы. Индукция по длине построения формулы.
-
Логическая сложность пропозициональных формул. Теорема характеризации множества пропозициональных формул.
-
Теорема о единственности синтаксического анализа пропозициональной формулы.
-
Оценки пропозициональных букв и индуктивное определение истинностного значения пропозициональной формулы. Множество истинностных оценок и функция истинности пропозициональной формулы. Таблица истинности пропозициональной формулы.
-
Выполнимые и общезначимые формулы(тавтологии).
-
Отношение семантического следования и семантической равносильности пропозициональных формул. Семантический modus ponens и семантическая теорема дедукции.
-
Основные равносильности межу пропозициональными формулами и булева алгебра пропозициональных формул.
-
Специальные виды пропозициональных формул. Литерал, дизъюнкты и конъюнкты относительно списка букв. Семантические свойства дизъюнктов и конъюнктов. Определение ДНФ и КНФ.
-
Теорема о приведении любой пропозициональной формулы к КНФ и ДНФ. Алгоритм нормализации(приведения к КНФ и ДНФ).
-
СДНФ и СКНФ. Теорема единственности СКНФ и СДНФ.
-
Описание всех семантических следствий конечного списка пропозициональных формул через приведение к СКНФ.
-
Переключательные схемы и их функции истинности. Представление схем пропозициональными формулами.
-
Общее понятие исчисления(формальной аксиоматической теории).
-
Логическое исчисление и вывод в исчислении (формальной теории): алфавит, множество выражений и правил вывода исчисления.
-
Посылки и заключение правила вывода, понятие непосредственного следствия и определение вывода из множества выражений.
-
Отношение выводимости, вывод из гипотез и определение доказуемости в исчислении. Порождающие грамматики как пример формальных теорий.
-
Понятие о языке-объекте и метоязыке. Элементарные свойства отношения выводимости в формальной теории.
-
Построение исчисления высказываний. Его аксиомы и правила вывода.
-
Пример построения выводов в исчислении высказываний (ИВ).
-
Теорема дедукции в исчислении высказываний.
-
Применение теоремы дедукции к построению выводов. Допустимые правила в исчислении высказываний.
-
Теорема адекватности исчисления высказываний.
-
Непротиворечивые и противоречивые множества формул в исчислении высказываний. Теорема о непротиворечивости выполнимого множества формул.
-
Свойства непротиворечивых множеств формул в исчислении высказываний. Непротиворечивое множество аксиом в исчислении высказываний.
-
Нумерация пропозициональных формул по Геделю.
-
Теорема о расширении непротиворечивого множества до максимально непротиворечивого множества до максимально непротиворечивого множества.
-
Теорема о выполнимости максимально непротиворечивого множества.
-
Теорема о полноте исчисления высказываний и некоторые её следствия.
-
Понятие независимости формулы от множества формул. Пример зависимых и независимых пропозициональных формул.
-
Понятие о многозначных логиках. Примеры трехзначных логик.
-
Метод многозначных логик в доказательстве независимости аксиом исчисления высказываний.
Поделитесь с Вашими друзьями:
