2001-0084-0-01 (Лабы), страница 2

4).01110СДНФ этой функции представляет собой10001шесть конъюнкций ранга 3, объединенные10110знаками дизъюнкции, т. е. достаточно гро11010моздкое выражение. В то же время СКНФ11110этой функции будет выглядеть так:7F = (x1 ∨ x2 ∨ x3 ) ( x1 ∨ x2 ∨ x3).(2)В выражении (2) имеются две дизьюнкции, объединенные знакомконъюнкции.1.4. Элементарные преобразования булевых выраженийЧасто преобразование булевых выражений выполняется с целью упрощения последних или, как говорят, с целью их минимизации. Легкообосновываются следующие правила минимизации:– поглощения: x ∨ xy = x; x(x ∨ y) = x;– склеивания: xy ∨ x y = x;– обобщенного склеивания: xz ∨ y z ∨ xy = xz ∨ y z;– x ∨ x y = x ∨ y.Покажем, как можно применить правило склеивания для минимизации мажоритарной функции.

Аналитическое выражение перепишем вследующем виде:(3)F = x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3.Повторение конъюнкции x1x2x3 не меняет значение функции, так какY ∨ Y = Y, где Y – любое булево выражение. Тогда, склеивая 1-й и 4-йчлены, 2-й и 5-й, 3-й и 6-й, получаем эквивалентное выражение(4)F = x2 x3 ∨ x1 x3 ∨ x1 x2.Выражение (4) будет дизъюнктивной, нормальной формой функции, таккак в каждую из конъюнкций входят не все аргументы функции.Преобразование булевых выражений с помощью приведенных правил поглощения, склеивания и обобщенного склеивания применяетсядостаточно редко, так как имеется более эффективный способ минимизации булевых функций, число аргументов которых не превышает 11.Кроме того, так же просто обосновывается преобразование, называемое правилом де Моргана:а) x1 x2 = x1 ∨ x2 ;(5)б) x1 ∨ x2 = x1 x2 .Покажем, как применить правило де Моргана для вывода формулыСКНФ.

В табл. 4 имеется значение функции, инверсной к F, т. е. F . Этафункция имеет только две единицы, поэтому СДНФ ее будет представлятьсобой две конъюнкции, каждая ранга 3, объединенные знаком дизъюнкции:8(6)F = x1 x2 x3 ∨ x1 x2 x3 .Проинвертируем левую и правую части выражения (6) и применим кправой части правило де Моргана, тогда получимF = (x1∨ x2 ∨ x3 ) ( x1 ∨ x2 ∨ x3) .В результате получена формула СКНФ функции F.1.5. Минимизация булевых функций с помощьюдиаграмм Вейча (карт Карно)Диаграммы Вейча представляет собой ту же таблицу истинностибулевой функции, только в более компактной форме.

Так, для функциитрех аргументов, которая задается на восьми наборах, таблица истинности будет содержать восемь клеток, причем каждая клетка в диаграмме Вейча соответствует некоторому набору в таблице истинности.Области в диаграмме Вейча обозначим следующим образом: подчеркнутые столбцы или строки будут соответствовать истинному значению аргумента, а не подчеркнутые – ложному. Тогда диаграмма Вейча мажоритарной функции примет видx21x31x111Из полученной диаграммы Вейча легко выписывается минимальноевыражение для мажоритарной функцииF = x2 x3 ∨ x1 x3 ∨ x1 x2.Возьмем некоторую функцию F четырех аргументов, диаграммаВейча которой имеет видBA111DC119Эта функция принимает значение 1 на пяти наборах, отмеченных надиаграмме единицами. На остальных наборах функция принимает значение 0.

СДНФ этой функции содержала бы пять конъюнкций каждаяранга 4, объединенные знаками дизъюнкций. Однако из диаграммы Вейчалегко выписывается минимальное выражение функции в дизъюнктивной нормальной формеF = AC ∨ B C D .Области в диаграмме Вейча обозначаются так, чтобы две соседниеклетки соответствовали бы “склеивающимся” конъюнкциям (т.

е. конъюнкциям, отличающимся значением только одного аргумента). Так,например:A B C D ∨ A B C D = AC D .Это обеспечивает наглядность минимизации.В общем случае области в диаграммах Вейча для функций большого числа аргументов обозначаются кодом Грэя.Таблица 5Особенностью этого кода является то, что две00000000соседние комбинации отличаются значением только одного аргумента.

