bulevy-funktsii-i-postr.-log.-skhem (Методические документы), страница 11

Отрицание построено.Реализация функции x на логическом элементе f  x, y, z показана на рис. 16.3.х 1 0« »Рис. 16.3. Реализацияна ЛЭ.Из полинома Жегалкина строим вспомогательную функциювида xy  bx  cy  d , где b, c, d 0,1 . Например, можно сделатьтак:f 1, y, x   1 x  xy  1  y  xy  x  y  1 .В этом случае b  1, c  1 , d  1.Введём функцию h  x, y  :h  x, y   f 1, y  b, x  c   bc  d  f 1, y , x   f 1, f  0,1, y  , f  0,1, x   .Получили, что h  x, y   f 1, f  0,1, y  , f  0,1, x   .

Найдём её значения на всех наборах:h  0,0   f 1, f 1,0,1 , f 1,0,1   f 1,1,1  0 ;86h  0,1  f 1, f  0,1,1 , f  0,1,0    f 1,0,1  0 ;h 1,0   f 1, f  0,1,0  , f  0,1,1   f 1,1,0   0 ;h 1,1  f 1, f  0,1,1 , f  0,1,1   f 1,0,0   1 .Составим таблицу функции h  x, y  :x0 0 1 1y0 1 0 1h  x, y  0 0 0 1Таблица функции h  x, y  совпадает с таблицей конъюнкции,следовательно, h  x, y   x  y .Так как h  x, y   x  y и h  x, y   f 1, f  0,1, y  , f  0,1, x   , тоx  y  f 1, f  0,1, y  , f  0,1, x   . Конъюнкция построена.Реализация конъюнкции x  y на логическом элементеf  x, y, z  показана на рис. 16.4.у х 1 0f« »ff«»« »Рис. 16.4.

Реализация конъюнкцииэлементе.87на логическом17. Теорема о максимальном числе булевыхфункций в базисеОпределение 17.1. Система булевых функций A  P2 называется базисом (в P2 ), если1)  A  P2 ; 2) f  A  A \  f   P2 .Теорема 17.1. Максимальное число булевых функций в базисе равно четырём.Доказательство.1) Докажем, что из любой полной системы можно выделитьполную подсистему, содержащую не более четырёх функций.Действительно, если A - полная система (  A  P2 ), то согласнотеоремеПоставнейсуществуютпятьфункцийf0  T0 , f1  T1, f S  S , f M  M , f L  L . По теореме Поста системафункций  f0 , f1, f S , f M , f L  полна.

Рассмотрим функциюf0  x1,..., xn   T0 , тогда f0  0,0,...,0   1. Возможны два случая:a) f0 1,1,...,1  1 ⇒ f0  S ⇒  f0 , f1, f M , f L   P2 и система f0 , f1, f M , f L  полна;b) f0 1,1,...,1  0 ⇒ f0  M , f0  T1 ⇒  f0 , f S , f L   P2 и система f0 , f S , f L  полна.2) Покажем, что существует базис из четырёх функций. Действительно, рассмотрим систему функций 0, 1, xy, x  y  z .Эта система функций полная, так как 0  T1 , 0  S , 1  T0 , xy  L ,x  y  z  M . Однако, любая её подсистема не полна:0, 1, xy  M ;0, 1, x  y  z  L ;0, xy, x  y  z  T0 ;1, xy, x  y  z  T1 .Теорема доказана.

□С технической точки зрения выбор базиса эквивалентен выбору типов логических элементов, на которых может быть по88строена логическая схема, реализующая произвольную булевуфункцию.Наиболее широкое распространение получили следующиечетыре базиса:• B1  , ,  – (И, ИЛИ, НЕ) - булев базис;• B2  , ,1 – (И, М2, 1) - базис Жегалкина;| – (ИЛИ-НЕ), (И-НЕ) - универсальные ба• B3   , B4  зисы.Это перечисление показывает, что базисы могут быть избыточными (базис B1 ) и минимальными (базисы B3 и B4 ).Базис минимальный, если удаление хотя бы одной функциипревращает систему булевых функций в неполную систему.17.1.

