Things you should do…

Predicate Logic & Quantification

• Homework 1 due today at 3pm

– Via gradescope. Directions posted on the website.

• Group homework 1 posted, due Tuesday.

– Groups of 1-3. We suggest 3.
– In LaTeX
EECS 203: Discrete Mathematics
Lecture 3 Spring 2016
(Sections 1.4 and start on 1.5)

Warmup Question Warmup Question

• “Neither the fox nor the lynx can catch the hare if • The expression (p → q) → (¬ q → p)
the hare is alert and quick.” can only be satisfied by the truth assignment
• F: the fox can catch the hare a. p= T, q = F
• L: the lynx can catch the hare
• A: the hare is alert
b. p= F, q = T
• Q: the hare is quick c. This is not satisfiable
d. None of the above
– (A) ¬(F ∨ L) → (A ∧ Q)
– (B) (A ∧ Q) → ¬F ∧ ¬L
– (C) ¬F ∧ ¬L ∧ A ∧ Q
– (D) (¬A ∨ ¬Q) → (F ∨ L)
 Relational (First-Order) Logic Propositions & Predicates
• In propositional logic, • Proposition:
– All we have are propositions and connectives, – A declarative statement that is either true or false.
making compound propositions.
– E.g. “A nickel is worth 5 cents.”
– We learn about deductions and proofs based
– “Water freezes at 0 degrees Celsius at sea level.”
on the structure of the propositions.

• In first-order logic, • Predicate:

– We will add objects, properties, and relations. – A declarative statement with some terms unspecified.
– We will be able to make statements about – It becomes a proposition when terms are specified.
what is true for some, all, or no objects. – These terms refer to objects.
• And that comes now.

A “truth table” for quantifiers Examples: English Quantifications

“Everyone will buy an umbrella or a raincoat”
∀x P(x) ∃x P(x)
∀x (B(x,umbrella) ∨ B(x,raincoat))
True
P(x) true for at least one x
when P(x) true for every x
in the domain of discourse in the domain of discourse “Everyone will buy an umbrella or everyone will
: buy a raincoat”
False
when P(x) false for at least one x P(x) false for every x
in the domain of discourse in the domain of discourse
: “No one will buy both a raincoat and umbrella”
 Examples: English Quantifications Examples: English Quantifications
“Everyone will buy an umbrella or a raincoat” “Everyone will buy an umbrella or a raincoat”
∀x (B(x,umbrella) ∨ B(x,raincoat)) ∀x (B(x,umbrella) ∨ B(x,raincoat))

“Everyone will buy an umbrella or everyone will “Everyone will buy an umbrella or everyone will
buy a raincoat” buy a raincoat”
∀x B(x,umbrella) ∨ ∀x B(x,raincoat) ∀x B(x,umbrella) ∨ ∀x B(x,raincoat)

“No one will buy both a raincoat and umbrella” “No one will buy both a raincoat and umbrella”
¬∃x(B(x,umbrella) ∧ B(x,raincoat)) ¬∃x(B(x,umbrella) ∧ B(x,raincoat))
This has the potential
quantified variable the scope of the variable variable scope variable scope to cause confusion so
we’ll try to avoid it!

Examples: English Quantifications Nested Quantifiers

P(x,y) : “person x loves person y”
• “Everyone has a car or knows someone with a car.”
– Let C(x) be “x has a car”
∀x∃y P(x,y) means:
– Let K(x,y) be “x knows y”
“For every x (in the domain) there is at least one y (in the domain), that
can depend on x and may be equal to x, such that
(A) ∃x∃y [C(x) ∨ (K(x,y) ∧ C(y))] P(x,y) is true.”
(B) ∃y∀x [C(x) ∨ (K(x,y) ∧ C(y))] “Everyone loves someone (e.g. his/her mother)”
(C) ∀x∃y [C(x) ∨ (K(x,y) ∧ C(y))]
(D) ∀x∀y [C(x) ∨ (K(x,y) ∧ C(y))] ∃y∀x P(x,y) means:
“There is at least one y such that for every x (including
the case y=x), P(x,y) is true.”
“There’s one guy/gal that everyone loves (e.g. Santa)”
 Defining Limits
