Question

Are these sets of operators functionally complete?

a) \(\left\{ {{\bf{ + ,}} \oplus } \right\}\)

b) \(\left\{ {\,{\bf{,}} \oplus } \right\}\)

c) \({\bf{\{ \cdot,}} \oplus {\bf{\} }}\)

Short answer

(a) \(\left\{ { + , \oplus } \right\}\)is not functionally complete.

(b)\(\left\{ {\,, \oplus } \right\}\)is not functionally complete.

(c)\(\left\{ {\cdot, \oplus } \right\}\)is not functionally complete.

Step-by-step solution

Definition

The complements of elements \(\overline 0 = 1\) and\(\overline 1 = 0\).

The Boolean sum \( + \) or OR is 1 if either term is 1.

The Boolean product \(\left( {\bf{.}} \right)\) or AND is 1 if both terms are 1.

The NAND operator | is 1 if either term is 0.

The NOR operator\( \downarrow \)is 1 if both terms are 0.

\({\bf{x}} \oplus {\bf{y}}\) if and only if exactly one of the two terms is equal to 1.

First the solution of\(\left\{ {{\bf{ + ,}} \oplus } \right\}\).

(a)

Now first consider the set\(\left\{ { + , \oplus } \right\}\).

Here\(0 \oplus 0 = 0 = 0 + 0\). This then implies that every function uses only the operation\( + \) and \( \oplus \) will 0 as output when all inputs are 0.

However, it is then not possible to construct a function that has only 0’s as input and 1 as output. Thus, such functions cannot be written using only the operation \( + \)and\( \oplus \), which means the set \(\left\{ { + , \oplus } \right\}\) is not functionally complete.

Evaluate the\(\left\{ {\,{\bf{,}} \oplus } \right\}\).

(b)

Consider the set\(\left\{ {\,, \oplus } \right\}\).

Here\(\overline {\left( {x \oplus y} \right)} = \overline x \oplus y,\,\,x \oplus x = 0,\,\,x \oplus \overline x = 1,\,\,x \oplus 1 = \overline x ,\,\,x \oplus x = x\).

However, it is not possible to express \(x + y\) in terms of \( - \) and\( \oplus \), which means that \(\left\{ {\,, \oplus } \right\}\) is not functionally complete.

determine the result of\({\bf{\{ \cdot,}} \oplus {\bf{\} }}\).

(c)

Consider the set\(\left\{ {\cdot, \oplus } \right\}\).

Here\(0.0 = 0 = 0 \oplus 0\). This implies that every function uses only the operation (.) and \( \oplus \) as output when all input is 0.

However, it is then not possible to construct a function that has only 0’s as input and 1 as output. Thus, such functions cannot be written using only the operation (.) and\( \oplus \), which means the set \(\left\{ {\cdot, \oplus } \right\}\) is not functionally complete.

Therefore, parts a, b, and c are not functionally complete sets.