BOOLEAN ALGEBRA

The circuits in digital computers follow the logic of 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' state of Boolean of an electronic device. The two permitted states of Boolean algebra are usually represented by 0 and 1.

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

  1. The OR addition represented by a plus (+) sign.
  2. The AND multiplication represented by cross (X) or a dot (.) sign.
  3. The NOT operation 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 (.) operation 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 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 theorems are dual of 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, proof of Boolean algebra theorem is simple:
  2. (a) A + 1 = 1
    (b) A . 0 = 0

    Let us prove part (b) of this theorems:
    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 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 dual of part (a). Let us try to prove part (b) by 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 same for all these four cases.
    ABA + BA . ( A + B)
    0000
    0110
    1011
    1111
  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 of part (a)