I Проверить выводимость в исчислении высказываний методом Куайна

I.Проверить выводимость в исчислении высказываний методом Куайна, методом редукции и методом резолюций.
⊢A→A∧A⋁B

Решение
1. Метод Куайна
Предположим, что B=1, тогда функция принимает значение
F=A→A∧A⋁1=A→A∧1
При A=1
F1=1→1∧1=1→1=1
При A=0
F2=0→0∧1=0→0=1
Если B=0
F=A→A∧A⋁0
При A=1
F3=1→1∧1⋁0=1→1∧1=1→1=1
При A=0
F4=0→0∧0⋁0=0→0∧0=0→0=1
Следовательно, наша функция при любых наборах значений переменных является тождественно истинной или тавтологией и выводима.
2. Метод редукции
Допустим наша формула в некоторой интерпретации равна 0
Тогда по правилу импликации
A=1
A∧A⋁B=0
Во второй формуле заметим, что A=1
1∧1⋁B=1∧1=1
Мы пришли к противоречию, следовательно, формула тождественно истинна или выводима
3. Метод резолюций
По теореме обратной теореме дедукции посылку можно перенести в левую часть
A⊢A∧A⋁B
Запишем инверсию исходной формулы
A∧A⋁B
Применяем законы де Моргана
A⋁A⋁B
A⋁A∧B
Используем законы дистрибутивности дизъюнкции относительно коньюнкции
A⋁A∧A⋁B=A∧A⋁B
Получаем множество дизъюнктов
A,A,A⋁B
Применяем к первому и второму дизъюнкту, правило резолюций
A,A,A⋁B,∅
Таким образом пустой дизъюнкт выведен, следовательно, выражение с отрицанием высказывания опровергнуто, следовательно, само высказывание доказано.

II.Пусть Омега – множество людей. На множестве Омега заданы следующие предикаты:
1.E(x, y)=И⇔x и y – один и тот же человек;
2.P(x, y)=И ⇔ x родитель y;
3.C(x, y)=И ⇔ x и y – супруги;
4.M(x)=И ⇔ x – мужчина;
5.W(x)=И ⇔ x – женщина.

С использованием этих предикатов записать формулы, выражающие следующие утверждения

14. X – кузина

Решение.
Кузина – двоюродная сестра – дочь брата или сестры матери, либо дочь брата или сестры отца.
Введем дополнительные понятия
Y-человек к которому X является кузиной
Y1-родитель Y⇔P(Y1, Y)=И
Y2-родитель Y1⇔P(Y2, Y1)=И
X1-родитель X⇔P(X1, X)=И
Тогда, что бы X1 и Y1 были сестрами или братьями необходимо, что бы
Y2-родитель X1⇔P(Y2, X1)=И
И кроме того, X1 и Y1 не были одним и тем же человеком
E(X1, Y1)=И
Последнее условие – кузина должна быть женщиной
W(X)=И
Окончательно записываем наше высказывание
X – кузина⇔∃Y, Y1, Y2,X1∈Ω: P(Y1, Y)∧P(Y2, Y1)∧P(X1, X)∧P(Y2, X1)∧E(X1, Y1)∧W(X)=И

III.Привести формулу к предваренной форме
¬∃x∀yQx,y→¬∀y∃xQx,y

Решение.
1. Исключаем импликацию, заменяя ее КНФ
∃x∀yQx,y∨¬∀y∃xQx,y
2. Применяем отрицание
∃x∀yQx,y∨∃y∀xQx,y

2. Выносим кванторы вперед
∃x∃y∀zQx,z∨∀wQw,y
∃x∃y∀z∀wQx,z∨Qw,y
Данная форма приведена к предварено нормальной, в дальнейшем, в ней можно исключить кванторы существования и общности, для сведения к предложению (бескванторной дизъюнкций литералов)
Qa,z∨Qw,b

IV.Построить машину Тьюринга для перевода из одной конфигурации в другую. На ленте всех машин Тьюринга записаны лишь нули и единицы, при этом пустые ячейки содержат нули. (x, y, z≥1) Проверить работу машины Тьюринга для конкретных значений x, y, z .
q11x01y=q01x;x>yq01y;x≤y

Решение.
Алфавит у нас состоит из двух элементов 0 и 1
Начальное слово
1x01y
Конечное слово у нас зависит от того какая последовательность единиц длиннее, 1x или 1y.
Запишем сначала функциональную схему.

q1
q2
q3
q4
q5
q6
q7
q8
q9
q10
q11
0
q21П
q71П
q40П
q51Л
q121Л
q10Л
q80П
q90Л
q90Л

q00П
1
q11Л
q30П
q31П
q41П
q60Л
q61Л
q71П
q80П
q100Л
q110Л
q111Л

q12
q13
q14
0
q130Л
q140П
q140П
1
q121Л
q130Л
q00П

