Formal system

A formal system is a system of rules and symbol strings. The rules are rules for converting a symbol string into another, so productions of a formal grammar. The application of the rules can without knowing the meaning of the symbols, so be purely syntactically. Formal systems are used in various scientific disciplines such as logic, mathematics, computer science and linguistics, in particular to new statements from already existing knowledge to derive.

Calculus is often used in the same meaning as formal system; sometimes, however, is understood to certain limitations under a calculus, a formal system.

Definition of a formal system

A formal system can be regarded as quadruples, ie it is constituted by the following determination pieces:

• Is an alphabet, that is a lot of arbitrary characters. These are the basic characters that make up the strings of symbols of the formal system.
• Is a subset of all the words that can be formed over the alphabet. These are the " well-formed " or " well-formed formulas " (english well-formed formulas, wff ), so those under the symbol strings which give a "sense". " Make sense " but it means nothing else than that these signs ranks of the grammar of the formal system and that it therefore should be admitted for further investigation. is thus a formal language over the alphabet. In practice, the (usually infinite) set quantity is in turn determined by formation rules or defined inductively.
• Is a set of axioms. Axioms must be wffs. That is, a subset of the must. In addition to that, this term is quite formal to understand: the axioms are - in principle arbitrary - output formulas for the derivation relation of the formal system.
• Is a set of at least two binary relations over words from, is defined by the derivation relation. contains the rules for the derivation. Two (or more) in a wffs these relations to each other, then the last of the previous or derived. Starting from the axioms - which are in advance as " derivable " defined - this results in a lot of - according to the relation - derived wffs.

With regard to the performance of formal systems, especially the axioms and the latter relation must be considered. By this derivation relation is defined. It is often symbolized with. The spelling of two words a and b from the set B means so that b can be derived from a formal. So there is a sequence of relations in R, (possibly using other derivable formulas ) set the a and b together in a formal derivation relationship.

The term " formal system " is very general, there may be no or infinitely many axioms At least one relation must exist, but it can also be infinitely many But in every case: .. . A wff A if and only one of the (formal ) derived formulas when the scan can specify " reversed tree-like " structure of derivation rules one that starts from axioms and their "tribe" with a ends. Has the formal system no axioms, so are nothing but empty character strings to the " leaf tips " of the tree.

Such derivative term is called syntactically. It is generally not reflected thereon, for which the formula A can be derived, it is in principle not possible in the world relation has no meaning without semantics.

However, interestingly, of course, such formal systems whose derivation relation of a semantic entailment relation ( possibly the human in particular ) as closely as possible. That one wishes to have everything one can infer semantically, can be derived formally. Thus, although within the framework of formal systems is already exceeded. More detailed information can be found among others in the article logic.

Calculi

Occasionally you can find for calculi before the restriction that the set of relations in R must be finite. In addition, frequently asked further demands on the derivation relation of calculi, such as the fulfillment of the shell axioms and the finiteness axiom. Otherwise, the calculus term is usually used synonymously with the term of the formal system.

Formal system in mathematics

Mathematics uses always formal systems. The elementary algebra, how they learn in school, is such a system. It makes use of numbers, mathematical symbols for addition, subtraction, multiplication and division as well as the letters for the unknown. The computation rules are the transformation rules that can be applied mechanically, when it has once viewed. For example, to the

Interpreted as

A mechanical rule could then be:

Example of use

The basic arithmetic operations of arithmetic form the first formal system that is learned in elementary school. There will be symbols for the digits 1,2,3,4,5,6,7,8,9 and a symbol for zero, which is 0, the addition is replaced by the symbol " ". It is now the symbols string together and receives strings of symbols, for example:

123 45 7 0 123456 666 1607 23 56 The first three correspond to the (not formulated in detail ) rules for well-formed strings of symbols. The last two do not and can not be subjected to the following rule.

Addition rule: Take the two rightmost digits each digit string and replace it with the following rule: 0 1 = 1, 1 1 = 2, 1 2 = 3, ..., 5 5 = 0 carry. .. 9 9 = 8 transfer. Write the resulting digits to the right place of the new digit string and you realize the transfer. Take now the second digit from the right from every chain and replace it with the same rule. If a carry in the previous step was available, turn on the replacement to the new digit and 1. Replace a result, the second digit from the right by the new symbol and remember again the carry. Set the method of right away to the left until no digits are available. If a chain is shorter than the other, replace missing digits with '0 '. If a carry at the end is present, write the result leftmost '1 '.

The chain " 987 789 " is thus replaced by the application of this addition rule by the chain in 1776. To transfer this approach to the formalization described above, we can say, " 1776 " was derived from " 987 789 ". However, we must be aware that the derivation was alone at the character level us. It would also be possible, by means of another derivation rule of " 987 789 ", the string " 198 " to derive (which in this case is the difference ) or the string " 87 78 " in accordance with the rule: " Let the first and the last character " away. Sum and difference in terms of our everyday vocabulary belong to the semantics and are therefore out of reach of the previously kalkülisierten mathematical systems.