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

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

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

Так как q(0) = 1, то после элемента единичной задержки необходимо поставить элемент, реализующий отрицание. А для того, чтобыпри прохождении элемента единичной задержки не потерять значениеq(t), перед элементом единичной задержки также поставим элемент, реализующий отрицание:41I1,1IV.2.14(3). По схеме, реализующей функцию f из Pb2,од, построитьканонические уравнения, каноническую таблицу и диаграмму Мура:x(t)¬з¬з↓y(t)J Пусть верхний элемент задержки соответствует состоянию q1 , а нижний — q2 .Канонические уравнения данной функции имеют вид:y(t) = q1 (t − 1) ↓ q2 (t − 1),q (t) = x(t),1f:q2 (t) = q1 (t − 1),q1 (0) = q2 (0) = 0.Строим каноническую таблицу:42x(t) q1 (t − 1) q2 (t − 1) y(t) q1 (t) q2 (t)000010001010101110011011100000010001110101111001По канонической таблице восстанавливаем диаграмму Мура:1(1)11(0)20(0)1(0)0(1)0(0)*01(0)30(0)Заметим, что в ней состояния 0 и 1 эквивалентны, и их можно объединить:21(1)0(0)1(0)*1=01(0)0(1)30(0)I1,1IV.2.13(9).

Для функции f из P2,одпостроить схему над множеством,состоящим из элемента единичной задержки и функциональных элементов «дизъюнкция», «конъюнкция» и «отрицание». f задается диаграммой Мура:43010(1)1(0)0(0)1(0)0(0)*000(0)101(1)1(1)11J По заданной диаграмме Мура построим каноническую таблицу:x(t) q1 (t − 1) q2 (t − 1) y(t) q1 (t) q2 (t)000000001110010000011001100001101001110111111100По канонической таблице выпишем канонические уравнения. Для этогопостроим ДНФ для каждой из функций y(t), q1 (t), q2 (t) (для сокращениязаписи вместо x(t), q1 (t − 1), q2 (t − 1) будем писать x, q1 , q2 ).y(t) = x & q1 & q2 ∨ x & q1 = x ∨ q1 & q2 ∨ x & q1 ,q (t) = x & q & q ∨ x & q & q ,12121q2 (t) = x & q1 & q2 ∨ x & q1 ∨ x & q1 & q2 ,q1 (0) = q2 (0) = 0.Для упрощения восприятия схемы используем не только функциональные элементы «дизъюнкция», «конъюнкция» и «отрицание», но и сложение по модулю 2.Заметим, чтоq2 (t) = x & q1 & q2 ∨ x & q1 ∨ x & q1 & q2 == q1 & (x ⊕ q2 ) ∨ x & q1 .Строим схему:44x(t)¬¬&&&&з¬з&y(t)IЗанятие № 1.13Автоматы.

Часть 2IV.2.1(24). Построить диаграмму Мура, каноническую таблицу и ка1,1нонические уравнения для функции f (exω ) = y(1)y(2) . . . y(t) . . . из P2,од,5где y(t) есть t-я цифра после запятой в двоичном разложении числа 7 .J Для решения задачи необходимо, прежде всего, найти двоичное разложение числа 75 (например, поделив числа в столбик в двоичной системесчисления): 5101== (0, (101))2 .7 10111 2Очевидно, что в диаграмме будет 3 состояния, и функция будет автономной (то есть не зависящей от входных данных).*00(1), 1(1)0(1), 1(1)10(0), 1(0)2По диаграмме Мура восстанавливаем каноническую таблицу (доопределённые ячейки выделены):45x(t) q1 (t − 1) q2 (t − 1) y(t) q1 (t) q2 (t)000101001010101000011011100101010101110100111011Затем по канонической таблице выписываем канонические уравнения:y(t) = q̄2 (t − 1),q (t) = q (t − 1),12q2 (t) = q1 (t) ∼ q2 (t − 1),q1 (0) = q2 (0) = 0.

