Рассмотрим правило склеивания в методе карт Карно.
Упрощение выражений переключательных функций (минимизация) основывается на понятии несущественности переменных. Переменная называется несущественной на паре наборов, если, при изменении ее значения на противоположное, переключательная функция сохраняет свое значение.
Например, для переключательной функции трех переменных f (1,3,5,6,7) = 1 шестая и седьмая конъюнкции имеют вид x1 x2 x 3, x1 x2 x3. Тогда по дистрибутивному закону x1 x2 x 3 v x1 x2 x3 = x1 x2 (x3 v x3 ) = x1x2.
То есть, две конъюнкции, содержащие несущественную переменную, заменяются одной, в которой несущественная переменная отсутствует.
В кубическом виде склеивание имеет следующую интерпретацию: 1 1 0 1 1 1 = 1 1 X, что соответствует конъюнкции x1x2.
Приведем основные определения, используемые при минимизации переключательных функций. Данные определения используют понятия нормальных (канонических) форм булевых функций.
Число переменных, входящих в элементарную конъюнкцию (для ДНФ) или в элементарную дизъюнкцию (для КНФ) называется ее рангом.
В основе любых методов минимизации лежит операция склеивания.
Два элементарных произведения одного ранга (для ДНФ) или элементарных суммы одного ранга (для КНФ) склеиваются, если они различаются только по одной переменной.
Для ДНФ: операция Аx v A = A называется полным склеиванием; операция Аx v A = A v Аx v A называется неполным склеиванием.
Для КНФ: операция ( А v x )·( A v … ) = A называется полным склеиванием; операция ( А v x )·( A v … ) = A· ( А v x )· ( A v … ) называется неполным склеиванием.
Пример полного склеивания: (x1 v x2 v x3)· (x1 v x2 v 3) = x1 v x2.
Пример неполного склеивания: x1x2x3 v x1x23 = x1x2 v x1x2x3 v x1x23 .
Импликантой называется элементарное произведение, равное единице на одном или нескольких наборах, где данная функция равна 1, и равное нулю на всех наборах, где функция равна 0. Импликанта покрывает один или несколько минтермов рассматриваемой переключательной функции. Обычно, импликанта - результат склеивания соответствующих минтермов или импликант.
Простая импликанта содержит хотя бы минтерм функции, но перестает быть импликантой после удаления любого аргумента (иными словами, это импликанта, к которой нельзя применить операцию склеивания).
Сокращенная ДНФ - дизъюнкция всех простых импликант.
Существенная импликанта - простая импликанта, образованная склеива-нием таких минтермов, что, по крайней мере, для одного из них данная опера-ция была единственной. Существенные импликанты образуют ядро функции.
Тупиковая ДНФ - дизъюнкция простых импликант, из которых ни одна не является лишней.
МДНФ (минимальная ДНФ) - тупиковая ДНФ с минимальным числом вхождений переменных (минимальным числом букв) по сравнению с другими тупиковыми формами этой функции.
Имплицентой называется элементарная логическая сумма, равная 0 на одном или нескольких наборах, где данная функция равна 0, и равная 1 на всех наборах, где данная функция равна 1. Имплицента покрывает один или несколько макстермов рассматриваемой булевой функции. Обычно, имплицента -результат склеивания соответствующих макстермов.
Простая имплицента содержит хотя бы макстерм функции, но перестает быть имплицентой после удаления любого аргумента (имплицента, к которой нельзя применить операцию склеивания).
Сокращенная КНФ - конъюнкция всех простых имплицент.
Существенная имплицента - простая имплицента, образованная склеива-нием таких макстермов, что, по крайней мере, для одного из них данная опера-ция была единственной. Существенные имплиценты образуют ядро функции.
Тупиковая КНФ - конъюнкция простых имплицент, из которых ни одна не является лишней.
МКНФ (минимальная КНФ) - тупиковая КНФ с минимальным числом вхождений переменных (минимальным числом букв) по сравнению с другими тупиковыми формами этой функции.