Логика высказываний (стр. 1 из 2)
ЛОГИКА ВЫСКАЗЫВАНИЙ
Важнейшей функцией логики является установление того, что из чего следует, а значит установление того, какие формулы являются теоремами, а какие нет. Это достигается с помощью аксиоматического метода. При аксиоматическом построении исчисления высказываний выбирают некоторое, небольшое количество формул, которые включают в систему без доказательства. Это аксиомы системы. Остальные формулы могут быть присоединены к системе только тогда, когда они следуют из аксиом или являются определениями. Существует много эквивалентных систем исчисления высказываний, различающихся аксиомами и исходными терминами. Здесь мы опишем систему Д. Гильберта и В. Аккермана. В исчислении высказываний определение формулы такое же, как и в алгебре высказываний.
В качестве аксиом принимаются следующие четыре высказывания:
a) рÚ q®р
b) р® рÚ q
c) рÚ q® q Ú р
d) (р® q) ®( rÚ р ® rÚ q)
e)
В этой системе принимаются три определения:
Д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 →(φ2→( φ3→ …(φп-1 →φп)…) строится следующим образом:
1. В первых n-1 строках выписываются последовательно выражения φ1, φ2,… φп-1 в качестве условий теоремы.
2. К доказательству можно присоединить:
a) ранее доказанные теоремы в качестве новых строк;
b) новые строки на основании уже имеющихся строк по правилам ПО, ВК, УК, ВД, УД, ВЭ, УЭ.
1. Доказательство закончено, если его последняя строка есть выражение φп. Последняя строка доказательства не нумеруется; тем самым отмечается, что доказательство закончено.
Косвенное доказательство выражения φ1 →(φ2→( φ3→ …(φп-1 →φп)…) строится следующим образом:
1. а) В первых n-1 строках выписываются последовательно выражения φ1, φ2,… φп-1 в качестве условий теоремы.
b) В n-ой строке выписывается выражение`φп в качестве допущения косвенного доказательства.
2. К доказательству можно присоединить:
a) ранее доказанные теоремы в качестве новых строк;
b) новые строки на основании уже имеющихся строк по правилам ПО, ВК, УК, ВД, УД, ВЭ, УЭ.
3. Доказательство закончено, если в нем имеются две противоречащие строки. Окончание доказательства отмечается написанием в последней ненумерованной строке выражения «ПРТВРЧ» (сокращение слова «противоречие») с указанием справа номеров двух противоречащих строк.
Продемонстрируем приемы доказательства на ряде примеров. Их мы будем нумеровать с указанием слева Ті( теорема номері )
Т1 (Закон гипотетического силлогизма)
(p→q)→(( q → r)→( p→ r))
Доказательство:
1)
p→q2) q → r íДопущенияý
3) р
4) q íПО : 1,3ý
r íПО : 2,4ý
Т2 (Закон контрапозиции)
(`p→q)→( `q →р) (30)
1)
`p→q íДопущенияý2) `q
3) `p íДопущения косвенного доказательстваý
4) q íПО : 1,3ý
ПРТВРчí 2,4ý
Т3 (Второй закон гипотетического силлогизма)
(p→q)Ù( q → r)→( p→ r)
Доказательство:
1)
p→q2) q → r íДопущенияý
3) р
4) q íПО : 1,3ý
r íПО : 2,4ý
Т4 ( Закон экспортации)
(pÙq → r) →(р→(q → r)) (32)
Доказательство:
1)
pÙq → r2) р íДопущенияý
3) q
4) pÙq íВК : 2,3ý
r íПО : 2,4ý
Т5¢
(p→q)Ù( р → r) →(p→q Ù r) (32¢ )
Доказательство:
1)
(p→q)Ù( р → r) íДопущенияý2) р
3)
p→q íУК : 1ý q Ù r4) р → r
5) q íПО : 2,3ý
6) r íПО : 2,4ý
q Ù r íВК : 5,6ý
Докажем теперь аксиомы a), b), c), d):
a) pÚq→р
Доказательство:
1) pÚq íДопущенияý
р íУД : 1ý
b) р→ pÚq
Доказательство:
1) p íДопущенияý
рÚq íВД : 1ý
pÚq→ qÚр
Доказательство:
1) pÚq íДопущенияý
2) qÚр íДопущения к.д.ýПРТВВРч1, 2
c) (р→ q) → (rÚр→ rÚq)
Доказательство:
1)
р→ q íДопущенияý