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