PROPOSITIONAL CALCULUS

EIGHT BASIC RULES OF INFERENCE (NON-HYPOTHETICAL)

Negation Elimination (~E – version of double negation DN)

~~pp

Example:

If it is not the case that Bob is not here, then Bob is here

Conditional Elimination (→E – modus ponens MP)

pq

p

˫ q

Example:

If Bob is here, then we are in big trouble

Bob is here

Therefore we are in big trouble

Conjunction Introduction (&I – conjunction CONJ)

p

q

˫ p & q

Example:

Bob is here

Joe is here

Therefore, Bob is here and Joe is here

Conjunction Elimination (&E – simplification SIMP)

p & q

˫ p

Example:

Bob is here and Joe is here

Therefore, Bob is here

p

˫ p v q

Example:

Bob is here

Therefore, Bob is here or my head turned into an octopus

Disjunction Elimination (vE – version of constructive dilemma CD)

p v q

pr

qr

˫ r

Example:

The U.S. will launch a nuke or Russia will launch a nuke

If the U.S. launches a nuke, then everyone on the planet will die

If Russia launches a nuke, then everyone on the planet will die

Therefore, everyone on the planet will die

Biconditional Introduction (↔I – version of material equivalence ME)

pq

qp

˫ pq

Example:

If I go to the movies with you, then you will pay for my ticket

If you pay for my ticket, then I will go to the movies with you

Therefore, I will go to the movies with you if and only if you pay for my ticket

Biconditional Elimination (↔E – version of material equivalence ME)

pq

˫ pq

or

˫ qp

Example:

Jill is here if and only if Jill’s ugly boyfriend is here

Therefore, if Jill is here, then her ugly boyfriend is here

Therefore, if Jill’s ugly boyfriend is here, then Jill is here

Example of a proof using the basic rules of inference

1. ~~P [assumption]

2. P ↔ Q [assumption]

3. P → Q [2, ↔E (ME)]

4. P [1, ~E (DN)]

5. Q [3, 4, →E (MP)]

6. R v Q [5, vI (ADD)]

7. ˫ P & (R v Q) [4, 6, &I (CONJ)]

DERIVED RULES

Modus Tollens (MT)

p q

~q

˫ ~P

Example:

If Bob is here, then we are in for big trouble

It is not the case that we are in for big trouble

Therefore, it is not the case that Bob is here

Hypothetical Syllogism (HS)

pq

qr

˫ pr

Example:

If you look back, then you will turn into a pillar of salt

If you turn into a pillar of salt, then deer will lick your face for eternity

Therefore, if you look back, then deer will lick your face for eternity

Disjunctive Syllogism (DS)

p v q

~p

˫ q

Example:

We will have hot dogs for dinner or we will have hamburgers for dinner

It is not the case that we will have hot dogs for dinner

Therefore, we will have hamburgers for dinner

Absorption (ABS)

pq

˫ p → (p & q)

Example:

If Bob is here, then we are in for big trouble

Therefore, if Bob is here, then Bob is here and we are in for big trouble

Constructive Dilemma (CD)

p v q

pr

qs

˫ r v s

Example:

Mom will come home first tonight or dad will come home first tonight

If mom comes home first tonight, then we will have hot dogs for dinner

If dad comes home first tonight, then we will have hamburgers for dinner

Therefore, we will have hot dogs for dinner or we will have hamburgers for dinner

Repeat (RE)

p

˫ p

Example:

I’m not going to say this again

Therefore, I’m not going to say this again

p

~p

˫ Any wff

Example:

Bob is here

It is not the case that Bob is here

Therefore, my head turned into an octopus

Theorem Introduction

Theorem Introduction (TI):

Introduce any tautology,

Example: ~(P & ~P)

It is not the case that (Bob is here and Bob is not here)

Theorems are wffs that are tautologies (i.e., whose instances are logically necessary), and any theorem can be inserted into a lines of proofs

They are provable without making any nonhypothetical assumptions

Biconditional equivalences are tautologies, and thus theorems

The symbol “˫” designates a theorem

Examples:

˫ ~(P & ~P)

˫ P → (P v Q)

˫ P → [(P → Q) → Q]

˫ P ↔ ~~P

˫ P v ~P

EQUIVALENCES (ALSO CALLED RULES OF REPLACEMENT)

