Задача №1.

Условие: Из данной совокупновти секвенций выбрать доказуемые, построить их доказательства, для недоказуемых показать их недоказуемость с помощью

А) алгоритма Квайна

Б) метода редукции

В) метода резолюций.

Выбрать оптимальное в каждом случае.

1. yx |— yx

2. (xy)(yx) |— xy

3. x|— (xy)(xyz)(xyz)

4. x,y,z|—xyz

Решение:

a) yx |— yx

(yx) (yx)

x	y	x	yx	yx	(yx) (yx)
0	0	1	1	1	1
0	1	1	1	1	1
1	0	0	1	1	1
1	1	0	0	0	1

Секвенция доказуема.

Доказательство:

y |— y , yx |—yx

y|—x , y|—x y|—y

yx, y|—yx y|—yy |—yy

yx |— yx

b) (xy)(yx) |— xy

((xy)(yx))(xy)

x	y	xy	yx	(xy)(yx)	xy	((xy)(yx))(xy)
0	0	1	0	0	0	1
0	1	1	1	1	1	1
1	0	1	1	1	1	1
1	1	0	1	0	1	1

Секвенция доказуема.

Доказательство:

y|—y yx|—yx

yx , yx yy

(xy)(yx) |— yx yx , y|— yx y|— yy |— yy

(xy)(yx) |— xy

c) x|— (xy)(xyz)(xyz)

x((xy)(xyz)(xyz))

x	Y	z	xy	xyz	xyz	(1)(2)	(3)(4)	x(5)
0	0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	0	1
0	1	0	0	0	0	0	0	1
0	1	1	0	0	0	0	0	1
1	0	0	0	0	1	0	1	1
1	0	1	0	1	0	1	1	1
1	1	0	1	0	0	1	1	1
1	1	1	1	0	0	1	1	1
			(1)	(2)	(3)	(4)	(5)

Секвенция доказуема.

Доказательство:

x|—x xy|—xy

x|—x(yy) xy|—xy(zz)

x|—(xy)(xy) , xy|— (xyz) (xyz)

x|— (xy)(xyz)(xyz)

d) x,y,z|—xyz

(xyz)(xyz)

x	y	z	xyz	Xyz	(xyz)(xyz)
0	0	0	0	0	1
0	0	1	0	1	1
0	1	0	0	1	1
0	1	1	0	1	1
1	0	0	0	1	1
1	0	1	0	1	1
1	1	0	1	1	1
1	1	1	0	1	1

Секвенция доказуема.

Доказательство:

x|—x y|—y

x|— xy y|—xy

x , y|—xy

x , y , z|— xy

x , y , z|—xyz

Задача №2.

Условие: найти формулу исчисления предикатов, истинную на алгебраической системе  и ложную на  .

=< R;  > =< Z;  >

Решение:

a b( ((a b)  ( a=b)) c(( a  c)  ( c  b )))

Задача №3.

Условие: построить доказательство в исчислении предикатов.

x y P(x,y)  y x P(x,y)

Решение:

P(x,y) |—P(x,y)

y x P(x,y) |—P(x,y)

P(x,y) |—P(x,y) P(x,y) |—(y x P(x,y))

x yP(x,y) |—P(x,y) P(x,y) |—y x P(x,y)

x yP(x,y) P(x,y) , P(x,y) |—y x P(x,y)

x y P(x,y) |— y x P(x,y)

Задача №4.

Условие: установить выполнимость формулы ИП. Если выполнима, то построить модель.

x y z ( P(x,z)P(z,y))&(x=z)(z=y)

Решение:

x y z ( P(x,z)P(z,y))

z=f(x,y)

{ P(x , f(x,y) ) , P( f(x,y), y ) }

(1) (2)

res((1),(2))= P(x , f(x,y) )P( f(x,y), y )

Формула выполнима.

Модель:

=< R; < > , где P(a,b) означает a<b.

Задача №5.

Условие: привести к пренексной и клазуальной нормальным формам.

x y P(x,y)x y Q(x,y)

Решение:

x y P(x,y)x y Q(x,y) 

x y P(x,y)x y Q(x,y) 

 x u P(x,u)v y Q(v,y) 

x u v y(P(x,u)Q(v,y))

Задача №6.

Условие: методом резолюции проверить, противоречиво ли множество предложений {1, 2, 3}. Если множество непротиворечиво, то построить модель.

1= x y(P3(f(x),x)(P2(y,x)P3(f(x),y)))

2= x (f(x)=f(f(x)))

3= x y z v u (P1(f(x),z)(P2(v,u)(P3(f(u),y)P1(y,v))))

Решение:

Если x (f(x)=f(f(x))), то х f(x)=x

