**Boolean functions**, sometimes also called switching functions, are functions that take as their input zero or more boolean values (1 or 0, true or false, etc.) and output a single boolean value. The number of inputs to the function is is called the arity of the function and is denoted as *k*. Every *k*-ary function can be written as a propositional formula, a sentence in propositional logic. A binary Boolean function, a Boolean function with two arguments, can be described by one out of sixteen canonical formulas.

## Binary Boolean Functions

Consider a function that has two binary-valued inputs and outputs a binary value. Two inputs that can each take on one of two values, 0 or 1, means that there are possible combinations of input values.

x | y |
---|---|

0 | 0 |

0 | 1 |

1 | 0 |

1 | 1 |

A common way to illustrate binary Boolean functions is with a **truth table**, a table that enumerates over every possible input combination and it’s output. For example the truth table for function that applies the Boolean operator *And*, denoted with the propositional logic symbol ∧, to its two inputs looks like:

x | y | x ∧ y |
---|---|---|

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

Other functions will have different output values in the last column for the respective inputs. Considering that there are 4 possible output values, one for each of the input combinations, this means that there are , or 16, possible combinations of output values, ie., for a pair of binary inputs there are exactly 16 possible Boolean functions that can be applied to them. These are called *canonical functions*, because any binary Boolean function can be reduced to one of these 16 forms. In general, for *k* inputs, there are canonical Boolean functions.

The table below lists the 16 canonical binary Boolean functions:

x, y | |||||
---|---|---|---|---|---|

Boolean Function | Proposition | 0, 0 | 0, 1 | 1, 0 | 1, 1 |

Constant 0 | 0 | 0 | 0 | 0 | 0 |

And | x ∧ y | 0 | 0 | 0 | 1 |

x And Not y | x ∧ ¬y | 0 | 0 | 1 | 0 |

x | x | 0 | 0 | 1 | 1 |

Not x And y | ¬x ∧ y | 0 | 1 | 0 | 0 |

y | y | 0 | 1 | 0 | 1 |

Xor | (x ∧ ¬y) ∨ (¬x ∧ y) | 0 | 1 | 1 | 0 |

Or | x ∨ y | 0 | 1 | 1 | 1 |

Nor | ¬(x ∨ y) | 1 | 0 | 0 | 0 |

Equivalence | (x ∧ y) ∨ (¬x ∧ ¬y) | 1 | 0 | 0 | 1 |

Not y | ¬y | 1 | 0 | 1 | 0 |

y Implies x (if y then x) | y ⇒ x ⇔ x ∨ ¬y | 1 | 0 | 1 | 1 |

Not x | ¬x | 1 | 1 | 0 | 0 |

x Implies y (if x then y) | x ⇒ y ⇔ ¬x ∨ y | 1 | 1 | 0 | 1 |

Nand | ¬(x ∨ y) | 1 | 1 | 1 | 0 |

Constant 1 | 1 | 1 | 1 | 1 | 1 |

Two of the functions above, Nor and Nand, are very special in that either one of them alone can be used to define the other fifteen functions. That, however, is a story for another post.