Минимизация булевых функций
ЛЕКЦИЯ 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-х переменных.