Дискретная математика:
логика, группы, графы, фракталыАкимов О.Е.
1.5. Операции над предикатами и кванторами
Конкретизация предикатов
Пусть предметная область предиката Р(х) состоит всего из двух конкретных значений a и b. Учитывая, что
∀х Р(х) = P(a) ∧ P(b), ∃хР(х) = P(a) ∨ P(b),
составим табл. 1.25, из которой непосредственно вытекают три элементарных клаузы:
∀х Р(х) ⇒ Р(a), Р(a) ⇒ ∃хР(х), ∀х Р(х) ⇒ ∃хР(х).Таблица 1.25
P(a) P(b) ∀х Р(х) ∃х Р(х) 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 Вместо P(a) в последних выражениях можно было бы взять P(b) — семантика клауз от этого не изменится, а она такова: если выражение «для всех х свойство Р выполняется» является истинным, то для конкретного значения х, равного а, это свойство тоже будет выполняться. Первая клауза является предикатной формой выражения аксиомы порядка:
∀х Р(х) = P(a), P(b) ⇒ P(a).Действие ее продемонстрируем на знакомом примере, который сейчас мы сформулируем более отчетливо:
Для всех х справедливо правило: если х — человек, то х смертен. Сократ человек. Следовательно, Сократ смертен.Введем два предиката:
А(х) = «х человек» и В(х) = «х смертен».Примем также, что а = «Сократ». Составим клаузу, соответствующую нашей легенде:
∀х(А(х) → В(х)), А(a) ⇒ В(a)Для ее доказательства достаточно перенести вторую посылку вправо за знак метаимпликации, чтобы клауза сразу же удовлетворяла аксиоме порядка в предикатной форме:
∀х(А(х) → В(х)) ⇒ А(a) → В(a).Ясно, что второй пример (о гениальности Сократа) — ложен, поскольку приводит к клаузе, противоречащей аксиоме порядка:
∃х(А(х) → В(х)) ⇒ А(a) → В(a).Конъюнктивная природа квантора общности и дизъюнктивная природа квантора существования, с точки зрения отношения эквивалентности, накладывают определенные ограничения при использовании их совместно с дизъюнкцией и конъюнкцией как логическими операциями.
Пусть для определенности предметная область состоит из двух элементов а и b (в общем случае для областей, состоящих из n элементов, все представленные здесь доказательства останутся теми же, только окажутся более громоздкими). Убедимся, что следующие два тождества выполняются:
∀х(А(х) ∧ В(х)) = ∀хА(х) ∧ ∀хВ(х),
∃х(А(х) ∨ В(х)) = ∃хА(х) ∨ ∃хВ(х).Действительно,
∀х(А(х) ∧ В(х)) = (А(a) ∧ В(a)) ∧ (А(b) ∧ В(b)) =
= (А(a) ∧ В(b)) ∧ (А(a) ∧ В(b)) = ∀хА(х) ∧ ∀хВ(х).Аналогично расписывается второе равенство.
Однако ситуация изменится, если квантор общности использовать совместно с дизъюнкцией, а квантор существования — с конъюнкцией:
∃х(А(х) ∧ В(х)) ⇒ ∃хА(х) ∧ ∃хВ(х).В самом деле,
∃х(А(х) ∧ В(х)) = (А(a) ∧ В(a)) ∨ (А(b) ∧ В(b)) = R ∧ Q,
R = (А(a) ∨ A(b)) ∧ (B(a) ∨ В(b)) = ∃хА(х) ∧ ∃хВ(х),
Q = (А(a) ∨ В(b)) ∧ (А(b) ∨ В(a)).Первая клауза верна, так как она сводится к аксиоме порядка:
R, Q ⇒ R.Аналогично доказывается клауза —
∀хА(х) ∨ ∀хВ(х)) ⇒ ∀х(А(х) ∨ В(х)).В логике предикатов, как и в логике высказываний или логике Буля, действует принцип двойственности. Клауза останется в силе, если ее посылки и заключения поменять местами, но при этом одновременно произвести замену:
∀ ⇔ ∃, ∧ ⇔ ∨, 0 ⇔ 1.Благодаря этому принципу, последнюю клаузу можно не доказывать отдельно, а составить, исходя из истинности предыдущей. Установленное свойство кванторов в отношении дизъюнкции отражается и на импликации, поскольку она может быть выражена через дизъюнкцию. Поэтому справедливы следующие выражения:
∃х(А(х) → В(х)) = ∀хА(х) → ∃хВ(х),
∃хА(х) → ∀хВ(х)) ⇒ ∀х(А(х) → В(х)).Но ситуация вновь изменится в пользу отношения эквивалентности, если любой из двух предикатов заменить высказыванием:
∀х(А ∨ В(х)) = А ∨ ∀хВ(х),
∃х(А ∧ В(х)) = А ∧ ∃хВ(х)).Действительно,
∀х(А ∨ В(х)) = (А ∨ В(a)) ∧ (А ∨ В(b)) =
= А ∨ (А ∧ В(a)) ∨ (А ∧ В(b)) ∨ (В(a) ∧ В(b)) =
= А ∨ (В(a) ∧ В(b)) = А ∨ ∀хВ(х).Раскрывая скобки и используя закон идемпотентности и поглощения или применяя вновь принцип двойственности, можно доказать второе равенство. Отсюда будут выполняться и равенства для импликации:
∀х(А → В(х)) = А → ∀хВ(х),
∀х(А(х) → В) = ∃хА(х) → В,
∃х(А → В(х)) = А → ∃хВ(х),
∃х(А(х) → В) = ∀хА(х) → В.Чтобы сохранить отношение эквивалентности при вынесении за скобки квантора ∃ при конъюнкции и квантора ∀ при дизъюнкции, когда даны два различных предиката, прибегают к введению дополнительной переменной, например:
∃хА(х) ∧ ∃хВ(х) = ∃xА(х) ∧ ∃yВ(y) =
= ∃х∃y (А(х) ∧ В(y)) = (А(a) ∨ A(b)) ∧ (B(a) ∨ В(b)).
Аналогично поступают в других случаях:
∀хА(х) ∨ ∀хВ(х) = ∀х∀y (А(х) ∨ В(y)),
∃хА(х) → ∀хВ(х) = ∀х∀y (А(х) → В(y)),
∃хА(х) ∨ ∀хВ(х) = ∃х∀y (А(х) ∨ В(y)) =
= ∀х∃y(А(х) ∨ В(y)) = ∀х∃y(А(y) ∨ В(х)).Последний пример показывает, что кванторы ∀ и ∃ можно переставлять местами, если они независимы (в данном случае они относятся к независимым одноместным предикатам).
Рассмотрим всевозможные комбинации кванторов при двухместных предикатах. С помощью законов коммутативности и ассоциативности, для конъюнкции и дизъюнкции доказывается справедливость двух тождеств:
∀х∀yР(х, y) = ∀y∀хР(х, y), ∃х∃yР(х, y) = ∃y∃хР(х, y),
т.е. одинаковые кванторы при двухместных предикатах можно переставлять местами. Но перестановка кванторов ∃ и ∀ подчинена только отношению порядка:
∃х∀yР(х, y) ⇒ ∀y∃хР(х, y).В самом деле,
∃х∀yР(х, y) = ∃х(Р(х, a) ∧ Р(х, b)) =
= (Р(a, a) ∧ Р(a, b)) ∨ (Р(b, a) ∧ Р(b, b)) = R ∧ Q,
где
Q = (Р(a, a) ∨ Р(b, b)) ∧ (Р(a, b) ∨ Р(b, a)).
R = (Р(a, a) ∨ Р(b, a)) ∧ (Р(a, b) ∨ Р(b, b)) =
∀y(Р(a, y) ∨ Р(b, y)) = ∀y∃хР(х, y).Таким образом, исходная клауза свелась к аксиоме порядка —
R, Q ⇒ R.Справедливость последней клаузы можно установить и с помощью таблицы истинности (табл. 1.26), в которой приняты следующие сокращения:
∀∀Р = ∀х∀yР(х, y), ∃∀Р = ∃х∀yР(х, y),
∀∃Р = ∀y∃хР(х, y), ∃∃Р = ∃х∃yР(х, y).Таблица 1.26
P(a, a) P(a, b) P(b, a) P(b, b) ∀∀P ∃∀P ∀∃P ∃∃P 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 1 0 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 На основе этой же таблицы можно установить истинность множества других клауз (k и m принимают значения a или b):
1. ∀х∀yР(х, y) ⇒ ∀х∃yР(х, y),
2. ∀х∀yР(х, y) ⇒ ∃х∀ yР(х, y),
3. ∀х∀yР(х, y) ⇒ ∃х∃yР(х, y),
4. ∃х∀yР(х, y) ⇒ ∃х∃yР(х, y),
5. ∀х∃yР(х, y) ⇒ ∃х∃yР(х, y),
6. ∃х∀ yР(х, y) ⇒ ∀ y∃хР(х, y),
7. ∀х∀ yР(х, y) ⇒ ∀хР(х, x),
8. ∃хР(х, x) ⇒ ∃х∃yР(х, y),
9. ∀х∀ yР(х, y) ⇒ Р(k, m),
10. Р(k, m) ⇒ ∃х∃yР(х, y),
11. ∀ yР(k, y) ⇒ ∀y∃хР(х, y),
12. ∀yР(k, y) ⇒ ∃х∀ yР(х, y),
13. ∀хР(х, m) ⇒ ∃y∀хР(х, y),
14. ∀хР(х, m) ⇒ ∀х∃yР(х, y),
15. ∀х∃y Р(х, y) ⇒ ∃yР(k, y),
16. ∃y∀хР(х, y) ⇒ ∃yР(k, y),
17. ∃х∀ yР(х, y) ⇒ ∃хР(х, m),
18. ∀y∃хР(х, y) ⇒ ∃хР(х, m).Пять первых клауз из приведенного списка сейчас особенно важны, так как они дают ключ к пониманию процедуры составления истинных клауз для многоместных предикатов с любым числом кванторов. Эту процедуру схематично можно пояснить следующим образом. Для одноместных предикатов справедливы три клаузы:
∀Р ⇒ ∀Р, ∀Р ⇒ ∃Р, ∃Р ⇒ ∃Р.Клауза ∃Р ⇒ ∀Р ошибочна. Для двухместных предикатов будут верны уже девять клауз, четыре из которых являются тождествами, а пять других как раз и возглавляют приведенный список:
∀(∀Р) ⇒ ∀(∀Р), ∀(∀Р) ⇒ ∃(∀Р), ∃(∀Р) ⇒ ∃(∀Р),
∀(∀Р) ⇒ ∀(∃Р), ∀(∀Р) ⇒ ∃(∃Р), ∃(∀Р) ⇒ ∃(∃Р),
∀(∃Р) ⇒ ∀(∃Р), ∀(∃Р) ⇒ ∃(∃Р), ∃(∃Р) ⇒ ∃(∃Р).Клаузы-тождества не следует отбрасывать, если мы хотим построить следующий ряд для трехместных предикатов, например:
∀(∀∀Р) ⇒ ∃(∀∀Р), ∀(∀∃Р) ⇒ ∃(∀∃Р).Зная процедуру построения правильных клауз, легко распознать истинность клауз, в частности:
∃∀∀∃∀Р ⇒ ∃∃∀∃∃Р — истинная,
∃∃∀∃∀Р ⇒ ∃∀∀∃∃Р — ложная.Соседние одинаковые кванторы в многоместных предикатах можно переставлять в любом направлении; что же касается различных кванторов, то здесь допустима лишь перестановка, описанная клаузой 6 в вышеприведенном списке:
... ∃u∀v ... P(... u, v ...) ⇒ ... ∀v∃u ... P(... u, v ...).Одинаковые кванторы могут быть объединены по схеме, продиктованной клаузами 7 и 8:
... ∀u∀v ... P(... u, v ...) ⇒ ... ∀u ... P(... u, u ...),
... ∃v ... P(... v, v ...) ⇒ ... ∃u∃v ... P(... u, v ...).Законы конкретизации, представленные в списке следующими десятью клаузами (с 8 по 18) и являющиеся производными от первых шести клауз, естественно, распространяются и на многоместные предикаты.
В отношении дизъюнкции и конъюнкции двух многоместных предикатов действуют примерно те же законы эквивалентности, что и для одноместных. Если все кванторы соответствуют операции, то введение дополнительных переменных необязательно, например:
∀x∀y(A(x, y) ∧ B(x, y)) = ∀x∀yA(x, y) ∧ ∀x∀yB(x, y).Во всех остальных случаях необходимо вводить переменные:
∀x∃y∀z∃u∀v∀w(A(x, y, z) ∨ B(u, v, w)) =
= ∀x∃y∀zA(x, y, z) ∨ ∃u∀v∀wB(u, v, w).Формализм теории предикатов, конечно, будет неполным без рассмотрения операции отрицания многоместных предикатов. Для понимания существа дела достаточно привести одно доказательство для двухместного предиката:
∃x∀yР(x, y) = ∃x(Р(x, a) ∧ Р(x, b)) =
= ∀x(Р(x, a) ∧ Р(x, b)) = ∀x∀yР(x, y) =
= (Р(a, a) ∨ Р(a, b)) ∧ (Р(b, a) ∨ Р(b, b)) =
= ∀x∃yР(x, y).Отсюда вытекает простое правило перемещения символа отрицания слева направо для многоместных предикатов, например:
∀∀∃∀∃Р = ∃∀∃∀∃Р = ∃∃∃∀∃Р =
= ∃∃∀∀∃Р = ∃∃∀∃∃Р = ∃∃∀∃∀Р.Таким образом, чтобы произвести полное отрицание многоместного предиката с кванторами, необходимо прибегнуть к замене:
∃ ⇔ ∀, Р ⇔ Р.
|
|
