А.А. Вороненко, В.С. Федорова - Дискретная математика. Задачи и упражнения с решениями (1060726), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

1Рис. 2J6. Построим каноническую таблицу для функции f1 :x1 (t) q1 (t − 1) y1 (t) q1 (t)001001011001100174По таблице построим канонические уравнения: y1 (t) = x̄1 (t)q̄1 (t − 1),q1 (t) = x1 (t) ⊕ q1 (t − 1),f1 : q (0) = 0.1Подставим выражение для y2 (t) вместо x1 (t) и добавим уравнения для переменной состояния q2 (t) к полученной системе:y1 (t) = x2 (t) · q2 (t − 1) · q̄1 (t − 1), q1 (t) = (x̄2 (t) ∨ q̄2 (t − 1)) ⊕ q1 (t − 1),q2 (t) = x2 (t) → q̄2 (t − 1),f1 (f2 ) :q1 (0) = 0, q (0) = 1.2Каноническая таблица:x2 (t) q1 (t − 1) q2 (t − 1) y1 (t) q1 (t) q2 (t)000011001011010001011001100011101100100011111010Диаграмма Мура:Cостояния диаграммы не эквиваленты друг другу, поэтому онаявляется приведенной.7.

Построим канонические таблицы и уравнения для f1 и f2 :75x1 (t) q1 (t − 1) y1 (t) q1 (t)0000011101111111x2 (t) q2 (t − 1) y2 (t) q2 (t)0011010001111110 y1 (t) = x1 (t) ∨ q1 (t − 1),q1 (t) = x1 (t) ∨ q1 (t − 1),f1 : q (0) = 0.1 y2 (t) = x2 (t) ∨ q̄2 (t − 1),q2 (t) = q̄2 (t − 1),f2 : q (0) = 1.2f1 (f2 ) :y1 (t) = x2 (t) ∨ q1 (t − 1) ∨ q̄2 (t − 1), q1 (t) = x2 (t) ∨ q1 (t − 1) ∨ q̄2 (t − 1),q2 (t) = q̄2 (t − 1),q1 (0) = 0, q (0) = 1.2x2 (t) q1 (t − 1) q2 (t − 1) y1 (t) q1 (t) q2 (t)000111001000010111011110100111101110110111111110Теперь построим диаграмму Мура:76Состояния 00, 10 и 11 эквивалентны, поэтому склеим их и получимприведенную диаграмму:Следовательно, для описания функции f1 (f2 ) достаточно однойпеременной состояния q 0 (t).x2 (t) q 0 (t − 1) y2 (t) q 0 (t)00010111101111110 y1 (t) = x2 (t) ∨ q (t − 1),q 0 (t) = 1,f1 (f2 ) : 0q (0) = 0.

IIV.2.9(1, 4). Построить канонические уравнения и приведённую диаграмму Мура ограниченно-детерминированной функции, получающейсяиз функции f введением обратной связи по переменным xi , yj :y1 (t) = x1 (t) → q(t − 1), y2 (t) = x1 (t) · x2 (t) ⊕ q(t − 1),1) i = 2, j = 1, f :q(t) = x1 (t) ∨ x2 (t) · q̄(t − 1),q(0) = 0;77y1 (t) = x1 (t) · q(t − 1) ∨ x2 (t), y2 (t) = x2 (t),4) i = 1, j = 2, f :q(t) = (x1 (t) → x2 (t)) ∨ q(t − 1),q(0) = 0.J1.

y1 (t) зависит от x2 (t) с запаздыванием, поэтому введение обратной связи возможно. Заменим все вхождения x2 (t) на правуючасть уравнения y1 (t): y2 (t) = x1 (t) · (x1 (t) → q(t − 1)) ⊕ q(t − 1),q(t) = x1 (t) ∨ (x1 (t) → q(t − 1)) · q̄(t − 1), q(0) = 0.Упростим уравнения: y2 (t) = x̄1 (t) · q(t − 1),q(t) = x1 (t) ∨ q̄(t − 1), q(0) = 0.Построим каноническую таблицу:x1 (t) q(t − 1) y2 (t) q(t)0001011010011101Построим диаграмму Мура:Состояния диаграммы не эквивалентны, поэтому она является приведенной.4.

y2 (t) зависит от x1 (t) с запаздыванием, поэтому введение обратнойсвязи возможно. Заменим все вхождения x1 (t) на правую часть78уравнения y2 (t): y1 (t) = x2 (t) · q(t − 1) ∨ x2 (t),q(t) = (x2 (t) → x2 (t)) ∨ q(t − 1), q(0) = 0.Упростим уравнения: y1 (t) = x2 (t),q(t) = 1, q(0) = 0.y1 (t) не зависит от q(t − 1), поэтому уравнения переменных состояния можно отбросить: y1 (t) = x2 (t).Построим диаграмму Мура, являющуюся, очевидно, приведенной:IIV.2.10(2, 4).

