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

a = <C, · >

b = <R, · >

Решение:

тк на множестве С-комплексных чисел, существует i –мнимая единица, запишим:

x z ((z z) x= - x),тогда формула ИП примет вид:

x z ((z z) x= - x) a

x z ((z z) x= - x) b

 

 

Вариант решение 2:

x z [(u (u,v)=u) ((x,x)=v (x=v))] z ((z,z))=x

v=1

x=-1

 

 

Задание №3

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

(P(x)Ù"yQ(y)) «"y(P(x)ÙQ(y))

Решение:

Используя привила вывода в ИП получим:

 

Задание №4

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

"xØP(x,x)Ù"x"y(P(x,y) ® ØP(y,x))Ù"x"y$z(P(z,x)ÙP(z,y))

Решение:

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

"xØP(x,x)Ù"x"y(ØP(x,y) Ú ØP(y,x))Ù"x"y$z(P(z,x)ÙP(z,y))

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

"xØP(x,x)Ù"x"y(ØP(x,y) Ú ØP(y,x))Ù"x"y$z(P(z,x)ÙP(z,y))

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

"x"v"y ØP(x,x)Ù (ØP(v,y) Ú ØP(y,v))Ù"x"y$z(P(z,x)ÙP(z,y))

"x"v"y"u"w$z ØP(x,x)Ù (ØP(v,y) Ú ØP(y,v))Ù P(z,u)ÙP(z,w)

4) Получим КлНФ, методом резолюций проверим выполнимость данной формулы:

(1) ØP(x,x)

(2) (ØP(v,y) Ú ØP(y,v))

(3) P(z,u)

(4) P(z,w)

(5) res(1,3) = res(1,4)=0 =>

данная формула противаречива

модель построить нельзя.

Задание №5

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

Ø"x($yP(x,y)Ù$yQ(x,y))Ù"xØ$yQ(x,y)

Решение:

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

Ø"x($yP(x,y)Ù$yQ(x,y))Ù"xØ$yQ(x,y)

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

$x(Ø($yP(x,y)Ù$yQ(x,y)))Ù"x"yØQ(x,y)

$x("yØP(x,y)Ù"yØQ(x,y))Ù"x"yØQ(x,y)

 

 

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

$x"y(ØP(x,y)Ù"yØQ(x,y))Ù"x"yØQ(x,y)

$x"y"u(ØP(x,y)ÙØQ(x,u))Ù"x"yØQ(x,y)

$x"y"u"v"w(ØP(x,y)ÙØQ(x,u))ÙØQ(v,w)

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

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

Задание №6

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

f₁ = $x$y$z((P₁(x,y) ® ØP₂(y,z))Ù(ØP₂(y,z)®P₁(x,y)))

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

f₃ = Ø$x$y(ØP₁(x,y) ÙP₂(x,y))

Решение:

Устраним непротиворечивость методом резолюций, если не противоречиво, то построим модель.

f₁ º $x$y$z((ØP₁(x,y)ÚØP₂(y,z)) Ù(P₂(y,z)ÚP₁(x,y)))

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

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

{f₁,f₂,f₃} = (ØP₁(x,y)ÚØP₂(y,z)), (P₂(y,z)ÚP₁(x,y), P₁(x,y), ØP₂(y,x), P₁(x,y), ØP₂(x,y))

Пусть в j₁ x=c₁ , y=c₂,z=c₃; в j₂ y=c₄; тогда:

{f₁,f₂,f₃} = (ØP₁(c₁, c₂)ÚØP₂(c₂, c₃)), (P₂(c₂, c₃)ÚP₁(c₁, c₂), P₁(x, c₄), ØP₂(c₄,x), P₁(x,y), ØP₂(x,y))

(1) (ØP₁(c₁, c₂)ÚØP₂(c₂, c₃))

