In more formal terms, a deduction is a sequence of statements such that every statement can be derived from those before it. It is understandable, then, that this leaves open the question of how we prove the first sentence (since it cannot follow from anything). Axiomatic propositional logic solves this by requiring the following conditions for a proof to be met:
A proof of α from an ensemble Σ of well-formed-formulas (wffs) is a finite sequence of wffs:β1,… ,βi,… ,βn
whereβn = α
and for each βi (1 ≤ i ≤ n), either
- βi ∈ Σ
- βi is an axiom,
- βi is the output of Modus Ponens for two
Different versions of axiomatic propositional logics contain a few axioms, usually three or more than three, in addition to one or more inference rules. For instance, Gottlob Frege's axiomatization of propositional logic, which is also the first instance of such an attempt, has six propositional axioms and two rules. Bertrand Russell and Alfred North Whitehead also suggested a system with five axioms.
For instance a version of axiomatic propositional logic due to Jan Lukasiewicz (1878-1956) has a set A of axioms adopted as follows:
- PL1 p → (q → p)
- PL2 (p → (q → r)) → ((p → q) → (p → r))
- PL3 (¬p → ¬q) → (q → p)
and it has the set R of Rules of inference with one rule in it that is Modu Ponendo Ponens as follows:
- MP from α and α → β, infer β.
The inference rule(s) allows us to derive the statements following the axioms or given wffs of the ensemble Σ.
Natural deductive logic
In one version of natural deductive logic presented by E.J. Lemmon that we should refer to it as system L, we do not have any axiom to begin with. We only have nine primitive rules that govern the syntax of a proof.
The nine primitive rules of system L are:
- The Rule of Assumption (A)
- Modus Ponendo Ponens (MPP)
- The Rule of Double Negation (DN)
- The Rule of Conditional Proof (CP)
- The Rule of ∧-introduction (∧I)
- The Rule of ∧-elimination (∧E)
- The Rule of ∨-introduction (∨I)
- The Rule of ∨-elimination (∨E)
- Reductio Ad Absurdum (RAA)
In system L, a proof has a definition with the following conditions:
- has a finite sequence of wffs (well-formed-formula)
- each line of it is justified by a rule of the system L
- the last line of the proof is what is intended (Q.E.D, quod erat demonstrandum, is a Latin expression that means: which was the thing to be proved), and this last line of the proof uses the only premise(s) that is given; or no premise if nothing is given.
Then if no premise is given, the sequent is called theorem. Therefore, the definitions of a theorem in system L is:
- a theorem is a sequent that can be proved in system L, using an empty set of assumption.
or in other words:
- a theorem is a sequent that can be proved from an empty set of assumptions in system L
An example of the proof of a sequent (Modus Tollendo Tollens in this case):p → q, ¬q ⊢ ¬p Modus Tollendo Tollens (MTT)Assumption numberLine numberFormula (wff)Lines in-use and Justification 1 (1) (p → q) A 2 (2) ¬q A 3 (3) p A (for RAA) 1,3 (4) q 1,3,MPP 1,2,3 (5) q ∧ ¬q 2,4,∧I 1,2 (6) ¬p 3,5,RAA Q.E.D
An example of the proof of a sequent (a theorem in this case):⊢p ∨ ¬pAssumption numberLine numberFormula (wff)Lines in-use and Justification 1 (1) ¬(p ∨ ¬p) A (for RAA) 2 (2) ¬p A (for RAA) 2 (3) (p ∨ ¬p) 2, ∨I 1, 2 (4) (p ∨ ¬p) ∧ ¬(p ∨ ¬p) 1, 2, ∧I 1 (5) ¬¬p 2, 4, RAA 1 (6) p 5, DN 1 (7) (p ∨ ¬p) 6, ∨I 1 (8) (p ∨ ¬p) ∧ ¬(p ∨ ¬p) 1, 7, ∧I (9) ¬¬(p ∨ ¬p) 1, 8, RAA (10) (p ∨ ¬p) 9, DN Q.E.D
Each rule of system L has its own requirements for the type of input(s) or entry(s) that it can accept and has its own way of treating and calculating the assumptions used by its inputs.
- Hypothetico-deductive method
- Induction (philosophy)
- Propositional calculus
- History of logic
All logic textbooks-and there are now hundreds of them-deal with deduction and inference. Here are some representative ones:
- Copi, Irving M., and Carl Cohen. Introduction to Logic. Prentice Hall. (Many editions; the latest, from 2004, is the 12th.)
- Hurley, Patrick J. A Concise Introduction to Logic. Belmont, CA: Wadsworth/Thompson Learning. (Many editions; the latest is the 9th.)
- Jennings, R. E. Continuing Logic, the course book of 'Axiomatic Logic' in Simon Fraser University, Vancouver, Canada
- Johnson, Robert M. Fundamentals of Reasoning: A Logic Book. Belmont, CA: Wadsworth. (Latest is the 4th edition.)
- Reese, William L. "Deduction," in Dictionary of Philosophy and Religion, New and Enlarged Edition. Atlantic Highlands, NJ: Humanities Press, 1996.
- Zarefsky, David. Argumentation: The Study of Effective Reasoning Parts I and II, The Teaching Company, 2002.
All links retrieved November 7, 2017.