TAOCP 7.1.1 Exercise 25
Let F(x_1,\ldots,x_n)=(x_1\vee x_2)\wedge(x_2\vee x_3)\wedge\cdots\wedge(x_{n-1}\vee x_n).
Exercise 25. [M21] [M21] How many prime implicants does $(x_1\vee x_2)\wedge(x_2\vee x_3)\wedge\cdots\wedge(x_{n-1}\vee x_n)$ have?
Verified: no
Solve time: 5m29s
Let
$$ F(x_1,\ldots,x_n)=(x_1\vee x_2)\wedge(x_2\vee x_3)\wedge\cdots\wedge(x_{n-1}\vee x_n). $$
A prime implicant of $F$ is a minimal conjunction of literals implying $F=1$.
1. Reduction to vertex covers
Since $F$ is monotone, every prime implicant can be taken to be of the form
$$ \bigwedge_{i\in S} x_i $$
for some $S\subseteq {1,\ldots,n}$.
Such a set $S$ forces each clause $(x_i\vee x_{i+1})$ to contain at least one variable from $S$, hence $S$ is a vertex cover of the path graph $P_n$.
Minimality of the implicant is equivalent to minimality of the vertex cover. Taking complements, if $I={1,\ldots,n}\setminus S$, then $I$ is a maximal independent set of $P_n$. Thus
$$ \text{prime implicants of }F ;\longleftrightarrow; \text{maximal independent sets of }P_n. $$
Let $a_n$ denote this number.
2. Recurrence for maximal independent sets
We analyze maximal independent sets of $P_n$ using the endpoint $1$.
Case 1: $1\in I$
Then $2\notin I$. Removing vertices $1,2$, the restriction of $I$ to ${3,\ldots,n}$ is a maximal independent set of $P_{n-2}$. Hence this case contributes $a_{n-2}$.
Case 2: $1\notin I$
Maximality forces $2\in I$, so $3\notin I$. Removing vertices $1,2,3$, the restriction of $I$ to ${4,\ldots,n}$ is a maximal independent set of $P_{n-3}$. Hence this case contributes $a_{n-3}$.
These cases are disjoint and exhaustive, so for $n\ge 4$,
$$ a_n = a_{n-2}+a_{n-3}. $$
3. Initial values
Direct inspection gives:
- $a_1=1$: ${1}$
- $a_2=2$: ${1},{2}$
- $a_3=2$: ${2},{1,3}$
4. Final answer
The number of prime implicants of $F$ equals $a_n$, where
$$ a_1=1,\quad a_2=2,\quad a_3=2,\quad a_n=a_{n-2}+a_{n-3}\ (n\ge 4). $$
No simpler Fibonacci closed form follows from this recurrence; the expression previously claimed is incorrect.
Thus the answer is exactly the sequence defined above.