Truth tables are one means of defining Boolean1 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 inputs2. The function itself is analogous to a process, by which the arguments3 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 2n 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 satisfied4. Such tables, which share some properties of Boolean function truth tables, are not considered here.
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 convention5 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 2n-1.
Conversely, writing the numbers 0 to 2n-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 2n 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 2n-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 22n to be accurately represented, which grows extremely rapidly with n.
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 values6. 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 care7 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 this8. 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 problem9, and will not be further discussed here.
When an abbreviated truth table entry contains m don't care arguments, it represents 2m unabbreviated entries (which gives 20=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.
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.