# Fiction variables?

In every Boolean function $f(x_1, x_2,\ldots, x_n)$, for every $i$ ($1\le i\le n$), $x_i$ is called fiction variable if and only if when for every Boolean assessment for the rest variables $x_1, x_2,\ldots, x_{(i-1)}, x_{(i+1)},\ldots,x_n$ the function has the same value for $x_i=0$ and $x_i=1$.

How many Boolean functions of $n$ variables have no fictional variables?

I have some ideas, but don't know how to prove it "formally". Any help would be greatly appreciated.

-

I think the question is how many Boolean functions of $n$ variables have no fictional variables. This can be answered using the inclusion-exclusion principle. If you take a subset $S$ of size $k$ of the $n$ variables and ask how many Boolean functions on $n$ variables have at least the variables in $S$ fictional, the answer is the same as the number of Boolean functions on the $n-k$ remaining variables, which is $2^{2^{n-k}}.$ Therefore, the number of Boolean functions on $n$ variables with no fictional variables is $$\sum_{0\le k\le n} (-1)^k \binom{n}{k} 2^{2^{n-k}}.\qquad (*)$$ This is OEIS A000371.

In response to the comment: the inclusion-exclusion principle says that if we have a finite set $U$ of properties and a set of objects, and if the number of objects with at least the properties in the set $T\subseteq U$ is $N(T)$, then the number of objects with none of the properties is $$N_0=\sum_{T\subseteq U} (-1)^{|T|} N(T). \qquad (+)$$ (*) follows immediately from (+) upon letting $\{x_1, \dots, x_n\}$ be the set of variables and letting $U$ be the set {"has at least $x_1$ as a fictional variable", $\dots$, "has at least $x_n$ as a fictional variable"}. This is because, if $T$ is a subset of $U$ of size $k$, then, as explained above, the set of Boolean functions on $n$ variables with at least the properties in $T$ has size $N(T)=2^{2^{n-k}}$.

To see why (+) is true, take as an example the case where $U$ has size 3. Then, if we let $X$ be the set of all objects and $A$, $B$ and $C$ be the subsets of $X$ which satisfy the first, second, and third properties of $U$, (+) reduces to $$|X\setminus (A\cup B\cup C)|=$$ $$|X|-|A|-|B|-|C|+|A\cap B|+|A\cap C|+|B\cap C|-|A\cap B\cap C|.\ \ (++)$$ On the right-hand side of (++), to count the number of objects with no properties, we start with the number of all objects, $|X|$, which is an overestimate. We then subtract $|A|+|B|+|C|$. This produces an underestimate, since $|X|-|A|-|B|-|C|$ correctly counts each object with no properties once and each object with exactly one property $0$ times, but if an object has exactly two properties, it is counted $-1$ times, and if it has all three properties, it is counted $-2$ times. To remedy this, we add $|A\cap B|+|A\cap C|+|B\cap C|$. This results in a count which is correct for objects with no properties, counting them once, or objects with exactly $1$ or $2$ properties, which are counted $0$ times. However, it overcounts objects with all three properties by counting them once instead of $0$ times. This is fixed by subtracting $|A\cap B\cap C|$, giving the correct and final form of (++).

The proof of (+) in the general case is similar. The inclusion-exclusion principle is also often stated in the form $$N_{\ge 1}=N(\emptyset)-N_0=\sum_{\emptyset\ne T\subseteq U} (-1)^{|T|-1} N(T),$$ where $N_{\ge 1}$ is now the total number of objects with at least one property.

-
can you explain a bit more how do you get a such answer, please? – DiscreteMath'sFan Jan 17 '13 at 23:22
Thanks David,I will consider it :) – DiscreteMath'sFan Jan 18 '13 at 6:01
One last question - what did you mean under "properties"...my English is very bad? – DiscreteMath'sFan Jan 18 '13 at 22:19
A property is something that might or might not be true of an object, like "being red", "having size at least two", "having $x_1$ as a fictional variable", and so on. – David Moews Jan 18 '13 at 22:25
Thanks again and sorry for the stupid questions. – DiscreteMath'sFan Jan 18 '13 at 22:31