- Substitution instance
In
propositional logic , a substitution instance of apropositional formula is a second formula obtained by replacing symbols of the original formula by other formulas. A key fact is that any substitution of atautology is again atautology .Definition
Where "Ψ" and "Φ" represent formulas of propositional logic, Ψ is a substitution instance of Φ
if and only if Ψ may be obtained from Φ by substituting formulas for symbols in Φ, always replacing an occurrence of the same symbol by an occurrence of the same formula. For example:::(R imp S) and (T imp S)is a substitution instance of:::P and Q
and
::(A eqv A) eqv (A eqv A)is a substitution instance of:::(A eqv 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 someaxiomatic system s. 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
A propositional formula is a
tautology if it is true under every valuation (or interpretation) of its predicate symbols. If Φ is a tautology, and Θ is a substitution instance of Φ, then Θ is again a tautology. This fact implies the soundness of the deduction rule described in the previous section.References
* Hunter, G. (1971). "Metalogic: An Introduction tothe 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
Wikimedia Foundation. 2010.
