Используя законы булевой алгебры, можно преобразовывать исходные выражения в более простые (минимизировать их). По упрощенным выражениям можно построить техническое устройство, имеющее минимальные аппаратные затраты.
Минимизация производится с помощью применения законов склеивания и поглощения.
Пример.
Найти минимальную ДНФ функции Y=f (x1, x2, x3); f (0,2,3,4,5,7)=1.
Решение.
Построим таблицу истинности функции Y.
| x1 x2 x3 | f (x1, x2, x3) |
| 0 0 0 | |
| 0 0 1 | |
| 0 1 0 | |
| 0 1 1 | |
| 1 0 0 | |
| 1 0 1 | |
| 1 1 0 | |
| 1 1 1 |
По данным таблицы запишем аналитическое выражение:
Y= 
1 2 3 v 1x2 3 v 1x2x3 v x1 2 3 v x1 2x3 v x1x2x3
Из дискретного анализа известно, что существуют такие формулы представления функции, которые дальше уже нельзя упростить. Они называются сокращенными. Известно также, что не всякая сокращенная форма является минимальной. Однако минимальную по числу переменных следует искать среди сокращенных форм. Переход к сокращенной форме основан на последовательном применении двух операций: операции склеивания и операции поглощения.
Для выполнения операции склеивания в выражении функции выявляются пары членов вида
w x и w 
,
различающиеся лишь тем, что один из аргументов в одном из членов представлен без инверсии, а в другом – с инверсией. Затем проводится склеивание таких пар членов:
w xÚw =w (xÚ )=w
Результаты склеивания w в выражение функции.
Операция поглощения основана на равенстве
wÚw× z=w×(1Úz)=w
Член w поглощает член w×z. При проведении этой операции из логического выражения вычеркиваются все члены, поглощаемые членами, которые введены в результате операции склеивания. Операции склеивания и поглощения выполняются последовательно до тех пор, пока это возможно.
Для получения нормальной минимальной конъюнктивной формы логической функции имеются следующие особенности:
- исходной формой для минимизации логического выражения является СКНФ;
- пары склеиваемых членов имеют вид
w Ú x и wÚ ;
- операция поглощения проводится в соответствии с выражением
z (z Ú y) = z Ú zy= z (1Úy)= z.
Сокращенная форма может содержать лишние члены, исключение которых из выражения не повлияет на значение функции. Дальнейшее упрощение логического выражения достигается исключением из выражения лишних членов. В этом заключается содержание минимизации.
Получим:
Y= 1x2 v x2x3 v x1x3 v x1 2 v 2 3 v 1 3
Данная ДФ является избыточной, так как отдельные конъюнкции могут быть лишними, т.е. их составные части могут включаться в другие конъюнкции. У данной функции существует пять безызбыточных ДФ, из которых только две являются минимальными:
Y1= 1x2 v x1x3 v 2x3;
Y2= 1x2 v x2x3 v x1 2 v 1 3;
Y3= 1x2 v x1x3 v x1 2 v 1 3;
Y4= 1 3 v x2x3 v x1 2;
Y5= 1 3 v 1x2 v x1x3 v x1 2.
Их приведенных зависимостей видно, что только функции Y1 и Y4 являются минимальными формами функций, так как они содержат наименьшее число конъюнкций и имеют минимальный ранг этих конъюнкций.
Практика.
Для функций, заданных по Вашему варианту, построить таблицы истинности, аналитическое выражение в КФ и ДФ и попытаться его минимизировать. Записать инверсную функцию.
Варианты:
1) f (1,2,3,4) = 1; f (2,4,5,6,7) = 1; f (1,2,3,8,13,14,15) = 1;
2) f (1,2,4,5) = 1; f (3,4,5,6,7) = 1; f (1,2,4,8,12,14,15) = 1;
3) f (1,2,5,6) = 1; f (1,3,5,6,7) = 1; f (1,2,5,7,13,14,15) = 1;
4) f (1,2,6,7) = 1; f (1,3,4,6,7) = 1; f (1,2,4,9,11,12,15) = 1;
5) f (0,2,4,6) = 1; f (1,2,4,5,7) = 1; f (0,3,5,10,12,13,14) = 1;
6) f (0,3,5,6) = 1; f (0,1,2,6,7) = 1; f (1,2,3,5,7,10,14) = 1;
7) f (1,2,5,7) = 1; f (0,3,4,5,7) = 1; f (1,2,4,5,8,12,13) = 1;
8) f (0,4,5,7) = 1; f (1,2,3,6,7) = 1; f (4,5,6,8,9,11,12) = 1;
9) f (0,1,2,3) = 1; f (3,4,5,6,7) = 1; f (8,9,11,12,13,14,15) = 1;
10) f (2,3,4,5) = 1; f (0,1,3,6,7) = 1; f (7,10,11,12,13,14,15) = 1;
11) f (3,4,5,6) = 1; f (0,1,2,5,7) = 1; f (0,4,8,12,13,14,15) = 1;
12) f (1,2,3,5) = 1; f (0,3,4,6,7) = 1; f (2,4,7,8,9,12,15) = 1;
13) f (1,2,3,6) = 1; f (0,2,4,5,7) = 1; f (3,6,9,12,13,14,15) = 1;
14) f (1,2,3,7) = 1; f (0,1,4,6,7) = 1; f (2,4,6,8,11,13,15) = 1;
15) f (1,2,4,6) = 1; f (0,1,4,5,7) = 1; f (0,5,7,10,11,12,13) = 1;
16) f (1,2,4,7) = 1; f (0,2,4,6,7) = 1; f (1,6,9,10,11,12,14) = 1;
17) f (0,1,3,6) = 1; f (1,2,4,5,6) = 1; f (0,2,4,9,11,12,13) = 1;
18) f (0,1,4,5) = 1; f (1,2,3,4,6) = 1; f (0,1,4,5,8,9,12) = 1;
19) f (0,1,3,5) = 1; f (1,2,4,6,7) = 1; f (1,2,4,15,9,10,12) = 1;
20) f (1,5,6,7) = 1; f (0,1,2,3,4) = 1; f (6,7,9,11,12,13,15) = 1;