Зачет по матлогике

Зачет

Математическая логика 2012

Уровень А (Формулировки без доказательства)

Высказывания: простые, сложные, примеры высказываний. Истинностное значение высказывания.

Дать определение конъюнкции и импликации

Дать определение дизъюнкции и эквиваленции.

Определение формулы алгебры высказываний.

Свойство коммутативности и дистрибутивности. Какие логические связки им удовлетворяют?

Свойство ассоциативности и идемпотентности. Какие логические связки им удовлетворяют?

Отрицание высказывания. Снятие двойного отрицания. Правила де Моргана.

Какое рассуждение называется логичным?

Равносильные формулы. Формулы поглощения и расщепления.

Тавтология и противоречие. Свойства констант.

Двойственная формула. Принцип двойственности.

Проблема разрешимости в логике высказываний. Определение КНФ. Как проверить, что формула является тавтологией с помощью КНФ?

Проблема разрешимости в логике высказываний. Определение ДНФ. Как проверить, что формула является противоречием с помощью ДНФ?

Определение аксиоматической теории (4 пункта).

Определение вывода в исчислении высказываний.

Правила подстановки и m. p.

Теорема дедукции.

Правила силлогизма и разъединения посылок.

Правила перестановки и соединения посылок.

Полнота и непротиворечивость аксиоматической теории.

Определение предиката. Предметное множество и предметные переменные.

Операции над предикатами. Связывание кванторами.

Интерпретация формулы. Равносильность формул в данной интерпретации.

Равносильность формул на множестве и в логике предикатов. Перенос квантора через отрицание.

Правила вынесения квантора за скобки.

Приведенная и нормальная формы формул

Правило резолюций

Алгоритм метода резолюций в логике высказываний

Алгоритмы.

Элементарные рекурсивные функции

Оператор .

Общая схема примитивной рекурсии для функции 1 переменной.

Общая схема примитивной рекурсии для функции 2 переменных.

Оператор минимизации для функции одной переменной.

Какая функция называется примитивно-рекурсивной.

Какая функция называется частично-рекурсивной.

Какая функция называется общерекурсивной.

Тезисы Черча, Тьюринга и Маркова

Функции информационной ленты машины Тьюринга.

Функции считывающей-записывающей головки машины Тьюринга.

Функции управляющего устройства машины Тьюринга.

Внешний алфавит и внутренние состояния машины Тьюринга.

Конфигурация на ленте машины Тьюринга.

Команда машины Тьюринга.

Программа машины Тьюринга.

Применимость и неприменимость машины Тьюринга к данному слову.

Произведение машин Тьюринга.

Итерация машины Тьюринга по паре состояний.

Разветвление машины Тьюринга.

Схемы машин Тьюринга.

Кодирование чисел и наборов чисел для машин Тьюринга. Программа вычисления 0(x).

Вычислимость по Тьюрингу.

Вычислимость элементарных рекурсивных функции. Программа для S(x).

Программа вычисления

Логическая схема Ляпунова: типы операторов, условные обозначения, принцип работы.

Пример логической схемы Ляпунова для произведения и итерации машин Тьюринга.

Нормальный алгоритм Маркова: алфавит, подстановка, правила очередности применения подстановок. Пример алгоритма Маркова.

ВС( доказать)

Свойства двойственных формул. Принцип двойственности Теорема1 исчисления высказываний Теорема 2 исчисления высказываний Доказать теорему Доказать теорему Доказать теорему Правило силлогизма Теорема 3 исчисления высказываний Правило перестановки Теорема 4 исчисления высказываний Правила с конъюнкцией Теорема 5 исчисления высказываний Правило соединения посылок Теорема 6 (а) исчисления высказываний Правило разъединения посылок Теорема 6 (б) исчисления высказываний Равносильные преобразования с кванторами: перенос квантора через отрицание, вынос квантора за скобки Доказать примитивную рекурсивность функций Доказать неразешимоесть проблемы самоприменимостимости и применимости к входному слову для машин Тьюринга Схема Ляпунова для вычисления