Abstract

In 1920 Emil Post classified all possible clones of functions on the set 2={0,1}, and gave a set of generating functions for each of them. For a clone C we define a class of structures ${\bf\cal B}_{C} = \{ \langle 2^{X},\cap, \cup, \neg, A_{C}\rangle: X$ is finite }, where $\langle 2^{X}, \cap, \cup,\neg \rangle $ is a Boolean algebra and $A_{C}$ is a unary relation distinguishing a subset closed under operations from $C$. Let $Th$ be the first order theory of ${\bf\cal B}_{C}$. In the present paper we show that the theory $Th$ is decidable iff a clone $C$ contains the ternary discriminator.