Is it possible to express XOR purely in terms of the Sheffer stroke ($↑$)?

Question

I've been trying to do it myself but I can only get as far as

$$\begin{align} P ⊕ Q &= (P \vee Q) \wedge ¬(P \wedge Q) \\ &= (P \vee Q) \wedge (P ↑ Q) \\ &= ((P ↑ P) ↑ (Q ↑ Q)) \wedge (P ↑ Q). \end{align}$$

If it is possible then a pointer in the right direction would be greatly appreciated, if not then is there a way to prove it?

Answer 1

Yes - the Sheffer stroke is functionally complete, so every Boolean operation can be expressed in terms of it.

You're almost done - all you need to do is express $\wedge$ in terms of the Sheffer stroke.

Well, $A\wedge B$ is just $\neg (\neg A\vee \neg B)$, and $\neg A$ is just $A\uparrow A$; so this reduces to the problem of expressing "$\vee$" in terms of Sheffer stroke.

But you've already done this . . .

---

If you follow this recipe blindly, the expression you get at the end is $$(((X\uparrow X)\uparrow (X\uparrow X))\uparrow((Y\uparrow Y)\uparrow(Y\uparrow Y)))\uparrow (((X\uparrow X)\uparrow(X\uparrow X))\uparrow ((Y\uparrow Y)\uparrow(Y\uparrow Y)),$$ where $X=((P\uparrow P)\uparrow(Q\uparrow Q))=P\vee Q$ and $Y=P\uparrow Q=\neg (P\wedge Q)$.

This can be simplified, though: $((A \uparrow A)\uparrow (A\uparrow A))=A$. So this gives us the much tamer $$(X\uparrow Y)\uparrow (X\uparrow Y),$$ or rather $$([((P\uparrow P)\uparrow(Q\uparrow Q))]\uparrow [P\uparrow Q])\uparrow ([((P\uparrow P)\uparrow(Q\uparrow Q))]\uparrow [P\uparrow Q]).$$ This is, of course, thoroughly godawful. But it works!

. . . And other things work much better (see Eli's answer below). But at least this shows it can be done.

Answer 2

Thanks to Rahul's help I was able to derive an expression using just $\uparrow$ equivalent to $A \oplus B$ which is $(A \uparrow (B \uparrow B)) \uparrow ((A \uparrow A) \uparrow B)$