# 编程代考 Boolean Algebra – cscodehelp代写

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
• ĀistrueifAisfalse • Ā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̄ 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.