Logic: truth tables

edit: 29 Mar, the compact proof truth table for modus ponens needed “2”, not “1” under column 7.

I think this will be the first of three posts on logic. In this one, I will look at truth tables and at using them to prove tautologies (valid logical propositions).

(If I had known how much typographic trouble this post would cause…. Well, after a little practice with the new symbols, it wasn’t so bad.)

I expect that the second post will deal with “quantifiers “, namely “there exists” and “for all”, and their classical or linguistic counterparts, “some”, and “all”.

And the third post should deal with Aristotle’s syllogisms. They started it all — for me in particular, and for the world in general. All I wanted to do when I started was review the syllogisms given what little I knew of modern logic. It turns out there’s a major difference between Aristotle and modern logic, largely motivated I think by the explicit idea of the empty set. We’ll see the difference in principle in the second post, in practice in the third.

As usual, I’m not trying to write an introductory text here, just picking out a few things that interest me.

Introduction

Let me also say up front — and I’ll try to remember to say it again — that we have more power in truth tables than I understand. That is to say, when people talk about “well formed formulas” and formal proofs, they seem to require “modus ponens” as a starting point.

That’s a fancy name for something we take for granted: that from two premises P and (P implies Q), we may conclude Q.

(Yes, that seems incredibly obvious. In fact, we almost never say it explicitly: we usually just write QED as soon as we have P and (P implies Q). It has a fancy Latin name — actually, its fancy name is modus ponendo ponens, which means something like “method that affirms by affirming”.

But I can prove “modus ponens” — to use its usual abbreviation — using truth tables. So why do I need to assume it?

I don’t know. I plan to keep my eyes open.

One of the things that happened to me, is that after looking at formal logic systems and named rules to be cited as line-by-line justifications (I’ll show you an example of that in the next post) — I lost sight of the fact that we can prove things using truth tables.

The point of a truth table is to show the truth or falsity of a compound statement as a function of the truth or falsity of its components. It is, in fact, a proof by exhaustive enumeration of all possible cases.

Let me just jump into truth tables now.

We may define “negation” by exhaustion, using the following table:

\left(\begin{array}{cc} P & \text{Not P} \\ \text{True} & \text{False} \\ \text{False} & \text{True}\end{array}\right)

That says two things: that if P is true, then not-P is false; and if P is false, then not-P is true. If I can (yes!), I will use \neg P for not-P.

By the way, my Mathematica® commands for that were:

Similarly, we may define “and” using the third column of the following table:

\left(\begin{array}{ccc} P & Q & P\land\ Q \\ \text{True} & \text{True} & \text{True} \\ \text{True} & \text{False} & \text{False} \\ \text{False} & \text{True} & \text{False} \\ \text{False} & \text{False} & \text{False}\end{array}\right)

That is, “P and Q”, wriiten P \land Q\ , is true exactly when P is true and Q is true.

For reference, the Mathematica commands were:

We will find it convenient to define the “inclusive or” — that is, “P or Q or both”. (Why is it convenient? Because it gives us “De Morgan’s Laws”, for which I’ll show an example below.)

The “exclusive or” would be “P or Q but not both” — so called because it excludes the possibility that both are true.

We take the following table as the definition of the inclusive or:

\left(\begin{array}{ccc} P & Q & P \lor Q \\ \text{True} & \text{True} & \text{True} \\ \text{True} & \text{False} & \text{True} \\ \text{False} & \text{True} & \text{True} \\ \text{False} & \text{False} & \text{False}\end{array}\right)

We see that the inclusive or is false exactly when both P and Q are false.

Once again, let me include the Mathematica commands:

Finally, we will take as our definition of “implies” the following — perhaps peculiar — table. (This choice has a name, material implication.)

\left(\begin{array}{ccc} P & Q & P \Rightarrow Q \\ \text{True} & \text{True} & \text{True} \\ \text{True} & \text{False} & \text{False} \\ \text{False} & \text{True} & \text{True} \\ \text{False} & \text{False} & \text{True}\end{array}\right)

What may seem peculiar is that the implication is false in only one of the four cases: the implication is false if P is true and Q is false.

In particular, we say the implication is true in the two cases when P is false. Another way to describe that is to say that the implication “P implies Q” is vacuously true whenever P is false — in both possible cases, Q false and Q true.

Both of the introductory logic books I have picked up (both titled “Introduction to Logic”, one by Gensler and the other by Copi & Cohen — both soon to be in the bibliography!) have more than a few pages about this. Interestingly, neither Exner nor Hummel say much about it. (We learn to take it for granted in mathematics.)

I’m not going to say much about it either. As I said, this definition of implication is called “material implication” — and I invite you to go search the internet or your books.

What I will say — and this is the bare minimum — is that we have effectively defined implication as being equivalent to this: we never have “P and not Q”. That is, with this definition — this truth table for implication — we have an equivalence:

(P\Rightarrow Q)\equiv \neg (P\land \neg Q)\ .

Oh, notation. I tend to use the angular symbols \land and \lor for “and” and “or”. (And I’m very glad that LaTeX will do them.) Given a chance, Mathematica would use && and ||. It also understands functions “And” and “Or”.

Worse, where I would prefer to use either ~ or \neg for negation, Mathematica uses !, or “Not”. In fact, I will use \neg whenever I can.

Worst, none of the symbols on the “basic typesetting” palette seems to work for “implication” — so I have to use its named function, “Implies”, in Mathematica.

Oh, let me show you an example of De Morgan’s Laws. We effectively used this equivalence

(P\Rightarrow Q) \equiv \neg (P\land \neg Q)\

to justify the definition of material implication. In this form, it seems very natural to me.

De Morgan’s Theorem (Law, Laws) says that I can eliminate the ( ) on the RHS by apply the negation operator to both pieces, and replacing “and” by “or”, getting:

(P\Rightarrow Q)\equiv \neg P\lor Q\ .

(And that’s the model, in my head anyway, that seems a little odd. Valid, but odd at first glance.)

Now is a good time to remark: we will find either of these equivalents handy. After all, they let us eliminate the implication symbol.

Having defined implication by a truth table, we are in a position to verify either of those equivalences. Let’s do the original one.

Proving an equivalence, long form

First, let me construct the truth table for the right-hand side. I will present this in detail. Then I will show you how to compress the proof.

\left(\begin{array}{ccccc} P & Q & \neg Q & P \land \neg Q & \neg (P \land \neg Q) \\ \text{True} & \text{True} & \text{False} &   \text{False} & \text{True} \\ \text{True} & \text{False} & \text{True} & \text{True}   & \text{False} \\ \text{False} & \text{True} & \text{False} &   \text{False} & \text{True} \\ \text{False} & \text{False} & \text{True} &   \text{False} & \text{True}\end{array}\right)

All we do is move from one column to the next, using our definitions to determine True or False, based on the previous (leftward) columns. Set P, set Q, set \neg Q from them, then do the next column….

It seems about as straight-forward as possible.

That gave us the RHS. For the LHS, we recall the definition of implication…

\left(\begin{array}{ccc} P & Q & P \Rightarrow Q \\ \text{True} & \text{True} & \text{True} \\ \text{True} & \text{False} & \text{False} \\ \text{False} & \text{True} & \text{True} \\ \text{False} & \text{False} & \text{True}\end{array}\right)

and we see that the last columns agree. (It’s a very good thing that P and Q were lined up correctly. How convenient. We’ll see that sometimes it takes work to arrange that in Mathematica. By hand, of course, it should be simple enough.)

It might be nice if we could lay out the equivalence in one table, rather than having to compare the two last columns in two tables.

(Let me say something. I didn’t work out the following two examples of compact proofs because they looked nice— although they do! I did it because I needed to work out exactly what the heck Hummel was doing. Yes, he was doing just what I thought he should — but I needed to do it for myself. And since Mathematica was pretty capable….)

Proving an equivalence, compact form

Here’s a way to do it in one table. Basically, we will use each symbol (counting not-Q as one symbol) of the tautology to be proved as a column heading in the truth table.

We want to show

(P\Rightarrow Q)\equiv \neg (P\land \neg Q)\ ,

so we take those symbols as our column headings. Alas, it’s easier to describe the finished product than to get Mathematica to lay it out progressively.

\left(\begin{array}{cccccccc} P & \Rightarrow  & Q & \equiv  & \neg  & (P &   \land  & \neg Q) \\ \text{True} & \text{True} & \text{True} & \text{True}   & \text{True} & \text{True} & \text{False} &   \text{False} \\ \text{True} & \text{False} & \text{False} &   \text{True} & \text{False} & \text{True} &   \text{True} & \text{True} \\ \text{False} & \text{True} & \text{True} & \text{True}   & \text{True} & \text{False} & \text{False} &   \text{False} \\ \text{False} & \text{True} & \text{False} &   \text{True} & \text{True} & \text{False} &   \text{False} & \text{True} \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 4 & 2 & 7 & 6 & 1 & 5 & 3\end{array}\right)

(There is a minor typo — a missing “)” — in the Mathematica headers, and I fixed it in the LaTeX.)

