Chapter 1: Fundamentals of Digital Logic
1
FUNDAMENTALS OF DIGITAL LOGIC
Unit Structure
1.1 Boolean Algebra
1.2 Logic Gates
1.3 Simplification of Logic Circuits
1.3.1 Algebraic Simplification
1.3.2 Karnaugh Maps
1.1 Boolean Algebra
Boolean algebra was invented in 1854 by George boole.
It uses only the binary numbers 0 1nd 1.
It is used to analyze and simplify the digital (logic) circuits.
It is also called Binary Algebra or logical Algebra.
It is mathematics of digital logic
A variable is a symbol usually represented with an uppercase letter
Complement is the inverse of a variable; it can be denoted by bar above
variable.
A literal ia a variable or the complement of a variable.
Boolean expressions are created by performing operations on Boolean
variables. – Common Boolean operators include AND, OR, and NOT
OR operation between two variables denoted using plus (+) symbol (A OR B
as A + B)
AND operation between two variables denoted using dot (.) symbol (A AND
B as A . B)
NOT operation is a unary operation i.e. complement of a variable (NOT A as
or A’ )
1
,COMPUTER ORGANIZATION AND ARCHITECTURE
Following are Boolean Algebra Law:
Sr. Law OR operation AND operation
No.
1 Commutative Law x+y=y+x x•y=y•x
2 Associative Law x+(y + z)=(x + y)+z x(y • z) = (x • y) • z
3 Distributive Law x •(y + z) =x • y + x • z x + y • z=(x + y)•(x + z)
4 Identity Law x+0=x x•1=x
5 Null Law x+1=1 x•0=0
6 Complement Law x + x’ = 1 x • x’ = 0
7 Idempotent Law x+x=x x•x=x
8 De Morgan’s Law
Duality Principle:
According to this principle every valid boolean expression (equality) remains valid
if the operators and identity elements are interchanged.
In this principle,
if we have theorems of Boolean Algebra for one type of operation then that
operation can be converted into another type of operation
i.e., AND can be converted to OR and vice-versa
interchange
'0 with 1',
'1 with 0',
'(+) sign with (.) sign' and
'(.) sign with (+) sign'.
This principle ensures if a theorem is proved using the theorem of Boolean
algebra, then the dual of this theorem automatically holds and we need not
prove it again separately. This is an advantage of dual principle.
2
, Chapter 1: Fundamentals of Digital Logic
Some Boolean expressions and their corresponding duals are given below,
Example :
If boolean expression is
A.(B+C)=(A.B) + (A.C)
Then its dual expression is ,
A+(B.C)=(A+B).(A+C)
Boolean expression :
It is an algebraic statement which contains variables and operators.
Theorems/axioms/postulates can also be proved using the truth table method.
The other method is by an algebraic manipulation using axioms/postulates or other
basic theorems.
Few application of dual principle are as follows:
Idempotency Law
A) x+x=x
B) x.x=x
We will prove part A)
LHS = (x + x). 1 ----------------- Identity law
= (x + x).(x + x’) ----------------- Complement law
= x + x.x’ ----------------- Distributive law
=x+0 ----------------- Complement law
=x ----------------- Identity law
= RHS
As part A is proved, according to dual principle we need not to prove
part B.
Absorption Law
A) x + (x . y) = x
B) x . (x + y) = x
3
1
FUNDAMENTALS OF DIGITAL LOGIC
Unit Structure
1.1 Boolean Algebra
1.2 Logic Gates
1.3 Simplification of Logic Circuits
1.3.1 Algebraic Simplification
1.3.2 Karnaugh Maps
1.1 Boolean Algebra
Boolean algebra was invented in 1854 by George boole.
It uses only the binary numbers 0 1nd 1.
It is used to analyze and simplify the digital (logic) circuits.
It is also called Binary Algebra or logical Algebra.
It is mathematics of digital logic
A variable is a symbol usually represented with an uppercase letter
Complement is the inverse of a variable; it can be denoted by bar above
variable.
A literal ia a variable or the complement of a variable.
Boolean expressions are created by performing operations on Boolean
variables. – Common Boolean operators include AND, OR, and NOT
OR operation between two variables denoted using plus (+) symbol (A OR B
as A + B)
AND operation between two variables denoted using dot (.) symbol (A AND
B as A . B)
NOT operation is a unary operation i.e. complement of a variable (NOT A as
or A’ )
1
,COMPUTER ORGANIZATION AND ARCHITECTURE
Following are Boolean Algebra Law:
Sr. Law OR operation AND operation
No.
1 Commutative Law x+y=y+x x•y=y•x
2 Associative Law x+(y + z)=(x + y)+z x(y • z) = (x • y) • z
3 Distributive Law x •(y + z) =x • y + x • z x + y • z=(x + y)•(x + z)
4 Identity Law x+0=x x•1=x
5 Null Law x+1=1 x•0=0
6 Complement Law x + x’ = 1 x • x’ = 0
7 Idempotent Law x+x=x x•x=x
8 De Morgan’s Law
Duality Principle:
According to this principle every valid boolean expression (equality) remains valid
if the operators and identity elements are interchanged.
In this principle,
if we have theorems of Boolean Algebra for one type of operation then that
operation can be converted into another type of operation
i.e., AND can be converted to OR and vice-versa
interchange
'0 with 1',
'1 with 0',
'(+) sign with (.) sign' and
'(.) sign with (+) sign'.
This principle ensures if a theorem is proved using the theorem of Boolean
algebra, then the dual of this theorem automatically holds and we need not
prove it again separately. This is an advantage of dual principle.
2
, Chapter 1: Fundamentals of Digital Logic
Some Boolean expressions and their corresponding duals are given below,
Example :
If boolean expression is
A.(B+C)=(A.B) + (A.C)
Then its dual expression is ,
A+(B.C)=(A+B).(A+C)
Boolean expression :
It is an algebraic statement which contains variables and operators.
Theorems/axioms/postulates can also be proved using the truth table method.
The other method is by an algebraic manipulation using axioms/postulates or other
basic theorems.
Few application of dual principle are as follows:
Idempotency Law
A) x+x=x
B) x.x=x
We will prove part A)
LHS = (x + x). 1 ----------------- Identity law
= (x + x).(x + x’) ----------------- Complement law
= x + x.x’ ----------------- Distributive law
=x+0 ----------------- Complement law
=x ----------------- Identity law
= RHS
As part A is proved, according to dual principle we need not to prove
part B.
Absorption Law
A) x + (x . y) = x
B) x . (x + y) = x
3
