Главная/

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

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

терму, незаштрихованная - минтерму). я1ЪВВВя0Вя1ДДя0Дї я1ГЕЕЕґ і я1ГЕЕЕя0Ая1ВВВя0ґ я1ГЕЕЕЕЕЕЕґ я1АБББББББЩ 2) Логическая сумма всех минтермов для любого заданного чис- ла переменных равна 1. 2я5nя0-1 V mя4iя0 = 1. i=0 3) Логическое произведение всех макстермов для любого задан- ного числа переменных равно 0. 2я5nя0-1 я7Lя0 Mя4iя0 = 0. i=0 . - 5 - 4) Два неодинаковых минтерма или макстерма имеют хотя бы од- ну переменную, входящую в один из них в прямой, а в другой - в инверсной форме, следовательно mя4iя5.я0mя4jя0 = 0, если i я7-я0 j; Mя4iя0 V Mя4jя0 = 1, если i я7-я0 j. я2Основная теорема алгебры логикия0: любую булеву функцию от n переменных можно выразить логической суммой минтермов, которая называетсяя2 совершенной нормальной дизъюнктивной формойя0, или логи- ческим произведением макстермов, которое называетсяя2 совершенной я2нормальной конъюнктивной формойя0. Логические функции отражают не только принцип работы некото- рых частей ЭВМ, но и их состав, если каждой элементарной функции соответствует реальный физический элемент. Любая сложная логичес- кая функция может быть реализована некоторой частью ЭВМ, если эта часть построена с помощью такого набора элементов, который реали- зует все функции одной из функционально полных систем. Такой на- бор называется функционально полным набором логических элементов Поскольку каждая функция может быть представлена в виде раз- личных логических уравнений, каждая функция может быть реализова- на при помощи различных логических схем. Очевидно, что более простому логическому уравнению соответствует более простая схема. Упрощение (минимизация) функции сводится к получению ее минималь- ной дизъюнктивной или конъюнктивной нормальной формы, т.е. такой формы, при которой функция содержит наименьшее число переменных и знаков логических операций. Существует несколько методов минимизации. В дальнейшем мы рассмотрим метод непосредственных преобразований и метод диаграмм Вейча. ПЕРВЫЙ СЕМЕСТР ЛЕКЦИЯ N 7 я2МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ я2Метод непосредственных преобразований Суть данного метода заключается в том, что минимизация ис- ходной логической функции производится путем применения к отдель- ным членам или группам членов формулы, выражающей данную логичес- кую функцию, основных законов алгебры логики с целью получения минимальной формы функции, т.е. такой, которая не содержит лишних переменных или членов. Лишними переменными или членами являются те, которые не вли- яют на значение преобразуемой формулы. Пример: я4_ я5 я4_ xя41я5.я0xя42я5.я0xя43я0 V xя41я5.я0xя42я5.я0xя43я0 = xя42я5.я0xя43я5.я0(xя41я5 я0Vя5 я0xя41я0) = xя42я5.я0xя43я5.я01 = xя42я5.я0xя43 т.е. в исходной формуле лишней являлась двоичная переменная xя41я0. Примечание: произведенная операция называется "склеиванием" членов формулы. Действия, отвечающие методу непосредственных преобразований, обычно проводятся в следующем порядке: 1) Выявляются группы двоичных переменных исходной формулы, к которым можно применить операцию склеивания или другие законы ал- гебры логики, приводящие выражение к более простой форме. 2) Упрощение исходной формулы путем применения к выявленным группам соответствующих законов. 3) Преобразование промежуточной логической формулы с целью образования таких групп переменных, к которым можно применить уп- рощающие законы алгебры логики. Здесь могут проводиться: - группирование членов; - действия по раскрытию скобок и выносу за скобки; - добавление фиктивных членов, т.е. таких, совокупность ко- торых тождественно равна нулю; - логическое умножение одного или нескольких членов на логи- ческую сумму переменной и ее отрицания. 4) Упрощение преобразованной промежуточной логической форму- лы с получением формы, близкой к минимальной, в виде некоторой ДНФ. 5) Выявление и удаление из полученной предварительной формы лишних членов, что дает минимальную форму исходной логической функции. В качестве примера рассмотрим минимизацию следующей функции: я4_ _ _ _ f(a,b,c) = ab V bc V bc V ab = . - 2 - (используем метод умножения всех членов формулы на сумму тех пе- ременных и их отрицаний, которые отсутствуют в данном члене;) я4_ _ _ _ _ _ _ _ = ab(cVc) V bc(aVa) V bc(aVa) V ab(cVc) = (в результате, отбросив повторяющиеся члены, получаем СДНФ функ- ции;) я4_я0 я4 __ я0 я4_я0 я4 _ _я0 я4 _я0 я4 __я0 я4 _я0 я4 _ _ = abc V abc V abc V abc V abc V abc V abc V abc = АДЩ ИНј АДЩ ИНј я4_ __ _ _ _ __ _ = abc V abc V abc V abc V abc V abc = (перегруппировываем члены с целью их упрощения) я4_ я9 я4 _ _ _ _ _ = bя9cя0(aVa) V ab(cVc) V ac(bVb) = (окончательно получим) я4_ _ _ = bc V ab V ac. Однако группирование членов после умножения можно провести и несколько иначе: я4_ _ _ _ _ _ _ _ _ f(a,b,c) = ab(cVc) V bc(aVa) V ac(bVb) = ab V bc V ac. Следовательно, данная функция имеет две минимальные формы. Недостатком метода непосредственной минимизации является трудность получения всех минимальных форм, если их несколько. Кроме того, метод в целом весьма трудоемок, результат минимизации в сильной степени зависит от квалификации и интуиции человека, проводящего минимизацию. Поэтому данный метод применяется лишь для минимизации простых логических формул. я2Метод минимизации с помощью карт Вейча Данный метод наиболее применим в инженерной практике благо- даря своей простоте и легкости использования. Однако метод удобен для упрощения функций, зависящих от небольшого числа переменных (до 8). Преимущество этого метода состоит в том, что нет необхо- димости приводить функцию к СДНФ. Рассмотрим изображение на карте Вейча функции я4__ _ _ _ __ _ __ _ f(a,b,c,d) = cd V abd V abc V abcd V abcd V bcd . - 3 - При нанесении заданной функции на карту никаких предвари- тельных преобразований не проводится. Каждый дизъюнктивный член рассматривается в отдельности, и в соответствующие ему квадратики вписывается 1 (т.е. дизъюнктивный член развертывается до минтер- мов). Например, нанесение на карту вейча заданной функции выполня- ется в следующей последовательности: a ЪДДДБДДДї ЪЪДДДВДДДВДДДВДДДї ЪДДДВДДДВДДДВДДДї ЪДДДВДДДВДДДВДДДї іі я_1я. і і і я_1я. і і я_1я. і я_1я. і і 1 і і 1 і 1 і і я_1я. і b ґГДДДЕДДДЕДДДЕДДДґї ГДДДЕДДДЕДДДЕДДДґ ГДДДЕДДДЕДДДЕДДДґ іі і і і іі і і і і і і і і і я_1я. і АГДДДЕДДДЕДДДЕДДДґГ d ГДДДЕДДДЕДДДЕДДДґ ГДДДЕДДДЕДДДЕДДДґ і і і і іі і і і і і і і і і і ГДДДЕДДДЕДДДЕДДДґЩ ГДДДЕДДДЕДДДЕДДДґ ГДДДЕДДДЕДДДЕДДДґ і я_1я. і і і я_1я. і і 1 і і і 1 і і 1 і і і 1 і АДДДБДДДБДДДБДДДЩ АДДДБДДДБДДДБДДДЩ АДДДБДДДБДДДБДДДЩ АДДДВДДДЩ я4__я0 cя4 я0 я4 __ _ __ _ _ _ cd cd V abd cd V abd V abc ЪДДДВДДДВДДДВДДДї