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

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

	q1	q2	q3
	1Cq3	Cq0	Πq3
1	2Cq3	1Cq0	1Πq3
2	3Cq3	2Cq0	2Πq3
3	4Cq3	3Cq0	3Πq3
4	5Cq3	4Cq0	4Πq3
5	6Cq3	5Cq0	5Πq3
6	7Cq3	6Cq0	6Πq3
7	7Cq3	7Cq0	7Πq3
8	8Cq3	8Cq0	8Πq3
9	Лq1	9Cq0	9Πq3
a0	1Cq3	a0Cq0	a0 Лq0
*	*Лq1	a0 Лq0	*Πq3

21

1

2

3

4

5

6

7

8

9

над словом

5673 12		10		6213 14		18		7548 14
↑				↑				↑
q1				q1				q1
6543 21		11		7145 23		19		5236 21
↑				↑				↑
q1				q1				q1
8564 31		12		3456 12		20		7143 83
↑				↑				↑
q1				q1				q1
4683 12		13		7352 14		21		6528 31
↑				↑				↑
q1				q1				q1
3782 14		14		3751 32		22		4835 12
↑				↑				↑
q1				q1				q1
7324 13		15		6427 21		23		7143 52
↑				↑				↑
q1				q1				q1
4276 21		16		4138 13		24		5876 31
↑				↑				↑
q1				q1				q1
5428 12		17		5423 61		25		3489 11
↑				↑				↑
q1				q1				q1
8681 23
↑
q1

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