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.

  • $\begingroup$ I just corrected my answer; please check it, I had to add one more conector to deal with negations. $\endgroup$ – Camilo Arosemena-Serrato Dec 21 '12 at 6:33

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.

  • $\begingroup$ Overkill perhaps? ;-) $\endgroup$ – Peter Smith Dec 21 '12 at 8:28
  • $\begingroup$ I can't understand how to determine the truth value of $G_i(X)$, when $X \notin \{ C_0, C_1\}$. Take $G_2$ as an example, is it true that iff $C_0 \vDash X$, $G_2(X)=T$? Thus I don't understand why $G_2$ assigns at least one of $A$, $B$ and $C$, to $T$. $\endgroup$ – Metta World Peace Dec 21 '12 at 21:40
  • $\begingroup$ The value of $G$ is extended to other formulas by induction on formulas, perhaps this clarifies your doubts little bit personal.kent.edu/~rmuhamma/Philosophy/Logic/Deduction/… $\endgroup$ – Camilo Arosemena-Serrato Dec 21 '12 at 22:51
  • $\begingroup$ So you mean $A$, $B$, $C$ are soly generated by $C_0$ and $C_1$? What if $A$, $B$, $C$ are also generated by other wffs which are not generated by $C_0$ and $C_1$? $\endgroup$ – Metta World Peace Dec 21 '12 at 23:11
  • $\begingroup$ yes, for if $\{¬,\#\}$ was complete, there would be a formula $A$ whose only propositions are $C_0$ and $C_1$ such that $A$ is equivalent to $C_0\wedge C_1$ $\endgroup$ – Camilo Arosemena-Serrato Dec 21 '12 at 23:16

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

  • $\begingroup$ This has the clear advantage over Peter Smith's approach that it actually works! $\endgroup$ – Henning Makholm Dec 21 '12 at 14:25
  • 1
    $\begingroup$ @Henning: I have to admit that I didn’t read the details of his answer; I was thinking just of the idea of using an invariant. $\endgroup$ – Brian M. Scott Dec 21 '12 at 14:27
  • $\begingroup$ Yep, dunce's corner for me. Sorry about that carelessness and thanks to @HenningMakholm for the obvious objection! $\endgroup$ – Peter Smith Dec 22 '12 at 14:05

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.

  • $\begingroup$ I have removed the peripheral question in this answer. Please consider asking this as a question of your own. $\endgroup$ – Alexander Gruber Dec 24 '12 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.