Lecture 1
TE 242
DIGITAL ELECTRONICS FOR
ENGINEERS 1
Basic Logic Gates and Boolean
Algebra
Basic logic gates and Boolean algebra
• Boolean constants and variable
• OR operation
• AND operation
• NOT operation
• NOR operation
• NAND operation
• Truth tables
• Basic logic gates
• Boolean algebra postulates and theorem
• Logic symbols and waveforms
• Properties of Boolean Algebra
– Reducing functions
– Transforming functions
What is Digital System
• Digital device and digital circuits operate in a
binary number system
• Boolean algebra differ significantly from the
conventional algebra
• Binary variables
– Can be 0 or 1 (T or F, low or high)
• In Boolean algebra there are no
• Fractions
• Decimals
• Negative numbers
• Square roots
• Imaginary numbers
Binary Logic Gates
• Binary variables
– Can be 0 or 1 (T or F, low or high, ON or
OFF)
– Variables named with single letters in examples
– Really use words when designing circuits
• Basic Functions
– AND (logical multiplication)
– OR (logical addition)
– NOT (logical inversion)
Digital Systems
• Analysis problem:
. Logic .
Inputs Outputs
Circuit
. .
• Determine binary outputs for each
combination of inputs
• Design problem: given a task, develop a circuit that
accomplishes the task
– Many possible implementation
– Try to develop “best” circuit based on some
criterion (size, power, performance, etc.)
Car Parking Gate Controller
• Consider the design of a car park gate
controller
• Inputs: 500, car sensor
• Outputs: gate lift signal, gate close signal
500 Logic Raise gate
Car? Circuit Close gate
• If driver pitches in 500, raise gate.
• When car has cleared gate, close gate.
AND operation(logical multiplication)
• Symbol is dot
Z = X · Y
• Or no symbol
Z = XY
• Truth table
• Z is 1 only if
Both X and Y are 1
OR operation (logical addition)
• Symbol is +
Not addition
Z=X+Y
• Truth table
• Z is 1 if either 1
Or both!
NOT operation
• Unary
• Symbol is bar
X= Ā
• Truth table
• Inversion
Gates
• Circuit diagrams are traditional to document
circuits
• Remember that 0 and 1 are represented by
voltages
Describing Circuit Functionality: Waveforms
AND Gate
Timing
Diagrams
°Can you create a truth table from the waveforms?
OR Gate
Inverter
Consider three-input gates
3 Input OR Gate
More Inputs
• Work same way
• What’s output?
Representation: Schematic
• Schematic = circuit diagram
Ordering Boolean Functions
° How to interpret AB+C?
• Is it AB ORed with C ?
• Is it A ANDed with B+C ?
° Order of precedence for Boolean algebra: AND before OR.
° Note that parentheses are needed here :
te242: Boolean Algebra 2008
Representation: Boolean Algebra
• For now equations with operators AND,
OR, and NOT
• Can evaluate terms, then final OR
F X YZ
• Alternate representations next
Representation: Truth Table
• 2n rows
where n =
# of variables
Functions
• Can get same truth table with different
functions
F X YZ
F ( X Y )( X Z )
• Usually want ‘simplest’
– Fewest gates, or using only particular types of
gates
– More on this later
Boolean Algebra theorem
• A Boolean algebra is defined as a closed algebraic
system containing a set K or two or more elements
and the two operators, . and +.
• Useful for identifying and minimizing circuit
functionality
• Identity elements
– a+0=a
– a.1=a
• 0 is the identity element for the + operation.
• 1 is the identity element for the . operation.
Commutativity and Associativity of the Operators
• The Commutative Property:
For every a and b in K,
– a+b=b+a
– a.b=b.A
• The Associative Property:
For every a, b, and c in K,
– a + (b + c) = (a + b) + c
– a . (b . c) = (a . b) . c
Distributivity of the Operators and Complements
• The Distributive Property:
For every a, b, and c in K,
– a+(b.c)=(a+b).(a+c)
– a.(b+c)=(a.b)+(a.c)
• The Existence of the Complement:
For every a in K there exists a unique element called a’
(complement of a) such that,
– a + a’ = 1
– a . a’ = 0
• To simplify notation, the . operator is frequently omitted.
When two elements are written next to each other, the
AND (.) operator is implied…
– a+b.c=(a+b).(a+c)
– a + bc = ( a + b )( a + c )
Duality
• The principle of duality is an important concept. This says
that if an expression is valid in Boolean algebra, the dual of
that expression is also valid.
• To form the dual of an expression, replace all + operators
with . operators, all . operators with + operators, all ones
with zeros, and all zeros with ones.
• Form the dual of the expression
a + (bc) = (a + b)(a + c)
• Following the replacement rules…
a(b + c) = ab + ac
• Take care not to alter the location of the parentheses if they
are present.
Involution
• This theorem states:
a’’ = a
• Remember that aa’ = 0 and a+a’=1.
– Therefore, a’ is the complement of a and
a is also the complement of a’.
– As the complement of a’ is unique, it
follows that a’’=a.
• Taking the double inverse of a value will
give the initial value.
Absorption
• This theorem states:
a + ab = a a(a+b) = a
• To prove the first half of this theorem:
a + ab = a . 1 + ab
= a (1 + b)
= a (b + 1)
= a (1)
a + ab =a
DeMorgan’s Theorem
• A key theorem in simplifying Boolean
algebra expression is DeMorgan’s
Theorem. It states:
(a + b)’ = a’b’ (ab)’ = a’ + b’
• Complement the expression
a(b + z(x + a’)) and simplify.
(a(b+z(x + a’)))’ = a’ + (b + z(x + a’))’
= a’ + b’(z(x + a’))’
= a’ + b’(z’ + (x + a’)’)
= a’ + b’(z’ + x’a’’)
= a’ + b’(z’ + x’a)
Table of Identities
Duals
• Left and right columns are duals
• Replace AND and OR, 0s and 1s
Single Variable Identities
Commutativity
• Operation is independent of order of
variables
Associativity
• Independent of order in which we group
• So can also be written as X Y Z
and
XYZ
Distributivity
• Can substitute arbitrarily large algebraic
expressions for the variables
– Distribute an operation over the entire
expression
DeMorgan’s Theorem
• Used a lot
• NOR invert, then AND
• NAND invert, then OR
Summary
• Basic logic functions can be made from AND, OR, and NOT
(invert) functions
• The behavior of digital circuits can be represented with
waveforms, truth tables, or symbols
• Primitive gates can be combined to form larger circuits
• Boolean algebra defines how binary variables can be
combined
• Rules for associativity, commutativity, and distribution are
similar to algebra
• DeMorgan’s rules are important.
– Will allow us to reduce circuit sizes.
Identities
• Use identities to manipulate functions
• I used distributive law …
X YZ ( X Y )( X Z )
• … to transform from
F X YZ
to
F ( X Y )( X Z )
Combinational Logic
• Basics of digital logic (review)
– Basic functions
– Boolean algebra
– Gates to implement Boolean functions
• Identities and Simplification (review?)
