ECM 1415 Predicate Logic & Rules of Inference

Question 1

What is predicate logic?

Answer 1

a generalization of propositional logic

Question 2

What is a predicate?

Answer 2

a proposition that can store variables in a scope

Question 3

What 3 features does predicate logic include?

Answer 3

Predicates
Quantifiers
Variables

Question 4

What does the Universal Quantifier, ∀x, do?

Answer 4

asserts P(x) is true for every x in the domain

Question 5

What does the Existential Quantifier, ∃x, do?

Answer 5

asserts P(x) is true for some x in the domain

Question 6

The domain is often denoted by U for universe of discourse
Example (Quantifier)
If P(x) denotes “x is even” and the U the integers, then…

Answer 6

• ∀x. P(x) is false
• ∃x. P(x) is true

Question 7

Nested Quantifier example
“Every real number has an inverse” is

Answer 7

∀x ∃y. (x + y = 0)

Question 8

Laws for Quantifiers:

Answer 8

¬(∀x. P(x)) _= ∃x. ¬P(x)
¬(∃x. P(x)) _= ∀x. ¬P(x)
Example
Not “There is a student in your class who has taken a course in Java” means “Every student in your class has not taken Java”

Question 9

Modus Ponens

Answer 9

P -> q
p
———
Therefore q

Corresponding tautology
(p /\ (p -> q)) -> q

Question 10

Modus Tollens

Answer 10

P -> q
¬q
———
Therefore ¬p

Corresponding tautology
(¬q /\ (p -> q)) -> ¬p

Question 11

Hypothetical Syllogism

Answer 11

P -> q
q -> r
———
Therefore p -> r

Question 12

Disjunctive Syllogism

Answer 12

P \/ q
¬p
———
therefore q

Question 13

Addition

Answer 13

p
Therefore p \/ q

Question 14

Simplification

Answer 14

p /\ q
Therefore p

Question 15

Resolution

Answer 15

¬p \/ r
p \/ q
———
Therefore q \/ r

Question 16

Conjunction

Answer 16

P
q
———
Therefore p /\ q