These rules allow you to replace one wff with another that is logically equivalent to it. It helps to think of the ↔ as an equal sign, where the wff one side of the ↔ is logically equivalent to the wff on the other side. The logical equivalence of the two wffs in question can be demonstrated on a truth table, where the truth assignment of the one wff is exactly the same as the truth assignment of the other wff. These rules of replacement apply to both complete premises and also parts of wffs. Each of these rules serves a particular strategy or purpose within logical proofs, as indicated beneath each of the following rules.

De Morgan’s Law (DM)

Version 1: ~(p & q) :: (~p v ~q)

Version 2: ~(p v q) :: (~p & ~q)

Purpose: Converts & into v (and vice versa)

Commutation (COM)

Version 1: (p v q) :: (q v p)

Version 2: (p & q) :: (q & p)

Purpose: Allows reversing order of disjuncts or conjunct

Association (ASSOC)

Version 1: [p v (q v r)] :: [(p v q) v r]

Version 2: [p & (q & r)] :: [(p & q) & r]

Purpose: Allows moving parentheses

Distribution (DIST)

Version 1: [p & (q v r)] :: [(p & q) v (p & r)]

Version 2: [p v (q & r)] :: [(p v q) & (p v r)]

Purpose: Allows pairing the first conjunct (or disjunct) with each part of the second conjunct

Double Negation (DN)

p :: ~~p

Purpose: Introduces or eliminates ~~

Transposition (TRANS)

(pq) :: (~q→~p)

Purpose: Modus tollens in one line

Material implication (MI)

(pq) :: (~p v q)

Purpose: Converts → into v

Material Equivalence (ME)

Version 1: (pq) :: [(p & q ) v (~p & ~q)]

Version 2: (pq) :: [(pq ) & (qp)]

Purpose: Converts ↔ into other logical connectives

Exportation (EXP)

[(p & q) → r) :: (p → (qr)]

Purpose: Converts & to → (and vice versa) in part of a wff

Tautology (TAUT)

Version 1: p :: (p & p)

Version 2: p:: (p v p)

Purpose: Creates an & or v from a single wff

HYPOTHETICAL RULES (RULES USING ASSUMPTIONS)

Negation Introduction (~I – indirect proof IP)

The rule:

Assume p

Get q & ~q

˫ ~p

Example:

1. (P & Q) v P / ˫ P

2. | ~P [Hypothesis for IP (~I)]

3. | P & Q [1, 2 DS]

4. | P [3 SIMP (&E)]

5. | P & ~ P [2, 4 CONJ (&I)]

6. ˫ P [2-5 IP (~I)]

Negate the intended conclusion, draw an explicit contradiction from the negation, infer the intended conclusion

An explicit contradiction (or an “absurdity”) is p&~p

Also called Reductio ad absurdum (reduction to absurdity)

Conditional Introduction (→I – conditional proof CP)

The rule:

Assume p

Get q

˫ pq

Example:

1. P / ˫ (P → Q) → Q

2. | P → Q [Hypothesis for CP (→I)]

3. | Q [2, 1 MP (→E)]

4. ˫ (P → Q) → Q [2-3 CP (→I)]

Tip: use when needed conclusion is a conditional

Guidelines for hypothetical rules

1. Each hypothesis introduced into a proof begins a new vertical line

2. No occurrence of a formula to the right of a vertical line may be cited in any rule applied after that line has ended

3. If two or more hypotheses are in effect simultaneously, then the order in which they are discharged must be the reverse of the order in which they are introduced

4. A proof is not complete until all hypotheses have been discharged

Proof Strategies

1. When conclusion is an atomic formula: If no other strategy is immediately apparent, hypothesize the negation of the conclusion for ~I. If this is successful, then the conclusion can be obtained after the ~I by ~E.

2. When conclusion is a negated formula: Hypothesize the conclusion without its negation sign for ~I. If a contradiction follows, the conclusion can be obtained by ~I.

3. When conclusion is a conjunction: Prove each of the conjuncts separately and then conjoin them with &I.

4. When conclusion is a disjunction: Sometimes (though not often) a disjunctive conclusion can be proved directly simply by proving one of its disjuncts and applying vI. Otherwise, hypothesize the negation of the conclusion and try ~I.

5. When conclusion is a conditional: Hypothesize its antecedent and derive its consequent by →I.

6. When conclusion is a biconditional: Use →I twice to prove the two conditionals needed to obtain the conclusion by ↔I.