Минимизация булевых функций
ЛЕКЦИЯ 3
--------
План
1.Методы минимизации.
2.Карты Карно.
3.Алгоритм графич.минимизации.
4.Сущность алгоритма.
3.Минимизация булевых функций
Существуют несколько способов минимизации булевых функций.Прежде всего,это аналитический символьный и аналитический кодовый методы,метод Квайна - Мак-Класки,метод Блека - Порецкого,метод обобщенных кодов[11] и графическая минимизация с помощью карт Карно[12].
Пример для демонстрации аналитических методов:
z = x_y+xy_+xy = (x_y+xy)+(xy_+xy) = y(x_+x) + x(y_+y) = x+y.
z = 01+10+11 = (01+11)+(10+11) = -1+1- = x+y.
Первые четыре метода чрезвычайно громоздки и малоэффективны уже при количестве аргументов более четырёх. Метод обобщенных кодов ориентирован на использование ЭВМ,однако может использоваться и при ручном синтезе для функций от большого числа переменных.
3.1.Минимизация полностью определенных булевых функций
Наиболее эффективна минимизация булевых функций с помощью карт
Карно.До сих пор существует ошибочное мнение,что этим методом можно
решать задачи для функций от не более, чем 6 аргументов. На самом деле
карты Карно могут применяться для функций даже от 8-12 переменных
[12]. На рис.3.1. представлены карты Карно для 2-6 переменных и приме-
ры минимизации с их помощью логических функций.
\ x1 \x2x1 \x2x1
x2 \ 0 1 x3\ 00 01 11 10 x4x3\ 00 01 11 10
\ ----T----- -----T----T----T----- ------T-----T-----T------
0 | а | а | 0 | а | | | а | 00 | 1 | 0 | 1 | 1 |
+----+----+ +----+----+----+----+ +-----+-----+-----+-----+
1 | | | 1 | | | | | 01 | 0 | 0 | 1 | 0 |
L----+----- L----+----+----+----- +-----+-----+-----+-----+
-- -- -- 11 | 0 | 0 | 1 | 0 |
а = X2 а = X3*X1 +-----+-----+-----+-----+
10 | 1 | 0 | 1 | 1 |
L-----+-----+-----+------
-- --
y = X2X1 + X3*X1
а) б) в)
\
\ X2X1
X5X4X3 \ 00 01 11 10
------T-----T-----T------
000 | а | а | b | b |
+-----+-----+-----+-----+ -- --
001 | | | b | b | а = X3*X2
+-----+-----+-----+-----+ --
011 | | | b | b | b = X5*X2
+-----+-----+-----+-----+
010 | а | а | b | b | c = X5*X3*X2
+-----+-----+-----+-----+
110 | а | а | | |
+-----+-----+-----+-----+
111 | | | с | с |
+-----+-----+-----+-----+
101 | | | с | с |
+-----+-----+-----+-----+
100 | а | а | | |
L-----+-----+-----+------
г)
\ Х3Х2Х1
Х6Х5Х4 \
000 001 011 010 110 111 101 100
----T---T---T---T---T---T---T----
000| a | в | c | | | c | в | a |
+---+---+---+---+---+---+---+---+
001| e | | | e | | | | | f=X6*X5*X4
+---+---+---+---+---+---+---+---+ __
011| m | k | k | m | m | k | k | m | n=X6*X4*X2
+---+---+---+---+---+---+---+---+
010| d | d | | | | | d | d |
+---+---+---+---+---+---+---+---+
110| n | n | | | | | n | n |
+---+---+---+---+---+---+---+---+
111| f | f | f | f | f | f | f | f |
+---+---+---+---+---+---+---+---+
101| | | | | | | | |
+---+---+---+---+---+---+---+---+
100| n | n | | | | | n | n |
L---+---+---+---+---+---+---+----
д)
Рис.3.1. Карты Карно для 2-6 переменных
Метод Карно основан на законе склеивания.Склеиваются наборы,
отличающиеся друг от друга лишь значением одного разряда.
Такие наборы называются соседними, и они соответствуют соседним
клеткам карты Карно.Формируются такие наборы(коды Грея) по принципу
симметрии[11,12].
Введем определение прямоугольника Карно, под которым будем пони-
мать некоторую, зачастую разрозненную, фигуру покрытия,удовлетворяющую
принципу симметрии,т.е. сплошь состоящую из элементарных прямоугольни-
ков Карно,закодированных только соседними наборами.
Алгоритм "НИИРТА"
графической минимизации логических функций
1.Заполнить карту Карно нулями и единицами в соответствии с таб-
лицей истинности.
2.Покрыть все единичные наборы минимальным количеством прямоу-
гольников Карно, каждый из которых имеет максимальную площадь.
3.Каждому прямоугольнику Карно соответствует одна импликанта,
причем, если в границах прямоугольника Карно какая-либо переменная
принимает значение как 0, так и 1, то она склеивается.
На рис. 3.2 представлены фигуры покрытия,не являющиеся прямоу-
гольника Карно
\ x3x2x1
x5x4 \ 000 001 011 010 110 111 101 100
----T---T---T---T---T---T---T----
00 | К | К | | К | К | | К | К |
| | | | | | | | |
+---+---+---+---+---+---+---+---+
01 | П |П | | | | | | |
| | | | | | | | |
+---+---+---+---+---+---+---+---+
11 | | | | М |М |М |М | |
| | | | | | | | |
+---+---+---+---+---+---+---+---+
10 | П |П | | М |М |М |М | |
| | | | | | | | |
L---+---+---+---+---+---+---+----
Рис. 3.2 Фигуры покрытия,не являющиеся прямоугольниками Карно
Применим карту Карно для решения задачи 2.1 о синтезе автомата
для тайного голосования.Это решение представлено на рис. 3.3
\ x2x1
x4x3 \ 00 01 11 10
----T----T----T-----
00 | 0 | 0 | 0 | 0 | y= x4x1 + x4x2 + x4x3 + x3x2x1
+----+----+----+----+
01 | 0 | 0 | 1 | 0 | Это выражение представляет собой пример
+----+----+----+----| минимальной дизъюнктивной нормальной
11 | 1 | 1 | 1 | 1 | формы (МДНФ).
+----+----+----+----+
10 | 0 | 1 | 1 | 1 |
L---------+----------
Рис. 3.3. Решение задачи 2.1.
В некоторых случаях приведение результата минимизации к скобочной
форме позволяет уменьшить сложность булевой функции. Скобочная форма
для (3.3) имеет вид
y= x4(x1 + x2 + x3) + x3x2x1.
Реализация скобочной формы логической функции автомата для тайно-
го голосования в виде релейной схемы изображена на рисунке.
| x3 x2 x1 |
+----------------L-----L------L-------------- |
| | ------- |
| x4 x3 | | | |
+------L---T-----L-----T--------------------+---+ УИ +----+
| | x2 | | | |
| +-----L-----+ L------ |
| | x1 | |
| L-----L------ |
| |
|+Еп |-Еп
Релейная схема автомата к задаче 2.1
На схеме представлены контакты реле x4,x3,x2,x1.При включении
тумблера срабатывает соответствующее реле и замыкает свои контак-
ты.Например,если за прием абитуриента проголосовали председатель(x4) и
3-й член комиссии(х3),то замкнутся контакты х4 и х3 и сработает уст-
ройство индикации(УИ),запитанное от источника с напряжением Еп.
Домашнее задание.
1.Найти z5,z7,z11,z13,z14,z15 для функций от трех переменных.
------T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---T----
| uxy |z0 |z1 |z2 |z3 |z4 |z5 |z6 |z7 |z8 |z9 |z10|z11|z12|z13|z14|z15|
+-----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 000 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 001 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 010 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 011 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 100 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 101 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 110 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 111 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
L-----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+----
2.Найти общее количество функций от 3-х переменных.