|
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
posessed 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. See
also, the problem of logical omniscience.
Systems Of Natural Deduction
Sometimes, it is said that systems of natural deductions don't have any axioms, but that is misleading. It raises the
question, as to what is meant by the term 'axiom'. Setting that question aside, here we
give an example of an axiomatic system of natural deduction. The section on symbolic logic also mentions axiomatic treatments of the subject.
Name Of System: L1
Let A,B denote statements.
Undefined terms: not, and
Axiom(conjunction C): A,B; therefore A and B
Axiom(simplification1 S1): A and B; therefore A
Axiom(simplification2 S2): A and B; therefore B
Axiom(double negation1 DN1): not(not A); therefore A
Axiom(double negation2 DN2): A; therefore not(not A)
Axiom(Conjunctive Syllogism CS): A,not(A and not B); therefore B
Definition: A or B = not(not A and not B)
Definition: If A then B = not(A and not B)
Definition: A if and only if B = (if A then B) and (if B then A)
Notice that the axioms were not framed using any of the definitions. This is consistent with common sense, which tells us that
definitions aren't logically necessary, but represent abbreviations.
A simple formal example of a natural deduction proof is contained in the first theorem of this system.
Theorem1: A and B; therefore B and A
1. A and B [Stipulated to be true]
2. B [1, simplification2]
3. A [1, simplification1]
4. B and A [2,3; conjunction]
QED
As you can see, the natural deduction above is a theorem of L1. Now, the question of whether or not L1 is complete, can be raised. That is, the question as to whether or not L1 contains
enough axioms in order for a reasoning agent to figure out all possible natural deductions (memory limitations aside), can be
raised. If the answer is yes, then the system is said to be complete. It turns out that L1 is complete, but proving so is rather
difficult.
The name 'natural deductive system' is suggestive. One of the popular ways of viewing natural deduction is that it is an
application of the axioms(laws, rules, whatever) of a system of natural deductive logic to what some have called our "natural
modes" of inference.
For instance, if I say that
- all men are mortal, and I say that
- Sammy isn't mortal, then one naturally infers that
- Sammy must not be a man.
In the above 'inference', one of the natural deductions was used, but it isn't obvious which one. The answer is modus
tollens.
What is happening, is this. The first premise of this argument is a statement made using first order
logic. The statement that "all men are mortal" can be symbolized as follows:
For any X: if X is a man then X is mortal.
In fact, we can use set theory to simplify the statement above even more.
Let A denote the set of men. Let M denote the set of mortals. Thus, the first premise can be symbolized as follows:
Premise1: For any X: if X is an element of A then X is an element of M.
The second premise of the argument is that sammy isn't mortal. This can be symbolized using set theory as follows. Let s
denote the individual sammy.
Premise2: s isn't an element of M
The conclusion of the argument can be symbolized as follows:
Conclusion: s isn't an element of A
So here is the whole argument:
Premise1: For any X: if X is an element of A then X is an element of M.
Premise2: s isn't an element of M
Conclusion: s isn't an element of A
Now, one of the rules of first order logic, is called universal instantiation. There is a universal set which is called the
domain of discourse, and only objects in that set can be instantiated for quantified variables. The quantified variable in
premise1 above, is X. Even though the domain of discourse wasn't explicitly stated, we are to presume that sammy is one of the
elements of the domain of discourse. Thus, s can be substituted(instantiated) for X. After using the rule of universal
instantiation UI, we are to conclude that the following statement is true:
If s is an element of A then s is an element of M.
We can now see how modus tollens is being used in the argument above.
Let P=s is an element of A
Let Q=s is an element of M
So here is the structure of the argument above, after universal instantiation was used, properly symbolized for
simplicity:
Premise1: If P then Q
Premise2: Not Q
Conclusion: not P
Now, here is the natural deduction known as modus tollens:
Modus Tollens MT: If A then B, not B; therefore not A
So you can see that indeed the argument above used modus tollens, but you can also see that it used universal instantiation.
The first philosopher to really make an in depth analysis of first order logic, was Aristotle. In fact, one of his most studied
(and consequently now famous) inferences, was this:
All men are mortal.
Socrates is a man.
Therefore, Socrates is mortal
In the roughly 2400 years following Aristotle, first order logic has been brought to near perfection. There are still problems
with the concept of a domain of discourse. It isn't always clear what can and cannot be instantiated for a quantified variable,
see Russell's Paradox. There are also problems with set theory
as well. But these problems aren't problems with systems of natural deduction. Both first order logic, and set theory, have
nothing whatsoever to do with natural deductions.
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
- Classical Logic, Stanford Encyclopedia of Philosophy
|