DLCOA – Syllabus 1.

3 (Part 2) &
1.4
Rithesh Kini
Computer Engg. Dept., TSEC
Contents
 Logic Gates: AND, OR, NOT, NAND, NOR, EX-OR (Syllabus
1.4)
 Boolean Algebra (Syllabus 1.3 Part2)

Rithesh Kini, Computer Engg Dept., TSEC

Basic Digital Circuits – LOGIC GATES
 In a digital system there are only a few basic operations performed,
irrespective of the complexities of the system.
 These operations may be required to be performed a number of
times in a large digital system like digital computer.
 The basic operations are
 AND, OR, NOT, and FLIP-FLOP
 The AND, OR, and NOT operations are discussed here & the FLIP-
FLOP, which is a basic memory element used to store binary
information will be discussed later.

Rithesh Kini, Computer Engg Dept., TSEC

Logic Gates Classification

Rithesh Kini, Computer Engg Dept., TSEC

BASIC LOGIC GATES – The AND Gate
 The 2 input AND gate
 Boolean equation:
Y=A·B
 Truth Table : a table containing all possible input combinations (2N
combinations for N inputs) and their corresponding outputs.

Rithesh Kini, Computer Engg Dept., TSEC

BASIC LOGIC GATES – The AND Gate
 N input AND Gate: has N inputs (N≥2) and one output
 Digital signals are applied at the input terminals A, B, …, N
 Definition : the output of an AND gate is 1 if and only if all the
inputs are 1.
 Its Boolean equation is,
Y = A AND B AND C … AND N
=A·B·C·…·N
= ABC … N
 All the variables are binary (logical variables)
 Inputs are applied & output is obtained w.ref.t. ground terminal.
Rithesh Kini, Computer Engg Dept., TSEC
BASIC LOGIC GATES – The AND Gate

Timing diagram (waveform)

Rithesh Kini, Computer Engg Dept., TSEC
LOGIC GATES – The OR Gate
 The 2 input OR gate
 Boolean equation:
Y=A+B
 Truth Table :

Rithesh Kini, Computer Engg Dept., TSEC

LOGIC GATES – The OR Gate
 N input OR Gate : It has N inputs (N≥2) and one output
 Definition : the output of an OR gate is 1 if and only if one or more
inputs are 1.
 Its Boolean equation is,
Y = A OR B OR C … OR N
=A+B+C+…+N

Rithesh Kini, Computer Engg Dept., TSEC

LOGIC GATES – The OR Gate

Timing diagram (waveform)

Rithesh Kini, Computer Engg Dept., TSEC
LOGIC GATES – The NOT Gate
 It has one input (A) and one output (Y)
 It is also known as an inverter
 Its Boolean equation is,
Y = NOT A
=A
 Read as
“Y equals NOT A” or “Y equals complement of A”.
 The NOT operation is also referred to as an inversion or complementation
 The presence of a bubble, always denotes inversion in digital circuits.
Rithesh Kini, Computer Engg Dept., TSEC
LOGIC GATES – The NOT Gate
 Truth Table :

Timing diagram (waveform)

Rithesh Kini, Computer Engg Dept., TSEC

LOGIC GATES – NAND & NOR GATEs
 Any Boolean (or logic) expression can be realised by using the AND,
OR and NOT gates.
 From these three operations, two more operations have been
derived: the NAND operation and NOR operation.
 NAND and NOR gates are known as universal gates because they are
sufficient for the realization of any logical expression! (we will see this
shortly)

Rithesh Kini, Computer Engg Dept., TSEC

LOGIC GATES – The NAND Gate
 The 2 input NAND gate
 Boolean equation:
Y=A.B
 Truth Table :

Rithesh Kini, Computer Engg Dept., TSEC

LOGIC GATES – The NAND Gate

 NAND = NOT–AND
 It is an N inputs (N≥2) AND gate followed by a NOT gate.
 Its Boolean equation : [ref Fig. 1.10 (a)]
Let the output of the AND gate Y’ = AB…N
∴ the output of the NOT gate Y = Y′ = AB…N

Rithesh Kini, Computer Engg Dept., TSEC

LOGIC GATES – The NOR Gate
 The 2 input NOR gate
 Boolean equation:
Y=A+B
 Truth Table :

