Demorgan laws ?

[tron87]

Can someone plz give us some pointers on where to start with this ?

Use DeMorgan laws to show that the NAND circuit ("logic.jpg") on the left is equivalent to the AND_OR circuit("logic2.jpg") on the right?



thx

 

[MrAl]

Hi,

If you take a logic element and invert all of the inputs and outputs then the logical connective is the invert of the original too.

In the following truth tables in each row the first number is the first input, the second number is the second input, and the last number is the output.

Start with a NAND gate:
001
011
101
110

invert all inputs and the output:
110
100
010
001

and we ended up with a NOR gate.

Of course if we started with a NOR gate we would have ended up with a NAND gate.

You use this idea to show that one circuit is equivalent (or not) to another.

This is more clear schematically as shown in the attachment. Note that when we use inverters on the inputs and outputs of the AND gate we get the OR function.

 

[tron87]

Thx mrAl 4 reply


I have to show that its equivalent by using the technique from demorgan of breaking the bar in the algebraic expression that describes the logic circuit.How would i go about doing this also ?

 

[MrAl]

Hi,

You mean like this:

  ___
C=A*B
  _ _ _
C=A * B

C=A' + B'

The bar above the symbols (all of them including the AND symbol) is broken so that part of it covers each symbol alone. The operations due to each smaller bar are then performed one at a time.

 

[tron87]

Hi,

You mean like this:

  ___
C=A*B
  _ _ _
C=A * B

C=A' + B'

The bar above the symbols (all of them including the AND symbol) is broken so that part of it covers each symbol alone. The operations due to each smaller bar are then performed one at a time.

Yes thts what i meant.

 

[tron87]

********************************************_ _* _
For the circuit with AND_OR gates i got the expression of A.C+B.C

*************************************** ______
****************************************** _
For the circuit with NAND gates i got the expression A.C+B.C



What steps are required to reduce the second expression to match the first expression to show the two circuits are equivalent ?

 

[MrAl]

Hi again,


If you use "code" wraps you can write out the logic statements so that they can be read more easily.
Your first expression came out to:

  _ _   _
  A*C+B*C

which can also be written as:

  _  _
  C*(A+B)

What you need to do is go over the NAND circuit again because your expression for that circuit does not look correct. When you get the correct expression from this particular circuit it should be the exact same as the AND OR circuit.

However, with Demorgan in mind what we can do is redraw the NAND circuit using INVERTERS and AND gates rather than NAND gates. The final NAND gate (on the far right) is thus turned into an AND gate with inverters on the input and on the output, and the two other NAND gates are turned into just AND gates. Then looking at the final AND gate with both it's inputs and it's outputs inverted, we can then draw it as an OR gate with no inverters. This makes the circuit look *exactly* like the circuit with the AND and OR gates, and this happens without doing any math at all. This is really the essence of using Demorgan rather than simply Boolean Algebra, but the Boolean Algebra simplifies too this way as expected through Demorgan.
We can draw that final AND gate (with inverters on it's inputs and output) as an OR gate because of Demorgan's which in other words states that:
"If we invert all inputs and outputs we can invert the logical connective and remove all inverters".
Since the final AND gate has all it's inputs and outputs inverted, we can remove all of the inverters and change the gate to an OR gate because the invert of an AND gate is an OR gate. That's the beauty of Demorgan.