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.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

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

Your Answer

 
discard

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.