Formation rule
Encyclopedia
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
).
s the essential feature of which is 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 meaning
s 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.
s, 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.
may, for instance, take a form such that;
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 (α)Φ and (α)Φ each to be formulas of our predicate calculus.
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, formation rules are rules for describing which strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
of symbols
Symbol (formal)
For other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...
formed from the alphabet of a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
are syntactically
Syntax (logic)
In logic, syntax is anything having to do with formal languages or formal systems without regard to any interpretation or meaning given to them...
valid
Validity
In logic, argument is valid if and only if its conclusion is entailed by its premises, a formula is valid if and only if it is true under every interpretation, and an argument form is valid if and only if every argument of that logical form is 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
Semantics
Semantics is the study of meaning. It focuses on the relation between signifiers, such as words, phrases, signs and symbols, and what they stand for, their denotata....
(i.e. what the strings mean). (See also formal grammar
Formal grammar
A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
).
Formal language
A formal language is an organized set of symbolSymbol
A symbol is something which represents an idea, a physical entity or a process but is distinct from it. The purpose of a symbol is to communicate meaning. For example, a red octagon may be a symbol for "STOP". On a map, a picture of a tent might represent a campsite. Numerals are symbols for...
s the essential feature of which is 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
Reference
Reference is derived from Middle English referren, from Middle French rèférer, from Latin referre, "to carry back", formed from the prefix re- and ferre, "to bear"...
to any meaning
Meaning (linguistics)
In linguistics, meaning is what is expressed by the writer or speaker, and what is conveyed to the reader or listener, provided that they talk about the same thing . In other words if the object and the name of the object and the concepts in their head are the same...
s of any of its expressions; it can exist before any interpretation
Interpretation (logic)
An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation...
is assigned to it—that is, before it has any meaning. A formal grammar
Formal grammar
A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
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 axiomAxiom
In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
s, or have both. A formal system is used to derive
Proof theory
Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...
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 calculusPropositional calculus
In mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...
may, for instance, take a form such that;
- if we take Φ to be a propositional formula we can also take Φ to be a formula;
- if we take Φ and Ψ to be a propositional formulas we can also take (Φ Ψ), (Φ Ψ), (Φ Ψ) and (Φ Ψ) 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
Variable (mathematics)
In mathematics, a variable is a value that may change within the scope of a given problem or set of operations. In contrast, a constant is a value that remains unchanged, though often unknown or undetermined. The concepts of constants and variables are fundamental to many areas of mathematics and...
then we can take (α)Φ and (α)Φ each to be formulas of our predicate calculus.