Все основные правила вывода исчисления высказываний

1.      Все основные правила вывода исчисления высказываний.

2.      Правила введения и удаления кванторов общности и существования.

Для записи схем правил введения и удаления кванторов общности и существования можно пользоваться символом j (х/w), обозначающем выражение, полученное из j подстановкой вместо именной переменной х выражения w при выполнении следующих условий:

1)     В выражении j замена переменной х производится лишь в тех местах, где она свободна. Если х входит в j несколько раз, то столько же раз она заменяется выражением w.

2)     Если в j переменная х находится в области действия квантора, связывающую предметную переменную z, то вместо х не подставляется выражение содержащее z в качестве свободной переменной. Короче говоря, подстановку следует производить так, чтобы свободные переменные подставляемого выражения не оказались связанными в выражении, полученном в результате подстановки.

Если это правило нарушается, то можно получить ложное высказывание. Так, в выражении $m (m>n) переменная m связана, а переменная n свободна. Если мы вместо n подставим m+1, то получим ложное выражение: $m (m> m+1).

Правило удаление квантора общности:

У" .

Примером рассуждения по правилу У":

 

.

Правило введения квантора общности:

В"  применяется лишь при условии, что переменная х не входит в качестве свободной в допущение косвенного доказательства.

Примером рассуждения по правилу

В": .

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

 

В$ .

Примером рассуждения по правилу В$:

 

2 – четное и простое число

$х (х – четное и простое).

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

 

У$ ,

где у₁, …у_n- все свободные именные переменные выражения j, отличные от переменной х, а выражение j(х/σ у₁, …у_n) – результат подстановки в выражение j постоянной σ, отмеченной индексами у₁, …у_nвместо х. Заметим, что переменные у₁, …у_n, входящие в выражение σ у₁, …у_n рассматриваются в качестве свободных. Поэтому выражение σ у₁, …у_n можно подставлять в выражение j вместо переменной х тогда, и только тогда, когда эта переменная не находится в области действия квантора, связывающего переменные у₁, …у_п.

В качестве примеров вывода формул в натуральном узком исчислении предикатов рассмотрим вывод аксиом e),f), а также формул (37), (38).

 

е) "х F(х)® F(у)

 

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

1)     "х F(х) {Допущение}

 F(у) {У": 1}

 

f) F(у) ® $х F(х)

 

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

1)     F(у) {Допущение}

$х F(х) {В$: 1}

Докажем формулу (37):

 

р®"х (рÚ F(х))

 

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

1)     р {Допущение}

2)     рÚ F(х) {ВД: 1}

"х рÚ F(х) {В": 2}

Докажем теперь формулу (38):

 

"х F(х) ®$х F(х)

 

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

1)         "х F(х) {Допущение}

2) F(у) {У": 1}

$х F(х) {В$: 2}

5. ПОГРУЖЕНИЕ АРИСТОТЕЛЕВСКОЙ СИЛЛОГИСТИКИ В УЗКОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

В логике Аристотеля и его последователей вплоть до конца ХІХ столетия основная роль приписывалась четырем видам суждений, называемым категорическими А, Е, I, О. Символические суждение А «Все S суть Р» записывается так:

 

"х ( S(х) ®Р(х)) (39)

Суждение Е «Никакое S не есть Р» :

`$х (S(х) Ù Р(х)) (40) или по другому "х ( S(х) ®`R(х)) (40¹ )

Суждение I «Некоторые S суть Р»:

$х (S(х) Ù Р(х)) (41)

Суждение О «Некоторые S не суть Р»:

$х (S(х) Ù`R(х)) (42)

Докажем некоторые модусы непосредственных умозаключений.

Модус АSР® ISР, пользуясь (39)-(42) запишем так:

"х ( S(х) ®Р(х)) ®$х (S(х) Ù Р(х)) (43)

 

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

1)     "х ( S(х) ®Р(х)) {Допущение}

2)     S(у) ®Р(у) {У": 1}

3)     S(у) {Допущение}

4)     Р(у) {ПО: 2,3}

5)     S(у) ÙР(у) {ВК: 3,4}

$х (S(х) Ù Р(х)) {В$: 5}

Модус ЕSР®ОSР опять-таки с помощью (39-42) записываем так:

"х ( S(х) ®`R(х)) ® $х (S(х) Ù`R(х)) (44)

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

1)     "х ( Sх ®`R(х)) {Допущение}

2)     "х ( S(х) ®`R(х)) ®(S(у) ®`R(у)) {подстановка в аксиому е)}

