(A+B).(A+C) with 3 NANDS and 2 INVERTERS?

[cae27]

Hi,

I'm just getting to grips with boolean algebra and I've found a
problem I can't solve. I'm told I should be able to use Demorgan's
theorem to convert (A+B).(A+C) into a form using 3 NAND gates and 2
INVERTERS, but I can't seem to manage it! I should say that this is
quite new to me so if anyone here can point me in the right direction
I'd appreciate it, thanks.

Chris.

 

[Jonathan Kirwan]

On 15 Nov 2004 14:04:35 -0800, limewolf@gmail.com (cae27) wrote:

I'm just getting to grips with boolean algebra and I've found a
problem I can't solve. I'm told I should be able to use Demorgan's
theorem to convert (A+B).(A+C) into a form using 3 NAND gates and 2
INVERTERS, but I can't seem to manage it! I should say that this is
quite new to me so if anyone here can point me in the right direction
I'd appreciate it, thanks.

Does it have to be (3) NANDs and (2) inverters? Is it okay to use (2) NANDs and
(1) inverter? (Could use the full complement, but it's not necessary.)

I'll use / to indicate NOT, + for OR and * for AND:

(a + b) * (a + c)

= a * (a + c) + b * (a + c)
= a*a + a*c + b*a + b*c
= a*a + a*c + a*b + b*c
= a*(a + c + b) + b*c
= a*(1 + c + b) + b*c
= a*(1) + b*c
= a + b*c

Once this is arrived at, try a double NOT to convert the + to an *:

= //(a + b*C)
= / ( /a * /(b*c) )

Rewrite this in function form:

= /*( /a, /*(b, c) )

So:

c -----|\
| >o----|\
b -----|/ | >o---->
,----|/
a --|>o---'

For three NANDs and two inverters (if you just have to have the exact number)
you could just slap them on, like:

c -----|\
| >o----|\ ,--|\
b -----|/ | >o---+ | >o---|>o---->
,----|/ '--|/
a --|>o---'

Or you could take a different route:

(a + b) * (a + c)

= / ( / ( (a + b) * (a + c) ) )
= / ( ( /(a + b) + /(a + c) ) )
= / ( ( (/a * /b) + (/a * /c) ) )
= / ( (/a * /b) + (/a * /c) )
= /(/a * /b) * /(/a * /c)
= /*(/a,/b) * /*(/a,/c)

And wind up with something like this:

b --|>o----|\
| >o--,
,-|/ |
| '-|\
a --|>o--+ | >o---|>o---->
| ,-|/
'-|\ |
| >o--'
c --|>o----|/

Of course, that's (3) NANDs and (4) inverters.

Jon

 

[Jonathan Kirwan]

On Tue, 16 Nov 2004 01:04:23 GMT, Jonathan Kirwan <jkirwan@easystreet.com>
wrote:

= / ( / ( (a + b) * (a + c) ) )
= / ( ( /(a + b) + /(a + c) ) )
= / ( ( (/a * /b) + (/a * /c) ) )
= / ( (/a * /b) + (/a * /c) )
= /(/a * /b) * /(/a * /c)
= /*(/a,/b) * /*(/a,/c)

Oh, cripes, I left out, in function form:

= *( /*(/a,/b), /*(/a,/c) )
= / ( /*( /*(/a,/b), /*(/a,/c) ) )

And that matches the last diagram I drew.

Whew!

Jon

 

[Jonathan Kirwan]

On Tue, 16 Nov 2004 05:52:18 GMT, Rich Grise <rich@example.net> wrote:

I was gonna start in on you about not giving kids their homework answers,
but this is a howler! Good Job!

OP did say that they'd been working on it and posted in frustration. Also, I
usually don't try and provide something that is "bookish" but uses my own way of
looking at it so they have to stretch a little to get there. If they do, that's
fine. (Boolean 'algebra' has a lot of similarities with conventional algebra
taught for finite real numbers. Even the words or phrases, like factor and
term, come from traditional algebraic usage. De Morgan's is just a unary
inversion operator and rules for its distribution, I think.)

Jon

 

[cae27]

Rich Grise <rich@example.net> wrote in message news:<pan.2004.11.16.04.56.35.416560@example.net>...

I was gonna start in on you about not giving kids their homework answers,
but this is a howler! Good Job!

Well to be honest it's homework I've set myself, I'm a Physics/Biology
graduate that find himself in an electrical engineering department
(and hence involved at some level in electronics, not something I've
done much of).

Cheers,

limewolf.

 

[cae27]

Jonathan Kirwan <jkirwan@easystreet.com> wrote in message news:<27ejp09756pj7gfint5nnvd9f5de728dgh@4ax.com>...

On Tue, 16 Nov 2004 05:52:18 GMT, Rich Grise <rich@example.net> wrote:

I was gonna start in on you about not giving kids their homework answers,
but this is a howler! Good Job!

OP did say that they'd been working on it and posted in frustration.

Well, i did post only after trying myself, it's easy when you have
seen it - thanks for your post it's cleared up my confusion. I think
most of the problem is down to me not having done anything like this
for far too long .

Thank again,

limewolf.

 

[Rich Grise]

On Tue, 16 Nov 2004 15:20:42 -0800, cae27 wrote:

Rich Grise <rich@example.net> wrote in message news:<pan.2004.11.16.04.56.35.416560@example.net>...

I was gonna start in on you about not giving kids their homework answers,
but this is a howler! Good Job!

Well to be honest it's homework I've set myself, I'm a Physics/Biology
graduate that find himself in an electrical engineering department
(and hence involved at some level in electronics, not something I've
done much of).

OK, fair enough.

I hope that the rest of my answer was useful for you, because it
_was_ real, you know.

Thanks,
Rich

 

[Jonathan Kirwan]

On 16 Nov 2004 15:25:47 -0800, limewolf@gmail.com (cae27) wrote:

Well, i did post only after trying myself, it's easy when you have
seen it - thanks for your post it's cleared up my confusion. I think
most of the problem is down to me not having done anything like this
for far too long .

hehe. Actually, it's really not too hard and lots of fun once you've learned a
couple of things. Simple things like the fact that both AND and OR are
commutative and associative, of course. You can re-derive the rest whenever you
need it.

Some things are only slightly sneaky to remember, like:

(a*/b) + b = a + b
(a*b) + /b = a + /b

