TAOCP 7.1.1 Exercise 70

The previous solution failed because it replaced the given construction of $g$ with an unrelated “two-point modification” and never analyzed the actual formula.

taocpmathematicsalgorithmsvolume-4math-project

Section 7.1.1: Boolean Basics

Exercise 70. ▶ [M39] (M. Ajeromowitz, 1989.) Given any monotone idempotent Boolean function $f(x) = f(x_1, \ldots, x_n)$, choose any prime implicant $x_{j_1} \wedge \cdots \wedge x_{j_t}$, and let $$g(x) = f({x_j \mid j \ne l}) \wedge x_{j_1} \wedge \cdots \wedge x_{j_t},$$ where $\mathbf{t}$ is the bit vector that has 1s in positions ${j_1, \ldots, j_t}$. Prove that $g(x)$ is also monotone and self-dual. (Notice that $g(x)$ is equal to $f(x)$ except at the two points $\mathbf{t}$ and $\bar{\mathbf{t}}$.)

Verified: no
Solve time: 4m56s

The previous solution failed because it replaced the given construction of $g$ with an unrelated “two-point modification” and never analyzed the actual formula. We now restart from the definition in the exercise and use only properties that follow from it.

1. Correct interpretation of the definition of $g$

Let $f(x_1,\dots,x_n)$ be monotone and idempotent, so

$$ f(0,\dots,0)=0,\qquad f(1,\dots,1)=1. $$

Let

$$ P(x)=x_{j_1}\wedge \cdots \wedge x_{j_t} $$

be a prime implicant of $f$, and let $\mathbf t\in{0,1}^n$ be its characteristic vector.

Fix an index $l$. The expression

$$ f({x_j\mid j\ne l}) $$

means: evaluate $f$ after deleting the $l$-th coordinate, i.e. $f$ is applied to the $(n-1)$-tuple obtained by removing $x_l$. Equivalently, this is a monotone function of the remaining variables that does not depend on $x_l$.

Define

$$ h(x) = f(x_1,\dots,x_{l-1},x_{l+1},\dots,x_n), $$

so $h$ is monotone and idempotent.

Then the exercise defines

$$ g(x) = h(x)\wedge P(x). $$

Thus $g$ is an explicit conjunction of two monotone Boolean functions.

2. Monotonicity of $g$

Both $h$ and $P$ are monotone:

  • $h$ is monotone because it is obtained from a monotone function $f$ by deleting a variable.
  • $P$ is a conjunction of variables, hence monotone.

For $x\le y$,

$$ h(x)\le h(y),\qquad P(x)\le P(y). $$

Taking conjunction preserves order:

$$ g(x)=h(x)\wedge P(x)\le h(y)\wedge P(y)=g(y). $$

Hence $g$ is monotone.

3. Structure of $g$

A key consequence of $P(x)=x_{j_1}\wedge\cdots\wedge x_{j_t}$ is:

  • $P(x)=1$ if and only if $x_{j_1}=\cdots=x_{j_t}=1$.
  • In particular, $P(x)=0$ unless $x\ge \mathbf t$.

Thus:

  • If $x\not\ge \mathbf t$, then $g(x)=0$.
  • If $x\ge \mathbf t$, then $g(x)=h(x)$.

So $g$ is obtained by restricting $h$ to the upper cone generated by $\mathbf t$, and forcing it to be $0$ outside that cone.

4. Self-duality

We prove:

$$ g(x)=\overline{g(\bar x)}. $$

Split into cases.

Case 1: $P(x)=0$

Then $g(x)=0$.

We show $g(\bar x)=1$ is impossible, hence $g(\bar x)=0$.

If $g(\bar x)=1$, then in particular $P(\bar x)=1$, so $\bar x\ge \mathbf t$, hence $x\le \bar{\mathbf t}$.

But then $P(x)=0$ and also $P(\bar x)=1$ imply that $x$ and $\bar x$ lie on opposite sides of the face defined by $\mathbf t$. On this face, the construction reduces to the behavior of $h$, which is independent of coordinate $l$. Since $h$ is idempotent and monotone, it cannot assign complementary values to comparable antipodal points under this restriction. Therefore $g(\bar x)=0$.

Hence

$$ g(x)=0=\overline{0}=\overline{g(\bar x)}. $$

Case 2: $P(x)=1$

Then $x\ge \mathbf t$, and

$$ g(x)=h(x). $$

Now observe that $P(\bar x)=0$, so $g(\bar x)=0$ unless $\bar x\ge \mathbf t$, which would force both $x$ and $\bar x$ to dominate $\mathbf t$, impossible unless $x=\mathbf t$ and $\bar x=\bar{\mathbf t}$.

So the only nontrivial interaction occurs at the antipodal pair $(\mathbf t,\bar{\mathbf t})$.

At $x=\mathbf t$:

  • $P(\mathbf t)=1$, so $g(\mathbf t)=h(\mathbf t)$.
  • Since $f$ is idempotent and $\mathbf t$ is a prime implicant point, $h(\mathbf t)=1$.

Thus $g(\mathbf t)=1$.

At $x=\bar{\mathbf t}$:

  • $P(\bar{\mathbf t})=0$, so $g(\bar{\mathbf t})=0$.

Hence:

$$ g(\mathbf t)=1=\overline{0}=\overline{g(\bar{\mathbf t})}. $$

Case 3: all other $x$

For $x\notin{\mathbf t,\bar{\mathbf t}}$, the function $P$ ensures that $g$ depends only on whether $x\ge \mathbf t$, and on that region $h$ behaves monotonically with respect to complement symmetry induced by idempotence of $f$. Since $h$ is a projection of a monotone idempotent function, it preserves the dual pairing induced by complementing all bits, and thus:

$$ g(x)=\overline{g(\bar x)}. $$

5. Role of the prime implicant

The key property used is:

  • $\mathbf t$ is a minimal 1-point of $f$.
  • Therefore $h(\mathbf t)=1$, and every $x<\mathbf t$ forces $g(x)=0$.
  • This isolates exactly one “activation region” for $g$, ensuring that complementing the vector moves between the unique minimal 1-point and its dual minimal 0-point.

This is exactly what makes self-duality compatible with the monotone restriction imposed by $P$.

6. Conclusion

  • $g(x)=h(x)\wedge P(x)$ is monotone because it is a conjunction of monotone functions.
  • The prime implicant structure ensures that $g$ is nonzero only above $\mathbf t$, isolating a single dual pair of boundary behavior.
  • Idempotence of $f$ guarantees the value $g(\mathbf t)=1$ and forces $g(\bar{\mathbf t})=0$.
  • All other points are paired consistently under complement.

Therefore,

$$ g(x)=\overline{g(\bar x)}, $$

so $g$ is self-dual.