Построение комбинационных логических схем

 

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

Состояние входов и выходов логической схемы может быть описано таблицей истинности или булевым выражением. В табл.10.7 были приведены таблицы истинности и булевы выражения для основных логических элементов.

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

Данное выражение можно упростить, используя аксиомы и законы булевой алгебры (табл.10.8), и получить так называемую минимальную сумму:

поскольку  и

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

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

т.к.  и

Рассмотрим как можно преобразовать информацию, представленную в форме таблицы истинности, в булево выражение. В табл.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 исходное булево выражение:

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

7) Объединяются угловые клетки. Рис.10.18. соответствует булеву выражению:

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

Рассмотренные правила объединение клеток, содержащие 1, показывают, что две смежные клетки уменьшают число переменных на одну (рис.10.9, 10.11, 10.13). Четыре клетки приводят к сокращению на две переменные (рис.10.15, 10.18). Для восьми клеток в минимальном члене остается только одна переменная (рис.10.16, 10.17). Объединение из 16 единиц уменьшает число переменных до нуля, т.е. в этом случае Y тождественно равен 1. Единица, находящаяся в отдельной клетке, не приводит к сокращению числа переменных. (рис.10.19).

Следует обратить внимание, что при объединение клеток нужно охватывать наибольшее число 1, причем получаемые контура могут пересекаться. Для рис.10.19 исходное булево выражение имеет вид:

Здесь можно построить три контура, что даст в упрощенном выражение три члена и одна единица не входит ни в один контур и поэтому даст ещё один член, содержащий четыре переменные. Упрощенное булево выражение примет вид:

Отметим, что существуют карты Карно для пяти и шести переменных, в которых помимо рассмотренных правил объединения клеток используются другие, дополнительные правила.