Chapter 03 Summary

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.