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
Методом резолюций проверить, противоречиво ли множество предложений {f1,f2,f3}. Если множество непротиворечиво, то построить модель этого множества.
f1 = $x$y$z((P1(x,y) ® ØP2(y,z))Ù(ØP2(y,z)®P1(x,y)))
f2 = "x$y(P1(x,y)ÙØP2(y,x))
f3 = Ø$x$y(ØP1(x,y) ÙP2(x,y))
Решение:
Устраним непротиворечивость методом резолюций, если не противоречиво, то построим модель.
f1 º $x$y$z((ØP1(x,y)ÚØP2(y,z)) Ù(P2(y,z)ÚP1(x,y)))
f2 = "x$y(P1(x,y)ÙØP2(y,x))
f3 = "x"y(P1(x,y) Ù ØP2(x,y))
{f1,f2,f3} = (ØP1(x,y)ÚØP2(y,z)), (P2(y,z)ÚP1(x,y), P1(x,y), ØP2(y,x), P1(x,y), ØP2(x,y))
Пусть в j1 x=c1 , y=c2,z=c3; в j2 y=c4; тогда:
{f1,f2,f3} = (ØP1(c1, c2)ÚØP2(c2, c3)), (P2(c2, c3)ÚP1(c1, c2), P1(x, c4), ØP2(c4,x), P1(x,y), ØP2(x,y))
(1) (ØP1(c1, c2)ÚØP2(c2, c3))
(2) (P2(c2, c3)ÚP1(c1, c2)
(3) P1(x, c4)
(4) ØP2(c4,x)
(5) P1(x,y)
(6) ØP2(x,y)
(7) resP1,p2(1,2)= 0 => данное множество противоречиво, модели не существует
Задание №7
Доказать примитивную рекурсивность функций, выражая их через простейшие с помощью операторов суперпозиции и примитивной рекурсии.
f(x)=4x
Доказательство:
Введём функцию:h(x1,x2)
I 1 1(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
Решение:
| … | …. |
q1
q101x0 º> q0014x0
Например: x=2, тогда 4x=4*2=8, тогда Машина выглядит так в начальном состоянии:
| …. | …. |
q1
1q1 -> 0q1
0q1 -> Rq2
1q2 -> Rq2
0q2 -> Rq3
0q3 -> 1q4
1q3 -> Rq3
1q4 -> Rq5
0q5 -> 1q6
1q6 -> Rq7
0q7 -> 1q8
1q8 -> Rq9
0q9 -> 1q10
| …. | …. |
q10
1q10 -> Lq11
0q11 -> Lq12
0q12 -> Rq14
1q12 -> Lq13
1q13 -> Lq13
0q13 -> Rq1
| …. | …. |
q1
При повторении действии q1-q13 получаем искомую Машину: q0014x0
0q14 -> Rq0
| …. | …. |
q0
Задача №1.
Из данной совокупности секвенций выбрать доказуемые, построить их доказательства, для недоказуемых показать их недоказуемость с помощью: а) алгоритма Квайна, б) алгоритма редукции, в)метода резолюций. Среди этих доказательств недоказуемости выбрать оптимально в каждом конкретном случае.
a) ├ x Ú (Ø x ® x)
b) x Ú Øy├ Øx ® Øy
c) x Ù y Ù z├ (x Ú y) ® (y Ú z)
d) x Ù Øx├ y ® Øy.
Решение:
- ├ x Ú (Ø x ® x) – доказуема (исходя из таблицы истинности)
Доказательство:
├ x – тождество истинно
├ x Ú (xÚ x)
├ x Ú (Ø x ® x)
- x Ú Øy├ Øx ® Øy – доказуема (исходя из таблицы истинности)
Доказательство:
x Ú Øy├ x Ú Øy – тождество истинно
x Ú Øy├ Øx ® Øy
- 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)
- 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.
Методом резолюций проверить, противоречиво ли множество предложений {f1,f2}. Если множество непротиворечиво, то построить модель этого множества.
f1=$x"y$z"u (P1(x)Ù((P2(x,y)®ØP3(y,z))ÚØ(P1(z)®P3(z,u)))),
f2="x (P1(x)®$y (P2(x,y)ÙØP3(x,y))).
Решение:
f1= $x"y$z"u (P1(x)Ù((P2(x,y)®ØP3(y,z))ÚØ(P1(z)®P3(z,u)))) ~
~$x"y$z"u (P1(x)Ù((P2(x,y)®ØP3(y,z))Ú (P1(z)ÙØP3(z,u)))) ~
~$x"y$z"u (P1(x)Ù(P1(z)ÚØP2(x,y)ÚØP3(y,z))Ù(ØP2(x,y)ÚØP3(y,z)).
f2= "x (P1(x,y)®$y (P2(x,y)ÙØP3(x,y))) ~
~"x(ØP1(x)Ú$y (P2(x,y)ÙØP3(x,y))) ~
~"x$y((ØP1(x)ÚP2(x,y)Ù(ØP1(x)ÚØP3(x,y))).
(1)P1(x) (2)P1(z)ÚØP2(x,y)ÚØP3(y,z) (3)ØP2(x,y)ÚØP3(y,z) (4)ØP1(x)ÚP2(x,y) (5)ØP1(x)ÚØP3(x,y)
Строим модель: S=<P 
,P 
,P 
>
res((1),(4)) = P2(x,z) - (6)
res((6),(3)) = ØP3(y,z)
ØP3(y,z) = 0 Þ P3(y,z) = 1
Задача №7.
Доказать примитивную рекурсивность функций, выражая их через простейшие с помощью операторов суперпозиции и примитивной рекурсии.
f(x) = 
Задание №8.
Построить машины Тьюринга для вычисления функций:
f(x) =
| … | … |
q1
| 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) resZ(1,2) = ØYÚU
(5) resU(3,4) = ØY
Следовательно данная секвенция недоказуема.
2. ¢ ØØY®Y Данная секвенция доказуема!
Y ¢ Y
8 ØØ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) resX,Y(1,2) = ØU
(7) resU(4,6) = 0
Следовательно, данная секвенция недоказуема.
4. YÚØZ ¢ ØY®ØZ Данная секвенция доказуема!
Тождественно истина доказуема доказуема
¢ ØZ; 12 12 ØZ ¢ ØZ; 12 YÚØZ ¢ YÚØZ
6 YÚØZ,ØY,Y ¢ ØZ; YÚØZ,ØY,ØZ ¢ ØZ; YÚØZ, ØY ¢ YÚØZ
8 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))
Решение:
Безусловный вывод. Безусловный вывод.
1 ¢P(x); ¢ØQ(x)
15 ¢P(x)ÙØQ(x)
5 ¢$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
Методом резолюций проверить, противоречиво ли множество предложений {j1, j2, j3}. Если множество непротиворечиво, то построить модель множества.
j1 = "x$y$z"u(P1(x,y)Ù(P1(x,y)®P2(x,z,u)))
j2 = $x"y"z(P(x,y,z)Ù$u$v(P2(x,y,z)®P1(x,u)ÙP1(v,x)))
j3 = "x"y$z(P2(z,x,y)ÙØP1(z,x))
Решение:
j1 = "x$y$z"u(P1(x,y)Ù(ØP1(x,y)ÚP2(x,z,u)))
j2 = $x"y"z$u$v(P(x,y,z)Ù(P2(x,y,z)®P1(x,u)ÙP1(v,x)))
j2 = $x"y"z$u$v(P(x,y,z)Ù(ØP2(x,y,z)Ú(P1(x,u)ÙP1(v,x))))
j2 = $x"y"z$u$v(P(x,y,z)Ù(ØP2(x,y,z)ÚP1(x,u))Ù(ØP2(x,y,z)ÚP1(v,x)))
j3 = "x"y$z(P2(z,x,y)ÙØP1(z,x))
{j1, j2, j3} = {P1(x,y), ØP1(x,y)ÚP2(x,z,u)), P(x,y,z), ØP2(x,y,z)ÚP1(x,u)), ØP2(x,y,z)ÚP1(v,x)), P2(z,x,y), ØP1(z,x)}
Пусть в j1 y = с1, z = с2, в j2 x = с3, u = с4, v = с5, в j3 z = с6 тогда:
{j1, j2, j3} = {P1(x,с1), ØP1(x,с1)ÚP2(x,с2,u), P(с3,y,z), ØP2(с3,y,z)ÚP1(с3,с5), ØP2(с3,y,z)ÚP1(с5,с3), P2(с6,x,y), ØP1(с6,x)}
(1) P1(x,с1)
(2) ØP1(x,с1)ÚP2(x,с2,u)
(3) P(с3,y,z)
(4) ØP2(с3,y,z)ÚP1(с3,с5)
(5) ØP2(с3,y,z)ÚP1(с5,с3)
(6) P2(с6,x,y)
(7) ØP1(с6,x)
(8) res(1,2) = P2(x,с2,u)
(9) res(1,7) = 0
(10) res(4,6) = res(4,8) = P1(с3,с5)
(11) res(5,6) = res(5,8) = P1(с5,с3)
(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:
D1 = x v y v u res(D1, D2 ) = x D6 = x
D2 = y v u res(D4, D6 ) = 0
D3 = x v z
D4 = x
D5 = 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 (х ∙ у)) Λ (С1 ∙ С2 = С2 ∙ С1)
Рассмотрим множество дизъюнктов:
{ х ∙ S (у) = S (х ∙ у); (С1 ∙ С2 = С2 ∙ С1) }
res (1,2) = 0
c1 /x; c2 /S(y); c 2 ∙ c1/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.