(2) (P₂(c₂, c₃)ÚP₁(c₁, c₂)

(3) P₁(x, c₄)

(4) ØP₂(c₄,x)

(5) P₁(x,y)

(6) ØP₂(x,y)

(7) res_P1,p2(1,2)= 0 => данное множество противоречиво, модели не существует

 

 

Задание №7

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

f(x)=4x

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

Введём функцию:h(x1,x2)

I ₁ ¹(x)= 2 0+1=1

 

 

h(x1,x2+1)= f(x1,x2,h(x1,x2))=f(x1,x2,h(x1,x2))=s(,h(x1,x2))= h(x1,x2)+1=

= x1+(x2+1)

 

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

Задание №8

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

f(x)=4x

Решение:

 

…

….

q₁

q₁01^x0 º> q₀01^4x0

Например: x=2, тогда 4x=4*2=8, тогда Машина выглядит так в начальном состоянии:

….

….

q₁

1q₁ -> 0q₁

0q₁ -> Rq₂

1q₂ -> Rq₂

0q₂ -> Rq₃

0q₃ -> 1q₄

1q₃ -> Rq₃

1q₄ -> Rq₅

0q₅ -> 1q₆

1q₆ -> Rq₇

0q₇ -> 1q₈

1q₈ -> Rq₉

0q₉ -> 1q₁₀

….

….

q₁₀

1q₁₀ -> Lq₁₁

0q₁₁ -> Lq₁₂

0q₁₂ -> Rq₁₄

1q₁₂ -> Lq₁₃

1q₁₃ -> Lq₁₃

0q₁₃ -> Rq₁

 

 

….

….

q₁

При повторении действии q₁-q₁₃ получаем искомую Машину: q₀01^4x0

0q₁₄ -> Rq₀

 

….

….

q₀

Задача №1.

 

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

 

a) ├ x Ú (Ø x ® x)

b) x Ú Øy├ Øx ® Øy

c) x Ù y Ù z├ (x Ú y) ® (y Ú z)

d) x Ù Øx├ y ® Øy.

 

Решение:

 

1. ├ x Ú (Ø x ® x) – доказуема (исходя из таблицы истинности)

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

├ x – тождество истинно

├ x Ú (xÚ x)

├ x Ú (Ø x ® x)

 

1. x Ú Øy├ Øx ® Øy – доказуема (исходя из таблицы истинности)

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

x Ú Øy├ x Ú Øy – тождество истинно

x Ú Øy├ Øx ® Øy

 

1. x Ù y Ù z├ (x Ú y) ® (y Ú z) – доказуема (исходя из таблицы истинности)

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

y├ y 12 – тождество истинно

y,xÚy├ y 12

y,z,xÚy├ y 12

x,y,z,xÚy├ y 4

x,y,z,xÚy├ yÚz 7

x Ù y Ù z├ (x Ú y) ® (y Ú z)

 

1. x Ù Øx├ y ® Øy– доказуема (исходя из таблицы истинности)

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

 

├ Øy – тождество истинно

├ ØyÚØy

├ y®Øy

x Ù Øx├ y ® Øy

 

Задача №2.

 

Найти формулу исчисления предикатов истинную на алгебраической системе А=<R;·> и ложную на системе B=<Q;·>.

 

Решение:

 

Q – множество рациональных чисел.

R – множество действительных чисел.

 

"xÎR($yÎR(x=y*y*y*…*y))

 

Задача №3.

 

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

($x P(x)Ú$x Q(x))«$x (P(x)ÚQ(x)).

 

Решение:

 

($x P(x)Ú$x Q(x))«$x (P(x)ÚQ(x))

 

