6. PROPOSITIONAL CALCULUS
Outline
James Fieser, UT Martin
updated 6/1/2021
Propositional calculus builds upon propositional logic, and it involves a collection of inference rules that are used to produce proofs of valid argument forms. This chapter discusses four groups of inference rules.
A. EIGHT BASIC RULES OF INFERENCE (non-hypothetical)
1. Negation Elimination (~E – version of double negation DN)
~~p
˫ p
Example:
1. If it is not the case that Bob is not here
2. Therefore, Bob is here
2. Conditional Elimination (→E – modus ponens MP)
p → q
p
˫ q
Example:
1. If Bob is here, then we are in big trouble
2. Bob is here
3. Therefore we are in big trouble
3. Conjunction Introduction (&I – conjunction CONJ)
p
q
˫ p & q
Example:
1. Bob is here
2. Joe is here
3. Therefore, Bob is here and Joe is here
4. Conjunction Elimination (&E – simplification SIMP)
p & q
˫ p
Example:
1. Bob is here and Joe is here
2. Therefore, Bob is here
5. Disjunction Introduction (vI – addition ADD)
p
˫ p v q
Example:
1. Bob is here
2. Therefore, Bob is here or my head turned into an octopus
6. Disjunction Elimination (vE – version of constructive dilemma CD)
p v q
p → r
q → r
˫ r
Example:
1. The U.S. will launch a nuke or Russia will launch a nuke
2. If the U.S. launches a nuke, then everyone on the planet will die
3. If Russia launches a nuke, then everyone on the planet will die
4. Therefore, everyone on the planet will die
7. Biconditional Introduction (↔I – version of material equivalence ME)
p → q
q → p
˫ p ↔ q
Example:
1. If I go to the movies with you, then you will pay for my ticket
2. If you pay for my ticket, then I will go to the movies with you
3. Therefore, I will go to the movies with you if and only if you pay for my ticket
8. Biconditional Elimination (↔E – version of material equivalence ME)
p ↔ q
˫ p → q
or
˫ q → p
Example:
1. Jill is here if and only if Jill’s ugly boyfriend is here
2. Therefore, if Jill is here, then her ugly boyfriend is here
3. 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)]
B. DERIVED RULES
1. Modus Tollens (MT)
p → q
~q
˫ ~P
Example:
1. If Bob is here, then we are in for big trouble
2. It is not the case that we are in for big trouble
3. Therefore, it is not the case that Bob is here
2. Hypothetical Syllogism (HS)
p → q
q → r
˫ p → r
Example:
1. If you look back, then you will turn into a pillar of salt
2. If you turn into a pillar of salt, then deer will lick your face for eternity
3. Therefore, if you look back, then deer will lick your face for eternity
4. Disjunctive Syllogism (DS)
p v q
~p
˫ q
Example:
1. We will have hot dogs for dinner or we will have hamburgers for dinner
2. It is not the case that we will have hot dogs for dinner
3. Therefore, we will have hamburgers for dinner
5. Absorption (ABS)
p → q
˫ p → (p & q)
Example:
1. If Bob is here, then we are in for big trouble
2. Therefore, if Bob is here, then Bob is here and we are in for big trouble
6. Constructive Dilemma (CD)
p v q
p → r
q → s
˫ r v s
Example:
1. Mom will come home first tonight or dad will come home first tonight
2. If mom comes home first tonight, then we will have hot dogs for dinner
3. If dad comes home first tonight, then we will have tofu for dinner
4. Therefore, we will have hot dogs for dinner or we will have tofu for dinner
6. Repeat (RE)
p
˫ p
Example:
1. I’m not going to say this again
2. Therefore, I’m not going to say this again
7. Contradiction (CON)
p
~p
˫ Any wff
Example:
1. Bob is here
2. It is not the case that Bob is here
3. Therefore, my head turned into an octopus
Explanation: if you assert two propositions that contradict each other, then the world of logic falls apart, and anything goes.
Proof (where Z is any arbitrary proposition)
1. P [assumption]
2. ~P [assumption]
3. P v Z [1, vI (ADD)]
4. ˫ Z [3, 2 DS]
8. 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 line of a proof
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
C. EQUIVALENCES (also called rules of replacement)
These rules allow you to replace one wff with another that is logically equivalent to it. Unlike the previous rules, these apply to both complete premises and also sub-wffs within premises. The four-dot "::" symbol used below in these equivalence rules is another way of representing a biconditional relation, which so far we have been symbolizing with the double arrow "↔". The four-dot symbol is used here only because it makes the rules easier to understand upon first glance, in contrast with using the double arrow symbol which can be confusing. It helps to think of the :: sign (and also the ↔ sign) 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. Each of these rules serves a particular strategy or purpose within logical proofs, as indicated beneath each of the following rules.
1. 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)
2. Commutation (COM)
Version 1: (p v q) :: (q v p)
Version 2: (p & q) :: (q & p)
Purpose: Allows reversing order of disjuncts or conjunct
3. 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
4. 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 (or disjunct)
5. Double Negation (DN)
p :: ~~p
Purpose: Introduces or eliminates ~~
6. Transposition (TRANS)
(p → q) :: (~q→~p)
Purpose: Modus tollens in one line
7. Material implication (MI)
(p → q) :: (~p v q)
Purpose: Converts → into v
8. 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
9. Exportation (EXP)
[(p & q) → r] :: [p → (q → r)]
Purpose: Converts & to → (and vice versa) in part of a wff
10. Tautology (TAUT)
Version 1: p :: (p & p)
Version 2: p :: (p v p)
Purpose: Creates an & or v from a single wff
D. HYPOTHETICAL RULES (rules using assumptions)
1. Conditional Introduction (→I – conditional proof CP)
The rule:
Assume p
Get q
˫ p → q (yellow designates the main conditional operator in conclusion)
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)]
Purpose: use as a shortcut in a proof when you need to conclude a conditional statement (the conclusion of all conditional proofs have a conditional as its main operator)
Procedure: if you are trying to prove a conditional statement, such as "(P → Q) → Q)", introduce the antecedent of the conditional as a hypothesis (e.g., "P → Q"), and then work to derive the intended consequent to that conditional (e.g., "Q"). The premises with the vertical lines (e.g., statements 2 and 3), designate something like a quarantined work area where you are solving the problem based on your assumption.
Tips: (1) in easy examples like this, as usual, bring down the conclusion in statement 1 to the conclusion in statement 4; (2) place the conclusion's antecedent into the first statement in the quarantined area (e.g., "P → Q"); (3) place the conclusion's consequent in the last statement of the quarantined area (e.g., "Q").
Intuitive reading of the above example: In this example, you are given just "P", and asked to conclude from this "(P → Q) → Q". Conjunction Introduction (conditional proof), provides a short cut for doing this. Begin by assuming as a hypothesis that someone like Santa Claus magically gave you the antecedent of your conclusion (i.e., "P→Q"), which you then write down in your quarantine area on statement two. Using this assumption, along with what you are given in premise 1 (i.e., P), you can use modus ponens to conclude Q, which you write down in your quarantine area on statement three. The conclusion, then, is essentially a summary of what you just did in your quarantine area: by assuming (P → Q), you were able to infer Q. Written out formally in your conclusion as "(P → Q) → Q", the yellow conditional means that you inferred the consequent "Q" from the assumed antecedent (P → Q).
2. 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)]
Example:
1. ~(B v C)
2. A → B,
3. ~A → B / ˫ ~(B v C) & (B v C)
4. |A [Hypothesis for IP (~I)
5. | B [2, 5 →E (MP)]
6. | B v C [5 vI (ADD)]
7. |~(B v C) & (B v C) [1, 6 &I (CONJ)]
7. ~A [4-7 IP (~I)]
8. B [3, 7 →E (MP)]
9. B v C [8 vI (ADD)]
10. ˫ ~(B v C) & (B v C) [1, 9 &I (CONJ)]
Purpose: this is a quick way of proving a conclusion by assuming its opposite and then drawing a contradiction from that assumption.
Procedure: negate the intended conclusion as an hypothesis, 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)
3. 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
4. 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.