Question

How many Boolean functions of degree two are there\({\bf{?}}\)

Short answer

There are \(16\) possible Boolean functions.

Step-by-step solution

Definition

Product rule: If one event can occur in \(m\) ways and a second event can occur in \(n\) ways, then the number of ways that the two events can occur in sequence is then \(m \cdot n\).

Using the product rule

A Boolean function of degree \(n\) is a function from \({B_n}{\bf{ = }}\left\{ {\left( {{x_1},{x_2}, \ldots ,{x_n}} \right)\mid {x_i} \in B} \right\}\) to \({\bf{B = }}\left\{ {{\bf{0,1}}} \right\}\).

In this case, when interested in Boolean functions of degree \(2\). Let \(x\) and \(y\) be the two variables, then \(x\) and \(y\) can both take on the value \(0\) or \(1\), which results in a total of \(2 \cdot 2{\bf{ = }}4\) possible values for \((x,y)\) The \(4\) possible values are \((0,0),(0,1),(1,0),(1,1)\).

The Boolean function \(F\) can take on the value \(0\) or \(1\) for each input \((x,y)\), thus there are \(2\) possible values for each of the \(4\) values of \((x,y)\). By the product rule:

\(\begin{array}{c}\underbrace 2_{(x,{\bf{y) = (}}0,0)} \cdot \underbrace 2_{(x,{\bf{y) = (0}},1)} \cdot \underbrace 2_{(x,y{\bf{) = (1}},0)} \cdot \underbrace 2_{(x,{\bf{y) = (1}},1)}{\bf{ = }}{{\bf{2}}^{\bf{4}}}\\{\bf{ = }}16\end{array}\)

Therefore, there are \(16\) possible Boolean functions.