Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

Negation Normal Form

A concept is in Negation Normal Form (NNF) if all occurences of negations in it are in front of atomic concepts.

Every \(\mathcal{ALC}\) concept can be transformed into an equivalent one in NNF using the following rules:

\[ \begin{aligned} NNF(C) &= C, \text{ if } C \text{ is atomic }\\ NNF(\neg C) &= \neg C, \text{ if } C \text{ is atomic}\\ NNF(\neg \neg C) &= NNF(C) \\ NNF(C \sqcup D) &= NNF(C) \sqcup NNF(D) \\ NNF(C \sqcap D) &= NNF(C) \sqcap NNF(D) \\ NNF(\neg(C \sqcup D)) &= NNF(\neg C) \sqcap NNF(\neg D) \\ NNF(\neg(C \sqcap D)) &= NNF(\neg C) \sqcup NNF(\neg D) \\ NNF(\forall R.C) &= \forall R.NNF(C) \\ NNF(\exists R.C) &= \exists R.NNF(C) \\ NNF(\neg \forall R.C) &= \exists R.NNF(\neg C) \\ NNF(\neg \exists R.C) &= \forall R.NNF(\neg C) \\ \end{aligned} \]


Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.