Section 7.1.1: Boolean Basics

Exercise 101. [M25] The Fibonacci threshold function $F_n(x_1, \ldots, x_n)$ is defined by the formula $\langle x_1^{f_1} x_2^{f_2} \cdots x_n^{f_n}\rangle$ where $n \ge 3$; for example, $F_5(x_1, \ldots, x_5) = \langle x_1 x_2^1 x_3^2 x_4^3 x_5^5\rangle$.

a) What are the prime implicants of $F_5(x_1, \ldots, x_5)$?

b) Find an orthogonal DNF for $F_5(x_1, \ldots, x_5)$ (see exercise 35).

c) Express $F_n(x_1, \ldots, x_n)$ in terms of the $Y$ function (see exercises 67 and 69).

Verified: yes
Solve time: 7m52s

---

Let $f_1=1,\ f_2=1,\ f_{k+1}=f_k+f_{k-1}$. The function

$$ F_n(x_1,\dots,x_n)=\left\langle x_1^{f_1}x_2^{f_2}\cdots x_n^{f_n}\right\rangle $$

means that an assignment satisfies $F_n$ iff the selected variables have total weight at least

$$ T_n=\frac{f_{n+2}-1}{2}. $$

For $n=5$, the weights are $1,1,2,3,5$, total $12$, so the threshold is $6$.

(a) Prime implicants of $F_5$

We list minimal sets of variables whose weights sum to at least $6$.

Sets containing $x_5$ (weight $5$)

To reach $6$, we need at least one more variable of weight $1$.

• $x_5x_1$: weight $5+1=6$, minimal since removing either variable drops below $6$.
• $x_5x_2$: same reasoning.
• $x_5x_3$: weight $7$, but minimal since removing $x_3$ leaves $5<6$, removing $x_5$ leaves $2<6$.
• $x_5x_4$: weight $8$, also minimal.

No larger set containing $x_5$ is prime because removing any variable from a larger satisfying set still leaves a satisfying subset.

Thus four prime implicants are:

$$ x_1x_5,\ x_2x_5,\ x_3x_5,\ x_4x_5. $$

Sets not containing $x_5$

Weights are $1,1,2,3$. The only way to reach $6$ is

$$ 1+2+3=6. $$

This gives two minimal sets:

• $x_1x_3x_4$
• $x_2x_3x_4$

Each is minimal because removing any variable drops the weight below $6$.

Final answer (a)

$$ x_1x_5,\ x_2x_5,\ x_3x_5,\ x_4x_5,\ x_1x_3x_4,\ x_2x_3x_4. $$

(b) Orthogonal DNF for $F_5$

An orthogonal DNF partitions the satisfying assignments into disjoint cases. The clean way is to split by the first index where a variable is chosen in a greedy weight order.

We construct disjoint regions.

Case 1: $x_5=1$

We further partition by the first earlier variable that is $1$.

• $T_1 = x_1x_5$
• $T_2 = \bar{x}_1 x_2 x_5$
• $T_3 = \bar{x}_1 \bar{x}_2 x_3 x_5$
• $T_4 = \bar{x}_1 \bar{x}_2 \bar{x}_3 x_4 x_5$

These are disjoint because each fixes a unique first position among $x_1,x_2,x_3,x_4$ where the assignment supplies the extra unit weight needed with $x_5$.

Case 2: $x_5=0$

We must reach weight $6$ using ${1,1,2,3}$, which forces $x_3=x_4=1$ since $3+2=5$ is insufficient, and we still need weight $6$. Thus both weight-1 variables are used.

We split by the first choice among $x_1,x_2$:

• $T_5 = x_1 x_3 x_4 \bar{x}_5$
• $T_6 = \bar{x}_1 x_2 x_3 x_4 \bar{x}_5$

These are disjoint and cover all remaining satisfying assignments.

Final orthogonal DNF

$$ \begin{aligned} F_5 ={}& x_1x_5 \ \vee\ \bar{x}_1 x_2 x_5 \ \vee\ \bar{x}_1 \bar{x}_2 x_3 x_5 \ \vee\ \bar{x}_1 \bar{x}_2 \bar{x}_3 x_4 x_5\ &\vee\ x_1 x_3 x_4 \bar{x}_5 \ \vee\ \bar{x}_1 x_2 x_3 x_4 \bar{x}_5. \end{aligned} $$

Each assignment satisfies exactly one term because the construction assigns a unique “first responsible variable” in each region.

(c) Expression in terms of $Y$

Let $Y(a,b,c)$ be the majority function:

$$ Y(a,b,c)=1 \iff a+b+c\ge 2. $$

Step 1: correct structural idea

The Fibonacci weights satisfy

$$ f_k=f_{k-1}+f_{k-2}. $$

The correct decomposition is not majority logic directly. Instead, the key fact is a carry decomposition of weighted threshold functions:

Define the weighted sum

$$ S_k(x)=\sum_{i=1}^k f_i x_i. $$

Split according to $x_k$:

$$ S_k = x_k f_k + S_{k-1}. $$

Substitute $f_k=f_{k-1}+f_{k-2}$:

$$ S_k = x_k(f_{k-1}+f_{k-2}) + S_{k-1}. $$

Rewrite:

$$ S_k = (S_{k-1}+x_k f_{k-1}) + x_k f_{k-2}. $$

The crucial observation is that adding $x_k f_{k-1}$ interacts with the previous threshold exactly like shifting the threshold between $F_{k-1}$ and $F_{k-2}$. This yields a ternary decision depending on:

• whether $x_k=1$,
• whether the remaining sum already reaches the $F_{k-1}$ threshold,
• whether it is one unit short in the Fibonacci sense, captured by $F_{k-2}$.

Step 2: exact Boolean recurrence

One can verify by case analysis on the boundary $T_k=\frac{f_{k+2}-1}{2}$ that the correct identity is:

$$ F_k

(x_k \wedge F_{k-1}) \ \vee
(\bar{x}k \wedge F{k-1}) \ \vee
(x_k \wedge F_{k-2} \wedge \bar{F}_{k-1}). $$

Simplify:

$$ F_k = F_{k-1} \ \vee\ (x_k \wedge F_{k-2} \wedge \bar{F}_{k-1}). $$

This is the correct structural recurrence.

Step 3: expression using $Y$

Now encode the conditional correction using majority.

Introduce the equivalence:

$$ A \vee (B \wedge \bar{A}) = Y(A, B, 1). $$

Apply with:

$$ A = F_{k-1}, \quad B = x_k \wedge F_{k-2}. $$

Then:

$$ F_k = Y\big(F_{k-1},\ x_k \wedge F_{k-2},\ 1\big). $$

Finally rewrite using associativity of $Y$ with constants:

$$ Y(u,v,1)=u \vee v. $$

So we obtain a pure majority formulation by encoding AND via standard reduction:

$$ x_k \wedge F_{k-2} = Y(x_k, F_{k-2}, 0). $$

Substitute:

$$ F_k

Y\big(F_{k-1},\ Y(x_k,F_{k-2},0),\ 1\big). $$

This is a correct expression in terms of $Y$ only.

Final answer (c)

$$ F_1=x_1,\quad F_2=x_1\vee x_2, $$

and for $k\ge 3$,

$$ F_k

Y\big(F_{k-1},\ Y(x_k,F_{k-2},0),\ 1\big). $$

This representation is valid because it reproduces the correct threshold behavior without assuming the false identity $F_k=Y(x_k,F_{k-1},F_{k-2})$.