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