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?
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.