• In calculus, the limit • Two statements involving quantifiers and
– Is defined to mean: predicates are logically equivalent if they have
the same truth value, regardless of the domain
of discourse or the meaning of the predicates.
– As close as you want f(x) to be to L (∀ε > 0), ≡ denotes logical equivalence.
– there is a margin for x around a (∃δ > 0),
– so that for any x within that margin around a, • Need new equivalences involving quantifiers.
– f(x) will be as close as you wanted to L.

• The limit is an essential concept for calculus.

Negating Quantifiers Be Careful with Equivalences

• ¬∀x P(x) ≡ ∃x ¬P(x) • It’s true that:
– There is an x for which P(x) is false.
– ∀x [P(x) ∧ Q(x)] ≡ [∀x P(x)] ∧ [∀x Q(x)]
– If P(x) is true for every x then ∃x ¬P(x) is false.
• But it’s not true that:
• ¬∃x P(x) ≡ ∀x ¬P(x) – ∀x [P(x) ∨ Q(x)] ≡ [∀x P(x)] ∨ [∀x Q(x)]
– For every x, P(x) is false. • Why not?
– If there is an x for which P(x) is true then ∀x ¬P(x) is
false
• Likewise, it’s true that:
• This is really just DeMorgan’s Laws, extended. – ∃x [P(x) ∨ Q(x)] ≡ [∃x P(x)] ∨ [∃x Q(x)]
• ¬(p ∧ q) ≡ ¬p ∨ ¬q • But it’s not true that:
• ¬(p ∨ q) ≡ ¬p ∧ ¬q – ∃x [P(x) ∧ Q(x)] ≡ [∃x P(x)] ∧ [∃x Q(x)]
 Be Careful With Translation to Logic Be Careful With Translation to Logic
• “Every student in this class has studied calculus.” • “Some student in this class is a math genius.”
– S(x) means “x is a student in this class”. – S(x) means “x is a student in this class”.
– C(x) means “x has studied calculus”. – G(x) means “x is a math genius”.
• Is this correct? ∀x [ S(x) ∧ C(x) ] • Is this correct? ∃x [ S(x) → G(x) ]
– (A) Yes – (A) Yes
– (B) No – (B) No

• How about this? ∀x [ S(x) → C(x) ] • How about this? ∃x [ S(x) ∧ G(x) ]
– (A) Yes – (A) Yes
– (B) No – (B) No

Hard Problem Prove the A → B Direction

• Prove: ∀x P(x) ∨ ∀x Q(x) ≡ ∀x∀y [P(x) ∨ Q(y)] • Assume that ∀x P(x) ∨ ∀x Q(x) is true.
• We can rename a bound variable: ∀x Q(x) ≡ ∀y Q(y) – Consider the case where the disjunct ∀x P(x) is true.
• The other case, ∀x Q(x), is the same.

– Method: to prove A ≡ B
– Then for any value of y, ∀x (P(x) ∨ Q(y)) is true.
• We might prove A → B and B → A.
• by the Identity Law, since P(x) is true.
– But that will turn out to be too hard.
– This is the definition of ∀y ∀x (P(x) ∨ Q(y)).
• by definition of the universal quantifier.
• Instead we will prove A → B and ¬A → ¬B.
– That will do the trick just as well.
– And this is equivalent to ∀x ∀y (P(x) ∨ Q(y)).
• section 1.5, example 3 (pp.58-59).
– Thus: ∀x P(x) ∨ ∀x Q(x) → ∀x ∀y (P(x) ∨ Q(y))
∀x P(x) ∨ ∀x Q(x) ≡ ∀x∀y [P(x) ∨ Q(y)]
 Exercises.
