How many n-ary Boolean functions essentially dependent on each of their arguments?

544 Views Asked by At

How many n-ary Boolean functions essentially dependent on each of their arguments? essentially dependent means that $$f(b_1,…,b_{i−1},0,b_{i+1},…,b_n) \neq f(b_1,…,b_{i−1},1,b_{i+1},…,b_n)$$

1

There are 1 best solutions below

0
On BEST ANSWER

There are $2^{2^n}$ $n$-ary Boolean functions. For any subset $A$ of the $n$ arguments, there are $2^{2^{n-k}}$ $n$-ary Boolean functions that do not depend on any argument in $A$. Thus, by a standard inclusion-exclusion argument there are

$$\sum_{k=0}^n(-1)^k\binom{n}k2^{2^{n-k}}=\sum_{k=0}^n(-1)^{n-k}\binom{n}k2^{2^k}$$

$n$-ary Boolean functions that depend essentially on all $n$ arguments. This sequence is OEIS A000371; if there’s a closed form, OEIS isn’t aware of it.