Concept

# Negation normal form

Summary
In mathematical logic, a formula is in negation normal form (NNF) if the negation operator (\lnot, ) is only applied to variables and the only other allowed Boolean operators are conjunction (\land, ) and disjunction (\lor, ). Negation normal form is not a canonical form: for example, a \land (b\lor \lnot c) and (a \land b) \lor (a \land \lnot c) are equivalent, and are both in negation normal form. In classical logic and many modal logics, every formula can be brought into this form by replacing implications and equivalences by their definitions, using De Morgan's laws to push negation inwards, and eliminating double negations. This process can be represented using the following rewrite rules (Handbook of Automated Reasoning 1, p. 204): :\begin{align} A \Rightarrow B &~\to~ \lnot A \lor B \ A \Leftrightarrow B &~\to~ (\lnot A \lor B) \land (A \lor \lnot B) \ \lnot (A \lor B) &~\to~ \lnot A \land \
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications

Related people

Related units