Boolean algebra and basic postulates

Chapter 2

Boolean Algebra And Logic Gate

Boolean Algebra like any other mathematical system can be defined with a set of elements, a set of operator and a no of unproved postulates. This algebra in two valued system can be used to represent the properties of bistable circuit.

Two Valued Boolean Algebra

It is defines on a set of two elements B= {0,1} with rules for the two binary operators as following:

x	y	x+y
0	0	0
0	1	1
1	0	1
1	1	1

x	y	x.y
0	0	0
0	1	0
1	0	0
1	1	1

 Basic Postulates

These postulates are used to prove various Boolean theorems and do not need any proof:

POSTULATES:-

1)      x+0= x

2)      x.1=x

3)      x+x’=1

4)      x.x’=0

5)      x(y+z)=xy+xz

6)      x+y+z=(x+y)(x+z)

7)      x+y=y+x

8)      x.y=y.x

Basic theorems

The above listed postulates are used to prov some basic theorems. The theorems are listed as following:-

Theorem 1

a)      x+x= x

(x+x)= (x+x)(x+x’)= x+x.x’= x

b)      x.x= x

x.x= x.x+0= x.x+x.x’= x (x+x’) = x

Theorem 2

a)      x+1=1

x+1= (x+1).1= (x+1)(x+x’)= x+x’=1

b)      x.0=0 (by the duality of a)

Theorem 3

(x’)’=x (INVOLUTION)

Proof: performing complement of variables two times preserving the same original value.

Theorem 4

a)      x+xy=x (absorption)

x+xy= x (1+y) = x.1= x

b)      x(x+y)=x

x(x+y) = x.x+x.y= x+xy= x (1+Y) = x

De Morgan’s Theorem

1)      (x+y)’=(x’.y’)

2)      (x.y)’=(x’+y’)

The validity of the de Morgan’s theorem is proved by using truth table.

x	y	x+y	(x+y)’	x’	y’	x’+y’
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

Both columns are same. Hence verified

x	y	x.y	(x.y)’	x’	y’	x’+y’
0	0	0	1	0	1	1
0	1	0	1	0	0	1
1	0	0	1	1	1	1
1	1	1	0	1	0	0

Both columns are same. Hence verified

Use of De Morgan’s theorem

It is used to realize a NORing operation with the use of only AND gates and NOT gates and similarly NANDing operation by using only OR gates can also be achieved.