Рассмотрим алгоритм по подробнее. Допустим начальное слово
01110111110
Машина находится в начальном положении состоянии q1 в ячейке 0
q101110111110
Команда q21П – обозначаем границу слева (смотрим пересечение q1 и 0), записываем 1 вместо 0, переход вправо и изменения состояния на q2
1q21110111110
Команда q30П – стираем первую единицу набора 1x, записываем 0 вместо 1, переход вправо и изменения состояния на q3
10q3110111110
Команда q31П остальные единицы набора 1x не меняются, до тех пор пока машине не встретится 0 по середине между наборами
1011q30111110
Команда q40П, ноль не изменяется однако состояние меняется на q4, переход вправо
10110q4111110
Команда q41П, остальные единицы набора 1y не меняются, до тех пор пока машине не встретится крайний 0 справа
1011011111q40
Команда q51Л – обозначаем границу справа, записываем 1 вместо 0, переход влево и изменения состояния на q5
101101111q511
Команда q60Л – стираем последнюю единицу набора 1y, записываем 0 вместо 1, переход влево и изменения состояния на q6
10110111q6101
Далее команды повторяют тоже самое, но в обратном порядке. q61Л не меняет цифры набора 1y и происходит сдвиг влево пока не встретится 0.
1011q60111101
Команда q10Л, не меняет ноль посередине, переход влево и изменение состояния на q1
101q110111101
Команда q11Л, не меняет оставшиеся единицы в наборе 1x, переход влево пока не встретится 0
1q10110111101
Ситуация приходит в изначальную позицию. Первый цикл завершился. Повторяя аналогичные рассуждения в конце второго цикла
11q1010111011
Третий цикл
111q100110111
Данный цикл отличается от изначального, что команда q21П, перезаписывает как обычно ноль, однако следующая ячейка тоже 0, весь набор 1x кончился первым
1111q20110111
Поэтому управление переходит на команду q71П
11111q7110111
Теперь нам необходимо оставить единицы, оставшиеся от набора 1y, поэтому, происходит переход вправо q71П, пока не встретится 0
1111111q70111
Команда q80П оставляет 0, как есть переходит вправо и в состояние q8
11111110q8111
Оставшиеся единицы нам не нужны поэтому стираем их командой q80П, пока не встретится крайний 0 справа
11111110000q80
Команда q90Л оставляет 0, как есть, переходит влево и в состояние q9
1111111000q900
Команда q90Л переводит позицию машины влево, пока не встретится единица.
111111q9100000
Нам необходимо стереть две лишних единицы, поэтому стираем их команадами q100Л и q110Л
1111q1110000000
Окончательно надо передвинуть указатель машины на начало нового слова. Это делается командой q111Л. До тех пор пока мы не дошли до крайнего 0 слева.
q110111110000000
Команда q00П смещает указатель обратно вправо и останавливает машину
0q0111110000000
Для другой ситуации, когда последовательность 1x длиннее, например.
q101111101110
Сначала все происходит аналогично однако циклы будем считать в состоянии q4 Первый цикл.
1011110111q40
Второй цикл
110111011q401
Третий цикл
11101101q4011
Четвертый цикл
1111010q40111
При дальнейшем переходе мы получим, что по команде q51Л, мы перейдем снова на 0, так как все единицы набора 1y кончились
111101q501111
и мы переходим командой q121Л на подпрограмму в состояние q12
11110q12111111
Остатки единиц от набора 1x оставляем командами q121Л, пока не доходим до 0.
1111q1200111111
Командой q130Л оставляем 0, и переходим влево в состояние q13
111q1310111111
Оставшиеся единицы нам не нужны поэтому стираем их командой q130Л, пока не встретится крайний 0 слева
q13000000111111
Команда q140П оставляет 0, как есть, переходит влево и в состояние q14
0q1400000111111
Снова такой же командой передвигаем указатель к началу нашего слова
000000q14111111
Так как в этом случае необходимо стереть лишь одну лишнюю единицу, то хватит команды q00П, которая ее сотрет и остановит программу
000000q011111
Как видим в нашем случае потребовалось 14 состояний что бы данная программа работала, как надо.

V.Показать примитивную рекурсивность функции f(x,y)
fx,y=5;3≤y≤8×1;иначе

Решение
Найдем значения функции fx,y. Для любых значений
y<3;y>8
fx,y=x=I12x,y
Для всех остальных значений 3≤y≤8
fx,y=5=SSSSSOx
Где I12x,y=x функция проектор
Ox=0 – нуль-функция
Sx=x+1 – функция следования
Все эти функции являются примитивно-рекурсивными
Следовательно, и их композиция, тоже является примитивно рекурсивной функцией, что мы и показали выше.

СилаУма 4.3

О себе - штатный преподаватель одного из ведущих вузов страны. Есть множество публикаций в журналах ВАК. Специализация - менеджмент, экономика и юриспруденция. Область научных интересов - экономические проблемы на макро и микроуровне.

Нанять автора