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

Акимов О.Е.

1.5. Операции над предикатами и кванторами

Практические задания по логике предикатов

1. Установить истинность логического выражения своего варианта путем конкретизации.

1. ∀x∀y P(x, y) ⇒ ∃x∃y P(x, y),

2. ∀x∃y (A(y) ∨ B(x)) = ∃x A(x) ∨ ∀x B(x),

3. ∃x (B(x) ∧ A) = ∃x B(x) ∧ A,

4. ∃x (A(x) → B) = ∀x A(x) → B,

5. ∀x∀y P(x, y) ⇒ ∀x P(x, x),

6. ∃x (A(x) ∨ B(x)) = ∃x A(x) ∨ ∃x B(x),

7. ∃x A(x) → ∀x B(x) ⇒ ∀x (A(x) → B(x)),

8. ∀x (A(x) → B) = ∃x A(x) → B,

9. ∀x∀y (A(x) → B(y)) = ∃x A(x) → ∀x B(x),

10. ∃x (A(x) → B(x)) = ∀x A(x) → ∃x B(x),

11. ∀x A(x) ∨ ∀x B(x) ⇒ ∀x (A(x) ∨ B(x)),

12. ∃x A(x) ∨ ∀x B(x) = ∃x∀y (A(x) ∨ B(y)),

13. ∃x (A → B(x)) = A → ∃x B(x),

14. ∀x∀y P(x, y) ⇒ ∀x∃y P(x, y),

15. ∃x∀y P(x, y) ⇒ ∃x∃y P(x, y),

16. ∀x∃y P(x, y) ⇒ ∃x∃y P(x, y),

17. ∃x∀y (A(x) ∨ B(y)) = ∀y∃x (A(x) ∨ B(y)),

18. ∀y P(a, y) ⇒ ∀y∃x P(x, y),

19. ∃x∀y P(x, y) ⇒ ∃x P(x, b),

20. ∀x (A ∨ B(x)) = A ∨ ∀x B(x),

21. ∀x A(x) ∨ ∀x B(x) = ∀x∀y (A(x) ∨ B(y)),

22. ∃x A(x) → ∀x B(x) = ∀x∀y (A(x) → B(y)),

23. ∀x (A → B(x)) = A → ∀x B(x),

24. ∃x P(x, x) ⇒ ∃x∃y P(x, y),

25. ∀x P(x, b) ⇒ ∃y∀x P(x, y).

2. Доказать истинность предикатных клауз методом резолюций.
Здесь были ошибки; сейчас они устранены; проверено 18.12.2012

1. ∀z B(b, z, z) ∨ ∃v A(b, v, b), ∀u B(u, u, a) ∨ ∀y∀z A(y, y, z) ⇒ ∃w B(w, c, w) ∧ ∃u A(u, u, u); ∃w∀u B(b, u, w) ∧ ∃z∀x B(x, c, z).

2. ∃x∀z B(x, b, z) → ∀w A(w, b, w), ∃x∀z A(x, z, z) ∨ ∀x B(a, x, x) ∨ ∀u A(a, b, u) ⇒ ∃v∀w A(v, b, w);∃u∀v B(u, v, v) ∧ ∃u A(a, u, c) ∧ ∀u∃z B(u, b, z) ∧ ∃x∀z A(x, b, z).

3. ∀y∃z B(y, c, z), ∀x∃y A(x, y, y) ∨ ∀x B(b, x, a) ∨ ∃x∀w A(x, c, w) ∨ ∀u∃w B(u, c, w) ⇒ ∃z B(z, c, z) ∧ ∀u∃w A(u, c, w); ∀u∃w B(u, w, w) ∧ ∃u A(b, u, u) ∧ ∃x B(b, c, x).

4. ∀x∃z B(x, z, a), ∀u∃w A(u, w, w) ∨ ∃z∀w B(w, z, z) ∨ ∃z∀x A(x, c, z) ⇒ ∀x∃w A(x, x, w) ∧ ∀u∃v B(u, v, b); ∃v∃w B(b, v, w) ∧ ∃z A(b, z, z) ∧ ∃v∀u B(u, v, a).

5. ∀x∀z A(x, x, z), ∃x∃y B(x, x, y) → ∀z A(z, b, z) ⇒ ∃u∃v A(u, v, v) ∧ ∃z B(z, z, z); ∀u∃v A(a, v, u) ∧ ∃y B(a, y, a) ∧ ∃x A(x, b, c). 

