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

Boolean Function Reduction

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


This Entry concerns Boolean Algebra1, and proves a statement about Boolean functions. It shows that Boolean functions having three or more arguments may be expressed as a composition of functions having only two arguments, including a method for achieving this simplification. This implies that:

Any Boolean function, no matter how complex, can be implemented using electronic logic devices having only two inputs.

Definition of a Boolean Function

A general Boolean function has a number of arguments, and a unique value depending only upon those arguments - with the arguments and function value being limited to one of two distinct values, which we shall call true and false. Such a function is completely defined by a truth table, which we shall assume has no don't care entries, and no duplicate entries2.

Argument Extraction

Suppose we have a function of n > 2 arguments, F say, represented by its truth table. We can select any argument, which we shall call X, and use it to split the given truth table into two equal parts, tables P and Q, say, by the following procedure.

Each entry in the table for F is examined in turn, and used to create a modified truth table item with X omitted. If the value of X was false, then the new item is added to table P, and if X was true the new item is added to table Q.

When this process is complete, the tables P and Q will each have only half the number of entries present in the F table. None of the details of F are lost, since the splitting process is readily reversed, by taking all the entries in P augmented with an argument X of value false, and adding all the entries in Q augmented with an argument X of value true3.

If the truth table of F is valid, then for every combination of arguments it contains one entry. It therefore contains entries where X is false with every combination of the other arguments, and entries where X is true with every combination of the other arguments. Thus each of the tables P and Q included every combination of all arguments of F except for X, and hence are valid truth tables for functions of n - 1 arguments. This justifies supposing that tables P and Q represent functions, which may as well be called P and Q respectively.

When X is false, the value of F is given by P, and when X is true, the value of X is given by Q, and hence

F = ( ( NOT X ) AND P ) OR ( X AND Q )

Using two auxiliary functions A and B, defined by A = ( NOT X ) AND P and B = X AND Q gives F = A OR B

Thus we have expressed F as a composition of functions of two arguments, and the sub-functions P and Q.

Completing the Simplification

We have shown that a function F of n arguments can be expressed as a composition of functions of two arguments, and the sub-functions P and Q, which have n-1 arguments only.

But the procedure used can also be applied to the sub-functions, each time reducing the number of arguments in the new sub-functions which are produced. Thus we must eventually reach a point where the sub-functions produced are functions of two arguments only.

All of the sub-functions produced by such repetition are combined using functions of two arguments only and hence we have shown that

All functions of more than two arguments can be expressed as compositions of functions of only two arguments.

Practical Note

The final composition of F obtained by this method may be far from optimum, in terms of the complexity of the expression which results. It is very dependent upon the order in which variables are extracted. However, the fact that this simplification is always possible is a useful guarantee for more heuristic methods.


1 Named after George Boole (1815 - 1864), an English mathematician.
2 These assumptions are not a restriction on the function, but only on the form of truth table.
3 The definition of F is not changed if the entries in its truth table are rearranged.

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: A2266760 (Edited)

Written and Researched by:
Old Hairy

Edited by:
SchrEck Inc.


Date: 26   April   2004


Text only
Like this page?
Send it to a friend


Referenced Guide Entries
Mathematics
Propositional Logic
Boolean Algebra
Algorithms
Electronic Logic Conventions
Boolean Truth Tables
Boolean Functions Classified
Universal Functions of Boolean Algebra
Boolean Expressions from Truth Tables


Related BBC Pages
BBC 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