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

93 Теперь построим декомпозиционную матрицу для X" = (х^х^) и х' =(Х2,Х}). Эта матрица для функцииfi(x],x2,xi,x4) имеет вид: X' \ X 00 01 10 11 00 0 0 0 1 01 1 1 1 1 10 1 1 1 1 11 0 0 0 1 Можно доказать следующую теорему. Теорема 3.25. Булева функция f(X), зависящая от п переменных, допускает двумерную разделительную декомпозицию кратности один тогда и только тогда, когда декомпозиционная матрица, соответствующая { заданному разбиению множества X на непересекающиеся подмножества и | Х\ содержит не более двух различньпс столбцов значений функций. Из этой теоремы следует, что в рассмотренном примере функция /, допускает требуемую декомпозицито, ибо декомпозиционная матрица имеет только два различных столбца значений функции/, для заданных ^ = (x^Xi) яХ' =(х2,хз). Ясно, что имеем: f,(X,,X2,X3,X4) =go(^,gi(X')), где goCX".s)=(x,^X4)^s, g,(X')-=X2&X3. Рассмотрим ещё функцию fiixj.xi.xb.xd - Х]&Х4=!>(Х2^ хд) =^(х2= хз). Положим, что = (xi,x4) и Х' =(х2,хз). Значения этой функции приведены в записанной ранее таблице истинности. Тогда декомпозиционная матрица для f2(x:i,x2,x3,x4) имеет следующий вид: у \ X' 00 01 10 и 00 1 0 0 1 01 1 0 0 1 10 1 0 0 1 и 1 0 1 1 Построенная декомпозиционная матрица содержит три различных столбца значений функции,/^ поэтому эта функция не допускает двумерную разделительную декомпозицию кратности один при заданных = ( XI.XJ) И Х' = (Х2,Хз). Двумерной разделительной декомпозицией кратности к функции / является ее представление в виде: f(X)=go(J^,g,(X'), g2(X'),...,gUX')). Структурная (функциональная) схема ее представлена на рис.3.8.