Основные этапы минимизации

Процедура минимизации выполняется в два этапа.

1. Раз метка карты Карно. Разметка заключается в выделении групп единичных клеток, представляющих собой контерм, или конъюнктивный член с меньшим числом первичных термов, чем у минтсрма. Группу могут составлять 2, 4, 8, 16 клеток. Объединенные в группу клетки обводят на карте Карно тонкой линией. Объединению подлежат только те заполненные единицами клетки, которые подчинены правилу склеивания. К ним относятся:

=> две соседние клетки;

=> клетки, составляющие полные столбцы или строки из 2,4 и 8 клеток; => клетки, составляющие полные квадраты из 4 и 16 клеток;

=> две группы клеток, расположенные симметрично относительно центральных вертикальных или горизонтальных осей карты и осей, разделяющих столбцы и строки карты с номерами 001 и 011, 111 и 101 (для М = 5 и 6).

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

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

Рассмотрим некоторые характерные случаи минимизации.