Rithesh Kini, Computer Engg Dept., TSEC

LOGIC GATES – The NOR Gate

 NOR = NOT–OR
 It is an N inputs (N≥2) OR gate followed by a NOT gate.
 Its Boolean equation :
Let the output of the OR gate Y’ = A + B + … + N
Now, the output of the NOT gate Y = Y′ = A + B + … + N

Rithesh Kini, Computer Engg Dept., TSEC

LOGIC GATES – The EX-OR Gate
 EX-OR is widely used in digital circuits.
 Its not a basic operation.
 It can be performed using
a. the basic gates—AND, OR & NOT or
b. universal gates—NAND or NOR Inputs Output

 Its Boolean equation is : A B Y

0 0 0
Y = A EX-OR B = A ⨁ B
0 1 1
1 0 1
1 1 0
Rithesh Kini, Computer Engg Dept., TSEC
LOGIC GATES – The EX-OR Gate
 Compare the truth table of an EX-OR gate with that of an OR gate.
Inputs Output Inputs Output
A B Y A B Y
0 0 0 0 0 0
0 1 1 0 1 1
1 0 1 1 0 1
1 1 0 1 1 1

 Application of EX-OR gate : to compare two digital signals.

Rithesh Kini, Computer Engg Dept., TSEC

LOGIC GATES – The EX-OR Gate

Timing diagram (waveform)

Rithesh Kini, Computer Engg Dept., TSEC
LOGIC GATES – The EX-NOR Gate
 Its not a basic operation.
 It can be performed using
 the basic gates—AND, OR & NOT or
 universal gates—NAND or NOR
Inputs Output
 Its Boolean equation is :
A B Y
Y = A EX-NOR B
0 0 1
= A EX−OR B = A ⨁ B = A ⨀ B 0 1 0
 Application : Coincidence operation 1 0 0
1 1 1

Rithesh Kini, Computer Engg Dept., TSEC

BOOLEAN ALGEBRA
 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.

Rithesh Kini, Computer Engg Dept., TSEC

BOOLEAN ALGEBRAIC THEOREMS

Rithesh Kini, Computer Engg Dept., TSEC (Continued)

BOOLEAN ALGEBRAIC THEOREMS

Rithesh Kini, Computer Engg Dept., TSEC

BOOLEAN ALGEBRAIC THEOREMS
Distribitive Laws : Commutative Laws :
𝐴∙ 𝐵+𝐶 =𝐴∙𝐵+𝐴∙𝐶 𝐴+𝐵 =𝐵+𝐴

𝐴+ 𝐵∙𝐶 = 𝐴+𝐵 ∙ 𝐴+𝐶 𝐴∙𝐵 =𝐵∙𝐴

Associative Laws : De Morgan’s Laws :

𝐴∙ 𝐵∙𝐶 = 𝐴∙𝐵 ∙𝐶 A + B = A∙B

𝐴+ 𝐵+𝐶 = 𝐴+𝐵 +𝐶 A∙B=A +B

Rithesh Kini, Computer Engg Dept., TSEC

BOOLEAN ALGEBRAIC THEOREMS
 From these theorems, we observe that the even numbered
theorems can be obtained from their preceding odd numbered
theorems by
(i) interchanging + and · signs, and
(ii) interchanging 0 and 1.
 Theorems which are related in this way are called duals.
 Theorems 1.1 to 1.8 involve a single variable only.
 Each of these theorems can be proved by considering every possible
value of the variable

Rithesh Kini, Computer Engg Dept., TSEC

BOOLEAN ALGEBRAIC THEOREMS
 For example, in Theorem 1.1,
if A = 0 then 0 + 0 = 0 = A
& if A = 1 then 1 + 0 = 1 = A
and hence the theorem is proved.

Rithesh Kini, Computer Engg Dept., TSEC

BOOLEAN ALGEBRAIC THEOREMS
 Theorems 1.9 to 1.20 involve more than one variable and can be
proved by making a truth table.
 Example: Theorem 1.10 can be proved by making the truth table given
in Table 1.9.

Rithesh Kini, Computer Engg Dept., TSEC

BOOLEAN ALGEBRAIC THEOREMS

For each combination of A, B, C, the value of A + BC is the same as that of

