Page 304 - Encyclopedia of Philosophy of Language

Language and Logic
based on ideas about what is provable rather than on semantic ideas like 'truth' and 'counter-example.'
1. Prepositional Logic and Truth Tables
from other formulas(like the examples concerning 'v' and '-' above). Each logical connective must have both introduction and elimination rules.
These rules are then used to check which logical formulas can be derived from which. For example, suppose one wished to show that example (4) above was provable in a natural deduction system for classi- cal prepositional logic, then a finite sequence of for-
Consider the case of classical, two-valued, prep-
ositional logic. This is the system of logic which
assumes that every proposition is either true or false
(and not both) and whose logical connectives ('not,' 'and,''or'and'if...then')aredefinedbythefollowing mulaswouldbeconstructedasfollows: truth-tables (where T=true and F = false):
(notP) (PandQ) (PorQ) -P P&Q PvQ
FT TTT TTT TF TFF TTF FFT FTT FFF FFF
(ifPthenQ) (1)
TTT TFF FTT FTP
(1) (2) (3) (4)
(5) (6)
1,2
1, 2, 3 2, 3
P Assumption (6) Pr>Q Assumption
QrsR Assumption
Q From land 2by
=3-elimination (modus ponens) R From 3 and 4 by =>-elimination Pr>R From 1and 3 by =>-introduction
A formula of this system of logic is said to be a 'tautology' or 'valid,' provided it is true whatever the value of its constituent propositions (provided it always has the value T under the main connective of its truth-table). If this is not the case, there is a 'counter- example' to the formula, and it is said to be 'invalid.'
With these basic ideas one can test (some) natural language arguments for validity by translating them into the notation of prepositional logic and using truth-tables; either one finds a counter-example or the argument is valid. For example, many 'logical principles' which people intuitively accept can be shown to be valid:
P or not P (2) if P implies Q and Q is false then P must be false. (3) if P implies Q and Q implies R then P implies R. (4) ifPorQaretrueandQisfalsethenPmustbetrue. (5)
2. NaturalDeductionandProof
Natural deduction methods proceed quite differently. Keeping to the example of classical prepositional logic, the same underlying semantic ideas can be found, but everything is articulated in terms of what is provable from what—in terms of 'proof-rules' or 'inference-rules.' For example, one of the rules will say that from the conjunction 'P&Q' one can derive 'P '; another will say that from '— P ' one can derive 'P '; another will say that from the formula 'P ' one can derive 'P vQ'; another will say that if you can derive both 'Q' and '-Q ' from 'P ,' then '-P ' is provable, etc. The rules consist of 'introduction rules' and 'elim- ination rules': the elimination rules permit the 'elim- ination' of a logical connective from a formula, that is, they show which logically simpler formulas can be derived from a formula containing a given logical connective (like the examples concerning '&' and '— ' above); the introduction rules permit the 'intro- duction' of logical connectives, that is, they show which logically more complex formulas can be derived
where the numbers without brackets list the formulas on which the formula to their right 'depends.' This finite sequence of formulas shows that the formal equi- valent of example (4) above is provable in standard natural deduction systems for classical prepositional logic (with the rules indicated; for a detailed expo- sition of such a system see Lemmon 1965).
A natural deduction system for classical prep- ositional logic then consists of a set of inference rules, like those mentioned above, and one uses these rules to test whether a given formula can be derived from other formulas. This is different from testing for val- idity by constructing truth- tables. On the natural deduction approach one constructs finite sequences of formulas, each of which is either an assumption made for the purpose of the test, or is derived from other formulas in the sequence by one of the rules of the natural deduction system. The object is to see if one can derive the conclusion of an argument from its premises using valid rules of inference.
The rules of 'natural deduction' systems are fre- quently rather 'unnatural' (especially for systems richer than prepositional logic), and the process of constructing a proof sequence within such a system is often counterintuitive. However, it is fair to say that natural deduction systems are more 'natural' than 'axiomatic' approaches to logic. Gottlob Frege was the first person to articulate the principles of modern logic, in his Begriffsschrift (1879), and his presentation of logic was axiomatic (i.e., resembling Euclid's axiomatic presentation of geometry). Russell and Whitehead's Principia Mathematica (1910-13) was similar in its axiomatic approach to logic. S. Jas- kowski and G. Gentzen independently devised natural deduction approaches to logic in the early 1930s. However, the method of 'semantic tableaux' (due to E. Beth in the mid-1950s) is probably the most 'natu- ral' way of testing the validity of arguments (for a good exposition, see Jeffery 1967; for more on the history and development of natural deduction systems see Kneale and Kneale 1962:538).
282