2.2.2. Исчисление высказываний как формальная система

Рассмотрим формальную аксиоматическую систему ФС₁ для исчисления высказываний.

Исходными термами ФС₁ являются буквы латинского алфавита с индексами или без них. Исходные термы называются высказывательными переменными или атомами. Исходными символами логических связок являются ¬, &, , →, которые интерпретируются как отрицание, конъюнкция, дизъюнкция и импликация. Для удобства записи формул введем еще пару символов ( и ), называемых скобками. Других исходных символов исчисление высказываний не имеет.

Правила образования ППФ:

1. все атомы есть ППФ;

2. если A и B – ППФ, то ¬A, A & B, A  B, A → B – также ППФ;

3. других правил образования ППФ нет.

Примеры ППФ: X → ¬Y, X & Y → (Y  ¬Z). Для удобства внешние скобки будем опускать, а применяя правила силы операций, перейдем к той же форме записи ППФ, что и формул исчисления высказываний. При интерпретации ППФ интерпретируются все атомы, в нее входящие, а затем производится интерпретация результатов логических операций. Окончательный результат интерпретаций операций считается результатом интерпретации всей ППФ. Понятие ППФ, как мы уже выяснили в 2.1, является эффективным.

Система аксиом (П.С. Новиков).

I a1. A → (B → A);

a2. (A →(B→ С)) → ((A → B) → (A → C));

II a3. A & B → A;

a4. A & B → B;

a5. (A → B) → ((A → C) →(A → B & C));

III a6. A → A  B;

a7. B → A  B;

a8. (А → C) → ((B→ C) → (A  B → C));

IV a9. (A → B) → (¬B → ¬A);

a10. A → ¬ ¬A;

а11. ¬ ¬A → A.

Все аксиомы – общезначимые ППФ.

Правила вывода.

Правило 1. Все аксиомы выводимы.

Правило 2. Правило подстановки. Пусть А – ППФ, содержащая атом X.

Тогда, если A – теорема исчисления высказываний, то заменив в ней атом X всюду, куда он входит, на произвольную ППФ В, мы получим также теорему. Сокращенно обозначим это правило через ПС. В принципе, считая, что каждая аксиома понимается как схе­ма аксиом, т. е. включает в себя бесконечно много аксиом, это пра­вило излишне. Мы оставим его ввиду наглядности и ясности изложения.

Правило 3. Правило modus ponens (правило дедуктивного вывода). Если А и А → В – теоремы, то В – также теорема. Это правило будем сокращенно обозначать через МР.

Правило 4. Других правил вывода нет.

Выводимость из посылок.

Считаем, что каждая ППФ В выводима из множества посылок А₁, А₂, …, А_n, если:

1. каждая А_i (1 ≤ i ≤ n) выводима из A₁, A₂, …, A_n;

2. каждая выводимая в ФС₁ ППФ выводима также из А₁, А₂, …, А_n;

3. из выводимости А и А → В из А₁, А₂,…,А_n следует выводимость В из А₁, А₂,…, А_n.

Если А₁, А₂, …, А_n являются аксиомами или другими выводи­мыми ППФ, то множество выводимых из них ППФ совпадает с множеством всех выводимых в данной ФС₁ ППФ.

Понятие выводимости сводится к понятию доказуемости с по­мощью теоремы Ж. Эрбрана о дедукции, которая гласит:

Если А₁, А₂, …, А_n ├ B, то ├ А₁ → (А₂ → (…(А_n → B)…)).

Таким образом, показывается, что если ППФ В выводима из по­сылок А₁, А₂, …, А_n, то ППФ А₁ → (А₂ → (…(А_n → B)…)) есть теорема. Как следствие этой теоремы, приведем несколько правил ФС₁. которые значительно сокращают путь доказательства теорем.

Правило 1 (правило силлогизма).

Если ├ А → B и ├ B → С, то ├ A → С.

Очевидно, что

1. A→B, B→C, A├ C MP;

2. ├ (A → B) → ((B → C) → (A → C)) теорема дедукции;

3. ├ (B → C) → (A → C) MP;

4. ├ A → C MP.

Правило 2 (разновидность силлогизма).

Если A├ B, C├ D и B, D├ E, то A, C├ E.

1. ├ C → D теорема о дедукции;

2. B├ D → E теорема о дедукции;

3. B├ C → E силлогизм из 1, 2;

4. ├ B→ (C → E) теорема о дедукции;

5. ├ A → B теорема о дедукции;

6. ├ A→ (C → E) силлогизм из 4, 5.

Правило 3 (правило перестановки мест посылок).

Если ├ A→ (B → C), то и ├ B→ (A → C).

1. A→ (B → C), B, A├ C МР;

2. A→ (B → C)├ B→ (A → C) теорема о дедукции.

