Boolean Algebra


   
 
Principle of Duality (Contd...)
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)
 
From (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
 
(xy)' = x' + y'
 
Proof:
 
By definition of complement of an element it is sufficient to prove
 
xy + (x' + y') = 1
 
and 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)
 
xy (x' + y')
 
= 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.
 
 
 
 
     
   
Get unlimited tutoring in Math, English, Physics, Chemistry, Biology, Algebra, Geometry and all other subjects at $99.99 per month!

(100% money-back guarantee)

Customer Care

Click to get customer service, technical support and subscription help.

Customer Care Chat


Refer-A-Friend

Get One Month Free!
When you refer a friend