Непейвода Н.Н. Прикладная логика

Подождите немного. Документ загружается.

9.3. СЕМАНТИЧЕСКИЕ ТАБЛИЦЫ С КВАНТОРАМИ

221

9.3.4. ∀x (A(x) ∨ B(x)) ⇒ ∃x A(x) ∨ ∀x B(x).

9.3.5.

∃x A(x)&∀x (¬A(x) ∨ B(x)) ⇒ ∃x B(x).

9.3.6.

∃x A(x)&∃x B(x) ⇒ ∀x (A(x) ∨ B(x)).

9.3.7.

∀xA(x)&∃xC(x)&∃xB(x) ⇒ ∃x(A(x)&B(x)&C(x)).

9.3.8.

∃x (A(x)&B(x)) ⇒ ∃x A(x)&∀x B(x).

9.3.9.

(∃xA(x) ⇒ ∀xB(x)) ⇒ ∀x(A(x) ⇒ B(x)).

9.3.10.

¬∃x(A(x) ⇒ B(x)) ⇒ ∃xA(x)&∀xB(x).

9.3.11.

∀x∃yA(x, y)&∃x∀yB(x, y) ⇒ ∃x∃y (A(x, y)&B(x, y)).

9.3.12.

∀x(A(x) ∨ B(x))&(∀xA(x) ⇒ ∃xC(x))&∀x(B(x) ⇒ C(x)) ⇒

∃xC(x).

9.3.13.

∀x (A(x) ∨ B(x))&∃x(A(x) ∨ C)&∃x(C ⇒ B(x)) ⇒ ∃xB(x).

9.3.14.

∀x(A(x) ∨ B(x))&∃x¬A(x)&

∀x∀y(B(x) ⇒ C(y))&∃xD(x) ⇒ ∃x(C(x)&D(x)).

9.3.15.

∀x∃y (A(x) ⇒ B(y))&(∃xA(x) ⇒ C) ⇒ (C ⇒ ∃zB(z)).

9.3.16.

∀x∀y(A(x) ⇒ B(y))&(∃xC(x) ⇒ ∃xA(x))&∃x(¬C(x) ⇒ B(x)) ⇒

∃xB(x).

9.3.17.

¬(∃xA(x) ⇒ ∀yB(x, y)) ∨ ∀x¬A(x).

9.3.18.

∀x∃y (A(x) ⇒ B(y)) ⇒ (∀xA(x) ⇒ ∃xB(x)).

9.3.19.

∀x(A(x) ⇒ B(x))&

∃x(B(x)&¬C(x)) ⇒ ∃x(B(x)&¬A(x)).

9.3.20.

(∃xB(x) ∨ ∃xC(x))&

∀x(C(x) ⇒ B(x)) ⇒ ∃xB(x).

9.3.21.

∀x (C(x) ⇒ B(x)&D(x))&

∃x(A(x)&C(x)) ⇒ ∃x(A(x)&B(x)).

9.3.22.

[K]

Некоторые птицы, гордящиеся своим хвостом, не могут петь.

Ни одна птица,кроме павлина,не может гордиться своим хвостом.

Значит, некоторые павлины не могут петь.

222

ГЛАВА 9. КЛАССИЧЕСКИЕ СТ

9.3.23.

[K]

Все львы свирепы. Некоторые львы не пьют кофе. Следова-

тельно, некоторые из тех, кто пьет кофе, не свирепы.

9.3.24.

[K]

Ни одно ископаемое животное не может быть несчастно в

любви. Устрица может быть несчастна в любви. Следовательно,

некоторые устрицы — не ископаемые животные.

9.3.25.

[K]

Золото тяжелое. Ничто, кроме золота, не может заставить его

замолчать. Следовательно, ничто легкое не может заставить его

замолчать.

9.3.26. Некоторые лампочки плохо светят.Лампочки предназначены для

того, чтобы светить. Следовательно, некоторые вещи, предназна-

ченные для того, чтобы светить, светят плохо.

