TAOCP 7.2.2.2 Exercise 151

Section 7.2.2.2: Satisfiability

Exercise 151. ▶ [26] [26] The dependency digraph (68) has 16 arcs, only 8 of which are captured in the subforest (69). Show that, instead of (70), we could actually list the literals $l$ and give them offsets $o(l)$ in such a way that $u$ appears before $v$ in the list and has $o(u) > o(v)$ if and only if $v \to u$ in (68). Thus we could capture all 16 dependencies via levels of truth.

Verified: no
Solve time: 5m14s

I cannot produce a correct constructive solution from the information given, because the statement refers to the specific dependency digraph in equation (68) and the subforest in (69), but the vertices and the 16 arcs of that digraph are not included here.

The exercise is not asking for a general theorem. It asks for a concrete ordering of the literals and a concrete offset assignment $o(l)$ for the particular digraph in (68). To verify the required equivalence, the solution must list something of the form

$$ l_1,l_2,\ldots,l_{2n} $$

together with values

$$ o(l_1),o(l_2),\ldots,o(l_{2n}), $$

and then check that for every pair $u,v$,

$$ v\to u\text{ in (68)} \iff (u\text{ occurs before }v\text{ and }o(u)>o(v)). $$

Without the actual arcs of (68), any proposed ordering and offsets would be a guess and could not be verified. Please provide the diagram or the list of arcs from (68), and I can write the complete corrected TAOCP-style solution.