Исчисление высказываний

Логическим исчислением принято называть синтаксическую (т.е. формализованную аксиоматическую) теорию математической логики. Описание всякого исчисления включает:

1) описание алфавита, т.е. множества символов, используемых для построения формул теории;

2) описание языка, т.е. правил построения допустимых последовательностей символов (слов) в алфавите, называемых формулами;

3) задание системы аксиом – некоторого множества истинных формул, называемых аксиомами;

4) определение правил вывода, позволяющих из одних истинных формул получать другие формулы рассматриваемой синтаксической теории.

Исчисление высказываний – это аксиоматическая логическая система, адекватная алгебре высказываний. Опишем это исчисление.

В качестве алфавита исчисления высказываний возьмем следующее множество символов:

1) счетное множество высказывательных переменных, обозначаемых прописными латинскими буквами с индексами и без них;

2) символы логических операций ;

3) скобки (,).

Вместе с символами алфавита будем использовать и метасимволы: латинские буквы жирного шрифта для обозначения формул и знак = для обозначения формул метасимволами.

Множество формул обычно задается индуктивным определением. Допустимыми последовательностями символов или словами в языке исчисления высказываний являются формулы алгебры высказываний. Пункты 1 и 2 этого определения (см. методические указания “Алгебра высказываний. Булевы функции”) определяют элементарные формулы, а п. 3 – механизм образования новых формул.

Следует заметить, что в исчислении высказываний не разрешается опускать скобки для операций с большим приоритетом, что допустимо в алгебре высказываний. Так, например, формула алгебры высказываний не является формулой исчисления высказываний, ее следует записать, как , в дальнейшем изложении мы будем опускать лишь внешние скобки.

Следующим шагом в описании исчисления высказываний будет выделение класса формул, которые будем называть истинными или доказуемыми в исчислении высказываний. Это определение имеет такой же рекуррентный характер, как и определение формулы.

Сначала определим исходные истинные формулы, называемые аксиомами. В качестве системы аксиом примем следующие формулы (аксиоматика П.С.Новикова).

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

После этого определим правила, позволяющие из истинных формул образовывать новые. Эти правила, мы будем называть правилами вывода. Образование истинной формулы из исходных истинных формул или аксиом путем применения правил вывода будем называть выводом данной формулы из аксиом.

Определим правила вывода, которые являются отношениями на множестве формул.

1. Правило подстановки.

Пусть U – формула, содержащая высказывательную переменную A. Тогда если U – истинная формула в исчислении высказываний, то, заменяя в ней переменную A всюду, куда она входит, произвольной формулой B, мы также получим истинную формулу.

2. Правило заключения (modus ponens).

Если U и U ® B истинные формулы в исчислении высказываний, то B также истинная формула.

Указанием аксиом и правил вывода мы полностью определили понятие истинной, или выводимой в исчислении высказываний, формулы. Пользуясь правилами вывода, мы можем, исходя из аксиом, конструировать новые истинные формулы и получать, таким образом, каждую истинную формулу. Формула B называется доказуемой (теоремой в исчислении высказываний), если существует конечная последовательность формул

B₁, B₂,..., B_t, (4)

в которой каждая из формул B_i является либо аксиомой, либо, получена по правилам вывода из некоторых предыдущих формул последовательности (4). Эта последовательность называется доказательством формулы (теоремы). Рассмотрим примеры таких доказательств.

Задание 1. Показать, что формулы:

1) ;

2)

истинны в исчислении высказываний.

Решение.

1) Формула

является результатом подстановки в аксиому 2 высказывательной переменной A вместо C. Так как посылка полученного следования есть аксиома 1, то, применяя правило заключения, получим, что

истинная формула.

2) В соответствии с правилом подстановки, заменив все вхождения переменной A в аксиоме 5 на формулу , получим

.

Так как посылка этой аксиомы является аксиомой 4, то по правилу заключения формула

является истинной формулой. Заменим в этой формуле высказывательную переменную C на A

.

Снова воспользовавшись правилом заключения, что возможно, так как посылка истинной формулы является аксиомой 3, получим требуемую формулу

.

Замечание. Рассмотренная нами аксиоматика не является единственно возможной. Приведем и другие, эквивалентные данной, системы аксиом.

I. Операции: (аксиоматика С.Клини (1952)).

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

II. Операции: (аксиоматика Россера (1953)).

1.

2.

3.

III. Операции: (аксиоматика Д.Гильберта и Аккермана (1938)).

1.

2.

3.

4.

IV. Операции: ®, Ø (аксиоматика Лукасевича).

1.

2.

3.

Как легко видеть, вывод истинной в исчислении высказываний формулы непосредственно из аксиом с использованием правил вывода является достаточно громоздкой процедурой, которую хотелось бы упростить. Для этого определим понятие выводимости и производные правила вывода, ключевым среди которых является теорема дедукции, которые позволят нам устанавливать выводимость различных формул без непосредственного вывода этих формул.

