Основы дискретной схемотехники (стр. 2 из 3)

Конъюнктивная нормальная форма - это функция, представляющая собой произведение членов, каждый из которых является суммой всех переменных или их инверсий:

Данное выражение можно упростить и получить минимальное произведение:

т.к.

и

Рассмотрим как можно преобразовать информацию, представленную в форме таблицы истинности, в булево выражение. В табл.10.9 показаны все возможные комбинации трех входов (A,B,C) и выхода (Y). Из табл.10.9 видно, что только три из восьми возможных комбинаций двоичных сигналов на входах А,В,С дают на выходе логическую 1. Эти комбинации представлены выражениями:

(читается как: не С и не В и А), и . В булевом выражении эти три комбинации связываются логической функцией или т.о. булево выражение имеет вид:

Таблица 10.9. Таблица истинности

Заметим, что полученное булево выражение можно упростить:

Это выражение содержит две комбинации входов, но в столбце выхода (табл.10.9) имеется три логические 1.

Легко произвести обратное преобразование - по булеву выражению построить таблицу истинности. Для выражения:

в табл.10.10, находим комбинации входов А,В,С и проставляем логические 1 в столбце значений выхода.

Таблица 10.10. Таблица истинности

Построим логическую схему для булева выражения, соответствующую табл.10.9. На выходе логической схемы должен быть логический элемент ИЛИ (OR). Кроме этого, схема (рис.10.4) содержит два элемента И (AND) и два инвертора (NOT).

На рис.10.5 представлена логическая схема для табл.10.10.

Рассмотрим булево выражение:

Для реализации логической схемы, соответствующей этому выражению, необходимы три элемента И, два инвертора и один элемент ИЛИ с тремя входами (рис.10.6).

Составим таблицу истинности для логической схемы, изображённой на рис.10.6.

Таблица 10.10. Таблица истинности

Анализ табл.10.10. показывает, что она соответствует таблице истинности логического элемента ИЛИ (табл.10.7). Булево выражение для элемента ИЛИ имеет вид: A+B=Y, а логическая схема изображена на рис.10.7.

Приведённый пример показывает, что для реализации исходного булева выражения нет необходимости использовать шесть логических элементов (рис.10.6). Используя упрощения булева выражения можно получить более простую логическую схему (рис.10.7.). Для упрощения булевых выражений можно воспользоваться методами, использующими карты Карно.

Карты Карно

В 1953 г. Морис Карно предложил систему графического представления и упрощения булевых выражений. На рис.10.8 приведена карта Карно для двух входных переменных. Логические члены представлены в ней в отдельных клетках. Для двух переменных получается 22 = 4 комбинации, поэтому карта состоит из четырех клеток

На рисунке показано, какие поля карты относятся к переменным, а какие — к их дополнениям. Переменные размещаются на карте таким образом, что при переходе из одной клетки в соседнюю клетку, как по горизонтали так и по вертикали, меняется только одна переменная. Если требуется получить карту Карно для какого - либо выражения, то сначала это выражение записывается в дизьюктивной нормальной форме. Каждый член, который появляется в этой форме, задаётся на карте с помощью 1 в соответствующей клетки. Затем соседние единицы объединяются в один контур группами по две, четыре или восемь единиц. Построение контуров продолжается до тех пор пока все единицы не окажутся внутри контуров. При этом каждый контур представляет собой новый член упрощённого булева выражения.

Рассмотрим пример. Пусть исходное булево выражение имеет вид:

Заполним карту Карно (рис.10.9.), разместив логические единицы в тех квадратах, которым соответствуют произведению в исходном булевом выражении.

Объединим логические 1 в два контура. Это означает, что упрощённое выражение будет состоять из двух членов, связанных функцией ИЛИ. Рассмотрим верхний контур (рис.10.9). Заметим, что А здесь встречается в комбинации с В и

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

При применении карт Карно для упрощения булевых выражений следует помнить, что каждый контур даёт в минимальную сумму один член, и при этом исключаются члены, дополняющие друг друга внутри контура.

Карта Карно для трех переменных приведена на рис.10.10.

Для трёх переменных имеется восемь квадратов, которые соответствуют восьми возможным комбинациям переменных. Для булева выражения:

заполненная карта Карно приведена на рис.10.10. Каждая группа из двух соседних единиц составляет один контур. Булево выражение в дизьюктивной нормальной форме будет содержать два члена. В нижний контур входят С и

, поэтому они опускаются. В верхнем контуре опускаются переменные В и . Упрощенное булево выражение примет вид:

Карта Карно для четырёх переменных содержит 24 = 16 клеток (рис.10.12).

Рассмотрим булево выражение:

Заполненная карта Карно для данного выражения показана на рис.10.13. Группы из двух и четырёх единиц объединены конурами. Контур, содержащий две единицы, даёт возможность опустить D и

. В другом контуре, содержащем четыре единицы, есть возможность опустить D, и А, . В результате упрощенное булево выражение примет вид:

Из рассмотренных примеров можно сделать вывод, что для упрощения булевых выражений с двумя, тремя и четырьмя переменными применяются одинаковые правила и чем больше размеры контуров, тем больше переменных можно опустить.

Рассмотрим основные правила объединения на картах Карно клеток, содержащих единицы, для булевых выражений не более чем с четырьмя переменными:

1) Объединяются две соседние клетки, в столбце или ряду (рис.10.9, 10.11, 10.13).

2) Объединяются четыре соседние клетки, составляющие квадраты (рис.10.13).

3) Объединяются клетки или пары клеток, крайние в столбце или рядах (рис.10.14). Для примера, на рис.10.14 исходное булево выражение имеет вид:

В результате упрощения получим:

4) Объединяются полные столбцы или ряды (рис.10.15). Для рис.10.15 исходное булево выражение:

Упрощённое выражение:

5) Объединяются пары рядом расположенных столбцов или рядов. Для рис.10.16 исходное булево выражение:

Упрощённое выражение: Y=A.

6) Объединяются крайние столбцы или ряды. Для рис.10.17 исходное булево выражение: