Файл: Ю. П. Шевелев.pdf

ЧАСТЬ 2. БУЛЕВА АЛГЕБРА
В предыдущем подразделе сказано, что всякая булева функция заданного числа аргументов представима в виде суммы минтермов единственным образом. Это утверждение справедливо только в том случае, если исходная функция и ее СДНФ зависят от одних и тех же аргументов. В общем же случае, если заданная функция содержит k аргументов, то с помощью теоремы разложения ее можно представить в СДНФ любого, большего k, числа аргументов, те. всякая булева функция представима в СДНФ неоднозначно, если нет ограничений на число аргументов.
Теорему разложения можно использовать при доказательстве других теорем. Например, докажем, что 2 Это далеко не очевидное тождество. Чтобы доказать его справедливость,
достаточно правую часть разложить по аргументу A:
(1
)
(0
)
A
B
A
B
A
B
A
AB
1 2 1
1 1
2 Точно также можно доказать, что
A
AB
A
B
1 2 Теорема разложения применима ив тех случаях, когда функцию требуется представить в виде
f
=
j
1
+
j
2
,
при условии, что j
1
× j
2
= 0, те. функции j
1
и j
2
являются ортогональными [16]. Такое представление возможно для всякой функции, достаточно применить к ней теорему разложения. Найдем j
1
и j
2
, например, для функции
f
AB
AC
1 2
Разложим ее по аргументу B:
(
1
)
(
0
)
f
B A
AC
B A
AC
ABC
AB
1 2 3 3
2 3 Отсюда получаем 2
1 2
;
;
0.
ABC
AB
ABC AB
1 2 1 2 1 1 2 Упражнения. Разложите функции по аргументу A. Результаты вводите в устройство в аналитической форме (минтермы упорядочить по возрастанию их индексов) (461). f = AB; 2) (МТ2).
;
f
AB
1 3) (РОЮ. f = B; 4) (ТАО). f = BC.
2. Сколько минтермов содержит СДНФ булевой функции вида f = A, если ее разложить по аргументам) СТ и B? 3) (717) A, B, C, D? 4) (РТ) A, B, C, D, E, F, K?
3. Сколько минтермов содержит функция f = AC + D, если ее разложить по аргументам) (839) A, C, D?
3) (И5С) A, B, C, D, E, F?
2) (Д) A, B, C, D?
4) (ХБТ) A, B, C, D, E, F, K, L?
4. Сколько минтермов содержит СДНФ функции f = 1, если ее разложить по аргументам) (ВИА) A?
3) (200) A, B, C, D?
2) (ИРИ) A и B?
4) (ТЛЯ) A, B, C, D, E, F?

6. ДИЗЪЮНКТИВНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ
121
6.6.
КАРТА ВЕЙЧА
Карта Вейча (ее модификацию называют диаграммой Карно) — это замечательное изобретение, позволяющее легко осуществлять различные преобразования булевых функций до пяти–шести аргументов.
Сначала рассмотрим карту двух аргументов (рис. 40). Левая половина карты обозначена буквой A, правая — той же буквой, нос инверсией. По горизонтали карта также разделена на две части. Верхняя половина обозначена буквой B, нижняя — буквой
B
Левая верхняя клетка находится на пересечении областей A и B — записываем в нее минтерм AB. Правая верхняя клетка находится на пересечении областей A и B. Записываем в эту клетку минтерм
AB
Аналогично записываем A B ив оставшиеся две клетки. На рис. 41 приведена та же карта,
но в клетках ее указаны десятичные номера минтермов.
Рассмотрим карту Вейча трех аргументов (рис. 42). В ней также для каждого минтерма отведена одна клетка, и, как ив случае карты двух аргументов,
алгебраическая запись минтермов строго соответствует системе расположения букв вокруг карты. На рис. 43 изображена та же карта, нов клетках указаны номера минтермов. Кроме того, на ней указаны только неинверсные аргументы. Это значит, что буква A не пишется, но подразумевается.
На рис. 44 приведена карта четырех аргументов, где в клетках указаны минтермы в их аналитической записи. Вокруг карты размещены переменные, для каждой из которых строго закреплена своя зона. В дальнейшем для
Рис. Рис. Рис. Рис. Рис. 44

