In Stasys Jukna's book "Boolean Function Complexity", he states that for an n variable Boolean function, the number of distinct subfunctions on $Y$ variables (meaning $Y$ variables have not been assigned to constants), is the minimum of $2^{n-|Y|}$ and $2^{2^{|Y|}}$. The first number is the number of ways constants could be assigned to all variables not in $Y$, and the second number is the number of Boolean functions on $Y$ variables. My question is why is the number of distinct subfunctions the minimum of these two numbers, and not their product, as it seems to me for each configuration of constants for variables not in $Y$, each boolean function on $Y$ could be applied.
Asked
Active
Viewed 96 times
2 Answers
1
Case 1: 2$^n$$^-$$^m$ > 2$^{2^m}$. So, as we go on setting n-m variables to constants, at each setting we get a subfunction with a truth-table of size 2$^m$. It is some part of the original truth-table of size 2$^n$. So, by setting n-m variables to constants, we cannot get more distinct subfunctions out from the original truth-table than 2$^{2^m}$. So, the number of distinct subfunctions of $f$ on Y in this case is upper-bounded by 2$^{2^m}$.
Example: Let us imagine a function on 32 variables. There are 2$^{32}$ rows in the truth-table. Let Y = $\{x_1, x_2\}$. There are 16 different functions on 2 variables and 2$^{30}$ ways to set variables {x$_3$,...x$_{32}$} to constants. As we go on and realize all possible settings to constants, we will not be able to exceed the limit of 16 different codomains.
Case 2: 2$^n$$^-$$^m$ < 2$^{2^m}$. As we go on setting n-m variables to constants, at each setting we get a subfunction with a truth-table of size 2$^m$. But since there are less variables to set to constants than there are different functions on m variables, not all of the 2$^{2^m}$ functions will be realized. So, the number of distinct subfunctions of $f$ on Y in this case is upper-bounded by 2$^n$$^-$$^m$.
Example: Let us imagine a function on 3 variables. There are 2$^{3}$ rows in the truth-table. Let Y = $\{x_1, x_2\}$. There are 16 different functions on 2 variables and 2$^{1}$ ways to set the variable {x$_3$} to a constant. As we go on and realize 2 possible settings to constants, we are not able to realize all 16 possible different codomains. We will just realize 2 codomains, and whether they are distinct or not depends on how $f$ was originally defined.
istex
- 11
0
In this context, a subfunction is a function $f(X_Y)$. The number of it is related to the sensitivity of the function on the other fixed variables $X_{\overline{Y}}$. For example, in $IP_n$, the sensitivity is low; while in CNF or DNF, it can be high. Anyways, here's how I believe he got this:
$\leq2^{2^{|Y|}}$: since the subfunction is a function of $X_Y$, the number of which is $2^{2^{|Y|}}$.
$\leq2^{|\overline{Y}|}$: each assignment to variables in $X_{\overline{Y}}$ may create at most a distinct subfunction (high sensitivity), and there are $2^{|\overline{Y}|}$ of assignments.
4Dmovie
- 1
-
Can you explain why the number of subfunctions it is the minimum of those two though and not the product? That's what I am going down the wrong path on. – ian.p.swift Jan 27 '20 at 23:16
-
@ian.p.swift Yes. Since the number of subfunctions has to be less than both $2^{2^{|Y|}}$ and $2^{|\overline{Y}|}$, it's less the minimum of the two. – 4Dmovie Feb 04 '20 at 18:25
-
Perhaps I should rephrase. Yes you can create $2^{2^{|Y|}}$ subfunctions by assigning variables functions to the variables in $Y$, but then with the variables in $\overline{Y}$ there are $2^{|\overline{Y}|}$ combinations. Since these two sets are disjoint, for every assignment to one of the sets, there is an independent assignment to the other set. So for each choice in set one, there is a choice in set two, which implies a product and not a minimum of the number of functions these two produce. What am I missing? – ian.p.swift Feb 11 '20 at 16:17