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)
“Literature is a defense against the attacks of life. It says to life: “You can’t deceive me. I know your habits, foresee and enjoy watching all your reactions, and steal your secret by involving you in cunning obstructions that halt your normal flow.””
—Cesare Pavese (1908–1950)
“Have you never been moved by poor men’s fidelity, the image of you they form in their simple minds? Why should you always talk of their envy, without understanding that what they ask of you is not so much your worldly goods, as something very hard to define, which they themselves can put no name to; yet at times it consoles their loneliness; a dream of splendor, of magnificence, a tawdry dream, a poor man’s dream—and yet God blesses it!”
—Georges Bernanos (1888–1948)