 |
| Principle of Duality (Contd...) |
|
| Theorem 6(a) (Demorgan's Law): |
| |
| Let B be a Boolean algebra, then |
| |
| (x + y)' = x'y' |
| |
|
| |
| 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' |
| |
|
| |
| 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' |
| |
|
| |
| 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. |
| |
| |
| |
 |
| |
