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

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

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}}}}$$

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

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 /> x+y = \overline{\overline{x}\bullet\overline{y}}<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]

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

Which is the same as

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

 

[LCKurtz]

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

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

Which is the same as

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

 

[thomas49th]

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

I think so

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

is the same as

$$<br /> (A+B) + (C + D) = n(\overline{n(\overline{A},\overline{B}}),\overline {n(\overline{C},\overline{D}})<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 /> (A+B) + (C + D) = n(\overline{n(\overline{A},\overline{B}}),\overline {n(\overline{C},\overline{D}})<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.