Solving NAND Boolean Logic Homework w/ Q=A+B+C+D

[thomas49th]

Homework Statement

Taking the statement Q = A + B + C + D

Rewrite using only NAND (2 inp) and NOT gates

Homework Equations

Well I want to do it all in NAND gates - because we can easily tie NAND inputs to make it a NOT


\overline{AA} = \overline{A}

The Attempt at a Solution

At the moment Q is equal to true if A OR B OR C OR D is true.

I can change OR into a NAND gate quite easily.

\overline{\overline{(x+y)}} = \overline{\overline{x}\bullet\overline{y}}

which is

x+y = \overline{\overline{x}\bullet\overline{y}}

this means I obtain

\overline{\overline{A}\bullet\overline{B}\bullet\overline{C}\bullet\overline{D}}

But this has NOTs and AND logic in, not NAND. I need expressions in NAND which is \overline{AB}

Any hints?

Thanks
Thomas

 

[LCKurtz]

Start by using your identity

<br /> x+y = \overline{\overline{x}\bullet\overline{y}}<br />

on (A+B) + (C+D).

 

[thomas49th]

Still get to the same place:


(A+B)+(C+D)

\overline{\overline{A}\bullet\overline{B}} + \overline{\overline{C}\bullet\overline{D}}

\overline{\overline{\overline{\overline{A}\bullet\overline{B}}} + \overline{\overline{\overline{C}\bullet\overline{D}}}}

<br /> \overline{\overline{A}\bullet\overline{B}\bullet\overline{C}\bullet\overline{D}}<br />

Hmmm :(

Was I meant to perform some other manipulation part way?

Thanks
Thomas :)

 

[LCKurtz]

Here's how I sometimes think of these things. Let's denote the nand function of A and B by n(A,B). So

n(A,B) = \overline{A\cdot B}

So your equation
<br /> <br /> x+y = \overline{\overline{x}\bullet\overline{y}}<br /> <br />

becomes

A + B = n(\overline A,\overline B)

or "the sum becomes the nand of the complements" (DeMorgans rule). This gives

(A+B) + (C + D) = n(\overline{A+B},\overline{C+D})

Now apply the same rule to the sums on the right side. This will leave you an expression with only nands and complements, which can be expressed with inverters.

 

[thomas49th]

<br /> (A+B) + (C + D) = n(\overline{n(\overline{A},\overline{B}}),\overline{n(\overline{C},\overline{D}})<br />

Which is the same as

<br /> \overline{\overline{\overline{\overline{A}\bullet\overline{B}}} + \overline{\overline{\overline{C}\bullet\overline{D }}}}<br />

 

[LCKurtz]

<br /> (A+B) + (C + D) = n(\overline{n(\overline{A},\overline{B}}),\overline{n(\overline{C},\overline{D}})<br />

Yes. So are we done here? Do you see how to implement it as a nand and inverter circuit?

Which is the same as

<br /> \overline{\overline{\overline{\overline{A}\bullet\overline{B}}} + \overline{\overline{\overline{C}\bullet\overline{D }}}}<br />

 

[thomas49th]

Yes. So are we done here? Do you see how to implement it as a nand and inverter circuit?

I think so

<br /> <br /> \overline{\overline{A}\bullet\overline{B} + \overline{C}\bullet\overline{D}}<br /> <br />

is the same as

<br /> <br /> (A+B) + (C + D) = n(\overline{n(\overline{A},\overline{B}}),\overline {n(\overline{C},\overline{D}})<br /> <br />

I just can't see how to get into the NAND form: \overline{A \bullet B}
instead of using the new implementation you use n(\overline{A},\overline{B}})

Thank
Thomas

 

[LCKurtz]

<br /> <br /> (A+B) + (C + D) = n(\overline{n(\overline{A},\overline{B}}),\overline {n(\overline{C},\overline{D}})<br /> <br />

I just can't see how to get into the NAND form: \overline{A \bullet B}

Thank
Thomas

I think all the overlines get very confusing. But you can use that n form to immediately draw a nand and inverter circuit. The outside n gives you the nand of two things. What two things? The invert of the two inside nands. So I would start by drawing the output nand gate with inverters at its two inputs. What is on the inputs of these inverters? The inside nands. So put a nand in front of each inverter with their inputs which are the inverted A,B,C, and D inputs.

 

[LCKurtz]

To express it as in logic notation in terms of just nands and complements, the n expression could be written like this:

\overline{\left(\overline{\left(\overline{\overline A \cdot \overline B}\right)}\right)<br /> \cdot \left(\overline{\left(\overline{\overline C \cdot \overline D}\right)}\right)}

Here the big parentheses with the complement over them represent a nand gate, and its inputs are the complments of the nand gates represented by the inner parentheses. The second level nands have the complents of A,B,C, and D for inputs.

 

[thomas49th]

\overline{\left(\overline{\left(\overline{\overline A \cdot \overline B}\right)}\right) \cdot \left(\overline{\left(\overline{\overline C \cdot \overline D}\right)}\right)}

is the same as

\overline{\overline{\overline{\overline{A}\bullet\overline{B}}} + \overline{\overline{\overline{C}\bullet\overline{D }}}}

You've just put brackets in seperating the complements that COULD cancel?

Right.
Excellent :)

 

[LCKurtz]

\overline{\left(\overline{\left(\overline{\overline A \cdot \overline B}\right)}\right) \cdot \left(\overline{\left(\overline{\overline C \cdot \overline D}\right)}\right)}

is the same as

\overline{\overline{\overline{\overline{A}\bullet\overline{B}}} + \overline{\overline{\overline{C}\bullet\overline{D }}}}

You've just put brackets in seperating the complements that COULD cancel?

Right.
Excellent :)

You don't want to cancel the complements. Your expression has a "+" in it which represents OR. It may be logically equivalent but it doesn't give a nand and inverter representation any more than A + B + C + D does.