1. Интуитивное понятие алгоритма и его основные характеристики

Вопросов к экзамену по математической логике для студентов групп ВИ-1-02, ВИ-2-02 (7 семестр)1.Интуитивное понятие алгоритма и его основные характеристики.2.Определение рекурсивных и частично рекурсивных функций. Соотношение между классами примитивно рекурсивных, общерекурсивных и частично рекурсивных функций.3.Примеры алгоритмически неразрешимых массовых задач. Примеры алгоритмически разрешимых и неразрешимых задач из алгебры и др. разделов математики.4.Понятие нормального алгоритма Маркова. Примеры. Композиция нормальных алгоритмов. Нормальные алгоритмы для реализации элементарных рекурсивных функций.5.Определение машины Тьюринга. Понятие универсальной машины . Определение машины Поста. Представление машиной Тьюринга машины Поста, представление машиной Поста машины Тьюринга. Принцип Тьюринга-Поста.6. Вычисление на машине Тьюринга элементарных рекурсивных функций.7. Алгебра высказываний и алгебра предикатов.8. Основные логические операции и их свойства. Понятие булевой алгебры.9.Алгебра высказываний и алгебра подмножеств как примеры булевых алгебр.10. Предикаты на множестве и их связь с отношениями. Логические операции над предикатами. Определение формулы алгебры предикатов. Выполнимые, тождественно истинные и тождественно ложные формулы.11.Равносильность формул, основные соотношения равносильности и их использование для упрощения формул.12. Существование для каждой формулы алгебры высказываний приведенной формы, дизъюнктивной и конъюнктивной нормальных форм.13.Понятие булевых функций и функций многозначной логики. Их представление формулами над заданной системой функций. Представление булевых функций формулами алгебры высказываний и многочленами Жигалкина.14. Замкнутые классы функций. Критерии полноты для булевых функций и функций многозначной логики. Псевдобулевы функции и их задание. Минимизация булевых функций.15.Общее понятие о логическом исчислении. Язык, аксиомы и правила вывода исчислений высказываний. Теорема дедукции. Непротиворечивость и полнота исчисления высказываний.16. Язык, аксиомы и правила вывода исчисления предикатов. Выводимость и доказуемость формул в исчислении предикатов. Вспомогательные правила вывода: правило силлогизма, правила умножения и разделения формул, правило умножения и разделения посылок, правило умножения заключений, правило перестановки посылок, правило контрапозиции, правила де Моргана, правила противоречия, закон исключения третьего.17. Теорема дедукции для замкнутой формулы.. Эквивалентность формул. Приведение формул к нормальным формам. Понятие об интерпретации исчисления предикатов..18. Непротиворечивость исчисления предикатов. Непротиворечивые, полные и выполнимые системы формул. Теорема Черча о неразрешимости исчислений предикатов.19. Подходы к оценкам сложности алгоритмов и вычислений. Модели вычислений. Сложность вычислений на машине Тьюринга. Свойства функций сложности. Нижние оценки. 20. Сложность распознавания симметрии слов. Сложность распознавания функциональной полноты системы булевых функций.(базовый учебник: Капитонова и…. Лекции по дискретной математике. М.2003)