Задача №6. Методом резолюций проверить, противоречиво ли множество предложений

{Ф₁ , Ф₂ , Ф₃}. Если множество непротиворечиво, то построить модель этого

множества.

Ф₁ = х ( у Р₁(х,у) Λ у ( Р₁(х,у) → ¬Р₂(у,х)))

Ф₂ = х ( у Р₁(х,у) Λ z Р₂(х,z))

Ф₃ = x y z u ( Р₂(х,у) Λ Р₁(y,z) Λ Р₁(z,u))

РЕШЕНИЕ.

Ф₁ = х ( у Р₁(х,у) Λ у ( Р₁(х,у) → ¬Р₂(у,х))) ≡

≡ х у ( Р₁(х,С₁) Λ ( Р₁(х,у) → ¬Р₂(у,х))) ≡

≡ у ( Р₁(С₂,С₁) Λ ( Р₁(С₂,у) → ¬Р₂(у, С₂))) ≡

≡ у ( Р₁(С₂,С₁) Λ (¬Р₁(С₂,у) v ¬Р₂(у, С₂)))

Ф₂ = х ( у Р₁(х,у) Λ z Р₂(х,z)) ≡ х ( Р₁(х,С₁) Λ Р₂(х,С₃))

Ф₃ = x y z u ( Р₂(х,у) Λ Р₁(y,z) Λ Р₁(z,u)) ≡

≡ х z ( Р₂(х,f(x)) Λ Р₁(f(x),z) Λ Р₁(z,f(z)))

{ Р₁(С₂,С₁) ; ¬Р₁(С₂,у) v ¬Р₂(у, С₂) ; Р₁(х,С₁) ; Р₂(х,С₃) ; Р₂(х,f(x)) ; Р₁(f(x),z) ; Р₁(z,f(z))}

res ( 1 , 2 ) = ¬Р₂(у, С₂)

C₁/y

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

Задача №10.

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

помощью операторов суперпозиции и примитивной рекурсии.

.

x − 3, при x > 3

f(x) =

0, при x ≤ 3

РЕШЕНИЕ.

f(x) = x − 3

f₁(x) = x − 1

0, при x ≤ 1

f₁(x) =

x − 1, при x > 1

f₁(0) = 0

f₁(x + 1) = x

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

f(x) = f₁(x) ◦ f₁(x) ◦ f₁(x) - суперпозиция

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

Задача №11.

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

РЕШЕНИЕ.

x − 3, при x > 3

f(x) =

0, при x ≤ 3

q₁ 1 → q₁ 0

q₁ 0 → R q₂

q₂ 1 → q₂ 0

q₂ 0 → R q₃

q₃ 1 → q₃ 0

q₃ 0 → R q₄

q₄ 0 → q₄ 1

q₄ 1 → q₀

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

Решение:

а)

Доказуема

б)

Недоказуема, покажем это по алгоритму редукции.

Формула будет неверна при следующих условиях:

в)

Недоказуема, покажем это по алгоритму Квайна:

Возьмем переменные по убыванию: x,z,y,u

Встретили 0, следовательно, формула недоказуема.

г)

Доказуема:

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

А=<Q;+>, B=<Z;+>

Решение:

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

Решение:

Докажем формулу в одну сторону:

Докажем формулу в другую сторону:

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

Решение:

y=f(x)

z=g(x)

Формула выполнима, ее модель:

x	f(x)	g(x)
a	a	b
b	b	a

P	a	b
a	+	+
b	+	+

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

Решение:

x=f(t,m)

y=g(t,m)

z=h(t,m)

k=s(t,m)

Ответ:

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

Решение:

x=k(y)

x=g(y)

z=t(y)

z= m(x,y)

Множество непротиворечиво, его модель:

x

a

b

y	k(y)	g(y)	t(y)
a	b	b	b
b	a	a	a

m(x,y)	a	b
a	a	b
b	b	a

c	f(c)
a	b
b	a

P1(a,b)	a	b
a	+	-
b	-	+

P2(a,b)	A	b
a	-	+
b	+	-

P(a,b)	a	b
a	+	-
b	-	+

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

f(x,y)=xy+1

Решение:

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

Решение:

X+1 Y+1
…..	0	1	…..	1	0	1	…..	1	0	….
		Q1

q₁1 → q₁R уменьшаем

q₁0 → q₂L массив единиц X на 1

q₂1 → q₃0

q₃0 → q₄L

q₄1 → q₄L

q₄0 → q₅R проверяем был ли X равен 0