6. A(b, b, c), ∀v∀w B(c, v, w), ∀u B(u, u, a) ⇒ ∀v A(b, v, b) ∧ ∃u B(c, u, u) ∧ ∃u∃x A(u, x, c); ∀x B(x, c, a) ∧ ∀y∀z A(y, y, z) ∧ ∀y B(c, y, y).

7. ∀u∃w A(b, u, w) ∨ B(c, c, c) ∨ ∃w∀u A(u, c, w) ∨ ∀w B(b, w, w), ∀w∃u B(w, u, a) ⇒ ∃u A(u, c, a) ∧ ∃v∃w B(w, v, w); ∃v∃w B(b, v, w) ∧ ∃z A(z, c, z) ∧ ∃x∀y B(y, x, a).

8. ∀y∀z A(a, y, z) ∨ ∀v∃w A(w, v, v), ∀x∀z B(x, a, z) ∨ ∀x B(x, c, a) ⇒ ∃u∀z A(u, z, c) ∧ ∃x B(x, x, a); ∃y B(b, y, b) ∧ ∃y B(c, y, a).

9. ∀z A(z, b, z) ∨ ∀x B(x, x, x), ∀z∃x A(a, x, z) ∨ ∀w∃u A(u, b, w) ⇒ ∃w A(a, w, w) ∧ ∀y B(a, y, a); ∃x A(x, x, c) ∧ ∃v∃w B(v, v, w).

10. ∀y∀zA(a, y, z) ∨ ∀wB(a, w, w) ∨ ∀y∃xA(x, y, c), ∃u∀zB(u, u, z) → ∃x∀yA(x, y, a) ⇒ ∃x∀z B(x, z, z) ∧ ∀w∃z A(z, w, w) ∧ ∀w∃u B(u, b, w); ∃u∀w A(u, w, c).

11. ∀x∀y B(x, y, y) ∨ ∀w A(w, w, w), ∃x∀y B(b, y, x) ∨ ∀v A(b, v, b) ∨ ∀u B(u, c, a) ⇒ ∃u∃w B(u, u, w); ∀u∀v A(u, u, v) ∧ ∃w B(w, c, w).

12. ∀y∀z A(a, y, z) ∨ ∀w B(w, b, w) ∨ ∀u∃v A(v, u, c), ∃x B(x, b, c) → ∀y∀z A(z, y, z) ⇒ ∃z∀x A(z, x, c); ∃x∀z B(a, x, z) ∧ A(b, b, b) ∧ ∀z∃x B(x, b, z) ∧ ∃z A(a, z, z).

13. ∃u A(u, b, c) → (∃v∃w B(v, v, w) → ∃v A(b, v, v)), ∃y B(a, y, a) ∨ ∀x A(b, x, x) ∨ ∀x∀u B(x, u, b) ⇒ ∀x A(x, x, c) → ∃y∃z A(b, y, z); B(a, a, b).

14. ∀w B(b, c, w), ∀x∃z B(x, b, z), ∀z A(a, z, z) ⇒ ∃u B(u, c, a) ∧ ∃w B(c, b, w) ∧ ∃u∀w A(b, u, w); ∃z∀w A(z, w, z) ∧ ∀u∃w B(u, w, w) ∧ ∃w A(w, a, w).

15. ∀v A(a, v, b) ∨ ∀v A(c, v, c),∀u A(u, u, b) ∨ ∀x∃w B(x, w, a) ⇒ ∃v∃w B(b, v, w) ∧ ∃y∀z B(z, y, y);∃u∃w A(u, b, w) ∧ ∃u A(u, a, b).

16. ∃x A(x, b, c) → (∃x∀z B(a, x, z) → ∀z A(b, a, z)), ∀w∃z B(w, z, w) ∨ ∃x∀z A(x, z, z) ∨ ∀z B(z, c, z) ⇒ ∀z A(a, b, z) → ∃u∀w A(u, a, w); ∃w B(c, w, w).

17. ∃z∀x A(x, b, z), (∀x∃z A(z, b, x) → ∀x∀z B(x, a, z)) → (∃u∀y A(y, b, u) ∧ ∀x∃y∀z B(x, y, z)) ⇒ ∀u∃w∃v B(u, v, w) ∧ ∃u∃z∀v B(z, u, v).

