BOOLEAN ALGEBRA

The circuits in digital computers follow the logic of the mind. Hence symbolic logic, invented by Boolean for solving logical problems, can be applied in the analysis and design of digital circuits. This logic is a binary or two-valued logic and resembles ordinary algebra in many respects. Hence this logic is also called Boolean algebra.

Boolean algebra permits only two values or states for a variable. In logic, these two states represent 'true' and 'false' and in circuits, they represent 'on' and 'off' or the 'cutoff' and 'saturation' states of Boolean of an electronic device. The two permitted states of Boolean algebra are usually represented by 0 and 1.

Only three operations are employed in Boolean algebra. These operations are:

1. The OR addition is represented by a plus (+) sign.
2. The AND multiplication is represented by the cross (X) or a dot (.) sign.
3. The NOT operation is represented by a bar over a variable.

The operations indicated by the symbol + and (.) are not the same in ordinary algebra.

The principle of duality is an important concept in Boolean algebra, particularly in proving various theorems. Briefly stated the principle of duality pronounces that given an expression which is always valid in boolean algebra, the dual expression is also always valid. The dual expression is found by replacing all + operations with (.), all (.) operations with (+) all 1's by 0's, and all 0's by 1's. As an example given the expression.

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

The dual of the expression is:

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

Now observe that both these were stated as postulates of Boolean algebra. The principle of duality will be used extensively in proving the Boolean algebra theorem. We shall prove that an expression is valid. Once it is proved, by the principle of duality, its dual is also valid. Hence, our effort in providing various theorems is reduced to half.

As Boolean algebra deals with a set consisting of only two elements, it is in principle, possible to prove every theorem by considering all possible cases, that is y truth table method.

Some postulates, laws and theorems are given as under:

1. Idempotency:
   (a) A + A = A
   (b) A . A = A
   Part (a) and (b) of this theorem are dual to each other.
   
   So it is sufficient to prove either part. Let us prove (b) part.
   L.H.S = A . A
              = A . A + 0
              = A . A + A . A = A . ( A + A )
             = A . 1
             = A = R.H.S
   We have applied various postulates in proving this theorem. In general, the proof of the Boolean algebra theorem is simple:
2. (a) A + 1 = 1
   (b) A . 0 = 0
   
   Let us prove part (b) of this theorem:
   L.H.S = A . 0
             = A . 0 + 0
             = A . 0 + A . A = A . ( 0 + A )= A . A 
             = 0 = R.H.S
   Part (a) can be similarly proved. In any case, part (a) is seen to be a dual of part (b). This theorem is important as it emphasizes the properties of the unique elements 1 and 0.

3. Absorption:
   
   (a) A + A . B = A
   (b) A . ( A + B) = A
   
   Let us prove part (a)
   L.H.S  =  A + A . B
              = A . 1 + A . B
              = A . ( 1 + B)
              = A . ( B + 1 )
              = A = R.H.S.
   Part (b) is a dual of part (a). Let us try to prove part (b) by the truth table method. It is 2 argument theorem, therefore in all these are four cases. We find the expression on the L.H.S and R.H.S is the same for all these four cases.

   A	B	A + B	A . ( A + B)
   0	0	0	0
   0	1	1	0
   1	0	1	1
   1	1	1	1

4. (a) A + A  . B = A + B(b) A . ( A + B ) = A . B
   
   Let us prove part (a) of this theorem
   
   L.H.S = A = A  . B= ( A + A ) . ( A + B )
             = 1 . ( A + B )
             = ( A + B ) . 1
             = ( A + B )
             = R.H.S
   
   Part (b) of the theorem is dual to part (a)