9.3.27.

[K]

Некоторые подушки мягкие. Ни одна кочерга не мягкая. Сле-

довательно, некоторые кочерги — не подушки.

9.3.28.

[K]

Лишь тот, кто храбр, достоин славы. Некоторые хвастуны —

трусы. Следовательно, некоторые хвастуны недостойны славы.

9.3.29.

[K*]

Необразованные люди обо всем судят поверхностно. Среди

студентов Удмуртского университета есть и образованные люди.

Значит, некоторые студенты УдГУ не судят обо всем поверхност-

но.

9.3.30.

[K*]

Все козлята прыгают. Ни одно молодое животное не прыга-

ет, если оно не здорово. Следовательно, все молодые козлята здо-

ровы.

9.3.31. Некоторые козы любят сено. Ни одна собака сена не любит. Зна-

чит, некоторые собаки — не козы.

9.3.32. Те, кто что-то учил, решили некоторые задачи. Андрей не решил

ни одной. Значит, он не учил ничего.

9.3.33. Все рыбаки любители приврать. Все священники соблюдают за-

поведи. Никто не может и соблюдать заповеди, и вместе с тем

врать. Значит, ни один рыбак не священник.

9.3.34. Не все политики мошенники. Все мошенники умны. Значит, не-

которые политики глупы.

9.4. СОКРАЩЕННЫЕ СТ

223

9.3.35. Студенты — любители покушать. Некоторые студенты худые.

Не все те, кто любит покушать, студенты. Значит, некоторые лю-

бители покушать не являются худыми студентами.

9.3.36. Все мафиози жестоки. Некоторые чеченцы жестоки. Следова-

тельно, некоторые чеченцы — мафиози.

9.3.37. Все шутки для того и предназначены, чтобы смешить людей. Ни

одно постановление Думы не является шуткой. Значит, ни одно

такое постановление не предназначено для того, чтобы смешить

людей.

§ 9.4. СОКРАЩЕННЫЕ СЕМАНТИЧЕСКИЕ ТАБЛИЦЫ

Рассмотрим случай, когда часть компонент в формуле избыточна. По-

строим таблицу для формулы

(A ⇒ B) & (B ⇒ D) & (D ⇒ E) ⇒ (B ⇒ E).

=| (A ⇒ B) & (B ⇒ D) & (D ⇒ E) ⇒ (B ⇒ E)

|= (A ⇒ B) & (B ⇒ D) & (D ⇒ E) =| (B ⇒ E)

|= (A ⇒ B) |= (B ⇒ D) |= (D ⇒ E) |= B =|

=| A |= B

=| B |= D

D |= E

B |= D

D |= E

(9.8)

Здесь видно, что разбор вариантов по первой импликации ничего не дал,

и можно было начать сразу со второй, получив гораздо более приличную

таблицу.

=| (A ⇒ B) & (B ⇒ D) & (D ⇒ E) ⇒ (B ⇒ E)

|= (A ⇒ B) & (B ⇒ D) & (D ⇒ E) =| (B ⇒ E)

|= (A ⇒ B) |= (B ⇒ D) |= (D ⇒ E) |= B =| E

=| B |= D

D |= E

(9.9)

Но как это усмотреть в самой таблице? В таблице (9.8) еще до ее разби-

ения появилась формула

|= B, которая получилась во втором варианте

224

ГЛАВА 9. КЛАССИЧЕСКИЕ СТ

первого разбиения. Значит, в этом варианте ни одной новой формулы не

появилось, и мы сделали пустой шаг

Определение 9.4.1.

Шаг построения таблицы называется

избыточным

если хотя бы в одной из получающихся подтаблиц не появляется новых

формул, либо если разбивается формула

|= ∃x A(x)

, а в таблице уже

имеется формула

|= A(c

)

, либо разбивается

=| ∀x A(x)

, а в таблице уже

имеется

=| A(c

)

. Подтаблица называется

финальной

, если в ней не мо-