Мы будем говорить, что формула B выводима из формул U₁, U₂,..., U_n в исчислении высказываний, если формулу B можно вывести только путем правила заключения, приняв за исходные формулы U₁, U₂,..., U_n и все истинные в исчислении высказываний формулы.

Точное определение выводимости формулы в исчислении высказываний имеет вид: формула B выводима из формул U₁, U₂,..., U_n, называемых исходными, что записывается символически как

U₁, U₂,..., U_n ú- B,

если существует такая конечная последовательность формул (4), что B_t есть B и для каждой формулы B_i выполнено одно из условий:

1) B_i есть посылка или теорема исчисления высказываний;

2) B_i получена из некоторых предыдущих формул последовательности (4) по правилу заключения.

Последовательность (4) называется в этом случае выводом формулы B из системы посылок U₁, U₂,..., U_n.

Рассмотрим пример вывода формулы.

Задание 2. Доказать, что A ú- .

Решение. Для данного примера система посылок содержит 1 формулу U₁ = A, а выводимая формула B = . Построим вывод этой формулы.

1) B₁ = A

2) B₂ = - аксиома 1

3) B₃ = B = - получено из B₁ и B₂ в силу правила заключения.

Заметим, что если посылки являются аксиомами или теоремами исчисления высказываний, то класс выводимых из них формул совпадает с классом всех истинных формул, выводимых из любой системы посылок.

Выводимость формулы из системы посылок отличается от доказательства теоремы в исчислении высказываний тем, что здесь допускается использование только правила заключения. Но при выводе формулы разрешается использовать любую теорему исчисления высказываний, для получения которой может применяться правило подстановки.

Из каждой формулы U с помощью правила подстановки, производящего замену высказывательных переменных в этой формуле любыми формулами, может быть получено бесконечное множество формул. Это множество формул называется схемой формулы U и обозначается выражением, полученным заменой в формуле U всех входящих в нее высказывательных переменных метасимволами .

Например, из формулы

возникает схема формул

. (5)

Этой схеме принадлежит формула

.

Новые схемы формул можно получить заменой ее метасимволов схемами формул. Эти схемы выделяют некоторое подмножество формул из множества формул, принадлежащих исходной схеме. Например, из схемы (5) можно получить схему формул

. (6)

Формула принадлежит как схеме формул (5), так и (6).

Для формул, являющимися аксиомами или теоремами, схемы формул называются соответственно схемами аксиом или схемами теорем. Схемами аксиом являются:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

Таким образом, при выводе формулы из системы посылок (которая может быть и пустой) будут использоваться схемы аксиом и правило заключения, правило подстановки применяется неявно в схеме аксиом.

Наряду с правилом заключения, мы будем использовать и другие правила образования истинных и выводимых формул. Эти правила являются производными от основных и используются для сокращения многократного применения основных правил.

Перечислим основные из производных правил вывода. Как и прежде, метасимволы являются произвольными формулами, а через T обозначим конечное множество формул (возможно пустое).

1. Правило повторения посылки.

T, ú-

2. Правило введения посылки.

Если T ú- , то T, ú- .

3. Правило удаления посылки.

Если T, ú- и T ú- , то T ú- .

4. Правило силлогизма.

Если T ú- ,..., T ú- и ú- , то T ú- .

5. Правило введения импликации.

Если T, ú- , то T ú- .

Это весьма важное свойство называют еще теоремой дедукции. Учитывая, что - конечное множество формул, свойство 5 можно сформулировать в следующем виде:

Теорема дедукции. Если

ú- B,

то

ú- .

6. Правило удаления импликации.

Если T ú- , то T, ú- .

7. Правило введения конъюнкции.

T, ú- .

8. Правило удаления конъюнкции.

T, ú- ,

T, ú- .

9. Правило введения дизъюнкции.

T, ú- ,

T, ú- .

10. Правило удаления дизъюнкции.

Если T, ú- и T, ú- , то T, ú- .

11. Правило введения отрицания.

Если T, ú- и T, ú- , то T ú- .

12. Правило удаления отрицания.

T, ú-

13. Правило контрапозиции.

Если T, ú- , то T, ú- .

Правила 1-13 называют обычно правилами естественного вывода, а вывод формулы из системы посылок, при котором используются эти правила, - естественным выводом.

Рассмотрим примеры вывода формул с использованием правил естественного вывода. Несложно доказать, таким образом, справедливость основных эквивалентностей алгебры высказываний. Всюду далее, строя вывод формулы, будем рядом с каждой формулой последовательности указывать применяемое правило (его номер), а затем, в круглых скобках, номера формул исходных посылок, к которым применялось данное правило.

Задание 3. Доказать выводимость формул закона двойственности:

1) ú- ;

2) ú- .

Решение. Покажем вначале справедливость формулы 1).

1. A ú-
2. B ú-
3. ú-	13 (1)
4. ú-	13 (2)
5. , ú-
6. ú-	4 (3, 4, 5)
7. ú-	5 (6)

Построим теперь обратный вывод.

