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

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


This entry is chiefly intended to be a reference for other entries. It enumerates all Boolean functions of two arguments or less. The functions are all named, and they are classified in various ways. Every reference to a function is capitalised. (This makes text uglier, but function names which are common English words must be distinguished. Otherwise, the words AND, OR and NOT in particular become ambiguous.)

Boolean Functions of Two Variables

When there are two arguments, there are 22 = 4 argument combinations, since each argument may be either true or false. When there are four argument combinations, there are 24 = 16 possible sets of function values. All these functions are tabulated below, in terms of arguments A and B, with true and false shown as T and F respectively. Each function has been given a number, obtained (in binary) from its truth table values, defining true as 1 and false as 0.

Arguments
AB
FF
FT
TF
TT
 
Function Values (16 different functions, numbered 0 to 15)
0123456789101112131415
FFFFFFFFTTTTTTTT
FFFFTTTTFFFFTTTT
FFTTFFTTFFTTFFTT
FTFTFTFTFTFTFTFT

Every function has a name, although some names are not well known, and rarely used. The names are given below, in order of the function number assigned to the truth table.

  0: FALSE function, logical constant, degenerate function with no arguments
  1: AND function, A and B
  2: INHIBIT function, A and not B, that is, A unless inhibited (made false) by B
  3: IDENTITY function, A, degenerate function of A only
  4: INHIBIT function, B and not A, that is, B unless inhibited (made false) by A
  5: IDENTITY function, B, degenerate function of B only
  6: XOR function, A xor B, full name EXCLUSIVE OR to signify A or B but not both
  7: OR function, A or B, sometimes called INCLUSIVE OR to signify A or B or both
  8: NOR function, not ( A or B )
  9: EQUIVALENCE function, A ≡ B, true when A and B are the same (both true or both false)
10: NOT function, not B, degenerate function of B only
11: IMPLICATION function, B implies A, false if B is true but A is false
12: NOT function, not A, degenerate function of A only
13: IMPLICATION function, A implies B, false if A is true but B is false
14: NAND function, not ( A and B )
15: TRUE function, logical constant, degenerate function with no arguments

Alternative names

Some of these functions have alternative names which may be encountered.

  • The NOT function applied to an argument is often referred to as giving the inverse or complement of that argument, but the use of these names as functions is less common.
  • The AND function of any number of arguments is also known as the logical intersection of those arguments, or their conjunction, or their logical product.
  • The OR function of any number of arguments is also known as the logical union of those arguments, or their disjunction, or their logical sum. It is also sometimes called the inclusive disjunction.
  • The EQUIVALENCE function is also commonly known as the XNOR function. This is a contraction of exclusive NOR, intending to signify the function NOT ( A or B but not both ).
  • The XOR function is also called a half-add in the context of binary arithmetic, and sometimes the exclusive disjunction.
  • The NAND function is sometimes known as the Sheffer stroke function (and is then denoted by a vertical bar operator).
  • The NOR function is sometimes known as the Pierce function (and is then denoted by a downwards arrow operator).

Degenerate Functions

Some of these functions are degenerate, that is, they are functions of less than two arguments. The degenerate functions fall into two classes, according to the number of required arguments

  • The FALSE and TRUE functions are merely logical constants, and not functions of any argument.
  • The IDENTITY and NOT functions have one argument. Reference to another argument is superfluous.

Symmetric Functions

A function of any number of arguments, whose value is unchanged by permutation of its arguments, is known as a symmetric function. All functions of less than two arguments are (trivially) symmetric. For functions of two arguments, the only permutations of the arguments are interchanges of one another.

All the functions of two arguments are symmetric, except for the INHIBIT and IMPLICATION functions, which therefore appear twice in the table. (The IDENTITY and NOT functions also appear twice, but because they are functions of a single argument, and there are two arguments in the table.)

Reflexive Pairings

Let F ( A, B ) denote that F is a function of arguments A and B. If a function F ( A, B ) is associated with another function G ( A, B ), and G ( A, B ) is similarly associated with F ( A, B ), the association is said to be reflexive. There are two reflexive pairings, functions which are complements of each other, and functions which are duals of each other.

If G ( A, B ) = NOT F ( A, B ) for all values of the arguments, the functions F and G are complements of each other. When G ( A, B ) = NOT F ( A, B ) then NOT G ( A, B ) = F ( A, B ), so that F ( A, B ) = NOT G ( A, B ), and thus the association is reflexive. These pairings are

  • NAND complements AND
  • NOR complements OR
  • XOR complements EQUIVALENCE
  • IMPLICATION complements INHIBIT, that is, A implies B is the logical complement of A inhibited by B

If G ( A, B ) = NOT F ( NOT A, NOT B ) for all values of the arguments, the functions F and G are duals of each other. When G ( A, B ) = NOT F ( NOT A, NOT B ) then G ( NOT A, NOT B ) = NOT F ( A, B ) and then NOT G ( NOT A, NOT B ) = F ( A, B ) so that F ( A, B ) = NOT G ( NOT A, NOT B ), and thus the association is reflexive. These pairings are

  • AND duals OR
  • NAND duals NOR
  • XOR duals EQUIVALENCE
  • IMPLICATION duals INHIBIT, that is, A implies B is the logical dual of B inhibited by A


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

Written and Researched by:
Old Hairy

Edited by:
Mikeo the gregarious


Date: 15   March   2004


Text only
Like this page?
Send it to a friend


Referenced Guide Entries
Boolean Algebra
Boolean Truth Tables
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