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)$$
2026-03-30 10:39:17.1774867157
How many n-ary Boolean functions essentially dependent on each of their arguments?
544 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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.