|
Unlimited Tutoring & Homework Help
|
Theorem 6(a) (Demorgan's Law):
Let
B be a Boolean algebra, then
(x + y)' = x'y'
Proof:
We have to prove the complement of x + y = x'y'.
By definition of complement, it is sufficient to show(x + y) + x'y' = 1
(x + y)(x'y') = 0(x + y) + x'y' = (y + x) + x'y' (Axiom 3a)
= y + x + x'y' (Associative)= y + (x + x').(x + y') (Axiom 4b)
= y + 1(x + y') (Axiom 5)= y + (x + y') (Axiom 2b)
= y + y' + x (Associative of +)= 1 + x (Axiom 5)
= x + 1 (Axiom 3a)= 1 (Theorem 2a)
(x + y) + x'y' = 1 …(1)
(x + y)x'y' = ((x + y)x')y' Associativity
= (x'(x + y))y = (x'x + x'y)y' (Axioms 3a, 4a)= (0 + yx')y' (Axiom 5)
= (yx')y'= yy' x' (Axiom 3a)
= 0.x' (Axiom 5)= 0
(x + y)x'y' = 0 …(2)Fr
om (1) and (2), the complement of x + y is x'y' is
(x + y)' = x'y'
Theorem 6(b):
Let B be a Boolean algebra, for all x, y
B
Proof:
By definition of complement of an element it is sufficient to prove
xy + (x' + y') = 1and xy(x' + y') = 0
xy + (x' + y')= (xy + x') + y' (Associativity of +)
= (x + x')(y + x') + y' (Axiom 4b)= 1(y + x') + y' (Axiom 5)
= y + x' + y' (2b) or 1 . x = x= y + y' + x' (Axiom 3a)
= 1 + x' (Axiom 5)= x' + 1 (Axiom 3 a)
= 1 (Theorem 2a)
xy + (x' + y') = 1 ….(1)
= yx(x' + y') (Axiom 3b)
= y(xx' + xy') (Axiom 4a)= y(0 + xy') (Axiom 5)
= yxy' (Axiom 2a)= yy'x (Axiom 3a)
= 0.x = x.0 (3a and theorem 2b)= 0
xy(x' + y') = 0 …(2)
From (1) and (2), we have
(xy)' = x' + y'Boolean Functions
An expression consisting of combinations of binary operations +, . and unary operation and a finite number of elements of a Boolean algebra is called a Boolean function.
Example:
F = x + y'z
A Boolean function is an expression with logical relationship between binary variables. It is evaluated by determining the binary value of the expression for all possible values of the variables.

