# Formation rule

In mathematical logic, **formation rules** are rules for describing which strings of symbols formed from the alphabet of a formal language are syntactically valid within the language. These rules only address the location and manipulation of the strings of the language. It does not describe anything else about a language, such as its semantics (i.e. what the strings mean). (See also formal grammar).

## Formal language

A *formal language* is an organized set of symbols the essential feature being that it can be precisely defined in terms of just the shapes and locations of those symbols. Such a language can be defined, then, without any reference to any meanings of any of its expressions; it can exist before any interpretation is assigned to it—that is, before it has any meaning. A formal grammar determines which symbols and sets of symbols are formulas in a formal language.

## Formal systems

A *formal system* (also called a *logical calculus*, or a *logical system*) consists of a formal language together with a deductive apparatus (also called a *deductive system*). The deductive apparatus may consist of a set of transformation rules (also called *inference rules*) or a set of axioms, or have both. A formal system is used to derive one expression from one or more other expressions. Propositional and predicate calculi are examples of formal systems.

## Propositional and predicate logic

The formation rules of a propositional calculus may, for instance, take a form such that;

- if we take Φ to be a propositional formula we can also take [math]\displaystyle{ \neg }[/math]Φ to be a formula;
- if we take Φ and Ψ to be a propositional formulas we can also take (Φ [math]\displaystyle{ \wedge }[/math] Ψ), (Φ [math]\displaystyle{ \to }[/math] Ψ), (Φ [math]\displaystyle{ \lor }[/math] Ψ) and (Φ [math]\displaystyle{ \leftrightarrow }[/math] Ψ) to also be formulas.

A predicate calculus will usually include all the same rules as a propositional calculus, with the addition of quantifiers such that if we take Φ to be a formula of propositional logic and α as a variable then we can take ([math]\displaystyle{ \forall }[/math]α)Φ and ([math]\displaystyle{ \exists }[/math]α)Φ each to be formulas of our predicate calculus.

## See also

- Finite state automaton

Original source: https://en.wikipedia.org/wiki/Formation rule.
Read more |