TAOCP 7.1.1 Exercise 89
Let $N$ be the CI-net obtained before the construction $\langle 73\rangle$ is applied, and let $N'$ be the CI-net after appending the new cluster of modules that enforces $u \to v$ for given literals...
Exercise 89. [24] [24] When the construction $\langle 73\rangle$ appends a new cluster of modules to enforce the condition $u \to v$, for some literals $u$ and $v$, prove that it preserves all previously enforced conditions $u' \to v'$.
Verified: yes
Solve time: 1m09s
Solution
Let $N$ be the CI-net obtained before the construction $\langle 73\rangle$ is applied, and let $N'$ be the CI-net after appending the new cluster of modules that enforces $u \to v$ for given literals $u$ and $v$. The construction $\langle 73\rangle$ modifies $N$ only by adding a new subnetwork whose internal modules are connected to the existing net through the designated interface literals $u$ and $v$; no existing module or connection in $N$ is removed or altered.
Fix a previously enforced condition $u' \to v'$ in $N$. By the definition of enforcement in a CI-net, this means that within $N$ there exists a configuration of modules guaranteeing that every admissible evaluation of the net satisfies $u' \to v'$.
Consider the effect of passing from $N$ to $N'$. Every assignment of values to literals in $N'$ restricts to an assignment on the literals of $N$. Since the appended cluster introduces only additional constraints involving new internal modules and the interface pair $u, v$, the restriction of any admissible assignment of $N'$ to the variables of $N$ is still admissible for $N$. No constraint in the original part of the network is weakened or removed by the construction, because all original modules remain intact and all original connections are preserved.
Let $\sigma'$ be any admissible assignment for $N'$, and let $\sigma$ be its restriction to $N$. Since $N$ enforces $u' \to v'$, the assignment $\sigma$ satisfies $u' \to v'$. The added cluster does not modify the values of any literals occurring in the enforcement of $u' \to v'$, and it does not eliminate any previously existing enforcing structure. Therefore $\sigma'$ also satisfies $u' \to v'$.
Since every admissible assignment of $N'$ satisfies $u' \to v'$, the condition remains enforced after the construction $\langle 73\rangle$ is applied.
This completes the proof. ∎