# How can {→,⊕} be complete when {¬,⊕} isn't?

Please provide an example with {→,⊕} that can't be realized with {¬,⊕}. I can't think of what I can't realize with {¬,⊕}.

I have a simple model where I think the bottom is more like YES ⊕ NO (and it doesn't at all look like YES OR NO even though the picture doesn't say that YES and NO can't both be true for the same input(?)

It depends what we want the algorithm to do but usually the output should be neither "both YES and NO" nor "neither YES nor NO".

I understand we might want the cases with no answer for one case of input or both yes and no answer for another case of input.

The system I was modelling would output 0 XOR 1 and never something else.

-
Is $\oplus$ exclusive OR? – Brian M. Scott Mar 17 '13 at 20:10
$\land$ should work. I will leave it to others to figure out exactly how :-) – Myself Mar 17 '13 at 20:12
I don't understand your remark but the main thing is that $\land$ is not 'affine', i.e if you consider the isomorphism with the boolean algebra $\mathbb F_2[x,y]$ then $\land$ is non linear while $\lnot$ and $\oplus$ only permit linear functions. – Myself Mar 17 '13 at 20:15
I have written an answer that should clarify my remark. – Myself Mar 17 '13 at 20:30
@NickRosencrantz To show that a set of logical connectives is complete means to show that there is a connective that can't be realized with it, not that there is a value (0 or 1) that can't be realized with it. That is why the answers you are getting mention connectives (like $\vee$) that do not appear in the problem statement. – Trevor Wilson Mar 17 '13 at 21:14

It looks like you're confused about what "complete set of connectives" means.

By definition, what the claim "$\neg$ and $\oplus$ form a complete set of connectives" means is:

Every possible truth table is the truth table for the output of some expression built with only $\neg$ and $\oplus$ in addition to the input variables (and parentheses etc.)

Here, of course "possible truth table" implies that the ground rules for truth tables are followed -- every combination of input values must appear in exactly one line, but the output values are arbitrary, that is, no matter which output values we choose it must be possible to come up with an expression that produces exactly these outputs.

Since the claim we're investigating is one about "every truth table", it willl be false (and therefore $\{{\neg},{\oplus}\}$ is not a complete set) if we can find even a single truth table that doesn't have a matching expression. It is easy for an "every X" statement to go wrong, hard for it to hold.

Here's a truth table that has no matching expression built with only $\neg$ and $\oplus$:

 input 1     input 2   |   output
--------------------------------
0           0      |     0
0           1      |     1
1           0      |     1
1           1      |     1


(It happens to be the truth table for $\lor$, but that is not important, except possibly as a way to name the truth table without writing it down explicitly. What is important here is that we're interested in whether $\{\neg,\oplus\}$ can make every truth table. Here's some random truth table -- can we make it or not?)

It turns out that we can't. It is quite possible to find an expression with two variables (and all connectives $\neg$ or $\oplus$) such that inputs 0,0 produce output 0, and a different expression such that inputs 0,1 produce output 1, and so forth. But there's no single expression that produces the right answer for every line of the truth table.

(For proof that this particular truth table cannot be made, see the answer I linked to earlier).

So we know that this particular truth table cannot be generated with $\neg$ and $\oplus$ alone. We can then stop worrying about which other truth tables are possible or not; the existence of even one that can't be produced means by definition that $\neg$ and $\oplus$ is not complete.

-
I understand. Thanks. My thoughts are about decision problems only and that could be slightly different from functional completeness. I never need any other logic than XOR and negation. – Programmer 400 Mar 17 '13 at 22:47
@NickRosencrantz: What do you mean by "my thoughts are about decision problems"? What about the decision problem "is the two-bit input in the set $\{01,10,11\}$?"? – Henning Makholm Mar 17 '13 at 22:48
@Nick: It is not true that A?1:0 always results in 0 XOR 1. If A is false, then A?1:0 evaluates to 0, but 0 XOR 1 is 1 which not the same as 0. – Henning Makholm Mar 17 '13 at 22:57
Are you perhaps misunderstanding what "XOR" means? It is neither more nor less than the particular two-input function $f$ such that $f(0,0)=0$ and $f(1,0)=1$ and $f(0,1)=1$ and $f(1,1)=0$. There's nothing ternary or metaphysical about it. – Henning Makholm Mar 17 '13 at 23:00
In particular, saying "the output is always either 0 or 1" is not the same as saying "the output is always $0\oplus 1$". The former means "it is always the case that the output is 0 or that the output is 1 but not both at the same time". The latter means "the output is always 1", because "$0\oplus 1$" is just a verbose way to write $1$. – Henning Makholm Mar 17 '13 at 23:02

