Prove that the set {$\rightarrow, \oplus$} is functionally complete by using that it is {$+, \neg$}

Question

The set {$+, \neg$} is functionally complete, because every boolean function can be represented as only combination of Disjunctions ($+$) and Negations ($\neg$).

Prove that the set {$\rightarrow, \oplus$} is functionally complete by using that it is {$+, \neg$}

---

I'm a bit confused by this question. I know that in boolean logic, $a \rightarrow b$ is equivalent to $\neg a + b$, but what about $\oplus$ ? And how should I proceed ?

---

EDIT: First, there was a typo in the post (I wrote {$\rightarrow, \neg$} instead of {$+, \neg$}) that was now corrected. Hopefully it makes more sense now.

And I found the solution of the same exercise of last year. It says:

"Because every function can be represented with $+$ and $\neg$, it is sufficient to show that $+$ and $\neg$ can each be represented with $\rightarrow$ and $\oplus$. $\neg x=1\oplus x =(x \rightarrow x) \oplus x$ and $x + y= \neg x \rightarrow y =((x \rightarrow x) \oplus x) \rightarrow y$"

This solution seems kind of confusing to me, what they did kind of makes sense but I have no idea how to find that solution myself without help

Answer 1

It is, indeed, a trick; for a general functionally complete set $S$, you can't expect to have a non-bruteforce algorithm to express a given Boolean function in terms of $S$. That is a hard task. One (but not the main) aspect is that there is no uniqueness (see my prev. comment and yours that contain different formulae for $x+y$). Some choices of $S$, however, behave better, and later in the course you shall see examples such as CNF, DNF, or Zhegalkin polynomials. In many useful aspects, for an arbitrary function these normal forms are way easier to understand than an expression in terms of $S = \{\to, \oplus\}$.

Answer 2

It's a little bit of trial and error, for sure, but I wouldn't say it's quite a 'trick' either.

For example, given $\to$, it's fairly natural to think of what $x \to x$ would be, and you'll see that $x \to x = 1$. Likewise, you find that $x \oplus x = 0$.

OK, so now you have $1$ and $0$ to play with, so now you can try expressions like $x \to 0$ or $0 \oplus x$ or $x \oplus 1$ or ... . So doing that, you'll quickly find that $x \to 0$, $1 \oplus x$, and $x \oplus 1$ all work out to work like $\neg x$.

Great! $\neg$ was one of the operators you were looking for, so now you know how to express it using $\to$ and $\oplus$: following the answer from last year: $\neg x = 1 \oplus x = (x \to x) \oplus x$. But you could also have used $\neg x = x \oplus 1 = x \oplus (x \to x)$. Or: $\neg x = x \to 0 = x \to (x \oplus x)$

Now, what about the $+$? Here, we can use a well-known equivalence $x \to y = \neg x + y$, which means that $x + y = \neg x \to y$. So, plug in any of the expressions for $\neg x$ that already found, and you're there. Following the 'answer from last year': $x + y = \neg x \to y = ((x \to x) \oplus x) \to y$. But you could also have used $x + y = \neg x \to y = (x \oplus (x \to x)) \to y$, or $x + y = \neg x \to y = (x \to (x \oplus x)) \to y$

So yeah, the end results look complicated, and you may think 'How on earth could I have come up with that?!', but the process was actually pretty straightforward.