How to prove a set of sentential connectives is incomplete?

Question

On Page 52, A Mathematical Introduction to Logic, Herbert B. Enderton（2ed),

Show that $\{\lnot, \# \}$ is not complete.

A set of connective symbols is complete, if every function $G : \{F, T\}^n \to \{F, T\}$for $n > 1$ can be realized by a wff(well-formed formula) using only the connective symbols from it. A known fact is the set $\{\lnot, \land \}$ is complete.

$\#$ is a three-place sentential connective. For three arbitary wffs, $A$, $B$ and $C$, $\#ABC$ is tautologically equilvalent to: $$(A\land B)\lor(A\land C)\lor(B\land C)$$

Here's how far I understand:

The problem can be reduced to showing, given two wffs $A$ and $B$, there is nothing tautologically equivalent to $A \land B$ by using $\lnot$ and $\# $. For simplicity, assume $A$ and $B$ are not generated by any other wffs and there exist a finite number of wffs $\{ C_i:i \leq n\}$which are not generated by other wffs either.

If the tautogocial equilvalent of $A \land B$ exists, I can't exclude the occurence of $C_i$.

I'm also trying to use induction, but I got stuck when $C_i$s are involved.

Answer 1

Peter Smith’s approach is probably the best way to think about such problems in general. In this case there’s another fairly simple approach. Notice first that the connective $\#$ is symmetric in its three arguments: if $XYZ$ is any permutation of $ABC$, $\#ABC$ is equivalent to $\#XYZ$. From this it’s easy to see that all combinations of exactly two sentence letters $A$ and $B$ with $\#$ are equivalent either to $\#AAB$ or to $\#ABB$. Moreover, $\#AAB$ is equivalent simply to $A$, and $\#ABB$ to $B$; this suggests trying to show that as long as we work with at most two sentence letters, $\#$ essentially does nothing.

Claim: Every wff that can be constructed from the sentence letters $A$ and $B$ and the connectives $\neg$ and $\#$ is equivalent to one of $A,B,\neg A$, and $\neg B$.

Proof: The claim is easily proved by induction on the complexity of the wff. It’s certainly true for wffs with no connective: they are simply $A$ and $B$. Suppose that $\varphi$ has at least one connective. Then $\varphi$ is either $\neg\psi$ for some wff $\psi$, or $\#\psi_0\psi_1\psi_2$ for wffs $\psi_0,\psi_1$, and $\psi_2$. Suppose that $\varphi=\neg\psi$. The induction hypothesis ensures that $\psi$ is equivalent to one of $A,B,\neg A$, and $\neg B$, and $\varphi$ is therefore equivalent to one of $\neg A,\neg B,A$, and $B$, respectively.

Now suppose that $\varphi=\#\psi_0\psi_1\psi_2$. Again the induction hypothesis ensures that each of $\psi_0,\psi_1$, and $\psi_2$ is equivalent to one of $A,B,\neg A$, and $\neg B$. Any set of three chosen from $\{A,B,\neg A,\neg B\}$ necessarily contains either two copies of one of the four wffs or a wff and its negation, so $\varphi$ is equivalent to $\#XXY$ or $\#X\neg XY$ for some $X,Y\in\{A,B,\neg A,\neg B\}$. But $\#XXY$ is equivalent to $X$, and $\#X\neg XY$ is equivalent to $Y$, so in every case $\varphi$ is equivalent to one of $A,B,\neg A$, and $\neg B$. The claim now follows by induction. $\dashv$

Since $A\land B$ is not equivalent to $A,B,\neg A$, or $\neg B$, $\{\neg,\#\}$ is not complete.

(I’ve implicitly used the fact that if $\psi_0,\psi_1$, and $\psi_2$ are equivalent to $\psi_0',\psi_1'$, and $\psi_2'$, respectively, then $\#\psi_0\psi_1\psi_2$ is equivalent to $\#\psi_0'\psi_1'\psi_2'$. This is clear from consideration of the relevant truth tables.)

Answer 2

It sufficies to prove the case $n=2$.

Let $G_1,G_2,G_3,G_4:\{C_0,C_1\}\rightarrow\{T,F\}$ be given by $G_1(C_0)=T=G_1(C_1)$, $G_2(C_0)=T,G_2(C_1)=F$, $G_3(C_0)=F,G_3(C_1)=T$ and $G_4(C_0)=F=G_4(C_1).$

$(1)$ Let us prove by induction on formulas constructed over $\{C_0,C_1\}$ in the language $\{¬,\#,@\}$ that there is no formula equivalent to $C_0\wedge C_1$ or $¬(C_0\wedge C_1)$, where $$@ABC=(A\vee B)\wedge(A\vee C)\wedge(B\vee C).$$

You have to show that for any formulas $A,B,C$, $\#ABC$ and $@ABC$ are equivalent; (hint: $\#ABC$ is true if and only if at least two elements of $A,B,C$ are true, and the same holds for $@ABC$)

This clearly holds for atomic formulas.

Let us assume that $A,B,C$ are formulas such that the condition $(1)$ holds. Then $(1)$ holds for $¬A$. $(2)$

Suppose $\#ABC$ is equivalent to $C_0\wedge C_1$, then $G_1(\#ABC)=T$, so we may assume with no loss of generality that $G_1(A)=T$; because of the form of $\#ABC$. Also $G_i(\#ABC)=F$ for $i=2,3,4$, then by the form of $\#ABC$ it follows that $G_i(A)=F$ for $i=2,3,4$, which implies $A$ is equivalent to $C_0\wedge C_1$, contradicting the inductive hypothesis, thus $(1)$ holds for $\#ABC$.$(3)$

If $\#ABC$ was equivalent to $¬(C_0\wedge C_1)$, $@¬A¬B¬C$ would be equivalent to $C_0\wedge C_1$, then $\#¬A¬B¬C$ would be equivalent to $C_0\wedge C_1$, contradicting $(2)$ and $(3)$.

Since $\#ABC$ and $@ABC$ are equivalent, this finishes the proof.

Answer 3

In pp.12-13 of A Concise Introduction to Mathematical Logic, by W. Rautenberg, the author points out that $\{\lnot, \# \}$ defines precisely the class of self-dual boolean functions. Thus, in this particular case it would easily follow that no non-self-dual operator (such as any essentially binary boolean operator) is definable from $\lnot$ and $\#$ alone.