Графический метод минимизации

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

Структура карт Карно

Карта Карно для логических функций от М переменных Y = F(XM Хт,..., Х0) имеет форму прямоугольника или квадрата, который содержит Iм пронумерованных клеток (рис. 3.7). Номер клетки составляется из М-разрядного двоичного числа Хм ,...Хт...Х0, при этом старшими разрядами нумеруются строки, младшими – столбцы.

Представление логических функций с помощью карт Карно

Карту Карно для функции Y можно отождествить с таблицей истинности. Каждой клетке карты Карно соответствует строка таблицы истинности. Поэтому если для k-m набора переменных Хм_ v ..., Хт Х0 значение функции У* = 1, то в клетку с номером k заносится 1, в противном случае – 0 или клетка остается пустой. Клетки, заполненные единицами, будем называть единичными клетками, а заполненные нулями, или пустые клетки – нулевыми клетками.

На основании карты Карно (как и таблицы истинности) можно получить структурную формулу комбинационного устройства. Если каждой клетке карты Карно сопоставить минтерм и просуммировать все минтермы для клеток карты, заполненных единицами, то получим СДНФ логической функции. Если каждой клетке сопоставить макстерм и взять логическое произведение их всех для нулевых клеток, то получим СКНФ логической функции.

 
< Пред   СОДЕРЖАНИЕ     След >