Обычный двоичный код это00010001му условию не удовлетворяет.00100011Код Грэя используется в цифровых кодовых дат00110010чиках, что позволяет сделать ошибку равномерной при смещениях токосъемников, при этом ошиб01000110ка равна 2-m где m – число двоичных разрядов ко01010111дового датчика.

Это свойство кода Грэя исполь01100101зуется для обозначения областей в диаграммах01110100Вейча.В табл. 5 приведен код Грэя для четырех аргу10001100ментов (разрядов). Если требуется построить код10011101Грэя на меньшее число разрядов, то его легко по10101111лучить из имеющейся таблицы путем “вырезания” соответствующей части. Так, в приведенной10111110таблице показано, как получить двухразрядный код11001010Грэя.

Если требуется построить код Грэя на пять11011011разрядов, то код в таблице следует зеркально от11101001разить вниз и добавить еще один разряд, причем впервой половине в этом разряде будут стоять нули,1111100010а во второй – единицы. Аналогично строятся коды Грэя на любое числоразрядов.П р и м е р . Минимизировать функцию семи аргументов, заданнуюдиаграммой Вейча:DCBA11G1111111111111111FE11Минимальное выражение в дизъюнктивной нормальной форме имеет видF = AC E F ∨ A E F G ∨ A B C E F .Примеры для практических занятий.1.

Доказать с помощью диаграмм Вейча равенства, которые использовались для минимизации (поглощения и склеивания, а также правилоде Моргана).2. Построить диаграммы Вейча для следующих функций и выписатьминимальные выражения в дизъюнктивной нормальной форме:а)  abcd ∨  abcd ∨  abcd ∨  abcd ∨  abcd ∨  abcd = ;б) abc ∨ ab c ∨  abd ∨  bde =.1.6. Минимизация частично определенных булевых функцийДиаграммы Вейча могут использоваться для минимизации нетолько так называемых полностью определенных логических функций (когда функция в таблице истинности принимает только два значения: 0 или 1), но и для случая частичных (не полностью опреде11ленных) функций. При построении реальных цифровых устройств контроля и управления комбинационные схемы описываются, как правило, не полностью определенными булевыми функциями.

Оченьчасто функции не определены на большом числе наборов. В таблицеистинности и, следовательно, в диаграммах Вейча такие функциикроме 0 и 1 будут содержать еще и “–”; это означает, что такой набор никогда на вход устройства не поступает. Следовательно, поведение комбинационной схемы при таком наборе не имеет значения, ина месте “–” может быть произвольно поставлена либо 1, либо 0.Этот процесс называется доопределением булевой функции.

Доопределение булевой функции желательно выполнять так, чтобы получить возможно более простое выражение. В этом случае, как правило, реализованная комбинационная схема также оказывается болеепростой.Пусть задана диаграмма Вейча некоторой не полностью определенной функции:BA1D––C––11––1Приведенная функция имеет прочерки в шести клетках, в каждой изкоторых может быть поставлена как 1, так и 0. Следовательно, существует 26 = 64 различных способов доопределения булевой функции.Однако из диаграммы легко выбрать наилучший, который дает следующий результат минимизации:F = AC ∨ B D .Примеры для практических занятий.Доопределить функцию и выисать минимальное выражение из диаграмм Вейча:12а)б)cBbA1––DC1111––111–e––1–d––11a––1–в)c–11e1–1db–a1––––––1.7.

Проверка равенств в булевой алгебреДля того чтобы доказать равенство двух функций в булевой алгебре,например, F(x1, x2, …, xn) = P(x1, x2, …, xn), необходимо и достаточнопоказать, что на всех наборах аргументов x1, x2, …, xn левая часть равенства совпадает с правой.Например:(AB ↓ BC) → BD = ( B ∨ AC D) .Для доказательства этого равенства построим диаграммы Вейча длялевой и правой части равенства. Левая часть равенстваBBA1111AB111111AB↓BC1111BAA1 11 1BCBBA1 11 1BDA1 11 11 11DCAB↓BC→BD13Правая часть равенстваBBA1A111111111111111DCПоскольку диаграмма Вейча для левой части совпадает с диаграммой для правой, то имеет место приведенное выше равенство.Примеры для практических занятий.Упростить булевы выражения:;а) X Y Z → X P ⊕ (YZ / XZP) =б) ( A B ∨ AC D) ≡ ( B C ⊗ AC D) =;в) M(AB→C, ACD, BD∨AC) =.Под M(X, Y, Z) понимается мажоритарная функция от аргументов X,Y, Z, где последние – любые аргументы или булевы выражения.1.8.