Using truth tables

Type classification: this is a lesson resource.

Welcome! This is a lesson in the Introductory Discrete Mathematics for Computer Science course.

Previous lesson: Introduction to boolean logic

Truth Tables: Definition

Truth tables are mathematical tables used in logic, to compute the truth values of logical expressions. They are tables of boolean values (values that are either true or false). The boolean domain is the set of all possible boolean values; there are two elements in the boolean domain, true and false. Thus, the boolean domain can be written as {T, F}.

Boolean n-tuples

A boolean n-tuple is an array of n boolean values.

• For example, there are two possible boolean 1-tuples: (TRUE) and (FALSE).
• There are 4 possible boolean 2-tuples: (T, T); (T, F); (F, T); (F, F). The order in which the truth values are arranged is important.
• There are 2ⁿ possible boolean n-tuples.
• For large values of n, writing all possible boolean n-tuples can be confusing. This step is important, because it is required for constructing a truth table. One suggestion is to alternate the truth values of the rightmost element one by one, the truth values of the second rightmost element two by two, and so on with the truth values of the leftmost element alternated n by n.

Your First Truth Table

Here is your first example of a truth table!

$p\,\!$	$q\,\!$	?
T	T	T
T	F	T
F	T	F
F	F	F

What operation is performed here?

ANSWER: The operation performed is that the first truth value in the 3-tuple is copied. You can make many types of truth tables, some of which will be shown in this lesson.

• An n-operand truth table is a table that assigns a boolean value to each n-tuple.

Propositional Operators

A propositional operator is a rule defined by a truth table. Some propositional operators are represented by symbols. You will learn about some of these symbols in this lesson, and more next time.

Your first propositional operator is called the negation operator. It reverses the truth value of the input. The negation operator is a monadic operator, i.e. it operates on an input with only one argument. A dyadic operator operates on an input with two arguments, e.g. p and q.

$\neg$ : The negation operator. Some people call it the NOT operator. However, this is a bit dangerous because words in language tend to be far more vague than logic.

Let $p$ represent the statement: It is raining.

$\neg p$ , represents the negation of statement $p$: It is not the case that it is raining

Or just: It is not raining.

Here is the truth table for the negation operator:

$p$	$\neg p$
T	F
F	T

How Many Truth Tables are Possible?

• There are four possible truth tables for a monadic operator. Here they are:

1. This truth table is constant true, i.e. it always returns true.

$p$	Value returned
T	T
F	T

2. This truth table is the identity, i.e. it always returns the value of p.

$p$	Value returned
T	T
F	F

3. This truth table, as we have discussed, is the negation.

$p$	Value returned
T	F
F	T

4. This truth table is constant false, i.e. it always returns false.

$p$	Value returned
T	F
F	F

In general, there are 2²ⁿ truth tables for an n-tuple operator.

Next Lesson

The next lesson is called Logical AND.