I have numbered the columns in the second-to-last row for descriptive purposes — there is no need to do that for yourself. We wouldn’t usually show the numbers on the bottom row, either.

What’s it all mean?

First (as indicated by “1” at the bottom of columns 1 and 6), we lay out the possible values of P. Since there are two possible values for Q, we know we need 4 entries for P — two true, two false.

Then (“2” in column 3) we assign the 4 values of Q in such a way as to get all four possible sets of truth values for the set {P,Q}.

Third (“3” in column 8 ) we fill in \neg Q from Q in column 3.

Fourth (column 2), under the \Rightarrow symbol, we fill in the values for P \Rightarrow Q\ , using the values of P, Q in columns 1 and 3.

Let’s do that explicitly. Recall the definition of implication, once again:

\left(\begin{array}{ccc} P & Q & P \Rightarrow Q \\ \text{True} & \text{True} & \text{True} \\ \text{True} & \text{False} & \text{False} \\ \text{False} & \text{True} & \text{True} \\ \text{False} & \text{False} & \text{True}\end{array}\right)

… and let me display our complete table right close by:

\left(\begin{array}{cccccccc} P & \Rightarrow  & Q & \equiv  & \neg  & (P &   \land  & \neg Q) \\ \text{True} & \text{True} & \text{True} & \text{True}   & \text{True} & \text{True} & \text{False} &   \text{False} \\ \text{True} & \text{False} & \text{False} &   \text{True} & \text{False} & \text{True} &   \text{True} & \text{True} \\ \text{False} & \text{True} & \text{True} & \text{True}   & \text{True} & \text{False} & \text{False} &   \text{False} \\ \text{False} & \text{True} & \text{False} &   \text{True} & \text{True} & \text{False} &   \text{False} & \text{True} \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 4 & 2 & 7 & 6 & 1 & 5 & 3\end{array}\right)

