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

  • 1
    $\begingroup$ How did you get that? $\endgroup$
    – draks ...
    Mar 29, 2012 at 20:29
  • $\begingroup$ 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. $\endgroup$ Mar 30, 2012 at 7:49
  • $\begingroup$ @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 $\endgroup$
    – A. Napster
    Mar 30, 2012 at 8:00

1 Answer 1


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

  • 1
    $\begingroup$ 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. $\endgroup$
    – MJD
    Oct 9, 2012 at 13:51
  • $\begingroup$ Just discovered this amazing answer. Would like to echo MJD's appreciation (close to 5 years later). $\endgroup$
    – 6005
    Jul 13, 2017 at 21:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.