Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
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(x1, x2, …, xn)=f(x1, …, xk, xk+1, …, xn) =
= ˅ (x1δ 1 ˄ x2δ 2 ˄ … ˄ xkδ k ˄ f(δ 1, δ 2 , …, δ k, xk+1, …xn)); (1)
(δ 1, δ 2, …, δ k)
Notation: ˅
(δ 1, δ 2, …, δ k)
denotes repeated disjunction for all 2k sets of values(δ 1, δ 2, …, δ k). To prove that equation (1) is true we take an arbitrary set if argument values (a1, a2, …, an) and see if the left and right parts of (1) are equal.
f(a1, a2, …, an) = f(a1, …, ak, ak+1, …, an) =
= ˅ ( a1δ 1 ˄ a2δ 2˄ …˄ akδ k ˄ f(δ 1, δ 2, …δ k, ak+1, …, an));
(δ 1, δ 2, …δ k)
If any ai≠ δ i(i=1, …, k) then aiδ = 0, and the whole term
a1δ 1 ˄ … ˄ aiδ i˄ … ˄ akδ k ˄ f (δ 1, …, δ i, …, δ k, ak+1, …, an) = 0.
? 0? 0 or 1
Only on a single set of values, where all ai = δ i and aiδ = 1(i=1, …, k), we get
aiδ 1 ˄ … ˄ akδ k ˄ f (δ 1, …, δ 2, ak+1, …, an)=1 ˄ 1 ˄ …˄ 1 ˄ f(a1, …, an). 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 (δ 1, δ 2, z)) = ٠ 
٠ f(0, 0, z)˅ ٠ y٠ f(0, 1, z) ˅
4 sets of values of (δ 1, δ 2) ˅ 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(x1, x2, …, xn) = ( ˄ f(0, x2, ...xn)) ˅ (x˄ f(1, x2, …, xn)).
Carollary2 of (1): (disjunctive decomposition by all variables):
Any f(x1, x2, …, xn) = ˅ (x1δ 1 ˄ x2δ 2 ˄ …˄ xnδ n).
(δ 1, δ 2, …, δ n) for which f(δ 1, δ 2, …, δ n) = 1
H/a: Decompose the function f(x, y, z) = 
a) by x
b) by x, y, z.