Boolean Algebra
• High-level language program (in C) swap (int v[], int k) {
int temp = v[k]; v[k] = v[k+1]; v[k+1] = temp;
}
• Assembly language program (for MIPS) swap: sll $2, $5, 2 add $2, $4,$2
lw $15, 0($2) lw $16, 4($2) sw $16, 0($2) sw $15, 4($2) jr $31
• Machine (object) code (for MIPS)
C compiler
The Big Picture
assembler
000000 00000 00101 0001000010000000
000000 00100 00010 0001000000100000 …
The Big Picture
How do 0s and 1s communicate with the hardware? We will learn how to design circuits!
COMP273 Mc • BooleanFunctions
• Truth Tables
Truth Table
Truth Table
• Considerbinaryvariables,A,B
– Possible values are 0 (FALSE) and 1 (TRUE)
• Different possible inputs with n operands = 2n – 2 binary operands: 22 = 4 different possible inputs – 4 binary operands: 24 = 16 different possible inputs
A
B
C
A
B
A
0
1
COMP273 Mc Table
• Considerbinaryvariables,A,B
– Possible values are 0 (FALSE) and 1 (TRUE)
• Differentpossibleinputswithnoperands=2n – 2 binary operands: 22 = 4 different possible inputs – 4 binary operands: 24 = 16 different possible inputs
A
B
C
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
A
0
1
A
B
0
0
0
1
1
0
1
1
COMP273 Mc Operations: AND
• AND operator
• A∙B istrueifAandBarebothtrue • Logicalproduct
A
B
A∙B
0
0
0
1
1
0
1
1
COMP273 Mc Operations: AND
• AND operator
• A∙B istrueifAandBarebothtrue • Logicalproduct
A
B
A∙B
0
0
0
0
1
0
1
0
0
1
1
1
COMP273 Mc Operations: OR
• OR operator • A+Bistrueif
– A is true
– B is true
– A and B are both true
• Logicalsum
A
B
A+B
0
0
0
1
1
0
1
1
COMP273 Mc Operations: OR
• OR operator • A+Bistrueif
– A is true
– B is true
– A and B are both true
• Logicalsum
A
B
A+B
0
0
0
0
1
1
1
0
1
1
1
1
COMP273 Mc Operations: NOT
• NOT operator
• ĀistrueifAisfalse • ĀisfalseifAistrue
A
Ā
0
1
1
0
COMP273 Mc Operations: NOT
• TheTruthtabledefinesallpossibleoutcomes
• AND, OR, and NOT are the common Boolean Operations
A
B
A∙B
A+B
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
1
A
Ā
0
1
1
0
COMP273 Mc Common Binary Operations
• Three other very common operations: – NAND: Not And
– NOR: Not OR
– XOR: Exclusive OR
A
B
AND
OR
NAND
NOR
XOR
0
0
0
0
1
1
0
0
1
0
1
1
0
1
1
0
0
1
1
0
1
1
1
1
1
0
0
0
COMP273 Mc OMP273 Mc on Notation
OR(A,B) AND(A,B) NOT(A) A+B A∙B Ā A|B A&B ~A
A || B A && B !A AvB A^B ¬A
AB A’ When do we use which?
COMP273 Mc of Boolean Algebra
Boolean Expression
Boolean Expression
• ABooleanexpression/functionisanalgebraicexpression consisting of binary variables and the logic operation symbols
• Any Boolean function can be written in terms of AND, OR, NOT
COMP273 Mc OMP273 Mc : Derive Boolean Expression
• Three inputs, A, B, and C
• Three outputs, D, E, and F.
– D is true if at least one input is true
– E is true if exactly two inputs are true – F is true only if all three inputs are true
• Find the Boolean expression for D, E, and F
Find the Truth Table
Find the truth table: D is true if at least one input is true
A
B
C
D
E
F
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
COMP273 Mc the Truth Table
Find the truth table: E is true if exactly two inputs are true
A
B
C
D
E
F
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
COMP273 Mc the Truth Table
Find the truth table: F is true only if all three inputs are true
A
B
C
D
E
F
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
1
1
1
0
0
1
0
1
0
1
1
1
1
1
0
1
1
1
1
1
1
0
COMP273 Mc Boolean Expression
A
B
C
D
E
F
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
1
1
1
1
0
1
0
0
1
0
0
1
0
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
1
COMP273 Mc is true only if all three inputs are true F=
Derive Boolean Expression
A
B
C
D
E
F
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
1
1
1
1
0
1
0
0
1
0
0
1
0
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
1
COMP273 Mc is true if at least one input is true D=
Derive Boolean Expression
A
B
C
D
E
F
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
1
1
1
1
0
1
0
0
1
0
0
1
0
1
1
1
0
1
1
0
1
1
0
1
1
1
1
0
1
COMP273 Mc is true if exactly two inputs are true E=
COMP273 Mc of Products vs Product of Sums
• Canonical form for any logic function
– Only two levels of logic operations, one AND, the other OR – Possible inversion on the final output.
E = (A ∙ B ∙ C’) + (A ∙ C ∙ B’) + (B ∙ C ∙ A’) Sum-of-Product E = (A’+B’+C) ∙ (A’+C’+B) ∙ (B’+C’+A) Product-of-sum
Boolean Algebra
Are two Boolean functions equivalent?
Prove it or find values to show that they are not! X = A ∙ B ∙ C’ + A ∙ C ∙ B’ + B ∙ C ∙ A’
Y = B ∙ (A ∙ C’ + C ∙ A’)
COMP273 Mc ‘t Care!
COMP273 Mc on’t Care
• Situations where we do not care about the value of an output
• In the truth table, marking X for “Don’t Care” (instead of 0 or 1) – e.g., Y is true if A is true or B is true.
If A is true, then Y is true. We don’t need to check B
– e.g., Y is true if A is true and B is true
If A is false, then Y is false. We don’t need to check B
Don’t Care
• Write the truth table, marking X for “Don’t Care” – Inputs A, B, C
– Output Y
– If A is true, output is B
– If A is false, output is C
A
B
C
Y
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
1
COMP273 Mc ’t Care
• Write the truth table, marking X for “Don’t Care” – Inputs A, B, C
– Output Y
– If A is true, output is B
– If A is false, output is C
A
B
C
Y
0
x
0
0
0
x
1
1
0
x
0
0
0
x
1
1
1
0
x
0
1
0
x
0
1
1
x
1
1
1
x
1
COMP273 Mc ’t Care
• Write the truth table, marking X for “Don’t Care” – Inputs A, B, C
– Output Y
– If A is true, output is B
– If A is false, output is C
A
B
C
Y
0
x
0
0
0
x
1
1
1
0
x
0
1
1
x
1
COMP273 Mc
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
Y
0
0
0
1
0
x
0
1
1
0
x
1
1
0
x
Don’t Care
• WritetheBooleanExpressionforY
1 1
COMP273 McGill
1
1
Simplify Boolean Expression
COMP273 Mc Boolean Expression
• Why? Minimize the complexity and size of the circuit – Using the law of Boolean algebra
– Using Karnaugh Maps
• TheproblemisbeyondthescopeofCOMP273
– Simplify Boolean function is Optional in this course
– However, if you simplify your boolean expression, it’s easier for you to design your circuits
Simplify Boolean Expression
Y = A’B’C + A’BC + AB’C’ + AB’C
A
B
C
Y
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
0
1
1
1
0
COMP273 Mc glance at Karnaugh maps
COMP273 McGill
• “Group” the 1’s
• All 1’s should be circled at least once
Brief glance at Karnaugh maps
A
B
C
Y
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
0
1
1
1
0
B’C’
B’C
BC
BC’
A’
0
1
1
0
A
1
1
0
0
COMP273 Mc
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
Y
0
0
0
1
0
x
0
1
1
0
x
1
1
0
x
Simplify Boolean Expression
Y = A’B’CD + A’BCD + AB’C’D’ + AB’CD + ABC’D’ + ABCD
1 1
COMP273 McGill
1
1
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
0
0
1
0
x
0
1
1
0
x
1
1
0
x
Simplify Boolean Expression
C’ D’
C’ D
C D
C D’
A’ B’
0
0
1
0
A’ B
0
x
1
0
A B
1
0
1
x
A B’
1
0
1
x
1 1
COMP273 Mc
1
Y
1
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Y
0
0
0
1
0
x
0
1
1
0
x
1
1
0
x
1
Simplify Boolean Expression
Boolean algebra: Y = CD + AC’D’ Karnaugh Map: Y = CD + AD’ Why?
Let’s treat the 2nd and the 3rd don’t care as 1.
COMP273 Mc and more information
• How to drive a Boolean expression
– Step 1: Write down the truth table
– Step 2: Find the sum-of-product or product-of-sum – Step 3: Simplify it (optional)
• References
– Notes: truth-tables.pdf
– Textbook: Appendix B of 5th edition