How can I show $p \land q$ using only the symbols $p$ $q$ $⊕$ $∼$ $( )$? If it isn't possible why?

Question

Is it possible to express $p \land q$ using only the symbols $p$ $q$ $⊕$ $∼$ $( )$? If it is indeed possible can you prove it using logical equivalence laws? If it is not possible could you explain why.

Thank you :)

lots of trial and error/ brute force to no avail. Tried rearranging using laws of logical equivalences. Not sure how to go about it. I'm starting to think that it can't be proved. Do you have any understanding to why it could not be proved?

Answer 1

$(\sim A) \oplus B = \sim(A \oplus B)$, so every expression can be written as $\sim f(P, Q)$ or as $f(P, Q)$ where $f(P,Q)$ doesn't contain any $\sim$.

$\oplus$ is associative and commutative, so each of those expressions is equivalent to an expression $g(P) \oplus h(Q)$, and there are only 3 possible unary operators.

So there are only a few cases to check.

Answer 2

If you map truth values to the field with two elements (that is, the integers modulo 2), with $0$ representing "false" and $1$ representing "true", then

• logical negation corresponds to adding $1$,
• $\oplus$ corresponds to addition.

Thus, by induction on the structure of an expression built from these operations, it will always implement an affine function of the inputs, having the form $f(p,q)=a+bp+cq$ for some coefficients $a,b,c$.

However $p \land q$ cannot have this form, because $$f(1,0)-f(0,0)=b=f(1,1)-f(0,1)$$ but $(1\land 0)-(0\land 0)=0-0=0$ whereas $(1\land 1)-(0\land 1)=1-0=1$, and $b$ cannot be both $0$ and $1$.

So $\land$ cannot be built from $\neg$ and $\oplus$.