жет быть сделано ни одного неизбыточного применения правил.

Избыточные разбиения просто не нужно делать. Более того, поня-

тие избыточного разбиения позволило нам дать точный ответ на вопрос,

когда же можно переходить к построению контрпримера: когда нашли

финальную подтаблицу.

На рассмотренных практических примерах видно,что иногда разбор

при помощи семантических таблиц можно сократить далее. Например,

если в подтаблице встречаются формулы

|= A ⇒ B и |= A, то подтабли-

ца с =| A сразу же закрывается, и нетривиальна лишь таблица с |= B.

|= A ⇒ B

|= A

=| A |= B

(9.10)

Здесь без нарушения строгости и общности можно обойтись без раз-

деления таблицы и просто добавить

|= B.Это правило сокращения фор-

мулируется следующим образом:

|= A ⇒ B |= A

|= B

(Modus Ponens)

Modus Ponens — название этого правила в традиционной логике.

Аналогично устанавливаются следующие правила сокращения:

|= A ⇒ B =| B

=| A

(Modus tollens)

|= A ∨ B =| B

|= A

|= A ∨ B =| A

|= B

На самом деле ничуть не лучше и формула =| A, появившаяся в первом варианте,

поскольку элементарная формула

A больше нигде не встречается.

9.4. СОКРАЩЕННЫЕ СТ

225

=| A&B |= B

=| A

=| A&B |= A

=| B

Еще один класс правил сокращения, применимых менее часто, это

контрприменения,или обращения правил,не разбивающих таблицу.На-

пример, имея |= A и |= B, можно заключить |= A&B. Эти правила це-

лесообразно применять для того, чтобы избежать разбиения таблицы по

сложной формуле в ситуации, подобной следующей:

|= A&B ⇒ D

|= A |= B

|= A&B

|= D

(9.11)

В отличие от предыдущих правил сокращения, которые являлись

полностью безопасными, следующие правила сокращают лишь поиск

опровержения, а при поиске доказательства заводят в тупик. Они осно-

ваны на наблюдении, что семантическая таблица с кванторами не все-

гда дает минимальную опровергающую модель. Избежать этого можно,

разрешив подставлять в кванторные правила, в которых требуется но-

вая константа, константу имеющуюся. Если при такой попытке подта-

блица не закрылась, то мы находим опровергающую модель, если же

закрылась, то попытка наша неудачна и нужно вернуться к стандарт-

ным правилам. Рассмотрим, как с помощью этого приема упрощается

построение последней таблицы предыдущего параграфа.

=| ∀x∃y A(x, y) ⇒ ∃xA(x, x)

=| ∃xA(x, x) |= ∀x∃yA(x, y)

|= ∃y A(c

, y) |= A(c

, c

) =| A(c

, c

)

|= ∃y A(c

, y) |= A(c

, c

)

=| A(c

, c

)

(9.12)

А вот если взять в предпоследней строке

вместо c

, наша таблица

“закроется”.

Подытожим

Если мы ищем доказательство, то нужно обязательно рас-

сматривать все варианты, брать новые константы, но под-

становки констант можно искать самые многообещающие,

а не перебирать все подряд.

226

ГЛАВА 9. КЛАССИЧЕСКИЕ СТ

Если мы ищем опровержение,можно ограничиваться одним,

самым бесперспективным с точки зрения противоречий ва-

риантом, иногда брать старые константы вместо новых, но

подстановки обязательно проделать все.

Работая в одном направлении (доказательство либо опро-

вержение),нельзя слишком увлекаться приведенными выше

послаблениями, поскольку и Ваша первоначальная оценка

формулы как истинной либо опровержимой может оказать-

ся неверной, и сама формула в реальных задачах может быть

видоизменена, так как никакая формализация не отражает

полностью содержания реальной задачи.

При оформлении готового решения эти послабления можно

использовать вовсю.

Чаще всего разумно до разделения таблицы проделать все

действия, которые можно выполнить без разделения.

