Вопросы к зачету

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. Задачи P-класса, NP-класса и NP-полные задачи.

28. Эффективность алгоритмов.

29. Алгоритмы Магу.

30. Эффективность на примере алгоритмов сортировки.

31. Основные положения нечёткой логики.

32. Структура контроллера нечёткой логики.

33. Операции над нечеткими множествами

34. Нечеткий вывод по Мамдани.

35. Алгоритмические логики.

36. Основные понятия логики предикатов.

37. Операции в логике предикатов.

38. Кванторы в логике предикатов.

39. Доказательство истинности предикатных формул.

40. Предваренная, сколемовская и клаузальная формы.

41. Алгоритм получения клаузальной формы.

42. Теорема Робинсона и метод резолюций в логике предикатов.

43. Принцип логического программирования.

44. Темпоральные логики.

45. Темпоральные операторы и формальная верификация.

46. Алгоритмическая логика Хоара.

47. Аксиоматический метод для построения научной теории.

48. Метатеория и метаязык.

49. Метаматематика и формальный вывод.

50. Мышление и формальная логика.

Учебное издание Математическая логика и теория алгоритмов

Учебная программа

Составитель:

Архангельский Владимир Всеволодович

	Редактор: Петров И.Е.
	Корректор: Журавлева О.Н.
	Подписано в печать «__» _____ 20__г.
	Усл. печ. л. _____
	Тираж _______экз.
	Отпечатано на ризографе ВСЭИ
	Издательский орган ВСЭИ 610000 Киров, Большевиков, 91А тел./факс 67-02-35

15