Switching Algebra and Logic Representations
Z. Jerry Shi
Department of Computer Science and Engineering
University of Connecticut
CSE2300W:Digital Logic Design
Boolean algebra
English mathematician George Boole invented a two-value algebraic system
Boolean Algebra.
A proposition
iti can have
h one off the
th two
t values:
l TURE or FALSE.
FALSE
Claude E. Shannon uses it to describe the behavior of circuits Switching
Algebra.
A variable can take one of the two values: 1 or 0.
0
Positive-logic convention
Analog voltages LOW, HIGH 0, 1
N ti logic
Negative l i
Signal values denoted by variables
(X, Y, FRED, etc.)
Axioms
A1. X = 0 if X != 1 A1. X = 1 if X != 0
A2. If X = 0, then X = 1 A2. If X = 1, then X = 0
A3. 0 0 = 0 A3. 1 + 1 = 1
A4. 1 1 = 1 A4. 0 + 0 = 0
A5 0 1 = 1 0 = 0
A5. A5. 1 + 0 = 0 + 1 = 1
A5
Principle of Duality
Any theorem or identity in switching algebra remains true if 0 and 1 are swapped
and and + are swapped throughout.
Boolean operators
Complement: X (opposite of X)
AND: XY
Function described
OR: X+Y
with truth table.
Logic symbols of NOT, AND, and OR
Definitions
Literal: a variable or its complement
X, X, FRED, CS_L
Expression: literals combined by
AND, OR, parentheses, complementation
X+Y
PQR
A+BC
((
((FRED Z)
) + CS_L
CS A B C + Q5)
Q ) RESET
S
Equation: Variable = expression
((FRED Z)) + CS_L A B C + Q
P = (( Q5)) RESET
Assignment: Assign a specific value to each variable
More definitions
Product term : A single literal or a product of two or more literals
A, A B, A B C '
Sum-of-products : A logic sum of product terms
ABC' +C D+E
Sum term : A single literal or a logical sum of two or more literals
A+B
Product-of-sums : A logic product of sum terms
(A + B) (C + D) E
Normal term
A product or sum term in which no variable appears more than
once
XYZ X + Y +Z
If a term is
i not normal,
l it
i can be
b reduced
d d to a constant or a
normal term
Gates
Gates are basic digital devices
A gate takes one or more inputs and produces an output
Can be considered as a function
Inputs are either 0 or 1
Although they may have very different values of voltage
Example of basic building blocks: AND, OR, NOT
Theorems
Proofs by perfect induction
Example: In T1, X has two values 0 or 1.
If X = 0,
0 X + 0 = 0 + 0 = 0 = X.
X
If X = 1, X + 0 = 1 + 0 = 1 = X.
More Theorems
Duality
Swap 0 & 1, AND & OR
Result: Theorems still true
Why?
Each axiom (A1-A5) has a dual (A1-A5)
Counterexample:
X + X Y = X (T9) X + (X Y) = X (T9)
X X + Y = X (dual)
X + Y = X (T3)
X (X + Y) = X (dual)
???????????? (X X) + (X Y) = X (T8)
X + (X Y) = X (T3
(T3'))
parentheses,
operator precedence!
N-variable Theorems
T12 and T13 can be pproved usingg finite induction
Proving Shannons expansion is an exercise problem in the book
DeMorgans theorems change gate types and location of inverters
XOR gates
Like an OR gate, but excludes the case where both inputs are 1
No direct, simple implementation
XNOR: complement of XOR
XOR
XNOR
XOR
XY=XY+XY
XX=0
XX=1
X0=X
X1=X
(X Y) Z = X (Y Z)
XYY=X
(X Y) = X Y = X Y
(X Y Z) = X Y Z
If X = Y Z,
Z then X Y = Z
Examples
X+XY
X+XY
A B C + A B C + A B C
(X Y) Y
(X Y) Y
(X Y) +Y
(X Y) Z = (X Z) (Y Z) (homework)
(h k)
NAND and NOR
DeMorgan Symbol Equivalence
Likewise for OR
DeMorgan Symbols
XOR and XNOR symbols
Sum-of-products Form
AND-OR
NAND-NAND
Product-of-sums form
OR AND
OR-AND
NOR-NOR
Sum-of-products preferred in CMOS and TTL (NAND-NAND)
Minterm and maxterm
Normal term
Ap
product or sum term in which no variable appears
pp more than once
XYZ X + Y +Z
If a term is not normal, it can be reduced to a constant or a normal term
An n-variable minterm : a normal product term with n variables
Only
y one assignment
g makes a minterm = 1
An n-variable maxterm : a normal sum term with n variables
Only one assignment makes a maxterm = 0
Consider an n-variable
n variable function
function, how many minterms and maxterms?
Truth table, minterms, and maxterms
More
Canonical sum :
A sum of the minterms corresponding to truth
truth-table
table rows for
which the function produces a 1 ouptut
On-set for the logic functions
Canonical product :
A product of the maxterms corresponding to truth-table rows for
which the function produces a 0 ouptut
Off-set for the logic functions
Example:
XYZ F Minterm 0: X Y Z
000 1 Minterm 3: X Y Z
001 0 Minterm 4: X Y Z
010 0 Minterm 6: X Y Z
Minterm 7: X Y Z
011 1
100 1
Maxterm 1: X + Y + Z
101 0 Maxterm 2: X + Y + Z
110 1 Maxterm 5: X + Y + Z
111 1
F=
x,, y, z ((0,, 3,, 4,, 6,, 7)) = XYZ+XYZ+XYZ + XYZ+XYZ
F = x,y,z (1, 2, 5) = (X + Y + Z)(X + Y+Z)(X + Y + Z)
Another example
Find all the minterms and maxterms for the following function
X+YZ
(X + Y) (Y + Z)
A logic function can be represented with
Truth table
Canonical product
Canonical sum
Minterm list with
Maxterm list with
