Ersetzung (Logik) - Substitution (logic)
Substitution ist ein grundlegendes Konzept in Logik . Eine Substitution ist eine syntaktische Transformation von formalen Ausdrücken. Gelten eine Substitution zu einem Expressionsmittel konsequent seine variable zu ersetzen oder Platzhalter, Symbole durch andere Ausdrücke. Der resultierende Ausdruck wird als Ersatzinstanz oder kurze Instanz des ursprünglichen Ausdrucks bezeichnet.
Aussagelogik
Definition
Wo ψ und & phgr; repräsentiert Formeln der Aussagenlogik, ψ ist eine Substitution Instanz von φ , wenn und nur wenn ψ erteilen kann φ durch die Formeln für die Symbole in Substituieren φ , jedes Auftreten desselben Symbols durch ein Auftreten der gleichen Formel ersetzt wird . Beispielsweise:
- (R → S) & (T → S)
ist eine Ersatzinstanz von:
- P & Q
und
- (A ↔ A) ↔ (A ↔ A)
ist eine Ersatzinstanz von:
- (A ↔ A)
In einigen Deduktionssystemen für die Aussagenlogik kann ein neuer Ausdruck (eine Aussage ) in eine Zeile einer Ableitung eingegeben werden, wenn es sich um eine Substitutionsinstanz einer vorherigen Zeile der Ableitung handelt (Hunter 1971, S. 118). So werden in einigen axiomatischen Systemen neue Leitungen eingeführt . In Systemen, die Transformationsregeln verwenden , kann eine Regel die Verwendung einer Substitutionsinstanz umfassen, um bestimmte Variablen in eine Ableitung einzuführen.
In der Logik erster Ordnung heißt jede geschlossene Aussagenformel , die aus einer offenen Aussagenformel a durch Substitution abgeleitet werden kann, eine Substitutionsinstanz von a . Wenn a eine abgeschlossene Aussagenformel ist, zählen wir a selbst als ihre einzige Substitutionsinstanz.
Tautologien
Eine Aussageformel ist eine Tautologie, wenn sie unter jeder Bewertung (oder Interpretation ) ihrer Prädikatssymbole wahr ist . Wenn Φ eine Tautologie ist und Θ eine Substitutionsinstanz von Φ ist, dann ist Θ wieder eine Tautologie. Diese Tatsache impliziert die Richtigkeit der im vorherigen Abschnitt beschriebenen Abzugsregel.
Logik erster Ordnung
In der Logik erster Ordnung ist eine Substitution eine totale Abbildung σ : V → T von Variablen auf Terme ; viele, aber nicht alle Autoren verlangen zusätzlich σ ( x ) = x für alle außer endlich vielen Variablen x . Die Schreibweise { x 1 ↦ t 1 , ..., x k ↦ t k } bezieht sich auf eine Substitution Mapping jede Variable x i zu dem entsprechenden Term t i , für i = 1, ..., k und jede andere Variable mit sich selbst; die x i muss paarweise verschieden sein. Anwendung , dass die Substitution zu einer Laufzeit t wird in geschrieben Postfixnotation als t { x 1 ↦ t 1 , ..., x k ↦ t k }; es bedeutet, (gleichzeitig) jedes Vorkommen jedes x i in t durch t i zu ersetzen . Das Ergebnis tσ der Anwendung einer Substitution σ auf einen Term t wird eine Instanz dieses Termes t genannt . Anwenden der Substitution { x ↦ z , z ↦ h ( a , y ) } auf den Term
f ( z , a , g ( x ), j ) ergibt f ( h ( a , j ) , a , g ( z ), j ) .
Die Domäne dom ( σ ) eine Substitution σ wird allgemein als die Menge von Variablen definiert tatsächlich ersetzt, das heißt dom ( σ ) = { x ∈ V | xσ ≠ x }. Eine Substitution ist ein sogenannter Boden Substitution , wenn sie alle Variablen seiner Domäne abbildet Boden , dh variable frei, Begriffe. Das Substitutions Beispiel tσ eine Grundsubstitution ist ein Grundterm , wenn all t ‚ s sind Variablen in σ ‘ s - Domäne ist , dh wenn Vars ( t ) ⊆ dom ( σ ). Eine Substitution σ ist eine sogenannte Linear Substitution wenn tσ a lineare Term für einig (und damit jeder) linearer Term t genau die Variablen enthalten , σ ' s - Domäne, dh mit Vars ( t ) = dom ( σ ). Eine Substitution σ heißt flache Substitution, wenn xσ eine Variable für jede Variable x ist . Eine Substitution σ heißt Umbenennungssubstitution, wenn es sich um eine Permutation auf der Menge aller Variablen handelt. Wie jede Permutation hat auch eine Umbenennungssubstitution σ immer eine inverse Substitution σ −1 , so dass tσσ −1 = t = tσ −1 σ für jeden Term t . Es ist jedoch nicht möglich, für eine beliebige Substitution eine Inverse zu definieren.
Zum Beispiel ist { x 2, y ↦ 3+4 } eine Grundsubstitution , { x ↦ x 1 , y ↦ y 2 +4 } ist nicht geerdet und nicht flach, aber linear, { x ↦ y 2 , y ↦ y 2 +4 } ist nicht linear und nicht flach, { x ↦ y 2 , y ↦ y 2 } ist flach, aber nicht linear, { x ↦ x 1 , y ↦ y 2 } ist sowohl linear als auch flach, aber keine Umbenennung, da es sowohl y als auch y 2 auf y 2 abbildet ; jede dieser Substitutionen hat die Menge { x , y } als ihre Domäne. Ein Beispiel für eine Umbenennungs Substitution { x ↦ x 1 , x 1 ↦ y , y ↦ y 2 , y 2 ↦ x }, ist es die inverse hat { x ↦ y 2 , y 2 ↦ y , y ↦ x 1 , x 1 ↦ x }. Die flache Substitution { x ↦ z , y ↦ z } kann keine Inverse haben, da zB ( x + y ) { x ↦ z , y ↦ z } = z + z , und letzterer Term nicht zurück in x + y . zurücktransformiert werden kann , da die Information über den Ursprung von a z verloren geht. Die Grundsubstitution { x ↦ 2 } kann aufgrund eines ähnlichen Verlusts der Ursprungsinformation keine Inverse haben, zB in ( x +2) { x ↦ 2 } = 2+2, selbst wenn das Ersetzen von Konstanten durch Variablen durch eine fiktive Art von . erlaubt wäre "generalisierte Substitutionen".
Zwei Substitutionen gelten als gleich, wenn sie jede Variable auf strukturell gleiche Ergebnisterme abbilden , formal: σ = τ falls xσ = xτ für jede Variable x ∈ V . Die Zusammensetzung zweier Substitutionen σ = { x 1 ↦ t 1 , …, x k ↦ t k } und τ = { y 1 ↦ u 1 , …, y l ↦ u l } erhält man durch Entfernen von { x 1 ↦ t 1 τ , …, x k ↦ t k τ , y 1 ↦ u 1 , …, y l ↦ u l } jene Paare y i ↦ u i für die y i ∈ { x 1 , …, x k }. Die Zusammensetzung von σ und τ wird mit στ bezeichnet . Die Komposition ist eine assoziative Operation und mit der Substitutionsanwendung kompatibel, dh ( ρσ ) τ = ρ ( στ ) bzw. ( tσ ) τ = t ( στ ) für jede Substitution ρ , σ , τ und jeden Term t . Die Identitätssubstitution , die jede Variable auf sich selbst abbildet, ist das neutrale Element der Substitutionszusammensetzung. Eine Substitution σ heißt idempotent, wenn σσ = σ , also tσσ = tσ für jeden Term t . Die Substitution { x 1 ↦ t 1 , ..., x k ↦ t k } ist idempotent , wenn und nur wenn keine der Variablen x i in jedem auftritt t i . Die Substitutionszusammensetzung ist nicht kommutativ, dh στ kann sich von τσ unterscheiden, auch wenn σ und τ idempotent sind.
Zum Beispiel ist { x 2, y 3+4 } gleich { y ↦ 3+4, x ↦ 2 }, aber verschieden von { x 2, y ↦ 7 }. Die Substitution { x ↦ y + y } ist idempotent, zB (( x + y ) { x ↦ y + y }) { x ↦ y + y } = (( y + y )+ y ) { x ↦ y + y } = ( y + y )+ y , während die Substitution { x ↦ x + y } nicht idempotent ist, zB (( x + y ) { x ↦ x + y }) { x ↦ x + y } = (( x + y ) + y ) { x ↦ x + y } = (( x + y ) + y ) + y . Ein Beispiel für nicht-Pendel Substitutionen ist { x ↦ y } { y ↦ z } = { x ↦ z , y ↦ z }, aber { y ↦ z } { x ↦ y } = { x ↦ y , y ↦ z } .
Siehe auch
- Substitutionseigenschaft in Gleichheit (Mathematik)#Einige grundlegende logische Eigenschaften der Gleichheit
- Logik erster Ordnung#Inferenzregeln
- Universelle Instanziierung
- Lambda-Kalkül#Substitution
- Wahrheitswert-Semantik
- Vereinigung (Informatik)
- Metavariable
- Mutatis mutandis
- Ersetzungsregel
- Substitution (Algebra) – über das Anwenden von Substitutionen auf Polynome und andere algebraische Ausdrücke
- String-Interpolation – wie man es in der Computerprogrammierung sieht
Anmerkungen
Verweise
- Crabbé, M. (2004). Zum Begriff der Substitution . Logisches Journal der IGPL, 12, 111–124.
- Curry, HB (1952) Zur Definition von Substitution, Ersetzung und verwandten Begriffen in einem abstrakten formalen System . Revue philosophique de Louvain 50, 251–269.
- Jäger, G. (1971). Metalogic: Eine Einführung in die Metatheorie der Standardlogik erster Ordnung . University of California Press. ISBN 0-520-01822-2
- Kleene, SC (1967). Mathematische Logik . Nachdruck 2002, Dover. ISBN 0-486-42533-9
Externe Links
- Substitution in nLab