PROPOSITIONAL CALCULUS

BASIC RULES OF INFERENCE (NON-HYPOTHETICAL)

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

~~*p*
→ *p*

Example:

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

Conditional Elimination (→E – modus ponens MP)

*p*
→ *q*

*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

Disjunction Introduction (vI – addition ADD)

*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*

*p*
→ *r*

*q*
→ *r*

˫
*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)

*p*
→ *q*

*q*
→ *p*

˫
*p* ↔ *q*

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)

*p*
↔ *q*

˫
*p* → *q*

or

˫
*q* → *p*

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)

*p* → *q*

*q* → *r*

˫ *p* → *r*

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)

*p* → *q*

˫ *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*

*p* → *r*

*q* → *s*

˫ *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

Contradiction (CON)

*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)

(*p* → *q*)
↔ (~*q*→~*p*)

Purpose: Modus tollens in one line

Material implication (MI)

(*p* → *q*)
↔ (~*p* v *q*)

Purpose: Converts → into v

Material Equivalence (ME)

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

Version 2: (*p*
↔ *q*) ↔ [(*p* → *q* ) & (*q* →
*p*)]

Purpose: Converts ↔ into other logical connectives

Exportation (EXP)

[(*p* & *q*)
→ *r*) ↔ (*p* → (*q* → *r*)]

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*

˫
*p* → *q*

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.