Исчисление высказываний (теория L)

В качестве первого примера формальной аксиоматической теории

рассмотрим исчисление высказываний - теорию L.

1. Символами теории L являются (Только  перевернутое), ⇒,), (и буквы Аi с

целыми положительными числами в качестве индексов: А1, А2, А3,... Символы

, ⇒ будем называть примитивными связками, а А1, А2, А3,... -

пропозициональными буквами.

2. Формулы теории L определим индуктивным образом:

1) все буквы А1, А2, А3,... суть формулы;

2) если А и В формулы, то ( А) и (А ⇒ В) тоже формулы;

3) выражение теории L является формулой только тогда, когда это следует из

1) и 2).

Будем считать, что

А& В служит обозначением для формулы ( (А⇒ ( В))),

А∨ В служит обозначением для формулы (( А)⇒ В),

А≡ В служит обозначением для формулы ( ((А⇒ В)⇒ ( (В⇒ А)))).

Из определения формул видно, что всякая формула из L есть

пропозициональная форма, построенная из пропозициональных букв А1, А2... с

помощью связок  и ⇒.

Будем придерживаться тех же правил опускания скобок в формулах, что и

раньше для пропозициональных форм.

3. Аксиомы теории L. Каковы бы ни были формулы А, В и С теории L,

следующие формулы суть аксиомы теории L:

А1: А⇒ (B⇒ А);

A2: (А⇒ (B⇒ C))⇒ ((А⇒ B)⇒ (А⇒ C));

A3: ( B⇒  А)⇒ (( B⇒ А)⇒ B).

Заметим, что А1 - А3 являются схемами аксиом, т.е. указывают, как строятся

аксиомы для произвольных формул А, В и С. В силу произвольности фор-мул

А, В и С схемы аксиом А1-А3 порождают бесчисленное множество аксиом.

Легко убедиться, например, с помощью таблиц истинности, что каждая аксио-

ма полученная по схемам А1-А3 является тавтологией.

4. Единственным правилом вывода теории L служит правило modus ponens: В

есть непосредственное следствие А и А⇒ В. Это правило сокращенно

обозначают МР.

Modus ponens в переводе означает «правило отделения». Отметим, что

теорема 1.1 утверждает, что если А и А⇒ В тавтологии, то и В тоже

тавтология. Следовательно, правило modus ponens из тавтологий получает

тавтологию. Очевидно, правило МР означает, что А, А⇒ В − В.

Таким образом, задали некоторую формальную аксиоматическую теорию,

которая и называется исчислением высказываний. Рассмотрим некоторые до-

казательства в этой теории.

1.(30) Основные понятия МЛиТА................................................................................................................ 1

2. История развития теории алгоритмов...................................................................................................... 2

3. Роль алгоритма в науке и технике............................................................................................................ 4

4. Понятие алгоритма..................................................................................................................................... 5

5. Алгоритмический процесс....................................................................................................................... 6

6. Основные вопросы теории алгоритмов................................................................................................... 7

7. Классификация алгоритмов...................................................................................................................... 8

8. Свойства алгоритмов................................................................................................................................ 9

9. Понятие предиката.................................................................................................................................. 13

10. Интерпретация. Модель......................................................................................................................... 15

12. Нормальные алгорифмы Маркова........................................................................................................ 17

13. Гипотеза Черча....................................................................................................................................... 18

14. Машина Тьюринга.................................................................................................................................. 19

15. Рекурсивные функции........................................................................................................................... 21

16. Алгоритмически неразрешимые проблемы........................................................................................ 22

17. Понятие о сложности............................................................................................................................ 24

18. Временная и вычислительная сложность алгоритмов....................................................................... 26

19. Понятие Р- и NP-задач.......................................................................................................................... 28

20. NP-трудные и NP-полные задачи......................................................................................................... 31

21. Темпоральные логики. Нечеткая и модальные логики................................................................... 32

Модальные логики...................................................................................................................................... 34

24. Дедуктивные теории............................................................................................................................. 38

25. Свойства дедуктивных теорий............................................................................................................. 40

26. Формальные аксиоматические теории................................................................................................ 41

27. Свойства выводимости......................................................................................................................... 42

31.(38) логические функции........................................................................................................................ 43

34. Кванторы................................................................................................................................................ 44

39. Алгоритм Сортировка слиянием......................................................................................................... 46

40. Алгоритм Пузырьковая сортировка.................................................................................................... 48

41. Алгоритм Сортировка вставками......................................................................................................... 49

42. Алгоритм Сортировка Шейкером....................................................................................................... 50

43. Алгоритм Быстрая сортировка............................................................................................................. 52

47. Логика высказываний........................................................................................................................... 56

48. Булева алгебра и основные логические тождества............................................................................. 57

Основные тождества.................................................................................................................................... 57

49. Пропозициональные буквы, связки и формы (формулы логики высказываний). Построение

таблиц истинности...................................................................................................................................... 59

50. Исчисление высказываний (теория L)................................................................................................ 61

62__