A normal form is a notion a restricted form into which things can be brought, preserving meaning, by means of a normalization procedure. A normalization procedure defines a mapping of everything into something, such that eventually (by reapplying it often enough) everything is transformed into something fixed (a form that is mapped onto itself).

For example: consider character sequences, like the sentences I'm writing here. In any character sequence, I can swap the first two adjacent characters that are not in alphabetical order. This is a normalization procedure, since it will eventually put any sequence into a form that is no longer modified, namely, alphabetical order. Sequences in alphabetical order are the normal forms in this case. Except that this procedure doesn't preserve the meaning of character sequences, unless we are using them for some specific purpose in which the order of the characters doesn't matter.

Normal forms are often important when dealing with formalisms. Many formalisms allow the same meaning to be expressed in many different ways, and it is often desirable to simplify or standardize the way in which this is done.

For example, in first-order predicate logic, a form is a logical expression, containing quantors ('for all' or 'there exists a'), variables, and logical connectives ('and', 'or', 'not', etcetera). It turns out that some of these elements can be systematically eliminated from the expression without affecting its meaning. For example, every 'and' can be described in terms of 'or' and 'not', and every use of the 'for all' quantor can be described in terms of 'not' and 'there exists a'. So there are normal forms for predicate logic in which these constructs do not occur.

So a normal form is a subset of expressions of a formalism that is no less expressive than the full formalism, and a known procedure must exist to convert arbitrary expressions from the full formalism into the given normal form.

A normal form does not necessarily define a unique representation for each meaning: it may still be the case that two different expressions have the same meaning, even though they are both in normal form.

Different normal forms can be defined for the same formalism. For instance, in predicate logic, we may choose to eliminate the 'for all' quantor, but it is just as well possible to eliminate the 'there exists a' quantor instead.

To take examples from a different field: in formal language theory, formalisms describe languages, that is, sets of finite strings of items. An example of such a formalism is the grammar. A grammar consists of a finite set of rewrite rules, that can be used to generate strings.

Many restrictions on the form of grammars are important in practice; some of these, such as the ones listed in the Chomsky hierarchy, can only describe a subset of the languages described by arbitrary grammars; therefore, they are not normal forms of arbitrary grammars. But within these classes of grammars, normal forms are frequently used.

For more details, see the section on equivalent grammars.

Normal forms also abound in relational database theory, which defines a hierarchy of normal forms for database tables, representing different levels of avoiding redundancy within the data. Third normal form, Boyce-Codd normal form and project-join normal form are most important in practice.

Log in or register to write something here or to contact authors.