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)

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

(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.