18. (∀u A(u, a, b) → ∃z∀y∃x B(z, y, x)) → (∀u∃v∀w B(u, v, w) ∨ ∀x∃y A(x, y, a)), ∃u∀v A(u, v, a) ⇒ ∀u∃w∃v B(u, v, w) ∧ ∃x∃y∀z B(x, y, z).

19. ∃x∀y∃z B(x, y, z), ∃u∀y∀x A(u, x, y) ∨ ∀x∃z B(x, a, z), ∀z∃x B(z, a, x) → ∀u∃v∀w B(u, v, w) ⇒ ∃u∃v∀w A(u, v, w) ∧ ∃v∃w∀u A(w, v, u).

20. ∀x∃y A(y, x) → ∀x∀y∃z B(x, y, z), ∃u∀v A(u, v) → ∀z∀x∃y B(x, z, y), ∀y∃x A(x, y) ∨ ∃v∀u A(v, u) ⇒ ∀y∀z∃x B(z, y, x) ∧ ∃y∀z∃x B(y, z, x).

21. ∃x∀y∀z A(x, y, z) → A(a, b, c), ∀y∀z A(b, y, z) ∨ ∃x∀z A(x, a, z), ∃x∃y∀z A(x, y, z) → A(a, b, d) ⇒ ∀x∃z A(x, b, z) ∧ ∀y∃z A(a, y, z).

22. ∀x∃y∃z A(x, z, y) ∨ ∃u∀v∃w A(u, v, w) ⇒ ∃x∀z B(x, b, z), (∀u∃v B(u, b, v) → ∃y∀x A(a, x, y)) → (∀z∃x B(z, b, x) ∨ ∀u∀z∃x A(z, u, x)).

23. ∀u∀v∀w A(u, v, w) ∨ ∀x∃y B(x, b, y) ∨ ∀u∀v C(u, v, b), ∃x A(x, a, b) ∨ ∀y∃z B(a, y, z) ∨ ∀v∀u C(v, u, a), ∀w B(a, b, w) ⇒ ∀u∃v∃w C(u, v, w) ∧ ∃x∀y∃z C(x, y, z).

24. ∃u∀w A(u, a, w) ∨ ∃v∀w A(b, v, w) ⇒ ∃v∃w A(a, v, w) ∧ ∀u∃w A(u, b, w); ∀u∃v∃w A(u, v, w) ∧ A(b, a, d); A(b, a, c) ∧ ∀u∀v∃w A(u, v, w).

25. ∃y∀z B(y, a, z) → ∀u∀v A(b, v, u), ∀u∀v A(v, u, a) ∨ ∀y∃u∀z B(u, y, z), ∀z B(z, z, z) ⇒ ∃y B(a, y, b) ∧ ∃x∀y∃z A(x, y, z); ∃u∀v∃w A(u, v, w).

3. Для легенды вашего варианта (с.66, задание 3) введите соответствующие предикаты, составьте предикатную клаузу и докажите ее истинность методом резолюций. Если предикаты для вашей клаузы ввести затруднительно, придумайте новую легенду, для которой введение предикатов и кванторов было бы возможно.

4. Задана ПРОЛОГ-программа «Родственные отношения». Необходимо выполнить трассировку программы отдельно для двух целей, предварительно введя недостающие предикаты и правила. Так как может существовать несколько значений для переменных x и y, удовлетворяющих одной и той же цели, при трассировке допустимо ограничиться одним истинным значением x или y. Кроме того, ввиду большого числа повторных вызовов, можно указывать только первую и последнюю строки повторяющихся вызовов, например:

...
81. В: муж (Феликс) — 85,
82. П: муж (Феликс) — 1,
...
99. П: муж (Феликс) — 18,
100. У: муж (Феликс) — 19.

ПРОЛОГ-программа «Родственные отношения»

муж (x) — x мужчина.
дочь (x, y) — x дочь y.
жен (x) — x женщина.
сын (x, y) — x сын y.
отец (x, y) — x отец y.
род (x, y) — x родитель y.
мать (x, y) — x мать y.
брат (x, y) — x брат y.
сестра (x, y) — x сестра y.

Клаузы:

