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?

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.

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.