**Chapter 3: Inference in Propositional Logic**

**Summary**

- Valid arguments and logical truths may be proven semantically using truth tables, or proof-theoretically using a derivation or proof.
- A derivation, or proof, is a sequence of formulas, every member of which is an assumed premise or follows from earlier formulas in the sequence.
- Direct proof is a derivation method that proceeds without making any assumptions beyond the initial premises.
- Conditional proof is a derivation method useful for deriving conditional conclusions. It proceeds by assuming the antecedent of a desired conditional and deriving the consequent.
- Indirect proof is a derivation method, sometimes called
*reductio ad absurdum*, or reduction to the absurd. It proceeds by assuming a premise, showing that it leads to an unacceptable (or absurd) consequence, and then concluding the opposite of the assumed premise. - Conditional and indirect proofs are often embedded within a larger direct proof by means of an indented sequence.
- An indented sequence is a series of lines in a derivation that do not follow from the premises directly, but only with a further assumption, indicated on the first line of the sequence.
- Conditional and indirect proofs may be embedded within one another by means of a further indented sequences.
- A nested sequence is an indented sequence within another indented sequence; it is an assumption within another assumption.
- A justification shows the rule used to derive a line in a proof, along with the earlier line number(s) to which the rule is being applied.
- QED stands for
*Quod erat demonstrandum*, which is Latin for ‘that which was required to be shown’. ‘QED’ is a logician’s punctuation mark signaling the end of the derivation. - A system of inference is a set of rules for derivations.
- Our system of inference for
**PL**has two types of rules: rules of inference and rules of equivalence. - A rule of inference is a valid argument form.
- A rule of equivalence is a pair of logically equivalent proposition forms.
- The way in which we use rules of equivalence differs from the way in which we use rules of inference in three ways: (1) rules of equivalence are justified by showing that expressions of each form are logically equivalent, whereas rules of inference are justified by showing that they are valid argument forms; (2) rules of equivalence can be used in two directions, whereas rules of inference can be used in only one direction; and (3) rules of equivalence apply to any part of a proof, not just to whole lines, whereas rules of inference apply only to whole lines.
- Modus ponens (MP) is a rule of inference of
**PL**, having the form α ⊃ β, α / β. - Modus tollens (MT) is a rule of inference of
**PL**, having the form α ⊃ β, ~β / ~α. - Disjunctive syllogism (DS) is a rule of inference of
**PL**, having the form α ˅ β, ~α / β. - Hypothetical syllogism (HS) is a rule of inference of
**PL**, having the form α ⊃ β, β ⊃ γ / α ⊃ γ. - Conjunction (Conj) is a rule of inference of
**PL**, having the form α, β / α • β. - Addition (Add) is a rule of inference of
**PL**, having the form α / α ˅ β. - Simplification (Simp) is a rule of inference of
**PL**, having the form α • β / α. - Constructive dilemma (CD) is a rule of inference of
**PL**, having the form α ⊃ β, γ ⊃ δ, α ˅ γ / β ˅ δ. - Biconditional modus ponens (BMP) is a rule of inference of
**PL**, having the form α ≡ β, α / β. - Biconditional modus tollens (BMT) is a rule of inference of
**PL**, having the form α ≡ β, ~α / ~β. - Biconditional hypothetical syllogism (BHS) is a rule of inference of
**PL**, having the form α ≡ β, β ≡ γ / α ≡ γ. - ⇄ is a metalogical symbol used for ‘is logically equivalent to’.
- De Morgan’s laws (DM) are rules of equivalence of
**PL**, having the forms ~(α • β) ⇄ ~α ˅ ~β and ~(α ˅ β) ⇄ ~α • ~β. - Association (Assoc) are rules of equivalence of
**PL**, having the forms α ˅ (β ˅ γ) ⇄ (α ˅ β) ˅ γ and - α • (β • γ) ⇄ (α • β) • γ.
- Distribution (Dist) are rules of equivalence of
**PL**, having the forms α • (β ˅ γ) ⇄ (α • β) ˅ (α • γ) and - α ˅ (β • γ) ⇄ (α ˅ β) • (α ˅ γ).
- Commutativity (Com) are rules of equivalence of
**PL**, having the forms α ˅ β ⇄ β ˅ α and - α • β ⇄ β • α.
- Double negation (DN) is a rule of equivalence of
**PL**, having the form α ⇄ ~ ~α. - Contraposition (Cont) is a rule of equivalence of
**PL**, having the form α ⊃ β ⇄ ~β ⊃ ~α. - Material implication (Impl) is a rule of equivalence of
**PL**, having the form α ⊃ β ⇄ ~α ˅ β. - Material equivalence (Equiv) are rules of equivalence of
**PL**, having the forms α ≡ β ⇄ (α ⊃ β) • (β ⊃ α) and α ≡ β ⇄ (α • β) ˅ (~α • ~β). - Exportation (Exp) is a rule of equivalence of
**PL**, having the form α ⊃ (β ⊃ γ) ⇄ (α • β) ⊃ γ. - Tautology (Taut) are rules of equivalence of
**PL**, having the forms α ⇄ α • α and α ⇄ α ˅ α. - Biconditional De Morgan’s law (BDM) is a rule of equivalence of
**PL**, having the form ~(α ≡ β) ⇄ ~α ≡ β. - Biconditional commutativity (BCom) is a rule of equivalence of
**PL**, having the form α ≡ β ⇄ β ≡ α. - Biconditional inversion (BInver) is a rule of equivalence of
**PL**, having the form α ≡ β ⇄ ~α ≡ ~β. - Biconditional association (BAssoc) is a rule of equivalence of
**PL**, having the form α ≡ (β ≡ γ) ⇄ (α ≡ β) ≡ γ. - A substitution instance of a rule is a set of wffs of
**PL**that match the form of the rule. - Our system of inference for
**PL**is complete, meaning that every valid argument and every logical truth is provable in that system. - Our system of inference for
**PL**is sound, meaning every provable argument is semantically valid; every provable proposition is logically true. - A contradiction is any statement of the form: α • ~α.
- Explosion is a characteristic of classical systems of inference by virtue of which every wff can be derived from a contradiction.
- The law of the excluded middle states that any claim of the form α ˅ ~α is a tautology, a logical truth of
**PL**. In metalinguistic terms, this means that every proposition is either true or false, and not both. Any truth value besides true and false is excluded. - A theory is a set of sentences, called theorems. A formal theory is a set of sentences of a formal language.
- Our theory of
**PL**can be characterized either by the set of its logical truths or by the set of its theorems, since all logical truths are theorems and all theorems are logical truths.