1= x y (P3(f(x),x)(P2(y,x)P3(f(x),y))) 

 x y (P3(f(x),x) (P2(y,x)P3(f(x),y))) 

 x y (P3(f(x),x) ( P2(y,x) P3(f(x),y))) 

 x y (P3(f(x),x)( P2(y,x) P3(f(x),y))) 

 x y(P3(f(x),x) ( P2(y,x) P3(f(x),y))) 

 x y(P3(f(x),x)( P2(y,x) P3(f(x),y))) 

 P3(f(c1),c1)[ P2(c2,c1) P3(f(c1),c2)]

 P3(c1,c1)[ P2(c2,c1) P3(c1,c2)]

{P3(c1,c1) , P2(c2,c1) P3(c1,c2)}

3= x y z v u (P1(f(x),z)(P2(v,u)(P3(f(u),y)P1(y,v)))) 

 x y z v u ( P1(f(x),z)(P2(v,u)(P3(f(u),y)P1(y,v)))) 

 x y z v u ( P1(f(x),z) P2(v,u)P3(f(u),y)P1(y,v)) 

x y z v u(P1(f(x),z) P2(v,u) P3(f(u),y) P1(y,v)) 

 P1(f(c3),z) P2(F(y,z),u) P3(f(u),y) P1(y,F(y,z))

 P1(c3,z) P2(F(y,z),u) P3(u,y) P1(y,F(y,z))

{P1(c3,z) ,  P2(F(y,z),u) ,  P3(u,y) ,  P1(y,F(y,z))}

{P3(c1,c1) , P2(c2,c1) P3(c1,c2) , P1(c3,z) ,  P2(F(y,z),u) ,  P3(u,y),

(1) (2) (3) (4) (5)

 P1(y,F(y,z))}

(6)

res((2),(5))= P2(c2,c1) (6) { c1/u ; c2/y }

Множество предложений непротиворечиво.

Построим модель этого множества.

{P3(c1,c1) , P2(c2,c1) , P1(c3,z) ,  P2(F(y,z),u) ,  P1(y,F(y,z))}

<N; >

Р1 (х, у)== х > у

Р2 (х, у) == х-у всегда попадает в пределы множества N

Р3 (х, у) == х<у

F(x, y) == х+у

C1=3

C2=4

C3=0

Задача №10.

Условие: доказать примитивную рекурсивность функции, выражая её через простейшие с помощью операторов суперпозиции и примитивной реурсии.

f(x)=3x

Решение:

y=3x;

f 1(x,y)=x+y;

f1(x,0)=x; примитивная

f1(x,y+1)=f1(x,y)+1; рекурсия

f(x)=3x;

f(x)=f1(x,f1(x,x)) - cуперпозиция

f(x)- примитивно-рекурсивная функция

Задача №11.

Условие: построить машину Тьюринга для задачи №10.

Р ешение:

0

0

1

…

1

0

1

…

1

0

1

…

1

0

0

х+1 х+1 х+1

q0 1  q1 R

q1 1  q1 R

q1 0  1 q2 // вставили единицу

q2 1  R q2

q2 0  1 q3 // вставили единицу

q3 1  R q3

q3 0  q4

q4 0  L q4

q4 1  0 q5 // убрали единицу

q5 0  L q5

q5 1  0 q6 // убрали единицу

q6 0 L q6

q6 1  0 q7 // убрали единицу

q7 0  L q7

q7 1  0 q8 // убрали единицу

q8 0  L q8

q8 1  q9

q9 1 L q9

q9 0 q0

Задача 1.

Из данной совокупности секвенций выбрать доказуемые, построить их доказательства, для недоказуемых показать их недоказуемость с помощью: а) алгоритма Квайна, б) алгоритма редукций, в) метода резолюций. Среди этих доказательств недоказуемости выбрать оптимальное в каждом конкретном случае.

а) x y, x y, y z ├ u z

б) ├ (x y) (x y)

в) x y, x z, u (x z) ├ (u y) z

г) y├ (y x) x

Решение.

а) Проверим доказуемость с помощью таблицы истинности.

x	y	z	u	x y	x y	y z	1 2	4 3	u z	5 6
0	0	0	0	0	1	1	0	0	0	1
0	0	0	1	0	1	1	0	0	1	1
0	0	1	0	0	1	1	0	0	1	1
0	0	1	1	0	1	1	0	0	1	1
0	1	0	0	1	1	0	1	0	0	1
0	1	0	1	1	1	0	1	0	1	1
0	1	1	0	1	1	1	1	1	1	1
0	1	1	1	1	1	1	1	1	1	1
1	0	0	0	1	0	1	0	0	0	1
1	0	0	1	1	0	1	0	0	1	1
1	0	1	0	1	0	1	0	0	1	1
1	0	1	1	1	0	1	0	0	1	1
1	1	0	0	1	1	0	1	0	0	1
1	1	0	1	1	1	0	1	0	1	1
1	1	1	0	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1	1	1
				1	2	3	4	5	6	7

