3
$\begingroup$

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.

  • 0
    IIRC, you can find sufficient and necessary conditions for completeness of connectives in Robert Reckhow's thesis.2012-05-24

2 Answers 2

1

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

  • 0
    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?2012-05-24
  • 0
    Yes, exactly so.2012-05-24
  • 0
    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)^*$ ...?2012-05-24
  • 0
    Could you please try to proceed with your suggested way?2012-05-24
1

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.