Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 22
Текст из файла (страница 22)
1. Для заданной булевой функции находят ее оптимальную в смысле количества связок Ч, 8с, скобочную форму, т. е. форму, б 2.4. Полнота. Построгниг супгрпогиций булевых функций 115 представляющую собой композицию первичных термов х т = 1, 2, ..., и, операций Ч, Й, и скобок, вводимых в выражение булевой функции на основе использования закона дистрнбутивности. 2.
Выражают классические связки Ч, Й, в виде суперпозиции заданного базиса. 3. Подставляют результаты п. 2 в выражение, полученное в п. 1, отмечая штриховой линией стыки блоков, моделирующих Ч, Й, в заданном базисе. 4. Анализируя стыки, устраняют избыточность логической схемы, используя закон двойного отрицания. П р им е р 2 б. Синтезировать логичесвую схему, раавиауюшую булаву функцию Г 1 иа -Π— 10, 10 — 11, 0 — 101, у(~" хт' хю тм ь) ((О на 1 — 10- 1 — 001 Π— 100 в бааисе В = (-+, 0). 1. Поврывая таблицы рааличнй (табл. 2.18), найдем совращенную ДНФ полностью определенной булевой фунацни 7, единичная Мс н нулевая Мо области Таблица 2.18 догорай валючмот соатзггстваняо единичную и иулавую области заданной фунв- лни у, 7 Э / Фунвция у маиорнруст функцию у.
Совращенная ДНФ фунвцни 7 имеет следующий вяд: у(хы хт, ..., хь) ха Ч х1хь. Эта форма являахся и минимальной. 2. Выранаем свяавн ч, Ьс, чарва связан имвливатнвного бааиса: а = а -+ О, а ч Ь = а ч Ь = а -+ Ь = (а -+ 0) -+ Ь, а Ь =а ч Ь = а -+ Ь = а -+ (Ь -+ О) = (а -+ (Ь -+ О)) -+ О. Гл. 2. Машемашичгская логика 11б 3 2.5. Дифференцирование булевых функций 117 3. Выполнение и.
3 представим в виде графа, вершины которого взвешены символами -+, У, хн О (рис. 2.7,о). В денном бвансе закан двойного отрипз- 2Ц~ Г Рнс. 2.7 ник моиио изобразить так, пвк покваано нв рис. 2.7, б. Устранив избыточность, получаем логи сескую схему Я (рис. 2.7, е), катерок определяет суверпозицшо в нмплнкатпвном базисе рассматриваемой функции У, У(х1~ хт~ °, хз) = (хз + х1) + хз.
Описанный метод синтеаа монна с успехом применять прн проектировании простых схем. $2 б. Дифференцирование булевых функций Рассмотрим метод, позволяющий проектировать логические схемы и соответствуюшие им суперпозиции большей сложности— метод каскадов. Мепзод каскадов, основанный на разложении Шеннона У(х1, ..., хь, ха+1, ..., х„) = ь Ч орь х'1 У(о1, ат, ..
ч аь хьф1, ..., х„), Ч(а1 от,..ниь) 1=1 позволяет при наличии блоков исключения 1с переменных свести реализацию булевой функции от п переменных к реализации функции от и — 1с, 1с > 1, переменных. Размерность остаточных функций У(ог, от, ..., оы хьфг, ..., х„) в свою очередь можно понизить, исключая 1 переменных до тех пор, пока остаточные функции не примут простой вид и их реализация в заданном базисе не будет очевидной. Сложность остаточных функций зависит от порядка исключения переменных в заданной булевой функции У(хг, хт, ..., х„). Число всевозможных способов исключения переменных растет комбинаторно. Например, при использовании только блоков, исключаюших одну и ту же переменную на каждом ярусе, зто число равно и), но на каждом ярусе можно исключить не только одну и ту же переменную, но и различные переменные; далее, можно исключать на каждом шаге различное число переменных (одну, две, три и т.
д.). Выбор оптимального исключения переменных перебором всех способов исключения — трудоемкий процесс. Оптимальное исключение переменных ишут, используя эвристические критерии, один из которых основан на использовании понятия производной от булевой функции. Производная первого порядка дУУдхз от булевой функции У по переменной х; есть сумма по модулю 2 соответствуюших остаточных функций: дУ д, = Их» 2, ..., *; „1, ..., х„) е Х1 ти у (х1 хт, ° ° ., х; 1, О, ..., х„), (2.13) где У(хг, хт, .. н х; 1, 1, ..., х„) — единичная остаточная функция; У(х1, хт, ..., х1 1, О,..., х„) — нулевая остаточная функция; 9 — сумма по модулю 2.
Единичная остаточная функция получается в результате приравнивания переменной х; единице, нулевая — приравниванием х; нулю. Пример 2.7. Вычислим пронзводкую дУУдх1 от булевой функции У(х,, з)) = Ч(О, б, 7), где О, 4, 7 — десятичные эквиваленты двоичных наборов, на которых функция У равна 1: У(21г хз~ хз) = Л222 ч х122хз, Согласно определенны а а., — = (лзлз ч хзхз) 6 лзхлз = (лзлз ч хзхз) бслзлз ч (хзхз ч хзхз) й хзхз = = (Лзхз ЧхзхзКхз Чха) Ч (хз Ч ха)(хз Чхз) йдзхз = хзхз Производнвк первогопарплкв дУУдх1 от булевой фунвции У(х1, хз, ..., х„) определлег условии, при которых зтв функции нвменкет влечение при переклю сенин переменной х; (при иамененнн значения х; на противополоиное).
В рассмотренном примере функции У(х1, хз, хз) измеилет свое аначенне е нв Н(о -+ Л), а = О, 1, при иамеиенпи знвченна переменной х1, п1 -+ Н1 при условии, что конъюнкшзл хзхз прпнимвег внесение "истинно", т. е. хз —— зз хз = 1.
Смешанной производной д"~/(дх;1 дх;, ...дх;„) от булевой функции У по переменным х;„х;„..., х;„называется выражение вида а'у д у а'-у дх;, дх;,...дх;„, дх;„дх1, ~,дх11 дх;2...дх;з 1/ ' 2,5. Дифференцирование булевых функциа Гл. 2. Математическая логика 118 Смешанную производную 12-го порядка д"//(дх;1 дх;,...дх;„) вычисляют, применяя соотношение (2.13) 1с раз фиксацией переменных х;„х22,..., х;, (цорядок фиксации переменных не имеет значения); количество упорядочиваний равно Й! Производная 1с-го порядка дз//д(х;„хг„..., х; ) от булевой функции /(х1, х2 °, х„) ло переменным х;„х;„..., х;, определяет условия, при которых эта функция изменяет значение лри одновременном изменении значений переменных х;,, х;„..., х;„, Согласно Бохману производная гс-го порядка д" //д(хз„ х;„..., х;,) от булевой функции /(х1, х2, ..., х„) по переменнйм х;,, х;„..., х; равна сумме па модулю 2 всех производных первого порядка, вторых, третьих и гп, д., 1с-х смешанных производных при фиксации переменных х;„х;„..., хг„.
д'у д/ дг/ дз)' д"/ дх;дхудх, ''' дх; дх; ...дх;,' 1чзг газ 1ззз з~ г1 в~ — 21~ 22~ . 1 зь Пример 2.8. Определим условия переключения выходного канала У логической схемы, реалнауюшей булеву Функюпо у(хг, хг, хз) = хг хг ч ХЗУЗ, прн переключении каидото входного канала, первого и второго каналов одновременно и всех трех каналов хг, хг, хз олновременно. Имеем дУ ВУ вЂ” = хг Чхз, — = хгехгхз и х1(1 9 Уз) = хгхз, дх1 ' дхз ау — =Х1Х2ех! =Х1(хге1) =ХЗУ2.
дхз Условие дУ/дх1 = 1 является условием переклп1чения выходного канала У при переклю сенин входного канала Х11 при подаче на второй канал 1 или на третий О, при переклкненпи первого канала хг с е на У (е -+ У) выходной канал перевлючается с е на У (о -з У, в = О, 1). Выходной канал У переключается (о' -+ У) при переалкненни входного канала хг (е -+ У), если хг = хз ю 1, и У переключается (е -+ У), насда переклвнается хз (а -1 е) при хг = 1,хг = О, в = О, 1.
Далее находим дзУ д /дУ'1 = — ~ — ! =19Уз=хз, дх1 дхг дхз дхг агу ау ду агу = — 9 — 9 = (хз Ч Уз) 9 хгхз 9 хз = д(х1, х2) дх дх дхг дхг = (хгчуз)щхз(хгщ1) = (хзчУз)щлгхз ы (хгчхз) Йхгхзч( ъ ч Уз) ЙУгхз = = (хг ЧУз)(х1 ЧУз) ЧУгхз Йхгхз = Уз Ч хгхг ЧУЗУзхз м Уз Чхгхг Ч Угхг. Выходной канал У переключается при любом одновременном переключении вводных каналов хг, хг, когда хз = О, или независимо от состояния входного канала хз кри переключении хг н хг с 11 на 00 или с 00 на 11. Вычислим да У/д(хг, хз, хз): ау а /ау~ азу а /ау1 = — ~ — ) =х291=Уз, = Х11 дх дхз дхз дх1 дх2 дхз дхз дхг азу а / дгу дхгдхгдхз дхг ~дхгдх / а'у ау ау ау а*у дгу дгу д(х„х„х,) д., Щах, а, а.,д; а.,а, +а,ах.
+ Щ дзУ = (хз Ч хз) 9 хгхз 9 ХЗУЗ 9 хз 9 хг 9 х1 Щ 1 = дхг дхз дхз = (Х2 Ч Уз) Щ хз (х1 Щ 1) 9 хз (хг Щ 1) Щ У1 = (хг Ч Уз ) Щ У1 хз Щ У1 Уг Щ У1 (хг Ч хз) 9 Угхз Щ хг(У2 Щ 1) ю (х2 Ч Уз) 9Угхз 9 У1 (хз 9 1)— = ((ХЗЧУз) ЙхгхзЧхг Ч хз Й хгхз) Щхзхг = ((ХЗЧУз)(х1ЧУз)ЧУгхз Й Узхз) 9 9 Угхг = (Уз Ч хгхз Ч УЗУзхз) Щ Угхг = (хз Ч хгхг Ч Угхг) 9 хгхг = ю (Уз Ч хгхг Ч УЗУЗ) Йхгхг Ч (хз Ч хгхг Ч УЗУз) Йхгхг зз = (Уз Ч хгхг Ч хгхз)(хг Ч хг) Ч хз(хг Ч Уг)(хг Ч хг)Угхг = хгУз ч хгхг чУЗУЗ ч хзлг ч У1Х2хз го ХЗУЗУЗ Ч ХЗХЗУЗ Ч ХЗХЗХЗ Ч ХЗХЗУЗ Ч УЗХЗХЗ Ч УЗХЗХЗ. При переключении входного вектора 4 ез 3, 6 ез 1 и 7 зз 0 выходной канал у переключается. Критерий оптимального исключения переменных в методе каскадов заключается в исключении сначала переменных, при переключении которых булева функция переключается при максимальном числе условий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
