Theorems of Boolean algebra

Theorems of Boolean algebra:

The theorems of Boolean algebra can be used to simplify many a complex Boolean expression and also to transform the given expression into a more useful and meaningful equivalent expression. The theorems are presented as pairs, with the two theorems in a given pair being the dual of each other. These theorems can be very easily verified by the method of ‘perfect induction‘. According to this method, the validity of the expression is tested for all possible combinations of values of the variables involved. Also, since the validity of the theorem is based on its being true for all possible combinations of values of variables, there is no reason why a variable cannot be replaced with its complement, or vice versa, without disturbing the validity. Another important point is that, if a given expression is valid, its dual will also be valid

Theorem 1 (Operations with ‘0‘ and ‘1‘)

(a) 0.X = 0 and (b) 1+X= 1

Where X is not necessarily a single variable – it could be a term or even a large expression.

Theorem 1(a) can be proved by substituting all possible values of X, that is, 0 and 1, into the given expression and checking whether the LHS equals the RHS:

• For X = 0, LHS = 0.X = 0.0 = 0 = RHS.

• For X= 1, LHS = 0.1 = 0 = RHS.

Thus, 0.X =0 irrespective of the value of X, and hence the proof.

Theorem 1(b) can be proved in a similar manner. In general, according to theorem 1,

0. (Boolean expression) = 0 and 1+ (Boolean expression) =1.

For example: 0. (A.B+B.C +C.D) = 0 and 1+ (A.B+B.C +C.D) = 1, where A, B and C are Boolean variables.

Theorem 2 (Operations with ‘0‘ and ‘1‘)

(a) 1.X = X and (b) 0+X = X

where X could be a variable, a term or even a large expression. According to this theorem, ANDing a Boolean expression to ‘1‘ or ORing ‘0‘ to it makes no difference to the expression:

• For X = 0,  LHS = 1.0 = 0 = RHS.

•  For X = 1, LHS = 1.1 = 1 = RHS. Also,

1. (Boolean expression) = Boolean expression and 0 + (Boolean expression) = Boolean expression.

For example,

1.(A+B.C +C.D) = 0+(A+B.C +C.D) = A+B.C +C.D

Theorem 3 (Idempotent or Identity Laws)

(a) X.X.X……X = X      and             (b) X+X+X +···+X = X

Theorems 3(a) and (b) are known by the name of idempotent laws, also known as identity laws.

Theorem 3(a) is a direct outcome of an AND gate operation, whereas theorem 3(b) represents an OR gate operation when all the inputs of the gate have been tied together. The scope of idempotent laws can be expanded further by considering X to be a term or an expression. For example, let us apply idempotent laws to simplify the following Boolean expression:

Theorem 4 (Complementation Law)

(a) X_X = 0          and    (b) X+X = 1

According to this theorem, in general, any Boolean expression when ANDed to its complement yields a ‘0‘ and when ORed to its complement yields a‘1‘, irrespective of the complexity of the expression:

Hence, theorem 4(a) is proved. Since theorem 4(b) is the dual of theorem 4(a), its proof is implied.

The example below further illustrates the application of complementation laws:

Theorem 5 (Commutative property)

Mathematical identity, called a ‖property‖ or a ‖law,‖ describes how differing variables relate to each other in a system of numbers. One of these properties is known as the commutative property, and it applies equally to addition and multiplication. In essence, the commutative property tells us we can reverse the order of variables that are either added together or multiplied together without changing the truth of the expression:

Commutative property of addition

A + B = B + A

Commutative property of multiplication

AB = BA

Theorem 6 (Associative Property)

The Associative Property, again applying equally well to addition and multiplication. This property tells us we can associate groups of added or multiplied variables together with parentheses without altering the truth of the equations.

Associative property of addition

A + (B + C) = (A + B) + C

Associative property of multiplication

A (BC) = (AB) C

Theorem 7 (Distributive Property)

The Distributive Property, illustrating how to expand a Boolean expression formed by the product of a sum, and in reverse shows us how terms may be factored out of Boolean sums-of-products:

Distributive property

A (B + C) = AB + AC

Theorem 8 (Absorption Law or Redundancy Law)

(a) X+X.Y = X     and  (b) X.(X+Y) = X

The proof of absorption law is straightforward:

X+X.Y = X. (1+Y) = X.1 = X

Theorem 8(b) is the dual of theorem 8(a) and hence stands proved.

The crux of this simplification theorem is that, if a smaller term appears in a larger term, then the larger term is redundant. The following examples further illustrate the underlying concept: