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 2² = 4 argument combinations, since each argument may be either true or false. When there are four argument combinations, there are 2⁴ = 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.

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