Важнейшей функцией логики является установление того, что из чего следует, а значит установление того, какие формулы являются теоремами, а какие нет. Это достигается с помощью аксиоматического метода. При аксиоматическом построении исчисления высказываний выбирают некоторое, небольшое количество формул, которые включают в систему без доказательства. Это аксиомы системы. Остальные формулы могут быть присоединены к системе только тогда, когда они следуют из аксиом или являются определениями. Существует много эквивалентных систем исчисления высказываний, различающихся аксиомами и исходными терминами. Здесь мы опишем систему Д. Гильберта и В. Аккермана. В исчислении высказываний определение формулы такое же, как и в алгебре высказываний.

В качестве аксиом принимаются следующие четыре высказывания:

1. рЪ q®р

2. р® рЪ q

3. рЪ q® q Ъ р

4. (р® q) ®( rЪ р ® rЪ q)

5. 
   

В этой системе принимаются три определения:

Д1 φ Ъ ψ ≡`φ →ψ

df

______

Д2 φ Щ ψ ≡`φЪ`ψ

df

Д3 (φ ≡ ψ) ≡ (φ →ψ) Щ (ψ →φ)

df

Здесь символ «» означает равносильные по определению.

Для получения новых формул, как из положенных в основу исходных формул, так и из уже выведенных формул, принимаются два правила:

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

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

β) Схема заключения.

Из двух формул φ и φ → ψ получаем новую формулу ψ.

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

ПРАВИЛО I. Если φ Ъ φ – доказуемая формула, то доказуема также формула φ.

Доказательство: Подставим в α) формулу φ. Получим φ Ъ φ→ φ. Поскольку φ Ъ φ доказуемая формула, то, по правилу β) доказуема и формула φ.

ПРАВИЛО II. Если φ – доказуемая формула, а ψ – любая другая формула, то формула φ Ъ ψ является также доказуемой.

Доказательство: Подставим в в) вместо р формулу φ, а вместо q - формулу ψ. Получаем φ ® φ Ъ ψ. Схема заключения дает φ Ъ ψ.

ПРАВИЛО III. Если φЪ ψ – доказуемая формула, то доказуема и формула ψ Ъφ.

Доказательство: Получаем из с) заменой р на φ, q на ψ и применяем схемы заключения.

ПРАВИЛО IV. Если φ→ ψ доказуемая формула, то формула γЪφ→ γ Ъ ψ также доказуема.

Доказательство : Получаем из α) заменой р на φ, q на ψ, r на γ и применяем схемы заключения.

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

Докажем, например, формулу:

(p→q)→((r→p)→(r→q))

Доказательство: Заменим в d) r на`r. Получаем (p→q)→ ((`rЪp)→(`rЪq)), но по Д1 эта формула есть иная запись доказываемой формулы.

Доказательство: Подставим в формулу вместо р формулу ψ, вместо q формулу γ, вместо r формулу φ. Получаем: (ψ → γ )→(( φ→ ψ)→( φ→ γ)) .

Применяя два раза схему заключения, получаем: φ→ γ.

Легко доказать, что в предложенной аксиоматической системе выводимы формулы алгебры высказываний. Докажем например, что формула `рЪp выводима.

Доказательство: Подставляем в в) вместо q переменную р , получаем формулу р→ рЪp. Из а) той же подстановкой получаем рЪp→ р. По правилу У выводим формулу p→ р. По Д1 эта формула представляет собой иную запись формулы`рЪp.

Аналогичным образом можно доказать остальные формулы алгебры высказываний.

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

Система исчисления высказываний может быть построена методом допущений. Этот метод ближе к обычным содержательно очевидным представлениям в том отношении, что доказательства в системах, построенных этим методом, почти не отличаются от математических доказательств и от рассуждений в других науках. Здесь оно излагается по книге Е. Слупецкого, Л. Борковского «Элементы математической логики и теории множеств».

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

1. Правило отделения (обозначает ПО):

ПО φ→ ψ

;

Читается эта схема так: «Если в доказательстве имеются уже формула φ→ ψ и формула φ независимо от порядка, в каком эти формулы входят в доказательство, то к доказательству можно присоединить в качестве строки и формулу ψ».

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

ВК φ

;

Способ чтения этой схемы аналогичен.

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

УК ,

Правило УК можно записать в виде одной схемы:

УК

Ψ

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

ВД ,

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

УД φЪ ψ φЪ ψ

,

5. Правило введения эквивалентности:

ВЭ φ→ ψ

6)Правило удаления эквивалентности:

УЭ ,

