8.2. Основные понятия и определения, используемые при минимизации

При минимизации переключательных функций существенную роль играют понятия импликанты, простой импликанты, имплиценты и простой имплиценты [14]. Пусть f(x), g(x), p(x) – полностью определенные функции, причем под х понимается некоторый набор из n переменных (х₁х₂...х_n). Функция f(х) определена на рабочих (единичных) наборах М₁[f(х)] и множестве запрещенных (нулевых) наборов М₀[f(х)]. Функция g(x) определена на множестве рабочих (единичных) наборов М₁[g(x)], а функция р(х) – на множестве запрещенных (нулевых) наборов М₀[р(х)].

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

Переключательная функция р(х) является имплицентой переключательной функции f(х), если множество запрещенных (нулевых) наборов функции р(х) совпадает или является подмножеством множества запрещенных (нулевых) наборов функции f(х), т.е. М₀[р(x)] М₀[f(x)].

Пусть функция в СДНФ имеет вид:

f(x₁x₂x₃)=x₁ x₂ x₃  x₁ x₂x₃  x₁x₂x₃;

g₁(x)=x₁ x₂ x₃ (конституента СДНФ);

g₂(x)= х₁ х₂x₃ (конституента СДНФ);

g₃(x)= х₁ х₂ х₃ (конституента СДНФ);

g₄(x)= f(х), т.е. сама функция в СДНФ.

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

Так:

Группировка первой и второй конституенты не позволяет применить закон склеивания:

Других вариантов комбинаций и склеиваний для f(х) нет.

Простой импликантой функции f(х) называется любая элементарная конъюнкция в g(х), являющаяся импликантой функции и обладающая тем свойством, что никакая ее собственная часть уже не является импликантой. В примере импликанты g₅=х₁х₂, g₆=х₂х₃ являются простыми импликантами функции f. Импликанты g₁, g₂, g₃, g₇ и, естественно, g₄ – не являются простыми, т.к. их части являются импликантами функции f: например, g₅ является частью g₂ (g₃). Говорят, что простые импликанты покрывают или поглощают соответствующие конституенты.

В булевой алгебре переключательных функций утверждается и доказывается: 1) дизъюнкция любого числа импликант переключательной функции также является импликантой этой функции; 2) любая переключательная функция равносильна дизъюнкции всех своих простых импликант, и такая форма ее представления называется сокращенной ДНФ (СкДНФ). Рассмотренный перебор всех возможных импликант переключательной функции f дает возможность убедиться, что простых импликант всего две: g₅, g₆. Тогда сокращенная ДНФ функции f имеет вид:

f=g₅g₆=х₁х₂х₂х₃.

Рабочими наборами функции f(х₁х₂х₃) являются 011, 110, 111 (табл. 34). Из таблицы видно, что импликанты g₅, g₆ в совокупности покрывают своими единицами все единицы функции f, т.е. рабочие наборы сокращенной ДНФ = 110, 111, 011, 111, последний повторяется дважды. Получение сокращенной ДНФ – первый этап минимизации.

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

Таблица 34

Таблица истинности импликант

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

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

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

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

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

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