Oct 122017
 

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 2^k 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 And y Truth Table
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 2^4, 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 2^2^k canonical Boolean functions.

The table below lists the 16 canonical binary Boolean functions:

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.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

(required)

(required)