CPSC 121 – Models of Computation
Module 02. Conditionals and Logical Equivalences
Prof. Karina Mochetti
2020.W1
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Announcements
Ask CPSC 121
http://www.cs.ubc.ca/~mochetti/CPSC121.html
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Goals
Translate between simple natural language statements and propositional logic.
Given a propositional logic statement, apply an equivalent rule to create an equivalent statement.
Explore alternate forms of propositional logic statements by application of equivalence rules.
Evaluate propositional logic as a “model of computation” for combinational circuits, including at least one explicit shortfall (e.g., referencing gate delays, fan-out, transistor count, wire length, instabilities, shared sub-circuits, etc.).
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Reading Review
Conditional
if p then q p only if q pimpliesq qif p
If you show up for work Monday morning, then you will get the job.
p is called the hypothesis (or antecedent) and q is called the conclusion (or consequent).
The sentence says nothing about what will happen if the condition is not met.
pqp→q FT FT TF TTT
F
T
F
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Reading Review
p→q
Equivalence: ∼p ∨ q Negation: p ∧ ∼q Contrapositive: ∼q → ∼p Converse: q → p
Inverse: ∼p → ∼q
Order of Operations for Logical Operators:
Negation
Disjunction and Conjunction Conditional and Biconditional
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Reading Review
Biconditional
p if, and only if, q p iff q
It is true if both p and q have the same truth values and is
false if p and q have opposite truth values.
p is a sufficient condition for q means if p then q. p is a necessary condition for q means if q then p.
p is a necessary and sufficient condition for q means p if, and only if, q.
pqp↔q FT FF TF TT
F
T
F
T
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Quiz #02 Feedback
Very well done overall!!! \o/
Question 3: Which of the following has the same meaning as
p → ∼q ?
A Anytime that p is true, q must be false.
B p can not be true unless q is false.
C q can not be false unless p is true.
D ifpistruethenqisfalse.
E q and p can never have the same truth value (both true or both false).
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Examples
p = Metallica is playing in Vancouver q = I’m going to a Metallica’s concert
Let me being happy means that the statement is True.
Conditional: p → q
If Metallica plays in Vancouver and I miss, I will be sad. If Metallica doesn’t come to Vancouver, then maybe I’ll travel to see them or maybe I’ll be home, but I am not sad because I am not missing their concert in Vancouver.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Examples
p = Metallica is playing in Vancouver q = I’m going to a Metallica’s concert
Let me being happy means that the statement is True.
Inverse: ∼p → ∼q
If Metallica doesn’t play in Vancouver, I’m not going to see them. I will be sad if I have to travel to see them and I don’t like them so much to be sad if they come here and I miss it.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Examples
p = Metallica is playing in Vancouver q = I’m going to a Metallica’s concert
Let me being happy means that the statement is True.
Converse: q → p
If I’m going to a Metallica’s concert, then they are playing in Vancouver. But maybe they are playing here and I’m not there. I’m not such a fan, so I’m not traveling and I would not be sad if I missed it.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Examples
p = Metallica is playing in Vancouver q = I’m going to a Metallica’s concert
Let me being happy means that the statement is True.
Contrapositive: ∼q → ∼p
If I’m not going to a Metallica’s concert, then they are not playing in Vancouver, because if they were, I’d be crying about missing it.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Examples
p = Metallica is playing in Vancouver q = I’m going to a Metallica’s concert
Let me being happy means that the statement is True.
Biconditional: p ⇔ q
If Metallica comes to Vancouver, I’m at their show and I am only at their show here. Traveling to see them makes me as sad as loosing their concert here.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Logic vs Everyday English
Be careful!
The meaning of if p then q in propositional language is not quite the same as in normal language.
In logic, a hypothesis (p) and conclusion (q) are not required to have related subject matters.
In informal language, simple conditionals are often used to mean biconditionals.
If you rob a bank, then you will go to jail!
Assuming the statement is truth, we need to evaluate:
The truth value of p (whether or not I lied)
The truth value of q (whether or not you will go to jail)
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Logic vs Everyday English
If you rob a bank, will you go to jail? a. Yes
b. No
c. Maybe
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Logic vs Everyday English
If you go to jail, have you robbed a bank? a. Yes
b. No
c. Maybe
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Logical Equivalence
Logical Equivalence
Two propositions are logically equivalent if they have the same Truth Table.
Showing equivalence:
1 Draw both truth tables and check if they are equal.
2 Use rules to change one proposition into the other:
We state the theorem we want to prove.
We indicate the beginning of the proof by Proof:
We start with one side and work towards the other, one step at a time, justifying each step.
We indicate the end of the proof by QED (Quod erat demonstrandum) or .
Tip: Usually we will simplify the more complicated proposition, instead of trying to complicate the simpler one.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Logical Equivalence Proofs: Laws
Identity Laws
p∧T≡p p∨F≡p
Universal Bounds Laws
p∧F≡F p∨T≡T
Idempotent Laws
p∧p≡p p∨p≡p
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Logical Equivalence Proofs: Laws
Commutative Laws
p∧q≡q∧p p∨q≡q∨p
Associative Laws
p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r
Distributive Laws
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Logical Equivalence Proofs: Laws
Absorption Laws
p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p
Negation Laws
p ∧ ∼p ≡ F p ∨ ∼p ≡ T
Double Negation Law
∼∼p ≡ p
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Logical Equivalence Proofs: Laws
DeMorgan’s Laws
∼(p ∧ q) ≡ (∼p) ∨ (∼q) ∼(p ∨ q) ≡ (∼p) ∧ (∼q)
Definition of XOR
p ⊕ q ≡ (p ∨ q)∧ ∼ (p ∧ q)
Definition of IF
p → q ≡ ∼p ∨ q
Contrapositive Law
p → q ≡ (∼q) → (∼p)
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Logical Equivalence Proofs: Summary of Laws
Identity p∧T ≡p Laws p∨F≡p
Universal p ∧ F ≡ F Bounds Laws p ∨ T ≡ T
Idempotent p ∧ p ≡ p Laws p∨p≡p
Commutative p∧q≡q∧p Laws p∨q≡q∨p
Associative p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r Laws p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r
Distributive p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Laws p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Absorption p∨(p∧q)≡p Laws p ∧ (p ∨ q) ≡ p
Negation p ∧ ∼p ≡ F Laws p ∨ ∼p ≡ T
Double Negation Law ∼∼p ≡ p
DeMorgan’s ∼(p ∧ q) ≡ (∼p) ∨ (∼q) Laws ∼(p ∨ q) ≡ (∼p) ∧ (∼q)
Definition of XOR p ⊕ q ≡ (p ∨ q)∧ ∼ (p ∧ q)
Definition of IF p → q ≡ ∼p ∨ q
Contrapositive Law p → q ≡ (∼q) → (∼p)
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Logical Equivalence Proofs
Prove that (∼a∧b)∨a≡a∨b. Proof: (∼a ∧ b) ∨ a ≡ a ∨ (∼a ∧ b)
Commutative Law Distributive Law
Identity Law
What is missing?
a. (a∨b)
b. F ∧ (a ∨ b)
c. a∧(a∨b)
d. Something else
e. Not enough info to tell
≡ (a ∨ ∼a) ∧ (a ∨ b) ≡ ?????
≡ a ∨ b
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Worksheet
Questions 1 – 2
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Questions?
Ask CPSC 121
http://www.cs.ubc.ca/~mochetti/askCPSC121.html
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
It has 3 inputs a, b, select and just one output m. It outputs a if select is False, and b if select is True.
a b sel m
FF FF FF FT TT TF TT TTTT
F
F
F
T
T
F
T
T
F
F
F
T
T
F
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
Let’s implement a circuit based on this Truth Table.
m = (∼sel ∧a)∨(sel ∧b)
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
Let’s implement a circuit based on this Truth Table.
m = (∼sel ∧a)∨(sel ∧b) But there is a problem with this circuit…
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
Gates are not instantaneous!!!
If we change the input of a gate at time t = 0.
The output of the gate will only reflect the change some time
later.
This time gap is called the gate delay.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
Assume the gate delay is 10 ns and a, b, sel are initially True.
How long will it take before output correctly reflects any changes in a, b, sel?
a. 10 ns
b. 20 ns
c. 30 ns
d. 40 ns
e. It may never happen.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
t = 0 ns: we are going to change sel from True to False and track what happens.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
t = 5 ns: since the gate delay is 10 ns, no reflection is seen on the circuit.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
t = 10 ns: all gates can reflect the changes seen so far, but not those made now.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
t = 20 ns: all gates can reflect the changes seen so far and this time it changes the output.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
t = 30 ns: finally the output gate changes again to reflect the correct answer.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
So the output changed from T (old output) to F and then to T (new output).
This is called an instability. The cause of the problem:
The information from select travels on two different paths to the output
These paths contain different numbers of gates
The shorter path may affect the output until the information on the longer path catches up
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
Which one(s) of the following oper- ation may cause an instability?
a. Changing a or b only
b. Changing select, when at
exactly one of a, b is F
c. Changing select, when both a, b are F
d. Both (a) and (b)
e. None of (a), (b) or (c).
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
When a and b are False, the output of both AND is False no matter the value of sel so changing sel does not affect on the output and there is no instability.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
When a is False and b is True, the AND with a as input is always False, so the output will come only from the AND with b as input. Since there is only one path for sel, then there is no instability.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
When a is True and b is False, the AND with b as input is always False, so the output will come only from the AND with a as input. Since there is only one path for sel, then there is no instability.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Multiplexers
When a and b are True, the output should be True, we can enforce that by adding an AND gate in the middle. For all other cases it will be False and maintain the original output.
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Questions?
Ask CPSC 121
http://www.cs.ubc.ca/~mochetti/askCPSC121.html
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Exercise
Prove:
(a ∧ ∼b) ∨ (∼a ∧ b) ≡ (a ∨ b) ∧ ∼(a ∧ b)
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
Exercise: Solution
Prove:
(a ∧ ∼b) ∨ (∼a ∧ b) ≡ (a ∨ b) ∧ ∼(a ∧ b)
(a∨b)∧∼(a∧b) ≡ (a∨b)∧(∼a∨∼b)
≡ ((a ∨ b) ∧ ∼a) ∨ ((a ∨ b) ∧ ∼b)
(De Morgan’s Law) (Distributive Law) (Commutative Law) ≡ ((∼a∧a)∨(∼a∧b))∨((∼b∧a)∨(∼b∧b)) (Dist. Law)
≡ (∼a∧(a∨b))∨(∼b∧(a∨b))
≡(F ∨(∼a∧b))∨((∼b∧a)∨F) ≡ (∼a ∧ b) ∨ (∼b ∧ a)
≡ (∼a ∧ b) ∨ (a ∧ ∼b)
≡ (a ∧ ∼b) ∨ (∼a ∧ b)
(Negation Law) (Identity Law) (Commutative Law) (Commutative Law)
Module 02. Conditionals and Logical Equivalences
CPSC 121 – Models of Computation
More Exercises
1 Consider the code:
if target = value then
if lean-left-mode = true then
call the go-left() routine
else
call the go-right() routine
else if target < value then
call the go-left() routine
else
call the go-right routine
Let gl mean “the go-left() routine is called”. Complete the following:
gl ↔
Module 02. Conditionals and Logical Equivalences
CPSC 121 - Models of Computation
More Exercises
2 The Java [String] equals() method returns true if and only if
the the
Let
n1:
n2:
nt:
s: the two objects are strings that represent the same sequence of characters.
Is the sentence logically equivalent to nt ↔ (n1 ∧ n2) ∨ s? Why or why not?
argument is not null and is a String object that represents same sequence of characters as this object.
the string is null
the argument is null the method returns true
Module 02. Conditionals and Logical Equivalences
CPSC 121 - Models of Computation
Meme
Module 02. Conditionals and Logical Equivalences
CPSC 121 - Models of Computation