Комбинаторика и теория графов. Решение Введем обозначения для элементарных высказываний Захватить противника врасплох А
![]()
|
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) = xQ(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, α))) = = 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, α)). 4. Произведем замену переменной y = w в крайнем левом вхождении: F = x(yP(y, α)&Q(x) Q(x)&yP(y, α)) = = x(wP(w, α)&Q(x) Q(x)&yP(y, α)). 5. Вынесем кванторы в префикс, не нарушая их последовательности: F = x(wP(w, α)&Q(x) Q(x)&yP(y, α)) = = xwy(P(w, α)&Q(x) Q(x)&P(y, α)). 6. Приведем формулу к КНФ: F = xwy(P(w, α)&Q(x) Q(x)&P(y, α)) = = xwy((P(w, α) Q(x)&P(y, α))&(Q(x) Q(x)&P(y, α))) = = xwy((P(w, α) Q(x))&(P(w, α) P(y, α))&(Q(x) P(y, α))). ПНФ формулы построена. II. Приведем ПНФ формулы к СНФ, удалив квантор существования и заменив связанную им переменную на функциональный терм y = f(x, w), аргументами которого являются переменные x и w, так как квантору существования предшествуют два квантора всеобщности: F = xwy((P(w, α) Q(x))&(P(w, α) P(y, α))&(Q(x) P(y, α))) = = xw((P(w, α) Q(x))&(P(w, α) P(f(x, w), α))&(Q(x) P(f(x, w), α))). СНФ формулы построена. 5. Машина Тьюринга имеет алфавит из трех символов {2,1,*} (символ * означает отсутствие символа на ленте), два состояния {q0, q2}, из которых q0 – начальное состояние, q2 – конечное. Символ R означает сдвиг читающей головки вправо по ленте, L – влево, E – головка остается на месте. В начальный момент головка указывает на крайний левый символ записи. Команды машины задаются набором: q02 → q01R, q01 → q02L, q0* → q22E. Какой результат даст машина на наборе {22122}? Решение: Начальное состояние МТ имеет вид:
В начальный момент МТ обозревает крайний левый символ записи и находится в состоянии q0:
Находим в программе команду с левой частью q02. Это команда q02 → q01R. Она означает, что в рассматриваемую ячейку записывается 1, головка сдвигается на одну ячейку вправо и устанавливается в состояние q0. В результате применения этой команды имеем:
Снова обозревается символ 2 и МТ находится в состоянии q0. В обозреваемую ячейку записывается 1, головка сдвигается на одну ячейку вправо и остается в состоянии q0. Получим:
Теперь обозревается символ 1. Находим в программе команду с левой частью q01. Это команда q01 → q02L. Она означает, что в рассматриваемую ячейку записывается 2, головка сдвигается на одну ячейку влево и устанавливается в состояние q0. В результате применения этой команды имеем:
Снова обозревается символ 1 и МТ находится в состоянии q0. В обозреваемую ячейку записывается 2, головка сдвигается на одну ячейку влево и остается в состоянии q0. Получим:
Снова обозревается символ 1 и МТ находится в состоянии q0. В обозреваемую ячейку записывается 2, головка сдвигается на одну ячейку влево и остается в состоянии q0. Получим:
Теперь обозревается символ *. Находим в программе команду с левой частью q0*. Это команда q0* → q22Е. Она означает, что в рассматриваемую ячейку записывается 2, головка остается на месте, и МТ переходит в состояние q2. В результате применения этой команды имеем:
Состояние q2 – заключительное, поэтому машина заканчивает работу. Получено выходное слово {222222}. 6. Пусть A = {α, β}. Построить алгоритм Маркова, который приписывает символ β к концу слова. Решение: Чтобы приписать символ β к концу слова, сначала нужно отметить конец слова. Для этого введем в алфавит дополнительный знак *, который сначала находится перед словом, а затем перемещается к его концу. После этого символ * заменяется на символ β. Перемещение символа * от начала к концу слова – это замена пары *α(*β) на пару α*(β*), которая реализуется простыми подстановками *α → α* и *β → β*. Таким образом, получаем алгоритм Маркова, который приписывает символ β к концу слова: *α → α*, *β → β*, * → •β, Λ → *. 7. Построить конечный автомат, распознающий язык L над алфавитом {a, b}, длина слов которого кратна трем. Решение: Обозначим состояния автомата следующим образом: q1 – начальное состояние q2 – «ошибочное» состояние (если автомат переходит в это состояние, значит, ему на вход подано «неправильное» слово) q3 – на первом шаге поступило a или b q4 – на втором шаге поступило a или b q5 – заключительное состояние. Таблица переходов:
|