Editing Rewriting (section)

=== Logic ===
In [[logic]], the procedure for obtaining the [[conjunctive normal form]] (CNF) of a formula can be implemented as a rewriting system.<ref name="MarriottStuckey1998">{{cite book|author1=Kim Marriott|author2=Peter J. Stuckey|title=Programming with Constraints: An Introduction|url=https://books.google.com/books?id=jBYAleHTldsC&q=%22conjunctive+normal+form%22+%28%22%28rewrite+OR+rewriting%29+%28system+OR+engine%29%22+OR+%22term+rewriting%22%29+-wikipedia&pg=PA436|year=1998|publisher=MIT Press|isbn=978-0-262-13341-8|pages=436–}}</ref> For example, the rules of such a system would be:

:<math>\neg\neg A \to A</math> ([[double negation elimination]])
:<math>\neg(A \land B) \to \neg A \lor \neg B</math> ([[De Morgan's laws]])
:<math>\neg(A \lor B)  \to \neg A \land\neg B</math>
:<math> (A \land B) \lor C \to (A \lor C) \land (B \lor C)</math> ([[distributivity]])
:<math> A \lor (B \land C) \to (A \lor B) \land (A \lor C),</math><ref group=note>This variant of the previous rule is needed since the commutative law ''A''∨''B'' = ''B''∨''A'' cannot be turned into a rewrite rule. A rule like ''A''∨''B'' → ''B''∨''A'' would cause the rewrite system to be nonterminating.</ref>
For each rule, each [[variable (mathematics)|variable]] denotes a subexpression, and the symbol (<math>\to</math>) indicates that an expression matching the left hand side of it can be rewritten to one matching the right hand side of it. In such a system, each rule is a [[logical equivalence]], so performing a rewrite on an expression by these rules does not change the truth value of it. Other useful rewriting systems in logic may not preserve truth values, see e.g. [[equisatisfiability]].