<< Предыдущая

стр. 2
(из 5 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

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

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

Из полученной диаграммы Вейча легко выписывается минимальное
выражение для мажоритарной функции
F = x2 x3 ? x1 x3 ? x1 x2.
Возьмем некоторую функцию F четырех аргументов, диаграмма
Вейча которой имеет вид
B
A

1 1 1


D
1 1
C
9
Эта функция принимает значение 1 на пяти наборах, отмеченных на
диаграмме единицами. На остальных наборах функция принимает зна-
чение 0. СДНФ этой функции содержала бы пять конъюнкций каждая
ранга 4, объединенные знаками дизъюнкций. Однако из диаграммы Вейча
легко выписывается минимальное выражение функции в дизъюнктив-
ной нормальной форме
F = AC ? B C D .
Области в диаграмме Вейча обозначаются так, чтобы две соседние
клетки соответствовали бы “склеивающимся” конъюнкциям (т. е. конъ-
юнкциям, отличающимся значением только одного аргумента). Так,
например:
A B C D ? A B C D = AC D .
Это обеспечивает наглядность минимизации.
В общем случае области в диаграммах Вейча для функций большо-
го числа аргументов обозначаются кодом Грэя.
Таблица 5
Особенностью этого кода является то, что две
соседние комбинации отличаются значением толь-
0000 0000
ко одного аргумента. Обычный двоичный код это-
0001 0001
му условию не удовлетворяет.
0010 0011
Код Грэя используется в цифровых кодовых дат-
0011 0010 чиках, что позволяет сделать ошибку равномер-
ной при смещениях токосъемников, при этом ошиб-
0100 0110
ка равна 2-m где m – число двоичных разрядов ко-
0101 0111
дового датчика. Это свойство кода Грэя исполь-
0110 0101 зуется для обозначения областей в диаграммах
Вейча.
0111 0100
В табл. 5 приведен код Грэя для четырех аргу-
1000 1100
ментов (разрядов). Если требуется построить код
1001 1101
Грэя на меньшее число разрядов, то его легко по-
1010 1111 лучить из имеющейся таблицы путем “выреза-
ния” соответствующей части. Так, в приведенной
1011 1110
таблице показано, как получить двухразрядный код
1100 1010
Грэя. Если требуется построить код Грэя на пять
1101 1011 разрядов, то код в таблице следует зеркально от-
разить вниз и добавить еще один разряд, причем в
1110 1001
первой половине в этом разряде будут стоять нули,
1111 1000

10
а во второй – единицы. Аналогично строятся коды Грэя на любое число
разрядов.
П р и м е р . Минимизировать функцию семи аргументов, заданную
диаграммой Вейча:
D
C
B
A
1 1


1 1 1 1 1 1 1 1
1 1 1 1
1 1 1 1
G


F
1 1
E

Минимальное выражение в дизъюнктивной нормальной форме име-
ет вид
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.
Этот процесс называется доопределением булевой функции. Дооп-
ределение булевой функции желательно выполнять так, чтобы полу-
чить возможно более простое выражение. В этом случае, как прави-
ло, реализованная комбинационная схема также оказывается более
простой.
Пусть задана диаграмма Вейча некоторой не полностью определен-
ной функции:
B
A
1 – – 1
1 –
D – –
– 1
C

Приведенная функция имеет прочерки в шести клетках, в каждой из
которых может быть поставлена как 1, так и 0. Следовательно, суще-
ствует 26 = 64 различных способов доопределения булевой функции.
Однако из диаграммы легко выбрать наилучший, который дает следу-
ющий результат минимизации:
F = AC ? B D .
Примеры для практических занятий.
Доопределить функцию и выисать минимальное выражение из диаг-
рамм Вейча:




12
а) б)
c
B
b
A a
1 – – –
1 1 –
1 1 – 1 –
– –
1
e
– 1 –
D
– 1 1 –
1 – 1 d
C
в)
c
b
a
– – 1
1 1 – –
1 –
e
1 – – – –
d


1.7. Проверка равенств в булевой алгебре
Для того чтобы доказать равенство двух функций в булевой алгебре,
например, F(x1, x2, …, xn) = P(x1, x2, …, xn), необходимо и достаточно
показать, что на всех наборах аргументов x1, x2, …, xn левая часть ра-
венства совпадает с правой.
Например:
(AB v BC) > BD = ( B ? AC D) .
Для доказательства этого равенства построим диаграммы Вейча для
левой и правой части равенства. Левая часть равенства


B
B B B B
A
A A A A
1 1 1 1 11 11
1 11 1 1 11 11
1 11 1 1 11 D
1 1 1 1 1 C

AB BC ABvBC BD ABvBC>BD

13
Правая часть равенства
B
B
A A
1 1 1 1
1 1 1 1
1 1 1 1 D
1 1 1 1 C


Поскольку диаграмма Вейча для левой части совпадает с диаграм-
мой для правой, то имеет место приведенное выше равенство.
Примеры для практических занятий.
Упростить булевы выражения:
а) 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. Функционально полные наборы и базисные наборы
Функционально полным называется набор булевых функций {f1,
f2, …, fn} такой, что любая сколь угодно сложная булева функция может
быть выражена в виде суперпозиции (сочетания) функций из этого на-
бора.
Базисным называется такой функционально полный набор, из кото-
рого нельзя исключить ни одну булеву функцию без ущерба для его
функциональной полноты.
Поскольку любая булева функция, заданная таблицей истинности,
может быть представлена в виде СДНФ (или СКНФ), то набор
1) {&, ?, ? ) – функционально полный набор.
Набор 1) не является базисным набором, так как из него можно исклю-
чить либо &, либо ?, а недостающую функцию реализовать с помощью
оставшихся функций. Например, если из набора 1) исключена &, то ее
можно реализовать так: AB = ? (? A ?? B) (выражение справа понимает-
ся так: A ? B ). Если же из набора 1) исключена функция ?, то она может
быть реализована так: X ? Y = ? (? X? Y) = X Y .
14
Таким образом, получаем два функционально полных (базисных) на-

<< Предыдущая

стр. 2
(из 5 стр.)

ОГЛАВЛЕНИЕ

Следующая >>