Truth Tables

In the last chapter, we covered propositional operators that essentially enable us to create new propositions from atomic propositions. In there, we also came across truth tables, in exploring the semantics of the operators.

However, we didn't get a rigorous definition of truth tables, nor did we see how to represent complex propositions using truth tables where we have more than two variables. In this chapter, our aim is to formalise our understanding of truth tables.

Let's begin.

If we were to precisely define a truth table, we'd get something as follows:

In simpler words, a truth table simply evaluates a given proposition in all possible truth values for the simpler propositions that it is composed of.

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.

For example, to show whether a compound proposition is always true, or always false, we could model it using a truth table and then see the column representing the truth value of 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.

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 we come to the compound proposition.

The compound proposition is then evaluated in the last column. This is one convention to draw a truth table.

Let's back all this long discussion by considering a real example.

Suppose we're given the proposition ::(p \to (q \wedge \neg q)) \vee \neg p:: and we're asked to draw a truth table for it.

1. 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::

2. 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::

3. Next up, 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!

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 of these 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?

It's good to know how to figure out how many rows would there be in the truth table for a given 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 next 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!

Let's apply this idea on one example.

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 length by 2.

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.

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.

For instance, given the expression ::(p \to q) \to \neg p::, here's how it would be represented using this convention"

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

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.