Methods of Proof II

Key Topics

* Valid Inference Steps in Informal Proofs

* Proof by Cases

* Proof by Contradiction

* Formal Proof Illustrations

* Subproofs

Remember: All proofs must be rigorous, i.e., each step in a proof must provide definitive evidence that the intermediate conclusion follows from things already established.

Formal Proof: Every step in the proof is provided (i.e., no steps are left out), a fixed set of rules are used as explanations of intermediate conclusions; usually presented in a highly stylized, formal way.

Informal Proof: Usually stated in English, in paragraph form; less formal and the more obvious steps are left out.

Valid Inference Steps in Informal Proofs

Every step in an informal proof should be significant and easily understood (and correct!).

The following generally go unmentioned in informal proofs:

Conjunction Elimination: From P^Q infer P .

Conjunction Introduction: From P and Q, infer P ^ Q

Disjunction Introduction: Form P, infer P v Q

Proof by Cases

To prove S from P1 v … v Pn, prove S from each of P1, …, Pn.

1) Given: (boy(Elliot) ^ girl(Caroline)) v ((boy(Brian) ^ girl(Caroline))

Prove: girl(Caroline)

2) Given: (boy(Elliot) ^ girl(Caroline)) v ((boy(Brian) ^ girl(Emily))

Prove: boy(Elliot) v boy(Brian)

3) Given: All integers n not divisible by 5

Prove: n²/5 leaves a remainder of 1 or 4.

Proof by Contradiction

Contradiction: any claim that cannot be true, or any set of claims that cannot all be true in any single situation.

To prove ~S, assume S and prove a contradiction ^.

1) Given: red(a) v green(a)

teal(b)

Prove: ~(a = b)

2) Given: 3n+2 is odd

Prove: n is odd

3) Prove: There is no largest integer.

Formal Proof Illustrations

Conjunction Elimination: allows us to assert Pi of a conjunctive sentence P1^…^Pi^…^Pn which we have already derived in our proof.

Conjunction Introduction: allows us to assert P1^…^Pn provided we have already established each of the conjuncts P1 through Pn.

Disjunction Introduction: allows us to go from a sentence Pi to any disjunction where Pi is among the disjuncts, say P1 v…v Pi v … v Pn.

Disjunction Elimination: This is the formal counterpart of “proof by cases”: If we have established a disjunction P1 v … v Pn and we also know that S follows from each of the disjuncts P1 through Pn, then we can conclude S.

Negation Introduction: This is the formal counterpart of “proof by contradiction”: If you can prove a contradiction ^ on the basis of an additional assumption P, then you can infer ~P from the original premises.

^ Introduction: This rule allows us to obtain a contradiction symbol if have established an explicit contradiction in the form of P and its negation ~P.

^ Elimination: This rule allows us to assert P, once we have established the contradiction ~P. (Actually it allows us to assert any sentence at all, once we have established a contradiction!)

Subproofs

Given: (boy(e) ^ girl(d)) v (girl(d) ^ boy(b))

Prove: girl(d) ^ boy(e)