В случае, если разбор случаев может быть заменен на пра-

вило сокращения, это целесообразно сделать.

Избыточное разбиение формул делать не нужно.

Если в некотором варианте все разбиения избыточны, он го-

тов для построения по нему опровергающей модели.

Упражнения к § 9.4

Проверить на семантических таблицах высказывания и рассужде-

ния. Если заключение частично опущено, восстановите его сами.

9.4.1.

((A ⇒ B&C) ⇒ D)&(C ⇒ B) ⇒ (A ⇒ C).

9.4.2. (A ∨ B ⇒ D&C)&((A ⇒ C) ⇒ E)&((A ⇒ D) ⇒ H)&(B ⇒

F ) ⇒ E&H&F .

9.4.3. ((A ⇒ B) ∨ ((A ⇒ B) ⇒ C) ⇒ D) ⇒ D.

9.4.4. (A ∨ B ⇒ D&C) ⇒ (A ⇒ C)&(A ⇒ D)&(B ⇒ D).

9.4.5. (A ⇒ C)&(A ⇒ D)&(B ⇒ D) ⇒ (A ∨ B ⇒ D&C).

9.4.6. (A ∨ B ⇒ D&C)&¬A ⇒ ¬B ∨ C ∨ D.

9.4.7. A ∨ C ∨ D ⇒ (A&¬B ⇒ C)&(D&B ⇒ C).

9.4. СОКРАЩЕННЫЕ СТ

227

9.4.8. (A&B ⇒ D ∨ C) ⇒ D ∨ (¬C&A ⇒ ¬B).

9.4.9.

(A ∨ B ⇒ D&C)&((A ⇒ C) ⇒ E)&((B ⇒ D) ⇒ H)&

(E&H ⇒ F ) ⇒ F .

9.4.10.

((A ⇒ D) ⇒ E)&((D ⇒ A) ⇒ H)&(E ∨ H ⇒ G ∨ F ) ⇒ G.

9.4.11.

(A ∨ B ⇒ D)&(A ∨ C ⇒ E)&(¬A ⇒ B ∨ C) ⇒ E ∨ D.

9.4.12.

(¬A ∨ ¬B ∨ ¬C ∨ D) ⇒ (A ⇒ D) ∨ (B ⇒ D) ∨ (C ⇒ D).

9.4.13.

(A ⇒ D&C)&((A ⇒ D) ⇒ E)&((A ⇒ C) ⇒ H)&(E ∨ H ⇒

G) ⇒ G.

9.4.14.

((A ⇒ B&C) ⇒ D)&(A ⇒ B)&(E&A ⇒ C) ⇒ (E ⇒ D).

9.4.15.

((A ⇒ B&C) ⇒ D)&(A&E ⇒ B)&(¬E&A ⇒ C) ⇒ D.

9.4.16.

(A&H ⇒ B)&(¬H&A ⇒ C)&(¬A ⇒ D) ⇒ B ∨ C ∨ D.

9.4.17.

(A ⇒ B ∨ C ∨ D)&((A ⇒ D) ⇒ E)&((A ⇒ C) ⇒ E) ⇒ E.

9.4.18.

(A&B ⇒ D)&(A ⇒ B ∨ H)&(B ⇒ A ∨ E) ⇒ D ∨ H ∨ E.

9.4.19.

((A ⇒ B) ∨ (A ⇒ C))&((A ⇒ B ∨ C) ⇒ D)&(D&E ⇒

G) ⇒ (E ⇒ G).

9.4.20.

(A ⇒ B&C)&(B ⇒ D&E)&(C ⇒ F )&(E&F ⇒ G)&(G&D ⇒

H) ⇒ (A ⇒ H).

9.4.21.

∀x(A(x)&B(x))&∃x(A(x)⇒C(x))&∃x(B(x)⇒D(x))&

∀x(C(x)&D(x)⇒E(x)) ⇒ ∃xE(x).

9.4.22. ∃x(A(x) ⇒ B(x))&∀x(A(x) ∨ C)&

