Create a logic circuit only using AND & OR gates

Question

yesterday I had an exam, in which I still don't know how to resolve the problem. The question of the exam was: Create a logic circuit with 4 inputs (A,B,C,D) using ONLY AND & OR with 2 INPUTS gates starting from the truth table where:

• When the inputs are all 0, or all 1, the output is indifferent
• The output is 1 if the number of 1 in inputs is odd
• The output is 0 if the number of 1 in inputs is even

So this is the truth table:

A	B	C	D	Output
0	0	0	0	X
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	1
0	1	0	1	0
0	1	1	0	0
0	1	1	1	1
1	0	0	0	1
1	0	0	1	0
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	1
1	1	1	1	X

And the Karnaugh Map:

AB/CD	00	01	11	10
00	X	1	0	1
01	1	0	1	0
11	0	1	X	1
10	1	0	1	0

So the minimum function is:

ABC + ABD + ACD + BCD + !A!B!C + !A!B!D + !A!C!D + !B!C!D

I think I know how to deal with using AND & OR with 2 inputs, by doing groups like this: (tell me if I'm wrong)

A(BC + BD) + C(AD + BD) + !B(!A!C + !A!D) + !D(!A!C + !B!C)

But I dont understand how it's possible to do this without using a NOT gate, I asked the professor and he clearly said that I can only use AND & OR gates. I tried multiple approaches but they always involved NOT, NOR, NAND gates.

The professor said it's possible to resolve this exercise. Can you please help me?

• Stack Exchange Broke The Law: I don't see how it's possible either. Without NOT you have the requirement that turning inputs from 0 to 1 can only turn the output from 0 to 1, not from 1 to 0. And A=1 B=0 C=0 D=0 gives output 1, but A=1 B=0 C=0 D=1 gives output 0. There's no way that turning D from 0 to 1 can turn the output from 1 to 0 without a NOT gate
• Eugene Sh.: This looks like A xor B xor C xor D (if we take don't cares as 0). Can it be done without NOT gate? I don't think so. You have either misread the question, or it is just a bad one.
• zyzz777: Thanks for the answers, I also saw that this was kinda the form of a XNOR gate. I think I was doing something wrong but the professor literally said to me that I can only use AND & OR gates, nothing else.
• SamGibson: @All - Please stop the aggressive series of comments now. Read the Code of Conduct if you don't already know the rules on this. Tone is important - if you can't be friendly, then don't post a comment. || I can't see a way to erase just the aggressive comments since other comments refer to them. Therefore several comments have gone. Don't refer to now-deleted answers as other people can't see them and comments below the question are for clarification and improvement of the question, not for hints, rebukes, claims of what a deleted answer means, or anything else.
• Mitu Raj: If your professor were true, AND and OR could have been used as universal gates.

Answer 1

We know, that the gates AND and OR do not form a functionally complete set. It is true even if we add constants 0 and 1 to it. Let's convince ourselves that there is no way to create an inverter out of this set by simply providing all possibilities:

AND(X,0) = 0
AND(X,1) = X
AND(X,X) = X
OR(X,0) = X
OR(X,1) = 1
OR(X,X) = X

As we can see - we get back either the same constant that were fed to input, or the same input X. So there is no way to create an inverter.

---

Now, let's assume we could implement the requested function. Let's take a look at the two lines of it's truth table:

A B C D Out
-------------------
0 1 0 0 1
0 1 0 1 0

We can see that the ABC inputs are identical, an Out is the inverted D. If we had constants in our disposal (which we already saw do not change the fact that we work with functionally incomplete set), we could simply set ABC to 010 and create a NOT gate with input D and output Out. This way we would magically create a complete functional set out of an incomplete one. And this is a contradiction proving the assignment is not possible.

• SteveSh: One more thing. By functionally complete we mean that you can implement ANY arbitrary function of n variables with just those functions. NAND or NOR gates are functionally complete. So are AND and NOT, OR and NOT, etc. But as Eugene pointed out, AND and OR's by themselves are not functionally complete. Learned the theory & math behind this in a graduate discrete structures class many year ago.
• zyzz777: Thank you for your answers, and for the time you spent on this. I reached out to the colleagues doing this exam and noone was able to resolve this problem. We will talk with the professor about this. Thank you again.

Answer 2

The circuit description sounds like a parity generator. The internal schematics of a 74180 or CD40101 both have XOR and XNOR gates internally. That should be some guidance, but not a direct answer.

Start with a 2-bit circuit, 2 inputs and one output that meet the description. From there, cascade the remaining inputs. That is, the second circuit has the first circuit's output as one input, and the next data bot as the other input. That output is one of the inputs for the third stage, etc.

Don't get overwhelmed with all four inputs at once. Solve the 2-bit problem, and compound it for the remaining bits. The first four lines of the first table look exactly like an XOR gate. Design one of those without an explicit inverter anywhere, and you're there.

• Eugene Sh.: I don't see how it is helpful. How will one implement even a single 2-input XOR with AND and OR only?
• zyzz777: The exam is far away from what you are saying, thanks for the answer aswell