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

91 Рис. 3.6 Сложность схемы из функц-ионалъных элементов - это число функциональных элементов в этой схеме. Приведённая на Рис. 3.6 схема имеет сложность 9. § 21. Функциональная декомпозиция Пусть задана произвольная булева функция f(xi,x2,...,x,j. Обозначим А'= (xi,x2,...,xj, тогда исходную функцию можно записать: f(JQ. Декомпозицией булевой функции f(X) называется представление ее в виде f(X)=go(X''.g,(X').....g,(r)), где к>1, т>1, X - некоторое подмноисество множества переменных^ т.е. X' = ,Xi^ , \.< ij<n, , \<j<k(i), \ <k(i)<n, \<i<m: gi(X) - некоторая булева функция, зависящая от мнолсества переменных^', 1<1<к, 1 </'<т. Рассмотрим пример. Пусть f(x,y,z)=x:::i>y&z; X={x,y.z} : У= {х}, Х' ={у, z}. lQVixa.f(x,y.z) = gB(X". gj(X')) =gn(x, g,( y.zj ), где go{x,y) = x=^y, g,(x.y)=x&y. В зависимости от введенных выше чисел т и к, а также от способа разбиения множества X на подмножества X различают несколько видов функциональной декомпозиции. Если булева функция f(X) допускает декомпозицию при к=\ и т = 1, т.е. f(X)=goiX",g,(X')), то такая декомпозиция называется простой. ^1ксло множеств X ' называется размерностью декомпозиции, а число к- кратностыо deKOMnosuijuu. Размерность декомпозиции равна т+1. Если декомпозиция выполняется при условии, чтоХ'пХ' =0для любых i, j, i^j\ то декомпозиция называется разделительной. Если хотя бы одно пересечение подмножеств X ' w. Х-' не пусто, то декомпозиция называется неразделительной.