Реферат: 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)