Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

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 имеем следующую клаузу:

xy 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,

ab, bc, ca, xu, yv, zw.

Для варианта 1: из принципа двойственности по варианту 9.

Для варианта 2: B3 ∨ C1, A1 ∨ B1 ⇒ A2; B2 ∧ C2.

A1 = A'1 ∨ A''1 = ∃xz A(x, z, z) ∨ ∀u A(a, b, u),

A2 = sup(A'1, A''1) = ∃vw A(v, b, w), A1 ⇒ A2,

B1 = inf (B'2, B''2) = ∀x B(a, x, x), B1 ⇒ B2,

B2 = B'2 ∧ B''2 = ∃uv B(u, v, v) ∧ ∀uz B(u, b, z),

B1 ⇒ B3 = ∃xz B(x, b, z),

C2 = C'2 ∧ C''2 = ∃u A(a, u, c) ∧ ∃xz 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 = ∀xz A(x, x, z), A2 = ∃uv A(u, v, v), A1 ⇒ A2 ,

B1 = ∃z B(z, z, z), B2 = ∃y B(a, y, a), B1 ⇒ B2,

B3 = ∃xy B(x, x, y), B1 ⇒ B3,

C1 = inf (C'2, C''2) = ∀z A(z, b, z), C1 ⇒ C2 ,

C2 = C'2 ∧ C''2 = ∀uv A(a, v, u) ∧ ∃x A(x, b, c).

Для варианта 6: из принципа двойственности по варианту 13.

Для варианта 7: из принципа двойственности по варианту 12.

Для варианта 8:

A'1 ∨ A''1, B1 ∨ C'1 ⇒ A2 ∧ C2; B2C''1 ,

A'1 ∨ A''1, B1 ∨ C'1, A2 C2, B2 ∨ C''1 ⇒ 0, A1 ⇒ A2,

A1 = A'1 ∨ A''1 = ∀yz A(a, y, z) ∨ ∀vw A(w, v, v),

A2 = ∃uz A(u, z, c), B1 = ∀xz 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 = ∀zx A(a, x, z) ∨ ∀wu A(u, b, w),

A2 = ∃x A(x, x, c), B1 = ∀z A(z, b, z),

B2 = ∃w A(a, w, w), C2 = ∃vw 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 C2B''2, A2 ⇒ 0,

A1 = A'1 ∨ A''1 = ∀yz A(a, y, z) ∨ ∀yx A(x, y, c),

A2 = sup (A'1, A''1) = ∃uw A(u, w, c),

B1 = inf (B'2,B''2) = ∀w B(a, w, w),

B2 = B'2 ∧ B''2 = ∃xz B(x, z, z) ∧ ∀wu B(u, b, w),

B3 = ∃uzB(u, u, z), A1 ⇒ A2, B1 ⇒ B2, B1 ⇒ B3,

C1 = ∃xy A(x, y, a), C2 = ∀wz A(z, w, w), C1 ⇒ C2.

Для варианта 11: из принципа двойственности по варианту 5.

Для варианта 12: по клаузе 10 со следующими обозначениями:

A1 = A'1 ∨ A''1 = ∀yz A(a, y, z) ∨ ∀uv A(v, u, c),

A2 = ∃zx A(z, x, c), B1 = ∀w B(w, b, w),

B3 = ∃x B(x, b, c), C1 = ∀yz A(z, y, z),

B2 = B'2 ∧ B''2 = ∃xz B(a, x, z) ∧ ∀zx 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 = ∃vw B(v, v, w), B1 ⇒ B2,

C'1 = ∃v A(b, v, v), C''1 = ∀x A(b, x, x),

C2 = ∃yz A(b, y, z), C'1 ⇒ C2, C''1 ⇒ C2,

D1 = ∀xu 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 = ∀wz B(w, z, w),

B2 = ∃xz B(a, x, z), C'1 = ∀z A(b, a, z), C''1 = ∃xz A(x, z, z),

C2 = ∃uw 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'2B''2, A ∨ B1, AC, C ∨ B1 ⇒ 0,

A = ∀xz A(z, b, x) = ∀zx A(x, b, z) = ∀uy A(y, b, u),

B1 = ∀xyz B(x, y, z) = inf (B'2, B''2) ⇒ B'2 ∧ B''2 =

= ∀uwv B(u, v, w) ∧ ∃uzv B(z, u, v), C = ∀xz B(x, a, z).

Для варианта 18:

(A → B1) → (B1 ∨ C), C ⇒ B'2 ∧ B''2,

A = ∀u A(u, a, b), C = ∀xy A(x, y, a),

B1 = inf (B'2, B''2) = ∀uvw B(u, v, w) = ∀zyx B(z, y, x) ⇒  

⇒ B'2 ∧ B''2 = ∀uwv B(u, v, w) ∧ ∃xyz B(x, y, z).

Для варианта 19:

C, A1 ∨ B, B → C ⇒ A'2 ∧ A''2,

A1 = inf (A'2, A''2) = ∃uyx A(u, x, y) ⇒ A'2 ∧ A''2 =

= ∃uvw A(u, v, w) ∧ ∃vwu A(w, v, u),

B = ∀xz B(x, a, z) = ∀zx B(z, a, x),

C = ∀xyz B(x, y, z) = ∀uvw B(u, v, w).

Для варианта 20:

A → C1, B → C1, A ∨ B ⇒ C'2 ∧ C''2,

A = ∀xy A(y, x) = ∀yx A(x, y), B = ∃uv A(u, v) = ∃vu A(v, u),

C1 = ∀xyz B(x, y, z) = ∀zxy B(x, z, y) =

= inf (C'2, C''2) ⇒ C'2 ∧ C''2 =

= ∀yzx B(z, y, x) ∧ ∃yzx 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 =

= ∀xz A(x, b, z) ∧ ∀yz A(a, y, z),

B1 = ∀yz A(b, y, z) ⇒ ∃xyz A(x, y, z) = B2,

C1 = ∃xz A(x, a, z) ⇒ ∃xyz A(x, y, z) = C2.

Для варианта 22:

C' ∨ C'' ⇒ B, (B → A) → (B ∨ C),

A = ∃yx A(a, x, y), C = ∀uzx A(z, u, x) = sup (C', C''),

B = ∀xz B(x, b, z) = ∀uv B(u, b, v) = ∀zx B(z, b, x),

xyz A(x, z, y) ∨ ∃uvw 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 = ∀uvw A(u, v, w), A2 = ∀x A(x, a, b),

B'1 = ∀xy B(x, b, y), B''1 = ∀yz B(a, y, z),

B2 = ∃w B(a, b, w), C'' ⇒ C ⇒ C1 ∧ C2, C' = ∀uv C(u, v, b),

C'' = ∀vu C(v, u, a), C = ∀uvw C(u, v, w),

C1 = ∀uvw C(u, v, w), C2 = ∃xyz C(x, y, z).

Для варианта 24: из принципа двойственности по варианту 21.

Для варианта 25:

B2 → A'1, A''1 ∨ B1, D ⇒ C ∧ A2; A2,

A'1 = ∀uv A(b, v, u), A''1 = ∀uv A(v, u, a),

A2 = ∃xyz A(x, y, z), A'1 ⇒ A2, A''1 ⇒ A2,

B1 = ∀yuz B(u, y, z), B2 = ∃yz 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»:

xyzA(x, y, z) → (∃xyw C(x, y, w) → ∀xyv 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»: ∀xy A(x, y); «если некоторые x извергают какие-то y, то будет высокая урожайность»: ∃xy 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 = Анатолий.


 
  


Hosted by uCoz