(A + B) (A + C), which proves the theorem.
Rithesh Kini, Computer Engg Dept., TSEC
BOOLEAN ALGEBRAIC THEOREMS
 Theorems 1.21 and 1.22 are known as De Morgan’s theorems.
 These theorems can be proved by first considering the two variable case and
then extending this result.
 From the truth table given in Table 1.10 we get the relations,

A∙B=A +B & A+B=A∙B

 Now Consider the NAND operation of three variables,

A∙B∙𝑪= A∙B ∙𝑪 Prove for NOR case!

= A∙B +𝑪
=𝑨+B+𝑪
Rithesh Kini, Computer Engg Dept., TSEC
BOOLEAN ALGEBRAIC THEOREMS

Rithesh Kini, Computer Engg Dept., TSEC

BOOLEAN ALGEBRA
 A logic problem can be represented in terms of
 a logic equation or
 a truth table.
 A Digital circuit using the gates discussed above can be designed to
realize a logic equation.
 In general, it is possible to simplify (minimize) a logic equation. But
why minimize?
 The minimized logic equation will probably need less number of
gates and/or less number of inputs for the gates.

Rithesh Kini, Computer Engg Dept., TSEC

BOOLEAN ALGEBRA
Prove the Following Boolean Expressions :
1. A + AB = A
2. A +AB = A + B
3. (A + B)(A + C) = A + BC

Rithesh Kini, Computer Engg Dept., TSEC

 Revisiting The NAND & NOR Gate
(Universal Gates)
 Recollect NAND and NOR gates are known as universal
gates because they are sufficient for the realization of any
logical expression.

Rithesh Kini, Computer Engg Dept., TSEC

 NOT using NAND
The Boolean expression for NOT gate is Y = A

Output of NAND gate is Y=A∙B

If input A = Input B then, Y = A ∙ A = A

Y= A
Rithesh Kini, Computer Engg Dept., TSEC
 AND using NAND
The Boolean expression for AND gate is Y = 𝑨 ∙ 𝑩
Taking double inversion,
𝐘=𝑨∙𝑩
But 𝑨 = 𝐀
Therefore, 𝐘 = 𝐀 ∙ 𝑩

𝑌 =𝐴∙𝐵

Rithesh Kini, Computer Engg Dept., TSEC

 OR using NAND
The Boolean expression for OR gate is Y = A + B
Taking double inversion,
Y=A+B
But by De Morgan’s theorem
A+B =A ∙B 𝑨
Therefore, 𝐘 = 𝐀 ∙ 𝐁
Y= 𝑨 + 𝑩

𝑩
Rithesh Kini, Computer Engg Dept., TSEC
 NOR using NAND
The Boolean expression for NOR gate is Y = A + B
But by De Morgan’s theorem,
A+B =A ∙B
Y=A ∙B
Taking double inversion,
𝐘=𝑨 ∙𝑩

Circuit diagram (exercise !)

Rithesh Kini, Computer Engg Dept., TSEC

 EX-OR using NAND
The Boolean expression for EX-OR gate is
Y = A⨁B
Y= A∙B+A∙B
Taking double inversion,
Y=A∙B+A∙B
Let A ∙ B = X & A∙B=Z
Y=X+Z
Using De Morgan’s theorem
X+Z=X∙Z
𝐘=𝐗 ∙𝐙= 𝐀∙𝐁 ∙ 𝐀∙𝐁 Circuit diagram (exercise)?
Rithesh Kini, Computer Engg Dept., TSEC
NOT, AND, OR, NAND, NOR & EX-OR using NOR
NOT using NOR:
Y=A+B
If A = B, Y = A + A
But A + A = A
Therefore, Y = A

Y =A
Solve the remaining as exercise!
Rithesh Kini, Computer Engg Dept., TSEC
 Combinational Circuits versus
Sequential Circuits
 Combinational Circuits
The input values explicitly determine the output
 Sequential circuit
The output is a function of the input values and the
existing state of the circuit
 We describe the circuit operations using
 Boolean expressions
 Logic diagrams
 Truth tables

Rithesh Kini, Computer Engg Dept., TSEC

 References
1. R. P. Jain, “Modern Digital Electronic”, McGraw-Hill Publication,
4thEdition.

Rithesh Kini, Computer Engg Dept., TSEC

 Thank You

Rithesh Kini, Computer Engg Dept., TSEC