МИНИМИЗАЦИЯ ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ

в вычислительной технике, системах автоматического (автоматизированного) управления и контроля, возникает

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

функции в смысле наименьшего числа входящих в нее символов (букв).

Процесс получения такого представления будем называть минимизацией.

функциональной полной системе элементных переключательных функций. Наиболее детально такие методы

разработаны для систем из дизъюнкции, конъюнкции и инверсии.

импликанты, простой импликанты, имплиценты и простой имплиценты.
Пусть f(x), g(x), p(x)

– полностью определенные функции, причем под х понимается некоторый набор из n переменных (х1х2...хn).
Функция f(х) определена на рабочих (единичных) наборах М1[f(х)] и множестве запрещенных (нулевых) наборов М0[f(х)].
Функция g(x) определена на множестве рабочих (единичных) наборов М1[g(x)], а функция р(х) – на множестве запрещенных (нулевых) наборов М0[р(х)].

рабочих (единичных) наборов функции g(х) совпадает или является подмножеством множества

рабочих наборов функции f(х), т.е. М1[g(x)]⊆ М1[f(x)], где ⊆ – знак включения в множество, означающий, что всякий элемент левого множества является элементом правого множества. При этом говорят, что М1[f(x)] содержит М1[g(x)], т.е. в соответствии с определением импликации g(x)→f(x).

запрещенных (нулевых) наборов функции р(х) совпадает или является подмножеством множества

запрещенных (нулевых) наборов функции f(х), т.е. М0[р(x)]⊆ М0[f(x)].

членов (конституент) и многократного использования (по возможности) закона склеивания, пока

не останется конъюнкций, отличающихся значениями одной переменной.

g(х), являющаяся импликантой функции и обладающая тем свойством, что никакая

ее собственная часть уже не является импликантой.

любого числа импликант переключательной функции также является импликантой этой функции;

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

или несколько простых импликант, не нарушая количества необходимых рабочих наборов.

Такие простые импликанты назовем лишними.
Исключение лишних простых импликант из сокращенной ДНФ – второй этап минимизации.

отсутствуют лишние простые импликанты.
Устранение лишних простых импликант из сокращенной ДНФ

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

путем построения и перебора всех тупиковых ДНФ и выбора из

них самой минимальной, называется общей (абсолютной) тупиковой ДНФ.

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

одной или нескольких тупиковых ДНФ, из которых выбирают минимальную, – её называют частной минимальной ДНФ и считают близкой к общей (абсолютной).

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

доопределение за счет условных наборов, которое соответствует минимальной ДНФ, содержащей наименьшее число букв.

склеивании при возможности всех конституент (членов СДНФ). Для этого каждая

конституента сравнивается с последующими, что приводит к получению импликант. Полученные импликанты вновь подвергаются сравнению и при возможности склеиваются – и т.д. до тех пор, пока оставшиеся импликанты уже не будут поддаваться склеиванию. Это и есть простые импликанты, их дизъюнкция представляет собой сокращенную ДНФ.

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

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

использования ЭВМ. Формализация заключается в записи конституент единицы (членов СДНФ)

их двоичными номерами. Все номера разбиваются на непересекающиеся группы по числу единиц в двоичном номере. Склеивания производятся только между соседними группами. Ликвидируемый разряд обозначается знаком «–» («тире»). Дальнейшие группы из полученных импликант образуются с учетом однинакового расположения тире. Такое обозначение импликант называется обобщенными кодами

единицы по числу единиц:

далее производится по импликантной таблице

ее произвольной ДНФ, а не по СДНФ, как в методах

Квайна и Квайна-Мак-Класки, используя закон обобщенного склеивания

как полностью определенных, так и не полностью определенных переключательных функций,

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

позволяет графически получать экономное покрытие переключательной функции правильными конфигурациями её

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

Карно в классе ДНФ заключается в покрытии ее единиц минимальным

количеством максимальных правильных контуров. В эти контуры могут включаться и условные наборы. Контуры могут пересекаться, но не могут включаться друг в друга – иначе не получатся простые импликанты.

переменных могут быть следующие:
одноклеточный – одна клетка с единицей, окруженная

нулями;
двухклеточный – две соседние клетки, окруженные нулями;

соседних клеток, окруженных нулями;

соседних клеток, окруженных нулями;

минимизация в классе КНФ. В этом случае каждому контуру из

нулей с возможным добавлением «тильд» соответствует имплицента – член КНФ, которая строится также из переменных, не меняющих своего значения в номере клеток «нулевого» контура, только, если переменная в номере клетки равна нулю, то в КНФ она будет без инверсии, а если равна единице – то в КНФ она будет с инверсией.