For column 2 — and the trick is getting used to looking at column 2 instead of column 3! Oh, when I say row 1, for example, I am not counting the header…

  1. For row 1, we have P,Q = T,T so we enter T in column 2, according to the truth table for implication.
  2. For row 2, we have P,Q = T,F so we enter F in column 2.
  3. For row 3, we have P,Q = F,T so we enter T in column 2.
  4. For row 4, we have P,Q = F,F so we enter T in column 2.

(No, the order in which we do columns isn’t actually set in stone, although I think it makes sense to define Q and then \neg Q instead of the other way around. But we could have done column 4 third instead of fourth, as soon as we had columns 1 and 3 which determine it.)

Similarly, fifth, we fill in the column labeled \land (column 7) with the values for P \land \neg Q\ . This time we are using the truth table for “and” applied to the row-by-row entries for P and \neg Q in columns 6 and 8.

Sixth, use the column labeled \neg (column 5) to hold the values of \neg(P \land \neg Q)\ , found by negating the values in column 7.

Seventh and finally, in column 4 we explicitly record the equivalence, row by row, of columns 2 and 5, which contain the LHS and RHS respectively.

We conclude that the equivalence is true because every entry in column 4 is True.

OK?

Proving an implication, compact form

Let’s try that for an implication rather than for an equivalence.

Let’s prove “modus ponens”:

\left(\begin{array}{ccccccc} (P & \Rightarrow  & Q) & \land  & P & \Rightarrow  & Q   \\ \text{True} & \text{True} & \text{True} & \text{True}   & \text{True} & \text{True} & \text{True} \\ \text{True} & \text{False} & \text{False} &   \text{False} & \text{True} & \text{True} &   \text{False} \\ \text{False} & \text{True} & \text{True} &   \text{False} & \text{False} & \text{True} &   \text{True} \\ \text{False} & \text{True} & \text{False} &   \text{False} & \text{False} & \text{True} &   \text{False} \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 3 & 2 & 4 & 1 & 5 & 2\end{array}\right)

(Once again I have edited the LaTeX to add ( ) which are not actually in the Mathematica headings. and edit: column 7 should have “2” on the bottom.)

