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)

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

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

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

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

f(x, y)=xy+1

Решение:

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

Решение:

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 ---------------Конец работы программы------------