9.3. Содержание и формы промежуточной аттестации

Формы аттестации по дисциплине: экзамен.

Вопросы к экзамену:

1. Высказывания. Логические операции над высказываниями.

2. Понятие булевой функции. Число булевых функций от n переменных. Булевы функции от двух переменных. Связь между ними.

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. m-опе­ра­ция (опе­ра­ция ми­ни­ми­за­ции). Час­тич­но ре­кур­сив­ное опи­са­ние фун­к­ции. Час­тич­но ре­кур­сив­ная фун­кция. При­ме­ры час­тич­но ре­кур­сив­ных фун­кций. Об­ще­ре­кур­сив­ная фун­кция. При­ме­ры об­ще­ре­кур­сив­ных фун­кций.

28. Ма­ши­на Тью­рин­га. Опе­ра­ции над ма­ши­на­ми Тью­рин­га (опе­ра­ция ком­по­зи­ции, опе­ра­ция вет­вле­ния, опе­ра­ция за­цик­ли­ва­ния). Гё­де­ле­ва ну­ме­ра­ция ма­шин Тью­рин­га.

29. Фун­кция, вы­чис­ли­мая по Тью­рин­гу. До­ка­за­те­ль­ст­во су­ще­ст­во­ва­ния фун­к­ций, не­вы­чис­ли­мых по Тью­рин­гу. При­мер не­вы­чис­ли­мой по Тью­рин­гу фун­кции.

30. При­ме­ры ал­го­рит­ми­че­с­ки не­раз­ре­ши­мых проблем (про­бле­ма рас­по­зна­ва­ния са­мо­при­ме­ни­мо­сти, про­бле­ма при­ме­ни­мо­сти).

29