Ok, if we did that manually — of course Mathematica did it all for me —

  1. we fill in columns 1 and 5 with values for P;
  2. we fill in columns 3 and 7 with appropriate values for Q (we need the four possible ordered pairs of values for (P,Q);
  3. we fill in column 2 with the values of P \Rightarrow Q using the values in columns 1 and 3;
  4. we fill in column 4 using the values of (P \Rightarrow Q) \land P using columns 2 and 5;
  5. finally, we fill in column 6 using the values in columns 4 and 7.

We see that in every possible case, the implication in column 6 has the value True.

The two examples differ in how the final column (which is not the rightmost!) was computed. In the previous example, we entered T in column 4 when columns 2 and 5 were the same (since we were testing equivalence); that turned out to be every time, i.e. every row.

In this second example, we entered T in column 6 whenever it was true that column 4 implied column 7. To be explicit, columns 4 and 7 do not have the same values, row by row — they differ only in the third row. But for the third row, for example, it is true that F implies T, so we enter T in row 3 of column 6.

Look at it another way: if columns 4 and 7 always agreed in this case, we would have proven equivalence instead of implication.

Let me add that I worked this out in more detail, below.

Let me emphasize that it is not necessary to use the compact form that I’ve laid out. Having worked the first example both ways, let me now work the second example in the not-so-compact way.

Proving an implication, long form

So we want to prove “modus ponens” again:

\text{LHS table} = \left(\begin{array}{cccc} P & Q & P \Rightarrow Q & (P \Rightarrow Q) \land P \\ \text{True} & \text{True} & \text{True} & \text{True}   \\ \text{True} & \text{False} & \text{False} &   \text{False} \\ \text{False} & \text{True} & \text{True} &   \text{False} \\ \text{False} & \text{False} & \text{True} &   \text{False}\end{array}\right)

The RHS is simply Q — but I need to line up the occurences of Q. Hmm. And I need four values.

That’s what I need.

Now, let’s construct a table for LHS \Rightarrow RHS\ .

Our first column is the final column of the LHS table…

t5=Take[t3,All,-1];

t5 = \left(\begin{array}{c} \text{True} \\ \text{False} \\ \text{False} \\ \text{False}\end{array}\right)

Our second column is the RHS… (Sewing these together was a little annoying; this illustrates why I find it easier to use the compact tables for proofs: corresponding Ps and Qs are lined up.)

\text{LHS - RHS table} = \left(\begin{array}{cc} \text{LHS} & \text{RHS} \\ \text{True} & \text{True} \\ \text{False} & \text{False} \\ \text{False} & \text{True} \\ \text{False} & \text{False}\end{array}\right)

And now we recall the truth table for implication, since that’s what we’re trying to prove.

\left(\begin{array}{ccc} P & Q & P \Rightarrow Q \\ \text{True} & \text{True} & \text{True} \\ \text{True} & \text{False} & \text{False} \\ \text{False} & \text{True} & \text{True} \\ \text{False} & \text{False} & \text{True}\end{array}\right)

We see that row 2 of implication does not occur in our LHS-RHS table (row 4 occurs twice), and the missing row 2 is the only one that is false — so all of the rows of our final column are True:

\left(\begin{array}{ccc} \text{LHS} & \text{RHS} & LHS \Rightarrow RHS   \\ \text{True} & \text{True} & \text{True} \\ \text{False} & \text{False} & \text{True} \\ \text{False} & \text{True} & \text{True} \\ \text{False} & \text{False} & \text{True}\end{array}\right)

That is, LHS \Rightarrow RHS is true in every possible case. (And that is the additional detail that I promised when I did the compact proof of modus ponens.)

I should point out that we certainly don’t want to have to use truth tables for everything: they are literally a proof by complete enumeration of all possible cases. This is one reason for coming up with a handy list of tautologies (valid rules of inference) and using rules instead of truth tables.

(But it still doesn’t answer the question troubling me: if I can prove modus ponens, why must they take it as an axiom when they set up rules of inference? When I understand this, I’ll talk about it. For all I know, the very existence of truth tables may implicitly require modus ponens!)

The next logic post should deal with the classical quantifers, “all” and “some” and “none”, and their modern counterparts, “there exists” and “for all”.

Advertisements
Posted in logic. 2 Comments »

2 Responses to “Logic: truth tables”

  1. Bill Says:

    awesome!

  2. rip Says:

    Thanks. Keep coming back… there should be some more logic posts eventually.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: