Today I was reading up once more on some of the nice results regarding functional completeness, notably Post's celebrated classification theorem with the 5 classes that need to be avoided. (See this PDF for a nice overview and proof of this result.)

Now it is well-known that the only two functionally complete binary connectives are the Sheffer strokes.

From these and the other familiar functionally complete pairs it is easy to construct some functionally complete ternary connectives. But not all of them will have such a nice reducible form.

How many ternary functionally complete connectives are there (out of $2^{2^3} = 256$ options)? Can they be easily described?

I'm also curious about the $n$-ary case, so if it can be easily generalised, go ahead -- particularly where it comes to a characterisation of these connectives.

I realise this might be a bit tough to address in complete detail in an answer, so I'm also definitely welcoming references and/or partial results.

  • $\begingroup$ Most probably, the answer is, no simple way. $\endgroup$ – user21820 Apr 23 '16 at 12:42
  • $\begingroup$ among the n-ary operators ($n=3$ being a particular case), the majority vote operator (value 1 iff there are more ones than zeros as entries) may be of interest... $\endgroup$ – Jean Marie Apr 23 '16 at 14:12
  • $\begingroup$ @JeanMarie: Why is it of interest? It is not complete even with constants 0,1 because it's monotonic. However, the minority operator with constant 0 is complete. I'm sure it's also not complete if you don't have constants but I don't see an easy way to prove it right now. $\endgroup$ – user21820 Apr 24 '16 at 11:42
  • 1
    $\begingroup$ You might want to have a look at this. $\endgroup$ – J Marcos Apr 29 '16 at 23:11
  • 1
    $\begingroup$ @JMarcos Thanks! That answers the question for all $n$: the number is $2^{2^n-2}-2^{2^{n-1}}$. Could you distil the two-sentence analysis given there into an answer with proof (given Post's result)? $\endgroup$ – Lord_Farin Apr 30 '16 at 17:45

Your Answer

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

Browse other questions tagged or ask your own question.