Boolean Functions Classified
Created  Updated Jul 9, 2013
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^{2} = 4 argument combinations, since each argument may be either true or false. When there are four argument combinations, there are 2^{4} = 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 halfadd 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