Математика : Реферат: Логика высказываний

Реферат: Логика высказываний

ЛОГИКА ВЫСКАЗЫВАНИЙ

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

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

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→q

2)     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→q

2)         q → r íДопущенияý

3)         р

4)         q íПО : 1,3ý

r íПО : 2,4ý

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

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

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

1)     pÙq → r

2)     р íДопущенияý

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 Ù r

4)     р → 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 íДопущенияý

2)     rÚр

3)     р íУД : 2ý

4)     q íПО : 1, 3ý

rÚq íВД : 4ý

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

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

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

(φ→ ψ)Ù φ→ ψ.

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

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

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

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

Литература

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

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

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

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

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

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

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