Substitution (logic)
A substitution is a syntactic transformation on formal expressions. To apply a substitution to an expression means to consistently replace its variable, or placeholder, symbols with other expressions.
The resulting expression is called a substitution instance, or instance for short, of the original expression.
Propositional logic[edit]
Definition[edit]
Where
- (R → S) & (T → S)
is a substitution instance of:
- P & Q
and
- (A ↔ A) ↔ (A ↔ A)
is a substitution instance of:
- (A ↔ A)
In some deduction systems for propositional logic, a new expression (a proposition) may be entered on a line of a derivation if it is a substitution instance of a previous line of the derivation (Hunter 1971, p. 118). This is how new lines are introduced in some axiomatic systems. In systems that use rules of transformation, a rule may include the use of a substitution instance for the purpose of introducing certain variables into a derivation.
Tautologies[edit]
A propositional formula is a tautology if it is true under every valuation (or interpretation) of its predicate symbols. If
First-order logic[edit]
In first-order logic, a substitution is a total mapping
f( z , a, g( x ), y) yields f( h(a,y) , a, g( z ), y) .
The domain dom(
For example, { x ↦ 2, y ↦ 3+4 } is a ground substitution, { x ↦ x1, y ↦ y2+4 } is non-ground and non-flat, but linear, { x ↦ y2, y ↦ y2+4 } is non-linear and non-flat, { x ↦ y2, y ↦ y2 } is flat, but non-linear, { x ↦ x1, y ↦ y2 } is both linear and flat, but not a renaming, since it maps both y and y2 to y2; each of these substitutions has the set {x,y} as its domain. An example for a renaming substitution is { x ↦ x1, x1 ↦ y, y ↦ y2, y2 ↦ x }, it has the inverse { x ↦ y2, y2 ↦ y, y ↦ x1, x1 ↦ x }. The flat substitution { x ↦ z, y ↦ z } cannot have an inverse, since e.g. (x+y) { x ↦ z, y ↦ z } = z+z, and the latter term cannot be transformed back to x+y, as the information about the origin a z stems from is lost. The ground substitution { x ↦ 2 } cannot have an inverse due to a similar loss of origin information e.g. in (x+2) { x ↦ 2 } = 2+2, even if replacing constants by variables was allowed by some fictitious kind of "generalized substitutions".
Two substitutions are considered equal if they map each variable to syntactically equal result terms, formally:
For example, { x ↦ 2, y ↦ 3+4 } is equal to { y ↦ 3+4, x ↦ 2 }, but different from { x ↦ 2, y ↦ 7 }. The substitution { x ↦ y+y } is idempotent, e.g. ((x+y) {x↦y+y}) {x↦y+y} = ((y+y)+y) {x↦y+y} = (y+y)+y, while the substitution { x ↦ x+y } is non-idempotent, e.g. ((x+y) {x↦x+y}) {x↦x+y} = ((x+y)+y) {x↦x+y} = ((x+y)+y)+y. An example for non-commuting substitutions is { x ↦ y } { y ↦ z } = { x ↦ z, y ↦ z }, but { y ↦ z} { x ↦ y} = { x ↦ y, y ↦ z }.
Algebra[edit]
Substitution is a basic operation in algebra, in particular in computer algebra.[4][5]
A common case of substitution involves polynomials, where substitution of a numerical value (or another expression) for the indeterminate of a univariate polynomial amounts to evaluating the polynomial at that value. Indeed, this operation occurs so frequently that the notation for polynomials is often adapted to it; instead of designating a polynomial by a name like P, as one would do for other mathematical objects, one could define
so that substitution for X can be designated by replacement inside "P(X)", say
or
Substitution can also be applied to other kinds of formal objects built from symbols, for instance elements of free groups. In order for substitution to be defined, one needs an algebraic structure with an appropriate universal property, that asserts the existence of unique homomorphisms that send indeterminates to specific values; the substitution then amounts to finding the image of an element under such a homomorphism.
Substitution is related to, but not identical to, function composition; it is closely related to
See also[edit]
- Integration by substitution
- Lambda calculus § Substitution
- String interpolation
- Substitution property of Equality
- Trigonometric substitution
- Universal instantiation
Notes[edit]
- ^ Some authors use [ t1/x1, …, tk/xk ] to denote that substitution, e.g. M. Wirsing (1990). Jan van Leeuwen (ed.). Algebraic Specification. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 675–788., here: p. 682.
- ^ From a term algebra point of view, the set T of terms is the free term algebra over the set V of variables, hence for each substitution mapping
σ : V → T there is a unique homomorphismσ : T → T that agrees withσ on V ⊆ T; the above-defined application ofσ to a term t is then viewed as applying the functionσ to the argument t.
Citations[edit]
- ^ a b David A. Duffy (1991). Principles of Automated Theorem Proving. Wiley.
- ^ a b Franz Baader, Wayne Snyder (2001). Alan Robinson and Andrei Voronkov (ed.). Unification Theory (PDF). Elsevier. pp. 439–526. Archived from the original (PDF) on 2015-06-08. Retrieved 2014-09-24.
- ^ N. Dershowitz; J.-P. Jouannaud (1990). "Rewrite Systems". In Jan van Leeuwen (ed.). Formal Models and Semantics. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 243–320.
- ^ Margret H. Hoft; Hartmut F.W. Hoft (6 November 2002). Computing with Mathematica. Elsevier. ISBN 978-0-08-048855-4.
- ^ Andre Heck (6 December 2012). Introduction to Maple. Springer Science & Business Media. ISBN 978-1-4684-0484-5.
substitution.
References[edit]
- Crabbé, M. (2004). On the Notion of Substitution. Logic Journal of the IGPL, 12, 111–124.
- Curry, H. B. (1952) On the definition of substitution, replacement and allied notions in an abstract formal system. Revue philosophique de Louvain 50, 251–269.
- Hunter, G. (1971). Metalogic: An Introduction to the Metatheory of Standard First Order Logic. University of California Press. ISBN 0-520-01822-2
- Kleene, S. C. (1967). Mathematical Logic. Reprinted 2002, Dover. ISBN 0-486-42533-9
External links[edit]
- Substitution at the nLab