1
$\begingroup$

I was reading vellmans how to prove it and he forms a link between formal logic and proof writing. For instance, he decomposes if p then q to not(p and not q) and similarly for other such proof writing statements. However what I don't follow is What's the motivation for writing out truth tables and evaluating conditions for them.

Usually, we write out Boolean statements like p and not q etc. and evaluate the truth tables when we wish to evaluate different conditions of p and q. Here however, we know that p is either true or not and q is determined accordingly. Why truth tables?

My question might seem a bit vague and under thought but I can't seem to grasp the fundamentals itself so all else is shaky too.

3 Answers 3

3

You say

we know that p is either true or not and q is determined accordingly.

But that's just not true. If we have "if p then q" and p is false, then q may be true or false, since there's no "only if" in our statement. It may be that p being true makes q true, but that some other circumstance could also make q true. All that we have ruled out is "p and not q": in other words, the statement "if p then q" is exactly the statement "not (p and not q)" which, by standard manipulations (or you can use truth tables to work this out!) is the same as "not p, or else q".

Now, why do we care at all? Well, writing out truth tables helps us to understand complex statements and their interaction. So that, for example, we can discover that $(((p\Rightarrow q)\Rightarrow p)\Rightarrow p)$ is true regardless of $p$ and $q$, and we can use it in proofs accordingly. Similarly, we can establish that $p \Rightarrow p$ is true, and that $(q \Rightarrow r) \Rightarrow ((p \Rightarrow q) \Rightarrow (p \Rightarrow r))$ is true, which together sort of tell us that $\Rightarrow$ up to propositional equivalence is a partial order (but that's beyond the scope of this answer).

  • 0
    The way I see it, I *already* care about q, and I'm just going to use "if p then q" to help me understand it. My knowledge of truth tables (or whatever) can tell me that that statement only helps if "p" is true. But suppose I have "if p then q" and I also have "if not p then r" and "if r then q". It's not hard to see that under these conditions, q is definitely true. Truth tables can help me to see that.2012-07-05
0

Truth tables are of limited use in mathematical proofs. They are useful only for proving theorems in propositional calculus (PC), that is theorems without quantifiers ($\forall$ or $\exists$). If a statement in PC can be shown to be true regardless of whether its constituent propositions are true or false (in every possible combination) by using a truth table, then that statement is said to be a theorem in PC. (For a nice truth table generator, see: http://mathdl.maa.org/images/upload_library/47/mcclung/index.html)

There are other ways to prove theorems in PC that do not involve truth tables (see "natural deduction"). They rely on a set of axioms and rules to derive statements from other statements. If, for example, we have statements $P$ and $P\rightarrow Q$, the Detachment Rule allows us to infer $Q$. (You may want to play around with these rules of inference using my DC Proof 2.0 software, available free at my website http://www.dcproof.com)

0

You talk about True and False for these statements and I am not used to that when discussing logic. I am used to rational or not rational, valid or not valid. Are we thinking of different kinds of proofs?