Section Progress:

6.1 Truth Tables for &, v and ~

You've already learned how to translate sentences into BOOL. Now we are going to add a feature to our system that will allow us to prove things with BOOL.

That feature is truth tables, which are little charts showing every possible way a sentence could be true or false.

Let's start simple. We translated "Pia is guilty" as P.

Truth values: T and F.

P is just an atomic sentence. We know from bivalence that it could be true or false, which we will write T and F.

The truth table for P looks like this:

The sentence goes above the line and all its possible truth values go below it.

The truth table for every atomic sentence is the same: as far as the truth table knows, every atomic sentence could be true or false.

Complex sentences, though, are more interesting.

When is ~P true or false? Well, that depends on when P is true or false.

The truth value of any complex sentence is determined by the truth values of the atomic sentences in it.

This concept is so important it has a name: truth functionality.

Truth functional: input truth values determine output truth value.

Truth functionality is a property of connectives: a connective is truth functional just in case the truth value of a sentence made with that connective is determined just by the truth values of the input sentences.

Here's how a complex truth table looks:

The complex sentence we want to make a truth table for goes on the right, and we put the atomic sentence in a column on the left called the reference column.

We already know the atomic sentence can be true or false. Now we just have to figure out what to put for the values of ~P.

Since ~ means negation, when P is true then ~P is false, and vice versa. So the full table looks like this:

Notice that the values for negation go under the ~ symbol, so that we don't confuse those with the values for P. Keeping your columns straight will be important in larger sentences.

Negation is a simple truth function: it just inverts the truth value of the input.

Now we'll see if you can figure out the other Boolean connectives. The truth table for & looks something like this:

Since P&Q has two atomic sentences, there are two reference columns on the left.

In order to remain consistent, we must always make the reference columns in the same way, which we'll call canonical form.

Canonical form: 1. Reference columns are alphabetical. 2. The patterns of Ts and Fs is always the same.

First, they must be ordered alphabetically. Second, the patterns of Ts and Fs must be the same. The atomic sentence furthest to the right (last in the alphabet) always alternates T and F. The one next to it then alternates pairs of Ts and Fs.

Now, given what you know about &, what values should go in for each mark? When is "and" true or false?

Next, we'll figure out disjunction.

Here's an important tip for disjunction. Sometimes when people say "or", they mean one or the other but not both. That is called exclusive disjunction. For example, if you win the lottery you get it paid out annually or all at once, but not both.

v is inclusive: it is true when both inputs are true.

Boolean disjunction is not like that: it is inclusive, meaning it is still true even when both inputs are true.

So far we've learned the truth functions for the Boolean connectives.

Those truth functions are definitional: we stipulate, for example, that value of ~P is F when the value of P is T. That is what makes ~ mean negation.

Next, we'll learn how to use those definitions to compute the truth function of any sentence in BOOL.

6.1 Truth Tables for &, v and ~