Rules of Inference

Inference

• When looking at proving equivalences, we were showing that expressions in the form p↔q were tautologies and writing p≡q.
  • But we don't always want to prove ↔. Often we only need one direction.
  • In general, mathematical proofs are “show that p is true” and can use anything we know is true to do it.
  • Basically, we want to know that [everything we know is true]→p is a tautology.
  • … then we know p is true.
• We can use the equivalences we have for this.
  • Since they are tautologies p↔q, we know that p→q.
  • But we can also look for tautologies of the form p→q.
• Here's a tautology that would be very useful for proving things:
  ((p→q)∧p)→q.
• For example, if we know that “if you are in this course, then you are a DDP student” and “you are in this course”, then we can conclude “You are a DDP student.

Rules of Inference

• If we have an implication tautology that we'd like to use to prove a conclusion, we can write the rule like this:

  	p→q
  	p
  ∴	q

  • This corresponds to the tautology ((p→q)∧p)→q.
  • The ∴ symbol is therefore.
  • The first two lines are premises.
  • The last is the conclusion.
  • This inference rule is called modus ponens (or the law of detachment).
• Here are the rules of inference that we can use to build arguments:

  Name	Rule
  Modus ponens	p p→q ∴ q
  Modus tollens	¬q p→q ∴ ¬p
  Hypothetical syllogism	p→q q→r ∴ p→r
  Disjunctive syllogism	p∨q ¬p ∴ q
  Addition	p ∴ p∨q
  Simplification	p∧q ∴ p
  Conjunction	p q ∴ p∧q
  Resolution	p∨q ¬p∨r ∴ q∨r

• Using these rules by themselves, we can do some very boring (but correct) proofs.
• e.g. “If I am sick, there will be no lecture today;” “either there will be a lecture today, or all the students will be happy;” “the students are not happy.”
  • Translate into logic as: s→¬l, l∨h, ¬h.
  • Then we can reach a conclusion as follows:
    1. l∨h [hypothesis]
    2. ¬h [hypothesis]
    3. l [disjunctive syllogism using (1) and (2)]
    4. s→¬l [hypothesis]
    5. ¬s [modus tollens using (3) and (4)]
  • So, I am not sick.
  • Notice a similar proof style to equivalences: one piece of logic per line, with the reason stated clearly.

Inference and Quantified Statements

• Rules of inference start to be more useful when applied to quantified statements.
• Rules for quantified statements:

  Name	Rule
  Universal instantiation	∀xP(x) ∴ P(c)
  Universal generalization	P(c) [for an arbitrary c] ∴ ∀xP(x)
  Existential instantiation	∃xP(x) ∴ P(c) [for some particular c]
  Existential generalization	P(c) [for some particular c] ∴ ∃xP(x)

• Now we can prove things that are maybe less obvious.
• e.g. “Students who pass the course either do the homework or attend lecture;” “Bob did not attend every lecture;” “Bob passed the course.”
  • Translate into logic as (with domain being students in the course): ∀x(P(x)→H(x)∨L(x)), ¬L(b), P(b).
  • Then we can conclude:
    1. ∀x(P(x)→H(x)∨L(x)) [hypothesis]
    2. P(b)→H(b)∨L(b) [Universal instantiation]
    3. P(b) [hypothesis]
    4. H(b)∨L(b) [modus ponens using (2) and (3)]
    5. ¬L(b) [hypothesis]
    6. H(b) [Disjunctive syllogism using (4) and (5)]
  • So, Bob must have done the homework.
• e.g. “Bob failed the course, but attended every lecture;” “everyone who did the homework every week passed the course;” “if a student passed the course, then they did some of the homework.” We want to conclude that not every student submitted every homework assignment.
  • Translate into logic as (domain for s being students in the course and w being weeks of the semester):
    ¬P(b)∧∀w(L(b,w)),∀s[(∀wH(s,w))→P(s)],∀s[P(s)→∃wH(s,w)].
  • Then we can conclude:
    1. ¬P(b)∧∀w(L(b,w)) [hypothesis]
    2. ¬P(b) [simplification using (1)]
    3. ∀s[(∀wH(s,w))→P(s)] [hypothesis]
    4. (∀wH(b,w))→P(b) [universal instantiation using (3)]
    5. ¬∀wH(b,w) [modus tollens using (4) and (2)]
    6. ∃w¬H(b,w) [quantifier negation using (5)]
    7. ∃s∃w¬H(s,w) [existential generalization using (6)]
  • So, somebody didn't hand in one of the home works.
  • We didn't use one of the hypotheses. That's okay.
• In the last line, could we have concluded that ∀s∃w¬H(s,w) using universal generalization?
  • i.e. every student missed at least one homework.
  • Hopefully not: there's no evidence in the hypotheses of it (intuitively).
  • The problem is that b isn't just anybody in line 1 (or therefore 2, 5, 6, or 7). It's Bob.
  • It's not an “arbitrary” value, so we can't apply universal generalization.