1.

Logic Gates
2. Boolean Expressions
3. DeMorgan’s Theorem
4. Boolean Analysis of Logic Circuits
Logic Gates

➢ Logic is human reasoning that tells us if a

proposition or declarative statement is true.
➢ Logic gates are electronic circuits that can
implement logic expressions on single or multiple
binary inputs and give one binary output.
➢ The operation of logic gates is based on Boolean
algebra or mathematics.
➢ Logic gate found its uses in our day-to-day basis
such as in the architecture of our telephones,
laptops, tablets, and memory devices.
Logic Gates

➢ Basic logic gates, namely the OR gate, the AND

gate, and the NOT gate.
➢ Other logic gates derived from these basic gates are
the NAND gate, the NOR gate, the EXCLUSIVE-OR
gate and the EXCLUSIVE-NOR gate.
Truth Table

➢ A truth table lists all

possible combinations of
input binary variables and
the corresponding outputs
of a logic system.
➢ If a logic circuit has n
binary inputs, its truth
table will have 2n possible
input combinations, or in
other words 2n rows.
NOT Gate/The Inverter

➢ 𝑌 = 𝐴ҧ
➢ A NOT gate is a one-input,
one-output logic circuit
whose output is always the
complement of the input.
➢ When a HIGH level is
applied to an inverter
input, a LOW level will
appear on its output.
➢ When a LOW level is
applied to its input, a
HIGH will appear on its
output.
OR Gate

➢ The Boolean Expression for the OR gate is the

logical addition of inputs denoted by the plus
sign(+)
➢ The output of an OR gate is LOW only when
all of its inputs are LOW.
➢ For all other possible input combinations, the
output is HIGH.
AND Gate

➢ An AND gate is used to

perform logical
multiplication of binary
input.
➢ The output of an AND gate
is HIGH only when all of its
inputs are in the HIGH
state.
➢ In all other cases, the output
is LOW.
NAND Gate

➢ NAND stands for NOT

AND. An AND gate
followed by a NOT circuit
makes it a NAND gate.
➢ The output of a NAND
gate is a logic ‘0’ when all
its inputs are a logic ‘1’.
➢ When any of the inputs is
‘0’, the output will be ‘1’.
 NOR Gate

➢ NOR stands for NOT OR. An OR gate followed by

a NOT circuit makes it a NOR gate.
➢ NOR gate returns the complement result of the
OR gate.
➢ The output of a NOR gate is a logic ‘1’ when all its
inputs are logic ‘0’.
Exclusive OR Gate

➢ The output of an EX-OR gate

is a logic ‘1’ when the inputs
are opposite and a logic ‘0’
when the inputs are like.
➢ Although EX-OR gates are
available in integrated circuit
form only as two-input gates,
unlike other gates which are
available in multiple inputs.
➢ Multiple-input EX-OR logic
functions can be implemented
using more than one two-
input gates.
 Exclusive NOR Gate

➢ EXCLUSIVE-NOR (commonly
written as EX-NOR) means NOT of
EX-OR.
➢ The output of a two-input EX-NOR
gate is a logic ‘1’ when the inputs are
the same logic level and a logic ‘0’
when they are opposite logic.
➢ In general, the output of a multiple-
input EX-NOR logic function is a
logic ‘0’ when the number of 1s in the
input sequence is odd and a logic ‘1’
when the number of 1s in the
input sequence is even including ‘0’.
IEEE/ANSI Standard Symbols
Negative True Symbols
Logic Gate ICs

➢ Logic gates ICs integrate multiple gates into a

single integrated circuit package.
➢ They provide the elementary digital functions
needed to implement all digital logic systems.
➢ These devices perform logical operations on one
or more binary inputs to produce a single
binary output.
➢ They are used in digital circuits to implement
various logical functions, such as AND, OR,
NOT, XOR, and NAND.
Boolean Algebra

➢ Boolean algebra is the mathematics of digital

logic.
➢ Boolean algebra is composed of a set of
symbols and a set of rules to manipulate these
symbols.
➢ Variables are the different symbols in a Boolean
expression.
➢ Each occurrence of a variable or its complement is
called a literal.
 Boolean Algebra

➢ The complement of a literal is the inverse of a variable and

is indicated by a bar over the variable (overbar).
➢ The complement of a given Boolean expression is
obtained by complementing each literal, changing all ‘.’ to
‘+’ and all ‘+’ to ‘.’, all 0s to 1s and all 1s to 0s.
➢ The dual of a Boolean expression is obtained by replacing
all ‘.’ operations with ‘+’ operations, all ‘+’ operations with
‘.’ operations, all 0s with 1s and all 1s with 0s and leaving
all literals unchanged
➢ Two given Boolean expressions are equivalent if one of
them equals ‘1’ only when the other equals ‘1’ and one
equals ‘0’ only when the other equals ‘0’.
Boolean Algebra vs Ordinary Algebra

➢ In ordinary algebra, the letter symbols can take on any

