Question

Show that the set of operators \(\left\{ {{\bf{ + , \cdot}}} \right\}\) is not functionally complete.

Short answer

Therefore, the set of operators \(\left\{ {{\bf{ + , \cdot}}} \right\}\) is not functionally complete.

Step-by-step solution

Definition.

The complements of an elements \(\overline {\bf{0}} {\bf{ = 1}}\) and \(\overline {\bf{1}} {\bf{ = 0}}\).

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

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

For the solution use the concept of \(\left( {{\bf{ + , }}{\bf{.}}} \right)\) Operation.

Show the result by an example.

Let’s consider an example for the result.

By the De Morgan law

\({\bf{x + y = }}\overline{\overline {{\bf{xy}}}} \)

This operation \({\bf{ + }}\) is replaced by dot \(\left( {\bf{.}} \right)\) and a complementation.

This set is functionally complete.

Similarly, \(\overline {\bf{x}} {\bf{ + }}\overline {\bf{y}} {\bf{ = }}\overline {{\bf{x}}{\bf{.y}}} {\bf{ = }}\overline {\overline {\bf{x}} {\bf{ + }}\overline {\bf{y}} } {\bf{ = x}}{\bf{.y}}\).

This se is functionally complete.

But there is no rule which directly takes \({\bf{ + }}\) to.or vice versa without the support of the complementation. So \(\left( {{\bf{ + , }}{\bf{.}}} \right)\) is a set which is not functionally complete.

Therefore, the set of operators \(\left\{ {{\bf{ + , \cdot}}} \right\}\) is not functionally complete.