Derivation

A derivation is a finite sequence of rule applications that transforms an initial symbol or expression into a final one. It records how the result follows from specified rules.

Formal system: A formal system consists of symbols, rules, and structures for deriving or interpreting expressions. A derivation takes place within a system whose rules define permitted steps.
Rewrite system: A rewrite system is a collection of rules that transform expressions into other expressions. It models derivations as repeated applications of expression-changing rules.
Formal proof: A formal proof is a finite sequence or structure of statements justified by explicit inference rules. A proof is a derivation whose final statement is the theorem being established.
Theorem: A theorem is a statement established by proof from axioms, definitions, or earlier results. A theorem is a proved endpoint; a derivation is the sequence or structure reaching it.
Rewrite rule: A rewrite rule specifies how one expression may be replaced by another. Each step in a derivation applies a rule to part or all of an expression.
Derivation tree: A derivation tree represents rule applications as a tree, with premises branching into conclusions. It displays the branching structure behind derivations with multiple premises.
Natural deduction: Natural deduction is a proof system organized around introduction and elimination rules for logical connectives and quantifiers. Its proofs are derivations built from rules that mirror logical reasoning.
Normal form: A normal form is an expression to which no specified reduction rule applies. A derivation is a path of transformations, whereas a normal form is a possible final result.
Formal language: A formal language is a set of strings defined over an alphabet by explicit rules or conditions. Derivations transform strings or expressions drawn from a system's formal language.
Proof tree: A proof tree is a tree-shaped representation of a formal proof, with inference rules at its branching steps. It makes the structure of a logical derivation explicit.

Linked from 11 pages