Boolean Algebra | Truth Tables | Expressions from Truth Tables
Universal Functions | Function Reduction | Functions Classified

Truth tables are one means of defining Boolean¹ functions. Here we describe the tables, show how they may be constructed, and give in detail a method for the abbreviation of such tables. Truth tables are widely used, the reasons for this including the following:

• They are relatively easy to understand, as they do not involve any formulae, yet can precisely describe the result of any Boolean formula.

• In the abbreviated form, they are succinct descriptions of Boolean operations, and are widely used in the data sheets of electronic logic devices for this reason.

• Difficult operations, such as simplifying Boolean expressions, can readily be performed by manipulating truth tables, and the abbreviation technique given here is a large part of such simplification.

• They can be used to define a logical formula, without that formula being known, and the formula can then be determined from the truth table.

It is beyond the scope of this Entry to describe these applications in detail, but some aspects of them are touched upon.

Outline of Boolean Algebra

A Boolean variable can have only two distinct values, which we shall call true and false. The laws governing such variables are the subject of Boolean algebra, which involves only three basic operations,

• A product of several variables, the logical AND operation, which gives a true result only when all constituent variables are true and a false result otherwise, in other words is true if the first variable AND the second variable AND...is true.

• A sum of several variables, the logical OR operation, which gives a true result when one or more constituent variables are true and a false result otherwise, in other words is true if the first variable OR the second variable OR...is true.

• A negation of a single variable, the logical NOT operation, which gives a true result if the variable is false, and a false result otherwise, in other words is true when a variable is NOT true.

Definition of Boolean Functions

A general Boolean function has a number of Boolean arguments, and a Boolean value, solely determined by those arguments. The arguments are analogous to inputs to the function, and are not affected by the function: they are not arguments in the sense of propositional logic. The value is analogous to an output from the function, in response to those inputs². The function itself is analogous to a process, by which the arguments³ are combined to give the value.

Construction of a Truth Table

Every Boolean function can be specified as a table. Suppose that the function has n arguments, then as each has two possible values, there are only 2ⁿ possible argument combinations, which can be listed in full. For each list entry, the function value can then be added, forming the truth table of the function. The truth table is a complete and unambiguous definition of the function, since it gives the function value in every possible case.

Care is needed to construct a truth table this way, as it is essential that every argument combination is listed. It does not matter if an argument combination is duplicated, provided that the same function value is assigned in such cases. A truth table satisfying these conditions will be called valid. The order of the entries does not matter: any rearrangement of the table entries does not change the function defined.

The following specimen truth tables (hopefully) clarify both the truth table concept and the Boolean operations.

Example Truth Tables: Basic Boolean Operations

The term truth table is often used in a slightly different sense. The entries in the table represent a multiplicity of conditions to be tested, and a required action when those conditions are satisfied⁴. Such tables, which share some properties of Boolean function truth tables, are not considered here.

Binary Notation

The construction of a truth table may be facilitated by using a binary notation, where the values true and false are replaced by the digits 0 and 1. It is a matter of convention⁵ only which digit is used to represent true, and then false is represented by the other digit.

If the arguments are listed in the same order each time, the values of n arguments can be represented as a string of n bits. This bit string can be interpreted as a binary number, associated with the relevant truth table entry. By this means, the entries for a function of n arguments are then numbered from 0 to 2ⁿ-1.

Conversely, writing the numbers 0 to 2ⁿ-1 in binary notation is a systematic way to list the argument combinations, which happens to give them a specific order.

The function value for each entry in an entire truth table can be written as a string of 2ⁿ bits, in the order arising naturally from the use of binary notation. This bit string may be a useful representation for automated manipulation of truth tables.

The 2ⁿ-bit string may also be interpreted as a binary number. This single number represents the entire truth table, but the usefulness of this is limited in practice. A function of n arguments requires any number in the range 0 to 2²ⁿ to be accurately represented, which grows extremely rapidly with n.

Abbreviated Tables

Often, both possible values of a specific argument, true and false, result in the same function value when all the other arguments have a specific combination of values⁶. In such circumstances, we do not care what value a specific argument has: the function value is determined anyway. Denoting an argument as don't care⁷ can then be used to merge two truth table entries.

All lines of a truth table with the same function value can be examined to see whether any of them can be merged by the following process. In the tables below the function value is given as same, to represent values which are all true, or all false. The process of abbreviation is to identify the essential combinations of argument values that result in the same function value, and eliminate the need to specify those parts which don't affect it. An example may help to clarify this.

Before abbreviation, the first two lines differ only in the value of the second argument, so that they can be abbreviated by merging to a single line. Further reduction then seems impossible, but note that if the second line had been duplicated, a further line merger would be possible, as shown below.

The first two lines are mergeable, and the last two lines are also mergeable. Although in the case the abbreviated result is still two entries (as before), in many applications it is advantageous for as many arguments as possible to be given don't care values. This simple example also illustrates some aspects of abbreviated tables.

• Although the function may be well defined, the representation when using don't care values may cease to be unique.

• Each of table entry with a don't care value represents two different entries from the unabbreviated table, but two abbreviated entries do not necessarily represent four unabbreviated entries.

In general, merging is permitted if both possible values of a specific argument, true and false, result in the same function value when all the other arguments have a specific combination of values, where each argument may be true or false or don't care. The merging process can then be repeated until no further merging is possible.

The following example demonstrates the first two stages of this⁸. The first stage is

Now, using the general reduction rule, further abbreviation is possible, giving

Again, to make maximum use of this may require certain entries to be duplicated. To reduce a truth table in a manner which is optimum for a specific application is a rather technical problem⁹, and will not be further discussed here.

When an abbreviated truth table entry contains m don't care arguments, it represents 2^m unabbreviated entries (which gives 2⁰=1 entry when there are no don't cares). However, the total number of entries represented in an abbreviated table is not necessarily found by adding such counts for each entry.

Caution

Truth tables may be constructed (designed?) in abbreviated form ab initio. However, this process is notoriously error prone, and it is recommended that such tables are expanded to the unabbreviated form to check their validity.