Modeling Logic with Truth Tables

As can be seen on the previous page, having to write out all logical expressions in English and keeping track of truth values can be tedious and burdensome. It also makes it difficult to evaluate the truth value of compound statements involving many propositions and logical connectives.

In analyzing a compound statement’s truth value, we need to be able to evaluate it for all combinations of truth values for it’s constituent parts. Without any organization, this can be quite error-prone. For example, in analyzing the relatively simple compound statement p ∧ q, we have four cases to check: p is false and q is false, p is false and q is true, p is true and q is false, and finally p is true and q is true. Without any systematic way of dealing with each case, mistakes are easy to make.

Organizing Logical Expressions

The first thing we can do to make things easy on ourselves is to simplify logical values. Up to now, propositions were evaluated as “true” or “false”. We can save ourselves a bit of writing by making the following substitutions:

0 can be used in place of “false”
1 can be used in place of “true”

What this allows us to do is express propositions (either primitive or compound) using numerical values. For example, if proposition p evaluates to “true”, we can also say that p evaluates to 1. Therefore, we can say that ¬p evaluates to “false”, or equivalently, we can say that ¬p evaluates to 0. Of course, the equals sign = can also be used. Thus, if we know that p = 1, then we’d have that ¬p = 0.

Next, we can organize groups of propositions into tables, and record the truth value of each proposition in a cell of that table. Such tables are called truth tables. In these types of tables, the first row is used to label each column with a proposition. Each row of these tables is used to record the numerical value of the propositions used in their respective columns.

Example 1.2.1

Suppose we want to evaluate the truth value for the proposition ¬p ∨ q when p is true and q is false, and when p is false and q is true. Note that this is a compound proposition made up of propositions ¬p and q connected by a conjunction. Furthermore, ¬p is the negation of proposition p.

We want to keep track of the values of p, q, ¬p, and ¬p ∨ q, so our table needs four columns. Next, we only want to evaluate these propositions at two sets of values: one where p is true and q is false, and one where p is false and q is true. So our table needs three rows (one row for recording the propositions being tracked in the table.) We’ll throw in two more rows just so we can capture all possible assignments of p and q.

We start by constructing our table as follows, where only the values of p and q are given initially. Remember, we can use 0 in place of “false”, and 1 in place of “true”.

p	q	¬p	¬p ∨ q
0	0
0	1
1	0
1	1

Next, let’s examine the cell colored green in the next table.

p	q	¬p	¬p ∨ q
0	0
0	1
1	0
1	1

The green cell is in the ¬p column, so that’s the expression being evaluated by the green cell. The given values for p and q in this row are p = 1 and q = 0. Based on how negation is defined that means that ¬p = 0. So, we fill in a 0 for the green cell.

p	q	¬p
0	0
0	1
1	0	0
1	1

Next, let’s focus on the next cell marked in green.

p	q	¬p
0	0
0	1
1	0	0
1	1

This cell is in the ¬p ∨ q column, so that is the expression being evaluated by this cell. In this row, the value of ¬p is 0, and the value of q is 0 as well. By definition of disjunction, we have that ¬p ∨ q = 0. We fill in this green cell with the number 0.

p	q	¬p	¬p ∨ q
0	0
0	1
1	0	0	0
1	1

We can fill out the second row of this truth table following the same basic procedure. In the second row of the ¬p column, since p = 0, we have that ¬p = 1. In the second row of the ¬p ∨ q column, since ¬p = 1 and q = 1, we have that ¬p ∨ q = 1.

p	q	¬p	¬p ∨ q
0	0
0	1	1	1
1	0	0	0
1	1

We take the same approach for filling out the first and fourth row to complete the truth table.

p	q	¬p	¬p ∨ q
0	0	1	1
0	1	1	1
1	0	0	0
1	1	0	1

Revisiting the Logical Connectives

We can use truth tables to evaluate the logical connectives talked about previously.

Negation is a very simple logical operation that depends on only one proposition.

p	¬p
0	1
1	0

Conjunction and disjunction (and and inclusive-or) act on two propositions, so we’ll need four rows to examine all possible combinations of truth values.

p	q	p ∧ q
0	0	0
0	1	0
1	0	0
1	1	1

p	q	p ∨ q
0	0	0
0	1	1
1	0	1
1	1	1

Next up, we also have the exclusive-or. Not quite as common as other logical connectives, but still simple enough.

p	q	p ⊻ q
0	0	0
0	1	1
1	0	1
1	1	0

Finally, we have the logical implications.

p	q	p → q
0	0	1
0	1	1
1	0	0
1	1	1

p	q	p ↔ q
0	0	1
0	1	0
1	0	0
1	1	1

We can also collect all of this information in one larger truth table.

p	q	¬p	p ∧ q	p ∨ q	p ⊻ q	p → q	p ↔ q
0	0	1	0	0	0	1	1
0	1	1	0	1	1	1	0
1	0	0	0	1	1	0	0
1	1	0	1	1	0	1	1

Tautologies and Contradictions

Using the previous logical connectives, let’s examine an interesting example.

Example 1.2.2

Consider the following truth table.

