CPSC 121 – Models of Computation
Module 05. Predicate Logic
Prof. Karina Mochetti
2020.W1
Module 05. Predicate Logic
CPSC 121 – Models of Computation 1 / 35
Announcements
What is new!
http://www.cs.ubc.ca/~mochetti/CPSC121.html
Module 05. Predicate Logic
CPSC 121 – Models of Computation 2 / 35
Goals
Understand statements in formal predicate logic notation and translate to closely matching informal language.
Understand the difference between proposition logic and predicates and when each one apply.
Translate between statements in formal predicate logic notation and equivalent statements in closely matching informal language.
Build statements about the relationships between properties of various objects using predicate logic.
Module 05. Predicate Logic
CPSC 121 – Models of Computation 3 / 35
Reading Review
Predicates
Some sentences can not be translated into proposition statements because it depends on the value of its variables that can be more than True or False.
P(x) : x2 > x
Q (x , y ) : x + y ≥ 10
P(2) is true. P(1) is false.
Truth Set
If P(x) is a predicate and x has domain D, the truth set of P(x) is the set of all elements of D that make P(x) true.
x ∈ D|P(x)
Module 05. Predicate Logic
CPSC 121 – Models of Computation 4 / 35
Reading Review
The Universal Quantifier: For All
∀
All human beings are mortal: ∀ human beings x, x is mortal.
If H is the set of all human beings: ∀x ∈ H, x is mortal.
The Existential Quantifier: Exists
∃
There is a student in CPSC 121: ∃ a person p, such that p is a student in CPSC 121.
If P is the set of all people: ∃p ∈ P, such that p is a student in CPSC 121.
Module 05. Predicate Logic
CPSC 121 – Models of Computation 5 / 35
Reading Review
∀x ∈ U if P(x) then Q(x)
It can always be rewritten in the form ∀x ∈ D,Q(x) by narrowing
U to be the domain D.
P(x) ⇒ Q(x)
Every element in the truth set of P(x) is in the truth set of Q(x),
or ∀x,P(x) → Q(x).
P(x) ⇔ Q(x)
P(x) and Q(x) have identical truth sets, or ∀x,P(x) ↔ Q(x).
Module 05. Predicate Logic
CPSC 121 – Models of Computation 6 / 35
Reading Review
∀x ∈ D,∃y ∈ E such that P(x,y)
Imagine that someone is allowed to choose any element (call it x) whatsoever from the set D. You have to find an element y in E so that for the person’s x and your y, P(x,y) is true.
∃x ∈ D,∀y ∈ E such that P(x,y)
You must find one element (call it x) in D. After you have found your x, someone else is allowed to choose any element from E and you should show that for your x and the person’s y, P(x,y) is true.
Module 05. Predicate Logic
CPSC 121 – Models of Computation 7 / 35
Quiz #05 Feedback
Yay! Very well done overall!!! \o/
Question 10: Let D be the domain of 8-bit signed binary numbers,
not mathematical integers. Is the following statement true? ∀x ∈ D , ∀y ∈ D , ((x > 0) ∧ (y > 0)) → (x + y ) > 0
Module 05. Predicate Logic
CPSC 121 – Models of Computation 8 / 35
Predicates vs Propositions
Is Propositional Logic a complete model? Can it be used to model every real-world situation? Which of the following can it model effectively?
a. Specializing abstract patterns to specific instances, like “Dogs have paws; therefore Pluto has paws”.
b. Generalizing from examples to abstract patterns like “Usain Bolt can’t run 100 m in under 9 seconds, so no human can”.
c. Defining what it means for a number to be prime.
d. It can model all of these effectively.
e. It can not model any of these effectively.
Module 05. Predicate Logic
CPSC 121 – Models of Computation 9 / 35
Predicates vs Propositions
Is Propositional Logic a complete model? Can it be used to model every real-world situation? Which of the following can it model effectively?
a. Specializing abstract patterns to specific instances, like “Dogs have paws; therefore Pluto has paws”.
b. Generalizing from examples to abstract patterns like “Usain Bolt can’t run 100 m in under 9 seconds, so no human can”.
c. Defining what it means for a number to be prime.
d. It can model all of these effectively.
e. It can not model any of these effectively.
Module 05. Predicate Logic
CPSC 121 – Models of Computation 9 / 35
Predicates vs Propositions
What is predicate logic good for modeling?
Relationships among real-world objects. Generalizations about patterns.
Infinite domains.
Generally, problems where the properties of the different concepts, or parts, depend on each other.
Module 05. Predicate Logic
CPSC 121 – Models of Computation 10 / 35
Predicates vs Propositions
Examples of predicate logic use:
Every key stored in the left subtree of a node N is smaller than the key stored at N (Data structures, CPSC 221).
No path via references exists from any variable in scope to any memory location available for garbage collection (Language definition, CPSC 311 or 312).
The relational model is based on predicate logic (Databases, CPSC 304).
In the worst case, every comparison sort requires at least cn log2 n comparisons to sort n values, for some constant c > 0 (Algorithms, CPSC 320).
Module 05. Predicate Logic
CPSC 121 – Models of Computation 11 / 35
Quantifiers Scope
A quantifier applies to everything to its right, up to the closing parenthesis of the () pair that contains it.
∀x ∈D,(∃y ∈D,Q(x,y)→∀z ∈F,R(y,z))∨P(x)
Module 05. Predicate Logic
CPSC 121 – Models of Computation 12 / 35
Quantifiers Scope
A quantifier applies to everything to its right, up to the closing parenthesis of the () pair that contains it.
∀x ∈D,(∃y ∈D,Q(x,y)→∀z ∈F,R(y,z))∨P(x)
Module 05. Predicate Logic
CPSC 121 – Models of Computation 12 / 35
Quantifiers Scope
A quantifier applies to everything to its right, up to the closing parenthesis of the () pair that contains it.
∀x ∈D,(∃y ∈D,Q(x,y)→∀z ∈F,R(y,z))∨P(x)
Module 05. Predicate Logic
CPSC 121 – Models of Computation 12 / 35
Quantifiers Scope
A quantifier applies to everything to its right, up to the closing parenthesis of the () pair that contains it.
∀x ∈D,(∃y ∈D,Q(x,y)→∀z ∈F,R(y,z))∨P(x)
Module 05. Predicate Logic
CPSC 121 – Models of Computation 12 / 35
Negation Scope
What is being negated in the following statement?
∼∃x ∈ Z+, ∀y ∈ Z+, x < y ∧ Even(y)
a. The quantifier ∃.
b. The quantified variable ∃x ∈ Z+. c. The expression up to x < y.
d. Everything to the right of the ∼. e. None of the above.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 13 / 35
Negation Scope
What is being negated in the following statement?
∼∃x ∈ Z+, ∀y ∈ Z+, x < y ∧ Even(y)
a. The quantifier ∃.
b. The quantified variable ∃x ∈ Z+. c. The expression up to x < y.
d. Everything to the right of the ∼. e. None of the above.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 13 / 35
Negation Scope
Original Statement: All CPSC instructors are nerds
Negation first version: Not all CPSC instructors are nerds Negation second version: There is some CPSC instructor who is not a nerd
The quantifier type changed from all to some and the property also changed from nerd to not a nerd.
CPSC 121 - Models of Computation
14 / 35
Module 05. Predicate Logic
Negation Scope
Original Statement: All CPSC instructors are nerds
Negation first version: Not all CPSC instructors are nerds Negation second version: There is some CPSC instructor who is not a nerd
The quantifier type changed from all to some and the property also changed from nerd to not a nerd.
C: all CPSC instructor
N(x): x is nerd.
Original Statement: ∀x ∈ C,N(x) Negation first version: ∼∀x ∈ C,N(x) Negation second version: ∃x ∈ C,∼N(x)
Module 05. Predicate Logic
CPSC 121 - Models of Computation 14 / 35
Predicates vs Propositions
What is the truth value of the statement:
∃x ∈ Z, x ∗ x = y
a. True because (for example) 5 · 5 = 25.
b. True because for every y, we know that y = √y · √y.
c. False, because of counterexamples like no integer multiplied by itself equals 3.
d. It depends on y, but given a value for y, we could calculate a truth value.
e. None of the above.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 15 / 35
Predicates vs Propositions
What is the truth value of the statement:
∃x ∈ Z, x ∗ x = y
a. True because (for example) 5 · 5 = 25.
b. True because for every y, we know that y = √y · √y.
c. False, because of counterexamples like no integer multiplied by itself equals 3.
d. It depends on y, but given a value for y, we could calculate a truth value.
e. None of the above.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 15 / 35
Predicates vs Propositions
What is the difference between a proposition and a predicate?
a. A predicate may contain unbound variables, but a proposition never does.
b. A predicate may contain one or more quantifiers, but a proposition never does.
c. A proposition’s name is a lowercase letter, whereas a predicate’s name is an uppercase letter.
d. They are the same thing, using different names.
e. None of the above.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 16 / 35
Predicates vs Propositions
What is the difference between a proposition and a predicate?
a. A predicate may contain unbound variables, but a proposition never does.
b. A predicate may contain one or more quantifiers, but a proposition never does.
c. A proposition’s name is a lowercase letter, whereas a predicate’s name is an uppercase letter.
d. They are the same thing, using different names.
e. None of the above.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 16 / 35
Predicates vs Propositions
A predicate is a logic formula with unbound variables, such as
PerfectSquare (y ) : ∃x ∈ Z, x · x = y
Then
PerfectSquare(25) is PerfectSquare(27) is
∃y ∈ Z,PerfectSquare(y) is ∀y ∈ Z,PerfectSquare(y) is
Module 05. Predicate Logic
CPSC 121 - Models of Computation 17 / 35
Predicates vs Propositions
Which variables do we need values for in order to determine this formula’s truth value?
∀i ∈ Z+,(i ≥ n) ↔ ∼∃v ∈ Z+,HasValue(l,i,v)
a. i and v.
b. l and n.
c. n and v.
d. i and n.
e. None of these are correct.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 18 / 35
Predicates vs Propositions
Which variables do we need values for in order to determine this formula’s truth value?
∀i ∈ Z+,(i ≥ n) ↔ ∼∃v ∈ Z+,HasValue(l,i,v)
a. i and v.
b. l and n.
c. n and v.
d. i and n.
e. None of these are correct.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 18 / 35
Questions?
Ask CPSC 121
http://www.cs.ubc.ca/~mochetti/askCPSC121.html
Module 05. Predicate Logic
CPSC 121 - Models of Computation 19 / 35
Translations
F: the set of foods. E(x): Alice eats food x. g: Alice grows.
s: Alice shrinks.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 20 / 35
Worksheet
Questions 1 - 2
Module 05. Predicate Logic
CPSC 121 - Models of Computation 21 / 35
Translations
D: the set of all creatures. F(x): x is a fierce creature. L(x): x is a lion.
C(x): x drinks coffee. T(x,y): x has bitten y.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 22 / 35
Worksheet
Questions 3 - 11
Module 05. Predicate Logic
CPSC 121 - Models of Computation 23 / 35
There are exactly k such that ...
There is at least one element with property P:
∃x ∈ D,P(x)
There are at least two elements with property P:
∃x ∈ D,∃y ∈ D, ...... There are at least three elements with property P:
∃x∈D,∃y∈D,∃z∈D, ......
Module 05. Predicate Logic
CPSC 121 - Models of Computation 24 / 35
There are exactly k such that ...
There is at least one element with property P:
∃x ∈ D,P(x)
There are at least two elements with property P:
∃x ∈D,∃y ∈D,P(x)∧P(y)∧x ̸=y There are at least three elements with property P:
∃x∈D,∃y∈D,∃z∈D, ......
Module 05. Predicate Logic
CPSC 121 - Models of Computation 24 / 35
There are exactly k such that ...
There is at least one element with property P:
∃x ∈ D,P(x)
There are at least two elements with property P:
∃x ∈D,∃y ∈D,P(x)∧P(y)∧x ̸=y There are at least three elements with property P:
∃x ∈ D,∃y ∈ D,∃z ∈ D,P(x)∧P(y)∧P(z)∧x ̸= y∧y ̸= z∧x ̸= z
Module 05. Predicate Logic
CPSC 121 - Models of Computation 24 / 35
There are exactly k such that ...
There is at least one element with property P:
∃x ∈ D,P(x)
There are at least two elements with property P:
∃x ∈D,∃y ∈D,P(x)∧P(y)∧x ̸=y There are at least three elements with property P:
∃x ∈ D,∃y ∈ D,∃z ∈ D,P(x)∧P(y)∧P(z)∧x ̸= y∧y ̸= z∧x ̸= z
We can extend this to n elements, however the number of terms is (n + n2)/2.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 24 / 35
There are exactly k such that ...
Suppose I have a large urn with many tennis balls; at most one ball is colored blue (the others are red).
I pick one ball B1 from the urn, it’s blue.
I put B1 back in the urn, stir, and pick another ball B2. It’s
also blue.
What can we say about B1 and B2?
Module 05. Predicate Logic
CPSC 121 - Models of Computation 25 / 35
There are exactly k such that ...
Suppose I have a large urn with many tennis balls; at most one ball is colored blue (the others are red).
I pick one ball B1 from the urn, it’s blue.
I put B1 back in the urn, stir, and pick another ball B2. It’s
also blue.
What can we say about B1 and B2? They are the same ball.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 25 / 35
There are exactly k such that ...
There is at most one element with property P: ∀x ∈ D,∀y ∈ D, ......
There is at most two elements with property P: ∀x∈D,∀y∈D,∀z∈D, ......
Module 05. Predicate Logic
CPSC 121 - Models of Computation 26 / 35
There are exactly k such that ...
There is at most one element with property P:
∀x ∈D,∀y ∈D,(P(x)∧P(y))→(x =y) There is at most two elements with property P:
∀x∈D,∀y∈D,∀z∈D, ......
Module 05. Predicate Logic
CPSC 121 - Models of Computation 26 / 35
There are exactly k such that ...
There is at most one element with property P:
∀x ∈D,∀y ∈D,(P(x)∧P(y))→(x =y) There is at most two elements with property P:
∀x ∈ D,∀y ∈ D,∀z ∈ D,
(P(x) ∧ P(y) ∧ P(z)) → (x = y ∨ y = z ∨ x = z)
Module 05. Predicate Logic
CPSC 121 - Models of Computation 26 / 35
There are exactly k such that ...
There is at most one element with property P:
∀x ∈D,∀y ∈D,(P(x)∧P(y))→(x =y) There is at most two elements with property P:
∀x ∈ D,∀y ∈ D,∀z ∈ D,
(P(x) ∧ P(y) ∧ P(z)) → (x = y ∨ y = z ∨ x = z)
There are exactly k objects with property P if there are at least k objects with property P and at most k objects with property P.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 26 / 35
For All and Exists together
Consider the following two statements:
A rich person gave $10,000 to every CPSC 121 student. Every CPSC 121 student received $10,000 from a rich person.
Do they mean the same thing?
a. Yes.
b. No.
c. Its impossible to tell
Module 05. Predicate Logic
CPSC 121 - Models of Computation 27 / 35
For All and Exists together
Consider the following two statements:
A rich person gave $10,000 to every CPSC 121 student. Every CPSC 121 student received $10,000 from a rich person.
Do they mean the same thing?
a. Yes.
b. No.
c. Its impossible to tell
Module 05. Predicate Logic
CPSC 121 - Models of Computation 27 / 35
For All and Exists together
R: the set of rich people
S: the set of students
E1: A rich person gave $10,000 to every student.
E2: Every rich person gave $10,000 to a student.
E3: A student received $10,000 from every rich person. E4: Every student received $10,000 from a rich person. P1: ∀r ∈ R,∃s ∈ S,Gave(r,s)
P2: ∀s ∈ S,∃r ∈ R,Gave(r,s)
P3: ∃s ∈ S,∀r ∈ R,Gave(r,s)
P4: ∃r ∈ R,∀s ∈ S,Gave(r,s)
Which of the following lists of equivalences is correct? a. E1≡P4,E2≡P1,E3≡P3,E4≡P2.
b. E1≡P2,E2≡P3,E3≡P1,E4≡P4.
c. E1≡P4,E2≡P3,E3≡P1,E4≡P2.
d. E1≡P2,E2≡P1,E3≡P3,E4≡P4. e. None of the above.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 28 / 35
Questions?
Ask CPSC 121
http://www.cs.ubc.ca/~mochetti/askCPSC121.html
Module 05. Predicate Logic
CPSC 121 - Models of Computation 29 / 35
Exercise
Given the definitions:
D: the set of all creatures. F(x): x is a fierce creature. L(x): x is a lion.
Describe the differences between each statement:
∀x ∈D,F(x)∧L(x) ∀x ∈D,F(x)∨L(x) ∀x ∈ D,F(x) → L(x) ∀x ∈ D,F(x) ↔ L(x)
Module 05. Predicate Logic
CPSC 121 - Models of Computation 30 / 35
Exercise: Solution
∀x ∈D,F(x)∧L(x)
All creatures are fierce and are lions. There are no creatures that are not lions. There are no creatures that are not fierce.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 31 / 35
Exercise: Solution
∀x ∈D,F(x)∨L(x)
All creatures are either fierce or lions or both. There are no creatures that are not a lion and are not fierce at the same time.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 32 / 35
Exercise: Solution
∀x ∈ D,F(x) → L(x)
All creatures that are fierce, are lions, but there are lions that are not fierce.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 33 / 35
Exercise: Solution
∀x ∈ D,F(x) ↔ L(x)
Either all creature are lions and fierce or they are not lions nor fierce. There are no lions that are not fierce. There are no fierce creature that are not lions. There are creatures that are not lions are not fierce.
Module 05. Predicate Logic
CPSC 121 - Models of Computation 34 / 35
Meme
Module 05. Predicate Logic
CPSC 121 - Models of Computation 35 / 35