Functional completeness - Proving $\nLeftrightarrow$ is functionally complete

Question

Can you help me with the following task:

I have to prove whether $\nLeftrightarrow$ is functionally complete or not.

Thereby $\nLeftrightarrow$ is defined as:

$$ x \nLeftrightarrow y := \lnot (x \Leftrightarrow y)$$

I also know after research that this is equivalent to this: $$ \lnot(x \Leftrightarrow y) = (x \oplus y) = (\lnot x \land y) \lor (x \land \lnot y)$$

I think it is not complete, but how can I prove it.

Answer 1

Indeed $\nLeftrightarrow$ is not functionally complete, it cannot express logical negation. To show this we will prove by induction on the complexity of the formula that for any formula $\varphi(x)$ that is built only using $\nLeftrightarrow$ we have that $\varphi(F) = F$, where $F$ means false. Then it immediately follows that there is no formula $\varphi(x)$, built from $\nLeftrightarrow$, that is logically equivalent to logical negation.

Base case. If $\varphi(x)$ is just $x$, then clearly $\varphi(F)$ is $F$.

Induction step. If $\varphi(x)$ is $\psi_1(x) \nLeftrightarrow \psi_2(x)$ then $\varphi(F)$ is $\psi_1(F) \nLeftrightarrow \psi_2(F)$. We can apply the induction hypothesis to see that $\psi_1(F) = \psi_2(F) = F$. So $\varphi(F)$ is $F \nLeftrightarrow F$, which is just $F$ and we are done.

Answer 2

Functionally complete sets of Boolean operators was solved and classified by Emil Post as referenced here. It mentions the only functional complete set of single operator are 2 possibilities NAND and NOR: {↑}, {↓}. And for your specific case of $\nLeftrightarrow$, it belongs to two possible classified characterizations of functional incompleteness:

Emil Post proved that a set of logical connectives is functionally complete if and only if it is not a subset of any of the following sets of connectives:

. The affine connectives, such that each connected variable either always or never affects the truth value these connectives return, e.g. {$ \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow$}.

. The falsity-preserving connectives; they return the truth value F under any interpretation which assigns F to all variables, e.g. {$ \vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow$}.

As user @Mark Kamsma already showed by induction on the complexity of the formula with your only operator, it's really a falsity-preserving connective returning $F$ under any interpretation which assigns $F$ to all variables. Thus it's a subset of Post's last classified falsity-preserving set and cannot express negation of falsity.

Since your operator also belongs to Post's affine connectives set such that each connected variable always affects the truth value these connectives return, you can also prove by induction on the complexity of the formula with your only operator that because two true Boolean variables will always return false and if either variable is changed to false will always return true only, thus it's functionally incomplete for the case when one variable is true and the other is false while the returned truth value needs to be false.

Finally note that even if you add negation operator ($\lnot$) to express negation, your system is surprisingly still incomplete per above first classification, and you can use the same proof in this section to prove that even including negation connective, it's still functionally incomplete for the case when one variable is true and the other is false while the returned truth value needs to be false...