Graph Theory37 sections · 1633 units
Open in Course

Converting OR to Implication

(The core transformation)

Take a clause "a OR b". This says at least one is true. Flip it around to see the implications. If a is false, then b is true to satisfy the clause. If b is false, then a is true. In graph terms: add edge (NOT a → b) and edge (NOT b → a).

These two edges represent the OR constraint perfectly. Every clause in your formula becomes exactly two directed edges in the graph. The graph has 2n2n nodes (for n variables) and 2m2m edges (for m clauses).