Примеры построение логических схем булевыхфункций в различных базисахzу x111&&2 ярус1 Рис.13 ярусРис. 17.1.1. Логическая схема, реализующая ДНФ функции89Булев базис B1  , ,  позволяет реализовать любую булеву функцию, аналитическое выражение которой записано в виде ДНФ или КНФ.В качестве примера построим логические схемы для булевойфункции, ДНФ и КНФ которой имеют вид: f  xy  x y  z иf   x  y  z   x  y  z .Логическая схема для ДНФ функции f показана на рис.17.1.1, для КНФ - на рис.17.1.2.Для схемы на рис.17.1.1 цена по Квайну SQ=10, задержкаT=3.zу x1111&12 ярус1 ярус3 ярусРис. 17.1.2. Логическая схема, реализующая КНФ функции.Для схемы на рис.17.1.2 цена по Квайну SQ=11, задержкасхемы T=3.90Сравнивая две полученные логические схемы, можно заметить, что в этом случае затраты на построение того или иного варианта схем практически одинаковы.Булев базис является избыточной системой, так как возможно удаление из него некоторых функций.

Например, используязаконы де Моргана, можно удалить либо конъюнкцию, заменивеё дизъюнкцией и отрицанием, либо дизъюнкцию, заменив еёконъюнкцией и отрицанием.В таблице 17.1.1 показан переход от базиса B1  , ,  к| , приведены логичеуниверсальным базисам B3   и B4  ские схемы реализации функций булева базиса на логическихэлементах «ИЛИ-НЕ» и «И-НЕ».Таблица 17.1.1Формулы преобразованияЛогические схемы реализациифункций базиса B1 к универфункций базиса B1 на элеменсальному базису B4тах И-НЕx  x x  x| xx y  xy  x | y   x | x |  y | yx  y  x  y   x | y   x | y |  x | yФормулы преобразованияфункций базиса B1 к универсальному базису B3Логические схемы реализациифункций базиса B1 на элементах ИЛИ-НЕx  x x  x x91x  y  x  y  x  y   x  y   x  yx y  x  y  x  y   x  x   y  yПри преобразовании формул ДНФ и КНФ булевой функции ксоответствующему универсальному базису используются дватехнических приёма: двойное инвертирование исходного выражения или его части и применение правил Де-Моргана.

Проиллюстрируем сказанное примерами.zу x&&&&&2 ярус1 ярус3 ярусРис. 17.1.3. Логическая схема, реализующая функциюв базисе.Согласно сформулированным выше приёмам, ДНФ рассмот| примет вид:ренной ранее функции f в базисе B4  92f  xy  x y  z  xy  x y  z  xy  x y  z  xy | x y | z   x | y  |  x | y  | z   x | y  |  x | x  |  y | y  | zДля компактности записи используется прежнее представление инверсии, при этом имеется в виду, что x  x  x  x | x . Ком| примет видпактная формула функции f в базисе B4  f   x | y  |  x | y  | z . Логическая схема, реализующая функцию fв базисе B4 , показана на рис. 17.1.3. Цена этой ЛС по КвайнуSQ=11, задержка T=3.zу x1111112 ярус1 ярус3 ярусРис. 17.1.4.

Логическая схема, реализующая функциюв базисе.Согласно сформулированным выше приёмам, КНФ функцииf в базисе B3   примет вид:f  x  y  z x  y  z   x  y  z x  y  z  93 x  y  z  x  y  z   x  y  z   x  y  z   x  y  z   x  y  z    x  x   y   z  z  x   y  y   z  z Аналогично для компактности записи используется прежнеепредставление инверсии, где x  x  x  x  x . Компактная формулафункциивбазисеимеетвидB3  ff   x  y  z    x  y  z  .