Найдите вес ограниченно-детерминированной функции, получающейся из ограниченно-детерминированной функции f введением обратной связи по переменным xi , yj :y1 (t) = x1 (t) ↓ q(t − 1), y2 (t) = x2 (t) ∨ q(t − 1),2) f :q(t) = x1 (t) · x2 (t),q(0) = 0;а) i = 1, j = 2;б) i = 2, j = 1;79y1 (t) = x2 (t) → q1 (t − 1), y2 (t) = q2 (t − 1) → x1 (t),q1 (t) = q̄2 (t − 1),4) f :q2 (t) = q1 (t − 1), q (0) = q (0) = 0;12a) i = j = 1;б) i = j = 2.J2. а) y2 (t) зависит от x1 (t) с запаздыванием, поэтому введение обратной связи возможно. Заменим все вхождения x1 (t) на правуючасть уравнения y2 (t): y1 (t) = (x2 (t) ∨ q(t − 1)) ↓ q(t − 1),q(t) = (x2 (t) ∨ q(t − 1)) · x2 (t),f1 : q(0) = 0.Упростим уравнения: y1 (t) = x̄2 (t) · q̄(t − 1),q(t) = x2 (t),f1 : q(0) = 0.y1 (t) существенно зависит от q(t − 1).

Оба состояния достижимы,следовательно, r(f1 ) = 2.б) y1 (t) зависит от x2 (t) с запаздыванием, поэтому введение обратной связи возможно. Заменим все вхождения x2 (t) на правуючасть уравнения y1 (t): y2 (t) = (x1 (t) ↓ q(t − 1)) ∨ q(t − 1),q(t) = x1 (t) · (x1 (t) ↓ q(t − 1)),f2 : q(0) = 0.q(t) ≡ 0, поэтому y2 (t) = x̄1 (t) и r(f2 ) = 1.4.

а) y1 (t) зависит от x1 (t) с запаздыванием, поэтому возможно введение обратной связи. Заменим все вхождения x1 (t) на правуючасть уравнения y1 (t):y2 (t) = q2 (t − 1) → (x2 (t) → q1 (t − 1)), q1 (t) = q̄2 (t − 1),f1 :q2 (t) = q1 (t − 1),q1 (0) = q2 (t) = 0.80Упростим уравнения:y2 (t) = q̄2 (t − 1) ∨ x̄2 (t) ∨ q1 (t − 1), q1 (t) = q̄2 (t − 1),f1 :q2 (t) = q1 (t − 1),q1 (0) = q2 (t) = 0.Построим каноническую таблицу:x2 (t) q1 (t − 1) q2 (t − 1) y2 (t) q1 (t) q2 (t)000110001100101110011101100110101000101111111101Все четыре состояния достижимы. При x2 (t) = 1 состояние 01отличается от остальных. Вне зависимости от входа мы последовательно проходим состояния 00, 10, 11, 01.

Таким образом,r(f1 ) = 4.б) y2 (t) зависит от x2 (t) с запаздыванием, поэтому возможновведение обратной связи. Заменим все вхождения x2 (t) на правуючасть уравнения y2 (t):y1 (t) = (q2 (t − 1) → x1 (t)) → q1 (t − 1), q1 (t) = q̄2 (t − 1),f2 :q2 (t) = q1 (t − 1),q1 (0) = q2 (t) = 0.Упростим уравнения:y1 (t) = q2 (t − 1) · x̄1 (t) ∨ q1 (t − 1), q1 (t) = q̄2 (t − 1),f2 :q2 (t) = q1 (t − 1),q1 (0) = q2 (t) = 0.Построим каноническую таблицу:81x1 (t) q1 (t − 1) q2 (t − 1) y1 (t) q1 (t) q2 (t)000010001100101110011101100010010001110111111101Все состояния последовательно достижимы: 00, 10, 11, 01. Выходные функции совпадают лишь для 10 и 11, но из этих состояниймы попадаем в неэквивалентные.

Поэтому r(f2 ) = 4.IЗанятие № 2.8Реализация ограниченно-детерминированныхфункций схемами. Полнота в множествахограниченно-детерминированных функцийIV.2.13(3, 5). Для функции f из P2,од построить схему над множеством, состоящим из элемента единичной задержки и функций, порождённых дизъюнкцией, конъюнкцией и отрицанием:3.