1) муж (Николай).
2) муж (Иван).
3) муж (Степан).
4) муж (Сергей).
5) муж (Павел).
6) муж (Игорь).
7) муж (Анатолий).
8) муж (Иосиф).
9) муж (Роман).
10) муж (Кирилл).
11) муж (Дмитрий).
12) муж (Максим).
13) муж (Евгений).
14) муж (Петр).
15) муж (Ефим).
16) муж (Юрий).
17) муж (Вадим).
18) муж (Олег).
19) муж (Феликс).
20) жен (Мария).
21) жен (Ольга).
22) жен (Татьяна).
23) жен (Жанна).
24) жен (Ирина).
25) жен (Алиса).
26) жен (Екатерина).
27) жен (Елена).
28) жен (Виктория).
29) жен (Полина).
30) жен (Луиза).
31) жен (Наталья).
32) жен (Барбара).
33) жен (Белла).
34) жен (Анна).
35) отец (Николай, Иван).
36) отец (Степан, Мария).
37) отец (Иван, Ольга).
38) отец (Иван, Сергей).
39) отец (Иван, Татьяна).
40) отец (Сергей, Виктория).
41) отец (Павел, Роман).
42) отец (Сергей, Дмитрий).
43) отец (Иосиф, Ирина).
44) отец (Ефим, Анатолий).
45) отец (Ефим, Полина).
46) отец (Юрий, Вадим).
47) отец (Петр, Ефим).
48) отец (Петр, Юрий).
49) отец (Петр, Анна).
50) отец (Максим, Петр).
51) отец (Дмитрий, Наталья).
52) отец (Феликс, Олег).
53) отец (Олег, Евгений).
54) мать (Алиса, Петр).
55) мать (Екатерина, Елена).
56) мать (Елена, Ефим).
57) мать (Елена, Юрий).
58) мать (Елена, Анна).
59) мать (Мария, Ольга).
60) мать (Анна, Виктория).
61) мать (Луиза, Евгений).
62) мать (Татьяна, Полина).
63) мать (Мария, Сергей).
64) мать (Анна, Олег).
65) мать (Татьяна, Анатолий).
66) мать (Анна, Дмитрий).
67) мать (Виктория, Белла).
68) мать (Мария, Татьяна).
69) мать (Ольга, Жанна).
70) мать (Ольга, Павел).
71) мать (Жанна, Ирина).
72) мать (Ирина, Игорь).
73) мать (Ирина, Кирилл).
74) мать (Барбара, Роман).
75) род (x, y) ⇐ отец (x, y).
76) род (x, y) ⇐ мать (x, y).
77) сын (x, y) ⇐ род (y, x), муж (x).
78) дочь (x, y) ⇐ род (y, x), жен (x).
79) брат (x, y) ⇐  род(z, x), род (z, y), муж (x), x ≠ y.
80) сестра (x, y) ⇐ род(z, x), род (z, y), жен (x), x ≠ y.

Цели (всегда раздельные, например, для варианта 1: найти тестя Феликса; затем найти племянника Павла):

1. тесть (Феликс, y), племянник (Павел, y).
2. тетя (Анна, y), внук (x, Алиса).
3. двоюр. брат (Вадим, y), внучка (x, Сергей).
4. дядя (Ефим, y), свекровь (Мария, y).
5. невестка (x, Максим), внук (x, Анна).
6. племянница (Жанна, y), внук (Роман, y).
7. теща (Елена, y), внучка (Белла, y).
8. теща (Мария, y), свекор (x, Елена).
9. внук (Евгений, y), дядя (Юрий, y).
10. тетя (Татьяна, y), двоюр. брат (Дмитрий, y).
11. зять (Петр, y), тетя (Ольга, y).
12. свекор (Петр, y), внучка (Полина, y).
13. свекровь (x, Луиза), дядя (Сергей, y).
14. тесть (x, Сергей), двоюр. брат (Вадим, y).
15. теща (x, Сергей), двоюр. сестра (x, Виктория).
16. троюр. сестра (x, Белла), зять (Сергей, y).
17. племянник (Вадим, y), внучка (Ирина, y).
18. невестка (Анна, y), двоюр. сестра (Виктория, y).
19. невестка (Елена, y), племянница (Виктория, y).
20. двоюр. сестра (Жанна, y), племянник (x, Ефим).
21. троюр. сестра (Наталья, y), свекор (Иван, y).
22. тесть (Петр, y), троюр. брат (Роман, y).
23. племянница (x, Сергей), зять (Ефим, y).
24. внучка (x, Мария), двоюр. сестра (Белла, y).
25. двоюр. сестра (x, Полина), зять (x, Петр).