Skolem normální forma - Skolem normal form

V matematické logice , je formule z logiky prvního řádu je v Skolem normální formě , pokud je to v prenexní tvar formě pouze s univerzálními prvního řádu kvantifikátory .

Každý vzorec prvního řádu lze převést do normální formy Skolem, aniž by se změnila jeho uspokojivost pomocí procesu zvaného Skolemization (někdy hláskovaná Skolemnization ). Výsledný vzorec nemusí být nutně ekvivalentní původnímu, ale je s ním srovnatelný : je uspokojivý právě tehdy, je-li uspokojivý původní.

Redukce na Skolemovu normální formu je metoda pro odstranění existenčních kvantifikátorů z formálních logických příkazů, která se často provádí jako první krok v automatizovaném důkazu teorémů .

Příklady

Nejjednodušší forma skolemizace je pro existenciálně kvantifikované proměnné, které nejsou v rozsahu univerzálního kvantifikátoru. Mohou být nahrazeny jednoduše vytvořením nových konstant. Například může být změněno na , kde je nová konstanta (nevyskytuje se nikde jinde ve vzorci). ${\ displaystyle \ existuje xP (x)}$${\ displaystyle P (c)}$${\ displaystyle c}$

Obecněji se skolemizace provádí nahrazením každé existenciálně kvantifikované proměnné výrazem, jehož funkční symbol je nový. Proměnné tohoto pojmu jsou následující. Pokud je vzorec v prenex normální formě , pak jsou proměnné, které jsou všeobecně kvantifikovány a jejichž kvantifikátory předcházejí proměnným z . Obecně se jedná o proměnné, které jsou kvantifikovány univerzálně (předpokládáme, že se zbavíme existenciálních kvantifikátorů v pořadí, takže všechny existenční kvantifikátory byly dříve odstraněny) a takové, které se vyskytují v rozsahu jejich kvantifikátorů. Funkce zavedená v tomto procesu se nazývá Skolemova funkce (nebo Skolemova konstanta, pokud má nulovou arititu ) a termín se nazývá Skolemův termín . ${\ displaystyle}$${\ displaystyle f (x_ {1}, \ ldots, x_ {n})}$${\ displaystyle f}$${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle}$${\ displaystyle \ existuje y}$${\ displaystyle \ existuje y}$${\ displaystyle f}$

Například vzorec není v normální formě Skolem, protože obsahuje existenční kvantifikátor . Skolemizace nahradí se , kde je nová funkce symbol, a odstraňuje kvantifikaci přes . Výsledný vzorec je . Termín Skolem obsahuje , ale ne , protože kvantifikátor, který má být odstraněn, je v rozsahu , ale nikoli v rozsahu ; protože tento vzorec je v normální formě prenex, odpovídá to tomu, že v seznamu kvantifikátorů předchází while ne. Vzorec získaný touto transformací je uspokojivý právě tehdy, je-li původní vzorec. ${\ displaystyle \ forall x \ existuje y \ forall zP (x, y, z)}$${\ displaystyle \ existuje y}$${\ displaystyle}$${\ displaystyle f (x)}$${\ displaystyle f}$${\ displaystyle}$${\ displaystyle \ forall x \ forall zP (x, f (x), z)}$${\ displaystyle f (x)}$${\ displaystyle x}$${\ displaystyle z}$${\ displaystyle \ existuje y}$${\ displaystyle \ forall x}$${\ displaystyle \ forall z}$${\ displaystyle x}$${\ displaystyle}$${\ displaystyle z}$

Jak funguje skolemizace

Skolemizace funguje uplatněním ekvivalence druhého řádu ve spojení s definicí uspokojivosti prvního řádu. Ekvivalence poskytuje způsob „přesunu“ existenčního kvantifikátoru před univerzální.

${\ displaystyle \ forall x {\ Big (} R (g (x)) \ vee \ existuje yR (x, y) {\ Big)} \ iff \ existuje f \ forall x {\ Big (} R (g ( x)) \ vee R (x, f (x)) {\ Big)}}$

kde

${\ displaystyle f (x)}$ je funkce, která se mapuje na . ${\ displaystyle x}$${\ displaystyle}$