IIV.2.1(16). Построить диаграмму Мура, каноническую таблицу иfω ) = y(1)y(2) . . . y(t) . . . изканонические уравнения для функции f (x1,1P2,од, где(x(t),если t нечётное,y(t) =x(t) ⊕ y(t − 1), если t чётное.J Используя описанную в условии формулу, восстановим информационное дерево. Для нахождения веса функции хватит пяти ярусов. Изучивдерево, видим, что вес функции равен 3.46По информационному дереву строим диаграмму Мура:По диаграмме Мура выписываем каноническую таблицу, доопределяянеобходимые значения:x(t) q1 (t − 1) q2 (t − 1) y(t) q1 (t) q2 (t)000101001100010000011011100010101000110100111011Затем по канонической таблице восстанавливаем канонические уравнения.y(t) = x(t) & q1 (t − 1) ∨ x(t) & q1 (t − 1) & q2 (t − 1),q (t) = q (t − 1) & q (t − 1) ∨ x(t) & q (t − 1) & q (t − 1),11212q2 (t) = x(t) & q1 (t − 1) & q2 (t − 1) ∨ q1 (t − 1) & q2 (t − 1),q1 (0) = q2 (0) = 0. IIV.2.5(1).

Для частично определённой детерминированной функцииf (exω ) : {0, 1} → {0, 1}, отображающей заданные последовательности взаданные, построить диаграмму Мура с возможно меньшим числом вершин; затем полученную диаграмму доопределить до диаграммы Мура1,1,всюду определённой ограниченно-детерминированной функции из P2,оди для этой новой функции построить каноническую таблицу и канонические уравнения:f (0eω ) = [01]ωиf ([10]ω ) = e1ω .J Используя описанные в условии формулы, построим диаграммы Мура:47f (e0ω ) = [01]ω0(0)*010(1)f ([10]ω ) = e1ω1(1)*010(1)Объединяем диаграммы и доопределяем функции y(t) и q1 (t):0(0), 1(1)*010(1), 1(1)По диаграмме Мура восстановим каноническую таблицу:x(t) q1 (t − 1) y(t) q1 (t)0001011010111110Затем по канонической таблице выпишем канонические уравнения:y(t) = x(t) ∨ q1 (t − 1),q1 (t) = q̄1 (t − 1),q (0) = 0.

I1IV.2.5(2). Для частично определённой детерминированной функцииf (exω ) : {0, 1} → {0, 1}, отображающей заданные последовательности взаданные, построить диаграмму Мура с возможно меньшим числом вершин; затем полученную диаграмму доопределить до диаграммы Мура1,1всюду определённой ограниченнодетерминированной функции из P2,од,и для этой новой функции построить каноническую таблицу и канонические уравнения:f ([01]ω ) = e0ωиf (1[10]ω ) = [001]ω .J Используя описанные в условии формулы, построим диаграммы Мура:f ([01]ω ) = e0ω4810(0)1(0)*0f (1[10]ω ) = [001]ω ⇔ f (1[101010]ω ) = 0[010010]ωОбъединяем диаграммы:По диаграмме Мура выпишем каноническую таблицу (доопределённыеячейки выделены):49x(t) q1 (t − 1) q2 (t − 1) q3 (t − 1) y(t) q1 (t) q2 (t) q3 (t)00000001000100010100011000111100010000101010000001100000011100001000001010010000010001110111100111000010110100001110000011110000Теперь по канонической таблице построим канонические уравнения:y(t) = q̄1 · q2 · q3 ,q1 (t) = q̄1 · q2 · q3 ,q2 (t) = q̄1 · q2 · q̄3 ∨ q1 · q̄2 · q̄3 ∨ x · q̄1 · q̄2 · q̄3 ,q3 (t) = x̄ · q̄1 · q̄2 ∨ q̄1 · q2 · q̄3 ,q (0) = q (0) = q (0) = 0.I123IV.2.11(1).

Найти вес ограниченно-детерминированной функции, получающейся из ограниченно-детерминированной функции f с помощьюоперации отождествления входных переменных xi и xj :y(t) = x1 (t) → x2 (t) & q1 (t − 1),q (t) = x (t) → x̄ (t) & q̄ (t − 1),1232f:q2 (t) = x1 (t) & x̄2 (t) ∨ q̄1 (t − 1),q1 (0) = q2 (0) = 0.а) i = 1, j = 2;б) i = 2, j = 3.50Jа) i = 1, j = 2. В этом случае исходная функция переходит вследующую:y(t) = x1 (t) → q1 (t − 1),q (t) = x (t) → x̄ (t) & q̄ (t − 1),1132f:q2 (t) = q̄1 (t − 1),q1 (0) = q2 (0) = 0.В соответствующей диаграмме Мура будет 4 состояния, причемвсе они достижимы.Величина y(t) существенно зависит от x1 (t) и q1 (t − 1), а q1 (t) –от x1 (t), x3 (t) и q2 (t − 1). Отсюда вес функции равен 4.б) i = 2, j = 3. В этом случае исходная функция переходит в следующую:y(t) = x1 (t) → x2 (t) & q1 (t − 1),q (t) = x (t) → x̄ (t) & q̄ (t − 1) = x̄ (t),12222f:q2 (t) = x1 (t) & x̄2 (t) ∨ q̄1 (t − 1),q1 (0) = q2 (0) = 0.Из полученных канонических уравнений следует, что q2 (t − 1) невлияет на y(t) и q1 (t).