ЧАСТЬ 2. БУЛЕВА АЛГЕБРА
всех карт будем указывать область только неинверсной буквы, полагая, что вторая половина карты обозначается буквой с инверсией.
На рис. 45 приведена карта, где размещены десятичные номера минтер
мов четырех аргументов.
На рис. 46 изображена карта пяти аргументов. Она получена из двух карт четырех аргументов. Левая карта обозначена буквой E, а правая соответственно буквой E Аналогичным образом можно построить карту Вейча на любое число аргументов, однако практически дело ограничивается картами пяти, реже шести и совсем редко семи и восьми аргументов, так как с увеличением числа аргументов быстро возрастает сложность карты и соответственно снижается эффективность ее использования.
Упражнения
1. Укажите на карте Вейча номер клетки, которой соответствует минтерм:
1) (И0Б). ABC;
3) (Д0В).
;
ABCD
5) (ГХГ).
;
AB
2) (0СД).
;
ABCD
4) (Е) (ЦВЖ).
ABCDEF
2. (ЕЮК). Сколько клеток имеет карта Вейча пяти аргументов. (УЦЛ). Сколько клеток имеет карта Вейча n аргументов. Запишите аналитическое выражение минтерма (через буквы A, B, C, находящегося в клетке карты Вейча с номером) (ЕС1). 4;
3) (ДР. 12;
5) (ТП3). 14;
2) (НП4). 0;
4) (ТЕК. НАНЕСЕНИЕ ФУНКЦИЙ НА КАРТУ ВЕЙЧА
Если функция представлена в виде суммы минтермов, то нанесение ее на карту сводится к отысканию клеток, за которыми закреплены номера соответствующих минтермов. В найденные клетки записываются единицы. Поясним это на примере функции 2
2 Рис. Рис. 46

6. ДИЗЪЮНКТИВНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ
123
Переведем минтермы в их номера (2, 3, 4, Воспользуемся картой, изображенной на рис. 43. В ее клетках записаны числа. Но их можно не писать, поскольку система расположения букв вокруг карты точно определяет место каждого минтерма. Удалим с карты номера и нанесем на нее функцию (рис. Единицы на карте обозначают номера минтермов, взятых из выражения (30). Самая правая единица (верхний ряд) занимает клетку с номером Это постоянное место минтерма
2
m
ABC
1
Поскольку он входит в заданную функцию, тов этой клетке и поставлена единица. Тоже самое относится и ко всем остальным единицам карты. Пустые клетки обозначают, что соответствующие минтермы не входят в функцию.
На карту можно нанести функцию, представленную не только в СДНФ,
но ив виде произвольной дизъюнкции конъюнкций. Например, пусть дана функция Она зависит от трех аргументов A, B, C. Соответствующая карта Вейча приведена на рис. 48. Первая конъюнкция, входящая в функцию, равна Находим на карте эту область. Она расположена на пересечении двух областей буквы A и буквы B. Это две верхние левые клетки. В них ставим единицы. На рис. 48 эти две единицы обведены и обозначены конъюнкцией Вторая конъюнкция имеет вид
AC
Находим область на карте, являющуюся общей для зон A и C. Это две клетки, расположенные вертикально.
Наконец, наносим на карту конъюнкцию
ABC
Она на карте занимает одну клетку на пересечении зон A, B и Мы рассмотрели случай, когда каждая конъюнкция на карте занимает новые области, не пересекающиеся с другими. Рассмотрим еще один пример. Нанесем на карту функцию A + Первая конъюнкция состоит из одной буквы. Конечно, это не конъюнкция, но для общности и одиночную переменную, входящую в функцию, удобно называть конъюнкцией. Нанесем эту одиночную переменную на карту
(рис. 49). Ей соответствует вся область A, состоящая из четырех клеток, следовательно, всю ее заполняем единицами.
Конъюнкция BC частью занимает новую клетку, а частью — уже занятую буквой A. Это значит, что седьмой минтерм нанесен на карту буквой поэтому вторично обозначать его нет необходимости.