Logic: exclusive-OR statements to form AND/OR statements

[Back2College]

Homework Statement

Using only NOT and XOR, construct a compound statement having the same truth table as:

(a) p OR q

(b) p AND q

Homework Equations

XOR is "exclusive OR." p XOR q = (p OR q) AND NOT (p AND q).

I have been working under the assumption that I can use parentheses.

The Attempt at a Solution

I know the truth tables for (p OR q) and (p AND q) are TTTF and TFFF, respectively. So, either three Trues and one false or one True and three Falses.

However, when I use only NOT and XOR I always get two Trues and two Falses. So far this has been the case no matter which combination I try or how many XORs I string together. It's always some combination of two Trues and two Falses.

Can anyone give me a hint?

Thanks.

 

[.Scott]

You can use parenthesis.

There is no solution:
XOR can be used to generate NOT: XOR(XOR(1,0),X) = NOT(X)
So the addition of the NOT gate is not needed.

XOR has affine connectives. That is: XOR(X,Y) = NOT(XOR(NOT(X),Y), so the XOR will always change when X changes. Of course, the same can be said for Y.
That's one of the attributes an operation must not have in order to be "functionally complete".
See https://en.wikipedia.org/wiki/Sheffer_stroke#Properties

The two operations that can be used to generate NOT, AND, and OR are NAND (the Sheffer Stroke) and NOR.

Actually, it's all explained here: https://en.wikipedia.org/wiki/Functional_completeness.

 

[phinds]

Using only NOT and XOR is exactly equivalent to "Using only XOR". This is because NOT is just an XOR with one input held high, so we can limit the analysis to just the XOR gate.

SO ... using a gate that ALWAYS has an output with two 1's and two 0's in the truth table would there be any way to make it have a single 1 or 3 ones?

This is the same as asking "if I always require an output of two apples, can I ever get outputs of 1 apple or 3 apples" ?

EDIT: Ah, I see Scott beat me to it.

 

[Back2College]

Thanks for your replies. I now understand why there can't be any solution.