p	q	p ∨ q	p → (p ∨ q)
0	0
0	1
1	0
1	1

We start by filling out the p ∨ q column:

p	q	p ∨ q
0	0	0
0	1	1
1	0	1
1	1	1

Now, based on how logical implication → works, we fill out the last column:

p	q	p ∨ q	p → (p ∨ q)
0	0	0	1
0	1	1	1
1	0	1	1
1	1	1	1

The last column consists entirely of 1s. So, no matter, what p and q evaluate to, whether they are simple or compound, it appears that p → (p ∨ q) is always true.

If we translate this to English, we get

“If p, then p or q”.

Of course if we start with p, then we always get p regardless if q is true or false. Thus, this statement should always evaluate to true, which is what we just observed.

Keep in mind that, in our example, we evaluated the associated proposition for every possible combination of values for p and q. In other words, no matter what p and q are, the expression always evaluates to 1.

We could run into the opposite situation where every value in a column evaluates to 0.

Example 1.2.3

Consider the following truth table:

p	q	¬p	¬p ∧ q	p ∧ (¬p ∧ q)
0	0
0	1
1	0
1	1

The third and fourth columns are relatively easy to evaluate. The last column doesn’t require too much work either. The complete table looks like the following:

p	q	¬p	¬p ∧ q
0	0	1	0
0	1	1	1
1	0	0	0
1	1	0	0

Notice that in the last column, every value is 0, meaning for all possible values of p and q, the expression p ∧ (¬p ∧ q) always evaluates to 0.

This should make sense. How can we have both p and ¬p? Suppose p represents the statement “The sun is shining”. Then ¬p represents the statement “The sun is not shining”. This means that ¬p ∧ p represents the statement “The sun is not shining, and the sun is shining” or perhaps equivalently “The sun is simultaneously not shining and shining”.

Such a statement is nonsensical. As such, any compound proposition that is made up of p and ¬p in a conjunction is probably impossible to be true. Depending on how complicated a logical expression is, the overall proposition may still evaluate to true, but care should be taken, especially when parts of that large proposition contains these kinds of constituent propositions.

For example, the proposition

q ∨ (p ∧ ¬p)

will evaluate to 1 when q = 1, even though the proposition (p ∧ ¬p) is contained within the larger proposition q ∨ (p ∧ ¬p).

We have special names for these kinds of situations.

Tautology, Contradiction

A compound statement is called a tautology if it is true for all possible truth value assignments for its component statements. The symbol T₀ is commonly used to represent tautological statements.

A compound statement is called a contradiction if it is false for all possible truth value assignments for its component statements. The symbol F₀ is commonly used to represent contradictory statements.

Satisfiability

Truth tables allow us to quickly determine whether or not for a given compound proposition, there are values for its constituent propositions that yield a value of 1 or 0.

Satisfiable, Unsatisfiable

A compound proposition is called satisfiable if there exists values of its constituent propositions that result in the compound proposition having a truth value of 1.

Otherwise, that compound statement is called unsatisfiable.

In order to be satisfiable, a compound statement has to have a truth value of 1 for at least one combination of truth values for its constituent parts. This means that in its truth table, there is at least one 1 in its column.

Notice that if a compound statement is a contradiction, then there will be no 1s in its column in a truth table. This means it is unsatisfiable. Otherwise, if a compound statement is not a contradiction, then there is at least one 1 in its column in a truth table.

In effect, this means that contradictions are unsatisfiable, while non-contradictions are satisfiable.

Notice that this definition says nothing about primitive propositions. That’s because either that primitive proposition is true or false. It doesn’t depend on other propositions, and so trying to test combinations of truth value assignments for those non-existent propositions would be meaningless.

Example 1.2.4

We can construct truth tables for compound propositions made up of three smaller propositions. These truth tables will require 8 rows for each value assignment.

Consider the following truth table:

p	q	r
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

The last two columns are relatively simple, so completing this table won’t be too much of a hassle.

p	q	r	p ∨ q	(p ∨ q) ∧ r
0	0	0	0	0
0	0	1	0	0
0	1	0	1	0
0	1	1	1	1
1	0	0	1	0
1	0	1	1	1
1	1	0	1	0
1	1	1	1	1

Here, there are only three cases where (p ∨ q) ∧ r can be made true. One such case is when p = 1, q = 0, and r = 1. Thus, the expression (p ∨ q) ∧ r is satisfiable.

Example 1.2.5

Let’s take another look at the truth table from Example 1.2.2:

p	q	p ∨ q	p → (p ∨ q)
0	0	0	1
0	1	1	1
1	0	1	1
1	1	1	1

In this case, we have that p → (p ∨ q) is a tautology. Every combination of values for p and q yield a truth value of 1. The expression p → (p ∨ q) is thus satisfiable.

Example 1.2.6

Let’s take another look at a slightly different truth table than what is presented in Example 1.2.3:

p	q	¬p	p ∧ q
0	0	1	0
0	1	1	0
1	0	0	0
1	1	0	1

Here, we have that ¬p ∧ (p ∧ q) = F₀. This compound statement is not satisfiable.

The Book ofFoundational Mathematics

Quick Links