Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

#1 2006-04-30 02:14:45

morik
Member

Offline

Logic gates and boolean algebra

Logoc gates, boolean algebra, truth tables, karnaugh maps... this stuff just doesn't click for me at all. So if anyone hear understands it, help would be muchly appreciated.
Here is the circuit... sorry it looks like a little kids drawing. i had to draw it in paint as i have no scanner to scan the official question paper with.
http://img49.imageshack.us/img49/9273/circuit4uv.jpg

What I have to do is...

1. Determine the Boolean function implemented by this circuit. Express that you determine it from the circuit above.

2. Create a truth table for this circuit.

3. Simplify the Boolean function found from above (you may use karnaugh mapping or algebraic methods to simplify the expression)

4. Draw a simpler circuit.

Thats it. Any answer or absolutely any tips or whatever will be awesome!
cheers guys
Jim

Last edited by morik (2006-04-30 02:15:54)

#2 2006-04-30 02:29:59

Ricky
Moderator

Offline

Re: Logic gates and boolean algebra

That circuit isn't valid.  One of the lines that goes into each and gate doesn't have a source.

Edit:

Unless they all branch out from B?  If a wire splits (i.e. goes off in two directions), you represent that by a dot where the split occurs.  For example:

http://www.geocities.com/rshadarack/gates.bmp

Is that what you mean?

Last edited by Ricky (2006-04-30 02:39:34)


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

#3 2006-04-30 02:47:41

morik
Member

Offline

Re: Logic gates and boolean algebra

yes,  that line you thought was invalid does branch out from B. Sorry, my fault for forgetting to pu the dot to represent the split in.

#4 2006-04-30 06:18:27

John E. Franklin
Star Member

Offline

Re: Logic gates and boolean algebra

Three input variables, so 2^3 is eight squares in the Karnaugh map.
You can make it a 2 by 4 grid or a 4 by 2 grid or a 2 X 2 X 2 cube, if you like symmetry and 3-D.
If you want to use a 4 by 4 grid, just remember that a variable D is a don't care value, either one or
zero, so you have two boxes for each of your permutations of A,B,and C.
It takes a while to catch on to this stuff, but I'll help more soon.


igloo myrtilles fourmis

#5 2006-04-30 06:24:57

John E. Franklin
Star Member

Offline

Re: Logic gates and boolean algebra

truth tables and Karnaugh maps are two ways of describing input combinations to outputs of false or true, or don't care.
"Don't care" values can be assigned 0 or 1 so the circuit or boolean expression ends up to your advantage.

In your example, the middle and gate is doing nothing for the circuit because a zero and a one are AND'd
together making a zero that is then put into the final 3-input or gate.  A zero into an OR gate means that the
other inputs are considered.  Why this is true requires explanation for which I might attempt later.

A logic one (true value) into an AND gate means that the other inputs will be considered.


igloo myrtilles fourmis

#6 2006-04-30 06:28:26

John E. Franklin
Star Member

Offline

Re: Logic gates and boolean algebra

Also, tell me which way you want to letter your C, B, A on a Karnaugh map.
C on left and B A on top edge or A on left and B C on top edge?
Then go 0 1 down for rows and 00 01 11 10 for columns across?
Is that how you were taught?


igloo myrtilles fourmis

#7 2006-04-30 08:16:56

krassi_holmz
Real Member

Offline

Re: Logic gates and boolean algebra

Karnaugh map???


IPBLE:  Increasing Performance By Lowering Expectations.

#8 2006-04-30 08:30:55

krassi_holmz
Real Member

Offline

Re: Logic gates and boolean algebra

This picture is some electric-like logic diagramq as I see.
Let's see what could be it...

1. Determine the Boolean function implemented by this circuit. Express that you determine it from the circuit above.

That means that the funtion will be obviously:
F(A,B,C)=F.

The triangle-circle block has 1 in and 1 out, so it may be f(x)=!x.
What does the half-circle means?
Is it "AND" or "OR"?

And what is the cutted-circle left F?
Union(...) or Intersection(...)?


IPBLE:  Increasing Performance By Lowering Expectations.

#9 2006-04-30 09:06:20

Ricky
Moderator

Offline

Re: Logic gates and boolean algebra

The triangle-circle block has 1 in and 1 out, so it may be f(x)=!x.

Great deduction krassi!

1.  Boolean function

I'm not entirely sure what you are looking for here.  Like for example, would a function be add or subtract, or NOR, or NAND or something similar?  If so, I don't know of any standard function that takes 3 inputs.

2. Create a truth table for this circuit.

You should be able to do this one, it isn't too hard.  Just start with the three inputs A, B, C being 0, 0, 0, and add 1 (in binary) each time.  So first is 0, 0, 0 then it's 0, 0, 1, then it's 0, 1, 0.  Each time, just go through and see which one is true or false.

3. Simplify the Boolean function found from above

I think the easiest way to do this is through boolean algebra.  Just take the sum of products to start out with:

^ is "and"
v is "or"
~ is "not"

(~A ^ B ^ ~C) v (A ^ B ^ ~C) v (A ^ B ^ C)

What I did was I took every entry in the truth table where F is 1 (true), and I anded all the conditions together.  For example, one line in my truth table is:

A B C F
0 1 0 1

So that's ~A since A is 0, B since B is 1, and ~C since C is 0.  And these three conditions together, then do the same for every other line that F turns out to be 1.  Now or all those conditions together.  And now, simplify.

From the above, you can take a B out of each since B must be true in each condition.  So it  becomes:

B ^ ( (~A ^ ~C) v (A ^ ~C) v (A ^ C) )

And you can simplify this futher.  Use the distributive property first, then use the reverse distributive property.  It will end up being:

B ^ (~C v A)

Now use this for 4.

4. Draw a simpler circuit.

Draw the ciruit in the order that you would read the expression.  For example, you read the parantheses first.  So take C, not it, and then or that with A.  Then take the output from this, and and it with B.  The output from this gate is F.  See how much simpiler your circuit is?  It only uses 2 gates instead of 4.

Last edited by Ricky (2006-04-30 09:08:10)


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

#10 2006-04-30 09:11:43

Ricky
Moderator

Offline

Re: Logic gates and boolean algebra

Oh, and for those who like to play around with these sort of things, Logisim is great fun.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

#11 2006-04-30 23:05:32

morik
Member

Offline

Re: Logic gates and boolean algebra

Hey guys,

In reply to John E. Franklin's question... I was taught to do karanugh maps with A on the left edge and B and C on the top edge with, like you say, 0 and 1 down and 00 01 11 10 across the top.

Thanks a lot for all your replies. They have certainly improved my understanding of the subject and have taken off a stress that I am suffering about the upcoming exam on it.

And Ricky, that piece of freeware is awesome! Thanks tons for that.

Cheers,
Jim

Board footer

Powered by FluxBB