1

Is it true or false that

the total number of boolean functions with $3$ variables is $255$?

${2^2}^3$ is $256$ so this statement is false.

user91500
  • 5,606
Kevin
  • 35

1 Answers1

2

$2^{2^3} = 256$.

You can work up to it by considering Boolean functions $\mathbb{B}^n \rightarrow \mathbb{B}$ for smaller values of $n$ first and looking at enumerating possible truth tables.

How many Boolean functions $\mathbb{B} \rightarrow \mathbb{B}$?

Think of the truth table for such a function. The possible inputs which the function must be defined for are:

input_1 | output
--------|-------
 true   |
 false  |

and so to enumerate all the functions defined on this domain, we must find all possible ways of filling out the right-hand column with trues and falses. There are $2^1$ places to fill, and there are $2^{(2^1)} = 4$ lists of length $2$ containing true and false. So there are $4$ possible unary Boolean functions.

Incidentally, these $4$ functions are: identity, not, always-true, always-false.

How many boolean functions $\mathbb{B}^2 \rightarrow \mathbb{B}$? These are the familiar binary operators like and, or and xor. The truth table to fill is:

input_1 | input_2 | output
--------|---------|-------
 true   | true    |
 true   | false   |
 false  | true    |
 false  | false   |

There are $2^2$ places to fill, and there are $2^{(2^2)} = 2^4 = 16$ lists of length $2^2$ containing true and false. So there are 16 possible binary Boolean functions.

How many boolean functions $\mathbb{B}^3 \rightarrow \mathbb{B}$? These are what you asked about. The truth table to fill is:

input_1 | input_2 | input_3 | output
------------------------------------
true    | true    | true    | 
true    | true    | false   |
true    | false   | true    |
true    | false   | false   |
false   | true    | true    |
false   | true    | false   |
false   | false   | true    |
false   | false   | false   |

There are $2^3$ places to fill and $2^{(2^3)} = 2^8 = 256$ ways to do it. So there are $256$ ternary Boolean functions.

Of course, following this pattern, in general there are $2^{(2^n)}$ possible $n$-ary Boolean functions.

Cai
  • 145