Дискретная математика

94 gk Рис. 3.8 Можно доказать следующую теорему. Теорема 3.26. Булева функция f(X), зависящая от п переменных, допускает двумерную разделительную декомпозицию кратности к тогда и только тогда, когда декомпозиционная матрица функции f(X), соответствующая заданному разбиению множества X на непересекающиеся подмножества J?" и Х', содержит не более чем 2* различных столбцов. Для ф у н к ц и и = Xi&X4=:i>(X2::^ Хз) =>(Х2= Х3) ПрИ = (xi.x^) VI Х' =(х2,хз) её декомпозиционная матрица содержит три различных столбца значений этой функции, т.е. не более чем 2^ различных столбца. Следовательно, /г допускает двумерную разделительную декомпозицию кратности 2 для заданных х" - (xj.x^) иХ' =('xj,xj). Ясно, что имеем; f2(XuX2,Xi,X4) =go(^~gi(X'), g2(X')), где go(X^. S,t)=-(x,&x^)z:>s=>t, g,(X ')=X2=>X3, g2(X')=X2^Xi. в настоящее время получены критерии и для некоторых других видов как разделительной, так и неразделительной декомпозиций.