Proof that {xor,not} is not functionally complete I am trying to figure out the formal proof that set of {xor, not} is not a functional complete system.
Firstly I tried to build it by structural induction and show that any formula created by using xor or not has exactly half true valuations and half false valuations (and it violates with e.g. OR that has 3/4 true valuations for A OR B). Then I realized that A xor (not A) breaks it.
Could anyone help me with this, please?
 A: You've been on the right track. It is just a slightly different claim that you can show by induction, namely that all formulae using these connectives only will have an even number of true valuations. The induction base should be easy, I will only sketch the induction step.
Show that if $A \dot\vee B$ has an odd number of true valuations, then either $A$ or $B$ has an odd number of true valuations, too.
Why is this so? Say $n$ is the number of true valuations of $A \dot\vee B$, and assume $n$ is odd. $n$ must be either $1$ or $3$. If it is $1$, then $A$ and $B$ agree in three assignments (for $A$ and $B$) and disagree in one. So one of them must have an odd number of true assignments. If it is $3$, then $A$ and $B$ agree in one assignment and disagree in three assignments. Within the three assignments in which they disagree, either $A$ or $B$ has an even number of true valuations, and the respective other an odd number (because if you have $a+b=3$, either $a$ or $b$ is odd). Taking in the fourth assignment, still either $A$ or $B$ will have an odd number of true valuations.
The contraposition of that is: if $A$ and $B$ both have an even number of true valuations, then so has $A \dot\vee B$. Then, of course, $\neg (A \dot\vee B)$ also has an even number of true valuations. This serves for the main part of the induction step.
