Natural deduction logic
|
|
A natural deduction is an instruction on how to use binary logic to move from one line to another, during a linear sequential proof. Every natural deduction, is one of the tautologies of the propositional calculus. As an example of a natural deduction, consider the hypothetical syllogism HS.
Hypothetical Syllogism HS:If A then B, if B then C; therefore If A then C.
Consider the following deduction of hypothetical syllogism HS, which employs the natural deduction known as modus ponens, in order to 'deduce' that hypothetical syllogism is a natural deduction. Let A,B denote arbitrary statements.
- If A then B [Stipulated to be true]
- If B then C [Stipulated to be true]
- A [Open scope of first assumption]
- B [1,3; Modus Ponens]
- C [2,4; Modus Ponens]
- If A then C [Close scope of first assumption]
QED
As can be seen, this proof that hypothetical syllogism is a natural deduction, relied on the reasoning agent already knowing that modus ponens is a natural deduction.
Modus Ponens MP: If A then B, A; therefore B
Thus, in order for a reasoning agent to learn that hypothetical syllogism is a valid natural deduction from this deduction(alternatively reasoning event), the reasoning agent had to already know that modus ponens is a natural deduction. Modus ponens is a priori knowledge of this reasoning event (knowledge possessed at the beginning of the reasoning event), and hypothetical syllogism is the a posteriori knowledge of this reasoning event(new knowledge).
A reasoning agent who already knows enough natural deductions, so that in principle (memory limitations aside), he can determine whether or not some statement is a natural deduction, is said to be logically omnisicent.
Natural deduction was rigorously worked on by S. Jaskowski in 1934, and G. Gentzen in 1935. However, serious work using natural deduction goes as far back as the ancient Greeks, who worked out the mathematics of geometry, using natural deductions. The greatest example of this, is Euclid's elements. Thus, the technique of natural deduction has been around for as long as there have been reasoners.
References
Hintikka, J. Knowledge and Belief: An Introduction to the Logic of the Two Notions, Cornell University Press, Ithaca: 1962.
External link
- The Logical Omniscience Of Reactive Systems, Nigel Seel (http://www.interweave-consulting.com/h/omnisc.html)
- Bayesian Epistemology, Stanford Encyclopedia of Philosophy (http://plato.stanford.edu/entries/epistemology-bayesian/)