$x P(x)Ú$x Q(x)®$x (P(x)ÚQ(x))Ù($x (P(x)ÚQ(x))®$x P(x)Ú$x Q(x)

 

Доказываем с помощью дерева, используя формулы.

 

P(x)ÚQ(x)├ P(x)ÚQ(x)P(x)ÚQ(x)├ P(x)ÚQ(x)

$x P(x)Ú$x Q(x)├ $x (P(x)ÚQ(x)), $x (P(x)ÚQ(x))├ $x P(x)Ú$x Q(x)

$x P(x)Ú$x Q(x)®$x (P(x)ÚQ(x))Ù($x (P(x)ÚQ(x))®$x P(x)Ú$x Q(x)

 

Задача №4.

 

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

"x P(x,x,x)Ù$x$y (Ø(x=y)ÙP(x,y,x))ÙØ"x"y"z P(x,y,z).

 

Решение:

 

"x P(x,x,x)Ù$x$y (Ø(x=y)ÙP(x,y,x))ÙØ"x"y"z P(x,y,z) ~

 

~ "x P(x,x,x)Ù$x$y (Ø(x=y)ÙP(x,y,x))Ù$x$y$z ØP(x,y,z) ~ (x=a, x=b, y=c, z=d) ~

 

~ "x$a$y$b$c$d (P(x,x,x)ÙØ(a=y)ÙP(a,y,a)ÙØP(b,c,d). – ПНФ.

 

a = f(x), b = g(x), y = e(x), c = s(x), d = h(x) Þ

 

P(x,x,x)ÙØ(f(x) = e(x))ÙP(f(x),e(x),f(x))ÙØP(g(x),s(x),h(x)).

 

(1) P(x,x,x,)

(2)Ø(f(x) = e(x))

(3) P(f(x),e(x),f(x))

(4) ØP(g(x),s(x),h(x))

 

Формула выполнима Þ строим модель: A={a,b}.

 

P(a,a,a) = P(b,b,b); f(a) = a, g(a) = a, e(a) = b, s(a) = b, h(a) = a;

f(b) =b, g(b) = b, e(b) = a, s(b) = a, h(b) = b;

 

Задача №5.

 

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

Ø(($x"y P(x,y)Ú$x$y Q(x,y))Ú$x$y R(x,y)).

 

Решение:

 

Ø(($x"y P(x,y)Ú$x$y Q(x,y))Ú$x$y R(x,y)) ~

 

~ Ø($x"y P(x,y)Ú$x$y Q(x,y))ÙØ ($x$y R(x,y)) ~

 

~ "x$yØP(x,y)Ù"x"yØQ(x,y)Ù"x"yØR(x,y) (- коньюктивная нормальная форма) ~

 

~ (x = a, y = b, x = c, y = d) ~ "x$y"a"b"c"d (ØP(x,y)ÙØQ(a,b)ÙØR(c,d)) -

 

– клазуальная нормальная форма (она же является пренексной нормальной формой в данном случае).

 

 

Задача №6.

 

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

 

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

f₂="x (P₁(x)®$y (P₂(x,y)ÙØP₃(x,y))).

 

Решение:

 

f₁= $x"y$z"u (P₁(x)Ù((P₂(x,y)®ØP₃(y,z))ÚØ(P₁(z)®P₃(z,u)))) ~

 

~$x"y$z"u (P₁(x)Ù((P₂(x,y)®ØP₃(y,z))Ú (P₁(z)ÙØP₃(z,u)))) ~

 

~$x"y$z"u (P₁(x)Ù(P₁(z)ÚØP₂(x,y)ÚØP₃(y,z))Ù(ØP₂(x,y)ÚØP₃(y,z)).

 

 

f₂= "x (P₁(x,y)®$y (P₂(x,y)ÙØP₃(x,y))) ~

 

~"x(ØP₁(x)Ú$y (P₂(x,y)ÙØP₃(x,y))) ~

 

~"x$y((ØP₁(x)ÚP₂(x,y)Ù(ØP₁(x)ÚØP₃(x,y))).

 

 

(1)P₁(x) (2)P₁(z)ÚØP₂(x,y)ÚØP₃(y,z) (3)ØP₂(x,y)ÚØP₃(y,z) (4)ØP₁(x)ÚP₂(x,y) (5)ØP₁(x)ÚØP₃(x,y)

 

Строим модель: S=<P ,P ,P >

 

res((1),(4)) = P₂(x,z) - (6)

res((6),(3)) = ØP₃(y,z)

ØP₃(y,z) = 0 Þ P₃(y,z) = 1

Задача №7.

 

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

 

f(x) =

 

 

Задание №8.

 

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

 

f(x) =

 

…

…

q₁

 

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

q13

Lq0

Lq5

Lq5

Rq0

Rq7

Rq9

1Rq10

1q11

Lq12

Rq13

Rq0

Rq2

Rq3

Rq4

Rq6

Lq5

Lq6

0Rq8

Rq8

Lq11

Lq6

 

Задание №1

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

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

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

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

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

1. Y®(Z®U) ⊦ (Y®Z)®U

2. ⊦ ØØY®Y

3. YÚXÚU, ØXÚØYÚU, ØUÚX ⊦ UÚY

4. YÚØZ ⊦ ØY®ØZ

Решение:

1. Y®(Z®U) ⊦ (Y®Z)®U

Данная секвенция недоказуема!

 

Метод Квайна: Y®(Z®U) ⊦ (Y®Z)®U

Пусть Y=0, тогда: Пусть Y=1, тогда:

0®(Z®U) ⊦ (0®Z)®U 1®(Z®U) ⊦ (1®Z)®U

1 ⊦ 1®U

 

Пусть U=0, тогда: Пусть U=1, тогда: Пусть Z=0, тогда:

1 ⊦ 1®0 1 ⊦ 1®1 1®(0®U) ⊦ (1®0)®U

1 ⊦ 0 1 ⊦ 1 1 ⊦ 0®U

тождественно ложно. Пусть Z=1, тогда:

1®(1®U) ⊦ (1®1)®U

1®(1®U) ⊦ 1®U

Пусть U=0, тогда: Пусть U=1, тогда:

1®(1®0) ⊦ 1®0 1®(1®1) ¢ 1®1

1®0 ¢ 0 1 ¢ 1

0 ¢ 0

Метод редукции (оптимальный): Y®(Z®U) ¢ (Y®Z)®U

Докажем что при (Y®Z)®U = 0, Y®(Z®U) =1

Чтобы выполнялось (Y®Z)®U = 0 надо, чтобы выполнялось:

(Y®Z) = 1, U = 0

Чтобы выполнялось Y®Z = 1 достаточно Y = 0.

Тогда Y®(Z®U) =1 тождественно истинно.

Значит при Y = 0 и любых Z и U данная секвенция недоказуема!

Метод резолюций: Y®(Z®U) ¢ (Y®Z)®U

Приведем формулу (Y®(Z®U)) ¢ ((Y®Z)®U) к КНФ.

(Y®(Z®U)), Ø((Y®Z)®U) = ØYÚØZÚU, Ø(Ø(ØYÚZ)ÚU) =

= ØYÚØZÚU, (ØYÚZ)ÙØU = ØYÚØZÚU,ØYÚZ,ØU

 

(1) ØYÚØZÚU

(2) ØYÚZ

(3) ØU

(4) res_Z(1,2) = ØYÚU

(5) res_U(3,4) = ØY

Следовательно данная секвенция недоказуема.

 

2. ¢ ØØY®Y Данная секвенция доказуема!

Y ¢ Y

₈ ØØY ¢ Y

¢ ØØY®Y

 

3. YÚXÚU, ØXÚØYÚU, ØUÚX ¢ UÚY

Данная секвенция недоказуема!

Метод Квайна: YÚXÚU, ØXÚØYÚU, ØUÚX ¢ UÚY

(YÚXÚU) Ù(ØXÚØYÚU) Ù(ØUÚX) ¢ UÚY

 

Пусть X = 0, тогда:

(YÚ0ÚU) Ù(Ø0ÚØYÚU) Ù(ØUÚ0) ¢ UÚY

(YÚU) Ù1 Ù(ØU) ¢ UÚY

 

Пусть Y = 0, тогда: Пусть Y = 1, тогда:

(0ÚU) Ù1 Ù(ØU) ¢ UÚ0 (1ÚU)Ù1Ù(ØU) ¢ UÚ1

U Ù1 Ù(ØU) ¢ U 1Ù(ØU) ¢ 1

 

Пусть U = 0, тогда: Пусть U = 1, тогда: Пусть U = 0, тогда: Пусть U = 1, тогда:

0 Ù1 Ù(Ø0) ¢ 0 1Ù1Ù(Ø1) ¢ 1 1Ù(Ø0) ¢ 1 1Ù(Ø1) ¢ 1

0 ¢ 0 0 ¢ 1 1 ¢ 1 0 ¢ 1

 

Пусть X = 1, тогда:

(YÚ1ÚU) Ù(Ø1ÚØYÚU) Ù(ØUÚ1) ¢ UÚY

1Ù(ØYÚU) Ù1 ¢ UÚY

 

Пусть Y = 0, тогда: Пусть Y = 1, тогда:

1Ù(Ø0ÚU) Ù1 ¢ UÚ0 1Ù(Ø1ÚU) Ù1 ¢ UÚ1

1Ù1 ¢ U 1ÙU ¢ 1

Пусть U = 0, тогда: Пусть U = 1, тогда: Пусть U = 0, тогда: Пусть U = 1, тогда:

1 ¢ 0 1 ¢ 1 1Ù0 ¢ 1 1Ù1 ¢ 1

Тождественно ложно! 0 ¢ 1 1 ¢ 1

 

Метод редукции: YÚXÚU, ØXÚØYÚU, ØUÚX ¢ UÚY

Докажем, что при (UÚY) = 0, (YÚXÚU) Ù(ØXÚØYÚU) Ù(ØUÚX) = 1

(UÚY) = 0 выполняется только при условии, что U = 0 и Y = 0

Тогда:

(0ÚXÚ0) Ù(ØXÚØ0Ú0) Ù(Ø0ÚX) = X Ù(ØXÚ1) Ù(1ÚX) = X Ù1Ù1 = X

Значит при U = 0, Y = 0, X = 1 данная секвенция недоказуема!

 

Метод резолюций (оптимальный): YÚXÚU, ØXÚØYÚU, ØUÚX ¢ UÚY

Приведем формулу YÚXÚU, ØXÚØYÚU, ØUÚX ¢ UÚY к КНФ

YÚXÚU,ØXÚØYÚU,ØUÚX, Ø(UÚY) = YÚXÚU,ØXÚØYÚU,ØUÚX, ØU, ØY

(1) YÚXÚU

(2) ØXÚØYÚU

(3) ØUÚX

(4) ØU

(5) ØY

(6) res_X,Y(1,2) = ØU

(7) res_U(4,6) = 0

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

 

4. YÚØZ ¢ ØY®ØZ Данная секвенция доказуема!

 

Тождественно истина доказуема доказуема

¢ ØZ; _{12 12} ØZ ¢ ØZ; ₁₂ YÚØZ ¢ YÚØZ

₆ YÚØZ,ØY,Y ¢ ØZ; YÚØZ,ØY,ØZ ¢ ØZ; YÚØZ, ØY ¢ YÚØZ

₈ YÚØZ, ØY ¢ ØZ

YÚØZ ¢ ØY®ØZ

Задание №2

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

A = <Í; b >, B = <Í; P(x,y)>, где P(x,y) означает что x и y взаимно просты.

 

Решение:

A: $x$y(xby), $x"y(xby)

B: $x$yØP(x,y)

Задание №3

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

 

"x (P(x)®Q(x))Ú$x (P(x)ÙØQ(x))

 

Решение:

 

Безусловный вывод. Безусловный вывод.

₁ ¢P(x); ¢ØQ(x)

₁₅ ¢P(x)ÙØQ(x)

₅ ¢$x (P(x)ÙØQ(x))

¢"x (P(x)®Q(x))Ú$x (P(x)ÙØQ(x))

 

Задание №4

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

"xØP(x,x)Ù"x,y(P(x,y)®P(y,x))Ù"x"y"z$u(P(u,x)ÙP(u,y)ÙP(u,z))

 

Решение:

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

"xØP(x,x)Ù"x,y(ØP(x,y)ÚP(y,x))Ù"x"y"z$u(P(u,x)ÙP(u,y)ÙP(u,z))

 

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

"xØP(x,x)Ù"x,y(ØP(x,y)ÚP(y,x))Ù"x"y"z$u(P(u,x)ÙP(u,y)ÙP(u,z))

 

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

"x"v,yØP(x,x)Ù(ØP(v,y)ÚP(y,v))Ù"x"y"z$u(P(u,x)ÙP(u,y)ÙP(u,z))

"x"v,y"n"m"z$uØP(x,x)Ù(ØP(v,y)ÚP(y,v))ÙP(u,n)ÙP(u,m)ÙP(u,z)

 

4. Получили КлНФ. Методом резолюций проверим выполнимость данной формулы:

(1) ØP(x,x)

(2) ØP(v,y)ÚP(y,v)

(3) P(u,n)

(4) P(u,m)

(5) P(u,z)

(6) res(1,3) = res(1,4) = res(1,5) = 0

 

Значит данное множество невыполнимо!

Задание №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

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

j₁ = "x$y$z"u(P₁(x,y)Ù(P₁(x,y)®P₂(x,z,u)))

j₂ = $x"y"z(P(x,y,z)Ù$u$v(P₂(x,y,z)®P₁(x,u)ÙP₁(v,x)))

j₃ = "x"y$z(P₂(z,x,y)ÙØP₁(z,x))

 

Решение:

 

j₁ = "x$y$z"u(P₁(x,y)Ù(ØP₁(x,y)ÚP₂(x,z,u)))

 

j₂ = $x"y"z$u$v(P(x,y,z)Ù(P₂(x,y,z)®P₁(x,u)ÙP₁(v,x)))

j₂ = $x"y"z$u$v(P(x,y,z)Ù(ØP₂(x,y,z)Ú(P₁(x,u)ÙP₁(v,x))))

j₂ = $x"y"z$u$v(P(x,y,z)Ù(ØP₂(x,y,z)ÚP₁(x,u))Ù(ØP₂(x,y,z)ÚP₁(v,x)))

 

j₃ = "x"y$z(P₂(z,x,y)ÙØP₁(z,x))

 

{j₁, j₂, j₃} = {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)}

 

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

 

{j₁, j₂, j₃} = {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, при xby

 

 

Задание №8

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

 

x-y, при x>y

F(x,y) =

0, при xby

 

 

"$«'&®£¢ØÙÚj

17 Задача №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
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
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
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
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)}

Задача №2.

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

Y = < N, ∙ >, Z = < Q, ∙ >

РЕШЕНИЕ.

Формулы исчисления предикатов, истинной на алгебраической системе Y и ложной

на системе Z не существует. Так как

Y = < N, ∙ >, Z = < Q, ∙ > - группы без кручения. Имеют одинаковые множества

выполнимых формул И.П., т.е. они элементарно эквивалентны.

Задача №3.

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

(х Р(х) Λ х Q(х)) ↔ х (Р(х) Λ Q(х))

РЕШЕНИЕ.

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

Пусть

Р(х) = φ

Q(х) = ψ

φ ├ φ; ψ ├ ψ φ ├ φ; ψ ├ ψ

13 12

φ ├ х φ; ψ ├ х ψ φ, ψ ├ φ; φ, ψ ├ ψ

12 1

φ, ψ ├ х φ; φ, ψ ├ х ψ φ, ψ ├ φ Λ ψ

1 13

φ, ψ ├ х φ Λ х ψ φ, ψ ├ х (φ Λ ψ)

х φ Λ х ψ ├ х (φ Λ ψ)

 

φ ├ φ; ψ ├ ψ φ ├ φ; ψ ├ ψ

12 13

φ, ψ ├ φ; φ, ψ ├ ψ φ ├ х φ; ψ ├ х ψ

1 12

φ, ψ ├ φ Λ ψ φ, ψ ├ х φ; φ, ψ ├ х ψ

13 1

φ, ψ ├ х (φ Λ ψ) φ, ψ ├ х φ Λ х ψ

х (φ Λ ψ) ├ х φ Λ х ψ

Задача №4.

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

Модель этой формулы.

х у (х ∙ S (у) = S (х ∙ у)) Λ х у (х ∙ у = у ∙ х)

РЕШЕНИЕ.

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

х у (х ∙ S (у) = S (х ∙ у)) Λ х у (х ∙ у = у ∙ х)

х у (х ∙ S (у) = S (х ∙ у)) Λ (С₁ ∙ С₂ = С₂ ∙ С₁)

Рассмотрим множество дизъюнктов:

{ х ∙ S (у) = S (х ∙ у); (С₁ ∙ С₂ = С₂ ∙ С₁) }

res (1,2) = 0

c₁ /x; c₂ /S(y); c ₂ ∙ c₁/S(x ∙ y)

Так как существует резолютивный вывод нуля, то формула невыполнима.

Задача №5.

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

((х у Р(х,у) v х у (х,у)) v х у R(х,у)

РЕШЕНИЕ.

((х у Р(х,у) v х у (х,у)) v х у R(х,у)

((х у Р(х,у) Λ (х у (х,у)) v х у R(х,у)

х у Р(х,у) Λ х у (х,у)) v х у R(х,у)

х (у Р(х,у) Λ у (х,у)) v х у R(х,у)

х z u ((Р(х,z) Λ у (х,у)) v у R(u,у))

х z u y ((Р(х,z) Λ (х,у)) v R(u,у)) – пренексная форма.

х z u y ((Р(х,z) v R(u,у)) Λ ((х,у) v R(u,у)) – клазуальная форма.

 

 

 

Задача №6.