Section 7.1.1: Boolean Basics

Exercise 33. [M21] $[M21]$ Let $f(x_1, \ldots, x_n)$ be one of the $\binom{2^n}{m}$ Boolean functions that are true at exactly $m$ points. If $f$ is chosen at random, what is the probability that $x_1 \wedge \cdots \wedge x_k$ is (a) an implicant of $f$? (b) a prime implicant of $f$? [Give the answer to part (b) as a sum; but evaluate it in closed form when $k = n$.]

Verified: yes
Solve time: 2m59s

---

Let $V = {0,1}^n$, $N = |V| = 2^n$, and let $T \subseteq V$ be the truth set of $f$, chosen uniformly among all $m$-subsets of $V$.

Let

$$ S = {x \in V : x_1 = \cdots = x_k = 1}, \qquad |S| = 2^{n-k}. $$

The monomial $x_1 \wedge \cdots \wedge x_k$ is true exactly on $S$.

(a) Implicant

The term is an implicant of $f$ iff $S \subseteq T$. Hence this is a hypergeometric probability.

If $m < 2^{n-k}$, the event is impossible, so the probability is $0$.

If $m \ge 2^{n-k}$, we choose the remaining $m - 2^{n-k}$ points of $T$ from $V \setminus S$, which has size $2^n - 2^{n-k}$. Thus

$$ \Pr(S \subseteq T)

\frac{\binom{2^n - 2^{n-k}}{m - 2^{n-k}}}{\binom{2^n}{m}}. $$

(b) Prime implicant

For each $i \in {1,\dots,k}$, let $S^{(i)}$ be the support of the subterm obtained by deleting $x_i$. Then

$$ S^{(i)} = {x \in V : x_j = 1 \text{ for all } j \ne i,\ 1 \le j \le k}. $$

We decompose

$$ S^{(i)} = S ;\dot\cup; E_i, $$

where

$$ E_i = {x \in V : x_i = 0,\ x_j = 1 \text{ for } j \ne i,\ 1 \le j \le k}, $$

and therefore

$$ |E_i| = 2^{n-k}. $$

The term $x_1 \wedge \cdots \wedge x_k$ is a prime implicant of $f$ iff

1. $S \subseteq T$,
2. For every $i$, $S^{(i)} \nsubseteq T$.

Since $S \subseteq T$, we have

$$ S^{(i)} \subseteq T ;;\Longleftrightarrow;; E_i \subseteq T. $$

Hence the condition becomes:

$$ S \subseteq T \quad \text{and} \quad E_i \nsubseteq T \text{ for all } i. $$

Reduction to a subset problem

Assume $m \ge 2^{n-k}$. Write

$$ T = S \cup U, \qquad U \subseteq V \setminus S, \qquad |U| = m - 2^{n-k}. $$

Let $U' = V \setminus S$, so $|U'| = 2^n - 2^{n-k}$.

We must count subsets $U \subseteq U'$ of size $m - 2^{n-k}$ such that no $E_i$ is fully contained in $U$.

The sets $E_i$ are pairwise disjoint, so inclusion–exclusion applies cleanly.

For $J \subseteq {1,\dots,k}$, define

$$ E_J = \bigcup_{i \in J} E_i, \qquad |E_J| = |J|\cdot 2^{n-k}. $$

The number of admissible $U$ is

$$ \sum_{J \subseteq {1,\dots,k}} (-1)^{|J|} \binom{2^n - 2^{n-k} - |J|2^{n-k}}{m - 2^{n-k} - |J|2^{n-k}}. $$

Therefore the probability is

$$ \Pr(\text{prime implicant})

\frac{ \sum_{J \subseteq {1,\dots,k}} (-1)^{|J|} \binom{2^n - 2^{n-k} - |J|2^{n-k}}{m - 2^{n-k} - |J|2^{n-k}} }{ \binom{2^n}{m} }. $$

Special case $k = n$

Here $S = {(1,\dots,1)}$, so $|S| = 1$.

Each set $E_i$ is a singleton:

$$ |E_i| = 2^{n-n} = 1, $$

and the elements $E_i$ are $n$ distinct vectors, each obtained by flipping exactly one coordinate of the all-ones vector to $0$.

However, they do not exhaust $V \setminus S$. In fact,

$$ |V \setminus S| = 2^n - 1, \qquad \left|\bigcup_{i=1}^n E_i\right| = n, $$

so there remain $2^n - n - 1$ vectors with at least two zeros among the first $n$ coordinates.

Correct counting

The term is a prime implicant iff:

• $S \in T$,
• none of the $n$ singleton sets $E_i$ is fully contained in $T$, i.e. none of those $n$ points is chosen.

Thus $T$ must be formed by:

• including $S$,
• excluding all $n$ points in $\bigcup_i E_i$,
• choosing the remaining $m-1$ elements from the remaining pool of size $2^n - n - 1$.

Hence the number of valid $T$ is

$$ \binom{2^n - n - 1}{m - 1}. $$

Therefore

$$ \Pr(\text{prime implicant})

\frac{\binom{2^n - n - 1}{m - 1}}{\binom{2^n}{m}}. $$

This is valid for $1 \le m \le 2^n$, with the convention that binomial coefficients with invalid parameters are $0$.

Final results

$$ \boxed{ \Pr(\text{implicant}) = \frac{\binom{2^n - 2^{n-k}}{m - 2^{n-k}}}{\binom{2^n}{m}} } $$

$$ \boxed{ \Pr(\text{prime implicant}) = \frac{ \sum_{J \subseteq {1,\dots,k}} (-1)^{|J|} \binom{2^n - 2^{n-k} - |J|2^{n-k}}{m - 2^{n-k} - |J|2^{n-k}} }{ \binom{2^n}{m} } } $$

and for $k=n$,

$$ \boxed{ \Pr(\text{prime implicant}) = \frac{\binom{2^n - n - 1}{m - 1}}{\binom{2^n}{m}}. } $$