Disjunctive decomposition of Boolean functions.

It uses special notations:

Let x, δ ∈ {0, 1}.

x^δ = x, if δ =0; è (it follows) x^δ = 1, if x=δ;
x, if δ =1; 0, if x≠ δ;

f(x_1, x₂, …, x_n)=f(x₁, …, x_k, x_k+1, …, x_n) =

= ˅ (x₁^{δ 1} ˄ x₂^{δ 2} ˄ … ˄ x_k^{δ k} ˄ f(δ ₁, δ ₂ , …, δ _k, x_k+1, …x_n)); (1)

(δ ₁, δ ₂, …, δ _k)

Notation: ˅

(δ ₁, δ ₂, …, δ _k)

denotes repeated disjunction for all 2^k sets of values(δ ₁, δ ₂, …, δ _k). To prove that equation (1) is true we take an arbitrary set if argument values (a₁, a₂, …, a_n) and see if the left and right parts of (1) are equal.

f(a₁, a₂, …, a_n) = f(a₁, …, a_k, a_k+1, …, a_n) =

= ˅ ( a₁^{δ 1} ˄ a₂^{δ 2}˄ …˄ a_k^{δ k} ˄ f(δ ₁, δ ₂, …δ _k, a_k+1, …, a_n));

(δ ₁, δ ₂, …δ _k)

If any a_i≠ δ _i(i=1, …, k) then a_i^δ = 0, and the whole term

a₁^{δ 1} ˄ … ˄ a_i^{δ i}˄ … ˄ a_k^{δ k} ˄ f (δ ₁, …, δ _i, …, δ _k, a_k+1, …, a_n) = 0.

? 0? 0 or 1

Only on a single set of values, where all a_i = δ _i and a_i^δ = 1(i=1, …, k), we get

a_i^{δ 1} ˄ … ˄ a_k^{δ k} ˄ f (δ ₁, …, δ _2, a_k+1, …, a_n)=1 ˄ 1 ˄ …˄ 1 ˄ f(a₁, …, a_n). End of proof.

Ex: f(x, y, z) = ˄ (y˄ z ˅ ) = (y٠ z )).

Make a disjunctive decomposition by x and y.

f(x, y, z) = ˅ (x^{δ 1} ˄ y^{δ 2}˄ f (δ ₁, δ ₂, z)) = ٠ ٠ f(0, 0, z)˅ ٠ y٠ f(0, 1, z) ˅

4 sets of values of (δ ₁, δ ₂) ˅ x٠ ٠ f(1, 0, z)˅ x٠ y٠ f(1, 1, z) è below

٠ ٠ f(0, 0, y) = ٠ ٠ [ ٠ (0٠ z˅ ] = ٠ ٠ [1٠ (0˅ )] = 0 ٠ ٠ f(0, 1, y) = ٠ ٠ [ ٠ (1٠ z˅ )] = ٠ ٠ [1٠ (z˅ )] = ٠ y ٠ ٠ f(1, 0, y) = ٠ ٠ [ ٠ (….)] = ٠ ٠ 0 = ٠ ٠ f(1, 1, y) = ٠ ٠ [ ٠ (….)] = x٠ ٠ 0 = è f(x, y, z) = ˅ (xδ ٠ yδ ٠ f(δ 1δ 2 , y)) = 0 ˅ ٠ y ˅ 0 ˅ 0 = y. End

H/a: Check the result of the above composition by making a truth table for the original formula and by simplifying the given formula.

H/a: Decompose disjunctively the function f (x. y. z) = ()˅ ( by x and y.

Carollary 1 of (1): (disjunctive decomposition by 1 variable):

Any f(x₁, x₂, …, x_n) = ( ˄ f(0, x_2, ...x_n)) ˅ (x˄ f(1, x₂, …, x_n)).

Carollary2 of (1): (disjunctive decomposition by all variables):

Any f(x₁, x₂, …, x_n) = ˅ (x₁^{δ 1} ˄ x₂^{δ 2} ˄ …˄ x_n^{δ n}).

(δ ₁, δ ₂, …, δ _n) for which f(δ ₁, δ ₂, …, δ _n) = 1

H/a: Decompose the function f(x, y, z) =

a) by x

b) by x, y, z.