Дискретная математика:
логика, группы, графы, фракталыАкимов О.Е.
1.5. Операции над предикатами и кванторами
Разбор решений задач по логике предикатов
1. Установим истинность следующих логических выражений путем конкретизации.
Для варианта 10 имеем следующее тождество:
∃x (A(x) → B(x)) = ∀x A(x) → ∃x B(x).
Доказательство:
∃x (A(x) → B(x)) = (A(a) → B(a)) ∨ (A(b) → B(b)) =
= A(a) ∨ B(a) ∨ A(b) ∨ B(b) = (A(a) ∨ A(b)) ∨ (B(a) ∨ B(b)) =
= ∃x A(x) ∨ ∃x B(x) = ∀x A(x) → ∃x B(x).
Для варианта 19 имеем следующую клаузу:
∃x∀y P(x, y) ⇒ ∃x P(b, x).
Для доказательства ее истинности избавимся от кванторов в обеих частях клаузы:
(Р(a, a) ∧ Р(a, b)) ∨ (Р(b, a) ∧ Р(b, b)) ⇒ Р(b, a) ∨ Р(b, b) ;
Р(a, a) ∨ Р(a, b), Р(a, b) ∨ Р(b, a),
Р(a, a) ∨ Р(b, b), Р(b, a) ∨ Р(b, b), Р(b, a) ⇒ Р(b, b) ;
Р(a, a) ∨ Р(a, b), Р(a, b) ∨ Р(b, a), Р(a, a) ∨ Р(b, b),Р(b, b) ⇒ Р(b, b) .
Последняя клауза верна в силу аксиомы порядка.
2. Решения для второго задания приведем для всех вариантов. Ответы нетрудно будет отыскать, если знать, каким образом были составлены логические выражения. Замена в соответствии с принципом двойственности предполагает одновременную перестановку местами всех заключений и посылок, а также замену обозначений:
∀ ⇔ ∃, ∨ ⇔ ∧, sup ⇔ inf, (,) ⇔ (;), A ⇔ B,
a ⇒ b, b ⇒ c, c ⇒ a, x ⇔ u, y ⇔ v, z ⇔ w.
Для варианта 1: из принципа двойственности по варианту 9.
Для варианта 2: B3 ∨ C1, A1 ∨ B1 ⇒ A2; B2 ∧ C2.
A1 = A'1 ∨ A''1 = ∃x∀z A(x, z, z) ∨ ∀u A(a, b, u),
A2 = sup(A'1, A''1) = ∃v∀w A(v, b, w), A1 ⇒ A2,
B1 = inf (B'2, B''2) = ∀x B(a, x, x), B1 ⇒ B2,
B2 = B'2 ∧ B''2 = ∃u∀v B(u, v, v) ∧ ∀u∃z B(u, b, z),
B1 ⇒ B3 = ∃x∀z B(x, b, z),
C2 = C'2 ∧ C''2 = ∃u A(a, u, c) ∧ ∃x∀z A(x, b, z),
C1 = inf (C'2, C''2) = ∀w A(w, b, w).
Для варианта 3: из принципа двойственности по варианту 2.
Для варианта 4: из принципа двойственности по варианту 10.
Для варианта 5: A1, B3 → C1 ⇒ A2 ∧ B1; C'2 ∧ B2 ∧ C''2 ,
A1, B3 ∨ C1, A2 ∨ B1, B2 ∨ C2 ⇒ 0,
A1 = ∀x∀z A(x, x, z), A2 = ∃u∃v A(u, v, v), A1 ⇒ A2 ,
B1 = ∃z B(z, z, z), B2 = ∃y B(a, y, a), B1 ⇒ B2,
B3 = ∃x∃y B(x, x, y), B1 ⇒ B3,
C1 = inf (C'2, C''2) = ∀z A(z, b, z), C1 ⇒ C2 ,
C2 = C'2 ∧ C''2 = ∀u∃v A(a, v, u) ∧ ∃x A(x, b, c).
Для варианта 6: из принципа двойственности по варианту 13.
Для варианта 7: из принципа двойственности по варианту 12.
Для варианта 8:
A'1 ∨ A''1, B1 ∨ C'1 ⇒ A2 ∧ C2; B2 ∧ C''1 ,
A'1 ∨ A''1, B1 ∨ C'1, A2 ∨ C2, B2 ∨ C''1 ⇒ 0, A1 ⇒ A2,
A1 = A'1 ∨ A''1 = ∀y∀z A(a, y, z) ∨ ∀v∃w A(w, v, v),
A2 = ∃u∀z A(u, z, c), B1 = ∀x∀z B(x, a, z), B1 ⇒ B2,
B2 = ∃y B(b, y, b), C'1 = ∀x B(x, c, a), C'1 ⇒ C2,
C2 = ∃x B(x, x, a), C''1 = ∀y B(c, y, a), C''1 ⇒ C2.
Для варианта 9: по клаузе 8 со следующими обозначениями:
A1 = A'1 ∨ A''1 = ∀z∃x A(a, x, z) ∨ ∀w∃u A(u, b, w),
A2 = ∃x A(x, x, c), B1 = ∀z A(z, b, z),
B2 = ∃w A(a, w, w), C2 = ∃v∃w B(v, v, w),
C'1 = ∀x B(x, x, x), C''1 = ∃y B(a, y, a).
Для варианта 10:
A'1 ∨ B1 ∨ A''1, B3 → C1 ⇒ B'2 ∧ C2 ∧ B''2; A2 ,
A'1 ∨ B1 ∨ A''1, B3 ∨ C1, B'2 ∨ C2 ∨ B''2, A2 ⇒ 0,
A1 = A'1 ∨ A''1 = ∀y∀z A(a, y, z) ∨ ∀y∃x A(x, y, c),
A2 = sup (A'1, A''1) = ∃u∀w A(u, w, c),
B1 = inf (B'2,B''2) = ∀w B(a, w, w),
B2 = B'2 ∧ B''2 = ∃x∀z B(x, z, z) ∧ ∀w∃u B(u, b, w),
B3 = ∃u∀zB(u, u, z), A1 ⇒ A2, B1 ⇒ B2, B1 ⇒ B3,
C1 = ∃x∀y A(x, y, a), C2 = ∀w∃z A(z, w, w), C1 ⇒ C2.
Для варианта 11: из принципа двойственности по варианту 5.
Для варианта 12: по клаузе 10 со следующими обозначениями:
A1 = A'1 ∨ A''1 = ∀y∀z A(a, y, z) ∨ ∀u∃v A(v, u, c),
A2 = ∃z∀x A(z, x, c), B1 = ∀w B(w, b, w),
B3 = ∃x B(x, b, c), C1 = ∀y∀z A(z, y, z),
B2 = B'2 ∧ B''2 = ∃x∀z B(a, x, z) ∧ ∀z∃x B(x, b, z),
C2 = C'2 ∧ C''2 = A(b, b, b) ∧ ∃z A(a, z, z).
Для варианта 13:
A2 → (B2 → C'1), B1 ∨ C''1 ∨ D1 ⇒ A1 → C2; D2,
A2 ∨ B2 ∨ C'1, B1 ∨ C''1 ∨ D1, A1, C2, D2 ⇒ 0,
A1 = ∀x A(x, x, c), A2 = ∃u A(u, b, c), A1 ⇒ A2,
B1 = ∃y B(a, y, a), B2 = ∃v∃w B(v, v, w), B1 ⇒ B2,
C'1 = ∃v A(b, v, v), C''1 = ∀x A(b, x, x),
C2 = ∃y∃z A(b, y, z), C'1 ⇒ C2, C''1 ⇒ C2,
D1 = ∀x∀u B(x, u, b), D2 = B(a, a, b), D1 ⇒ D2.
Для варианта 14: из принципа двойственности по варианту 16.
Для варианта 15: из принципа двойственности по варианту 8.
Для варианта 16: по клаузе 13 со следующими обозначениями:
A1 = ∀z A(a, b, z), A2 = ∃x A(x, b, c), B1 = ∀w∃z B(w, z, w),
B2 = ∃x∀z B(a, x, z), C'1 = ∀z A(b, a, z), C''1 = ∃x∀z A(x, z, z),
C2 = ∃u∀w A(u, a, w), D1 = ∀z B(z, c, z), D2 = ∃w B(c, w, w).
Для варианта 17:
A, (A → C) → (A ∧ B1) ⇒ B'2 ∧ B''2,
A, B'2 ∨ B''2, A ∨ B1, A ∨ C, C ∨ B1 ⇒ 0,
A = ∀x∃z A(z, b, x) = ∀z∃x A(x, b, z) = ∀u∃y A(y, b, u),
B1 = ∀x∃y∀z B(x, y, z) = inf (B'2, B''2) ⇒ B'2 ∧ B''2 =
= ∀u∃w∃v B(u, v, w) ∧ ∃u∃z∀v B(z, u, v), C = ∀x∀z B(x, a, z).
Для варианта 18:
(A → B1) → (B1 ∨ C), C ⇒ B'2 ∧ B''2,
A = ∀u A(u, a, b), C = ∀x∃y A(x, y, a),
B1 = inf (B'2, B''2) = ∀u∃v∀w B(u, v, w) = ∀z∃y∀x B(z, y, x) ⇒
⇒ B'2 ∧ B''2 = ∀u∃w∃v B(u, v, w) ∧ ∃x∃y∀z B(x, y, z).
Для варианта 19:
C, A1 ∨ B, B → C ⇒ A'2 ∧ A''2,
A1 = inf (A'2, A''2) = ∃u∀y∀x A(u, x, y) ⇒ A'2 ∧ A''2 =
= ∃u∃v∀w A(u, v, w) ∧ ∃v∃w∀u A(w, v, u),
B = ∀x∃z B(x, a, z) = ∀z∃x B(z, a, x),
C = ∀x∃y∀z B(x, y, z) = ∀u∃v∀w B(u, v, w).
Для варианта 20:
A → C1, B → C1, A ∨ B ⇒ C'2 ∧ C''2,
A = ∀x∃y A(y, x) = ∀y∃x A(x, y), B = ∃u∀v A(u, v) = ∃v∀u A(v, u),
C1 = ∀x∀y∃z B(x, y, z) = ∀z∀x∃y B(x, z, y) =
= inf (C'2, C''2) ⇒ C'2 ∧ C''2 =
= ∀y∀z∃x B(z, y, x) ∧ ∃y∀z∃x B(y, z, x).
Для варианта 21:
B2 → A''1, B1 ∨ C1, C2 → A'1 ⇒ A'2 ∧ A''2,
A'1 = A(a, b, c),A''1 = A(a, b, d),A1 = ∃z A(a, b, z) =
= inf (A'2, A''2) ⇒ A'2 ∧ A''2 =
= ∀x∃z A(x, b, z) ∧ ∀y∃z A(a, y, z),
B1 = ∀y∀z A(b, y, z) ⇒ ∃x∀y∀z A(x, y, z) = B2,
C1 = ∃x∀z A(x, a, z) ⇒ ∃x∃y∀z A(x, y, z) = C2.
Для варианта 22:
C' ∨ C'' ⇒ B, (B → A) → (B ∨ C),
A = ∃y∀x A(a, x, y), C = ∀u∀z∃x A(z, u, x) = sup (C', C''),
B = ∀x∃z B(x, b, z) = ∀u∃v B(u, b, v) = ∀z∃x B(z, b, x),
∀x∃y∃z A(x, z, y) ∨ ∃u∀v∃w A(u, v, w) = C' ∨ C'' ⇒ C.
Для варианта 23:
A1 ∨ B'1 ∨ C', A2 ∨ B''1 ∨ C'', B2 ⇒ C1 ∧ C2,
A1 ⇒ A2, B'1 ⇒ B2, B''1 ⇒ B2, C' ⇒ C,
A1 = ∀u∀v∀w A(u, v, w), A2 = ∀x A(x, a, b),
B'1 = ∀x∃y B(x, b, y), B''1 = ∀y∃z B(a, y, z),
B2 = ∃w B(a, b, w), C'' ⇒ C ⇒ C1 ∧ C2, C' = ∀u∀v C(u, v, b),
C'' = ∀v∀u C(v, u, a), C = ∀u∀v∃w C(u, v, w),
C1 = ∀u∃v∃w C(u, v, w), C2 = ∃x∀y∃z C(x, y, z).
Для варианта 24: из принципа двойственности по варианту 21.
Для варианта 25:
B2 → A'1, A''1 ∨ B1, D ⇒ C ∧ A2; A2,
A'1 = ∀u∀v A(b, v, u), A''1 = ∀u∀v A(v, u, a),
A2 = ∃x∀y∃z A(x, y, z), A'1 ⇒ A2, A''1 ⇒ A2,
B1 = ∀y∃u∀z B(u, y, z), B2 = ∃y∀z B(y, a, z), B1 ⇒ B2 ,
C = ∃y B(a, y, b), D = ∀z B(z, z, z), C ∧ A2; A2 = A2.
3. Для легенды варианта 2 практического задания 3 (c. 66) введем следующие предикаты:
A(x, y, z) — «x уважает y по причине z».
B(x, y, v) — «x дает y материальные средства v».
C(x, y, w) — «y возвращает x долг, выраженный в w».Области определения переменных:
x = {a, b, ...}, где a — бизнесмен, b — банкир, ...
y = {c, d, ...}, где c — художник, d — скульптор, ...
z = {e, f, ...}, где e — жалость, f — мастерство, ...
v = {i, j, ...},где i — деньги, j — помощь в организации выставки,
w = {g, h, ...}, где g — деньги, h — добрая репутация.Посылки: «Если некоторый x уважает некоторого y по причине некоторого z, то первый всегда окажет второму конкретную материальную помощь, если имеется определенная вероятность того, что y как-то компенсирует затраты x»:
∃x∃y∃zA(x, y, z) → (∃x∃y∃w C(x, y, w) → ∀x∀y∀v B(x, y, v)).
Из приведенной легенды следует, что «бизнесмен уважает художника за его мастерство»: A(a, c, f). Понятно также, что «бизнесмен будет иметь добрую репутацию мецената за то, что он помог художнику в организации выставки его картин»: C(a, c, h).
Заключение: «бизнесмен поможет художнику организовать выставку его картин»: B(a, c, j). Доказать истинность составленной из этих предикатов клаузы не составит большого труда.
Для легенды варианта 5 практического задания 3 (c. 67) можно ввести следующие предикаты: A(x, y) — «x извергает y». B — «Высокая урожайность». C(z) — «Источником блага является z».
Области:
x = {a, b, ...}, где a — вулкан, b — гроза,...
y = {c, d, ...}, где c — пепел, d — вода,...
z = {e, f, ...}, где e — Бог, f — природа...Посылки: «все x извергают какие-то y»: ∀x∃y A(x, y); «если некоторые x извергают какие-то y, то будет высокая урожайность»: ∃x∃y A(x, y) → B ; «высокая урожайность всегда несет благо людям»: B → ∀z C(z).
Заключение: «то, что источником блага является Господь Бог, не противоречит исходным посылкам»: C(e). Доказательство очевидно.
4. Произведем трассировку работы ПРОЛОГ-программы «Родственные отношения» для первой цели варианта 12. Для этого имеющуюся программу дополним клаузой:
81) свекор (x, y) ⇐
82) отец (x, z),
83) отец (z, u),
84) мать (y, u).
Цель:
85) свекор (Петр, y).
Трассировка программы:
1. В: цель ( ) – 85,
2. В: свекор (Петр, _) – 81,
3. В: отец (Петр, _) – 82,
4. П: отец (Петр, _) – 35,
...
15. П: отец (Петр, _) – 46,
16. У: отец (Петр, Ефим) – 47у,
17. В: отец (Ефим, _) – 83,
18. П: отец (Ефим, _) – 35,
...
26. П: отец (Ефим, _) – 43,
27. У: отец (Ефим, Анатолий) – 44у,
28. В: мать (_, Анатолий) – 84,
29. П: мать (_, Анатолий) – 54,
...
39. П: мать (_, Анатолий) – 64,
40. У: мать (Татьяна, Анатолий) – 65у,
41. У: цель ( ) – 85.Из соответствующих фактов и правил составим противоречие:
свекор (Петр, y) ∨ отец (Петр, z) ∨ отец (z, u) ∨ мать (y, u), отец (Петр, Ефим), отец (Ефим, Анатолий), мать (Татьяна, Анатолий) ⇒ 0.
Целевой дизъюнкт нейтрализуется предикатами под номерами 47, 44 и 65, когда переменные принимают конкретные значения:
y = Татьяна, z = Ефим, u = Анатолий.
|
|
