Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav08:homework03 [2008/03/06 19:26] vkuncak |
sav08:homework03 [2008/03/06 19:27] vkuncak |
||
|---|---|---|---|
| Line 22: | Line 22: | ||
| \end{array} | \end{array} | ||
| \] | \] | ||
| - | Note that each introduced equivalence such as $(p_i \leftrightarrow (q \land r))$ can generate several clauses. Suppose now that $F$ is in negation-normal form. Show that we can replace some of these equivalences with implications. Write the new transformation rules and prove that they are satisfiability-preserving. | + | Note that each introduced equivalence, such as, $(p_i \leftrightarrow (q \land r))$ can generate several clauses. Suppose now that $F$ is in negation-normal form. Show that we can replace some of these equivalences with implications. Write the new transformation rules and prove that they produce equisatisfiable formulas. |
| ===== Problem 3: Equivalence Preserving Transformation to CNF ===== | ===== Problem 3: Equivalence Preserving Transformation to CNF ===== | ||