3)      S(у) ®`R(у) {ПО: 1,2}

4)     S(у) {Допущение}

5)     `R(у) {ПО: 3,4}

6)     S(у) Ù `R(у) {ВК: 4,5}

$х S(х) Ù`R(х) {В$: 6}

Модус АSР® IРS записываем в виде:

"х ( Sх ®R(х)) ®$х (S(х) ÙR(х)) (45)

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

1)         "х ( S(х) ®R(х)) {Допущение}

2)     "х ( S(х) ®R(х)) ®(S(у) ®R(у)) {подстановка в аксиому е)}

3)         S(у) ®R(у) {ПО: 1,2}

4)         S(у) {Допущение}

5)         R(у) {ПО: 3,4}

6)         S(у) ÙR(у) {ВК: 4,5}

$х S(х) ÙR(х) {В$: 6}

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

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

Используя (39)-(42), записываем первый модус первой фигуры силлогизма АМРÙАSМ®АSР так:

 

"х (М(х)®Р(х)) Ù "х (S(х) → М(х)) →"х(S(х) →Р(х)) (46)

 

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

1)     "х (М(х)®Р(х)) Ù "х (S(х) → М(х)) {Допущение}

2)     "х (М(х)®Р(х)) {УК: 1}

3)     "х (S(х) → М(х)) {УК: 1}

4)     М(у)®Р(у) {У": 2}

5)     S(у) ® М(у) {У": 3}

6)     S(у) ® Р(у) {(29): 4,5}

"х(S(х) →Р(х)) {В": 6}

Докажем справедливость первого модуса второй фигуры силлогизма

ЕРМÙ АSМ→ЕSР.

Используя (39)-(42), записываем его в виде:

 

"х (Р(х) ®`М(х)) Ù "х (S(х) → М(х)) →"х(S(х) →`Р(х)) (47)

 

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

1)     "х (Р(х) ®`М(х)) Ù "х (S(х) → М(х)) {Допущение}

2)     "х (Р(х) ®`М(х)) {УК: 1}

3)     "х (S(х) → М(х)) {УК: 1}

4)     Р(у)®`М(у) {У": 2}

5)         S_ (у) ® М(у) {У": 3}

6)         `М(у)®`Р(у) {(30): 4}

7)         М(у)®`Р(у) {(9): 6}

8)         S (у)®`Р(у) {(29): 5,7}

"х(S(х) →`Р(х)) {В": 8}

Наконец, докажем первый модус третьей фигуры силлогизма

 

АМРÙАSМ→ІSР.

Используя (39)-(42), записываем его в виде:

 

"х (М(х)®Р(х)) Ù "х (М(х)→S(х)) →$х(S(х) Ù Р(х))

 

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

1)     "х (М(х)®Р(х)) Ù "х (М(х)→S(х)) {Допущение}

2)     "х (М(х)®Р(х)) {УК: 1}

3)     "х (М(х)→S(х)) {УК: 1}

4)     М(у)® Р(у) {У": 2}

5)     М(у)® S (у) {У": 3}

6)     М(у) {Допущение}

7)     S (у) {ПО: 5,6}

8)     Р(у) {ПО: 4,5}

9)     S (у) ÙР(у) {ВК: 7,8}

$х(S(х) Ù Р(х)) {В$: 9}

6. РАСШИРЕННОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

В узком исчислении предикатов переменные являются пропозициональные переменные, именные переменные и переменные представляющие предикаты. В формулах этого исчисления кванторы связывают только именные переменные. Это исчисление явно не завершено. Например, формула "R"х (Р(х)ÚР(х)) выполняется для любого предиката Р. значит, мы должны располагать квантором общности для предиката. С другой стороны формула "хF(х) явно не общезначима. Но она выполняется для некоторых F. Чтобы выразить это мы должны располагать и кванторами существования для предиката, и выполнимость этой формулы записать так: $F "хF(х).

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

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

Расширенное исчисление предикатов и полученные из него некоторые системы посредством добавления к его аксиомам аксиом специальной структуры дали возможность получить очень важные результаты в теории множеств, геометрии, арифметике, теории алгоритмов и во многих других областях. Однако как показали К. Гедель и др., проблема разрешимости в таких системах становится очень запутанной. И все дело в том, что, формализуя словесный оборот «все» с помощью квантора " мы пытаемся заключить бесконечное в конечные рамки. Но при этом мы можем рассчитывать лишь на частный успех.

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

Литература

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

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

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

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

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

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

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