Строим новые канонические уравнения:y(t) = x1 (t) → x2 (t) & q1 (t − 1),f : q1 (t) = x̄2 (t),q (0) = 0.1q1 (t − 1) — существенная переменная для y(t), принимающая обазначения, поэтому вес функции равен 2.IIV.2.8(1). Для суперпозиции f = f1 (f2 ) ограниченно-детерминиро1,1ванных функций f1 и f2 из P2,одпостроить канонические уравнения иприведённую диаграмму Мура:y(t) = x1 (t) → q1 (t − 1),f1 : q1 (t) = x̄1 (t, )q (0) = 0.1y(t) = x2 (t) ∨ q2 (t − 1),f2 : q2 (t) = x2 (t) ↓ q̄2 (t − 1),q (0) = 0.251J Построим суперпозицию заданных двух функций:y(t) = (x2 (t) ∨ q2 (t − 1)) → q1 (t − 1),q (t) = x̄ (t) & q̄ (t − 1) = x̄ (t),1222f:q2 (t) = x̄2 (t) & q2 (t − 1) ≡ 0,q1 (0) = q2 (0) = 0.Преобразуем формулу:y(t) = (x2 (t) ∨ q2 (t − 1)) → q1 (t − 1) == x̄2 (t) & q̄2 (t − 1) ∨ q1 (t − 1) == x̄2 (t) ∨ q1 (t − 1).Канонические уравнения приобретают следующий вид:y(t) = x̄2 (t) ∨ q1 (t − 1),f : q1 (t) = x̄2 (t),q (0) = 0.1Строим каноническую таблицу:x2 q1 (t − 1) y(t) q1 (t)0011011100011110Диаграмма Мура:I52Часть 2.Курс «Дополнительные главыдискретной математики»Занятие № 2.1Элементарные функции многозначной логики.Представление функций в первой и второйформахIII.1.1(1– 5, 11).

Доказать справедливость следующих равенств:1) −(x̄) =∼ x;· y;2) x ⊃ y =∼ x −· (x −· y) = min (x, y);3) x −4) (x ⊃ y) ⊃ y = max (x, y);5) (x ⊃ y) + x̄ = min (x, y);11) ∼ (x̄ · ȳ) = (∼ x) · ȳ.J1. Преобразуем левую и правую части равенства, используя определения соответствующих функций:0 при x̄ = 0,0 при (x + 1) (mod k) = 0,−(x̄) ===k − x̄ при x̄ 6= 0k − x̄ при (x + 1) (mod k) 6= 00 при x = k − 1,=(k − 1) − x при x 6= k − 10 при x = k − 1,∼ x = (k − 1) − x =(k − 1) − x при x 6= k − 1В результате преобразований было получено одно и то же выражение — верность равенства доказана.0, если 0 6 x < y 6 k − 1,· y = k−1−x −· y = k−1−2. ∼ x −=x − y, если 0 6 y 6 x 6 k − 1k − 1, если 0 6 x < y 6 k − 1,== x ⊃ y, что и требоk − 1 − x + y, если 0 6 y 6 x 6 k − 1валось доказать.530, если 0 6 x < y 6 k − 1,· (x −· y) = x −·3.

