Natural deduction logic
From Wikipedia, the free encyclopedia
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 propositional logic. 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,C 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 omniscient.
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.
