Posto de quantificadores

Na lógica matemática, o posto de quantificadores de uma fórmula é a profundidade do aninhamento de seus quantificadores, desempenhando um papel essencial na teoria de modelos.

Note que o posto de quantificadores é uma propriedade da própria fórmula (como a expressão em uma linguagem). Assim, duas fórmulas equivalentes podem ter diferentes postos, quando elas expressam duas coisas iguais porém de maneira diferente.

Definição

Posto de Quantificadores em uma fórmula da Lógica de Primeira Ordem (FO, do inglês First-order language).

Suponha que φ seja uma fórmula da Lógica de Primeira Ordem. O posto do quantificador de φ, escrito por pq(φ) é definido como

• $pq(\phi )=0$, se φ for atómico.
• $pq({\phi }_1\wedge {\phi }_2)=pq({\phi }_1\vee {\phi }_2)=max(pq({\phi }_1),pq({\phi }_2))$.
• $pq(\mathrm{\neg }\phi )=pq(\phi )$.
• $pq({\mathrm{\exists }}_x\phi )=pq(\phi )+1$.

Observação

• Escrevemos FO[n] para o conjunto de todas fórmulas φ da Lógica de Primeira Ordem com $pq(\phi )\le n$.
• FO[n] relacionais (sem símbolos de função) são sempre de tamanho finito, isto é, contém um número finito de fórmulas.
• Note que na Forma Normal Prenex o posto do quantificador de φ é exatamente o número de quantificadores que aparecem em φ.

Exemplos

• Uma sentença com posto de quantificador igual a 2:

∀x∃y R(x, y)

• Uma fórmula com posto de quantificador igual a 1:

∀x R(y, x) ∧ ∃x R(x, y)

• Uma fórmula com posto de quantificador igual a 0:

R(x, y) ∧ x ≠ y

• Uma fómula na Forma Normal Prenex com posto de quantificador igual a 3:

$\mathrm{\forall }x\mathrm{\exists }y\mathrm{\exists }z((\mathrm{\neg }x=y)\wedge xRy)\wedge ((\mathrm{\neg }x=z)\wedge zRx)$

• Uma fórmula com posto de quantificador igual a 2:

$\mathrm{\forall }x(\mathrm{\exists }y((\mathrm{\neg }x=y)\wedge xRy))\wedge (\mathrm{\exists }z((\mathrm{\neg }x=z)\wedge zRx))$

Referências

• Ebbinghaus, Heinz-Dieter; Flum, Jörg (1995), Finite Model Theory, 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), Finite model theory and its applications, Texts in Theoretical Computer Science. An EATCS Series, Berlin:Springer-Verlag, p. 133, ISBN 978-3-540-00428-8, Zbl 1133.03001.