Учебно-методический комплекс дисциплины «Математическая логика и теория алгоритмов»

Список основной литературы

Список дополнительной литературы

1. 
   Акимов, О.Е. Дискретная математика: логика, группы, графы / О.Е. Акимов, М.: Лаборатория Базовых Знаний, 2003. 376 с., 30 экз.
   
2. 
   Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.А. Максимова. М.: ФИЗМАТЛИТ, 2004. 256 с., 30 экз.
   
3. 
   Новиков, Ф.А. Дискретная математика для программистов / Ф.А. Новиков. СПб.: Питер, 2003. 301 с., 31 экз.
   
4. 
   Судоплатов, С.В. Математическая логика и теория алгоритмов / С.В. Судоплатов, Е.В. Овчинникова. М: Инфра-М, 2004. 224 с., 30 экз.
   

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. 
    Действия над машинами Тьюринга: композиция и разветвление.
    
31. 
    Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи.
    
32. 
    Классы задач P и NP. NP – полные задачи. Понятие сложности вычислений; эффективные алгоритмы.
    

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

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 с.
    

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. 
    Построение машин Тьюринга, вычисляющих заданные функции и осуществляющих определённые преобразования начальных слов.
    

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. 
    Формальная аксиоматическая теория: алфавит, аксиомы, правила вывода.
    
31. 
    Основные понятия теории доказательств: гипотеза, следствие, вывод, теорема, разрешимая и неразрешимая теория.
    
32. 
    Аксиоматическая теория исчисления высказываний: система аксиом и правила вывода.
    
33. 
    Теорема дедукции в исчислении высказываний.
    
34. 
    Аксиоматическая теория исчисления предикатов первого порядка: система аксиом и правила вывода.
    
35. 
    Теорема дедукции в исчислении предикатов.
    
36. 
    Теорема о полноте теории исчисления высказываний.
    
37. 
    Теорема о непротиворечивости теории исчисления высказываний.
    
38. 
    Теорема о непротиворечивости теорий первого порядка.
    
39. 
    Эффективная вычислимость функции.
    
40. 
    Примитивная рекурсия.
    
41. 
    Примитивно-рекурсивная функция.
    
42. 
    Оператор минимизации.
    
43. 
    Частично-рекурсивная функция.
    
44. 
    Общерекурсивная функция.
    
45. 
    Тезис Чёрча.
    
46. 
    Машина Тьюринга, её компоненты и принцип работы.
    
47. 
    Конфигурация машины Тьюринга.
    
48. 
    Функция, вычислимая по Тьюрингу.
    
49. 
    Тезис Тьюринга.
    
50. 
    Композиция машин Тьюринга.
    
51. 
    Разветвление машин Тьюринга.
    
52. 
    Классы задач P и NP.
    
53. 
    NP – полная задача.
    
54. 
    Понятие сложности вычислений.
    
55. 
    Эффективный алгоритм.