11
$\begingroup$

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

$\endgroup$
3
  • 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$
    – Willie Wong
    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

Reset to default
5
+100
$\begingroup$

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

$\endgroup$
2
  • 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$
    – Caleb Stanford
    Jul 13, 2017 at 21:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .