Pořadí kvantifikátoru - Quantifier rank

v matematická logika, hodnost kvantifikátoru a vzorec je hloubka jeho vnoření kvantifikátory. Hraje zásadní roli v teorie modelů.

Všimněte si, že pozice kvantifikátoru je vlastností samotného vzorce (tj. Výrazu v jazyce). Tedy dva logicky ekvivalentní vzorce mohou mít různé kvantifikační řady, když vyjadřují stejnou věc různými způsoby.

Definice

Pořadí kvantifikátoru vzorce ve formátu Jazyk prvního řádu (FO)

Nechť φ je vzorec FO. Hodnost kvantifikátoru φ, zapsaná qr (φ), je definována jako

${ displaystyle qr ( varphi) = 0}$ , pokud φ je atomový.
${ displaystyle qr ( varphi _ {1} land varphi _ {2}) = qr ( varphi _ {1} lor varphi _ {2}) = max (qr ( varphi _ {1}) , qr ( varphi _ {2}))}$ .
${ Displaystyle qr ( lnot varphi) = qr ( varphi)}$ .
${ displaystyle qr ( existuje _ {x} varphi) = qr ( varphi) +1}$ .

Poznámky

Píšeme FO [n] pro množinu všech první objednávka vzorce φ s ${ displaystyle qr ( varphi) leq n}$ .
Relační FO [n] (bez funkčních symbolů) má vždy konečnou velikost, tj. Obsahuje konečný počet vzorců
Všimněte si, že v Prenex normální forma Rank kvantifikátoru φ je přesně počet kvantifikátorů objevujících se v φ.

Kvantifikátor Pořadí vzorce vyššího řádu

Pro Logika fixního bodu, s operátorem LFP s nejméně pevným bodem:

qr ([LFP_φ] y) = 1 + qr (φ)

...

Příklady

Věta kvantifikátoru pořadí 2:

{ displaystyle forall x existuje yR (x, y)}

Vzorec kvantifikátoru pořadí 1:

{ displaystyle forall xR (y, x) klín existuje xR (x, y)}

Vzorec hodnosti kvantifikátoru 0:

{ displaystyle R (x, y) klín x neq y}

Věta v normální forma prenex stupně kvantifikátoru 3:

{ displaystyle forall x existuje y existuje z ((x neq y klín xRy) klín (x neq z klín zRx))}

Věta ekvivalentní předchozí, i když má kvantifikátor 2. úrovně:

{ displaystyle forall x ( existuje y (x neq y klín xRy)) klín existuje z (x neq z klín zRx))}

Viz také

Reference

Ebbinghaus, Heinz-Dieter; Flum, Jörg (1995), Teorie konečných modelů, Springer, ISBN 978-3-540-60149-4.
Grädel, Erich; Kolaitis, Phokion G .; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007), Teorie konečných modelů a její aplikace, Texty v teoretické informatice. Série EATCS, Berlín: Springer-Verlag, str. 133, ISBN 978-3-540-00428-8, Zbl 1133.03001.

externí odkazy

Kvantifikátor Rank Spectrum of L-infinity-omega Bakalářská práce, 2000