Перечень экзаменационных вопросов

1. Высказывание как первичное понятие алгебры логики. Основные операции над высказываниями.
2. Пропозициональные связки. Истинностные функции. Формулы алгебры высказываний, их виды. Истинностные таблицы формул алгебры высказываний.
3. Полные системы связок. Понятие о нечётких и модальных логиках.
4. Понятие булевой функции (функции двузначной логики). Элементарные булевы функции, логические связки.
5. Формулы алгебры логики, функции, их реализующие. Истинностные таблицы формул алгебры логики.
6. Основные эквивалентные формулы алгебры логики.
7. Элементарная конъюнкция и элементарная дизъюнкция.
8. Дизъюнктивная нормальная форма (ДНФ). Алгоритм приведения булевой функции к ДНФ. Теорема о дизъюнктивном разложении булевой функции.
9. Совершенная дизъюнктивная нормальная форма (СДНФ). Алгоритмы приведения булевой функции к СДНФ.
10. Конъюнктивная нормальная форма (КНФ). Алгоритм приведения булевой функции к КНФ. Теорема о конъюнктивном разложении булевой функции.
11. Совершенная конъюнктивная нормальная форма (СКНФ). Алгоритмы приведения булевой функции к СКНФ.
12. Полиномы Жегалкина. Алгоритмы приведения булевой функции к полиному Жегалкина.
13. Двойственность. Принцип двойственности.
14. Полные системы логических связок. Теорема Поста о функциональной полноте. Проблемы полноты и разрешимости.
15. Релейно-контактные схемы, их математическое описание и методы построения.
16. Кванторные операции как обобщения операций конъюнкции и дизъюнкции. Предикаты. Синтаксис и семантика языка логики предикатов. Формулы логики предикатов. Свободные и связанные переменные.
17. Интерпретации, выполнимость и общезначимость формул логики предикатов. Эквивалентные формулы логики предикатов.
18. Формальная аксиоматическая теория, её задание и компоненты. Основные понятия теории доказательств. Аксиоматическая теория исчисления высказываний. Теорема дедукции.
19. Теоремы теории исчисления высказываний. Теории исчисления высказываний Клини, Гильберта-Аккермана, Россера, интуиционистская.
20. Аксиоматическая теория исчисления предикатов первого порядка. Правила вывода теории исчисления предикатов. Теорема дедукции.
21. Теоремы теории исчисления предикатов. Примеры теорий первого порядка.
22. Метод резолюций в логике предикатов.
23. Метаязык и метатеория. Проблемы разрешимости, полноты и непротиворечивости формальных аксиоматических теорий. Теоремы о полноте и непротиворечивости теории исчисления высказываний.
24. Непротиворечивость теорий первого порядка. Теорема Гёделя о полноте.
25. Эффективная вычислимость функции. Уточнение понятия алгоритма. Разрешимые и перечислимые множества. Примитивная рекурсия. Примитивно-рекурсивные функции. Примитивная рекурсивность некоторых арифметических функций.
26. Оператор минимизации. Частично-рекурсивные функции. Общерекурсивные функции. Общерекурсивность некоторых арифметических функций. Тезис Чёрча.
27. Словарные множества и функции. Словарная примитивная рекурсия.
28. Машина Тьюринга, её компоненты и принцип работы. Конфигурация машины Тьюринга. Распознавание применимости машины Тьюринга к начальной конфигурации.
29. Понятие функции, вычислимой по Тьюрингу. Машины Тьюринга, вычисляющие некоторые арифметические функции. Тезис Тьюринга.
30. Действия над машинами Тьюринга: композиция и разветвление.

ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА ДЛЯ ПРЕПОДАВАТЕЛЯ

