1 of 2

8.1 Negation Normal Form (NNF)

Sentences in BOOL can be hard to read. Consider this one:


What does that actually mean?

Especially when there are a lot of negations around other connectives, our brains have a hard time parsing the formula.

If all the negations are narrow scope, though, we have an easier time understanding it:


That just says that Pia or Quinn is guilty, but Raquel and Stan are innocent.

Negation Normal Form (NNF): Any negations are narrow scope.

When sentences are like that, with all negations narrow scope, it is in negation normal form (NNF).

Let’s give you a chance to apply the concept.

When a sentence is in NNF, then the basic units in it are atomic sentences and negations of atomic sentences. Those are then combined with &s and vs.

Literals: atomic sentences and negations of atomic sentences.

It is helpful to have a term to refer to those basic units. We will call them literals. A literal is just an atomic sentence or the negation of an atomic sentence.

In the next section we’ll see how to use equivalences to put any sentence into NNF and make it easier to understand.