# Boolean question

1. Aug 11, 2004

### macca

Guys I need help with this problem if you'd be so kind?

Q. Make a circuit comprising four inputs, output is TRUE if an odd number of inputs are TRUE.

My solution => A+B+C+D+ABC+ABD+ACD+BCD

So, how do I simplify that?

Thank you.

2. Aug 11, 2004

### Janus

Staff Emeritus
First off, your solution is incorrect, since it would simplify to A+B+C+D.

Secondly, the real solution doesn't simplify using AND or OR gates. (but you can simplify the circuit.)

3. Aug 11, 2004

### Hurkyl

Staff Emeritus
I think he's using + for or, not xor. Silly having 4 ways to write the same thing.

4. Aug 12, 2004

### e(ho0n3

I thought the symbol for xor is a circle-enclosed plus sign. What "thing" are you talking about?

macca: Draw yourself a Karnaugh map of the circuit behaviour. It shouldn't be too difficult.

5. Aug 12, 2004

### Hurkyl

Staff Emeritus
In logic, xor is $\veebar$. In circuits, xor is $\oplus$. In GF(2n), xor is +. In C, xor is ^.

Last edited: Aug 12, 2004
6. Aug 12, 2004

### Alkatran

Assuming + is OR and multiplication is AND

A+B+C+D+ABC+ABD+ACD+BCD is wrong because:

ABD + ABC = AB(D + C)
A+B+C+D+ABC+ABD+ACD+BCD = A(True + BC + BD + CD) + B(True + CD) + C +D
True+BC+BD+CD = true and True + CD = true
A + B + C + D
If any of them is true...

(A xor BCD) + (B xor ACD) + (C xor ABD) + (D xor ABC)
would make more sense, either one is true or three are true. I'm not sure how to simplify this because.. well I haven't ever "done" boolean math except minimally in programming.

7. Aug 13, 2004

### master_coda

The simplest representation for this circuit that I know of is:

$$A\oplus(B\oplus(C\oplus D))$$

8. Aug 13, 2004

### Alkatran

Right, because every true NOTs the final answer (starting with false)... right?

9. Aug 13, 2004

### master_coda

If you mean what I think you mean, than yes.

Actually, I made it unnecessarily complicated. $A\oplus B\oplus C\oplus D$ does the same thing, now that I think about it. I forgot that xor is associative.

10. Aug 13, 2004

### Janus

Staff Emeritus

This what I meant when I said it could be simplfied. I was trying to give him a push in the right direction without giving him the answer outright, just in case this was a homework assignment.

11. Aug 14, 2004

### paul11273

This question has me curious. By putting it into a truth table, then transferring to a K-Map doesn't help. You are unable to make any groups.
So reading directly from the truth table, I end up with:
A'B'C'D + A'B'CD' + A'BC'D' + A'BCD + AB'C'D' + AB'CD + ABC'D + ABCD'

By beginning to group and simplify I get:

$$A'B'(C'D+CD') + AB(C'D+CD') + C'D'(A'B+AB') + CD(A'B+AB')$$

$$A'B'(C \oplus D) + AB(C \oplus D) + C'D'(A \oplus B) + CD(A \oplus B)$$

$$(A \oplus B) + (C \oplus D)$$

As you can see by this, I am not getting down to the simplified answer given by you guys:$$A \oplus B \oplus C \oplus D$$

But, I do agree with you answer, because when I figure a truth table using your answer, I get the desired output results of true when there are an odd number of true inputs.

How would one go about simplifying this step by step?
Where did I make an error in my algebra?

12. Aug 14, 2004

### master_coda

The third line does not follow from the second. You should instead be getting:

$$(AB+A'B')(C \oplus D) + (A \oplus B)(CD+C'D')$$

$$(A \oplus B)'(C \oplus D) + (A \oplus B)(C \oplus D)'$$

$$(A \oplus B)\oplus(C \oplus D)$$

13. Aug 14, 2004

### TenaliRaman

XOR gives 1 when odd number of inputs are high .... (works for n number of inputs and its bcos as noticed by master coda .... XOR is associative)

-- AI

14. Aug 14, 2004

### paul11273

Cool, I now see where my error was. Thanks master_coda.