Прямое доказательство выражения φ₁ →(φ₂→( φ₃→ …(φ_п-1 →φ_п)…) строится следующим образом:

1. В первых n-1 строках выписываются последовательно выражения φ₁, φ₂,… φ_п-1 в качестве условий теоремы.

2. К доказательству можно присоединить:

1. ранее доказанные теоремы в качестве новых строк;

2. новые строки на основании уже имеющихся строк по правилам ПО, ВК, УК, ВД, УД, ВЭ, УЭ.

1. Доказательство закончено, если его последняя строка есть выражение φ_п. Последняя строка доказательства не нумеруется; тем самым отмечается, что доказательство закончено.

Косвенное доказательство выражения φ₁ →(φ₂→( φ₃→ …(φ_п-1 →φ_п)…) строится следующим образом:

1. а) В первых n-1 строках выписываются последовательно выражения φ₁, φ₂,… φ_п-1 в качестве условий теоремы.

2. В n-ой строке выписывается выражение`φ_п в качестве допущения косвенного доказательства.

2. К доказательству можно присоединить:

1. ранее доказанные теоремы в качестве новых строк;

2. новые строки на основании уже имеющихся строк по правилам ПО, ВК, УК, ВД, УД, ВЭ, УЭ.

2. Доказательство закончено, если в нем имеются две противоречащие строки. Окончание доказательства отмечается написанием в последней ненумерованной строке выражения «ПРТВРЧ» (сокращение слова «противоречие») с указанием справа номеров двух противоречащих строк.

Продемонстрируем приемы доказательства на ряде примеров. Их мы будем нумеровать с указанием слева Т_і ( теорема номер і )

Т₁ (Закон гипотетического силлогизма)

(p→q)→(( q → r)→( p→ r))

Доказательство:

1. p→q

2. q → r нДопущенияэ

3. р

4. q нПО : 1,3э

r нПО : 2,4э

Т₂ (Закон контрапозиции)

(`p→q)→( `q →р) (30)

1. `p→q нДопущенияэ

2. `q

3. `p нДопущения косвенного доказательстваэ

4. q нПО : 1,3э

ПРТВРч н 2,4э

Т₃ (Второй закон гипотетического силлогизма)

(p→q)Щ( q → r)→( p→ r)

Доказательство:

1. p→q

2. q → r нДопущенияэ

3. р

4. q нПО : 1,3э

r нПО : 2,4э

Т₄ ( Закон экспортации)

(pЩq → r) →(р→(q → r)) (32)

Доказательство:

1. pЩq → r

2. р нДопущенияэ

3. q

4. pЩq нВК : 2,3э

r нПО : 2,4э

Т₅ў

(p→q)Щ( р → r) →(p→q Щ r) (32ў )

Доказательство:

1. (p→q)Щ( р → r) нДопущенияэ

2. р

3. p→q нУК : 1э q Щ r

4. р → r

5. q нПО : 2,3э

6. r нПО : 2,4э

q Щ r нВК : 5,6э

Докажем теперь аксиомы a), b), c), d):

1. pЪq→р

Доказательство:

1) pЪq нДопущенияэ

р нУД : 1э

2. р→ pЪq

Доказательство:

1) p нДопущенияэ

рЪq нВД : 1э

pЪq→ qЪр

Доказательство:

1) pЪq нДопущенияэ

2) qЪр нДопущения к.д.э

ПРТВВРч 1, 2

3. (р→ q) → (rЪр→ rЪq)

Доказательство:

1. р→ q нДопущенияэ

2. rЪр

3. р нУД : 2э

4. q нПО : 1, 3э

rЪq нВД : 4э

С помощью таблиц истинности можно убедиться, что ПО исключают случаи, когда его применения к истинным посылкам дает ложные результаты.

По определению импликации φ→ ψ ψ есть следствие φ во всех случаях, кроме такого, когда посылка φ истинна, а заключение ψ ложно. Так, что для доказательства того, что ПО позволяет делать из посылок следствия достаточно доказать, что импликация, антицидент которой является конъюнкция посылок, консеквент – вывод, полученный с помощью этого правила, является всегда истинной формулой.

Для ПО составляем формулу:

(φ→ ψ)Щ φ→ ψ.

И с помощью таблицы истинности убеждаемся, что эта формула тождественно истинна

φ	ψ	φ→ ψ	(φ→ ψ)Щ φ	(φ→ ψ)Щ φ→ ψ
0	0	1	0	1
0	1	1	1	1
1	0	0	0	1
1	1	1	1	1

Для ВК : φЩψ →φ Щψ.

Таблица истинности имеет вид

φ	ψ	φЩψ	φЩψ →φ Щψ
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	1

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

Литература

1. Логическое суждение. Руфулаев О.Н. К. – 2005 г.

2. Логика – исскуство мышления. Тимирязев А.К.– К. 2000 г.

3. Философия и жизнь – журнал- К. 2004 г.

4. История логики и мышления – Касинов В.И. 1999.

5. Логика и человек – М. 2000.

6. Философия жизни. Матюшенко В.М. – Москва – 2003 г.

7. Философия бытия. Марикова А.В. – К. 2000 г.