Negation normal form is an elementary canonical form in mathematical logic. There are similar requirements for negation normal form in different logic fragments.
In predicate logic, a logical formula is in negation normal form if negation occurs only immediately above elementary propositions, and {} are the only allowed Boolean connectives. In classical logic each formula can be brought into this form by replacing implications and equivalences by their definitions, using De Morgan's laws to push negation inside, and eliminating double negations. This process can be represented using the following rewrite rules:
A formula in negation normal form can be put into the stronger conjunctive normal form or disjunctive normal form by applying the distributivity laws.
Famous quotes containing the words negation, normal and/or form:
“Friendship, according to Proust, is the negation of that irremediable solitude to which every human being is condemned.”
—Samuel Beckett (1906–1989)
“Normality highly values its normal man. It educates children to lose themselves and to become absurd, and thus to be normal. Normal men have killed perhaps 100,000,000 of their fellow normal men in the last fifty years.”
—R.D. (Ronald David)
“Quite generally, the familiar, just because it is familiar, is not cognitively understood. The commonest way in which we deceive either ourselves or others about understanding is by assuming something as familiar, and accepting it on that account; with all its pros and cons, such knowing never gets anywhere, and it knows not why.... The analysis of an idea, as it used to be carried out, was, in fact, nothing else than ridding it of the form in which it had become familiar.”
—Georg Wilhelm Friedrich Hegel (1770–1831)