Logic gates and Boolean algebra
C.B. Pham 2-1
Boolean constants and variables
• Boolean constants and variables are allowed to have
only two possible values, 0 or 1.
• Boolean 0 and 1 do not represent actual numbers but
instead represent the state of a voltage variable, or what
is called its logic level.
• 0/1 and Low/High are used most of the time.
C.B. Pham 2-2
Truth Tables
How a logic circuit output depends on the logic levels
present at the inputs.
C.B. Pham 2-3
Logic gates
• Three Logic operations: AND, OR, NOT
• Logic Gates: Digital circuits constructed from diodes,
transistors, and resistors whose output is the result of a
basic logic operation (OR, AND, NOT) performed on the
inputs.
C.B. Pham 2-4
OR Operation with OR gates
Produce a result of 1 whenever any input is 1. Otherwise 0.
Truth table Circuit symbol for a two-input OR gate
C.B. Pham Circuit symbol for a three-input OR gate 2-5
OR Operation with OR gates
Determine the OR gate output below:
C.B. Pham 2-6
AND Operation with AND gates
An AND gate output will be 1 only for the case when all
inputs are 1; for all other cases the output will be 0.
Circuit symbol for a two-input AND gate
Truth table
C.B. Pham Circuit symbol for a three-input AND gate 2-7
AND Operation with AND gates
Determine the AND gate output below:
C.B. Pham 2-8
NOT Operation
• The NOT operation is performed on a single variable.
• Its output logic level is always opposite to the logic level
of this input.
Truth table
Circuit symbol for a NOT gate
C.B. Pham 2-9
Describing logic circuits algebraically
Any logic circuit, no matter how complex, can be completely
described using 3 basic Boolean operations through AND
gates, OR gates, and NOT gates.
C.B. Pham 2-10
Describing logic circuits algebraically
Logic circuit whose expression requires parentheses.
One input variable can be connected as an input to two
different gates.
C.B. Pham 2-11
Describing logic circuits algebraically
Derive the Boolean expression for the logic circuit below.
C.B. Pham 2-12
Evaluating logic circuit outputs
• Obtain the output from the Boolean expression.
In case: A = 0, B = 1, C = 1, and D = 1
• Obtain the output from a diagram.
C.B. Pham 2-13
Implementing circuits from Boolean Exp.
Example: draw the circuit diagram to implement the
expression:
C.B. Pham 2-14
NOR Gates and NAND Gates
Combined from three basic gates, NOR gates and NAND
gates are also widely used in digital circuits.
• NOR gate
NOR symbol
Truth table
C.B. Pham
Equivalent circuit 2-15
NOR Gates and NAND Gates
• NAND gate
NAND symbol
Truth table
Equivalent circuit
Note: A B A B and A.B A.B
C.B. Pham 2-16
Boolean theorems
Boolean algebra provides the operations and the rules for
working with the set {0,1}.
Single variable theorems
C.B. Pham 2-17
Boolean theorems
Note: the variable x may represent an expression
containing more than one variable.
C.B. Pham AB( AB) 0 AB AB 1 2-18
Boolean theorems
Multivariable theorems
C.B. Pham 2-19
Boolean theorems - examples
Simplify
Simplify
Simplify
C.B. Pham 2-20
DeMorgan’s theorems
DeMorgan’s theorems are
extremely useful in simplifying
expressions in which a product
or sum of variables is inverted.
Simplify
C.B. Pham AC BD 2-21
Universality of NAND gate & NOR gate
- Any expression can be implemented using combinations
of OR gates, AND gates, and INVERTERs.
- It is possible to implement any logic expression using only
NAND gates (or only NOR gates) and no other type of gate.
C.B. Pham 2-22
Universality of NAND gate & NOR gate
C.B. Pham 2-23
Universality of NAND gate & NOR gate
C.B. Pham 2-24
Universality of NAND gate & NOR gate
Example: implement the logic
circuit for x = AB + CD with a
minimum number of ICs. The
TTL integrated circuits are
available. Each IC is a quad.
C.B. Pham 2-25
Universality of NAND gate & NOR gate
C.B. Pham 2-26
Alternate logic gate representations
It is common to find circuit diagrams that utilize alternate
logic symbols in addition to the standard symbols.
C.B. Pham 2-27
Alternate logic gate representations
C.B. Pham 2-28
Alternate logic gate representations
• Logic symbol interpretation: active-HIGH / active-LOW
C.B. Pham 2-29
Alternate logic gate representations
Proper use of the alternate gate symbols can make the
circuit operation much clearer.
Truth table
C.B. Pham 2-30
Alternate logic gate representations
C.B. Pham 2-31
Alternate logic gate representations
Whenever possible, choose gate symbols so that bubble
outputs are connected to bubble inputs, and nonbubble
outputs to nonbubble inputs.
C.B. Pham 2-32
