Part 1: Understanding the truth table
Before implementing any functionality it is important to understand what we are building. Here we discuss what the truth table should look like and what it is made of. After that, we give a simple example where we build a truth table manually.
What is a truth table?
A truth table can be split into two or four parts. The table has a header which consists of propositional variables and subformulas. Each row of the table corresponds to a specific valuation and the evaluation for each subformula depends on that valuation. Here’s an illustration.
Figure 2. Truth table example. A truth table is organized into distinct parts. The header consists of the variables and subformulas, while the rows represent each valuation and its corresponding evaluation.
Note: To be concise, we will assume that the propositional variables can be either 0 (False) or 1 (True).
Example
Let us consider the formula $((A \land B) \lor C)$. The propositional variables present in this formula are $A$, $B$ and $C$. A subformula is defined as any formula that is contained within parentheses or that follows a negation symbol. In this context, we identify two subformulas: $(A \land B)$, and the entire formula $((A \land B) \lor C)$, which is also considered a subformula.
For a truth table with 3 propositional variables, there will be $2^3 = 8$ possible valuations represented in the table. This is because each of the 3 variables can take on 2 possible truth values (true or false), and the total number of unique combinations is $2 * 2 * 2 = 8$. Here they are:
| A | B | C |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
We start by evaluating the subformula $A \land B$:
| A | B | (A ∧ B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Note that the variable $C$ does not influence the outcome of this particular subformula.
For convenience, we can use the shorthand notation $AB$ to represent the subformula $(A \land B)$. With this, the formula $((A \land B) \lor C)$ can be more concisely expressed:
| AB | C | (AB ∨ C) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
We can then match the valuations and evaluations to complete the table:
| A | B | C | (A ∧ B) | ((A ∧ B) ∨ C) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Can truth tables be built efficiently?
Given a proposition, a truth table lists for each valuation, the truth value that the proposition is evaluated to. It means that we have to evaluate the propositional formula as many times as there are assignments of truth values to its variables. Unfortunately, the number of valuations is exponential in the number of variables. This makes the program slow as formulas get larger.
We will take the knowledge learned from part 1 to implement the truth table builder in the next part of this subproject. The goal is to learn new techniques and to generate truth tables automatically by providing formulas.