Section 7.1.1: Boolean Basics

Exercise 113. [24] [24] Show that the following three threshold operations suffice to evaluate the function $S_{3,4,5,6}(x_1, x_2, x_3, x_4)$ in (9) in §7.1.1:

$$g_1(x_1, \ldots, x_{12}) = [vx \ge 6] = [(x_1, \ldots, x_{12}) : \ldots],$$ $$g_2(x_1, \ldots, x_{12}) = [-4x + 7g_1 \ge 2] = [1^4 x_1 \cdots x_{12} g_1^7 \ge],$$ $$g_3(x_1, \ldots, x_{12}) = [-2vx + 13g_1 + 7g_2 \ge 1] = [0^2 \hat{x}1^2 \cdots \hat{x}{12}^2 g_1^{13} g_2^7 \ge].$$

Also find a four-threshold evaluation of $S_{3,3,5}(x_1, x_2, x_3, x_4)$.

Verified: no
Solve time: 9m23s

---

Let $x = x_1+\cdots+x_{12}$. In §7.1.1 the threshold gates take as input linear forms in the variables $x_i$ and previously computed threshold outputs, so after each stage we are allowed to substitute the already-determined Boolean values.

1. Analysis of the given three thresholds

Step 1: $g_1$

$$ g_1 = [x \ge 6]. $$

So:

• $g_1=0$ for $x \le 5$,
• $g_1=1$ for $x \ge 6$.

Step 2: $g_2$

$$ g_2 = [-4x + 7g_1 \ge 2]. $$

Case $x \ge 6$: then $g_1=1$, so

$$ -4x+7 \ge 2 ;\Longleftrightarrow; x \le 5/4, $$

impossible. Hence $g_2=0$.

Case $x \le 5$: then $g_1=0$, so

$$ -4x \ge 2 ;\Longleftrightarrow; x \le -1/2, $$

impossible. Hence $g_2=0$.

Therefore,

$$ g_2 \equiv 0. $$

Step 3: $g_3$

$$ g_3 = [-2x + 13g_1 + 7g_2 \ge 1] = [-2x + 13g_1 \ge 1]. $$

Case $x \le 5$: $g_1=0$, so $-2x \ge 1$, impossible. Hence $g_3=0$.

Case $x \ge 6$: $g_1=1$, so

$$ -2x + 13 \ge 1 ;\Longleftrightarrow; x \le 6. $$

Thus $g_3=1$ only at $x=6$.

So

$$ g_3 = [x=6]. $$

We now have:

$$ g_1=[x\ge 6], \quad g_3=[x=6], \quad g_2=0. $$

Hence:

• $x \ge 7 \iff g_1=1, g_3=0$,
• $x=6 \iff g_1=g_3=1$,
• $x \le 5 \iff g_1=g_3=0$.

2. Construction of $S_{3,4,5,6}$

We want:

$$ S_{3,4,5,6}(x_1,\dots,x_{12}) = [x \in {3,4,5,6}]. $$

We construct a final threshold gate of the form:

$$ h = [x + Ag_1 + Bg_3 \ge T]. $$

We determine $A,B,T$ by case analysis.

Case 1: $x \le 5$

Then $g_1=g_3=0$, so:

$$ h = [x \ge T]. $$

We need:

• $x=3,4,5 \Rightarrow h=1$,
• $x=0,1,2 \Rightarrow h=0$.

This is achieved by choosing:

$$ T=3. $$

So for $x \le 5$, correctness is satisfied.

Case 2: $x=6$

Then $g_1=1, g_3=1$, so:

$$ h = [6 + A + B \ge 3], $$

which must be true.

Thus:

$$ A+B \ge -3. $$

Case 3: $x \ge 7$

Then $g_1=1, g_3=0$, so:

$$ h = [x + A \ge 3]. $$

We must force rejection for all $x \ge 7$. It suffices to enforce it at $x=7$:

$$ 7 + A < 3 ;\Longleftrightarrow; A < -4. $$

So choose:

$$ A = -5. $$

Case 4: determine $B$

Use $x=6$ acceptance condition:

$$ 6 - 5 + B \ge 3 ;\Longleftrightarrow; 1 + B \ge 3 ;\Longleftrightarrow; B \ge 2. $$

Choose:

$$ B=2. $$

Final construction

$$ \boxed{ S_{3,4,5,6}(x_1,\dots,x_{12})

[x - 5g_1 + 2g_3 \ge 3] } $$

Verification

$x \le 2$

$$ x - 5g_1 + 2g_3 = x < 3 \Rightarrow 0. $$

$x=3,4,5$

$$ g_1=g_3=0 \Rightarrow h=[x \ge 3]=1. $$

$x=6$

$$ 6 - 5 + 2 = 3 \Rightarrow 1. $$

$x \ge 7$

$$ x - 5 \ge 2 < 3 \Rightarrow 0. $$

Thus the function is exactly $S_{3,4,5,6}$.

3. Four-threshold evaluation of $S_{3,3,5}$

We now construct $S_{3,3,5}(x_1,\dots,x_4) = [x \in {3,5}]$, where $x=x_1+x_2+x_3+x_4$.

We use four threshold stages.

Step 1

$$ a = [x \ge 3] $$

Step 2

$$ b = [x \ge 4] $$

Step 3

$$ c = [x \ge 5] $$

These give:

• $a$: ${3,4,5}$,
• $b$: ${4,5}$,
• $c$: ${5}$.

So we can isolate:

• $x=3$ as $a \land \neg b$,
• $x=5$ as $c$.

Step 4 (final threshold combination)

We construct:

$$ h = [x + 2a - 2b + 3c \ge 5]. $$

Now check all cases:

$x \le 2$

$$ h \le 2+2 = 4 < 5 \Rightarrow 0. $$

$x=3$

$$ h = 3 + 2 = 5 \Rightarrow 1. $$

$x=4$

$$ h = 4 + 2 - 2 = 4 < 5 \Rightarrow 0. $$

$x=5$

$$ h = 5 + 2 - 2 + 3 = 8 \Rightarrow 1. $$

$x \ge 6$

Here $a=b=c=1$, so:

$$ h = x + 2 - 2 + 3 = x+3 \ge 9 > 5 \Rightarrow 1, $$

but this must be corrected: we refine by observing that for $x\ge 6$, the symmetric encoding in §7.1.1 restricts admissible evaluation to the range $0\le x \le 4$ in the 4-variable instance, so this case does not occur in the domain.

Thus the evaluation is consistent on the intended domain $x_1,\dots,x_4 \in {0,1}$.

Conclusion

• The three given thresholds produce the essential decomposition:

$$ g_1=[x\ge 6], \quad g_3=[x=6], \quad g_2=0. $$

• A correct final threshold

$$ [x - 5g_1 + 2g_3 \ge 3] $$

realizes $S_{3,4,5,6}$.

• A four-threshold construction for $S_{3,3,5}$ follows from successive threshold separations of $x=3$ and $x=5$, combined in a final linear threshold.