Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов».
Логика высказываний.
Понятие высказывания и его структура: атомарные высказывания и составные высказывания. Логические союзы: дизъюнкция, конъюнкция, импликация, эквивалентность, отрицание. Символическая запись составных высказываний и формализация предложений естественного языка.
Алфавит и слова в алфавите. Формальные языки.
Алфавит языка логики высказываний. Индуктивное определение пропозициональной формулы. Понятие подформулы пропозициональной формулы. Индукция по длине построения формулы.
Логическая сложность пропозициональных формул. Теорема характеризации множества пропозициональных формул.
Теорема о единственности синтаксического анализа пропозициональной формулы.
Оценки пропозициональных букв и индуктивное определение истинностного значения пропозициональной формулы. Множество истинностных оценок и функция истинности пропозициональной формулы. Таблица истинности пропозициональной формулы.
Выполнимые и общезначимые формулы(тавтологии).
Отношение семантического следования и семантической равносильности пропозициональных формул. Семантический modus ponens и семантическая теорема дедукции.
Основные равносильности межу пропозициональными формулами и булева алгебра пропозициональных формул.
Специальные виды пропозициональных формул. Литерал, дизъюнкты и конъюнкты относительно списка букв. Семантические свойства дизъюнктов и конъюнктов. Определение ДНФ и КНФ.
Теорема о приведении любой пропозициональной формулы к КНФ и ДНФ. Алгоритм нормализации(приведения к КНФ и ДНФ).
СДНФ и СКНФ. Теорема единственности СКНФ и СДНФ.
Описание всех семантических следствий конечного списка пропозициональных формул через приведение к СКНФ.
Переключательные схемы и их функции истинности. Представление схем пропозициональными формулами.
Общее понятие исчисления(формальной аксиоматической теории).
Логическое исчисление и вывод в исчислении (формальной теории): алфавит, множество выражений и правил вывода исчисления.
Посылки и заключение правила вывода, понятие непосредственного следствия и определение вывода из множества выражений.
Отношение выводимости, вывод из гипотез и определение доказуемости в исчислении. Порождающие грамматики как пример формальных теорий.
Понятие о языке-объекте и метоязыке. Элементарные свойства отношения выводимости в формальной теории.
Построение исчисления высказываний. Его аксиомы и правила вывода.
Пример построения выводов в исчислении высказываний (ИВ).
Теорема дедукции в исчислении высказываний.
Применение теоремы дедукции к построению выводов. Допустимые правила в исчислении высказываний.
Теорема адекватности исчисления высказываний.
Непротиворечивые и противоречивые множества формул в исчислении высказываний. Теорема о непротиворечивости выполнимого множества формул.
Свойства непротиворечивых множеств формул в исчислении высказываний. Непротиворечивое множество аксиом в исчислении высказываний.
Нумерация пропозициональных формул по Геделю.
Теорема о расширении непротиворечивого множества до максимально непротиворечивого множества до максимально непротиворечивого множества.
Теорема о выполнимости максимально непротиворечивого множества.
Теорема о полноте исчисления высказываний и некоторые её следствия.
Понятие независимости формулы от множества формул. Пример зависимых и независимых пропозициональных формул.
Понятие о многозначных логиках. Примеры трехзначных логик.
Метод многозначных логик в доказательстве независимости аксиом исчисления высказываний.
Логика Предикатов.
Суждения, переменные высказывания и высказывательные формулы. Ковекторы в суждения. Примеры предикатов на наборе предметных областей.
Определение предиката и его множество истинности.
Логические операции над предикатами: логические связки и квантификации.
Теоретико-множественный смысл логических связок и кванторов.
Символическая запись суждений, выраженных предложением с кванторами.
Алфавит языка логики предикатов и его сигнатура: переменные, константы, функциональные и предметные символы, логические связки и кванторы.
Индуктивное определение термов в логике предикатов. Примеры термов. Атомарные термы и функциональная сложность терма.
Определение формул языка логики предикатов. Индуктивное построение множества формул на основе атомарных формул. Понятие логической сложности формулы.
Подтермы термов и подформулы формул. Область действия кванторных приставок в формуле. Способы вхождения предметных переменных в формулы. Параметры формулы и замкнутые формулы. Примеры суждений записываемых замкнутыми формулами.
Определение и примеры интерпретаций языка логики предикатов, конечные и бесконечные предметные области интерпретации.
Заполнения предметных переменных в предметной области интерпретации и значения термов при заданном заполнении.
Определение истинностного значения формулы в интерпретации при заданном заполнении. Примеры вычисления истинностных оценок формул в различных интерпретациях.
Классификация формул по их истинностным значениям. Отношение семантического следования. Семантическое следствие множества формул.
Семантические свойства истинности. Примеры логически общезначимых формул.
Семантическая равносильность формул логики предикатов. Список основных равносильностей.
Предваренные нормальные формы. ПНФ данной формулы и теорема о приведении к ПНФ. Алгоритм приведения к ПНФ.
Построение исчисления предикатов (ИП): алфавит, язык, аксиомы и правила вывода в ИП.
Выводимость из множества формул в ИП, доказуемость формулы в ИП. Теорема адекватности ИП.
Теореме дедукции в Исчислении предикатов.
Противоречивые и непротиворечивые множества формул в ИП. Непротиворечивость выполнимых множеств формул. Доказуемость любой формулы в противоречивой теории.
Теорема Геделя о полноте в логике предикатов.
Алгоритмические модели (эффективная вычислимость).
Понятие конструктивного объекта и интуитивное определение понятия «алгоритм». Слова в алфавитах как конструктивные объекты.
Эвристика модели Тьюринга: неформальное описание машины Тьюринга. Входной алфавит, алфавит внутренних состояний и команды машины Тьюринга.
Строгое определения машины Тьюринга и задание машины посредством тройки функций.
Определение конфигурации машины Тьюринга и отношение следования на множестве конфигураций. Начальное состояние и начальная конфигурация. Определение заключительной конфигурации. Протокол вычисления на машине Тьюринга.
Применимость и неприменимость машины Тьюринга к слову во входном алфавите. Словарная функция, задаваемая машиной Тьюринга. Определение вычислимой по Тьюрингу словарной функции и примеры вычислимых функций.
Вычислимость функций натурального аргумента в унарной кодировке натуральных чисел. Программа для функций сложения и следования. Вычислимость копировальной машины Тьюринга.
Характеристическая функция подмножества и определение разрешимого подмножества. Пример разрешимых подмножеств.
Полухарактеристическая функция подмножества и определение перечислимого подмножества. Примеры перечислимых подмножеств.
Теорема Поста о разрешимости перечислимого множества, если его дополнение перечислимо.
Вычислимые по Тьюрингу предикаты и конструкции вычислимых функций.
Нумерация машин Тьюринга и вычислимых по Тьюрингу функций. Разрешимые и перечислимые языки.
Проблемы самоприменимости и остановки, теоремы об их алгоритмической неразрешимости.
Тезис Черча-Тьюринга.
Алгоритмическая модель вычислимости С. Клини – частично-рекурсивные функции. Основные функции. Операторы суперпозиции и схемы примитивной рекурсии.
Определение и примеры примитивно-рекурсивных функций: сумма, произведение, max, min, усеченная разность, многочлены с целыми коэффициентами.
Оператор минимизации и определение частично-рекурсивных функций. Пример частично-рекурсивной, но не примитивно-рекурсивной функции.
Теорема о совпадении класса вычислимых по Тьюрингу функций и класса частично-рекурсивных функций.
Список литературы.
А.Н. Колмогоров, А.Г. Драгалин «Введение в математическую логику», М., изд. МГУ, 1982.
Э. Мендельсон «Введение в математическую логику», М., изд. «Наука», 1984.
А.И. Мальцев «Алгоритмы и рекурсивные функции», М., изд. «Наука», 1965.
С.Г. Гиндикин «Алгебра логики в задачах», М., изд. «Наука», 1972.
Дж. Булос, Р. Джеффри «Вычислимость и логика», М., изд. «Мир», 1994.
Г. Метакидес, А. Нерроу «Принципы логики и логического программирования», И., изд. «Факториал», 1998.
А.С. Герасимов «Курс математической логики и теории вычислимости», С.-Пб., изд. «Лема», 2011.
И. Лавров, А. Максимова «Сборник задач по теории множеств, математической логике и теории алгоритмов».
Н.К. Верещагин, А. Шень «Лекции по математической логике и теории алгоритмов», часть 2 «Языки и исчисления», часть 3 «Вычислимые функции», МЦНМО, 2002.
Д. Грис «Наука программирования», М., изд. «Мир», 1984(гл.1,2).
|