Функция трех переменных.

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

Карты Карно – это графическое представление таблиц истинности логических функций. Они представляют собой таблицы, содержащие по 2^N прямоугольных ячеек, где N – число логических переменных.

Если N = 3, то карта Карно будет содержать 8 ячеек. Пусть таблица истинности функции имеет вид.

Карта Карно размечается системой координат, соответствующих значениям входных переменных, например, верхняя строка карты для функции трех переменных соответствует нулевому значению переменной A, а нижняя – ее единичному значению. Каждый столбец этой карты характеризуется значениями двух переменных: B и C. Комбинация цифр, которыми отмечается каждый столбец, показывает, для каких значений переменных B и C вычисляется функция, размещаемая в клетках этого столбца. Координаты строк и столбцов в карте Карно следуют не в естественном порядке возрастания двоичных кодов, а в порядке 00; 01; 11; 10. Изменение порядка следования наборов кодов сделано для того, чтобы соседние наборы, отличающиеся между собой лишь цифрой какого-либо одного разряда, были соседними в геометрическом смысле.

Для данного примера структура карты Карно будет иметь следующий вид.

Ячейки, в которых функция принимает значение 1, заполняются единицами.

Процесс минимизации заключается в формировании прямоугольников, содержащих по 2^K ячеек, где K – целое число. В прямоугольники объединяются соседние ячейки, которые соответствуют соседним элементарным произведениям. В нашем примере объединены ячейки 1-ого столбца с координатами 000 и 100. При объединении этих ячеек образовался прямоугольник, в котором А изменяет свое значение. Следовательно, А исчезает при склеивании соответствующих элементарных произведений. Ячейки, расположенные в первой строке, содержат 1 и являются соседними. Поэтому они объединяются в прямоугольник, содержащий 2 ячейки. Переменная С в пределах прямоугольника меняет свое значение, следовательно, она исчезнет из результирующего элементарного произведения. Тогда получим:

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

Построим логическую схему и проверим ее работу, используя, программу Electronics Workbench.

Рис. 3

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