UNIT-I
BOOLEAN ALGEBRA AND COMBINATIONAL CIRCUITS
Boolean algebra: De-Morgan's theorem, switching functions and simplification using K
maps & Quine-McCluskey method, Design of adder, subtractor, comparators, code
converters,encoders, decoders,multiplexers and demultiplexers.
INTRODUCTION:
In 1854, George Boole, an English mathematician, proposed algebra for
symbolically representing problems in logic so that they may be analyzed
mathemnatically. The mathematical systems founded upon the work of Boole are called
Boolean algebra in his honor.
The application of a Boolean algebra to certain engineering problems was
introduced in 1938 by C.E. Shannon.
For the formal definition of Boolean algebra, we shall employ the postulates
formulated by E.V. Huntington in 1904.
Fundamental postulates of Boolean algebra:
from which
Thepostulates of a mathematical system forms the basic assumption
it is possible to deduce the theorems, laws and properties of the system.
structures are
The most common postulates used to formulate various
i) Closure:
elementsof S, the
A set S is closed w.r.t. a binary operator, if for every pair of
binary operator specifies a rule for obtaininga unique element of S.
1, 0 ¬B.
The result of each operation with operator (+) or () is either 1 or 0 and
i) Identity element:
there
A set S is said to have an identity element w.r.t a binary operation * on S, if
exists an element e ¬S with the property,
e*x=x* e=x
Eg: 0+0 = 0 0+ 1 =1+ 0=1 a) x+ 0=x
1.1=1 1.0=0.1=1 b) x.1=X
, ii) Commutative law:
A binary operator * on aset S is said to be commutative if,
x*y=y *x for all x, y¬S
Eg: 0+ 1= 1+ 0 =1 a) x+ y= y+ x
0.1=1.0 =0 b) x. y= y. x
iv) Distributive law:
lII *and are two binary operation ona set S, " is said to be distributive over +
whenever,
x. (y+ z) = (x. y) + (x. z)
Similarly, + is said to be distributive over " whenever,
x+ (y. z) = (x+ y). (x+ z)
v) Inverse:
A set S having the identity element e, w.r.t. binary operator * is said to
have an
inverse, whenever for every x¬S, there exists an element x'ESsuch that,
x. x' ¬e
a) x+ x=1, since 0+ 0 =0+ 1 and 1+ 1'=1+ 0 =1
b) x. x=1, since 0. 0' = 0.1 and 1. 1' =1.0 = 0
Summary:
Postulatesof Boolean algebra:
POSTULATES (a) (b)
Postulate 2 (ldentity) x+0=x
X.1= x
Postulate 3 (Commutative) X+ y=y+ x
Postulate 4 (Distributive) r x (y+ z) = xy+ xz
X.y=y.x
x+ yz = (x+ y). (xt z)
Postulate 5 (Inverse) x+x' =1
x. x = 0
, Basic theorem and properties of Boolean algebra:
Basic Theorems:
The theorems, like the postulates are listed in pairs; cach relation is the dual of the
one paired with it. The postulates are basic axioms of the algebraic structure and need no
proof. The theorems must be proven from the postulates. The proofs of the theorems with
one variable are presented below. At the right is listed the number of the postulate that
justifies each step of the proof.
1) a) xt x = x
x+ x= (x+ x).1 by postulate 2(b) [ x. 1 = x ]
= (x+ x). (x+ x) 5(a) [x+x= 1]
= X+ xx' 4(b) [ x+yz = (xty)(x+)l
= x+ 0 5(b) [x. x-0]
= X 2(a) [x+0 =x]
b) x. x = x
x. x= (x. x) +0 by postulate 2(a) [x+ 0 =x]
= (x. x) + (x. x) 5(b) [x. x = 0]
=x (x+x) 4(2) [x (y+z) =(xy)+ (xz)]
=x (1) 5(a) [x+x=1]
=X 2(b) [ x.1 =x]
2) a) x+ 1=1
x+1 =1. (x+ 1) by postulate 2(b) [ x. 1 =x]
= (x+ x). (x+ 1) 5(a) [ x+ x=1]
=X+x.1 4(b) [ x+yz= (xty)(x+z)]
=x+x 2(b) [x. 1=x]
=1 5(a) [x+ x=1]
b)x .0= 0
3) (x)=x
From postulate 5, we have x+t x=1 and x.x'=0, which defines the complemernt
of x. The complement of x is x and is also (x').
Therefore, since the complement is unique,
(x'Y = x.
BOOLEAN ALGEBRA AND COMBINATIONAL CIRCUITS
Boolean algebra: De-Morgan's theorem, switching functions and simplification using K
maps & Quine-McCluskey method, Design of adder, subtractor, comparators, code
converters,encoders, decoders,multiplexers and demultiplexers.
INTRODUCTION:
In 1854, George Boole, an English mathematician, proposed algebra for
symbolically representing problems in logic so that they may be analyzed
mathemnatically. The mathematical systems founded upon the work of Boole are called
Boolean algebra in his honor.
The application of a Boolean algebra to certain engineering problems was
introduced in 1938 by C.E. Shannon.
For the formal definition of Boolean algebra, we shall employ the postulates
formulated by E.V. Huntington in 1904.
Fundamental postulates of Boolean algebra:
from which
Thepostulates of a mathematical system forms the basic assumption
it is possible to deduce the theorems, laws and properties of the system.
structures are
The most common postulates used to formulate various
i) Closure:
elementsof S, the
A set S is closed w.r.t. a binary operator, if for every pair of
binary operator specifies a rule for obtaininga unique element of S.
1, 0 ¬B.
The result of each operation with operator (+) or () is either 1 or 0 and
i) Identity element:
there
A set S is said to have an identity element w.r.t a binary operation * on S, if
exists an element e ¬S with the property,
e*x=x* e=x
Eg: 0+0 = 0 0+ 1 =1+ 0=1 a) x+ 0=x
1.1=1 1.0=0.1=1 b) x.1=X
, ii) Commutative law:
A binary operator * on aset S is said to be commutative if,
x*y=y *x for all x, y¬S
Eg: 0+ 1= 1+ 0 =1 a) x+ y= y+ x
0.1=1.0 =0 b) x. y= y. x
iv) Distributive law:
lII *and are two binary operation ona set S, " is said to be distributive over +
whenever,
x. (y+ z) = (x. y) + (x. z)
Similarly, + is said to be distributive over " whenever,
x+ (y. z) = (x+ y). (x+ z)
v) Inverse:
A set S having the identity element e, w.r.t. binary operator * is said to
have an
inverse, whenever for every x¬S, there exists an element x'ESsuch that,
x. x' ¬e
a) x+ x=1, since 0+ 0 =0+ 1 and 1+ 1'=1+ 0 =1
b) x. x=1, since 0. 0' = 0.1 and 1. 1' =1.0 = 0
Summary:
Postulatesof Boolean algebra:
POSTULATES (a) (b)
Postulate 2 (ldentity) x+0=x
X.1= x
Postulate 3 (Commutative) X+ y=y+ x
Postulate 4 (Distributive) r x (y+ z) = xy+ xz
X.y=y.x
x+ yz = (x+ y). (xt z)
Postulate 5 (Inverse) x+x' =1
x. x = 0
, Basic theorem and properties of Boolean algebra:
Basic Theorems:
The theorems, like the postulates are listed in pairs; cach relation is the dual of the
one paired with it. The postulates are basic axioms of the algebraic structure and need no
proof. The theorems must be proven from the postulates. The proofs of the theorems with
one variable are presented below. At the right is listed the number of the postulate that
justifies each step of the proof.
1) a) xt x = x
x+ x= (x+ x).1 by postulate 2(b) [ x. 1 = x ]
= (x+ x). (x+ x) 5(a) [x+x= 1]
= X+ xx' 4(b) [ x+yz = (xty)(x+)l
= x+ 0 5(b) [x. x-0]
= X 2(a) [x+0 =x]
b) x. x = x
x. x= (x. x) +0 by postulate 2(a) [x+ 0 =x]
= (x. x) + (x. x) 5(b) [x. x = 0]
=x (x+x) 4(2) [x (y+z) =(xy)+ (xz)]
=x (1) 5(a) [x+x=1]
=X 2(b) [ x.1 =x]
2) a) x+ 1=1
x+1 =1. (x+ 1) by postulate 2(b) [ x. 1 =x]
= (x+ x). (x+ 1) 5(a) [ x+ x=1]
=X+x.1 4(b) [ x+yz= (xty)(x+z)]
=x+x 2(b) [x. 1=x]
=1 5(a) [x+ x=1]
b)x .0= 0
3) (x)=x
From postulate 5, we have x+t x=1 and x.x'=0, which defines the complemernt
of x. The complement of x is x and is also (x').
Therefore, since the complement is unique,
(x'Y = x.