Intuitivně je věta „pro každého existuje taková, že “ je převedena do ekvivalentní podoby „existuje funkce mapující všechny na takovou, že pro každou, kterou obsahuje “. ${\ displaystyle x}$${\ displaystyle}$${\ displaystyle R (x, y)}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle}$${\ displaystyle x}$${\ displaystyle R (x, f (x))}$

Tato ekvivalence je užitečná, protože definice uspokojivosti prvního řádu implicitně existenciálně kvantifikuje přes vyhodnocení funkčních symbolů. Zejména vzorec prvního řádu je uspokojivý, pokud existuje model a vyhodnocení volných proměnných vzorce, které hodnotí vzorec na true . Model obsahuje vyhodnocení všech funkčních symbolů; proto jsou funkce Skolem implicitně existenciálně kvantifikovány. Ve výše uvedeném příkladu je splnitelný právě tehdy, když existuje model , který obsahuje hodnocení pro , takové, které platí pro některé hodnocení jeho volných proměnných (v tomto případě žádné). To může být vyjádřeno v druhém pořadí jako . Podle výše uvedené rovnocennosti je to stejné jako uspokojivost . ${\ displaystyle \ Phi}$${\ displaystyle M}$${\ displaystyle \ mu}$${\ displaystyle \ forall xR (x, f (x))}$${\ displaystyle M}$${\ displaystyle f}$${\ displaystyle \ forall xR (x, f (x))}$${\ displaystyle \ existuje f \ pro všechny xR (x, f (x))}$${\ displaystyle \ forall x \ existuje yR (x, y)}$

Na meta úrovni lze uspokojivost prvního řádu vzorce psát s malým zneužitím notace, protože kde je model, je to hodnocení volných proměnných, což znamená, že je to pravda pod . Protože modely prvního řádu obsahují vyhodnocení všech funkčních symbolů, je jakákoli funkce Skolem, která obsahuje, implicitně existenciálně kvantifikována . Výsledkem je, že po nahrazení existenčních kvantifikátorů nad proměnnými existenčními kvantifikátory nad funkcemi v přední části vzorce lze se vzorcem stále zacházet jako s prvním řádem odstraněním těchto existenčních kvantifikátorů. Tento poslední krok zpracování, jak může být dokončen, protože funkce jsou implicitně existenciálně kvantifikovány v definici uspokojivosti prvního řádu. ${\ displaystyle \ Phi}$${\ displaystyle \ existuje M \ existuje \ mu ~. ~ (M, \ mu \ modely \ Phi)}$${\ displaystyle M}$${\ displaystyle \ mu}$${\ displaystyle \ models}$${\ displaystyle \ Phi}$${\ displaystyle M}$${\ displaystyle \ mu}$${\ displaystyle \ Phi}$${\ displaystyle \ existuje M}$${\ displaystyle \ existuje f \ pro všechny xR (x, f (x))}$${\ displaystyle \ forall xR (x, f (x))}$${\ displaystyle \ existuje M}$

Správnost skolemizace může být ukázána na příkladu vzorce následovně. Tento vzorec je splněn modelem právě tehdy, pokud pro každou možnou hodnotu pro v doméně modelu existuje hodnota pro v doméně modelu, která platí. Podle axiomu výběru , existuje funkce taková, že . Výsledkem je vzorec uspokojivý, protože má model získaný přidáním vyhodnocení do . To ukazuje, že je uspokojivý, pouze pokud je uspokojivý také. Naopak, pokud je uspokojivý, pak existuje model, který jej uspokojuje; tento model zahrnuje vyhodnocení funkce tak, že pro každou hodnotu vzorce platí. Výsledkem je, že je uspokojen stejným modelem, protože je možné zvolit pro každou hodnotu hodnotu , kde je hodnocena podle . ${\ displaystyle F_ {1} = \ forall x_ {1} \ dots \ forall x_ {n} \ existuje yR (x_ {1}, \ dots, x_ {n}, y)}$ ${\ displaystyle M}$${\ displaystyle x_ {1}, \ dots, x_ {n}}$${\ displaystyle}$${\ displaystyle R (x_ {1}, \ tečky, x_ {n}, y)}$${\ displaystyle f}$${\ displaystyle y = f (x_ {1}, \ tečky, x_ {n})}$${\ displaystyle F_ {2} = \ forall x_ {1} \ dots \ forall x_ {n} R (x_ {1}, \ dots, x_ {n}, f (x_ {1}, \ dots, x_ {n }))}$${\ displaystyle f}$${\ displaystyle M}$${\ displaystyle F_ {1}}$${\ displaystyle F_ {2}}$${\ displaystyle F_ {2}}$${\ displaystyle M '}$${\ displaystyle f}$${\ displaystyle x_ {1}, \ dots, x_ {n}}$${\ displaystyle R (x_ {1}, \ tečky, x_ {n}, f (x_ {1}, \ tečky, x_ {n}))}$${\ displaystyle F_ {1}}$${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle y = f (x_ {1}, \ tečky, x_ {n})}$${\ displaystyle f}$${\ displaystyle M '}$