q(0) = 1 и функция f задаётся канонической таблицей:x(t) q(t − 1) y(t) q(t)00010101100111105. Функция f задаётся диаграммой Мура, изображённой на рисунке:82J3. Построим канонические уравнения: y(t) = x(t) · q(t − 1),f:q(t) = x̄(t) ∨ q̄(t − 1), q(0) = 1.Заметим, что q(0) = 1, а выходной символ элемента единичнойзадержки — 0. Решим эту проблему следующим способом. Произведём замену: q 0 (t) = q̄(t). Тогда получаем:0 y(t) = x(t) · q̄ (t − 1),q¯0 (t) = x̄(t) ∨ q 0 (t − 1),f: 0q (0) = 0.Упростим:0 y(t) = x(t) · q̄ (t − 1),q 0 (t) = x(t) · q̄ 0 (t − 1),f: 0q (0) = 0.По полученным уравнениям строим схему:5.

По диаграмме Мура построим каноническую таблицу и уравнения:83x(t) q(t − 1) y(t) q(t)0011010000111101 y(t) = x̄(t) · q̄(t − 1) = x(t) ∨ q(t − 1),f:q(t) = x(t) ∨ q̄(t − 1),q(0) = 0.Схема:IIV.2.14(1, 4). По схеме, реализующей функцию f из Pb2,од , построитьканонические уравнения, каноническую таблицу и диаграмму Мура:1) схема изображена на рис. 1;4) схема изображена на рис. 2.84J1. Выпишем систему канонических уравнений: y(t) = q(t − 1) · x(t),q(t) = x̄(t),f: q(0) = 0.Каноническая таблица:x(t) q(t − 1) y(t) q(t)0001101000011110Диаграмма Мура:854. Выпишем систему канонических уравнений и упростим её: y(t) = x(t) · q(t − 1),q(t) = x(t),f: q(0) = 0.Каноническая таблица:x(t) q(t − 1) y(t) q(t)0000010010011111Диаграмма Мура:IIV.2.17(1, 4). Доказать полноту системы {f1 , f2 } в Pb2,од относительносовокупности операций {O1 , O2 , O3 , O4 , S}, если:1) f1 :y(t) = x̄1 (t) · x̄2 (t), t > 1, y(t) = x1 (t) · x̄2 (t) ∨ q(t − 1),q(t) = x1 (t) ∨ x2 (t),f2 : q(0) = 0;4) f1 :y(t) = x̄1 (t), t > 1, y(t) = x1 (t) · x2 (t) ∨ x3 (t) · q(t − 1),q(t) = x2 (t) · x3 (t),f2 : q(0) = 0.J1.

f1 образует полную в P2 (t) систему.86В f2 положим x1 (t) = 0 (константа получается из f1 ). Тогдаполучаем элемент единичной задержки: y(t) = q(t − 1),q(t) = x2 (t), q(0) = 0.Следовательно, система {f1 , f2 } полна в Pb2,од .4. Заменим x3 (t) на x̄2 (t) в функции f2 . Получимf3 : y(t) = x1 (t) · x2 (t).Система {f1 , f3 } полна в P2 (t).Построим элемент единичной задержки.

Получив константы, подставим x3 (t) = 1, x1 (t) = 0: y(t) = q(t − 1),q(t) = x2 (t), q(0) = 0.Следовательно, система {f1 , f2 } полна в Pb2,од .IЗанятие № 2.9Простейшие свойства машин ТьюрингаV.1.2(1– 4). Построить в алфавите {0, 1} машину Тьюринга, обладающую следующими свойствами (предполагается, что в начальный момент головка обозревает самый левый символ слова, и в качестве пустогосимвола берётся 0):1) машина имеет одно состояние, одну команду и применима к любому слову в алфавите {0, 1};2) машина имеет две команды, не применима ни к какому слову валфавите {0, 1}, и зона работы на каждом слове бесконечная;3) машина имеет две команды, не применима ни к какому слову валфавите {0, 1}, и зона работы на любом слове ограничена одними тем же числом ячеек, не зависящим от выбранного слова;4) машина имеет три команды, применима к словам 102n 1 (n > 1) ине применима к словам 102n+1 1 (n > 0).87J1.

Программа одной из таких машин: q1 0q1 1S. МТ просматриваеттекущую ячейку: если 1, то переходит в заключительное состояние, если 0, то записывает 1, не сдвигается и делает останов.2. Программа одной из таких машин: q1 0q1 0R, q1 1q1 1R.

МТ просматривает текущую ячейку и сдвигается вправо.3. Программа одной из таких машин: q1 0q1 1S, q1 1q1 0S. МТ просматривает текущую ячейку и меняет её содержимое на противоположное, не сдвигаясь.4. Программа одной из таких машин: q1 1q2 1R, q1 0q2 0R, q2 0q1 0R.

Характеристики

Список файлов книги