Example 3-8 Find the number of Boolean functions composed entirely of $n$ Boolean variables.



The text above is translated into English, preserving the original text's line breaks and format.
Before discussing Boolean functions with $n$ Boolean variables, let's start with $n=2$, two Boolean variables $x_{1}, x_{2}$, which can take values from $00, 01, 10$, to $11$, a total of $2^{2}=4$ states. For these 4 states, the Boolean function values can have $2^{4}=16$ possibilities, as shown in Table 3-1.
Taking $f_{7}$ and $f_{10}$ as examples, the calculations are as follows: where $f_{7}=\left(x_{1} \vee x_{2}\right) \wedge\left(x_{1} \vee x_{2}\right), f_{10}=\left(x_{1} \vee \cdot x_{2}\right) \wedge\left(x_{1} \vee x_{2}\right)$. The operation rules for $\vee$ and $\wedge$ are:
In fact, $x_{1} \vee x_{2}=f_{8}, \quad x_{1} \vee x_{2}=f_{15}, \quad x_{1} \vee x_{2}=f_{14}, \quad x_{1} \vee x_{2}=f_{12}$.
From the table above, we can see that $f\left(x_{1}, x_{2}\right)$ corresponds to 4-bit 0,1 symbols, and it includes unary Boolean functions and Boolean constants, which can be considered as special cases of binary Boolean functions. Truly binary Boolean functions number 10.
For an $n$-ary Boolean function $f\left(x_{1}, x_{2}, \cdots, x_{n}\right)$, the states of the variables $x_{1}, x_{2}, \cdots, x_{n}$ range from $(\underbrace{0,0, \cdots, 0}_{n \uparrow})$ to $\{\underbrace{1,1, \cdots, 1}_{n \uparrow})$, a total of $2^{n}$ states. The 0,1 symbol strings of $2^{n}$ dimensions have $2^{2^{n}}$ possibilities, meaning the number of $n$-ary Boolean functions is $2^{2^{n}}$, where the class where $x_{i}$ does not appear is denoted as $A_{i}, i=1,2, \cdots, n$. According to the principle of inclusion-exclusion, the number of Boolean functions completely determined by Boolean variables is
$$
\begin{aligned}
\left|\bar{A}_{1} \cap \bar{A}_{2} \cap \cdots \cap \bar{A}_{n}\right|= & 2^{2^{n}}-C(n, 1) 2^{2^{n}}+C(n, 2) 2^{2^{n}}{ }^{2}-\cdots \\
& +(-1)^{k} C(n, k) 2^{2^{k}}+\cdots+(-1)^{n} C(n, n) 2
\end{aligned}
$$
For $n=2$:
$$
\left|\bar{A}_{1} \cap \bar{A}_{2}\right|=2^{2^{2}}-C(2,1) 2^{2}+C(2,2) 2=16-8+2=10
$$

These 10 completely binary Boolean functions are:
$$
\begin{array}{l}
x_{1} \wedge x_{2}, \quad x_{1} \wedge \bar{x}_{2}, \quad \bar{x}_{1} \wedge x_{2}, \quad \bar{x}_{1} \wedge \bar{x}_{2}, \quad x_{1} \vee x_{2}, \\
\vec{x}_{1} \vee \vec{x}_{2}, \quad x_{1} \vee \vec{x}_{2}, \quad \bar{x}_{1} \vee x_{2}, \quad\left(x_{1} \vee x_{2}\right) \wedge\left(\bar{x}_{1} \vee \bar{x}_{2}\right), \\
\left(x_{1} \vee \bar{x}_{2}\right) \wedge\left(\bar{x}_{1} \vee x_{2}\right) \\
\end{array}
$$