Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A $n$-ary connective $\$$ is called self-dual if $f_\$(x_1^*, \ldots , x_n^*) = (f_\$(x_1, \ldots , x_n))^*$ where $0^* = 1$ and $1^* = 0$.

How to show that the set of such self-dual connectives doesn't form a functional complete set?

I think it got something to do with the "symmetry" in the truth-tables of such connectives and I guess you can't express $\lnot$ out of self-dual connectives. Is this right?

If so, how to show, that there's no way to express $\lnot$? I neither can think of an useful way of induction to show my claim nor do I have another idea.

share|cite|improve this question
IIRC, you can find sufficient and necessary conditions for completeness of connectives in Robert Reckhow's thesis. – Kaveh May 24 '12 at 5:02

I don't think you're going to be able to prove that $\lnot$ is inexpressible, because $\lnot$ is itself self-dual. Instead, I suggest you consider that for any self-dual operator:

$$ \begin{eqnarray} f(\bot,\ldots,\bot) & = & \hphantom{\lnot}f(\lnot\top,\ldots,\lnot\top) \\ & = & \lnot f(\top,\ldots,\top) \end{eqnarray} $$

so no self-dual operator has $f(\bot,\ldots,\bot) = f(\top,\ldots,\top)$. In particular I guess that the $\leftrightarrow$ operator may not be expressible.

Perhaps the proof should go like this: Suppose some expression with only self-dual operators is equivalent to $p\leftrightarrow q$. Let $E$ be such an expression of minimum depth $d$. Then the outermost operator of $E$ is a self-dual operator, and none of the proper subexpressions of $d$ are equivalent to $p\leftrightarrow q$. Then…

(I am not sure that this will work; post a comment if you would like me to try to finish.)

share|cite|improve this answer
Oh, alright, that's a good hint that no self-dual connective can have $f(0,...,0) = f(1,...,1)$. So it's shown for depth $d=1$ and then do induction on $d$, you suppose? – steltjen May 24 '12 at 3:53
Yes, exactly so. – MJD May 24 '12 at 3:54
Now consider $d+1$. So we've got expressions of depth $d$ which are not equivalent to $p \leftrightarrow q$ and build up on them an expression only with help of self-dual connectives. Then for any n-ary self-dual connective $f$--and $f^'_1, ..., f^'_n$ self-dual supexpressions--we have $f((f^'_1)^*, ..., (f^'_n)^*) = f(f^'_1, ..., f^'_2)^*$ ...? – steltjen May 24 '12 at 4:08
Could you please try to proceed with your suggested way? – steltjen May 24 '12 at 4:53

Negation isn’t a problem: $f_\lnot:B\to B:x\mapsto x^*$ is self-dual, since $f_\lnot(x^*)=(x^*)^*=\big(f_\lnot(x)\big)^*$. (Here $B=\{0,1\}$.) I suggest that you try to prove that every function in the clone generated by the self-dual functions is self-dual. Basically this amounts to showing that a composition of self-dual functions is self-dual, which is quite straightforward.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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