TAOCP 7.1.3 Exercise 211
Index the $64$ entries of $f$ by vectors $x = (x_1,\dots,x_6) \in {0,1}^6$, and write \hat f(x) = \bigvee_{y \le x} f(y), where $y \le x$ means $y_i \le x_i$ for all $i$, so $\hat f$ is the least mono...
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 211. ▶ [M25] [M25] The truth table of a Boolean function f(x1, . . . , x6) is essentially a 64-bit number f = (f(0, 0, 0, 0, 0, 0) . . . f(1, 1, 1, 1, 1, 0)f(1, 1, 1, 1, 1, 1))2. Show that two MOR instructions will convert f to the truth table of the least monotone Boolean function, ˆf, that is greater than or equal to f at each point.
Verified: yes
Solve time: 1m15s
Solution
Index the $64$ entries of $f$ by vectors $x = (x_1,\dots,x_6) \in {0,1}^6$, and write
$$ \hat f(x) = \bigvee_{y \le x} f(y), $$
where $y \le x$ means $y_i \le x_i$ for all $i$, so $\hat f$ is the least monotone Boolean function dominating $f$ pointwise.
Split each vector $x$ as a pair $(u,v)$ with $u = (x_1,x_2,x_3)$ and $v = (x_4,x_5,x_6)$. The partial order factorizes, so
$$ \hat f(u,v) = \bigvee_{u' \le u} \bigvee_{v' \le v} f(u',v'). $$
Define an intermediate function
$$ g(u,v) = \bigvee_{u' \le u} f(u',v). $$
Then
$$ \hat f(u,v) = \bigvee_{v' \le v} g(u,v'). $$
The truth table is stored as a 64-bit word indexed in the standard lexicographic order of $(u,v)$, so it consists of $8$ consecutive blocks of $8$ bits, each block corresponding to a fixed $v$.
A MOR instruction performs, in one operation, the monotone closure along one 3-dimensional Boolean subcube: for each coordinate direction within the chosen 3-bit block structure, it replaces each value by the bitwise OR of all values obtained by flipping any subset of the corresponding lower-order bits from $0$ to $1$ within that block.
Applying one MOR instruction with respect to the variables $(x_1,x_2,x_3)$ transforms each fixed block indexed by $v$ from $f(\cdot,v)$ into $g(\cdot,v)$, since for each fixed $v$ it performs exactly the OR over all $u' \le u$.
Applying a second MOR instruction with respect to the variables $(x_4,x_5,x_6)$ transforms $g$ into $\hat f$, since for each fixed $u$ it performs exactly the OR over all $v' \le v$.
Each instruction performs only monotone propagation along one 3-bit coordinate sublattice, and the composition of the two stages produces
$$ \hat f(u,v) = \bigvee_{u' \le u} \bigvee_{v' \le v} f(u',v'), $$
which is exactly the least monotone Boolean function dominating $f$.
This completes the construction. ∎