Главная/

Радиоэлектроника, компьютеры и периферийные устройства. /

Вычислительныемашины и системы. Первый семестр.

ПЕРВЫЙ СЕМЕСТР ЛЕКЦИЯ N 6 я2МЕТОДЫ УПРОЩЕНИЯ (МИНИМИЗАЦИИ) БУЛЕВЫХ ФУНКЦИЙ Сложные булевы функции могут быть построены из более прос- тых. я2Элементарными функциямия0 называются функции, образованные пу- тем использования однотипных логических операций: только операции И, только операции ИЛИ и т.д. Для представления сложных логических функций можно использо- вать не все элементарные функции, а только ту или иную часть их, называемую системой. Система элементарных функций fя41я0, ..., fя4kя0 на- зывается функционально полной, если любую сложную булеву функцию можно записать в виде формулы через функции fя41я0, ..., fя4kя0. Так, любую функцию можно представить с помощью одних только операций И-НЕ или только операций ИЛИ-НЕ. В цифровых устройствах часто применяется в качестве базовой система из трех функций: И, ИЛИ и НЕ. Используя законы алгебры логики, можно упрощать сложные ло- гические выражения. Упрощение заключается в уменьшении количества букв и количества отрицаний в выражении, что позволяет упростить схему устройства с жесткой логикой или программу устройства с программируемой логикой. Такое упрощение позволяет уменьшить се- бестоимость и увеличить быстродействие устройства. Рассмотрим функцию я4_________ я7( я4_я7 )я4 _ f(a,b.c) = aя5.я72я0b V aя5.я0cя72я0 V aя5.я0b я79 0 Используя законы алгебры логики, можно привести эту функцию к виду: я4_ я0 я5 я0 я4_ я0 я4 _ я0 я4_ __ _ я0 я4_ _ f(a,b.c) = aя5.я0(bя5.я0(aя5 я0Vя5 я0c)) V aя5.я0b = ab V abc V ab = ab V ab я4применяем я0 я4 я0 я4 применяем я4законы де Моргана я0 я4 закон поглощения Одной и той же логической функции может быть поставлено в соответствие неограниченное количество различных эквивалентных формул. Наиболее удобными для практического использования являют- ся так называемые я2нормальные формыя0 представления сложных логичес- ких функций. я2Элементарной конъюнкциейя0 Q называется логическое произведе- ние переменных и их отрицаний, причем каждая переменная должна встречаться в произведении только один раз. .. - 2 - я4_ _ Пример элементарной конъюнкции: Q = xя41я0xя42я0xя43я0xя44я0xя46я0. Аналогично я2элементарной дизъюнкциейя0 В называется логическая сумма переменных и их отрицаний, причем каждая переменная должна встречаться в сумме только один раз. я4_ Пример элементарной дизъюнкции: D = xя41я0 V xя43я0 V xя44я0. Формула, эквивалентная заданной и представляющая собой логи- ческую сумму элементарных конъюнкций, называется я2дизъюнктивной я2нормальной формойя0 (ДНФ) заданной формулы. Дизъюнктивная нормаль- ная форма существует для любой логической функции. Аналогично считается, что логическая функция задана своей я2конъюнктивнойя0 я2нормальной формойя0 (КНФ), если она выражена посредс- твом логического произведения элементарных дизъюнкций. КНФ также существует для любой логической функции. Например, для функции я4_________ я7( я4_я7 )я4 _ f(a,b.c) = aя5.я72я0b V aя5.я0cя72я0 V aя5.я0b я79 0 ДНФ будет иметь вид я4_ _ f(a,b.c) = ab V ab, КНФ будет иметь вид я4_ _ f(a,b.c) = (a V b)(b V c). Одна и та же функция путем эквивалентных преобразований мо- жет быть представлена различными КНФ и ДНФ. Из всей совокупности нормальных форм, представляющих данную функцию, выделяют одну КНФ и одну ДНФ, именуемые совершенными. я2Минтермомя0 (m) n аргументов называется логическое произведе- ние этих аргументов, причем каждый аргумент может входить в про- изведение в прямой или инверсной форме. Минтермы могут быть пронумерованы, причем номер минтерма оп- ределяется как десятичный эквивалент двоичного числа, образован- ного из значений переменных, входящих в данный набор: если пере- менная входит в прямой форме, то ей соответствует единица, если в инверсной - ноль. я2Макстермомя0 (M) n аргументов называется логическая сумма этих аргументов, причем каждый аргумент может входить в сумму в прямой или инверсной форме. Номер макстерма задается аналогично номеру минтерма. .. - 3 - Рассмотрим в качестве примера случай двух аргументов: ЪДДДДДВДДДДДВДДДДДДДДДДДДДВДДДДДДДДДДДДДДї і a і b і минтерм і макстерм і ГДДДДДЕДДДДДЕДДДДДДДДДДДДДЕДДДДДДДДДДДДДДґ і і і я4_я0 я4_я0 і я4_я0 я4_я0 і і 0 і 0 і mя40я0 = aя5.я0b і Mя40я0 = a V b і і і і я4_я0 і я4_я0 і і 0 і 1 і mя41я0 = aя5.я0b і Mя41я0 = a V b і і і і я4_я0 і я4_я0 і і 1 і 0 і mя42я0 = aя5.я0b і Mя42я0 = a V b і і і і я4 я0 і і і 1 і 1 і mя43я0 = aя5.я0b і Mя43я0 = a V b і АДДДДДБДДДДДБДДДДДДДДДДДДДБДДДДДДДДДДДДДДЩ Минтермы и макстермы можно геометрически представить на кар- тах (диаграммах) Вейча. Так, для двух переменных карта Вейча бу- дет представлять собой квадрат, причем левая половина квадрата определяется переменной a, а верхняя половина квадрата - перемен- ной b. Это означает, что леваяя4_я0 половина квадрата соответствует значению переменной a, правая - a, верхняя половина соответствует я4_ b, нижняя b. Карта Вейча для двух переменных: я4_ я2a a ЪДДДДДВДДДДДї і і я4_я0 і я2b я0і aя5.я0b і aя5.я0b і і і і ГДДДДДЕДДДДДґ я4_я0 і я4_я0 і я4_я0 я4_я0 і я2b я0і aя5.я0b і aя5.я0b і і і і АДДДДДБДДДДДЩ .. - 4 - Карта Вейча дляя5 я0трех переменных: я4_ я2a a я5ЪДДДДДДБДДДДДДї ЪДДДДДДБДДДДДДї ЪДДДДДДДВДДДДДДДВДДДДДДДВДДДДДДДї і я4_я0 і і я4_я0 і я4_я0 я4_я0 і я2b я0і aя5.я0bя5.я0c і aя5.я0bя5.я0c і aя5.я0bя5.я0c і aя5.я0bя5.я0c і і і і і і ГДДДДДДДЕДДДДДДДЕДДДДДДДЕДДДДДДДґ я4_я0 і я4_я0 я4_я0 і я4_я0 і я4_я0 я4_я0 і я4_я0 я4_я0 я4_я0 і я2b я0і aя5.я0bя5.я0c і aя5.я0bя5.я0c і aя5.я0bя5.я0c і aя5.я0bя5.я0c і і і і і і АДДДДДДДБДДДДДДДБДДДДДДДБДДДДДДДЩ я4_я0 я5АДДДДДДВДДДДДДЩя4 _ я2cя0 я2c c я2Свойства минтермов и макстермов: 1) Минтерм является инверсией некоторого макстерма и наобо- рот:я4 _ mя4iя0 = M 2я5nя0-1-i я4_ Mя4iя0 = m 2я5nя0-1-i я4_ Пример: mя41я0 =я4 я0Mя42я0 (заштрихованная площадь соответствует макс- терму