number of values including infinity. In Boolean algebra,
they can take on either of two values, that is, 0 and 1.
➢ The values assigned to a variable have a numerical
significance in ordinary algebra, whereas in its Boolean
counterpart they have a logical significance.
➢ While ‘.’ and ‘+’ are respectively the signs of multiplication
and addition in ordinary algebra, in Boolean algebra ‘.’
means an AND operation and ‘+’ means an OR operation.
➢ More specifically, Boolean algebra captures the essential
properties of both logic operations such as AND, OR and
NOT and set operations such as intersection, union and
complement.
Boolean Addition

➢ In logic circuits, a sum term is produced by an

OR operation with no AND operations
involved.
Boolean Multiplication

➢ In logic circuits, a product term is produced by an

AND operation with no OR operations involved.
Cumulative Laws

➢ The laws states that the order in which

variables are ANDed or ORed is immaterial.
𝑋+𝑌 =𝑌+𝑋
𝑋. 𝑌 = 𝑌. 𝑋
 Associative Laws

➢ The laws state that, when three variables are

being ORed or ANDed, it is immaterial whether
we do this by ORing or ANDing the result of the
first and second variables with the third variable
or by ORing or ANDing the first variable with
the result of ORing or ANDing of the second and
third variables or even by Oring or ANDing the
second variable with the result of ORing of the
first and third variables.
𝑋+ 𝑌+𝑍 = 𝑋+𝑌 +𝑍
𝑋(𝑌𝑍) = 𝑋𝑌 𝑍
Associative Laws
Distributive Law

➢ This law states that ORing two or more variables

and then ANDing the result with a single
variable is equivalent to ANDing the single
variable with each of the two or more variables
and then ORing the products.
𝑋 𝑌 + 𝑍 = 𝑋𝑌 + 𝑋𝑍
𝑋 + (𝑌𝑍) = (𝑋 + 𝑌). (𝑋 + 𝑍)
Distributive Law
DeMorgan’s Theorem
➢ DeMorgan’s theorems provide mathematical verification
of the equivalency of the NAND and negative-OR gates
and the equivalency of the NOR and negative-AND
gates.
➢ DeMorgan’s first theorem states that “The complement of
a product of variables is equal to the sum of the
complements of the variables”.
𝑋𝑌 = 𝑋ത + 𝑌ത
DeMorgan’s second theorem states that “The
complement of a sum of variables is equal to the product
of the complements of the variables”
𝑋 + 𝑌 = 𝑋𝑌
DeMorgan’s Theorem
➢ DeMorgan’s theorems provide mathematical verification
of the equivalency of the NAND and negative-OR gates
and the equivalency of the NOR and negative-AND
gates.
➢ DeMorgan’s first theorem states that “The complement of
a product of variables is equal to the sum of the
complements of the variables”.
𝑋𝑌 = 𝑋ത + 𝑌ത
DeMorgan’s second theorem states that “The
complement of a sum of variables is equal to the product
of the complements of the variables”
𝑋 + 𝑌 = 𝑋𝑌
DeMorgan’s Theorem
DeMorgan’s Theorem
Rules of Boolean Algebra
Boolean Analysis of Logic Circuits

➢ Boolean algebra provides a concise way to

express the operation of a logic circuit formed
by a combination of logic gates.
➢ To derive the Boolean expression for a given
combinational logic circuit, begin at the left-
most inputs and work toward the final output,
writing the expression for each gate
➢ Apply the rules of Boolean algebra to reduce
the expression to its simplest form.
Boolean Analysis of Logic Circuits
Practice Exercises

1. How would you hardware-implement a four-input OR

gate using two-input OR gates only?
2. Draw the output waveform for the OR gate and the
given pulsed input waveforms:

3. Develop the truth table for a 4-input AND gate.

4. For the logic circuit arrangements of Figs (a) and
(b), draw the output waveform
 Practice Exercises

5. Show the logic arrangements for implementing:

(a) a four-input NAND gate using two-input AND gates
and NOT gates;
(b) a three-input NAND gate using two-input NAND gates;
(c) a NOT circuit using a two-input NAND gate;
(d) a NOT circuit using a two-input NOR gate;
(e) a NOT circuit using a two-input EX-NOR gate
Practice Exercises

6. Find (a) the dual of A.𝐵ത + B.𝐶ҧ + C.𝐷

ഥ and (b) the
complement of [(A. Bഥ + Cത ). D + E
ഥ]. F
7. Apply DeMorgan’s theorems to the following
expressions:
Assignment

1. How do you implement three-input and four-

input EX-OR logic functions with the help of two-
input EX-OR gates?
2. Apply DeMorgan’s theorems to the
expressions:
a) XYZ and
b) X + Y + Z.
3. Simplify the following logic circuit using
Boolean Algebra
Assignment
 Recommended Text

1. Electronic Devices and Circuit Theory by Robert L.

Boylestad and Louis Nashelsky. Prentice Hall
Publications.
2. Electronic Devices, Circuits, and Applications by
Christopher Siu. Springer Nature Switzerland