CPSC 121 – Models of Computation
Module 01. Propositional Logic
Prof. Karina Mochetti
2020.W1
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Announcements
Ask CPSC 121
http://www.cs.ubc.ca/~mochetti/CPSC121.html
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Questions
Yes, the form works for everyone who just test it!
We at Computer Science are pessimists, we usually think of the worst case, not the average, specially because average is hard to tell (it depends on how the input is). But for some problems we do consider the average.
I am always referring to the Course Website, never Canvas.
Problems with time zone, send email to Trey, the course coordinator.
CPSC 110 is a co requisite, if you are waitlisted and don’t get in, you cannot take 121, unfortunately.
Tutorials are marked for attendance. Worksheets are not graded.
Chat on Zoom!
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Goals
Use propositional logic expressions to build computational systems.
Use digital logic circuits to build computational systems.
Find the equivalence between propositional logic expressions and digital logic circuits.
Apply propositional logic expressions and digital logic circuits to solve the light switch problem.
Apply propositional logic expressions and digital logic circuits to solve the 7-segments display problem.
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Reading Review
A statement (or proposition) is a sentence that is TRUE or FALSE but not both.
Negation
not p
∼p
p ∼p FT FT
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Reading Review
A statement (or proposition) is a sentence that is TRUE or FALSE but not both.
Negation
not p
∼p
p ∼p FT FT
Conjunction
p and q
p∧q
pqp∧q FF FF TF TTT
F
T
F
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Reading Review
A statement (or proposition) is a sentence that is TRUE or FALSE but not both.
Negation
not p
∼p
p ∼p FT FT
Conjunction Disjunction
p and q p or q
p∧q p∨q
pqp∧q pqp∨q FFFF FFFT TFTT TTT TTT
F
T
F
F
T
F
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Reading Review
A statement (or proposition) is a sentence that is TRUE or FALSE but not both.
Exclusive Or
p xor q
p⊕q
(p ∨ q) ∧ ∼(p ∧ q)
pqp⊕q FF FT TT TTF
F
T
F
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Reading Review
A statement (or proposition) is a sentence that is TRUE or FALSE but not both.
Exclusive Or Neg. Conjunction
p xor q p nand q
p⊕q p|q
(p ∨ q) ∧ ∼(p ∧ q) ∼(p ∧ q)
pqp⊕q pqp|q FFFT FTFT TTTT TTFTTF
F
T
F
F
T
F
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Reading Review
A statement (or proposition) is a sentence that is TRUE or FALSE but not both.
Exclusive Or Neg. Conjunction Neg. Disjunction
p xor q p nand q p nor q
p⊕q p|q p↓q
(p ∨ q) ∧ ∼(p ∧ q) ∼(p ∧ q) ∼(p ∨ q)
pqp⊕q pqp|q pqp↓q FFFTFT FTFTFF TTTTTF TTF TTF TTF
F
T
F
F
T
F
F
T
F
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Reading Review
A tautology is a statement form that is always TRUE.
A contradication is a statement form that is always FALSE.
Two statement forms are called logically equivalent if, and only if, they have identical truth values.
De Morgan’s Law
∼(p ∧ q) ≡ ∼p ∨ ∼q
p q ∼p ∼q p∧q ∼(p∧q) ∼p∨∼q FT FT TT TTFFTFF
F
T
T
F
T
T
T
F
F
T
F
F
T
F
T
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Reading Review
TRUE: switch on, high voltage, 1 FALSE: switch off, low voltage, 0
Circuits have binary inputs and produce binary outputs.
Each logical expression can be represented as a logic gate on a circuit.
A circuit is a sequence of logic gates connected.
A circuit can be represented as a proposition and a truth table.
Two digital logic circuits are equivalent if, and only if, their input/output tables are identical.
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Quiz #01 Feedback
Very very well done overall!!! \o/
Just be careful:
∼a∨∼b is not the same as ∼(a∨b). ∼a∧∼b is not the same as ∼(a∧b).
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Truth Table
A leap year is is a calendar year that contains an additional day (February 29th), it happens if: Y is divisible by 4 and Y is divisible by 100 and Y is divisible by 400 or Y is divisible by 4 and is not divisible by 100
p: Y divisible by 4 q: Y divisible by 100 r: Y divisible by 400
p q r p∧q∧r p∧∼q (p∧q∧r)∨(p∧∼q) FF FF FF FF TT TT TF TT
F
F
F
F
F
T
F
F
T
F
F
F
F
T
T
F
F
F
F
T
F
T
F
T
T
T
F
T
F
T
F
F
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Truth Table
Combinations in a truth table don’t need to be listed in a specific order.
We recommend an specific order, with k variables by the columns:
1st. 2k−1 FALSE follow by 2k−1 TRUE
2nd. 2k−2 FALSE follow by 2k−2 TRUE, repeated 2 times
3rd. 2k−3 FALSE follow by 2k−3 TRUE, repeated 4 times .
kth. 1 FALSE follow by 1 TRUE, repeated 2k−1 times
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Truth Table
For k = 3 variable, we have:
1st. 22 =4FALSEfollowby22 =4TRUE
p q r
F F F F T T T T
statement
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Truth Table
For k = 3 variable, we have:
1st. 22 =4FALSEfollowby22 =4TRUE
2nd. 21 = 2 FALSE follow by 21 = 2 TRUE, repeated 2 times
pq r
FF FF FT FT TF TF TT TT
statement
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Truth Table
For k = 3 variable, we have:
1st. 22 =4FALSEfollowby22 =4TRUE
2nd. 21 = 2 FALSE follow by 21 = 2 TRUE, repeated 2 times
3rd. 20 = 1 FALSE follow by 20 = 1 TRUE, repeated 4 times
p q r statement FFF
FFT
FTF
FTT TFF TFT TTF TTT
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Circuits to Propositions
Our first algorithm
Find the logical expression that corresponds to a circuit’s output
Write the operator for the gate that produces the circuit’s output.
Replace the operator’s left argument by the expression for the circuit connected to the gate’s first input.
Replace the operator’s right argument by the expression for the circuit connected to the gate’s second input.
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Circuits to Propositions
y=···
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Circuits to Propositions
y = A ∧ ∼B
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Circuits to Propositions
y = (C ∨ D) ∧ ∼B
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Circuits to Propositions
y = (C ∨ D) ∧ ∼(D ⊕ E)
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Circuits to Propositions
y = ((x1⊕x3)∨D)∧∼(D ⊕E)
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Circuits to Propositions
y = ((x1⊕x3)∨(x1⊕x2))∧∼((x1⊕x2)⊕E)
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Circuits to Propositions
y = ((x1⊕x3)∨(x1⊕x2))∧∼((x1⊕x2)⊕(x3⊕x4))
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Circuits to Propositions
y = ((x1⊕x3)∨(x1⊕x2))∧∼((x1⊕x2)⊕(x3⊕x4))
What does this circuit compute?
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Circuits to Propositions
y = ((x1⊕x3)∨(x1⊕x2))∧∼((x1⊕x2)⊕(x3⊕x4))
What does this circuit compute?
When the input has exactly 2 TRUE and 2 FALSE.
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Light Switches
Problem Definition
Design a light that changes state whenever any of the switches that control it is flipped. Ideally your solution would work with any number!
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Light Switches: Approach
Make sure to understand what we are designing.
Use propositional logic to model the circuit’s desired output.
Start with simple versions of the problem (1 switch, 2 switches, until we reach n switches).
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Light Switches: Output
Which of these would be usable (most useful) as the output of our circuit?
a. The switch is flipped
b. The switch is on
c. The light is on
d. The light changed state
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Light Switches: Input
Which of these would be usable (most useful) as the input of our circuit?
a. The switch is flipped
b. The switch is on
c. The light is on
d. The light changed state
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Light Switches: One Switch
Is the light on or off when the switch is on?
a. Always on.
b. Always off.
c. Depends, but a correct solution should always do the same thing.
d. Depends, and a correct solution might do different things at different times.
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Light Switches: One Switch
Which circuit(s) is/are correct solution(s) for one switch?
a. b. c.
d. Twoofa,b,c
e. All three a, b, c
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Light Switches: Two Switches
Which circuit(s) is/are correct solution(s) for two switches?
a. b. c.
d. Both a and b
e. Both b and c
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Questions?
Ask CPSC 121
http://www.cs.ubc.ca/~mochetti/askCPSC121.html
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Light Switches: 3 Switches
Can we built the solution for 3 switches from the 2 switches problem?
Let’s remember the solution for 2 switches.
s1 s2 x FF FT TT TF
F
T
F
T
CPSC 121 – Models of Computation
Module 01. Propositional Logic
Light Switches: 3 Switches
Can we built the solution for 3 switches from the 2 switches problem?
Let’s remember the solution for 2 switches.
If the third switch is always off, then the solution is the same circuit from before.
s1 s2 x FF FT TT TF
F
T
F
T
CPSC 121 – Models of Computation
Module 01. Propositional Logic
Light Switches: 3 Switches
Can we built the solution for 3 switches from the 2 switches problem?
Let’s remember the solution for 2 switches.
If the third switch is always off, then the solution is the same circuit from before.
If the third switch is turned on, then we need to change the output from before, i.e., negate the output from before.
s1 s2 x FF FT TT TF
F
T
F
T
CPSC 121 – Models of Computation
Module 01. Propositional Logic
Light Switches: 3 Switches
Can we built the solution for 3 switches from the 2 switches problem?
Let’s remember the solution for 2 switches.
If the third switch is always off, then the solution is the same circuit from before.
If the third switch is turned on, then we need to change the output from before, i.e., negate the output from before.
This is exactly what our circuit does already for 2 switches!!!
s1 s2 x FF FT TT TF
F
T
F
T
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Light Switches: N Switches
We can built the problem for any number of switches from the first problem with only 2. That is called Mathematical Induction and we will learn more about that later on the term!
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Light Switches: N Switches
We can built the problem for any number of switches from the first problem with only 2. That is called Mathematical Induction and we will learn more about that later on the term!
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Light Switches: N Switches
We can built the problem for any number of switches from the first problem with only 2. That is called Mathematical Induction and we will learn more about that later on the term!
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Light Switches: N Switches
We can built the problem for any number of switches from the first problem with only 2. That is called Mathematical Induction and we will learn more about that later on the term!
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Circuit Design Tip
First determine the inputs and the output Then build the truth table.
Finally turn it into a circuit.
Module 01. Propositional Logic
CPSC 121 – Models of Computation
7-Segment Displays
Problem Description
Design a circuit that displays the numbers 0 through 9 using seven LEDs (lights) in the shape illustrated below.
Module 01. Propositional Logic
CPSC 121 – Models of Computation
7-Segment Displays: Input
What is the smallest number of inputs (wires going into the circuit) possible?
a. 1
b. 4
c. 7
d. 10
e. None of the above
Module 01. Propositional Logic
CPSC 121 – Models of Computation
7-Segment Displays: Input
number a b c d
0F 1T 2F 3T 4F 5T 6F 7T 8F 9T
F
F
F
F
F
F
F
F
T
F
F
T
F
T
F
F
T
F
F
T
T
F
T
T
T
F
F
T
F
F
Module 01. Propositional Logic
CPSC 121 – Models of Computation
7-Segment Displays: Output
How many outputs (lights) are there? a. 1
b. 4
c. 7
d. 10
e. None of the above
Module 01. Propositional Logic
CPSC 121 – Models of Computation
7-Segment Displays
Let us look at the bottom-left segment (letter E on the illustration). Which column completes the truth table for this segment?
num a b c d E a. b. c. d. e. 0?T0 1?F2 2?T6 3?F8 4?T 5?F 6?T 7?F 8?T 9?F
F
F
F
F
F
F
F
T
F
F
T
F
F
F
T
T
F
T
F
F
F
T
F
T
F
T
T
F
F
T
T
T
T
F
F
F
T
F
F
T
T
T
0
F
F
3
T
F
4
F
T
8
F
T
F
F
T
F
F
F
T
T
F
F
Module 01. Propositional Logic
CPSC 121 – Models of Computation
7-Segment Displays: Proposition
Which proposition is true only for the red row?
num a b c d
0F
1T
2F
3T
4F c. ∼a∧∼b∧c∧∼d 5T
6F 7T 8F 9T
F
F
F
F
F
F
F
F
T
F
F
T
F
T
F
F
T
F
F
T
T
F
T
T
T
F
F
T
F
F
a. a∧b∨c∧d
b. ∼a∨∼b∨c∨∼d
d. a⊕b⊕c⊕d
e. None of the above
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Worksheet
Questions 1 – 7
Module 01. Propositional Logic
CPSC 121 – Models of Computation
7-Segment Displays: Approaches
One that’s mechanical and easy to use, but gives very long propositions in general.
One that relies on spotting patterns: it’s harder but produces much shorter propositions.
There is a third approach using something called Karnaugh maps; we will post information about it but not discuss it in class or expect you to use it on exams.
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Questions?
Ask CPSC 121
http://www.cs.ubc.ca/~mochetti/askCPSC121.html
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Exercise
What is the proposition for this circuit?
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Exercise: Solution
What is the proposition for this circuit?
y=···
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Exercise: Solution
What is the proposition for this circuit?
y=A∧B∧C
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Exercise: Solution
What is the proposition for this circuit?
y = ∼(a ∨ b) ∧ B ∧ C
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Exercise: Solution
What is the proposition for this circuit?
y =∼(a∨b)∧(a⊕c)∧C
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Exercise: Solution
What is the proposition for this circuit?
y = ∼(a ∨ b) ∧ (a ⊕ c) ∧ (D ∨ E)
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Exercise: Solution
What is the proposition for this circuit?
y =∼(a∨b)∧(a⊕c)∧((b∧d)∨E)
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Exercise: Solution
What is the proposition for this circuit?
y =∼(a∨b)∧(a⊕c)∧((b∧d)∨∼(c∧d))
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Exercise: Solution
What is the proposition for this circuit?
y =∼(a∨b)∧(a⊕c)∧((b∧d)∨∼(c∧d))
Module 01. Propositional Logic
CPSC 121 – Models of Computation
More Exercises
1 Finish the problem by building circuits for the other 5 segments.
2 Design a circuit that takes three bits as input, and outputs the binary representation for their sum.
3 Build the circuit for the 4-segment Boolean display problem.
4 Build the truth table that displays the numbers 1 through 9 represented by four Boolean values p, q, r, and s on a 4-segment Boolean display.
Module 01. Propositional Logic
CPSC 121 – Models of Computation
Meme
Module 01. Propositional Logic
CPSC 121 – Models of Computation