Substitution instance

Substitution instance

In propositional logic, a substitution instance of a propositional formula is a second formula obtained by replacing symbols of the original formula by other formulas. A key fact is that any substitution of a tautology is again a tautology.

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 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

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.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • substitution instance — noun : a statement in logic derived from a statement form by substitution of constants for variables …   Useful english dictionary

  • Substitution failure is not an error — (SFINAE) refers to a situation in C++ where an invalid substitution of template parameters is not in itself an error. The acronym SFINAE was first introduced by David Vandevoorde to describe related programming techniques. [cite book |… …   Wikipedia

  • substitution — [sub΄stə to͞o′shən, sub΄stətyo͞o′shən] n. the substituting of one person or thing for another substitutional adj. substitutionary * * * sub·sti·tu·tion (sŭb stĭ to͞oʹshən, tyo͞oʹ ) n. 1. a. The act or an instance of substituting. b. The state of… …   Universalium

  • Substitution matrix — In evolutionary biology, a substitution matrix describes the rate at which one character in a sequence changes to other character states over time. Substitution matrices are usually seen in the context of amino acid or DNA sequence alignments,… …   Wikipedia

  • substitution — sub·sti·tu·tion || ‚sÊŒbstɪ tuːʃn / tjuːʃn n. replacement; act or instance of substituting …   English contemporary dictionary

  • substitution — noun the action or an instance of substituting someone or something. Derivatives substitutional adjective substitutionary adjective …   English new terms dictionary

  • Explicit substitution — In computer science, Explicit substitution is an umbrella term used to describe several calculi based on the Lambda calculus that pay special attention to the formalization of the process of substitution. The concept of explicit substitutions has …   Wikipedia

  • Arene substitution patterns — are part of organic chemistry IUPAC nomenclature and pinpoint the position of substituents other than hydrogen in relation to each other on an aromatic hydrocarbon. Contents 1 Ortho, meta, and para substitution 2 Ipso, meso, and peri substitution …   Wikipedia

  • Simultaneous substitution — For the US equivalent to this practice, see Syndication exclusivity. The View as it appears on ABC in Canada before and after simultaneous substitution is implemented as requested by CTV. Note the appearance of CTV s bug in the lower right corner …   Wikipedia

  • Import substitution industrialization — (also called ISI) is a trade and economic policy based on the premise that a country should attempt to reduce its foreign dependency through the local production of industrialized products. Adopted in many Latin American countries from the 1930s… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”