Задание №5

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

xP(x,y)x((yP(x,y)yQ(x,y))yR(x,y))

Решение:

1. Удаляем импликацию:

xP(x,y)x((yP(x,y)yQ(x,y))yR(x,y))

2. Вносим отрицание к атомарным формулам:

xP(x,y)x((yP(x,y)yQ(x,y))yR(x,y))

3. Вынесем поочередно кванторы во внешнюю часть:

xzP(x,y)((yP(z,y)yQ(z,y))yR(z,y))

xzuP(x,y)((P(z,u)yQ(z,y))yR(z,y))

xzuvP(x,y)((P(z,u)Q(z,v))yR(z,y))

xzuvwP(x,y)(P(z,u)Q(z,v))R(z,w)

4. Бескванторное ядро приводим к ДНФ и КНФ и получаем соответственно ПНФ и КлНФ:

xzuvwP(x,y)(P(z,u)Q(z,v))R(z,w) - КлНФ

xzuvwP(x,y)((P(z,u)R(z,w))(Q(z,v)R(z,w)))

xzuvw(P(x,y)P(z,u)R(z,w))(P(x,y)Q(z,v)R(z,w))) – ПНФ

Задание №6

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

₁ = xyzu(P₁(x,y)(P₁(x,y)P₂(x,z,u)))

₂ = xyz(P(x,y,z)uv(P₂(x,y,z)P₁(x,u)P₁(v,x)))

₃ = xyz(P₂(z,x,y)P₁(z,x))

Решение:

₁ = xyzu(P₁(x,y)(P₁(x,y)P₂(x,z,u)))

₂ = xyzuv(P(x,y,z)(P₂(x,y,z)P₁(x,u)P₁(v,x)))

₂ = xyzuv(P(x,y,z)(P₂(x,y,z)(P₁(x,u)P₁(v,x))))

₂ = xyzuv(P(x,y,z)(P₂(x,y,z)P₁(x,u))(P₂(x,y,z)P₁(v,x)))

₃ = xyz(P₂(z,x,y)P₁(z,x))

{₁,₂,₃} = {P₁(x,y), P₁(x,y)P₂(x,z,u)), P(x,y,z), P₂(x,y,z)P₁(x,u)), P₂(x,y,z)P₁(v,x)), P₂(z,x,y), P₁(z,x)}

Пусть в ₁ y = с₁, z = с₂, в ₂ x = с₃, u = с₄, v = с₅, в ₃ z = с₆ тогда:

{₁,₂,₃} = {P₁(x,с₁), P₁(x,с₁)P₂(x,с₂,u), P(с₃,y,z), P₂(с₃,y,z)P₁(с₃,с₅), P₂(с₃,y,z)P₁(с₅,с₃), P₂(с₆,x,y), P₁(с₆,x)}

1. P₁(x,с₁)

2. P₁(x,с₁)P₂(x,с₂,u)

3. P(с₃,y,z)

4. P₂(с₃,y,z)P₁(с₃,с₅)

5. P₂(с₃,y,z)P₁(с₅,с₃)

6. P₂(с₆,x,y)

7. P₁(с₆,x)

8. res(1,2) = P₂(x,с₂,u)

9. res(1,7) = 0

10. res(4,6) = res(4,8) = P₁(с₃,с₅)

11. res(5,6) = res(5,8) = P₁(с₅,с₃)

12. res(7,10) = res(7,11) = 0

Данное множество противоречиво! Модели не существует!

Задание №7

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

x-y, при x>y

F(x,y) =

0, при xy

Задание №8

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

x-y, при x>y

F(x,y) =

0, при xy



1 7 Задача №1.

Из данной совокупности секвенций выбрать доказуемые, построить их

доказательства, для недоказуемых показать их недоказуемость с помощью:

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

б) алгоритма редукции;

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

Среди этих доказательств недоказуемости выбрать оптимальное в каждом

конкретном случае.

1) ¬x, ¬y├ (( y → x ) → z ) v ( ¬z → y ) → x ).

2) x v ¬y v u , y v ¬u , x v z ├ x v y.

3) x , y , z ├ ( x → y ) v ( y → z ).

4) x v y ├ ( x → z ) v ( y → z ).

РЕШЕНИЕ.

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

1. ¬x, ¬y├ (( y → x ) → z ) v ( ¬z → y ) → x.)

