Please enable JavaScript.
Coggle requires JavaScript to display documents.
Week 3 - Coggle Diagram
Week 3
About
Predicate Logic
Predicates: P(X),M(X)
Quantifiers
Variables : X,Y, Z
etc
R(2,-1,5)
R(3,4,7)
R(X,3,Z)
Not a Proposition
Quantifiers
etc: Some cats do not have fur
All men are mortals
Need to be express the meaning of English words
Two important
quantifiers
Universal Quantifier, “For all,” symbol: ∀
Existential Quantifier, “There exists,” symbol: ∃
Are said to bind the variable x in these expressions
∃x P(x)
“For some x, P(x)”
“There
is an x such that P(x),”
“For at least one x, P(x).”
∀x P(x)
“For all x, P(x)”
“For every x, P(x)”
De Morgan’s Laws for Quantifiers
Equivalent Statement
∀ ¬x P(x)
∃ ¬x P(x)
When Is
Negation True?
For every x, P(x) is false.
There is an x for which P
(x) is false.
Negation
¬∃xP (x)
¬∀xP (x)
When
False?
There is x for
which P(x) is true.
P(x) is true for
every x.
Questions on Translation from English
“Everybody loves somebody.”
Solution
: ∀x ∃y L(x,y)
“There is someone who is loved by everyone.”
Solution
: ∃y ∀x L(x,y)
“Siblinghood is symmetric.”
Solution:
∀x ∀y (S(x,y) → S(y,x))
“There is someone who loves someone.”
Solution
: ∃x ∃y L(x,y)
“Brothers are siblings.”
Solution
: ∀x ∀y (B(x,y) → S(x,y))
“Everyone loves himself”
Solution
: ∀x L(x,x)
Negating Nested Quantifiers
Part 1:
Use quantifiers to express the statement that “There does not exist a woman who has taken a flight on every airline in the world.”
Solution:
¬∃w∀a∃f (P(w,f )∧Q(f,a))
Solution:a
∀w∃a¬∃f (P(w,f)∧Q(f,a)) by De Morgan’s for ∀
∀w∃a∀f¬ (P(w,f)∧Q(f,a)) by De Morgan’s for ∃
∀w¬∀a∃f (P(w,f)∧Q(f,a)) by De Morgan’s for ∃
∀w∃a∀f (¬P(w,f) ¬Q(f,a)) by De Morgan’s for ∧.
¬∃w∀a∃f(P(w,f)∧Q(f,a))
Example 1
: Recall the logical expression developed three slides back:
∃w∀a∃f (P(w,f )∧Q(f,a))
Part 3:
Can you translate the result back into English?
Solution: “For every woman there is an airline such that for all flights, this woman has not taken that flight or that flight is not on this airline”