Бойт К. - Мир электроники, страница 11

Упрощение нормальной формы ИЛИ Нормальная форма ИЛИ воспроизводит содержание таблицы истинности в виде логического уравнения. По этому уравнению может быть синтезирована нужная схема. По нормальной форме ИЛИ можно синтезировать схему, удовлетворяющую соответствующей таблице истинности. Часто эта схема не является самым простым вариантом из возможных. Во многих случаях нормальные формы ИЛИ можно упростить. Это упрощение может быть выполнено с помощью алгебры логики.

Пример 1 Упростите нормальную форму ИЛИ У = (А л В) ч (А л В). Так как обе полные конъюнкции содержат переменную А, то она с помощью распределительного закона может быть вынесена за скобки: У =(АлВ)ч(АлВ); У = А л (В ч В). Выражение В ч В всегда равно 1 (см. гл. 4). У= Ал 1. Логическое сложение переменной с 1 дает в итоге переменную. Результат упрощения нормальной формы ИЛИ: Пример 2 Упростите следующую нормальную форму ИЛИ: У = (А л В л С) ч (А л В л С) ч (А л В л С) ч (А л В л С) . О4 Оз От О| Сначала упрощают полные конъюнкции О1 и Ф. А л В рассматривается как одна переменная и выносится за скобки: ((А л В) л С) ч ((А л В) л С) = (А л В) л (С ч С) = (А л В) л 1 = (А л В) . Также можно упростить полные конъюнкции ® и Ои. А л В рассматривается как одна переменная и выносится за скобки: ((А л В) л С) ч ((А л В) л С) = (А л В) л (С ч С) = (А л В) л 1 = (А л В) .

~Ъ Г 5~ Для У тогда: У = (А л В) ~ (А л В). В этом уравнении А может быть вынесена за скобки как совместная переменная: У = А л (В ~ В); У=Ал1; У = А. Достаточно сложная нормальная форма ИЛИ сильно упростилась в этом примере. Такое сильное упрощение во многих случаях невозможно. Существует много нормальных форм ИЛИ, которые не упрощаются. Пример 3 Упростите следующую нормальную форму ИЛИ: 2' = (А л В л С) ч (А л В л С) .

Так как обе полные конъюнкции содержат переменную, то она с помощью распределительного закона может быть вынесена за скобки: .с = С л ((А л В) и (А л В)). Можно поспорить, является ли вынесение за скобку С упрощением исходного выражения. Ответ будет очевиден только при сборке схемы на реальных элементах. Существенного преимущества в любом случае не получится. 5.3.2. Преобразование нормальной формы ИЛИ Схема, которая строится согласно нормальной форме ИЛИ, должна базироваться на основных логических элементах.

Во многих случаях можно использовать другие элементы, например И-НЕ или ИЛИ-НЕ. Нормальная форма ИЛИ в этих случаях должна быть преобразована. Перевести нормальную форму ИЛИ на элементы И-НЕ очень просто. Нормальная форма ИЛИ сначала подвергается двойному отрицанию. Двойное отрицание, как известно, не меняет содержание уравнения.

Затем нижняя черта инверсии разделяется согласно второй теореме де Моргана. Пример 1 У = (А л В л С) ~ (А л В л С); У = (А лВлС)н(А л ВлС); 6.6. м р р кр 65) Рие. 5.10. Схема только с элементами И-НЕ. л в с Получающаяся из уравнения схема представлена на рис.

5.10. Если требуется преобразовать нормальную форму ИЛИ так, чтобы схема состояла только из элементов ИЛИ-НЕ, то рекомендуется дважды инвертировать каждую полную коньюнкпию и каждую нижнюю черту инверсии преобразовать в соответствии с первой теоремой де Моргана. Затем все выражение еще раз подвергается двойному отрицанию. Пример 2 У = (В л В л С) ч (А л В л С); У = (А л ВлС) м(А лВ лС); У =Ах ВмСмАмВМС; У = А и В и С и А хр В и С. Схема к этому уравнению изображена на рис.