x −=x − y, если 0 6 y 6 x 6 k − 1· 0, если 0 6 x < y 6 k − 1,x−==· (x − y), если 0 6 y 6 x 6 k − 1x−x, если 0 6 x < y 6 k − 1,= min (x, y), что и требовалось до=y, если 0 6 y 6 x 6 k − 1казать.(k − 1) ⊃ y, если 0 6 x < y 6 k − 1,·4. (x ⊃ y) ⊃ y = x −=(k − 1 − x + y) ⊃ y, если 0 6 y 6 x 6 k − 1(k − 1) − (k − 1) + y, если 0 6 x < y 6 k − 1,==(k − 1) − (k − 1 − x + y) + y, если 0 6 y 6 x 6 k − 1y, если 0 6 x < y 6 k − 1,== max(x, y), что и требовалось доx, если 0 6 y 6 x 6 k − 1казать.k − 1 + x̄, если 0 6 x < y 6 k − 1,5. (x ⊃ y) + x̄ ==k − 1 − x + y + x̄, если 0 6 y 6 x 6 k − 1k − 1 + x + 1, если 0 6 x < y 6 k − 1,==k − 1 − x + y + x + 1, если 0 6 y 6 x 6 k − 1x, если 0 6 x < y 6 k − 1,== min (x, y), что и требовалось доy, если 0 6 y 6 x 6 k − 1казать.11.

∼ (x̄ · ȳ) =∼ (x̄ · ȳ) + 1 = (k − 1) − x̄ · ȳ + 1 = k − (x + 1)(y + 1) =k − 1 − x · y − x − y.(∼ x) · ȳ = (k − 1 − x)(y + 1) = k · y + k − y − 1 − x · y − x =k − 1 − x · y − x − y.В результате преобразований правой и левой частей равенствапришли к одному и тому же выражению — верность равенствадоказана.IIII.1.2(13). Показать, что функция f из Pk порождается с помощьюоперации суперпозиции множеством функций A (A ⊂ Pk ), если· y}.f = Jk−2 (x), A = {k − 1, x + 2, x −J С помощью функций множества A получим J0 (x):· x) .

. . −· x) −· x.J0 (x) = (. . . ((k − 1) −{z}|k − 1 разИскомая f = Jk−2 (x) = J0 (x + 2).IIII.1.11(1, 10). Для заданного k представить функцию f в первой ивторой формах (полученные выражения упростить):541) f = x̄, k = 3;· y 2 , k = 3.10) f = x −J1. Представим f (x) в первой форме:f (x) = max (min (0̄, J0 (x)), min (1̄, J1 (x)), min (2̄, J2 (x))) == max (min (1, J0 (x)), min (2, J1 (x)), min (0, J2 (x))) == max (min (1, J0 (x)), J1 (x)).Представим f (x) во второй форме:f (x) = 0̄ · j0 (x) + 1̄ · j1 (x) + 2̄ · j2 (x) = j0 (x) + 2j1 (x).10. Построим таблицу значений функции f (x):@ y@0 1 2x @@00 0 011 0 022 1 1Представим f (x, y) в первой форме:f (x, y) = max(min (1, J1 (x), J0 (y)), min (J2 (x), J0 (y)),min (1, J2 (x), J1 (y)), min (1, J2 (x), J2 (y))).Представим f (x, y) во второй форме:f (x, y) = j1 (x) · j0 (y) + 2 · j2 (x) · j0 (y) + j2 (x) · j1 (y) + j2 (x) · j2 (y).

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

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