# Finding Expressively Adequate truth Functions

I was wondering if someone could help me count the total number of Truth Functions of 3 variables, that can generate all the possible truth functions..

I got 56 but I'm not sure of the answer.

EDIT: Would just like to add that the functions have 3 variables but still have binary inputs and outputs. Also each function has a unique truth table

• How did you get that? – draks ... Mar 29 '12 at 20:29
• I've merged your duplicate accounts. If you register your account, then your edits to your own question will not require review by a higher rep user. – Willie Wong Mar 30 '12 at 7:49
• @draks Well the truth functions of 2 variables, that generate all the other truth functions are joint denial (NOR) and alternative denial(NAND). Suppose that I have a 3-variable function f(X,Y,Z) which can generate all truth functions. Then I assumed that there should be at least a pair (X,Y) of the variables X,Y,Z such that when X=Y, f(X,X,Z) gives a 2-variable generative truth function i.e NOR or NAND. Then by using the Inclusion–exclusion principle, I found it to be 56... Although I'm not too sure that my assumptions and calculations are correct – A. Napster Mar 30 '12 at 8:00

## 1 Answer

You are absolutely right : the exact number is 56, and it can be shown rigorously as follows.

By Post’s theorem, a boolean function is not expressively adequate iff it is either monotone, affine over $\frac{\mathbb Z}{2\mathbb Z}$, self-dual, truth-preserving or falsity-preserving.

In three variables this simplifies considerably. Indeed, not being truth- or falsity-preserving reduces to $f(0,0,0)=1$ and $f(1,1,1)=0$. Then $f$ is never monotone.

We now partition the remaining set of functions into four subsets indexed by $\lbrace 0,1 \rbrace^2$ : for $a,b$ in $\lbrace 0,1 \rbrace$, put

$$G_{a,b}=\lbrace f | f(0,0,0)=1, f(1,1,1)=0, f(0,0,1)=a, f(0,1,0)=b\rbrace$$

Each $G_{a,b}$ contains a unique affine map (explicitly, $f(x,y,z)=1+ax+by-(a+b)z$ modulo 2). This affine map is always self-dual, and $G_{a,b}$ contains exactly two self-dual maps. Finally, each $G_{a,b}$ contains two nonadequate functions, and hence $2^4-2=14$ adequate functions, which makes a total of $2^2\times (2^4-2)=56$.

• Thanks very much for posting this. I was completely unaware of Post's theorem about expressively adequate sets of functions and of the Post lattice, and I am very pleased to have found out about them. I feel that this is by far the best outcome I've gotten from the bounty system. – MJD Oct 9 '12 at 13:51
• Just discovered this amazing answer. Would like to echo MJD's appreciation (close to 5 years later). – 6005 Jul 13 '17 at 21:31