Class Notes (1,000,000)
CA (620,000)
UTSG (50,000)
CSC (1,000)
Lecture

# CSC258H1 Lecture Notes - Canonical Normal Form, Boolean Expression

Department
Computer Science
Course Code
CSC258H1
Professor
Steve Engels

This preview shows half of the first page. to view the full 1 pages of the document.
CIRCUIT CREATION
Making logic with gates
o Logic gates like the following allow us to create an output value,
based on two inputs
o What do we do in the case of more complex circuits, with several
inputs and more than one output?
Circuit example
o The circuit on the right has
tree inputs (A, B and C)
and two outputs (X and Y)
o What logic is needed to set
X high when all three
inputs are high?
o What logic is needed to set
Y high when the number of high inputs is odd?
Combinational Circuits
o Small problmes can be solved easily
o Larger problems require a more systematic approach
Ex. Given three inputs A, B, and C, make output Y high in the
case where all of the inputs are low, or when A and B are low
and C is high, or when A and C are low but B is high, or when A
is low and B and C are high.
Creating logic
o Basic steps
1. Create truth tables
2. Express as boolean expression
3. Convert to gates
o The key to an efficient design?
Spending extra time on Step 2
Creating Boolean expressions
o Terms to know:
Minterm = an AND expression with every input present in
true or complemented form, i.e. each row of a truth table
Set of values & the associated output
Maxterm = an OR expression with every input present in
true or complemented form
Ex. For 4 given inputs A, B, C and D
Valid minterms:
                    
Valid maxterms:
                    
Nether min nor maxterms:
              
AND expressions are denoted by the muliplcation symbol
Ex.               
OR expressions are denoted by the addition symbol
Ex.          
NOT is denoted by multiple symbols
Ex. 
XOR occurs rarely in circuit expressions
Ex. 
o Given n inputs, there are 2n minterms and maxterms possible
Minterms are labled as mx from m0 (A*B*C) to m7 (A*B*C)
Maxterms are labled as Mx from M0 (A+B+C) to M7 (A+B+C)
X indicates the entry in the truth table
Using Minterms and Maxterms
o A single minterm indicates a set of inputs that will make the output
go high
o Ex. m2 output (Y1) only goes high in the third line of truth table
A
B
C
D
m2
m8
Y1
Y2
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
1
0
1
1
0
1
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
1
0
1
1
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
1
0
1
1
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
1
0
0
0
0
1
1
1
0
0
0
0
0
1
1
1
1
0
0
0
0
o When OR two minterms (m2+m8), result is output (Y2) that goes
high in both minterm cases (3rd and 9th row)
o Two canonical forms of boolean expressions:
Sum-of-Minterms (SOM)
Since each minterm corresponds to a single high output
in the truth table, the combined high outputs are a
union of these minterms
Also known as: Sum-of-Products
Ex. Y = m2 + m6 + m7 + m10
A
B
C
D
m2
m6
m7
m10
Y
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
1
0
1
1
1
0
0
1
0
1
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
1
1
1
0
1
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
Product-of-Maxterms (POM)
Since each maxterm only produces a single low output
in the truth talbe, the combined low outputs are an
intersection of these maxterm expressions
Also known as: Product-of-Sums
Ex. Y = M3 * M5 * M7 * M10 * M14
A
B
C
D
M3
M5
M7
M10
M14
Y
0
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
1
0
0
1
0
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
0
1
0
0
1
1
1
1
1
1
0
1
0
1
1
0
1
1
1
0
0
1
1
0
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
0
1
0
0
0
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
0
1
0
1
1
1
0
1
0
1
0
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
o Sum-of-Minterms is a way of expressing which inputs cause the
output to go high.
Assumes that the truth table columns list the input according
to some logical or natural order
o Minterm and Maxterm expressions are used for efficiency reasons
More compact that display entire truth table
Sum-of-minterms are useful in cases with very few input
combinations that produce very high output
Sum-of-maxterms are useful when expressing truth tables that
have very few low output cases