Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2006-10-17 12:02:27

johnd29
Member
Registered: 2006-10-17
Posts: 7

Boolean algebra help

I know A + 1 = 1
but does A (negated) + 1 = 1 too?

or in any case.. would AB + 1 = 1 too?

and would AC(negated) * A(negated)C = 0?

Offline

#2 2006-10-17 12:56:42

polylog
Member
Registered: 2006-09-28
Posts: 162

Re: Boolean algebra help

I'll use "~A" to mean A negated.

We know that A + 1 = 1.

The OR operation needs *just one* of its operands to be 1 in order to evaluate to 1... so no matter what expression is "ORed" with 1 will give 1.

Therefore, ~A + 1 = 1, and AB + 1 = 1.

As for the second part:

Boolean And is commutative, so we can write:

A(~C) * (~A)(C) = A(~A) * C(~C) 

And in general, for any boolean X:  X * ~X = 0.

(ie, something can't be true AND not true at the same time!)

Therefore, A(~A) * C(~C)  = 0 * 0 = 0, as you said.

Last edited by polylog (2006-10-17 12:57:22)

Offline

#3 2006-10-17 13:25:27

johnd29
Member
Registered: 2006-10-17
Posts: 7

Re: Boolean algebra help

Wow, thanks a lot!!

Now, I'm having a bit of trouble with these three problems. I have the answers, but I can't seem to get there.

q = RST (all negated at the same time) ( R+S+T) (all negated at the same time)

the answer is supposed to be ~R~S~T ..but I just can't get there. Spent hours on this one.

The other one is:

y = ~(C+D) + ~AC~D + A~B~C + ~A~BCD + AC~D

and the answer is: ~D + A~B~C + ~A~BC  .. this one I got kinda close to.. but not quite.


and the last one (and hardest) is

x = ~(M+N+Q) + ~(M+~N+Q) + ~(~M+N+Q) 
and ALL of that negated

answer, apparently, is simply MN + Q.. I'm frustrated sad

Offline

#4 2006-10-17 13:46:43

polylog
Member
Registered: 2006-09-28
Posts: 162

Re: Boolean algebra help

For the 1st one:

You need De Morgan's Law, the two forms of it :

q = ~(RST) * ~(R + S + T)

= ~(RST) * (~R~S~T)

= (~R + ~S + ~T) * (~R~S~T)

now distribute:

= ~R(~R~S~T) + ~S(~R~S~T) + ~T(~R~S~T)

now notice that (~X)(~X) = ~X for any boolean X, and apply that:

= (~R~S~T) + (~R~S~T) + (~R~S~T)

now notice that ORing X with itself any number times is just X:  X + X + X + .... = X in boolean (weird but true)

Thus

= (~R~S~T)

Offline

#5 2006-10-17 14:27:35

johnd29
Member
Registered: 2006-10-17
Posts: 7

Re: Boolean algebra help

thanks..!!!!!

I'll keep trying on that last one..it's tough.

Offline

#6 2006-10-17 14:44:03

polylog
Member
Registered: 2006-09-28
Posts: 162

Re: Boolean algebra help

For the 2nd, are you sure the answer is supposed to be:

~D + A~B~C + ~A~BC

I got ~D + A~B~C + ~A~BCD

ie, with a D at the end...

It's a pain to type though... I just applied De Morgen to ~(C+D), and then factored out ~D on every term possible, then what was left over simplified to 1, which left ~D.

Offline

#7 2006-10-17 14:48:38

johnd29
Member
Registered: 2006-10-17
Posts: 7

Re: Boolean algebra help

polylog wrote:

For the 2nd, are you sure the answer is supposed to be:

~D + A~B~C + ~A~BC

I got ~D + A~B~C + ~A~BCD

ie, with a D at the end...

It's a pain to type though... I just applied De Morgen to ~(C+D), and then factored out ~D on every term possible, then what was left over simplified to 1, which left ~D.

that's exactly what I got! But apparently it's not correct..the book has the answer I told you. Maybe it's a mistake in the printing? (lol I always tell myself that).

Offline

#8 2006-10-17 14:57:18

polylog
Member
Registered: 2006-09-28
Posts: 162

Re: Boolean algebra help

It's quite possible that it's a typo in the book. smile
I can't see how to get that answer!

I got the third one too now, I'll need to learn the latex code for boolean to type it nicely, hold on a few minutes.. big_smile

Offline

#9 2006-10-17 15:10:14

polylog
Member
Registered: 2006-09-28
Posts: 162

Re: Boolean algebra help

This question is based on applying De Morgen ad nauseum, like 15 times:

Offline

#10 2006-10-17 15:16:03

johnd29
Member
Registered: 2006-10-17
Posts: 7

Re: Boolean algebra help

Wow. You are truly a kind man. Thanks a lot, you made it all very clear for me.

Offline

#11 2006-10-17 15:29:59

johnd29
Member
Registered: 2006-10-17
Posts: 7

Re: Boolean algebra help

I figured out another way to get a smaller answer for #2..

= ~C~D + ~AC~D + A~B~C + C (~A~BD + A~D)

= ~D [(~C+~AC) + AC] + C (~B + A~D)

= ~D [~C + (~A + AC)] + ~BC + AC~D

= ~D[ (C+~C) + A] + ~BC + AC~D

= ~D (1+A) + ~BC + AC~D

= ~D (1+AC) + ~BC


y = ~D + ~BC

don't know if it's right or not

Offline

#12 2006-10-18 04:00:06

polylog
Member
Registered: 2006-09-28
Posts: 162

Re: Boolean algebra help

You're welcome it was fun !
In your simplification, can you tell me how you got the 2nd line? I can't quite follow that step.

Offline

#13 2006-10-21 02:34:06

johnd29
Member
Registered: 2006-10-17
Posts: 7

Re: Boolean algebra help

Yeah..I think I made a mistake there because I'm figuring out a way to explain it, and can't think of what I did. Sorry, hehe.

Offline

Board footer

Powered by FluxBB