Аналогично можно доказать следующие два правила.

Правило 4 (правило объединения посылок).

Если ├ A→ (B → C), то ├ A & B → C.

Правило 5 (правило разъединения посылок).

Если ├ A & B → C, то ├ A→ (B → C).

Система аксиом исчисления высказывания обладает следующи­ми тремя важными свойствами: полнотой, непротиворечивостью и независимостью. Тот факт, что любая теорема ФС₁, является обще­значимой ППФ, вытекает из того, что все аксиомы – тавтологии и правила вывода, примененные к тавтологиям, всегда приводят к тавтологиям. Обратное утверждение и представляет собой теоре­му о полноте.

Теорема 2.1 (о полноте в широком смысле). Если ППФ А фор­мальной системы ФС₁ является общезначимой, то она есть теорема этой системы.

Кроме понятия полноты в широком смысле имеет место понятие полноты логического исчисления в узком смысле. Исчисление вы­сказываний называется полным в узком смысле, если присоедине­ние к его аксиомам какой-нибудь не выводимой в нем ППФ приво­дит к противоречию.

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

Любое логическое исчисление называется непротиворечивым, если в нем не выводимы никакие две ППФ, из которых одна явля­ется отрицанием другой. Если мы имеем противоречивую систему, то в ней мы могли бы вывести любые ППФ, что не представляло бы никакой ценности, так как в такой системе не было бы разли­чий между истиной и ложью.

Например, известно, что следующая ППФ есть теорема, т. е. ├ A→ (¬A → B) и если в противоречивой системе некоторая ППФ А была бы выводима вместе со своим отрицанием ¬А, то по пра­вилу МР была бы теоремой любая ППФ В.

Теорема 2.2 (о непротиворечивости). Исчисление высказываний непротиворечиво.

И наконец, третье свойство системы аксиом – независимость. Аксиома, не выводимая с помощью правил вывода из остальных аксиом, называется независимой от этих аксиом, а система аксиом, в которой ни одна аксиома не выводима из остальных, называется независимой системой аксиом.

Теорема 2.3 (о независимости). Каждая аксиома формальной системы ФС₁ независима.

В заключение этого раздела заметим, что с помощью теоремы о полноте устанавливается факт равноценности понятия общезна­чимости и доказуемости. Так как вопрос об общезначимости может быть эффективно решен для произвольной ППФ, то понятие теоре­мы в исчислении высказываний эффективно.

Пример 2.3. Докажем, что

1. A9

2.

ПС A на и B на

3. доказательство см. ниже

4. _{MP 2, 3}

5. A10

6. ПС A на A&B

7. сил. 4,6

Докажем, что

1. A8

2.

ПС А на , В на , С на

3. A9

4. ПС В на А&B

5. сил. 2,4

6. A3

7. MP 5,6

8. A9

9. ПС А на А&B

10. сил. 7,9

11. A4

12. MP 10,11

Пример 2.4. Докажем, что

 (A&B)(AB)

1.  (XY)((XZ)(XY&Z)) A5

2.  (XA)((XZ)(XA&Z)) ПС Y на A

3.  (XA)((XB)(XA&B)) ПС Z на B

4. (XA)((XB)(XA&B)) ПС X на X

5. (AX)(XA) A9

6. (AX)((XB)(XA&B)) сил. 4,5

7. (AAB)(((AB)B)((AB)A&B)) ПС X на AB

8. AAB A6

9. ((AB)B)((AB)A&B)) MP 7,8

10. (BA)(AB) A9

11. (B(AB))((AB)B) ПС A на AB

12. (B(AB)) ((AB)A&B)) сил. 9, 11

13. BAB A7

14. (AB)A&B MP 12,13

15. (BA)(AB) A9

16. ((CD)B)(B(CD)) ПС B на (CD), А на В

17. ((CD)A&B)((A&B)(CD)) ПС B на A&B

18. ((AB)A&B)((A&B)(AB)) ПС C на A, D на B

19.  (A&B)(AB) MP 14,18

20.  AA A11

21. (AB)(AB) ПС A на AB

22. (A&B)(AB) сил. 19,21

23. (A&B)(AB) ПС A на A

24. (A&B)(AB)

Задачи

I. Доказать тождественную истинность всех аксиом Новикова П.С. (исполь­зуя таблицы истинности).

II. Доказать правила 15 ФС1.

II.I Доказать средствами ФС1 следующие формулы:

1. AA

2.  (AB) A&B