Prove the ¬A → ¬B Direction
Start by defining your predicates!
• Assume that ∀x P(x) ∨ ∀x Q(x) is false.
– Then: ¬[ ∀x P(x) ∨ ∀x Q(x) ] • Every two people have a friend in common.
(Life isn’t facebook! If A is a friend of B, B is not necessarily a friend of A.)
≡ ¬∀x P(x) ∧ ¬∀x Q(x)
≡ ∃x ¬P(x) ∧ ∃x ¬Q(x)
• All my friends think I’m their friend too.
– Then let (a,b) be such that ¬P(a) and ¬Q(b).
– Therefore: ¬P(a) ∧ ¬Q(b)
• There are two people who have the exact same group of
≡ ∃x ∃y [ ¬P(x) ∧ ¬Q(y) ]
friends.
≡ ∃x ∃y ¬[P(x) ∨ Q(y)]
≡ ¬∀x ∀y [P(x) ∨ Q(y)]
• Everyone has two friends, neither of whom are friends
– Which is ¬B ∀x P(x) ∨ ∀x Q(x) ≡ ∀x∀y [P(x) ∨ Q(y)] with each other.
• QED. The whole statement is proved.

Additional Exercises Additional Exercises

• M(x) : “x is male” • M(x) : “x is male”
• F(x) : “x is female” • F(x) : “x is female”
• P(x,y) : “x is the parent of y” • P(x,y) : “x is the parent of y”
– “Everyone has at least one parent” – “Someone is an only child”
 Additional Exercises Additional Exercises
• M(x) : “x is male” • M(x) : “x is male”
• F(x) : “x is female” • F(x) : “x is female”
• P(x,y) : “x is the parent of y” • P(x,y) : “x is the parent of y”
– “Bob has a niece” – “I do not have any uncles” (rephrased: “any sibling of my parent is female”)

Additional Exercises So far…

• M(x) : “x is male” • You can
• F(x) : “x is female” – Express statements as compound propositions
• P(x,y) : “x is the parent of y” – Prove that two compound propositions are equivalent
– “Bob has a niece” – Express statements as quantified formulae (with
– “Not everyone has two parents of opposite sexes” predicates and universal & existential quantifiers)
– “I have a half-brother” (rephrased: “I and my half-brother share one but not two parents”)
– “I do not have any uncles” (rephrased: “any sibling of my parent is female”) • Next:
– “No one’s parents are cousins” (this is one is rather long...) – Formal proofs, rules of inference
– Proof methods
– Strategies for designing proofs
 Definition
• An argument for a statement S is a sequence of
statements ending with S.
Start on
• We call S the conclusion and all the other
Inference and Proofs statements the premises.
• The argument is valid if, whenever all the
premises are true, the conclusion is also true.
Section 1.5
– Note: A valid argument with false premises could lead
to a false conclusion.
• Proofs are valid arguments that establish the truth
of mathematical statements.

Simple Example Inferences

• Premises: • Basic building block of logical proofs is an inference
– “If you’re a CS major then you must take EECS 203 – Combine two (or one or more) known facts to yield another
before graduating.”
p→q premises Based on the tautology:
– “You’re a CS major.” p ((p → q) ∧ p) → q
• Conclusion: ∴q conclusion
– (Therefore,) “You must take EECS 203 before p∨q premises Based on the tautology:
graduating.” ¬p∨r ((p∨q) ∧ (¬p∨r)) → (q∨r)
∴ q∨r conclusion

• This is a valid argument (why?). Note: p→q This is not a valid inference because
q ((p→q) ∧ q) → p
∴p is not a tautology!
 The Basic Rules of Inference The Basic Rules of Inference
p→q Based on the tautology: “modus ponens” p Based on the tautology: “Addition”
p ((p→q) ∧ p) → q lit.: mode that affirms ∴p∨q
p→p∨ q
∴q