Логическая схема, реализующаяфункцию f в базисе B3 , показана на рис. 17.1.4. Цена этой ЛС поКвайну SQ=14, задержка T=3.18. Минимизация булевых функций18.1 Общие принципы минимизацииСДНФ (СКНФ) является исходной формой представлениябулевой функции при построении логических схем. Однако схемы, построенные непосредственно по СДНФ (СКНФ), громоздкии содержат излишне много элементов. После преобразованияСДНФ (СКНФ) к минимальному виду заданная функция реализуется более простой схемой (с меньшим числом логических элементов).

Например, для реализации в булевом базисе функцииf  x1, x2 , x3  , заданной СДНФf  x1, x2 , x3   x1x2 x3  x1x2 x3  x1x2 x3  x1x2 x3  x1x2 x3 ,понадобится девять логических элементов: 5 вентилей «3И»,один вентиль «5ИЛИ» и три инвертора. Если упростить даннуюформулу путём добавления конъюнкции x1 x2 x3 и вынесения заскобки общих элементов,f  x1, x2 , x3   x1x2 x3  x1x2 x3  x1x2 x3  x1x2 x3  x1x2 x3  x1x2 x3   x1x2 x3  x1x2 x3    x1x2 x3  x1x2 x3    x1x2 x3  x1x2 x3   x1x3  x2  x2   x1x3  x2  x2   x1x2  x3  x3   x1x3  x1x3  x1x2  x3  x1  x1   x1x2  x3  x1x2 ,94то получим новое представление булевой функцииf  x1, x2 , x3   x3  x1x2 .Очевидно, что оно проще для реализации в булевом базисе, таккак потребует только два элемента: один вентиль «2И» и одинвентиль «2ИЛИ».Таким образом, возникает задача наиболее простого представления булевых функций, известная как задача минимизациибулевых функций.

Сводится она к выбору рационального базиса инаиболее экономного представления функции в этом базисе.В дальнейшем задачу минимизации будем рассматривать какзадачу нахождения минимальной дизъюнктивной нормальнойформы булевой функции.18.2. Представление элементарных конъюнкций в формализованном виде.

Операция склеиванияНа множестве булевых переменных x1, x2 ,..., xn элементарнойmконъюнкции К  xi1  xi 2  ...  xi12mпоставим в соответствие n -мерный троичный вектор степеней   1, 2 ,..., n  по следующему правилу:, если переменная x j не входит в K , j  1, если x j входит в K ,0, если x j входит в K .Например, элементарной конъюнкции K  x2 x3 x5 на множестве переменных x1 , x2 , x3 , x4 , x5 соответствует 5-ти мерныйтроичный вектор степеней    01  0  .Соответствие между множеством элементарных конъюнкций, зависящих от переменных x1, x2 ,..., xn , и множеством пмерных троичных векторов степеней взаимнооднозначно, так кактроичному вектору степеней, состоящему из одних «прочерков»   , ,...,   , соответствует «пустая» конъюнкция.95Если вместо элементарной конъюнкции записать её троичный вектор степеней, то говорят, что элементарная конъюнкцияпредставлена в формализованном виде.Будем рассматривать троичные векторы степеней с равнымчислом компонент и соответствующие им элементарные конъюнкции.Отношение равенства троичных векторов степеней определяется как равенство одноимённых компонент.Отношение соседства по i -ой компоненте означает отличиетроичных векторов степеней только по i -ой компоненте, т.е.

i -якомпонента принимает значение 0 в одном из векторов и значение 1 – в другом, при этом значения остальных компонент попарно равны.Пусть соседним троичным векторам степеней1  1, 2 ,..., i 1,0, i 1,..., n1, n  , 2  1, 2 ,..., i 1,1, i 1,..., n1, n соответствуют элементарные конъюнкцииК1  x11  x2 2  ...  xi i11  xk  xi i11  ...  xn n ,К 2  x11  x2 2  ...