Комбинаторика и теория графов. Решение Введем обозначения для элементарных высказываний Захватить противника врасплох А

• Название: Решение Введем обозначения для элементарных высказываний Захватить противника врасплох А
• Анкор: Комбинаторика и теория графов
• Дата: 06.12.2021
• Размер: 119.59 Kb.
• Имя файла: Variant_2_11_zadaniy_393835.docx
• Тип: Решение; #294103
• страница: 2 из 3

4. Привести формулу логики предикатов сначала в ПНФ, затем в СНФ:

F = x(yP(y, α) ↔ Q(x))
Решение:

I. Приведем формулу к ПНФ.

1. Устраним логическую связку ↔, пользуясь равносильностью алгебры логики P(y) ↔ Q(x) = (P(y) → Q(x))&(Q(x) → P(y)):

F = x(yP(y, α) ↔ Q(x)) =

= x((yP(y, α) → Q(x))&(Q(x) → yP(y, α))).

2. Устраним логические связки →, пользуясь равносильностью алгебры логики P(y) → Q(x) = P(y)  Q(x):

F = x((yP(y, α) → Q(x))&(Q(x) → yP(y, α))) =

= x((yP(y, α)  Q(x))&(Q(x)  yP(y, α))) =

= x((yP(y, α)  Q(x))&(Q(x)  yP(y, α))).

3. Продвинем отрицание до элементарных формул, пользуясь правилом двойственности кванторов xQ(x) = xQ(x) и законами де Моргана:

F = x((yP(y, α)  Q(x))&(Q(x)  yP(y, α))) =

= x((yP(y, α)  Q(x))&(Q(x)  yP(y, α))) =

= x((yP(y, α)  Q(x))  (Q(x)  yP(y, α))) =

= x(yP(y, α)&Q(x)  Q(x)&yP(y, α)) =

= x(yP(y, α)&Q(x)  Q(x)&yP(y, α)) =

= x(yP(y, α)&Q(x)  Q(x)&yP(y, α)).

4. Произведем замену переменной y = w в крайнем левом вхождении:

F = x(yP(y, α)&Q(x)  Q(x)&yP(y, α)) =

= x(wP(w, α)&Q(x)  Q(x)&yP(y, α)).

5. Вынесем кванторы в префикс, не нарушая их последовательности:

F = x(wP(w, α)&Q(x)  Q(x)&yP(y, α)) =

= xwy(P(w, α)&Q(x)  Q(x)&P(y, α)).

6. Приведем формулу к КНФ:

F = xwy(P(w, α)&Q(x)  Q(x)&P(y, α)) =

= xwy((P(w, α)  Q(x)&P(y, α))&(Q(x)  Q(x)&P(y, α))) =

= xwy((P(w, α)  Q(x))&(P(w, α)  P(y, α))&(Q(x)  P(y, α))).

ПНФ формулы построена.
II. Приведем ПНФ формулы к СНФ, удалив квантор существования и заменив связанную им переменную на функциональный терм y = f(x, w), аргументами которого являются переменные x и w, так как квантору существования предшествуют два квантора всеобщности:

F = xwy((P(w, α)  Q(x))&(P(w, α)  P(y, α))&(Q(x)  P(y, α))) =

= xw((P(w, α)  Q(x))&(P(w, α)  P(f(x, w), α))&(Q(x)  P(f(x, w), α))).

СНФ формулы построена.

5. Машина Тьюринга имеет алфавит из трех символов {2,1,*} (символ * означает отсутствие символа на ленте), два состояния {q₀, q₂}, из которых q₀ – начальное состояние, q₂ – конечное. Символ R означает сдвиг читающей головки вправо по ленте, L – влево, E – головка остается на месте. В начальный момент головка указывает на крайний левый символ записи. Команды машины задаются набором:

q₀2 → q₀1R,

q₀1 → q₀2L,

q₀* → q₂2E.

Какой результат даст машина на наборе {22122}?
Решение:

Начальное состояние МТ имеет вид:

*

*

2

2

1

2

2

*

*

*

В начальный момент МТ обозревает крайний левый символ записи и находится в состоянии q₀:

*	*	2	2	1	2	2	*	*	*
		q0

Находим в программе команду с левой частью q₀2. Это команда q₀2 → q₀1R. Она означает, что в рассматриваемую ячейку записывается 1, головка сдвигается на одну ячейку вправо и устанавливается в состояние q₀. В результате применения этой команды имеем:

*	*	1	2	1	2	2	*	*	*
			q0

Снова обозревается символ 2 и МТ находится в состоянии q₀. В обозреваемую ячейку записывается 1, головка сдвигается на одну ячейку вправо и остается в состоянии q₀. Получим:

*	*	1	1	1	2	2	*	*	*
				q0

Теперь обозревается символ 1. Находим в программе команду с левой частью q₀1. Это команда q₀1 → q₀2L. Она означает, что в рассматриваемую ячейку записывается 2, головка сдвигается на одну ячейку влево и устанавливается в состояние q₀. В результате применения этой команды имеем:

*	*	1	1	2	2	2	*	*	*
			q0

Снова обозревается символ 1 и МТ находится в состоянии q₀. В обозреваемую ячейку записывается 2, головка сдвигается на одну ячейку влево и остается в состоянии q₀. Получим:

*	*	1	2	2	2	2	*	*	*
		q0

Снова обозревается символ 1 и МТ находится в состоянии q₀. В обозреваемую ячейку записывается 2, головка сдвигается на одну ячейку влево и остается в состоянии q₀. Получим:

*	*	2	2	2	2	2	*	*	*
	q0

Теперь обозревается символ *. Находим в программе команду с левой частью q₀*. Это команда q₀* → q₂2Е. Она означает, что в рассматриваемую ячейку записывается 2, головка остается на месте, и МТ переходит в состояние q₂. В результате применения этой команды имеем:

*	2	2	2	2	2	2	*	*	*
	q2

Состояние q₂ – заключительное, поэтому машина заканчивает работу.

Получено выходное слово {222222}.

6. Пусть A = {α, β}. Построить алгоритм Маркова, который приписывает символ β к концу слова.
Решение:

Чтобы приписать символ β к концу слова, сначала нужно отметить конец слова. Для этого введем в алфавит дополнительный знак *, который сначала находится перед словом, а затем перемещается к его концу. После этого символ * заменяется на символ β.

Перемещение символа * от начала к концу слова – это замена пары *α(*β) на пару α*(β*), которая реализуется простыми подстановками *α → α* и *β → β*.

Таким образом, получаем алгоритм Маркова, который приписывает символ β к концу слова:

*α → α*, *β → β*, * → •β, Λ → *.

7. Построить конечный автомат, распознающий язык L над алфавитом {a, b}, длина слов которого кратна трем.
Решение:

Обозначим состояния автомата следующим образом:

q₁ – начальное состояние

q₂ – «ошибочное» состояние (если автомат переходит в это состояние, значит, ему на вход подано «неправильное» слово)

q₃ – на первом шаге поступило a или b

q₄ – на втором шаге поступило a или b

q₅ – заключительное состояние.
Таблица переходов:

	a	b	-
q1	q3	q3	q2
q2	q2	q2	q2
q3	q4	q4	q2
q4	q5	q5	q2