Posto de quantificadores

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

Note que o posto do quantificador é 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 expressão 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(\varphi )=0$, se φ for atómico.
• $pq(\varphi _{1}\land \varphi _{2})=pq(\varphi _{1}\lor \varphi _{2})=max(pq(\varphi _{1}),pq(\varphi _{2}))$.
• $pq(\lnot \varphi )=pq(\varphi )$.
• $pq(\exists _{x}\varphi )=pq(\varphi )+1$.

Observação

• Escrevemos FO[n] para o conjunto de todas fórmulas φ da Lógica de Primeira Ordem com $pq(\varphi )\leq 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:

$\forall x\exists y\exists z((\lnot x=y)\land xRy)\land ((\lnot x=z)\land zRx)$

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

$\forall x(\exists y((\lnot x=y)\land xRy))\land (\exists z((\lnot x=z)\land zRx))$

== Referências ==

• {{Citation

  | last1=Ebbinghaus

  | first1=Heinz-Dieter

  | authorlink1=Heinz-Dieter Ebbinghaus

  | last2=Flum

  | first2=Jörg

  | title=Finite Model Theory

  | publisher=[[Springer Publishing|Springer]]

  | isbn=978-3-540-60149-4

  | year=1995

 }}.

• {{citation | last1=Grädel | first1=Erich | last2=Kolaitis | first2=Phokion G. | last3=Libkin | first3=Leonid | author3-link=Leonid Libkin | last4=Maarten | first4=Marx | last5=Spencer | first5=Joel | author5-link=Joel Spencer | last6=Vardi | first6=Moshe Y. | author6-link=Moshe Y. Vardi | last7=Venema | first7=Yde | last8=Weinstein | first8=Scott | title=Finite model theory and its applications | zbl=1133.03001 | series=Texts in Theoretical Computer Science. An EATCS Series | location=Berlin | publisher=[[Springer-Verlag]] | isbn=978-3-540-00428-8 | year=2007 | page=133 }}.