p→q Based on the tautology: “modus tollens” p∧q Based on the tautology: “Simplification”
¬q ((p→q) ∧ ¬q) → ¬p lit.: mode that denies ∴p ( p ∧ q) → p
∴ ¬p

p→q Based on the tautology: “hypothetical p Based on the tautology: “Conjunction”

q→r ((p→q) ∧ (q→r)) → syllogism” q ( (p) ∧ (q) ) → (p ∧ q)
∴ p→r (p→r) ∴p∧q

p∨q Based on the tautology: “disjunctive syllogism” p∨q Based on the tautology: “Resolution”
¬p ((p ∨ q) ∧ ¬p) → q ¬p∨r ((p∨q) ∧ (¬p∨r)) → (q∨r)
∴q ∴ q∨r

• Modus ponens
– “If you have access to ctools, you can download the homework.”
Common fallacies
– “You have access to ctools.”
p→q Not a tautology: “Fallacy of affirming
– (Therefore,) “you can download the homework.”
q ((p→q) ∧ q) → p the conclusion”
• Modus tollens When = , = :
∴p
– “If you have access to ctools, you can download the homework.” LHS: ( → )∧ ≡
RHS: =
– “You cannot download the homework.” Together: → ≡
– (Therefore,) “you do not have access to ctools.”
• Hypothetical syllogism
– “If you are registered for this course, you have access to ctools.”
– “If you have access to ctools, you can download the homework.” p→q Not a tautology: “Fallacy of denying
– (Therefore,) “if you are registered for this course, you can download the HW.” ¬p ((p→q) ∧ ¬p) → ¬q the hypothesis”
When = , = :
• Resolution ∴¬q
LHS: ( → )∧ ≡
– “If it does not rain today, we will have a picnic.” RHS: ¬ =
Together: → ≡
– “If it does rain today, we will go to the movies.”
– (Therefore,) “today, we will have a picnic or go to the movies.”
 Showing that an argument is valid Step 1: Convert to propositions
• Premises :
• Is this argument valid? How would we show its validity?
i. “If Jo has a bacterial infection, she will take i. B → A
antibiotics.”
• Premises : ii. “Jo gets a stomach ache when and only when ii. S ↔ (A ∧ ¬Y)
i. “If Jo has a bacterial infection, she will take antibiotics.” she takes antibiotics and doesn’t eat yogurt.”
iii. “Jo has a bacterial infection.” iii. B
ii. “Jo gets a stomach ache when and only when she takes antibiotics
and doesn’t eat yogurt.” iv. “Jo doesn’t eat yogurt.”
iv. ¬Y
iii. “Jo has a bacterial infection.” • Conclusion:
iv. “Jo doesn’t eat yogurt.” – “Jo gets a stomach ache.” S
• Conclusion:
– “Jo gets a stomach ache.” B: “Jo has a bacterial infection.”
A: “Jo takes antibiotics.”
S: “Jo gets a stomach ache.”
Y: “Jo eats yogurt.”

Step 2: Start with premises Step 3: Use inferences to make conclusion

i. B→A premise i. B→A premise
ii. S ↔ (A ∧ ¬Y) premise ii. S ↔ (A ∧ ¬Y) premise
iii. B premise iii. B premise
iv. ¬Y premise iv. ¬Y premise

1. A modus ponens, i, iii

2. (A ∧ ¬Y) conjunction, iv, 1
3. ((A ∧ ¬Y) → S) ∧ (S → (A ∧ ¬Y)) definition of ↔, ii
4. (A ∧ ¬Y) → S simplification, 3
5. S modus ponens, 2,4

B: “Jo has a bacterial infection.” B: “Jo has a bacterial infection.”

A: “Jo takes antibiotics.” A: “Jo takes antibiotics.” The desired
S: “Jo gets a stomach ache.” S: “Jo gets a stomach ache.” conclusion!
Y: “Jo eats yogurt.” Y: “Jo eats yogurt.”