1. ú-
2. ú-
3. ú-	13 (1)
4. ú-	13 (2)
5. ú-	10 (3, 4)
6. ú-	13 (5)
7. ú-	5 (6)

Выводить, как уже отмечалось, можно не только ТИ-формулы (теоремы исчисления высказываний), но и формулы, которые будут истинными при условии истинности системы посылок. Рассмотрим пример такого вывода.

Задание 4. Доказать, что

ú-

Решение. Построим вывод этой формулы.

1. ú-
2. ú-
3. ú-
4. ú-	6 (1)
5. ú-	6 (2)
6. ú-
7. ú-	4 (4, 6)
8. ú-	2 (3)
9. ú-	11 (7, 8)
10. ú-
11. ú-	4 (5, 10)
12. ú-	2 (3)
13. ú-	11 (11, 12)
14. , ú-
15. ú-	4 (9, 13, 14)
16. ú-	Теорема ИВ
17. ú-	4 (15, 16)

Часто для записи правил вывода используют сокращенную схему, они выражаются в следующих терминах.

“Если формулы U, B,... истинны, то формулы M, N,... также истинны”. Такие утверждения записываются в виде схемы:

.

Так, правило заключения запишется как

.

В виде аналогичной схемы можно записывать правило получения выводимости из некоторой системы посылок. Обозначим через – систему посылок . Выражение вида

ú- U₁,..., ú- U_n

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

ú- B

назовем допустимым в исчислении высказываний правилом, если в исчислении высказываний из ú- U₁,..., ú- U_n следует ú- B.

При выводе формул широко используются свойства монотонности конъюнкции, дизъюнкции и импликации.

Теорема 2.1. Имеют место следующие выводимости:

1) , ú- ;

2) , ú- ;

3) , ú- .

Следствие. Если ú- и ú- , то:

1) ú- ;

2) ú- ;

3) ú- .

Варианты заданий.

1. Какие из следующих выражений являются формулами исчисления высказываний:

a) ;

b) ;

c) ;

d) ;

e) .

2. Выписать все подформулы формул:

a) ;

b) ;

c) ;

d) .

Применяя правила подстановки и заключения, доказать, что следующие формулы являются теоремами исчисления высказываний (3 – 10).

3.

4.

5.

6.

7.

8.

9.

10.

Применяя правила подстановки и заключения, построить вывод формул из данной системы посылок (11 - 15).

11.

12.

13.

14.

15.

Являются ли выводами в исчислении высказываний следующие последовательности формул (16 – 18).

16.

17.

18.

B

Применяя производные правила вывода, показать, что доказуемы формулы (19 – 36).

19. U ® B, P ® Q ú- (U Ù P) ® (B Ù Q)

20. U ® B, P ® Q ú- (U Ú P) ® (B Ú Q)

21. U ® B, P ® Q ú- (B ® P) ® (U ® Q)

22. ú-

23. ú-

24. (P ® Q) ® ((Q ® R) ® (P ® R))

25. (P ® Q) ® ((R ® P) ® (R ® Q))

26. Q ® R ® (P Ú Q) ® (P Ú R)

27. (P ® Q) Ú (Q ® P),

28. P ® (Q ® (P Ù Q))

29. (P ® Q) Ú (P ® Ø Q)

30. (P ® Q) ® ((P ® (Q ® R)) ® (P ® R)))

31. ((P ® R) ® ((Q ® R) ® ((P Ú Q) ® R)))

32. ((P ® Q) ® ((P ® Ø Q) ® Ø P))

33. ((Ø Q ® Ø P) ® ((Ø Q ® P) ® Q))

34. Q ® ((P Ú Q) Ù (Q Ú Ø P)

35. Q Ú (P Ù Ø Q) ® (P Ú Q)

36. Q ® (P Ú Ø R Ù Q Ú Q)

Применяя производные правила вывода, построить вывод формул (37 – 43).

37. , ú-

38. ú-

39. ú-

40. ú-

41. ú-

42. ú-

43. ú-

Применяя производные правила вывода, построить вывод формул. Проверить, справедлива ли выводимость в обратную сторону, если да, то построить вывод (44 – 59).

44. ú-

45. ú-

46. ú-

47. ú-

48. ú-

49. ú-

50. ú-

51. ú-

52. A ® (C ® P) ú- (A Ù C) ® P

53. ú-

54. ú- () ® P

55. P ® Q ú- (P ® )®

56. P Ú R Ú Q ú- ((P ® R) ® ( ® R

57. (P ® Q) ® (P ® (Q ® R)) ú- (P ® R)

58. ú-

59. ú-

60. Пусть А – формула, В – подформула формулы А, А₁ - результат замены некоторого вхождения В в А на формулу В₁. Доказать (В ~ В ₁) ú- (А ~ А₁). (Теорема о замене)

61. Доказать, что если выводима формула U₁, …, U_n ú- B, то формула (U₁ Ù … Ù U_n ® B) тождественно истина.

62. Найти такие формулы и , что из доказуемости в исчислении высказываний следует доказуемость , но неверно, что ú- .

Дата добавления: 2015-06-27