BBC Home

Explore the BBC

Front Page

Life | The Universe | Everything | Advanced Search
 
Front PageReadTalkContributeHelp!FeedbackWho is Online

Click here to complete your registration.

 
3. Everything / Maths, Science & Technology / Computers / Computer Languages and Programming
3. Everything / Maths, Science & Technology / Mathematics

Boolean Truth Tables

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


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

AND Function
(A AND B)
Argument
A
Argument
B
Function
Value
falsefalsefalse
falsetruefalse
truefalsefalse
truetruetrue
OR Function
(A OR B)
Argument
A
Argument
B
Function
Value
falsefalsefalse
falsetruetrue
truefalsetrue
truetruetrue
NOT Function
(NOT A)
Argument
A
Function
Value
falsetrue
truefalse

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.

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 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.

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 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

Arguments
Function
Value
falsefalsetruesame
falsetruetruesame
falsetruefalsesame
other combinationsvarious
After Abbreviation

Arguments
Function
Value
falsedon't caretruesame
falsetruefalsesame
other combinationsvarious

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.

Before Abbreviation
with duplicate entry

Arguments
Function
Value
falsefalsetruesame
falsetruetruesame
falsetruetruesame
falsetruefalsesame
other combinationsvarious

After Abbreviation

Arguments
Function
Value
falsedon't caretruesame
falsetruedon't caresame
other combinationsvarious

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

Before Abbreviation

Arguments
Function
Value
falsefalsefalsesame
falsefalsetruesame
falsetruetruesame
falsetruefalsesame
other combinationsvarious
First Abbreviation

Arguments
Function
Value
falsefalsedon't caresame
falsetruedon't caresame
other combinationsvarious

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

First Abbreviation

Arguments
Function
Value
falsefalsedon't caresame
falsetruedon't caresame
other combinationsvarious
Second Abbreviation

Arguments
Function
Value
falsedon't caredon't caresame
other combinationsvarious

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.

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.


1 Named after mathematician George Boole (1815 - 1864).
2 The terms input and output are better reserved for logic devices which implement functions.
3 The terms argument and function are frequently used together in both mathematics and computer programming.
4 Systems analysts in particular use this alternative meaning.
5 Alternative conventions are explored in Electronic Logic Conventions.
6 A more general and precise rule is given later.
7 In large tables, X or ? are frequently used to denote don't care.
8 To show more than two stages requires rather large tables initially
9 The solution of this problem may require art rather than science.

Discuss this Entry  Click here to be the first person to discuss this Guide Entry





Add your Opinion!

There are tens of thousands of h2g2 Guide Entries, written by our Researchers. If you want to be able to add your own opinions to the Guide, simply become a member as an h2g2 Researcher. Tell me More!

 
Entry Data
Entry ID: A1325251 (Edited)

Written and Researched by:
Old Hairy

Edited by:
SchrEck Inc.


Date: 07   January   2004


Text only
Like this page?
Send it to a friend


Referenced Guide Entries
Mathematics
Propositional Logic
Boolean Algebra
Seven Secrets of Successful Programmers
Electronic Logic Conventions
Boolean Functions Classified
Boolean Function Reduction
Universal Functions of Boolean Algebra
Boolean Expressions from Truth Tables


Related BBC Pages
Learning


Most of the content on this site is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here to alert our Moderation Team. For any other comments, please start a Conversation below.
 


Front PageReadTalkContributeHelp!FeedbackWho is Online

Most of the content on h2g2 is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here. For any other comments, please start a Conversation above.


About the BBC | Help | Terms of Use | Privacy & Cookies Policy