Разложение Шенонна: __ F(X1,...,Xp, ..., Xn) = Xp * F(X1, ..., 0,...Xn) + Xp * F(X1,...,1,..Xn) Обозначим G0 = F(X1,...,0,...Xn), G1 = F(X1,...,1,...Xn) и в самом деле, если Xp = 0, то F = 1 * G0 + 0 * G1 = G0 = F(X1,...,0,..Xn) а если Xp = 1, то F = 0 * G0 + 1 * G1 = G1 = F(X1,...,1,...Xn). Разложение Шеннона
Из двойственности булевой алгебры следует, что есть еще разложение вида: _ F(X1,...,Xp,...,Xn) = [Xp + F(X1,...,0,..Xn)] * [Xp + F(X1,...,1,...Xn)] Все тоже самое: Если Xp = 0, то: F = (0 + G0) * (1 + G1) = G0 * 1 = G0 = F(X1,...,0,...Xn) а если Xp=1 то: F = (1 + G0) * (0 + G1) = 1 * G1 = G1 = F(x1,...,1,...Xn)
Как известно, если X * Y = 0 то X + Y = X (+) Y ----------------------------- X Y X*Y X+Y X(+)Y ----------------------------- 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 ----------------------------- 1 1 1 1 0 ----------------------------- Рассмотрим Разложение Шеннона: _ F = Xp * G0 + Xp * G1 _ _ (Xp * G0) * (Xp * G1) = (Xp * Xp) * (G0 * G1) = 0 * G0 * G1 = 0 Таким образом мы можем заменить в разложении Шеннона OR на XOR: _ F = Xp * G0 (+) Xp * G1 = = (1 (+) Xp) * G0 (+) Xp * G1 = = G0 (+) Xp * G0 (+) Xp * G1 = = G0 (+) (G0 (+) G1) * Xp Это называется разложением Рида. Разложение Рида
Попробуем разложить функцию 2 переменных по обеим переменным: (пишем + имеем в виду XOR): F(x2,x1) = F(0,x1) + [F(0,X1) + F(1,X1)] * x2 = = F(0,0) + [F(0,0) + F(0,1) ] * x1 + [ { F(0,0) + [F(0,0) + F(0,1) ] * x1 } + { F(1,0} + [F(1,0) + F(1,1) ] * x1 } ] * x2 = = F(0,0) + [ F(0,0) + F(0,1) ] * x1 + [ F(0,0) + F(1,0) ] * x2 + [ F(0,0) + F(0,1) + F(1,0) + F(1,1) ] * x1 * x2 Таким образом: F = A0 + A1*x1 + A2*x2 + A3*x1*x2 имеет коэффициенты: A0 = F(0,0) A1 = F(0,0) (+) F(0,1) A2 = F(0,0) (+) F(1,0) A3 = F(0,0) (+) F(0,1) (+) F(1,0) (+) F(1,1)
Попробуем выразить импликацию x1->x2 -------------- x2 x1 x1->x2 -------------- 0 0 1 0 1 0 1 0 1 1 1 1 -------------- A0 = 1 A1 = 1 (+) 0 = 1 A2 = 1 (+) 1 = 0 A3 = 1 (+) 0 (+) 1 (+) 1 = 1 таким образом импликация в полиномальной форме будет иметь вид: IMP_x1_x2(x2,x1) = 1 + x1 + x1*x2