TAOCP 7.1.1 Exercise 130
This part is correct in the proposed solution, and we briefly restate it cleanly.
Exercise 130. [M31] According to Table 3, there are 168 monotone Boolean functions of four variables. But some of them, like $x \wedge y$, depend on only three variables or fewer.
a) How many 4-variable monotone Boolean functions actually involve every variable? b) How many of those functions are distinct under permutation, as in Table 4?
Verified: no
Solve time: 5m55s
(a) Functions involving every variable
This part is correct in the proposed solution, and we briefly restate it cleanly.
Let $M(n)$ be the number of monotone Boolean functions on $n$ variables. From Table 3,
$$ M(4)=168,\quad M(3)=20,\quad M(2)=6,\quad M(1)=3,\quad M(0)=2. $$
Let $A_i$ be the set of monotone functions on $x_1,x_2,x_3,x_4$ that do not depend on $x_i$. Then
$$ |A_i|=M(3),\quad |A_i\cap A_j|=M(2),\quad |A_i\cap A_j\cap A_k|=M(1),\quad |A_1\cap A_2\cap A_3\cap A_4|=M(0). $$
By inclusion–exclusion, the number $E(4)$ of functions depending on all four variables is
$$ E(4)=168-\binom{4}{1}20+\binom{4}{2}6-\binom{4}{3}3+\binom{4}{4}2 =168-80+36-12+2=114. $$
So,
$$ \boxed{114}. $$
(b) Distinct functions under permutation of variables
The original argument incorrectly used cumulative orbit counts $T_k$. The correct approach is to separate monotone functions by exact number of essential variables and then pass to orbits carefully.
We proceed in two steps:
Step 1. Orbit structure in lower dimensions
Let $E(n)$ denote the number of monotone Boolean functions on $n$ variables that depend on all $n$ variables.
For $n=2$
$$ M(2)=6,\quad M(1)=3,\quad M(0)=2. $$
$$ E(2)=6-2\cdot 3+2=2. $$
So there are exactly two fully essential functions:
$$ x_1\wedge x_2,\quad x_1\vee x_2. $$
Thus the number of $S_2$-orbits of fully essential functions is
$$ o_2=2. $$
For $n=3$
$$ M(3)=20,\quad M(2)=6,\quad M(1)=3,\quad M(0)=2. $$
$$ E(3)=20-3\cdot 6+3\cdot 3-2=9. $$
Now classify orbits under $S_3$.
A function on 3 variables that is not fully essential depends on at most 2 variables, hence arises from a 2-variable function by adding a dummy variable. Each $S_2$-orbit induces exactly one $S_3$-orbit of inessential functions.
There are 5 $S_2$-orbits total, and all embed into 3 variables as distinct $S_3$-orbits. Hence there are 5 orbits with at most 2 essential variables.
Therefore the number of $S_3$-orbits of fully essential functions is
$$ o_3 = 10 - 5 = 5. $$
Step 2. Passage to 4 variables
Total number of monotone Boolean functions on 4 variables up to permutation is 39 (Table 4).
Functions on 4 variables that are not fully essential depend on at most 3 variables. Each $S_3$-orbit embeds into 4 variables by choosing a dummy variable, and all such embeddings are equivalent under $S_4$. Hence:
- Each $S_3$-orbit corresponds to exactly one $S_4$-orbit of functions with at most 3 essential variables.
- There are 10 such $S_3$-orbits in total.
Thus, the number of $S_4$-orbits of functions with at most 3 essential variables is 10.
Step 3. Final count
Subtract from the total number of orbits:
$$ \text{fully essential orbits} = 39 - 10 = 29. $$
Final answer
(a)
$$ \boxed{114} $$
(b)
$$ \boxed{29} $$