∃x(C ⇒ B(x)) ⇒ ∃xB(x).

9.4.23. (∀x A(x) ⇒ ∃x B(x))& ∀x(C(x) ⇒ A(x))&∀x(C(x) ∨ D) ⇒

∃xB(x) ∨ D.

9.4.24. ∀x(A(x) ⇒ ∃xB(x))&∀x(C(x) ∨ A(x))&

∃x(C(x) ⇒ B(x)) ⇒ ∃xB(x).

9.4.25. ∀x∃y(A(x, y) ∨ B(y, x))&∀x∀y(A(x, y) ⇒ C(x))&

∃x∀y(B(x, y) ⇒ C(x)) ⇒ ∃xC(x).

228

ГЛАВА 9. КЛАССИЧЕСКИЕ СТ

9.4.26. ∀x∃yA(x, y)&∀x∃y¬A(x, y)&∀x∀y(A(x, y)⇒B(x))&

∀x∀y(¬A(x, y)⇒C(x))⇒ ∀x(H(x)⇒B(x)&C(x)).

9.4.27. ∀x∃yA(x, y)&∃x∀y(A(x, y)&B(x) ⇒ C(x, y))&

∀zB(z)⇒ ∃x∃yC(x, y).

9.4.28. ∀x∃yA(x, y)&∀x∃y(A(x, y)&B(x) ⇒ C(x, y))&

∀zB(z) ⇒ ∃x∃yC(x, y).

9.4.29. ∀x(A(x) ⇒ ∃y(B(y)&R(x, y)))&∀x(A(x) ⇒ ∀y(Q(y) ⇒

¬R(x, y)))&∃xA(x) ⇒ ∃x(¬Q(x)&B(x)).

9.4.30. ∃x(Q(x)&∀y(B(y) ⇒ R(x, y))) ⇒ (∀x(Q(x) ⇒ B(x)) ⇒

∃x(B(x)&R(x, x))).

9.4.31. ∃x(Q(x) & ∃y(B(y) & ¬R(x, y))) &

∀y(A(y) ⇒ ∀x(Q(x) ⇒ R(x, y))) ⇒ ∃x¬Q(x).

9.4.32. ∀x(A(x) ⇒ ∀y(Q(y) ⇒ ¬R(x, y)))&∃x(A(x)&

∀y(B(y) ⇒ R(x, y))) ⇒ ¬∃x(¬Q(x)&B(x)).

9.4.33. ∀x(A(x) ⇒ (∃yB(x, y) ⇒ ∃yC(x, y)))&

∀x(∃yB(x, y) ⇒ B(x, x))&¬∃xB(x, x)&

∀x∀y(C(x, y) ⇒ B(y, x)) ⇒ ∀x(A(x) ⇒ ∀y¬B(x, y)).

9.4.34. ∀x(P (a, x) ⇒ Q(x, b))&(∃y Q(y, b) ⇒ ∃y Q(b, y)) ⇒

(∃z P (a, z) ⇒ ∃xQ(b, x)).

9.4.35. ∀x(A(x) ⇒ ∀y(Q(y) ⇒ R(x, y))) &

¬∀x(A(x) ⇒ ∀y(B(y) ⇒ R(x, y))) ⇒ ¬∀x(B(x) ⇒ A(x)).

9.4.36. Если ездить на работу на автобусе, то приходится висеть на под-

ножке или рискуешь опоздать. Если не ездить на нем, то надо хо-

дить пешком. Если ходишь на работу пешком, то никогда не ви-

сишь на подножке, но можешь простудиться. Следовательно, если

не рисковать опоздать, то надо висеть на подножке либо рисковать

простудиться.

9.4. СОКРАЩЕННЫЕ СТ

229

9.4.37. Если пойдешь в лес весной, тебя укусит клещ. Те, кого кусает

клещ, заболевают энцефалитом или им делают укол. Тех,кто забо-

лел, кладут в больницу. В больнице всегда делают уколы. Значит,

