What are truth tables?

Simply put:

A truth table explores all possible truth values for a compound proposition.

A truth table is a tabular way of drawing out all possible truth values for the constituent propositions of a given formula and then evaluating the formula using these truth values.

A truth table is a fundamental concept in propositional logic. It can be used to solve numerous categories of problems such as showing the semantics of logical operators; proving equivalences; solving SAT problems; etc.

To show whether a compound proposition is always true, or always false, we could represent it using a truth table and then see the column for the compound proposition.

If it contains all true values, or all false values, then we know that the proposition is always true, or false, respectively.

How to draw truth tables?

Creating a truth table for any proposition ain't difficult at all. We start by noticing the atomic propositions in the given proposition. Then we create a column for each of them, along with labeling the column so that we know which one corresponds to which proposition.

Next up, we compute each interim operation in the compound proposition one-by-one until and unless we come to the compound proposition.

This is usually evaluated in the last column but there's nothing saying that this must be the case.

One convention is to compute each interim operation under its respective operator. We'll see such a truth table later on.

Let's first back all this long discussion by creating a truth table for a given proposition.

Suppose we're given the proposition ::(p \to (q \wedge \neg q)) \vee \neg p::.

First we see that it has two atomic propositions i.e ::p:: and ::q::. These go into the first two columns of the table.

::p::::q::

After this, we list down all possible truth values for both these propositions.

::p::::q::
::\text T::::\text T::
::\text T::::\text F::
::\text F::::\text T::
::\text F::::\text F::

For each row, we evaluate the compound proposition by evaluating all the interim operations and then building all the way to the compound proposition.

::p::::q::::\neg q::::q \wedge \neg q::::p \to (q \wedge \neg q)::::\neg p::::(p \to (q \wedge \neg q)) \vee \neg p::
::\text T::::\text T::::\text F::::\text F::::\text F::::\text F::::\text F::
::\text T::::\text F::::\text T::::\text F::::\text F::::\text F::::\text F::
::\text F::::\text T::::\text F::::\text F::::\text T::::\text T::::\text T::
::\text F::::\text F::::\text T::::\text F::::\text T::::\text T::::\text T::

Once we do this for all the rows, we're done with our truth table.

That's it!

How many rows?

When starting out with truth tables, it's a common question that how many rows would be there for the given proposition?

Well, this is an interesting and useful question. At the end of the day, we ought to know when to stop writing ::\bold T:: or ::\bold F:: values in the columns denoting the atomic propositions.

So, let's think on the answer.

When we have one propositional variable, we have 2 rows. This is because the single variable can have two values.

Similarly, when we have two variables, we have 4 rows. The first variable can have 2 values. Then for each of these values, the second variable can have further two values. This means that altogether we have 4 (= 2 x 2) values.

When there are 3 variables, we have 8 rows. How?

For the first variable, we have 2 values. Then for each of these, the second variable can have further 2 values. This gives us 4 values. Now for each 4 values, the third variable can have further 2 values. This means that altogether we have 8 (= 2 x 2 x 2) possible permutations of truth values.

Notice any pattern?

For a compound proposition with ::n:: variables, its truth table has ::2^n:: rows.

How many rows would the truth table for the proposition ::(p \to q) \vee (r \vee s) \vee (\neg s \wedge t)::?

We just need to find out how many atomic propositions (propositional variables) are there in this compound proposition. Since there are 5 of them, the compound proposition has 32 (= 25) rows in its truth table.

Listing all possibilities

It's good to know how to figure out how many rows would there be in the truth table for a gien compound proposition. But how to list down all the possibilities without missing or repeating any one?

Well, we could create a rule for it.

  1. Divide the total number of possibilities, which is given by ::2^n::, by 2.
  2. In the first column, start with as many ::\bold T::'s, and then alternate with as many ::\bold F::'s.
  3. For the second column, start with half as many ::\bold T::'s as in the previous column. Then alternate with the same number of ::\bold F::'s and so on.
  4. Continue this process for each subsequent column, halving the number of ::\bold T::'s to start with until the last column is reached.
  5. The last column simply alternates between one ::\bold T:: and one ::\bold F::.

That's it!

Given the proposition ::(p \leftrightarrow (q \wedge r)) \oplus s::, we have to draw its truth table.

First we realise that it would have ::16 (= 2^4):: rows. This means that we would start with 8 ::\bold T::'s, and then alternate with as many ::\bold F::'s. And for each subsequent row, just divide this alternating distance by 2.

::p::::q::::r::::s::::q \wedge r::::p \leftrightarrow (q \wedge r)::::(p \leftrightarrow (q \wedge r)) \oplus s::
::\text T::::\text T::::\text T::::\text T::::\text T::::\text T::::\text F::
::\text T::::\text T::::\text T::::\text F::::\text T::::\text T::::\text T::
::\text T::::\text T::::\text F::::\text T::::\text F::::\text F::::\text T::
::\text T::::\text T::::\text F::::\text F::::\text F::::\text F::::\text F::
::\text T::::\text F::::\text T::::\text T::::\text F::::\text F::::\text T::
::\text T::::\text F::::\text T::::\text F::::\text F::::\text F::::\text F::
::\text T::::\text F::::\text F::::\text T::::\text F::::\text F::::\text T::
::\text T::::\text F::::\text F::::\text F::::\text F::::\text F::::\text F::
::\text F::::\text T::::\text T::::\text T::::\text T::::\text F::::\text T::
::\text F::::\text T::::\text T::::\text F::::\text T::::\text F::::\text F::
::\text F::::\text T::::\text F::::\text T::::\text F::::\text T::::\text F::
::\text F::::\text T::::\text F::::\text F::::\text F::::\text T::::\text T::
::\text F::::\text F::::\text T::::\text T::::\text F::::\text T::::\text F::
::\text F::::\text F::::\text T::::\text F::::\text F::::\text T::::\text T::
::\text F::::\text F::::\text F::::\text T::::\text F::::\text T::::\text F::
::\text F::::\text F::::\text F::::\text F::::\text F::::\text T::::\text T::

As you can see, the first column alternates between ::\bold {TTTTTTTT}:: and ::\bold {FFFFFFFF}::; the second one alternates between ::\bold{TTTT}:: and ::\bold{FFFF}::; the third one alternates between ::\bold{TT}:: and ::\bold{FF}::; and the fourth one (which is for the last variable) alternates between ::\bold T:: and ::\bold F::.

With each subsequent column, the length of ::\bold T::'s gets reduced down by a factor of 2.

Another convention

What we saw above is the most popular convention to represent truth tables. Each interim operation in the compound proposition is represented in a separate column. However, there is yet another convention to represent truth tables, that takes lesser space.

That is to evaluate each interim operation under its respective operator without creating a separate column for it.

For instance, given the same proposition as before, here's how it would be represented in the truth table

::p::::q::::(p::::\to::::q)::::\to::::\neg p::
::\text T::::\text T::::\text T::::\text F::::\text F::
::\text T::::\text F::::\text F::::\text T::::\text F::
::\text F::::\text T::::\text T::::\text T::::\text T::
::\text F::::\text F::::\text T::::\text T::::\text T::

As you can clearly notice, under each operator, we compute the truth values of the underlying operation; and in this way, build all the way up to the compound proposition.