Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

One day, I bought Principia Mathematica and saw a lot of proofs of logical equations, such as $\vdash p \implies p$ or $\vdash \lnot (p \wedge \lnot p)$. (Of course there's bunch of proofs about rel&set in later)

After reading these proofs, I suddenly thought that "why they don't use the truth table?". I know this question is quite silly, but I don't know why it's silly either (just my feeling says that).

My (discrete math) teacher says that "It's hard question, and you may not understand until you'll become university student," which I didn't expected (I thought the reason would be something easy).

Why people don't use truth table to prove logical equations? (Except for study logic (ex: question like "prove this logic equation using truth table"), of course.)

PS. My teacher is a kind of people who thinks something makes sense iff something makes sense mathematically.

share|improve this question
11  
I think "It's hard question, and you may not understand until you'll become university student," is a long way to say "I don't know" –  quanta May 17 '11 at 0:34
    
@quanta ..maybe, but I think he does know it (he doesn't speak indirectly, I think). –  JiminP May 17 '11 at 0:38
add comment

3 Answers

up vote 12 down vote accepted

In Principia, the authors wanted to produce an explicit list of purely logical ideas, including an explicit finite list of axioms and rules of inference, from which all of mathematics could be derived. The method of truth tables is not such a finite list, and in any case would only deal with propositional logic.

The early derivations of Principia are quite tedious, and could have been eliminated by adopting a more generous list of initial axioms. But for reasons of tradition, the authors wanted their list to be as small as possible.

Remark: Principia is nowadays only of historical interest, since the subject has developed in quite different directions from those initiated by Russell and Whitehead. The idea of basing mathematics (including the development of the usual integers, reals, function spaces) purely on "logic" has largely been abandoned in favour of set-theory based formulations. And Principia does not have a clear separation between syntax and semantics. Such a separation is essential to the development of Model Theory in the past $80$ years.

share|improve this answer
    
Thanks! (Since symbols and ideas(as you mentioned) in P.M. are 100 years old, now I'm reading both P.M. and metamath.) –  JiminP May 17 '11 at 0:49
add comment

First, of course, mathematicians and logicians often do use truth tables, so it is incorrect to suggest that they are not used. (I won't comment on your reading of Principia Mathematica, beyond saying that that text is not meant to be taken as a piece of pedagogy.)

But second, the truth table method is not a feasible method for large propositions. This is because for a formula with $n$ free variables, the truth table is an object with $2^n$ rows, exponentially large in size. But many logical expressions nevertheless have comparatively short derivations showing them to be tautological.

For example, $$(p_0\vee \neg p_0)\wedge(p_1\vee \neg p_1)\wedge\cdots\wedge(p_{100}\vee\neg p_{100})$$ has a truth table with $2^{101}$ rows, but there is a simple, obvious derivation that allows us to see it as taugological without calculating this table.

Thus, although when there are just two propositional variables, I don't mind computing a truth table, or even for three, it is often easier with more to use more focused reasoning.

share|improve this answer
    
Thanks, but I think there's "more" than just that reason... –  JiminP May 17 '11 at 0:34
    
The solution to the example could also be viewed as an efficiently calculated truth table. ($p_0\vee \neg p_0$ is always true, and $p_1\vee \neg p_1$ is always true, and so on.) –  André Nicolas May 17 '11 at 4:00
1  
Well, I suppose any derivation can be thought of as reasoning about the truth table, but I take the question to be drawing a distinction between these two modes of reasoning. In any case, did you actually calculate or even write down the truth table at all, even efficiently? –  JDH May 17 '11 at 10:40
    
In the context of the question, the term "derivation" had a syntactic feel. Actual proofs have a a good deal of semantic content, though they are (neologism?) syntaxable. –  André Nicolas May 17 '11 at 12:59
    
@JDH: And we run into the question of "what is a truth table?". If you're referring to a particular 'data structure', you are right, it's infeasible to use. But if you're referring to a type of 'object', then there are data structures that are more efficient to use in this case. –  Hurkyl May 12 '12 at 8:21
add comment

Your teacher may be referring to the difference between semantics and syntax. A syntactic proof is a finite formal derivation of a sentence from the axioms of a theory using the logical axioms and the rules of inference of a logic. A proof by a truth table is a semantic proof; in allowing truth tables you are tacitly assuming the completeness theorem of propositional logic. Essentially, a priori, we don't know that everything we can prove by studying the models of a theory (i.e. truth tables, in the case of propositional logic) can be proven syntactically, or even for that matter vice versa. It's a non-trivial result in logic, which I will state below:

Definition. Let $T$ be a theory in some logic. We say the logic is sound if every sentence $P$ which can be formally derived from the axioms of $T$ is true in every model of $T$, i.e. $T \vdash P$ implies $T \vDash P$. We say the logic is complete if when a sentence $P$ is true for every model of $T$, $P$ can also be derived formally from the axioms of $T$, i.e. $T \vDash P$ implies $T \vdash P$.

Theorem. Classical propositional logic is sound and complete.

Theorem (Gödel). Classical first-order logic is sound and complete.

And yes, it is that Gödel. There are also incomplete logics; you don't have to go very far to find them, since even second-order logic (under the usual semantics) is incomplete.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.