5.11. л в с Рие. 5.11. Схема только с элементами или-нв. 5.4. Метод карт Карно Метод карт Карно служит для наглядного представления и упрощения нормальной формы ИЛИ. Он был придуман математиком Карно, и его еще называют методом диаграмм Карно. 5.4.1. Карта Карно дпя двух переменных Карты Карно могут быть представлены в виде таблиц истинности для полных конъюнкций. (66 Г 5.~ Карты Карно всегда имеют количество полей, равное количеству возможных полных конъюнкций.

При двух переменных возможны 4 полные конъюнкции. Таким образом, карта Карно для двух переменных должна иметь 4 поля (см. рис. 5.12). По краям карты записываются переменные. Каждая переменная величина должна быть представлена в инвертированной и в неинвертированной форме (рис. 5.12). Переменные по краям являются координатной сеткой. Они определяют, какая полная конъюнкция какому полю принадлежит.

На рис. 5.13 по своим полям расписаны 4 полных конъюнкции. Я Я :У :Н л в Рвс. 5.13. Карта Карно для двух переменных (А, В), за- полненная полнымн конь- юнхпнямн. х в Рве. 5.12. Карта Карно для двух переменных (А, З). Поле полной конъюнкции А д В обозначено координатами А и В (рис. 5.13). Соответственно поле полной конъюнкции А д В находится по координатам А и В. Так как полные конъюнкции определяются координатами, то нет необходимости записывать их в полной форме, как на рис. 5.13. Наличие полной конъюнкции может обозначаться 1 в соответствующем поле. 1 в поле карты Карно означает наличие полной конъюнкции.

На карте Карно (рис. 5.14) отмечены полные конъюнкции А л В и А л В. Карта Карно отражает следующую нормальную форму ИЛИ: У = (А л В) м (А л В). Символ У в верхнем левом углу карты на рис. 5.14 показывает, что полные конъюнкции относятся к У. Отсутствующие полные конъюнкции обозначены нулем в соответствующем поле, или поле не заполняется. Присваивание переменных координатам карты Карно производится произвольным образом. Также возможно менять местами А и В на карте (рис.

5.15). Разумеется, переменные могут иметь совершенно другие обозначения, например Е, и Е,. Прямое и инверсное значения переменной должны обязательно находйться на одной стороне карты. Другое распределение координатных переменных ведет, естественно, к другому распределению полных конъюнкций по полям карты.

Желательно придерживаться определенной схемы распределения переменных и не менять ее без причины. Для облегчения работы рекомендуется первую переменную, например А, и ее инверсию все время ставить на верхнюю часть карты. Вторую переменную (например В) и ее инверсию ставить на левую часть карты. р.р. и р р к р Д в в Е, Е Рис. 5.15. Карта Карно с изме пенными координатами. Покажем на примере заполнение карты Карно нормальной формой ИЛИ и восстановление нормальной формы ИЛИ по карте Карно. Пример 1 Занесите в карту Карно нормальную форму ИЛИ: У = (А л В) и (А л В) кр (А рк В).

Сначала нужно нарисовать карту Карно с данными координатами. Затем найти поля с полными конъюнкциями, присутствующими в нормальной форме и обозначить их 1. Результат показан на рис. 5.16. Рис. 5.16. Карта Кар- но для нормальной формы ИЛИ. Рис. 5.17. Карта Кар- но для нормальной формы ИЛИ. Пример 2 Запишите нормальную форму ИЛИ, представленную на карте Карно (рис. 5.17). Нормальная форма ИЛИ содержит 2 полные конъюнкции: одна А рк В, вторая А д В. Следовательно, нормальная форма: И" = (А л В) м (А л В).

Представленная на карте Карно нормальная форма ИЛИ может быть упрощена при наличии определенных условий. «Соседние» полные конъюнкции можно объединять в «группы», Соседними считаются полные конъюнкции, клетки которых имеют общие стороны (рис. 5.18). Если клетки с полными конъюнкциями имеют только общий угол, то они не являются соседними. д д д д д д д д :Н Соаедние поп»не конъюнкции Неаааедние попние конъюнкции Рис. 5.18. Соседние и несоседние полные конъюнкции.

Рис. 5.14. Карта Кар- но для нормальной формы ИЛИ ю =1А д В) а'кА о В) :Н :Н :Ш В одной группе могут быть объединены 2 или 4 соседние полные коньюнкции. Каждая группа имеет определенные координаты. Группа слева наверху на карте Карно (рис. 5.18) имеет по одной стороне координату В, по другой— координату А и А.

Содержание группы характеризуется вв координатами. Переменные, чьи координаты присутствуют в прямой и инверсной форме одновременно, исключаются. У =(АлВ)ч(АлВ) упростилась до У= А. У =(АлВ)ч(АлВ); У = А л (В ч В); У =Ал1; т =А. Это упрощение может быть проверено с помощью алгебры логики. Рнс. 5Л9. Образова- ние группы в карте Карно. Рис. 5.20. Карта Кар- но с группой из че- тырех полей. г=д Особый случай представляет группа из 4 полных конъюнкций (рис. 5.20). Она имеет координаты А, А, В, В. Значит, переменные А и В исключаются.

Значение группы равно 1. Справедливость этого можно доказать с помощью таблицы истинности. Алгебра логики также приведет к этому результату: У = (Ал В)ч(А л В) ч(А л В)ч(Ал В); У = ~А л (В ч В)]м(А л(Вч В)~; У =(Ал1)ч(Ал1); У =АчА; У =1. Представленная на рис. 5.19 группа имеет координаты А, В и В. Переменная В имеет как прямую, так и инверсную формы.

Следовательно, она исключается. Значение группы будет А. Нормальная форма ИЛИ 5.4в д р гр 69~ Рис. 5.21. Карта Кар- Рис. 5.22. Карта Карно с несколькими но с двумя группами х в группами. иа двух полей. На одной карте можно образовать несколько групп (рис. 5.21). Одна полная конъюнкция может присутствовать в нескольких группах. При наличии нескольких групп упрощенное уравнение получается в результате логического сложения значений отдельных групп.

Для карты (рис. 5.21) значения групп получаются равньгми А и В. Упрощенное уравнение: х, = Ам В. На карте Карно (рис. 5.20) можно образовать также две группы из двух полей. Тогда получится упрощенное уравнение, но не в самом простом виде. Покажем это. На рис. 5.22 показана карта Карно с такой группировкой. Значения групп равны В и В. Упрощенное уравнение, следовательно: х, = ВмВ. Сложение переменной величины с ее инверсией дает в итоге по правилам алгебры логики 1.

Поэтому самой простой формой уравнения является г= 1. Для максимального упрощения уравнения необходимо образовывать группы как можно большего размера. Чтобы закрепить полученные знания, решим следующий пример. Пример 3 Максимально упростите при помощи карты Карно нормальную форму ИЛИ. Запишите упрощенное уравнение: Х = (А л В) м (А л В) м (А л В). Сначала полные конъюнкции заносятся в карту (рис. 5.23). Рис. 5.23. Карта Карно к примеру 3. Затем образуются две группы по два поля. Они имеют значения А и В. Упрощенное уравнение: Х = А л В. 5.4.2. Карта Карно для трех переменных Для трех переменных возможны 8 различных полных конъюнкций (рис.