если весной пойдешь в лес, ...

9.4.38. Будешь есть много хлеба, потолстеешь. Толстяки больны и вя-

лы. Больные не могут добиться успеха, если им не повезет. Вя-

лым людям никогда не везет. Значит, чтобы добиться успеха, не-

обходимо ...

9.4.39. Старательные люди добиваются успеха. Лишь тот может счи-

таться старательным, кто работает не менее десяти часов в сут-

ки. Нельзя одновременно работать и отдыхать по десять часов в

сутки. Легкомысленные люди отдыхают не менее десяти часов в

сутки. Следовательно, легкомысленные люди ...

9.4.40. Розовая вода приятно пахнет. Ни одно лекарство не пахнет при-

ятно. Если человек болен, он должен принимать лекарство либо

соблюдать режим. Соблюдать режим и не принимать лекарство

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

он не болен.

9.4.41. Если по телевизору не идет интересное кино, то в общежитии

собирается веселая компания. Веселая компания всегда шумна.

При шуме готовиться к занятиям невозможно. Если по телеви-

зору идет интересное кино, невозможно не смотреть телевизор.

Смотреть телевизор и готовиться к занятиям нельзя. Значит, в об-

щежитии ...

9.4.42. Известно, что убийца — Джон, Билл или Джек. Если Джон или

Джек —убийца,то убийство было после полуночи.Если убийство

было до полуночи, то Джон лжет или Билл — убийца. Если Джон

не лжет, то убийца — Билл. Следовательно, Билл — убийца или

убийство было после полуночи.

9.4.43. Коля и Вася никогда не бывают вместе. Маша придет на вече-

ринку только вместе с Колей, Вася — только вместе с Глашей.

Вечеринка веселая, только если на ней присутствуют и Маша, и

Глаша. Значит, веселых вечеринок не бывает.

230

ГЛАВА 9. КЛАССИЧЕСКИЕ СТ

9.4.44. Все парни самолюбивы. Ни один самолюбивый студент не акку-

ратен. Некоторые студенты аккуратны. Значит, некоторые студен-

ты — не парни.

§ 9.5. ИСЧИСЛЕНИЯ ТРАДИЦИОННОГО ТИПА

Исчисление —еще одно важнейшее понятие, наряду с формальным язы-

ком и семантикой введенное в число базовых математических конструк-

ций математической логикой. Исчисление I опирается на некоторый

формальный язык L и задает подкласс синтаксически правильно по-

строенных объектов этого языка, порождаемых, или выводимых, в I.

Для описания таких объектов и действий с ними используется новый

класс синтаксических конструкций — выводы (часто называемые в кон-

кретных исчислениях порождениями либо доказательствами). Выво-

ды включают в себя формулы, термы либо другие объекты языка L,

организованные в систему таким образом, что каждый из них связан с

ограниченным числом других согласно четким и проверяемым прави-

лам, а глобальная структура вывода также подчинена четким и прове-

ряемым условиям.

Пример 9.5.1.

Исчисление, порождающее подстановки порядка

Выводимые объекты — векторы

вида

, ∙∙∙ , i

)

, все

попарно

различны и находятся в диапазоне

1 : n

. Как известно, такие кортежи

задают перестановки чисел

1, ∙∙∙ , n

Выводы — циклические ориентированные графы с

пронумерован-

ными вершинами, такие, что вершина

i+1

следует за

при

i < k

, первая

следует за

-той, каждой вершине

сопоставлена подстановка

; под-

становка

в вершине, следующей за

, является произведением

Например, следующий граф есть вывод в исчислении подстановок 4-го

порядка:

(3, 4, 1, 2) (4, 1, 2, 3)

(2, 3, 4, 1) (1, 2, 3, 4)

(9.13)

Простейшим подклассом исчислений являются исчисления тради-

ционного типа. Такое исчисление

I задается описанием языка L, акси-

ом, являющихся выражениями языка L, и правил вывода, каждое из ко-