Question

How many of the \({\bf{1}}6\) Boolean functions in two variables \(x\) and \(y\) can be represented using only the given set of operators, variables \(x\) and \(y\), and values \(0\) and \(1\) \(?\)

\(\begin{array}{c}a)\{ {\bf{ - }}\} \\b)\{ \cdot \} \\c)\{ {\bf{ + }}\} \\d)\{ \cdot ,{\bf{ + }}\} \end{array}\)

The notation for an \(XOR\) gate, which produces the output \(x \oplus y\) from \(x\) and \(y\), is as follows:

Short answer

\(a)\)The answer is \(6\).

\(b)\)The answer is \(5\).

\(c)\)The answer is \(5\).

\(d)\)The answer is \(6\).

Step-by-step solution

Definition

Let \({\bf{B = }}\left\{ {{\bf{0,1}}} \right\}\). Then \({{\bf{B}}^{\bf{n}}}{\bf{ = }}\left\{ {\left( {{{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right)\mid {{\bf{x}}_{\bf{i}}} \in {\bf{B}}} \right.\)for \(\left. {1 \le {\bf{i}} \le {\bf{n}}} \right\}\) is the set of all possible \({\bf{n}}\)-tuples of \({\bf{0's}}\) and \({\bf{1's}}\). The variable \({\bf{x}}\) is called a Boolean variable if it assumes values only from \({\bf{B}}\), that is, if its only possible values are \(0\) and \(1\). A function from \({{\bf{B}}^{\bf{n}}}\) to \({\bf{B}}\) is a Boolean function and it has degree \({\bf{n}}\).

Using the complementation

(a)

In each case it can actually list all the functions.

The only function values can get \(x,y,0,1,\bar x\), and \(\bar y\), since applying complementation twice does not give anything new.

Therefore, the answer is \(6\).

Finding the function

(b)

Since \(s \cdot s = s\), \(s \cdot 1 = s\), and \(s \cdot 0 = 0\) for all \(s\), the only functions can get \(x,y,0,1\), and \(xy\).

Therefore, the answer is \(5\).

Using the duality

c)

By duality the answer here has to be the same as the answer to part \((b)\), namely \(5\).

Therefore, the answer is \(5\).

Finding the distinct function

(d)

There are \(6\) distinct functions \(x,y,0,1,xy\) and \(x{\bf{ + }}y\). Any further applications of these operations, however, returns to one of these functions. For example, \(xy{\bf{ + }}x{\bf{ = }}x\)

Therefore, the answer is \(6\).