Substituce (logika) - Substitution (logic)

Substituce je základním pojmem v logice . Substituce je syntaktická transformace na formální výrazy. Chcete-li použít substituci na expresních prostředky k trvale nahradit jeho proměnná nebo vyhrazené místo, symboly jinými výrazy. Výsledný výraz se nazývá substituční instance nebo krátká instance původního výrazu.

Výroková logika

Definice

Tam, kde ψ a cp představují vzorce výrokové logiky, ψ je substituce instance z cp tehdy a jen tehdy, když ψ lze získat od cp nahrazením vzorce pro symboly v cp , nahradí každý výskyt stejným symbolem o výskytu 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 lze na řádek derivace zadat nový výraz ( propozici ), pokud se jedná o substituční instanci předchozího řádku derivace (Hunter 1971, s. 118). Takto jsou v některých axiomatických systémech zavedeny nové řádky . V systémech, které používají pravidla transformace , může pravidlo zahrnovat použití substituční instance za účelem zavedení určitých proměnných do derivace.

V logice prvního řádu je každý uzavřený výrokový vzorec, který lze odvodit z otevřeného výrokového vzorce a substitucí, považován za substituční instanci a . Pokud je uzavřený výrokové formule počítáme na sebe jako jeho jediný substituční instance.

Tautologie

Výrokový vzorec je tautologie, pokud platí při každém ocenění (nebo interpretaci ) 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.

Logika prvního řádu

V logice prvního řádu je substitucí celkové mapování σ : V → T z proměnných na pojmy ; mnoho, ale ne všichni autoři navíc vyžadují σ ( x ) = x pro všechny, ale konečně mnoho proměnných x . Zápis { x 1  ↦  t 1 ,…, x k  ↦  t k } odkazuje na substituci mapující každou proměnnou x i na odpovídající termín t i , pro i = 1,…, k a každou další proměnnou k sobě; x i musí být párové odlišný. Použití této substituce na termín t je zapsáno v postfixové notaci jako t { x 1  ↦  t 1 , ..., x k  ↦  t k }; to znamená, že se (současně) nahradit každý výskyt každé x i v t o t i . Výsledek tσ aplikace substituce σ na člen t se nazývá instance tohoto členu t . Například použití substituce { x  ↦  z , z  ↦  h ( a , y )} na termín

f ( z , a , g ( X ), y )   výnosy
f ( h ( a , y ) , a , g ( z ), y ) .

Doména dom ( σ ) o substituční å je obecně definován jako soubor proměnných vlastně nahrazuje, tj dom ( σ ) = { x ∈ V | xσ ≠ x }. Substituce se nazývá pozemní substituce, pokud mapuje všechny proměnné své domény na základní , tj. Bez proměnných, pojmy. Substituce instance tσ pozemního substituce je důvod termín, zda jsou v t ‚ je proměnné jsou v å ‘ je doména, tedy v případě, Vars ( t ) ⊆ dom ( σ ). Substituce σ se nazývá lineární substituce, pokud tσ je lineární termín pro některé (a tudíž každý) lineární termín t obsahující přesně proměnné å ' s doménu, to znamená s Vars ( t ) = dom ( å ). Substituce σ se nazývá plochá substituce, pokud xσ je proměnná pro každou proměnnou x . Substituce σ se říká substituce přejmenování, pokud se jedná o permutaci na množině všech proměnných. Jako každá permutace, i přejmenovací substituce σ má vždy inverzní substituci σ −1 , takže tσσ −1 = t = tσ −1 σ pro každý člen t . Není však možné definovat inverzní funkci pro libovolnou substituci.

Například { x  ↦ 2, y  ↦ 3 + 4} je zemní substituce, { x  ↦  x 1 , y  ↦ y 2 +4} je neuzemněná a nerovná  , ale lineární, { x  ↦  y 2 , y  ↦  y 2 +4} je nelineární a ne ploché, { x  ↦  y 2 , y  ↦  y 2 } je ploché, ale nelineární, { x  ↦  x 1 , y  ↦  y 2 } je lineární i ploché, ale ne přejmenování, protože je mapuje y a y 2 až y 2 ; každá z těchto substitucí má jako doménu množinu { x , y }. Příkladem přejmenovací substituce je { x  ↦  x 1 , x 1  ↦  y , y  ↦  y 2 , y 2  ↦  x }, má inverzní { x  ↦  y 2 , y 2  ↦  y , y  ↦  x 1 , x 1  ↦  x }.  Plošná substituce { x ↦  z , y  ↦  z } nemůže mít inverzní funkci, protože např. ( X + y ) { x  ↦  z , y  ↦  z } = z + z a druhý člen nelze transformovat zpět na x + y jako informace o původu A z pramení z ztracena. Substituce 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ž nahrazení konstant proměnnými bylo povoleno nějakým fiktivním druhem "zobecněné substituce".

Dvě substituce jsou považovány za rovné , pokud Pro každou proměnnou, která konstrukčně stejných výsledků, pokud jde, formálně: σ = τ pokud xσ = xτ pro každou proměnnou x ∈ V . Složení dvou substitucí σ = { x 1  ↦  t 1 , ..., x k  ↦  t k } a τ = { y 1  ↦  u 1 , ..., y l  ↦ u l } se získá odstraněním z substituce { x 1  ↦  t 1 τ ,…, x k  ↦  t k τ , y 1  ↦  u 1 ,…, y l  ↦  u l } ty páry y i  ↦  u i, pro které y i ∈ { x 1 ,…, x k }. 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 . Substituce identity , která mapuje každou proměnnou k sobě, je neutrální element substituční kompozici. Substituce σ se nazývá idempotentní, pokud σσ = σ , a tedy tσσ = tσ pro každý člen t . Substituce { x 1  ↦  t 1 , ..., x k  ↦  t k } je idempotent tehdy, když žádná z proměnných x i se vyskytuje v každém t i . Substituční složení není komutativní, to znamená, že στ se může lišit od τσ, i když jsou σ a τ idempotentní.

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 náhrad  nedojíždějících je { x ↦  y } { y  ↦  z } = { x  ↦  z , y  ↦  z }, ale { y  ↦  z } { x  ↦  y } = { x  ↦  y , y  ↦  z } .

Viz také

Poznámky

Reference

externí odkazy