Математическая логика - типовой расчёт

ЗАДАНИЕ 5. Найти результат работы машины Тьюринга.

21

22

ЗАДАНИЕ 6.

Доказать, что

1xP (x)≡ xP (x)

2x (P (x) Q (y))≡ xP (x) Q (y)

3xP (x)≡ xP (x)

4x (P (x) Q (y))≡ xP (x) Q (y)

5x yP (x, y)≡ y xP (x, y)

6x (P (x) Q (x))≡ xP (x) xQ (x)

7x yP (x, y)≡ y xP (x, y)

8x (P (x) Q (x))≡ xP (x) xQ (x)

9x yP (x, y)→ y xP (x, y)≡1

Является ли формула тождественно истинной?

10x (Q (x)→ P (x)) ( xQ (x)→ xP (x))

11x (Q (x)→ P (x)) ( xQ (x)→ xP (x))

12(x)(Q (x)→ P (x))→( xQ (x)→ xP (x))

13x (Q (x)→ P (x))→( Q (x)→ xP (x))

14x (Q (x)→ P (x))→( xQ (x)→ xP (x))

Для вариантов 15–25 предикаты заданы на множестве натуральных чисел. D (x, y)≡ «y делится на x»;

P (x)≡ «x – простое число»;

G (x, y, z)≡ «z – наибольший общий делитель x и y».

23

Переведите на обычный язык формулы:

15x (P (x) D (z, x))

16x y (P (x) D (x, y))

17x y z (D (x, y) D (z, y) D (z, x))

18x y z (G (x, y, z) D (z, x) D (z, y))

19x y z (G (x, y, z) P (z) D (z, y) D (z, x))

20x y z (G (x, y, z) D (z, y) D (z, x))

21x y z (G (x, y, z) D (z, x) D (z, y))

22x y z (G (x, y, z) D (z, x) D (z, y))

23x y z (G (x, y, z) D (z, x) D (z, y))

24x y z (G (x, y, z) D (z, x) D (z, y))

25x y z (G (x, y, z) D (z, x) P (z))

24