Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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 –  Dan Mar 30 '12 at 8:00
add comment

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

share|improve this answer
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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