Матлогика.Всё к экзамену / Список вопросов матлогика
.docxМатематическая логика и теория алгоритмов
I. Алгебра высказываний (АВ)
1. Высказывания. Примеры высказываний. Пропозициональные переменные. Определение основных логических операций.
2. Алфавит, язык, правильно построенные формулы (п.п.ф) АВ. Примеры п.п.ф.
3. Теорема о замене подформулы п.п.ф. АВ. Пример.
4. Теорема о подстановке формулы вместо пропорциональной переменной в п.п.ф. АВ. Пример.
5. Значение п.п.ф. АВ. Таблица истинности. Пример построения таблицы истинности. Выполнимые, опровержимые, тождественно истинные, тождественно ложные формулы АВ. Примеры.
6. Теорема о подстановке п.п.ф. вместо пропозициональной переменной в тождественно истинной формуле. Теорема о правиле modus ponens.
7. Эквивалентные формулы АВ. Пример.
8. Теорема о подстановке п.п.ф. вместо пропозициональной переменной в эквивалентные формулы АВ. Теорема о замене подформулы на эквивалентную формулу в п.п.ф. АВ.
9. Понятие формулы с тесными отрицаниями. Теорема об эквивалентной формуле с тесными отрицаниями.
10. Понятие д.н.ф., к.н.ф. Примеры. Теоремы о существовании: эквивалентной д.н.ф., эквивалентной к.н.ф.
11. Теоремы о виде: тождественно ложной д.н.ф., тождественно истинной к.н.ф.
12. Понятие с.д.н.ф., с.к.н.ф. Построение с.д.н.ф., с.к.н.ф по таблице истинности данной формулы.
13. Построение с.д.н.ф. по данной д.н.ф. Построение с.к.н.ф. по данной к.н.ф.
14. Условие существования с.д.н.ф., с.к.н.ф.
15. Понятие логического следствия в АВ. Содержательный пример. Непротиворечивые (выполнимые) и противоречивые (невыполнимые) множества посылок. Примеры. Установление факта логического следствия из данного множества посылок по таблице истинности.
16. Установление факта логического следствия из данного множества посылок путем определениям совместности соответствующей системы логических уравнений.
17. Основные теоремы о логическом следствии (сведение установления факта логического следствия из данного множества посылок к установлению факта логического следствия из другого множества посылок).
18. Основные теоремы о логическом следствии (сведение установления факта логического следствия из данного множества посылок к проверке тождественной истинности или тождественной ложности формул АВ).
II. Исчисление высказываний.
19. Схемы аксиом ИВ. Получение аксиом из схем аксиом ИВ. Пример. Правило вывода modus ponens. Пример применения.
20. Понятие доказательства в ИВ. Понятие исчисления.
21. Понятие доказательства из гипотез в ИВ.
22. Основные теоремы о доказуемости из гипотез в ИВ.
23. Теорема о дедукции в ИВ.
24. Понятие производного допустимого правила вывода в ИВ. Пример.
25. Технология доказательства с использование производных допустимых правил вывода: сведение к подзадачам. Пример.
26. Теорема о совпадении множества тождественно истинных формул АВ и доказуемых формул ИВ.
27. Связь между наличием факта логического следствия в АВ и доказуемостью из гипотез в ИВ.
28. Непротиворечивость ИВ.
III. Алгебра предикатов (АП).
29. Понятие алгебраической системы.
30. Алфавит и язык АП. Сигнатура. Понятие терма данной сигнатуры. Пример. П.п.ф. АП. Пример. Предложение. Пример.
31. Понятие алгебраической системы данной сигнатуры.
32. Свободные и связанные переменные. Термы, свободные для данной переменной в данной формуле.
33. Значение терма данной сигнатуры в алгебраической системе той же сигнатуры. Пример.
34. Значение п.п.ф. АП данной сигнатуры в алгебраической системе той же сигнатуры. Пример.
35.
Кванторы
как обобщения логических связок & и
.
36. Выполнимые формулы АП. Пример. Тождественно истинные формулы АП. Пример доказательства тождественной истинности.
37. Эквивалентные формулы АП. Пример.
38. Теорема о замене подформулы на эквивалентную подформулу в п.п.ф АП.
39. Теорема о подстановке п.п.ф. вместо атомной формулы в эквивалетные п.п.ф АП.
40. Пренексные нормальные формы (п.н.ф.). Теорема о существовании эквивалентной п.н.ф.: алгоритм получения эквивалентной п.н.ф.
41. Сколемовская стандартная форма (с.с.ф.): основная теорема, функции Сколема, следствие основной теоремы.
42. Сколемовская стандартная форма (с.с.ф.): процедура построения, алгоритм Сколема, соотношение свойств невыполнимого предложения и его с.с.ф.
43. Понятие логического следствия в АП. Пример. Выполнимые и невыполнимые множества посылок в АП.
IV. Исчисление предикатов (ИП).
44. Схемы аксиом ИП. Получение аксиом из схем аксиом. Пример. Правила вывода ИП. Примеры применения.
45. Доказуемость и доказательство в ИП. Примеры доказательств.
46. Теоремы о доказуемых в ИП формулах.
47. Доказательство из гипотез в ИП. Пример.
48. Основные теоремы о доказуемости из гипотез в ИП.
49. Теорема о дедукции в ИП.
50. Производные допустимые правила вывода в ИП: доказательство правил, содержащих кванторы.
51. Формулировка теоремы Геделя (о полноте) и теоремы адекватности.
V. Принцип резолюции.
52. Понятие резольвенты в АВ. Пример.
53. Теорема о свойстве резольвенты.
54. Основная теорема.
55. Формулировка принципа резолюции в АВ.
56. Схема применения принципа резолюции для доказательства факта логического следствия в АВ. Пример применения принципа резолюции для доказательства факта логического следствия в АВ.
VI. Теория Алгоритмов.
57. Схема построения модели алгоритма.
58. Характерные черты алгоритма.
59. Элементы модели алгоритма. Основные предположения об элементах модели алгоритма.
60. Устройство машины Тьюринга.
61. Комбинация машин Тьюринга: композиция, разветвление, разветвление с циклом.
62. Вычислимые по Тьюрингу функции.
63. Разрешимые (рекурсивные) множества. Пример. Рекурсивно перечислимые множества. Пример.
64. Алгоритмически неразрешимые проблемы. Пример. Тезис Тьюринга.
65. Схема построения алгоритмической модели в виде частично рекурсивных функций. Основные элементы алгоритмической модели в виде частично рекурсивных функций.
66. Простейшие функции. Оператор суперпозиции.
67. Схема и оператор примитивной рекурсии.
68. Оператор минимизации.
69. Примитивно рекурсивные функции. Общерекурсивные функции. Частично рекурсивные функции. Соотношение между классами примитивно рекурсивных функций, общерекурсивных и частично рекурсивных функций.
70. Тезис Чёрча (Чёрча-Клини). Соотношение между двумя моделями алгоритма (машиной Тьюринга и рекурсивными функциями).