And keep in mind that 'b' can be some arbitrary factor or term -- it doesn't
have to be just 'b'. So:

a*c + a*/b + b*/c = a + b*/c

You can see this, if it's not already obvious, from:

a*c + a*/b + b*/c = a + b*/c
a*(c + /b) + b*/c = a + b*/c
a*(/b + c) + b*/c = a + b*/c
a*//(/b + c) + b*/c = a + b*/c
a*/(b*/c) + b*/c = a + b*/c

then set d= b*/c, giving:

a*/(d) + d = a + d
a*/d + d = a + d

which matches up from earlier.

Just stick a few things in mind. The rest is just game playing!

Jon

 

[Rich Grise]

On Tue, 16 Nov 2004 01:04:23 +0000, Jonathan Kirwan wrote:

On 15 Nov 2004 14:04:35 -0800, limewolf@gmail.com (cae27) wrote:

I'm just getting to grips with boolean algebra and I've found a
problem I can't solve. I'm told I should be able to use Demorgan's
theorem to convert (A+B).(A+C) into a form using 3 NAND gates and 2
INVERTERS, but I can't seem to manage it! I should say that this is
quite new to me so if anyone here can point me in the right direction
I'd appreciate it, thanks.

Does it have to be (3) NANDs and (2) inverters? Is it okay to use (2) NANDs and
(1) inverter? (Could use the full complement, but it's not necessary.)

I'll use / to indicate NOT, + for OR and * for AND:

(a + b) * (a + c)

= a * (a + c) + b * (a + c)
= a*a + a*c + b*a + b*c
= a*a + a*c + a*b + b*c
= a*(a + c + b) + b*c
= a*(1 + c + b) + b*c
= a*(1) + b*c
= a + b*c

I was gonna start in on you about not giving kids their homework answers,
but this is a howler! Good Job!

The first thing I notice about your example is that you're apparently
using a different part of DeMorgan's stuff than I thought I knew.

(a + b) - I'd start with this. I'm trying to derive something
using NANDs, using DeMorgan's Theorem. So I dredge the ol' memory-
pits, and come up with:

a + b = /(/a . /b)
lessee...
a b a+b /a /b y=/a./b /y
0 0 0 1 1 1 0
0 1 1 1 0 0 1
1 0 1 0 1 0 1
1 1 1 0 0 0 1

Yeah, I guess that's it.

The rest, of course, is left as an exercise for the reader. [Gawd!!
I _*LOVE*_ saying that!!!!!]


Rich