Použití skolemizace

Jedním z použití skolemizace je automatizované dokazování vět . Například v metodě analytických obrazů , kdykoli nastane vzorec, jehož hlavní kvantifikátor je existenční, může být generován vzorec získaný odstraněním tohoto kvantifikátoru pomocí Skolemization. Pokud se například vyskytne v tablo, kde jsou volné proměnné , pak může být přidáno do stejné větve tabla. Toto doplnění nemění uspokojivost tabla: každý model starého vzorce lze rozšířit přidáním vhodného vyhodnocení k modelu nového vzorce. ${\ displaystyle \ existuje x. \ Phi (x, y_ {1}, \ ldots, y_ {n})}$${\ displaystyle x, y_ {1}, \ ldots, y_ {n}}$${\ displaystyle \ Phi (x, y_ {1}, \ ldots, y_ {n})}$${\ displaystyle \ Phi (f (y_ {1}, \ ldots, y_ {n}), y_ {1}, \ ldots, y_ {n})}$${\ displaystyle f}$

Tato forma skolemizace je zdokonalením oproti „klasické“ skolemizaci v tom, že do Skolemova výrazu jsou umístěny pouze proměnné, které jsou ve vzorci volné. Toto je vylepšení, protože sémantika tabla může implicitně umístit vzorec do rozsahu některých univerzálně kvantifikovaných proměnných, které nejsou ve vzorci samotném; tyto proměnné nejsou ve skolemském termínu, zatímco by tam byly podle původní definice skolemizace. Další vylepšení, které lze použít, je použití stejného symbolu funkce Skolem pro vzorce, které jsou identické až po proměnné přejmenování.

Další použití je v metodě řešení pro logiku prvního řádu , kde jsou vzorce reprezentovány jako sady klauzulí chápaných jako univerzálně kvantifikovatelné. (Například viz paradox pití .)

Skolemské teorie

Obecně platí, že pokud je teorie a pro každý vzorec s volnými proměnnými existuje funkční symbol, pro který je prokazatelně Skolemova funkce , pak se nazývá Skolemova teorie . ${\ displaystyle T}$ ${\ displaystyle x_ {1}, \ dots, x_ {n}, y}$${\ displaystyle F}$${\ displaystyle}$${\ displaystyle T}$

Každá Skolemova teorie je úplná , tj. Každá substruktura modelu je elementární substrukturou . Vzhledem k tomu, model M z Skolem teorie T , nejmenší spodní stavby, který obsahuje určitou sadu se nazývá Skolem trup z A . Skolem Trup A je atomová primární model přes A .

Dějiny

Normální forma Skolem je pojmenována po zesnulém norském matematikovi Thoralfovi Skolemovi .

Viz také

• Herbrandizace , dvojka skolemizace
• Logika funktoru predikátu

Poznámky

Reference

• Hodges, Wilfrid (1997), Kratší teorie modelů , Cambridge University Press , ISBN   978-0-521-58713-6 CS1 maint: discouraged parameter ( link )

externí odkazy

• „Funkce Skolem“ , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Skolemizace na PlanetMath.org
• Skolemizace Hector Zenil, The Wolfram Demonstations Project .
• Weisstein, Eric W. „SkolemizedForm“ . MathWorld .