Rango del cuantificador

En lógica matemática , el rango cuantificador de una fórmula es la profundidad de anidamiento de sus cuantificadores . Desempeña un papel esencial en la teoría de modelos .

Observe que el rango del cuantificador es una propiedad de la fórmula misma (es decir, la expresión en un idioma). Por tanto, dos fórmulas lógicamente equivalentes pueden tener diferentes rangos de cuantificadores cuando expresan la misma cosa de diferentes maneras.

Definición

Rango cuantificador de una fórmula en lenguaje de primer orden (FO)

Sea φ una fórmula FO. El rango cuantificador de φ, escrito qr(φ), se define como

• ${\displaystyle qr(\varphi )=0}$, si φ es atómico.
• ${\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(\exists _{x}\varphi )=qr(\varphi )+1}$.
• ${\displaystyle qr(\forall _{x}\varphi )=qr(\varphi )+1}$.

Observaciones

• Escribimos FO[n] para el conjunto de todas las fórmulas de primer orden φ con . ${\displaystyle qr(\varphi )\leq n}$
• El FO[n] relacional (sin símbolos de función) siempre es de tamaño finito, es decir, contiene un número finito de fórmulas.
• Observe que en la forma normal de Prenex el rango de cuantificador de φ es exactamente el número de cuantificadores que aparecen en φ.

Rango de cuantificador de orden superior Fórmula

• Para lógica Fixpoint , con un operador de punto fijo mínimo LFP: ${\displaystyle qr([LFP_{\phi }]y)=1+qr(\phi )}$

Ejemplos

• Una oración de cuantificador de rango 2:

${\displaystyle \forall x\exists yR(x,y)}$

• Una fórmula de cuantificador de rango 1:

${\displaystyle \forall xR(y,x)\wedge \exists xR(x,y)}$

• Una fórmula de cuantificador de rango 0:

${\displaystyle R(x,y)\wedge x\neq y}$

• Una oración en forma normal prenex de cuantificador de rango 3:

${\displaystyle \forall x\exists y\exists z((x\neq y\wedge xRy)\wedge (x\neq z\wedge zRx))}$

• Una frase, equivalente a la anterior, aunque de rango cuantificador 2:

${\displaystyle \forall x(\exists y(x\neq y\wedge xRy))\wedge \exists z(x\neq z\wedge zRx))}$

Ver también

• Forma normal de Prenex
• Juego Ehrenfeucht
• Cuantificador

Referencias

• Ebbinghaus, Heinz-Dieter ; Flum, Jörg (1995), Teoría de modelos finitos , Springer , ISBN 978-3-540-60149-4.
• Grädel, Erich; Kolaítis, Phokion G.; Libkin, Leónidas ; Martín, Marx; Spencer, Joel ; Vardi, Moshe Y .; Venema, Ydé; Weinstein, Scott (2007), Teoría de modelos finitos y sus aplicaciones , Textos de informática teórica. Una serie EATCS, Berlín: Springer-Verlag , p. 133, ISBN 978-3-540-00428-8, Zbl  1133.03001.

enlaces externos

• Espectro de rango de cuantificador de la tesis de licenciatura L-infinito-omega, 2000