1. Алферова, З.В. Теория алгоритмов / З.В. Алферова. М.: Статистика, 1973. 165 с.
2. Аляев, Ю.А. Дискретная математика и математическая логика / Ю.А. Аляев, С.Ф. Тюрин. М.: Финансы и статистика, 2006. 368 с.
3. Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. М.: Мир, 1979. 535 с.
4. Булос, Дж. Вычислимость и логика / Дж. Булос, Р. Джеффри. М.: Мир, 1994. 396 с.
5. Владимиров, Д.А. Теория булевых алгебр / Д.А. Владимиров. Спб.: Изд-во Санкт-Петербургского университета, 2000. 616 с.
6. Гаврилов, Г.П. Задачи и упражнения по дискретной математике / Г.П.Гаврилов, А.А.Сапоженко. М.: ФИЗМАТЛИТ, 2004. 416 с.
7. Гильберт, Д. Основания математики. Логические исчисления и формализация арифметики / Д. Гильберт, П. Бернайс. М.: Наука, 1982. 556 с.
8. Гильберт, Д. Основания математики. Теория доказательств / Д. Гильберт, П. Бернайс. М.: Наука, 1982. 652 с.
9. Гиндикин, С.Г. Алгебра логики в задачах / С.Г. Гиндикин. М.: Наука, 1972. 288 с.
10. Гладкий, А.В. Математическая логика / А.В. Гладкий. М.: Рос. гос. гуманит. ун-т, 1998. 479 с.
11. Гудстейн, Р.Л. Математическая логика / Р.Л. Гудстейн. М.: ИЛ, 1961. 162 с.
12. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. М.: Мир, 1982. 416 с.
13. Драгалин, А.Г. Математический интуиционизм. Введение в теорию доказательств / А.Г. Драгалин. М.: Наука, 1979. 256 с.
14. Ершов, Ю.Л. Математическая логика / Ю.Л. Ершов, Е.А. Палютин. М.: Наука, 1979. 320 с.
15. Игошин, В.И. Математическая логика и теория алгоритмов / В.И. Игошин. М.: Академия, 2004, 448 с.
16. Карри, Х. Основания математической логики / Х. Карри. М.: Мир, 1969. 568 с.
17. Клини, С.К. Введение в метаматематику / С.К.Клини. М.: ИЛ, 1957. 529 с.
18. Клини, С.К. Математическая логика / С.К.Клини. М.: УРСС, 2005. 482 с.
19. Колмогоров, А.Н. Математическая логика / А.Н. Колмогоров, А.Г. Драгалин. М.: УРСС, 2006. 240 с.
20. Коваленко, С.И. Решение задач по математической логике с использованием элементарной алгебры / С.И. Коваленко. М.: ФИЗМАТЛИТ, 2004. 80 с.
21. Кук, В. Компьютерная математика / В. Кук, Г. Бейз. М.: Наука, 1990. 384 с.
22. Линдон, Р. Заметки по логике / Р. Линдон. М.: Мир, 1968. 128 с.
23. Мальцев, А.И. Алгоритмы и рекурсивные функции / А.И. Мальцев. М.: Наука, 1986. 368 с.
24. Марков, А.А. Теория алгорифмов / А.А. Марков, Н.М. Нагорный. М.: Наука, 1984. 432 с.
25. Марченков, С.С. Замкнутые классы булевых функций / С.С. Марченков. М.: ФИЗМАТЛИТ, 2000. 128 с.
26. Мендельсон, Э. Введение в математическую логику / Э. Мендельсон. М.: Наука, 1971. 320 с.
27. Новиков, П.С. Элементы математической логики / П.С. Новиков. М.: Наука, 1973. 400 с.
28. Новиков, П.С. Конструктивная математическая логика с точки зрения классической / П.С. Новиков. М.: Наука, 1977. 328 с.
29. Петер, Р. Рекурсивные функции / Р. Петер. М.: ИЛ, 1954. 264 с.
30. Роджерс, Х. Теория рекурсивных функций и эффективная вычислимость / Х. Роджерс. М.: Мир, 1972. 624 с.
31. Такеути, Г. Теория доказательств / Г. Такеути. М.: Мир, 1978. 412 с.
32. Успенский, В.А. Лекции о вычислимых функциях / В.А. Успенский. М.: Физматгиз, 1960. 492 с.
33. Фудзисава, Т. Математика для радиоинженеров. Теория дискретных структур / Т. Фудзисава, Т. Касами. М.: Радио и связь, 1984. 240 с.
34. Чень, Ч. Математическая логика и автоматическое доказательство теорем / Ч. Чень, Р. Ли. М.: Наука, 1983. 360 с.
35. Чёрч, А. Введение в математическую логику. Том 1 / А. Чёрч. М.: ИЛ, 1960. 488 с.
36. Шенфилд, Дж. Математическая логика / Дж. Шенфилд. М.: Наука, 1975. 528 с.
37. Яблонский, С.В. Функции алгебры логики и классы Поста / С.В. Яблонский, Г.П. Гаврилов, В.Б. Кудрявцев. М. Наука, 1966. 120 с.