Декомпозиция булевых функций.

Задача декомпозиции булевой функции в общем случае состоит в таком разделении множества ее аргументов на ряд подмножеств, при котором можно выразить исходную функцию f(x) через вспомогательную промежуточную функцию j(z), где zÌx.

В частном случае имеет место так называемая простая разделительная декомпозиция, при которой множество аргументов x разделяется на два непересекающихся подмножества (z,w®(zÇw=j;zÈw=x)) и приведение исходной функции к виду f(x)=f(j(z,w)).

Пример: f³(x)=V(1,2,4,7)

(f=1)

z=(x₂x₃) W={x₁}

_ _

j(z)=x₂x₃vx₂x₃

_ _

f(x)=x₁j(z)vx₁j(z) S_Q=13

S_Q=13 T=5t

Дата добавления: 2015-08-02