Substituce (logika) - Substitution (logic) - Wikipedia

Střídání je zásadní pojem v logika.A substituce je syntaktický transformace zapnuta formální výrazy aplikovat záměna za výraz znamená důsledně nahrazovat jeho proměnné nebo zástupné symboly jinými výrazy. Výsledný výraz se nazývá a substituční instancenebo krátké instance, původního výrazu.

Výroková logika

Definice

Kde ψ a φ zastupovat vzorce výrokové logiky, ψ je substituční instance z φ kdyby a jen kdyby ψ lze získat z φ nahrazením vzorců pro symboly v φ, nahradí každý výskyt stejného symbolu výskytem stejného vzorce. Například:

(R → S) & (T → S)

je substituční instance:

P & Q

a

(A ↔ A) ↔ (A ↔ A)

je substituční instance:

(A ↔ A)

V některých dedukčních systémech pro výrokovou logiku je nový výraz (a tvrzení ) lze zadat na řádek derivace, pokud se jedná o substituční instanci předchozího řádku derivace (Hunter 1971, s. 118). Takto jsou v některých zavedeny nové řádky axiomatické systémy. V systémech, které používají pravidla transformace, pravidlo může zahrnovat použití a substituční instance za účelem zavedení určitých proměnných do derivace.

v logika prvního řádu, každý uzavřený výrokový vzorec to může být odvozený z otevřeného výrokového vzorce A substitucí se říká substituční instance A. Li A je uzavřený výrokový vzorec, který počítáme A se jako jediná substituční instance.

Tautologie

Výrokový vzorec je a tautologie pokud je to pravda pod každým ocenění (nebo výklad ) jejích predikátových symbolů. Pokud Φ je tautologie a Θ je substituční instance Φ, pak Θ je opět tautologie. Tato skutečnost implikuje spolehlivost pravidla pro odpočet popsaného v předchozí části.[Citace je zapotřebí ]

Logika prvního řádu

v logika prvního řádu, a substituce je celkové mapování σ: PROTI → T z proměnné na podmínky; mnoho,[1]:73[2]:445 ale ne všichni[3]:250 autoři navíc vyžadují σ (X) = X pro všechny ale konečně mnoho proměnných X. Zápis { X1 ↦ t1, ..., Xk ↦ tk }[poznámka 1]označuje substituci mapující každou proměnnou Xi k odpovídajícímu výrazu ti, pro i=1,...,ka každá další proměnná sama o sobě; the Xi musí být párově odlišné. Přihlašování tuto substituci termínu t je napsán v postfixová notace tak jako t { X1 ↦ t1, ..., Xk ↦ tk }; to znamená (současně) nahradit každý výskyt každého z nich Xi v t podle ti.[poznámka 2] Výsledek tσ aplikace substituce σ na člen t se nazývá instance tohoto termínu t.Například použití substituce { X ↦ z, z ↦ h(A,y)} k termínu

F(z, A, G(X), y)  výnosy
F(h(A,y), A, G(z), y).

The doména dom(σ) substituce σ je běžně definována jako množina skutečně nahrazených proměnných, tj. dom(σ) = { X ∈ PROTI | Xσ ≠ X }. Substituce se říká a přízemní substituce, pokud mapuje všechny proměnné své domény na přízemní, tj. bez proměnných, podmínky. Substituční instance tσ pozemní substituce je základní člen, pokud všechny t 'Proměnné s jsou v doméně σ, tj. pokud vars(t) ⊆ dom(σ). Substituce σ se říká a lineární substituce, pokud tσ je a lineární termín pro nějaký (a tedy každý) lineární termín t obsahující přesně proměnné domény σ, tj. s vars(t) = dom(σ). Substituce σ se říká a byt substituce, pokud Xσ je proměnná pro každou proměnnou X. Substituce σ se říká a přejmenování substituce, pokud se jedná o a permutace na množině všech proměnných. Stejně jako každá permutace má i substituce pro přejmenování σ vždy inverzní substituce σ−1, takový, že tσσ−1 = t = tσ−1σ pro každý termín t. Není však možné definovat inverzní funkci pro libovolnou substituci.

