1.5.7. Разложение булевых функции
Пусть дан булевый вектор (x1; x2;. . .…xn), компоненты которого принимают значения siÎ{0; 1}. Тогда
Конъюнкция нескольких xisi в пределах заданного булевого вектора определяет формулу специального вида Kj=(x1s1×x2s2×…×xnsn), которую называют элементарной конъюнкцией.
Дизъюнкция элементарных конъюнкций по известным наборам значений булевого вектора есть разложение логической функции в дизъюнктивную нормальную форму (ДНФ).
Дизъюнкция xisi в пределах заданного булевого вектора определяет формулу специального вида D=(x1s1Úx2s2Ú…Úxnsn), которую называют элементарной дизъюнкцией.
Конъюнкция элементарных дизъюнкций по известным наборам значений булевого вектора есть разложение в конъюнктивную нормальную форму (КНФ).
1.5.7.1. Днф булевой функции
Всякая логическая функция f(x1; x2;...xn) может быть представлена в виде:
f(x1; x2;...xn)=Ú(x1s1×x2s2×…×xmsm)×f(s1; s2;¼sm; xm+1;…xn)),
где m£n, а дизъюнкция берётся по всем m наборам значений переменных (s1; s2;…sm).
Пусть m=1, тогда
f(x1; x2;…xn)=x1×f(1; x2;...xn)Ú`x1×f(0; x2;¼xn).
Пусть m=2, тогда
f(x1; x2;…xn)=x1×x2×f(1; 1;¼xn)Úx1×`x2×f(1; 0;…xn)Ú`x1×x2×f(0; 1;…xn)Ú `x1×`x2×f(0; 0;¼xn).
Пусть m=n, тогда
f(x1;x2;…xn)=Úx1s1×x2s2×…×xnsn×f(s1; s2;...sn).
Чтобы элементарная конъюнкция (x1s1×x2s2×…×xnsn) представляла логическую функцию f(x1;x2;…;xn) необходимо иметь f(s1;s2;…sn)=1, т.е.
f(x1;x2;…xn)=Úx1s1×x2s2×…×xnsn×1.
Если f(s1;s2;…sn)=0, то f(x1;x2;…xn)=Úx1s1×x2s2×…×xn ×0 = 0.
Функцию f(s1; s2;…sn)=1 называют конституентой единицы. Тогда любую булеву функцию, значение которой равно 1, представляет дизъюнкция элементарных конъюнкций булевых переменных булевого вектора.
Если элементарные конъюнкции в разложении имеют одинаковые число и имена булевых переменных, то разложение формирует совершенную дизъюнктивную нормальную форму формулы булевой функции (СДНФ).
Например, F=x1×x2×x3×x4Ú`x1×`x2×x3×x4Úx1×`x2×`x3×`x4 есть СДНФ.
Если логическая функция задана таблицей, то формулу СДНФ можно записать по значениям булевых переменных для булевой функции, имеющей значение “1”.
Например, для функции, заданной таблицей 1.25, имеем: F=x1×`x2×x3×`x4Úx1×x2×`x3×`x4
-
таблица 1.25
булевый вектор
функция
x1
x2
x3
x4
y=f(x1; x2; x3; x4)
0
0
0
1
f(0;0;0;1)=0
1
0
1
0
f(1;0;1;0)=1
1
1
0
0
f(1;1;0;0)=1
0
1
1
0
f(0;1;1;0)=0
...
...
...
...
...
Алгоритм преобразования формулы к СДНФ:
Шаг 1: преобразовать формулу так, чтобы в ней были только операции дизъюнкции, конъюнкции и отрицания;
Шаг 2: преобразовать формулу так, чтобы операция отрицания была применима только к двоичным переменным;
Шаг 3: если в некоторую конъюнкцию не входит переменная xi, то дополнить её выражением (xi Úxi) и выполнить преобразования формулы по закону дистрибутивности:
F=x1s1×x2s2×…×xksk×(xiÚxi)=x1s1×x2s2×…×xksk×xi Úx1s1×x2s2×…×xksk×xi;
Шаг 4: если в некоторую конъюнкцию не входит переменная xj, то повторить шаг 3, иначе - конец.
Пример: преобразовать формулу F=x1×x2Ú`x1×`x2×x3×x4 к виду СДНФ.
F=x1×x2×(x3Ú`x3)Ú`x1×`x2×x3×x4;
F=x1×x2×x3Úx1×x2×`x3Ú`x1×`x2×x3×x4;
F=x1×x2×x3×(x4Ú`x4)Úx1×x2×`x3×(x4Ú`x4)Ú`x1×`x2×x3×x4;
F=x1×x2×x3×x4Úx1×x2×x3×`x4Úx1×x2×`x3×x4Úx1×x2×`x3×`x4)Ú`x1×`x2×x3×x4.