q₅0 → q₆0 -----если Х=0, то

q₆0 → q₆R идем на первую 1 Y’а

q₆1 → q₇1 обнуляем его с конца

q₇1 → q₇R

q₇0 → q₈L

q₈1 → q₉0

q₉0 → q₈L

q₈0 → q₁₀R

q₁₀0 → q₁₀1 конец случая Х=0, Y-любое

q₁₀1 → q₅₆1 переход прибавлению 1

q₅1 → q₁₁1 -----если Х!=0, то

q₁₁1 → q₁₁R идем на первую 1 Y’а

q₁₁0 → q₁₂R

q₁₂1 → q₁₂R уменьшаем

q₁₂0 → q₁₃L массив единиц Y на 1

q₁₃1 → q₁₄0

q₁₄0 → q₁₅L

q₁₅1 → q₁₅L встали на начало Y

q₁₅0 → q₁₆R проверяем был ли Y= 0

q₁₆0 → q₁₇0 -----если Y=0, то

q₁₇0 → q₁₇L

q₁₇1 → q₁₈1 встали на последнюю 1 X’а

q₁₈1 → q₁₉0 обнуляем его с конца

q₁₉0 → q₁₈L

q₁₈0 → q₂₀R

q₂₀0 → q₂₀1 конец случая Х!=0, Y=0

q₂₀1 → q₅₆1 переход прибавлению 1

q₁₆1 → q₂₁1 -----если Y!=0, то

q₂₁1 → q₂₁R идем в конец Y

q₂₁0 → q₂₂L

q₂₂1 → q₂₂0 стираем 1

q₂₂0 → q₂₃L есть ли еще единицы?

q₂₃1 → q₂₄1 --если остались, то

q₂₄1 → q₂₄L идем на последний массив

q₂₄0 → q₂₅0 Х’ов (в процессе

q₂₅0 → q₂₆L умножения их появится >1)

q₂₆1 → q₂₆L

q₂₆0 → q₂₇L

q₂₇1 → q₂₆1

q₂₇0 → q₂₈R встаем на 0 перед 1’м X

q₂₈0 → q₂₉R –копируем этот Х в

q₂₉1 → q₃₀0 пространство слева от

q₃₀0 → q₃₁L этого 0

q₃₁0 → q₃₂1

q₃₂1 → q₃₂L

q₃₂0 → q₃₃L

q₃₃1 → q₃₃L

q₃₃0 → q₃₄1

q₃₄1 → q₃₄R

q₃₄0 → q₃₅R

q₃₅1 → q₃₅R

q₃₅0 → q₂₈0

q₂₉0 → q₃₆R

q₃₆0 → q₃₇L -корректируем результат

q₃₇0 → q₃₈1 (ликвидация лишнего 0)

q₃₈1 → q₃₈L

q₃₈0 → q₃₉R

q₃₉1 → q₄₀0

q₄₀0 → q₄₁L

q₄₁0 → q₄₂1

q₄₂1 → q₄₂L

q₄₂0 → q₄₃R

q₄₃1 → q₄₄0

q₄₄0 → q₄₅R

q₄₅1 → q₄₅R -конец коррекции и копир-я

q₄₅0 → q₄₆R идем на первую 1 Y’а

q₄₆1 → q₄₆R

q₄₆0 → q₄₇R

q₄₇1 → q₄₆1

q₄₇0 → q₄₈L

q₄₈0 → q₄₉L

q₄₉1 → q₄₉L

q₄₉0 → q₂₁R головка снова на первой единице Y’а, зацикливаем процесс умножения

q₂₃0 → q₅₀0 --в Y’e не осталось больше единиц, тогда

q₅₀0 → q₅₀L умножение закончено

q₅₀1 → q₅₁0 сдвигаем массивы единиц Х’ов в единое целое

q₅₁0 → q₅₁L (ликвидируем 0 между ними)

q₅₁1 → q₅₂1

q₅₂1 → q₅₂L

q₅₂0 → q₅₃1

q₅₃1 → q₅₄L

q₅₄1 → q₅₅1

q₅₅1 → q₅₅R

q₅₅0 → q₅₀0 цикл идет пока между Х’ми есть хоть один 0

q₅₄0 → q₅₆1 переход прибавлению 1

q₅₆1 → q₅₆L -----прибавление 1

q₅₆0 → q₅₇1

q₅₇1 → q₀1 ---------------Конец работы программы------------

(XY+1)+1
…..	0	1	…..	1	0	…..
		Q0