Functional complete and xor Give a formal proof for the claim that the set $\{xor\}$ is not functional complete.
One possible way is to show that we cannot create the function $\lnot$. I tried to prove it by using induction on the structure of $A$. If $A$ is a formula and $V$ is a model that gives $f$ to all atomic formulas then $V(A) = f$. The base case is $A = p$ and so $V(A) = f$. We assume that it holds for the formulas $B$ and $C$. We have $A = xor(B,C)$ and by using the induction hypothesis and the definition of $xor$ we get $V(A) = f$.
But I want to show that we cannot create the function $\land$ I tried using the same method as before but it doesn't seem to work. What should the induction hypothesis be in this case?
 A: You have to consider an induction on the number of occurrences of connective in the formula.
Consider $\land$
Basis : in $p \land q$, when $p$ and $q$ have different truth values, then $p \land q$ is false.
Induction step : let $F_n^{\land}(p,q)$ a formula built with only the literals $p$ and $q$ with $n$ occurrences of $\land$, and assume as Induction hypo that it is identically false. 
If we consider now $F_{n+1}^{\land}(p,q)$ (i.e $F_n^{\land}(p,q) \land p$ or $F_n^{\land}(p,q) \land q$), again it is identically false.
Consider $xor$ (i.e. $\nLeftrightarrow$)
Basis : in $p \nLeftrightarrow q$, when $p$ and $q$ have different truth values, then $p \nLeftrightarrow q$ is true.
Induction step : let $F_n^{\nLeftrightarrow}(p,q)$ a formula built with only the literals $p$ and $q$ with $n$ occurrences of $\nLeftrightarrow $, ans assume as Induction hypo that it is not identically false. 
If we consider now $F_{n+1}^{\nLeftrightarrow}(p,q)$ (i.e $F_n^{\nLeftrightarrow}(p,q) \nLeftrightarrow p$ or $F_n^{\land}(p,q) \nLeftrightarrow q$), it can be true or false, and adding a new literal $p$ (or $q$), the result $F_{n+1}^{\nLeftrightarrow}$ will "flip" according to the value of $p$ (or $q$).
Thus, we have that it is not identically false.
