Задача минимизации структурной формулы ПФ состоит в том, чтобы получить логическое выражение в минимальной дизъюнктивной нормальной форме (МДНФ) или в минимальной конъюнктивной нормальной форме (МКНФ), соответствующее заданной ПФ и содержащее наименьшее количество инверсий, конъюнкций и дизъюнкций и наименьшее число переменных (или их инверсий), над которыми выполняются операции конъюнкции и дизъюнкции.
Суть минимизации ПФ заключается в использовании закона склеивания соседних минтермов, которым на карте Карно соответствуют клетки, заполненные единицами, или соседних макстермов, которым соответствуют нулевые клетки (пустые). Минимизация путем склеивания единичных или нулевых клеток карт Карно (диаграмм Вейча) при небольшом числе переменных выполняется просто и наглядно.
Введем понятие подкуба, которое используется в теории ПФ и их минимизации. Подкуб – это совокупность 2i соседних клеток карты Карно, заполненных единицами (нулями), для которых по крайней мере одна переменная в координатах всех этих 2i клеток имеет неодинаковые значения (0 и 1). Из определения следует, что подкуб могут образовать 2, 4, 8, 16 и т.д. соседних клетки карты.
Каждый 2i-клеточный подкуб позволяет при минимизации исключить i переменных – 1,2,3,4 и т.д. Действительно, подкуб, состоящий из двух клеток, соседних по горизонтали или вертикали (рис.2,а,б,в,г) характеризуется тем, что координаты его клеток различаются значением одной переменной, а остальные переменные имеют одинаковое значение.
Переменная, значения которой для этих клеток различны (0 и 1), в соответствии с законом склеивания исчезает. Четырехклеточный подкуб содержит клетки, координаты которых различаются значениями двух переменных (рис.3,а,б,в), следовательно, четырехклеточный подкуб позволяет исключить две переменные. Восьмиклеточный подкуб позволяет исключить три переменные (рис.3,г,д).
Все минтермы (макстермы), вошедшие в подкуб, склеиваются за один прием. Результатом склеивания таких клеток является получение конъюнктивного терма (если склеиваются единичные клетки) или дизъюнктивного терма (если склеиваются нулевые клетки).
Контерм (конъюнктивный терм) – результат склеивания соседних минтермов, входящих в подкуб (соседних единичных клеток). В алгебраическом представлении контерм - есть конъюнкция переменных, имеющих неизменное значение в координатах строк и столбцов всех объединяемых клеток; если неизменное значение переменной в координатах равно 1, то в конъюнкции она записывается без инверсии, если равна 0 – то с инверсией.
На рис.2,а,б,в приведены примеры записи контермов 
для двухклеточных подкубов, а на рис.3,а,б,в,г,д – четырехклеточных (
) и восьмиклеточных (
).
МДНФ – есть дизъюнкция контермов.
Пример: МДНФ для ПФ y9 (рис.3,е) как результат минимизации по единичным значениям функции имеет вид:
. (5) Перейти на страницу: 1 2 3
Энергонезависимая память для телевизоров седьмого поколения Развитие вещательного телевидения идет по пути постоянного повышения качества телевизионного изображения и звукового сопровождения, расширения функциональных возможностей телевизора и п ...
Расчёт частотозадающих элементов принципиальной схемы передатчика радиолюбительского маячка В настоящей курсовой работе были приобретены умения и навыки расчёты частотозадающих элементов принципиальной схемы автогенератора, транзисторного усилителя мощности, схемы сложного вых ...
Защита информации от утечки по цепям питания Циркулирующая в тех или иных технических средствах конфиденциальная информация может попасть в цепи и сети электрического питания и через них выйти за пределы контролируемой зоны. Наприм ...