Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 12: Q20E (page 822)

Are these sets of operators functionally complete?

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

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

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

Short Answer

Expert verified

(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

Achieve better grades quicker with Premium

  • Unlimited AI interaction
  • Study offline
  • Say goodbye to ads
  • Export flashcards
Start your free trial Skip

Over 22 million students worldwide already upgrade their learning with Vaia!

01

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.

02

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.

03

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.

04

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.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Find the values, if any, of the Boolean variable \({\bf{x}}\) that satisfy these equations.

\({\bf{a)}}\)\({\bf{x}} \cdot {\bf{1 = 0}}\)

\({\bf{b)}}\)\({\bf{x + x = 0}}\)

\({\bf{c)}}\)\({\bf{x}} \cdot {\bf{1 = x}}\)

\({\bf{d)}}\)\({\bf{x}} \cdot {\bf{\bar x = 1}}\)

Construct a multiplexer using AND gates, OR gates, andinverters that has as input the four bits\({{\bf{x}}_{\bf{o}}}{\bf{,}}{{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{,}}{{\bf{x}}_{\bf{3}}}\)and the two control bits\({{\bf{c}}_{\bf{o}}}\)and\({{\bf{c}}_{\bf{1}}}\). Set up the circuit so that\({{\bf{x}}_{\bf{i}}}\)is the output, where iis the value of the two-bit integer\({{\bf{(}}{{\bf{c}}_{\bf{1}}}{{\bf{c}}_{\bf{o}}}{\bf{)}}_{\bf{2}}}\).The depthof a combinatorial circuit can be defined by specifyingthat the depth of the initial input is 0 and if a gate has ndifferent inputs at depths\({{\bf{d}}_{\bf{1}}}{\bf{,}}{{\bf{d}}_{\bf{2}}}{\bf{,}}.....{\bf{,}}{{\bf{d}}_{\bf{n}}}\),respectively, then its outputs have depth equal to max\({\bf{(}}{{\bf{d}}_{\bf{1}}}{\bf{,}}{{\bf{d}}_{\bf{2}}}{\bf{,}}.....{\bf{,}}{{\bf{d}}_{\bf{n}}}{\bf{) + 1}}\); this value is also defined to be the depth of the gate. The depth of a combinatorial circuit is the maximum depth of the gates in the circuit.

How many cells in a \({\bf{K}}\)-map for Boolean functions with six variables are needed to represent \({{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{\bar x}}_{\bf{1}}}{{\bf{x}}_{\bf{6}}}{\bf{, }}{{\bf{\bar x}}_{\bf{1}}}{{\bf{x}}_{\bf{2}}}{{\bf{\bar x}}_{\bf{6}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{{\bf{x}}_{\bf{3}}}{{\bf{x}}_{\bf{4}}}{{\bf{x}}_{\bf{5}}}\), and \({{\bf{x}}_{\bf{1}}}{{\bf{\bar x}}_{\bf{2}}}{{\bf{x}}_{\bf{4}}}{{\bf{\bar x}}_{\bf{5}}}\), respectively\({\bf{?}}\)

Draw the Hasse diagram for the poset consisting of the set of the \({\bf{16}}\)Boolean functions of degree two (shown in Table \({\bf{3}}\) of Section \({\bf{12}}{\bf{.1}}\)) with the partial ordering \( \le \).

Find the sum-of-products expansion of the Boolean function F (\({{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{,}}{{\bf{x}}_{\bf{3}}}{\bf{,}}{{\bf{x}}_{\bf{4}}}{\bf{,}}{{\bf{x}}_{\bf{5}}}\)) that has the value 1 if and only if three or more of the variables \({{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{,}}{{\bf{x}}_{\bf{3}}}{\bf{,}}{{\bf{x}}_{\bf{4}}}{\bf{,}}{{\bf{x}}_{\bf{5}}}\) have the value 1.
See all solutions

Recommended explanations on Math Textbooks

Theoretical and Mathematical Physics

Read Explanation

Pure Maths

Read Explanation

Calculus

Read Explanation

Discrete Mathematics

Read Explanation

Mechanics Maths

Read Explanation

Geometry

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free