Graph Theory37 sections · 1633 units
Open in Course

Why This Works

(Logic equivalence)

The statement "a OR b" is logically equivalent to "NOT a → b". They mean the same thing in boolean logic. If you walk into NOT a in the graph (meaning a is false), you are forced to walk into b (meaning b must be true). That is exactly what OR requires.

The reverse edge handles the symmetric case. Together they capture the constraint perfectly. This conversion is the foundation of the entire 22-SAT algorithm. It turns logic into graph structure.