Například, { X ↦ 2, y ↦ 3 + 4} je pozemní střídání, { X ↦ X1, y ↦ y2+4} je nezemněný a nerovný, ale lineární, { X ↦ y2, y ↦ y2+4} je nelineární a ne ploché, { X ↦ y2, y ↦ y2 } je plochý, ale nelineární, { X ↦ X1, y ↦ y2 } je lineární i plochý, ale nepřejmenovává, protože je mapuje oba y a y2 na y2; každá z těchto substitucí má množinu {X,y} jako jeho doména. Příkladem pro přejmenování substituce je { X ↦ X1, X1 ↦ y, y ↦ y2, y2 ↦ X }, má inverzní { X ↦ y2, y2 ↦ y, y ↦ X1, X1 ↦ X }. Plochá substituce { X ↦ z, y ↦ z } nemůže mít inverzní, protože např. (X+y) { X ↦ z, y ↦ z } = z+z, a druhý termín nelze transformovat zpět na X+y, protože informace o původu a z pochází z je ztracen. Střídání země { X ↦ 2} nemůže mít inverzi kvůli podobné ztrátě informací o původu, např. v (X+2) { X ↦ 2} = 2 + 2, i když nahrazování konstant proměnnými bylo povoleno nějakým fiktivním druhem „zobecněných substitucí“.

Uvažuje se o dvou substitucích rovnat se pokud mapují každou proměnnou na strukturálně stejné výsledné termíny, formálně: σ = τ pokud Xσ = Xτ pro každou proměnnou X ∈ PROTI.v složení dvou substitucí σ = { X1 ↦ t1, ..., Xk ↦ tk } a τ = { y1 ↦ u1, ..., yl ↦ ul } získá se odstraněním ze substituce { X1 ↦ t1τ, ..., Xk ↦ tkτ, y1 ↦ u1, ..., yl ↦ ul } ty páry yi ↦ ui pro který yi ∈ { X1, ..., Xk }. Složení σ a τ je označeno στ. Složení je asociativní operace a je kompatibilní se substituční aplikací, tj. (Ρσ) τ = ρ (στ) a (tσ) τ = t(στ) pro každou substituci ρ, σ, τ a každý člen t.v substituce identity, který mapuje každou proměnnou k sobě, je neutrálním prvkem substituční kompozice. Nahrazuje se substituce σ idempotentní pokud σσ = σ, a tedy tσσ = tσ pro každý termín t. Substituce { X1 ↦ t1, ..., Xk ↦ tk } je idempotent právě tehdy, když žádná z proměnných Xi vyskytuje se v jakémkoli ti. Substituční složení není komutativní, to znamená, že στ se může lišit od τσ, i když σ a τ jsou idempotentní.[1]:73–74[2]:445–446

Například, { X ↦ 2, y ↦ 3 + 4} se rovná { y ↦ 3+4, X ↦ 2}, ale liší se od { X ↦ 2, y ↦ 7}. Substituce { X ↦ y+y } je idempotentní, např. (((X+y) {X↦y+y}) {X↦y+y} = ((y+y)+y) {X↦y+y} = (y+y)+y, zatímco substituce { X ↦ X+y } není idempotentní, např. (((X+y) {X↦X+y}) {X↦X+y} = ((X+y)+y) {X↦X+y} = ((X+y)+y)+y. Příkladem nedojíždějících náhrad je { X ↦ y } { y ↦ z } = { X ↦ z, y ↦ z }, ale { y ↦ z} { X ↦ y} = { X ↦ y, y ↦ z }.

Viz také

Poznámky

  1. ^ někteří autoři používají [ t1/X1, ..., tk/Xk ] k označení této substituce, např. M. Wirsing (1990). Jan van Leeuwen (ed.). Algebraická specifikace. Příručka teoretické informatiky. B. Elsevier. 675–788., zde: str. 682;
  2. ^ Od a termínová algebra hledisko, sada T termínů je volná termínová algebra přes sadu PROTI proměnných, tedy pro každé substituční mapování σ: PROTI → T existuje jedinečný homomorfismus σ: T → T který souhlasí s σ na PROTI ⊆ T; výše definovaná aplikace σ na člen t se poté považuje za použití funkce σ k argumentu t.

Reference

  1. ^ A b David A. Duffy (1991). Principy automatizovaného dokazování vět. Wiley.
  2. ^ A b Franz Baader, Wayne Snyder (2001). Alan Robinson a Andrej Voronkov (vyd.). Teorie sjednocení (PDF). Elsevier. 439–526.
  3. ^ N. Dershowitz; J.-P. Jouannaud (1990). "Přepsat systémy". V Jan van Leeuwen (ed.). Formální modely a sémantika. Příručka teoretické informatiky. B. Elsevier. 243–320.

externí odkazy