¬x Λ ¬y → (( y → x ) → z ) v ( ¬z → y ) → x.)

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

Данная формула доказуема.

Построим её доказательство по правилам вывода.

2. x v ¬y v u, y v ¬u, x v z ├ x v y

((x v ¬y v u ) Λ (y v ¬u) Λ (x v z)) → x v y

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

Эта формула недоказуема.

Покажем её недоказуемость с помощью а) алгоритма Квайна;

б) алгоритма редукции;

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

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

(( x v ¬y v u ) Λ ( y v ¬u ) Λ ( x v z )) → x v y

первая ветвь вторая ветвь

х = 0 x = 1

(( 0 v ¬y v u ) Λ ( y v ¬u ) Λ ( 0 v z )) → 0 v y

(( ¬y v u ) Λ ( y v ¬u ) Λ z ) → y

у = 0 у =1

(( 1 v u ) Λ ( 0 v ¬u) Λ z → 0

1 Λ ¬u Λ z → 0

¬u Λ z → 0

z=0 z=1

0→0=1 ¬u →0

u=0 u=1

1→0=0 0 →0=1

Получили набор переменных, при котором функция обращается в ноль.

Следовательно, она недоказуема.

б) Алгоритм редукции.

(( x v ¬y v u ) Λ ( y v ¬u ) Λ ( x v z )) → x v y = Ф

Предположим, что Ф = 0, т.е. предположим , что формула недоказуема, тогда:

(( x v ¬y v u ) Λ ( y v ¬u ) Λ ( x v z )) → x v y = 0

Значит ( x v ¬y v u ) Λ ( y v ¬u ) Λ ( x v z ) = 1 , x v y=0

х = 0

у = 0

Следовательно,

y v ¬u = 1 x v z = 1

¬u = 1 0 v z = 1

¬u = 1, u = 0 z = 1

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

в) Метод резолюций.

x v ¬y v u, y v ¬u, x v z ├ x v y

S = { x v ¬y v u; y v ¬u; x v z ; ¬(x v y) }

Построим резолютивный вывод нуля из S:

D₁ = x v ¬y v u res( D₁, D₂ ) = x D₆ = x

D₂ = y v ¬u res( D₄, D₆ ) = 0

D₃ = x v z

D₄ = ¬x

D₅ = ¬y

Формула недоказуема.

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

3. x , y , z ├ ( x → y) v ( y → z )

(x Λ y Λ z) → ( x → y) v ( y → z )

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

Эта формула доказуема.

Покажем её доказуемость по правилам вывода.

x ├ x; y ├ y; z ├ z

12

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

7

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

1

x,y,z ├ (x → y) v (y → z)

4. x v y ├ ( x → z ) v ( y → z )

x v y → ( x → z ) v ( y → z )

x y z	1	2	3	4	5
0 0 0	0	1	1	1	1
0 0 1	0	1	1	1	1
0 1 0	1	1	0	1	1
0 1 1	1	1	1	1	1
1 0 0	1	0	1	1	1
1 0 1	1	1	1	1	1
1 1 0	1	0	0	0	0
1 1 1	1	1	1	1	1

Эта формула недоказуема.

Покажем её недоказуемость с помощью а) алгоритма Квайна;

б) алгоритма редукции;

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

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

x v y → ( x → z ) v ( y → z )

х = 0 х = 1

y → 1 v ( y → z ) 1 → ( 1 → z) v ( y → z)

y → 1 = 1 1 → z v ( y → z)

y = 0 y = 1

1 → z v 1 1 → z v z

1 → 1 = 1

z = 0 z = 1

1 → 0 = 0 1 → 1 = 1

Получили набор переменных, при котором функция обращается в ноль.

Следовательно, она недоказуема.

б) Алгоритм редукции

x v y → ( x → z ) v ( y → z ) = Ф

Предположим, что Ф = 0, т.е. предположим , что формула недоказуема, тогда:

( x → z ) v ( y → z ) = 0 , x v y = 1

x → z = 0 y → z = 0 x v y = 1

х = 1 y = 1 x = 1

z = 0 z = 0 y = 1

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

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

в) Метод резолюций

x v y ├ ( x → z ) v ( y → z )

S = { (x v y); ¬ ( x → z ); ¬ ( y → z )}