Substitution (logic)
Encyclopedia
Substitution is a fundamental concept
in logic
. Substitution is a syntactic
transformation on strings
of symbols
of a formal language
.
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 for any consistent
formal system
, any substitution of a tautology
will also produce a tautology.
Ψ 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:
is a substitution instance of:
and
is a substitution instance of:
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 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.
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.
Concept
The word concept is used in ordinary language as well as in almost all academic disciplines. Particularly in philosophy, psychology and cognitive sciences the term is much used and much discussed. WordNet defines concept: "conception, construct ". However, the meaning of the term concept is much...
in logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
. Substitution is a syntactic
Syntax (logic)
In logic, syntax is anything having to do with formal languages or formal systems without regard to any interpretation or meaning given to them...
transformation on strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
of symbols
Symbol (formal)
For other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...
of a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
.
In propositional logic, a substitution instance of a propositional formula
Propositional formula
In propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a truth value. If the values of all variables in a propositional formula are given, it determines a unique truth value...
is a second formula obtained by replacing symbols of the original formula by other formulas. A key fact is that for any consistent
Consistency
Consistency can refer to:* Consistency , the psychological need to be consistent with prior acts and statements* "Consistency", an 1887 speech by Mark Twain...
formal system
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
, any substitution of a tautology
Tautology (logic)
In logic, a tautology is a formula which is true in every possible interpretation. Philosopher Ludwig Wittgenstein first applied the term to redundancies of propositional logic in 1921; it had been used earlier to refer to rhetorical tautologies, and continues to be used in that alternate sense...
will also produce a tautology.
Definition
Where Ψ and Φ represent formulas of propositional logic, Ψ is a substitution instance of Φ if and only ifIf and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
Ψ 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 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
Proposition
In logic and philosophy, the term proposition refers to either the "content" or "meaning" of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence...
) 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 system
Axiomatic system
In mathematics, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A mathematical theory consists of an axiomatic system and all its derived theorems...
s. In systems that use rules of transformation
Rule of inference
In logic, a rule of inference, inference rule, or transformation rule is the act of drawing a conclusion based on the form of premises interpreted as a function which takes premises, analyses their syntax, and returns a conclusion...
, 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 tautologyTautology (logic)
In logic, a tautology is a formula which is true in every possible interpretation. Philosopher Ludwig Wittgenstein first applied the term to redundancies of propositional logic in 1921; it had been used earlier to refer to rhetorical tautologies, and continues to be used in that alternate sense...
if it is true under every valuation
Valuation (logic)
In logic and model theory, a valuation can be:*In propositional logic, an assignment of truth values to propositional variables, with a corresponding assignment of truth values to all propositional formulas with those variables....
(or interpretation
Interpretation (logic)
An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some 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.
See also
- Substitution property in Equality (mathematics)#Some basic logical properties of equality
- First-order logic#Rules of inference
- Rule of universal substitution
- Lambda calculus#Substitution
- Truth-value semanticsTruth-value semanticsIn formal semantics, truth-value semantics is an alternative to Tarskian semantics. It has been primarily championed by Ruth Barcan Marcus, H. Leblanc, and M. Dunn and N. Belnap...
- Unification (computer science)