3.  (CA)((CB)(CA&B)

4. (AC)((BC)(ABC))

5.  A&AB

6. AA

7.  AB(A&B)

8.  A&B( AB)

9.  (AB) ( AB)

10.  (A&B)(AB)

11. (AB)A&B

12.  (AB)((AB)B)

13.  (AB)(A&B)

14. (AB)(A&B)

15. A(B(AB))

IV. Доказать следующие утверждения средствами ФС1:

1. Если я пойду завтра на первое занятие, то должен буду встать рано, а если я пойду вечером на танцы, то лягу спать поздно. Если я лягу спать поздно, а встану рано, то я буду вынужден довольствоваться пятью часами сна. Я просто не в состоянии обойтись пятью часами сна. Следовательно, я должен или пропустить завтра первое занятие, или не ходить на танцы.

2. Если я поеду в метро, то я приеду на работу без опоздания. Если я поеду трамваем, то я опоздаю на работу. Я еду или на метро, или трамваем. Следовательно, я или опоздаю, или не опоздаю на работу.

3. Я пойду в гости или останусь дома и почитаю книгу. Если я почитаю книгу, то не останусь дома. Следовательно, я пойду в гости.

4. Если я лягу сегодня поздно, то утром буду в отупении. Если я лягу не поздно, то мне будет утром казаться, что жизнь – прекрасная штука. Следовательно, или я завтра буду в отупении, или мне будет казаться, что жизнь – прекрасная штука.

5. Я поеду отдыхать летом на юг, только если не поеду в стройотряд. Если я поеду в стройотряд, то не встречусь с любимой девушкой. Я не поеду отдыхать летом на юг. Следовательно, я не встречусь с любимой девушкой.

6. Если 2 – простое число, то это наименьшее простое число. Если 2 – наименьшее простое число, то 1 есть простое число. Число 1 не есть простое число. Следовательно, 2 не есть простое число.

7. Ваня или переутомился, или болен. Если он переутомился, то он раздражается. Он не раздражается. Следовательно, Ваня болен.

8. Если завтра будет холодно, то я надену теплое пальто, если рукав будет починен. Завтра будет холодно, а я не надену теплое пальто. Следовательно, рукав не будет починен.

9. Если команда А выигрывает в футбол, то город А’ торжествует, а если выигрывает команда В, то торжествовать будет город В’. Выигрывает или А, или В. Однако если выигрывает А, то город В’ не будет торжествовать, а если выигрывает В, то не будет торжествовать город А’. Следовательно, город В’ будет торжествовать тогда и только тогда, когда не будет торжествовать А’.

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

11. Или Валя и Борис одного возраста, или Валя старше Бориса. Если Валя и Борис одного возраста, то Наташа и Борис не одного возраста. Если Валя старше Бориса, то Борис старше Сергея. Следовательно, или Наташа и Борис не одного возраста, или Борис старше Сергея.

12. Если 6 – составное число, то 12 – составное число. Или 12 – не составное число, или существует простое число большее, чем 12. Если существует простое число больше 12, то существует составное число больше 12. Если 6 делится на 2, то 6 – составное число. Не существует составного числа, большего, чем 12. Следовательно, 6 не делится на 2.

13. Если я поеду автобусом, а автобус опоздает, то я пропущу назначенное свидание. Если я пропущу назначенное свидание и начну огорчаться, то мне не следует ехать домой. Если я не получу эту работу, то я начну огорчаться и мне следует поехать домой. Следовательно, если я поеду автобусом и автобус опоздает, то я получу эту работу.

14. Или этот предмет не сложен, или экзаменатор снисходителен. Если этот предмет интересен, то он сложен. Экзаменатор не снисходителен. Значит, этот предмет неинтересен.

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

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

17. Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжет. Если Смит не был убийцей, то Джонс не встречал его этой ночью и убийство имело место после полуночи. Если убийство имело место после полуночи, то либо Смит был убийцей, либо Джонс не лжет. Следовательно, Смит был убийцей.

18. Если капиталовложения останутся постоянными, то возрастут правительственные расходы или возникнет безработица. Если правительственные расходы не возрастут, то налоги будут снижены. Если налоги будут снижены и капиталовложения останутся постоянными, то безработица не возникнет. Капиталовложения остаются постоянными. Следовательно, правительственные расходы возрастут.

19. Либо Петя поехал отдыхать на юг, либо, если Петя не сдал вовремя сессию, то ему пришлось каникулы провести дома. Если Петя поехал отдыхать на юг, то он сдал сессию вовремя. Следовательно, если Петя не сдал сессию вовремя, то ему пришлось каникулы провести дома.

20. Если вечер скучен, то или Катя начинает плакать, или Толя рассказывает смешные истории. Если Сережа приходит на вечер, то или вечер скучен, или Катя перестает плакать. Или вечер скучен, или Сережа приходит на вечер. Сережа приходит на вечер тогда и только тогда, когда Толя рассказывает смешные истории. Следовательно, если Катя перестает плакать, то Толя рассказывает смешные истории.

21. Если N серьезный политик, он не будет делать никаких заявлений. А если у него есть программа, то он должен её изложить. N сделал такое заявление и не изложил свою программу. Значит, он не серьезный политик, и у него нет программы.

22. Если экзаменатор строг, то экзамен трудно сдать. Экзаменатор строг или студенты плохо посещают занятия. Если студенты плохо посещают занятия, то плохо работает администрация факультета. Однако администрация работает хорошо. Значит, экзамен трудно сдать.

23. Профсоюзы штата будут продолжать поддерживать губернатора, если он подпишет данный билль. А фермеры окажут ему поддержку, если он наложит на него вето. Губернатор либо подпишет данный билль, либо наложит на него вето. Значит, губернатора поддержат либо профсоюзы, либо фермеры.

24. Если у больного болит зуб, то рекомендуется принять анальгин; если болит голова, то также рекомендуется принять анальгин. В данном случае у больного болит зуб или голова. Следовательно, ему рекомендуется принять анальгин.

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

26. Если Ваня победит на соревнованиях, он будет доволен, а если он будет доволен, то он не обладает бойцовскими качествами. Но если он не победит на соревнованиях, то он потеряет доверие товарищей. Ваня не обладает бойцовскими качествами, если он потеряет доверие товарищей. Если он не обладает бойцовскими качествами, ему следует уйти из команды. Ваня или победит на соревнованиях или не победит. Следовательно, ему нужно уйти из команды.

27. Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжет. Если Смит не был убийцей, то Джонс не встречал его этой ночью, и убийство имело место после полуночи. Если убийство имело место после полуночи, то либо Смит был убийцей, либо Джонс не лжет. Следовательно, Смит был убийцей.

28. Либо свидетель не был запуган, либо, если Генри покончил жизнь самоубийством, то записка была найдена. Если свидетель не был запуган, то Генри не покончил жизнь самоубийством. Следовательно, если Генри покончил жизнь самоубийством, то записка была найдена.

29. Если Смит был убийцей, то Джонс лжет. Если Джонс лжет, то убийство имело место после полуночи. Джонс не встречал этой ночью Смита тогда и только тогда, когда Смит был убийцей. Если Джонс встречал этой ночью Смита, то убийство имело место после полуночи. Следовательно, убийство имело место после полуночи.

30. Или этот предмет не сложен, или экзаменатор снисходителен. Если этот предмет интересен, то он сложен. Экзаменатор не снисходителен. Значит, этот предмет неинтересен.

Ниже приведены варианты формальной записи утверждений 1-30.

А1.	A → B, C → D, D&B → E, ¬E ├ ¬A­­ v ¬C
А2.	A → B, C → D, A­­ v C ├ B v D
А3.	A v B&C, C → ¬B├ A­­
А4.	A → B, ¬A­­ → C ├ B v C
А5.	A → B, ¬A­­ → C, ¬B ├ C
А6.	A → B, B → C, ¬C ├ ¬A­­
А7.	A v B, A → C, ¬C ├ B
А8.	A → (B → C), A&¬C ├ ¬B
А9.	A → C, B → D, A v B, A → ¬D, B → ¬C ├ D  ¬C
А10.	A v B → C&D, C → E, ¬E ├ ¬A
А11.	A v B, A → C, B → D ├ C v D
А12.	A → B, ¬B v C, C → D, E → A, ¬D ├ ¬E
А13.	A&B → C, C&D → ¬E, ¬F→ D&E ├ A&B →F
А14.	¬A v B, C → A, ¬B ├ ¬C
А15.	A v B → C&D, D v E → G ├ A → G
А16.	A  B, B → C, C → D, ¬A → D ├ D
А17.	A → B v C, ¬B → A&D, D → B v ¬C ├ B
А18.	A → B v C, ¬B → D, D&A → ¬C, A ├ B
А19.	A v (B → C), A → ¬B ├ B → C
А20.	A → B v C, D → A v ¬B, A v D, D~C ├ ¬B → C
А21.	A → B, C → D, ¬B&¬D ├ ¬A­­&¬C
А22.	A → B, A v C, C → D, ¬D├ B
А23.	A → B, D → C, A v D ├ B v C
А24.	A → B, C → B, A v C ├ B
А25. А 26. A27 A28 A29 A30	A → B, C → B, A v C ├ B A → D, D→ ¬B , A→ C, C → D,  B → C , AvA ├ ¬C A → B v C, ¬B →A&D, D→ B v C ├ ¬B A v (B→ C), A → B, ├ B → C A →B, B → C, D A, ¬D→C ├ C A v B, C → A, B ├ C

V. Доказать свойства системы аксиом ФС1

1. Доказать, что система аксиом Новикова П.С. является непротиворечивой.

2. Доказать, что любая система аксиом Новикова П.C. является независимой по отношению ко всем остальным аксиомам этого исчисления.