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

A = <N, - >, B= <Z, - >

Решение:

A = <N, - > |= φ

B = <Z, - > |= φ

φ = "x$y Ø(x – y = 0) Ù Ø(x = y)

Задача №3: $xP(x)«^Ø"x^ØP(x)

Решение:

аксиома

P(x)├P(x) аксиома

11,12 $xP(x)├P(x) ØP(x)├ØP(x)

$xP(x), ØP(x)├P(x); $xP(x), ØP(x)├ØP(x) аксиома

$xP(x), ØP(x)├ $xØP(x), Ø$xP(x)├

$xP(x), "xØP(x)├ Ø"xØP(x), Ø$xP(x)├

$xP(x)├Ø"xØP(x) Ø"xØP(x)├$xP(x)

├($xP(x)®Ø"xØP(x)); ├(Ø"xØP(x)®$xP(x))

├(($xP(x))®Ø"xØP(x)Ù(Ø"xØP(x)®$xP(x))

├($xP(x))«Ø"xØP(x)

Задача №4: ╞"x$y$z$u$v(R(x,y,z)ÙR(x,u,v))ÙØ$xR(x,x,x)

Решение:

Формула j истинна, только если обе её части истинны:

"x$y$z$u$v(R(x,y,z)ÙR(x,u,v)) (1) истинна и Ø$xR(x,x,x) (2) истинна

(1) истинна, когда обе её части: "x$y$z(R(x,y,z)) (1.1) истинна и

"x$u$v(R(x,u,v)) (1.2) истинна

Пусть y=z=x и u=v=x, тогда "x(R(x,x,x)) истинна по первой части формулы j.

По второй части: Ø$xR(x,x,x), что значит (1) и (2) не могут быть истинны одновременно. Следовательно, формула j ложна. Модель построить нельзя.

Задача №5: Ø($x"yP(x,y)®"x($yQ(x,y)®$yR(x,y)))

Решение:

(а) = Ø("x"yØP(x,y)Ú"x("yØQ(x,y)Ú$yR(x,y)))≡ (a) ≡

≡ $x"yP(x,y)Ù$x($yQ(x,y)Ù"yØR(x,y))) ≡ (д,ж,з) ≡

≡ $x"y$u$v"w(P(x,y)ÙQ(u,v)ÙØR(u,w)) – КлНФ, ПНФ

Задача №6:

Ф₁= $x"y"z$u(P(x,y)ÙØ(f₁(x,z)=f₂(x,u)))

Ф₂= "x"y"z(P(x,y)®(f1(x,y)=f2(x,z)))

Ф₃= "x"y(P(f1(x,y),y)®ØP(f2(x,y),y))

Решение:

В первом предположении произведём замену u=F₃(y,z) и x=C₁.

Ф₂="x"y"z(ØP(x,y)Ú(f₁(x,y)=f₂(x,z)))

Ф₃="x"y(ØP(f₁(x,y),y)ÚØP(f₂(x,y),y))

w={P(C₁,y) (1), Ø(f₁(C₁,z)=f₂(C₁,F₃(y,z))) (2), ØP(x,y)Ú(f₁(x,y)=f₂(x,z) (3), ØP(f₁(x,y),y)ÚØP(f₂(x,y),y)) (4) }

res(1,3)_p=_{C1/x}f1(x,y)=f2(x,z) (5)

res(1,4)_p=_{C1/f1(x,y)}ØP(f2(x,y),y) (6)

res(1,6)_p=_{C1/f2(x,y)}0

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

Задача №7: f(x)=3x+1

Решение:

Ведём функцию h(x₁,x₂)

I₁¹(x)=3*0+1=1

h(x₁,x₂+1)=f(x₁, x₂, h(x₁,x₂))=S(h(x₁,x₂))=h(x₁,-x₂)+1=x₁+(x₂+1)

Т.о. доказали примитивную рекурсивность функции f(x₁,x₂)=x₁+x₂. На следующем шаге перейдём от этой функции к требуемой:

f(x₁,x₂)=x₁+x₂

h(x₁)=x₁

f(x₁,f(x₁,x₁))=3x

S(3x)=3x+1 – функция примитивно рекурсивная.

Задача №8: f(x)=3x+1

Решение:

x+1 x+1 x+1 1

0q₁®Rq₂

1q₂®Rq₂

0q₂®1q₃ - вставим 1

1q₃®Rq₃

0q₃®1q₄ - - вставим 1

1q₄®Rq₄

0q₄®Rq₅

1q₅®0q₆ – удалим 1

0q₆®Rq₇

1q₇®0q₈ - удалим 1

0q₈®Lq₈

1q₉®0q₁₀ - удалим 1

0q₁₀®Lq₁₁

1q₁₁®0q₁₂ - удалим 1

0q₁₂®Lq₁₃

1q₁₃®0q₁₄ - удалим 1

0q₁₄®Lq₁₅

1q₁₅®Lq₁₅

0q₁₅®0q₀