Translate

Sunday 3 June 2012

Boolean Algebra

The digital signals are discrete in nature and can only assume one of the two values 0 or 1. A number system based on these two digits is known as binary number system. In the middle of 19th century, an English mathematician George Boole developed rules for manipulations of binary variables, known as Boolean Algebra. This is the basis of all digital systems like computers, calculators, etc.

Binary variables can be represented by a letter symbol such as A, B, X, Y, ... The variable can have only one of the two possible values at any time, viz. 0 or 1. The Boolean algebraic theorems are shown in following table. 



Theorem No. Theorem
1) A + 0 = A
2) A . 1 = A
3) A + 1 = 1
4) A . 0 = 0
5) A + A = A
6) A . A = A
7) A + ~A = 1
8) A . ~A = 0
9) A . (B + C) = AB + AC
10) A + BC = (A + B) (A + C)
11) A + AB = A
12) A(A + B) = A
13) A + ~AB = (A + B)
14) A(~A + B) = AB
15) AB + A~B = A
16) (A + B). (A + ~B) = A
17) AB + ~AC = (A + C) (~A + B)
18) (A + B)(~A + C) = AC + ~AB
19) AB + ~AC + BC = AB + ~AC
20) (A + B)(~A + C)(B + C) = (A + B)(~A + C)
21) ~(A . B . C...) = ~A + ~B + ~C + ...
22) ~(A + B + C...) = ~A . ~B . ~C...

Theorems 1 to 8 involve a single variable only. Each of these theorems can be proved by considering every possible value of the variable. For example, in theorem 1,
if A = 0 then 0 + 0 = 0 = A
and if A = 1 then 1 + 0 = 1 = A
and hence the theorem is proved.

Theorems 9 to 20 involve more than one variable and can be proved by making a truth table. For example, Theorem 10 can be proved by making the truth table given below.

Truth table to prove Theorem 10

   A     B     C     BC     A + BC     A + B      A + C      (A+B) (A+C)   
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0
0 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1

For each combination, the value of A + BC is same as that of (A+B) (A+C), which proves the theorem.
Theorem 21 and 22 are known as De Morgan's theorems.

No comments:

Post a Comment