Данная формула доказуема. Построим доказательство по правилам вывода.

y├ y z├ z

12 12 4

x├ x y, x├ y z, y├ z; z├ (u z)

4 7 7

x├ (x y) y├ (x y) z├ (y z); z├ (u z)

1 2

x, y, z├ (x y); x, y, z├ (x y); x, y, z├ (y z); x, y, z├(u z)

1

x, y, z├ (x y) (x y) (y z); ├ x, y, z (u z)

8

(x y) (x y) (y z)├ (u z)

б) ├ (x y) (x y) =(x y) (x y) // (по аксиоме)

x 0 0 1 1

y 0 1 0 1

x y 0 0 0 1

x y 0 1 1 1

(x y) (x y) 1 1 1 1

Доказательство

x├ x; y├ y x├ x

x, y├ x; x, y├ y x, y├ x

x, y├ (x y) x, y├ (x y)

(x y) (x y)

в) x y, x z, u (x z) ├ (u y) z

X 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

y 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

z 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

u 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

x y 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1

x 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 2

x z 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 3

x z 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 4

u 4 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 5

1 3 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 6

6 5 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 7

u y 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 8

8 z 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 9

7 9 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 10

Покажем недоказуемость с помощью

1) Алгоритма Квайна:

((x y) ( x z) (u (x z))) ((u y) z)

x=0

(y u) ((u y) z)

y=0 y=1

0 (u z)=1. u (u z)

z=0 z=1

u u u 1=1

u=0 u=1

0 1=1 1 0=0

2)Алгоритма редукций:

предположим, что

((x y) ( x z) (u (x z))) ((u y) z)=0, т.е. предположим, что формула недоказуема, тогда

((x y) ( x z) (u (x z)))=1 ((u y) z)=0

значит: u y=1, z=0

отсюда: u=1,y=1, z=0;

x y=1, x z=1, u=1, x z=1

x 0=1, значит x=0

0 1=1, 0 0=1.

Противоречий нет. Формула недоказуема.

Наиболее оптимальным является алгоритм редукций.

г) y├ (y x) x

x 0 0 1 1

y 0 1 0 1

y x 1 0 1 1

1 x 0 1 1 1

y 2 1 1 1 1

Для доказательства воспользуемся эквивалентностями ИВ:

(φ ψ) ( φ ψ) ; (φ ψ) ( φ ψ) ;

(φ (ψ χ)) (φ ψ) (φ χ).

Преобразуем

(y x) x (y x) x ( y x) x (y x) x (y x) ( x x) y x

Получаем: y├ y x

Строим доказательство

y├ y

4

y├ y x

Задача 2.

Найти формулу исчисления предикатов истинную на алгебраической системе α и ложную на системе δ.

α =<R;∙> δ =<N;∙>

Решение

Истинной на системе α и ложной на системе δ будет формула

Задача 3.

Построить доказательство формулы в исчислении предикатов

Доказательство

- аксиома 1

- аксиома 14

Задача 4.

Установить, выполнима ли следующая формула и если выполнима, то построить модель этой формулы.

Задача 5.

Привести к пренексной и клазуальной нормальным формам следующую формулу:

Решение:

Задача 6.

Методом резолюций проверить, противоречиво ли множество предложений {Φ₁, Φ₂, Φ₃}. Если множество не противоречиво, то построить модель этого множества.

Решение:

Т.к. множество формулы {Ф₁, Ф₂} непротиворечиво

Задача 7.

Доказать примитивную рекурсивность функции, выражая ее через простейшие с помощью операторов суперпозиции и примитивной рекурсии.

f(x, y)=x∙y+1

Доказательство

Считаем sum(x,y) – примитивная рекурсия.

mult(x,y)=x∙y

mult(x,0)=0

mult(x,y+1)=x∙(y+1)=x∙y+x=mult(x,y)+x=sum(mult(x,y),x)

Задача 8.

Построить машину Тьюринга для вычисления функции

f(x, y)=x∙y+1

Решение

q	q0	q1	q2	q3	q4	q5	q6	q7	q8
1	0Rq1	1Rq2	1Rq2	0Rq4	1Rq4	1Rq5	1Lq6	1Lq8	1Lq9
0		0Rq13	0Rq3		0Rq5	1Lq6	0Lq7	0Lq15	1Lq10

q9	q10	q11	q12	q13	q14	q15	q16	q17
1Lq9	1Rq11	0Lq12	1Lq12	0Rq13		0Lq16	0Lq16	1
0Rq3	1Lq10		1Rq0	1Lq14	1	0Lq15	0Rq17	0Rq