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: Q29E (page 842)

Build a circuit using \(OR\) gates, \(AND\) gates, and inverters that produces an output of \({\bf{1}}\) if a decimal digit, encoded using a binary coded decimal expansion, is divisible by \(3\), and an output of \(0\) otherwise.

Short Answer

Expert verified

The Minimal expansion is \({\bf{wz + \bar xyz + xy\bar z + \bar w\bar x\bar y\bar z}}\)

Step by step solution

01

Definition

The complement is represented by an inverter in a circuit.

The Boolean sum is represented by an \(OR\) gate in a circuit.

The Boolean product is represented by an \(AND\) gate in a circuit.

The complement of an element: \({\bf{\bar 0 = 1}}\) and \({\bf{\bar 1 = 0}}\)

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

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

02

Mapping

A \(K{\bf{ - }}\)map for a function in four variables is a table with four columns \(yz,y\bar z,\bar y\bar z\) and \(\bar yz\); which contains all possible combinations of \(y\) and \(z\) and four rows \(wx,w\bar x,\bar w\bar x\) and \(\bar wx\); which contains all possible combinations of \(w\) and \(x\).

We place a \(d\) in the first row and in the first two cells of the second row of the \(K{\bf{ - }}\)map.

The input will be divisible by \(3\) if the digit is \({\bf{0}}\)(\(0000\) or equivalently \(\bar w\bar x\bar y\bar z\)), \(3\)(\(0011\) or equivalently \(\bar w\bar xyz\)), \(6\)(\(0110\) or equivalently \(\bar wxy\bar z\)), \(9\)(\(1001\) or equivalently \(w\bar x\bar yz\)), \(12\)(\(1100\) or equivalently \(wx\bar y\bar z\)) or \(15\)(\(1111\) or equivalently \(wxyz\)).

Place a \(1\) in the cells of the \(K{\bf{ - }}\)map for the numbers divisible by \(3\) (and that don't contain a \(d\)).

03

Minimal expansion

\(\bar w\bar x\bar y\bar z\) is isolated in the above graph, thus \(\bar w\bar x\bar y\bar z\) needs to be contained in the minimal expansion.

\(w\bar x\bar yz\)is contained in the block \(wz\) (which is the largest block containing the cell and other cells with \(1\)'s/\(d\)'s).

\(\bar w\bar xyz\)is contained in the block \(\bar xyz\) (which is the largest block containing the cell and other cells with \(1\) 's/\(d\)'s).

\(\bar wxy\bar z\)is contained in the block \(xy\bar z\) (which is the largest block containing the cell and other cells with \(1\) 's/\(d\)'s).

The Minimal expansion is the sum of the blocks.

Therefore, the Minimal expansion \({\bf{wz + \bar xyz + xy\bar z + \bar w\bar x\bar y\bar z}}\).

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

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

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

Construct circuits from inverters, AND gates, and ORgates to produce these outputs.

\(\begin{array}{l}{\bf{a)}}\overline {\bf{x}} {\bf{ + y}}\\{\bf{b)}}\overline {{\bf{(x + y)}}} {\bf{x}}\\{\bf{c)xyz + }}\overline {\bf{x}} \overline {\bf{y}} \overline {\bf{z}} \\{\bf{d)}}\overline {{\bf{(}}\overline {\bf{x}} {\bf{ + z)(y + }}\overline {\bf{z}} {\bf{)}}} \end{array}\)

Explain how to build a circuit for a light controlled by two switches using \({\bf{OR}}\) gates, \({\bf{AND}}\) gates, and inverters.

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

Draw the \({\bf{3}}\)-cube \({{\bf{Q}}_{\bf{3}}}\) and label each vertex with the minterm in the Boolean variables \({\bf{x, y}}\), and \({\bf{z}}\) associated with the bit string represented by this vertex. For each literal in these variables indicate the \({\bf{2}}\)-cube \({{\bf{Q}}_{\bf{2}}}\) that is a subgraph of \({{\bf{Q}}_{\bf{3}}}\) and represents this literal.

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.
See all solutions

Recommended explanations on Math Textbooks

Statistics

Read Explanation

Calculus

Read Explanation

Theoretical and Mathematical Physics

Read Explanation

Geometry

Read Explanation

Discrete Mathematics

Read Explanation

Decision Maths

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