World's most popular travel blog for travel bloggers.

# All output functions of a truth table

, ,
Problem Detail:

I can name one more: XNOR. But besides these, what other output functions are there?

###### Answered By : Lieuwe Vinkhuijzen

Suppose you try to come up with a new output function, which you call $A\otimes B$, with new, custom behaviour. You will have to come up with four values: $0\otimes 0, 0 \otimes 1, 1 \otimes 0, 1 \otimes 1$. One arbitrary example is: $0\otimes 0 = 0, 0 \otimes 1 = 1, 1 \otimes 0 = 0, 1 \otimes 1 = 0$. Any sequence of zeroes and ones will do (this is the answer to your question). So you can write a string of four zeroes or ones, and that will represent your function. For example, my function is represented with $0100$. How many such strings are there? Well, try enumerating them: $0000,0001,0010,0011,\ldots$ Hence the remark that there are $2^{4}=16$ possible functions.

Not all of these functions are equally useful. The example I gave is equivalent to $A\otimes B = \neg A \wedge B$. In fact, every (binary) output function can be written as a combination of the three functions $\neg, \wedge, \vee$, i.e. NOT, OR and AND.

Consider functions that use three arguments, $A,B,C$. The truth table of such a function has $8$ entries, so there are a total of $2^{8}=256$ functions on three variables. Can you find a formula for the number of functions on $n$ variables? The example functions in your excerpt are all examples of commutative functions, which are functions $\circ$ where $A\circ B = B \circ A$ for every value of $A$ and $B$. Can you think of a noncommutative function?