Vyloučení kvantifikátoru - Quantifier elimination

Eliminace kvantifikátoru je koncept zjednodušení používaný v matematické logice , teorii modelů a teoretické informatice . Neformálně lze kvantifikovaný výrok „ takový, že “ považovat za otázku „Kdy je takový ?“ A výrok bez kvantifikátorů lze považovat za odpověď na tuto otázku. ${\ displaystyle \ existuje x}$ ${\ displaystyle \ ldots}$ ${\ displaystyle x}$ ${\ displaystyle \ ldots}$

Jedním ze způsobů klasifikace vzorců je množství kvantifikace . Vzorce s menší hloubkou střídání kvantifikátoru jsou považovány za jednodušší, přičemž vzorce bez kvantifikátoru jsou nejjednodušší. Teorie má Kvantifikátor odstranění, pokud pro každý vzorec , existuje další formule bez kvantifikátorů, který je ekvivalentní k ní ( modulo tuto teorii). ${\ displaystyle \ alpha}$ ${\ displaystyle \ alpha _ {QF}}$

Příklady

Příklad ze středoškolské matematiky říká, že kvadratický polynom s jednou proměnnou má skutečný kořen právě tehdy, když je jeho diskriminátor nezáporný:

{\ displaystyle \ existuje x \ in \ mathbb {R}. (a \ neq 0 \ klínová sekera ^ {2} + bx + c = 0) \ \ \ Longleftrightarrow \ \ a \ neq 0 \ klín b ^ {2} -4ac \ geq 0}

Zde věta na levé straně zahrnuje kvantifikátor , zatímco ekvivalentní věta vpravo nikoli. ${\ displaystyle \ existuje x \ v \ mathbb {R}}$

Příklady teorií, které se ukázaly rozhodnutelnými pomocí eliminace kvantifikátoru, jsou Presburgerova aritmetika , algebraicky uzavřená pole , skutečná uzavřená pole , bezolovnaté booleovské algebry , algebry termínů , husté lineární řády , abelianské skupiny , náhodné grafy a také mnoho z jejich kombinací, jako je Boolean algebra s Presburgerovou aritmetikou a termínové algebry s frontami .

Eliminátorem kvantifikátoru pro teorii reálných čísel jako uspořádané skupiny aditiv je Fourier-Motzkinova eliminace ; pro teorii pole reálných čísel je to věta Tarski – Seidenberg .

Odstranění kvantifikátoru lze také použít k prokázání, že „kombinace“ rozhodných teorií vede k novým rozhodnutelným teoriím.

Algoritmy a rozhodnutelnost

Pokud má teorie eliminaci kvantifikátoru, lze se zaměřit na konkrétní otázku: Existuje pro každý způsob stanovení ? Pokud taková metoda existuje, nazýváme ji algoritmus eliminace kvantifikátoru . Pokud takový algoritmus existuje, potom se rozhodnutelnost teorie snižuje na rozhodování o pravdivosti vět bez kvantifikátoru . Věty bez kvantifikátoru nemají žádné proměnné, takže jejich platnost v dané teorii může být často vypočítána, což umožňuje použití algoritmů eliminace kvantifikátoru k rozhodnutí o platnosti vět. ${\ displaystyle \ alpha _ {QF}}$ ${\ displaystyle \ alpha}$

Související pojmy

S eliminací kvantifikátoru souvisí různé modelové teoretické nápady a existují různé ekvivalentní podmínky.

Každá teorie prvního řádu s eliminací kvantifikátoru je dokončena . Naopak teorie úplného modelu, jejíž teorie univerzálních důsledků má vlastnost sloučení , má eliminaci kvantifikátoru.

Modely teorie univerzálních důsledků teorie jsou přesně substrukturami modelů . Teorie lineárních řádů nemá eliminaci kvantifikátoru. Teorie jejích univerzálních důsledků má však vlastnost sloučení. ${\ displaystyle T}$ ${\ displaystyle T}$

Základní myšlenky

Chcete-li konstruktivně ukázat, že teorie má eliminaci kvantifikátoru, postačí ukázat, že můžeme eliminovat existenční kvantifikátor aplikovaný na spojení literálů , tj. Ukázat, že každý vzorec ve tvaru:

{\ displaystyle \ existuje x. \ bigwedge _ {i = 1} ^ {n} L_ {i}}

kde každý je literál, je ekvivalentní vzorci bez kvantifikátoru. Ve skutečnosti předpokládejme, že víme, jak eliminovat kvantifikátory z konjunkcí literálů, pokud je tedy vzorec bez kvantifikátoru, můžeme jej napsat v disjunktivní normální formě ${\ displaystyle L_ {i}}$ ${\ displaystyle F}$

{\ displaystyle \ bigvee _ {j = 1} ^ {m} \ bigwedge _ {i = 1} ^ {n} L_ {ij},}

a využij toho, že

{\ displaystyle \ existuje x. \ bigvee _ {j = 1} ^ {m} \ bigwedge _ {i = 1} ^ {n} L_ {ij}}

je ekvivalentní k

{\ displaystyle \ bigvee _ {j = 1} ^ {m} \ existuje x. \ bigwedge _ {i = 1} ^ {n} L_ {ij}.}

Nakonec eliminovat univerzální kvantifikátor

{\ displaystyle \ celkem xF}

kde je bez kvantifikátoru, transformujeme se do disjunktivní normální formy a použijeme fakt, který je ekvivalentní ${\ displaystyle F}$ ${\ displaystyle \ lnot F}$ ${\ displaystyle \ celkem xF}$ ${\ Displaystyle \ lnot \ existuje x. \ lnot F.}$

Vztah s rozhodovatelností

V rané teorii modelu byla eliminace kvantifikátoru použita k prokázání toho, že různé teorie mají vlastnosti jako rozhodovatelnost a úplnost . Běžnou technikou bylo nejprve ukázat, že teorie připouští eliminaci kvantifikátorů a poté dokázat rozhodnutelnost nebo úplnost zvážením pouze vzorců bez kvantifikátoru. Touto technikou lze ukázat, že Presburgerova aritmetika je rozhodnutelná.

Teorie by mohly být rozhodnutelné, ale nepřipustit eliminaci kvantifikátoru. Přísně vzato, teorie aditivních přirozených čísel nepřipouštěla eliminaci kvantifikátoru, ale ukázalo se, že je rozhodující expanze aditivních přirozených čísel. Kdykoli teorie rozhodnutelný, a jazyk jeho platných vzorců je spočetný , je možné rozšířit teorii s countably mnoha vztahů mít Kvantifikátor eliminace (například, je možné zavést pro každý vzorec teorie, symbol vztah, který vztahuje volné proměnné vzorce).

Příklad: Nullstellensatz pro algebraicky uzavřená pole a pro různě uzavřená pole .

Viz také

Poznámky

Reference

Viktor Kunčák a Martin Rinard. „ Strukturální Subtypizace typů nerekurzívní rozhodnutelný “. V Osmnáctém výročním sympoziu IEEE o logice v informatice, 2003.

Languages

In other projects