Теорема 3.5 (Черча). Проблема разрешимости исчисления предикатов в общем виде неразрешима.

Очевидно, что проблема разрешимости для конечных областей разрешима.

Контрольные вопросы и задания

3.1.	Определить	область	истинности	предиката
x(P(x) & Q(x) → R(x)) ,		если предикаты P(x), Q(x)		и R(x) заданы

на множестве натуральных чисел N:

•P(x): «число Х делится на 5»;

•Q(x): «число Х делится на 3»;

•R(x): «число Х четное».

3.2. Определить область истинности предикатаx(P(x) Q(x)) → R(x)) , если предикаты P(x), Q(x) и R(x) заданы на множестве натуральных чисел N:

•P(x): «число Х делится на 5»;

•Q(x): «число Х делится на 2»;

•R(x): «число Х нечетное».

3.3.			Определить	область	истинности			предиката
x(	P(x)	& Q(x) → R(x)) ,		если предикаты P(x), Q(x) и R(x) заданы
на множестве натуральных чисел N:
		Y	a	• P(x): «число Х делится на 7»;
				• Q(x): «число Х делится на 3»;
				• R(x): «число Х нечетное».
				3.4.	Найти область			истинности
-d			d	Х предиката		x2 + 2x +1	.
						x2 +3x + 2
			-a	3.5. Даны следующие условия для
				Х и Y (рис. 3.2). Записать их в виде
			Рис. 3.2	формулы исчисления предикатов.
				3.6.	Изобразить на			декартовой

плоскости область истинности предиката x2 + y2 ≤ 5 .

3.7. Изобразить на декартовой плоскости область истинности предиката (x − 2)2 + ( y + 2)2 = 0 .

110

3.8.

Определить

область

выполнения

формулы

R (B A) (B xA).

3.9.

Определить

область

выполнения

формулы

R (A B) ( xA B) .

3.10.

Определить

область

выполнения

формулы

.

R x(B(x) A(x)) xA(x)

3.11.

Определить

область

выполнения

формулы

R x(B(x) (A(x) A(x))).

3.12.

Исследовать

на

общезначимость

формулу

R:((A (B

)) ((A B) (A

))).

C

C

3.13.

Исследовать

на

общезначимость

формулу

R:((A (

C)) ((A

) (A C))).

B

B

3.14.

Исследовать

на

общезначимость

формулу

R:(((A (

C)) ((A

) (A C)))

) .

B

B

A A

3.15.

Исследовать

на

общезначимость

формулы

xR(x) P(x)) ( xR(x) xP(x)) .

3.16. Какие три аксиомы относятся к исчислению высказываний:

1)A1 : (A (B A));

2)A2 :((A (B C)) ((A B) (A C))) ;

3)A3 :((B A) ((B A) B)) ;

4)A4 : A B (A B) A B ;

5)А5 : A(x) tA(t);

6)А6 : xA(x) A(t);

7)A7 :(A B) (A B)&(B A) ;

8)А8 : xA(x) A(t) ;

9)А9 : A(t) xA(x)?

3.17. Какие пять аксиом относятся к исчислению предикатов первого порядка:

1)A1 :(A (B A));

2)A2 :((A (B C)) ((A B) (A C))) ;

3)A3 :((B A) ((B A) B)) ;

4)A4 : A B (A B) A B ;

111

5)А5 : A(x) tA(t);

6)А6 : xA(x) A(t);

7)A7 :(A B) (A B)& (B A) ;

8)А8 : xA(x) A(t) ;

9)А9 : A(t) xA(x)?

3.18. Даны формулы исчисления высказываний. Какие из формул являются тавтологиями?

1)R1 :(A (B A)) ;

2)R2 :((A (A A)) A A);

3)R3 :(A A);

4)R4 :(A (B A)) ;

5)R5 :(A (A A)) ;

6)R6 :((A (B C)) ((A B) (A C))) ;

7)R7 :((A A) (A A));

8)R8 :((A (B C)) ((A B) (A C))).

3.19. Даны следующие формулы исчисления высказываний. Какие из формул не являются ни тавтологиями, ни противоречиями?

1)R1 :(A (B A)) ;

2)R2 :((A (A A)) A A);

3)R3 :(A A);

4)R4 :(A (B A)) ;

5)R5 :(A (A A)) ;

6)R6 :((A (B C)) ((A B) (A C))) ;

7)R7 :((A A) (A A));

8)R8 :((A (B C)) ((A B) (A C))).

3.20. Даны формулы исчисления высказываний. Какие из формул являются противоречиями?

1)R1 :(A (B A)) ;

2)R2 :((A (A A)) A A);

112

3)R3 : (A → A) ;

4)R4 : (A → (B → A)) ;

5)R5 : (A → (A → A)) ;

6)R6 : ((A → (B →C)) → ((A → B) → (A →C))) ;

7)R7 : ((A → A) → (A → A)) ;

8)R8 : ((A → (B →C)) → ((A → B) → (A →C))) .

3.21.Даны формулы исчисления предикатов первого порядка.

Какие из формул являются равносильными?

1)R1 : x(C & Q(x)) = C & xQ(x) ;

2)R2 : x(C Q(x)) = C xQ(x) ;

3)R3 : x(C → Q(x)) = C → xQ(x) ;

4)R4 : x(C → Q(x)) = C → xQ(x) ;

5)R5 : xP(x) = xP(x) ;

6)R6 : x(C & Q(x)) = C & xQ(x) ;

7)R7 : x(C & Q(x)) = C & xQ(x) ;

8)R8 : xP(x) = xP(x) .

3.22. Даны следующие формулы исчисления предикатов первого порядка.

R = (B → A(x)) → (B → xA(x)) , R = (A(x) → B) → ( xA(x) → B) , R = ( A → xA(x)) .

Для каждой из них отметить свойства из приведенного списка, чтобы выражение «эта формула является….» стало истинным:

•общезначимой;

•невыполнимой;

•тождественно истинной во всякой области;

•противоречием;

•равносильностью;

•выполнимой на любом множестве;

•выполнимой на множестве X = {1, 0};

•выполнимой на множестве X = {1, 2, 3, 5, 6};

•тождественно ложной.

113