Show that $\lor$ cannot be produced using only $\neg$ and $\oplus$. One way to do this is to show that if $f(p,q)$ is any proposition in two variables constructed solely with $\neg$ and $\oplus$, the $4$-row truth table of $f$ has a $\mathsf{T}$ in an even number of rows. You can do this by structural induction on $f$: show that if $f$ has the property, then so does $\neg f$, and that if $f$ and $g$ have the property, then so does $f\oplus g$.

Note that you can replace $\lor$ by any connective that has an odd number of $\mathsf{T}$’s in its truth table; $\land$ works equally well, as does $\to$.

-
Many thanks Brian. It's very interesting but my answer won't need ∨ ever. I mean to realize a YES (¬¬) or to realize a NO (¬) you won't need →,∨ or ∧ anywhere. – Programmer 400 Mar 17 '13 at 20:22
@Nick: I don’t understand your comment. In order to show that $\{\neg,\oplus\}$ is not complete, you have to find a connective that it cannot generate, and $\lor$ is such a connective (though not, as I mentioned, the only one). – Brian M. Scott Mar 17 '13 at 20:23
I can't do →, &, ∨ but I don't understand the use for these if I just want to output 0 or 1. Thank you very much. I understand that I can't realize for instance A→B but the output {0⊕1} is never A→B. I mean the difference between {0⊕1} and {0∨1} – Programmer 400 Mar 17 '13 at 20:31
@Nick: I think that you don’t really understand what the problem is asking you to do. You are supposed to show that there is some Boolean connective (or function) that cannot be produced as a composition of $\neg$ and $\oplus$. I’ve suggested that you do this by showing that if $f(p,q)$ is a binary Boolean function that can be produced by composing $\neg$ and $\oplus$ in some way, then $0,2$, or $4$ of the values $f(0,0),f(0,1),f(1,0)$, and $f(1,1)$ must be $1$. But the function corresponding to $\lor$ is $f(0,0)=0,f(0,1)=f(1,0)=f(1,1)=1$, with three outputs of $1$, not $0,2$, or $4$, ... – Brian M. Scott Mar 17 '13 at 22:49
... so it cannot be built up from $\neg$ and $\oplus$. Since there is then at least one Boolean connective/function that can’t be built up from $\neg$ and $\oplus$, $\{\neg,\oplus\}$ is not complete. – Brian M. Scott Mar 17 '13 at 22:50

There are two ways to look at boolean connectives/functions. The usual way it to let $\mathbf B = \{0,1\}$, so you may think of them as functions $\mathbf B^i \to \mathbf B$. This is the classical interpretation with a truth table. For instance, $\land(0,1) = 0$.

But alternatively, you may think about boolean functions as polynomials over the field $\mathbf F_2 = \{0,1\}$. Then the 'addition' matches $\oplus$ and 'multiplication' matches $\land$. Now note that in this language

\begin{aligned} \lnot x &= 1+x \\ x\land y &= xy \\ x\lor y &= \lnot(\lnot x \land \lnot y) = 1 + (1+x)(1+y) = x+y+xy \\ x \oplus y &= x+y\\ x\to y &= (\lnot x \lor y) = (1+x)\lor y = 1+x + y + y + xy = 1+x+xy\dots \end{aligned}

This means that if you are only allowed to combine $\oplus$ and $\lnot$, then the only functions you can make by composing these are the affine ones, this mean functions of the form $$a_0 + a_1 x_1 + a_2 x_2 + \dots + a_nx_n.$$ Where $a_i \in \{0,1\}$. (In particular, for $2$ variables $x$ and $y$, there are $8$ affine functions namely $0$, $1$, $x$, $1+x$, $y$, $1+y$, $x+y$ and $1+x+y$.)

However, $\to$ is clearly non-affine, because it contains the second degree term $xy$, which shows that it cannot be created from composition of $\oplus$ and $\lnot$.

-
I can't do →, &, ∨ but I don't understand the use for these if I just want to output 0 or 1. – Programmer 400 Mar 17 '13 at 20:30