Posto de quantificadores: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m adicionou Categoria:Teoria dos modelos usando HotCat |
|||
Linha 1: | Linha 1: | ||
Na [[lógica matemática]], o '''posto de quantificadores''' de uma [[Fórmula matemática|fórmula]] é a profundidade |
Na [[lógica matemática]], o '''posto de quantificadores''' de uma [[Fórmula matemática|fórmula]] é a profundidade do aninhamento de seus quantificadores, desempenhando um papel essencial na teoria de modelos.<br /> |
||
Note que o posto |
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 == |
== Definição == |
Revisão das 12h52min de 25 de fevereiro de 2015
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
- , se φ for atómico.
- .
- .
- .
Observação
- Escrevemos FO[n] para o conjunto de todas fórmulas φ da Lógica de Primeira Ordem com .
- 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:
- Uma fórmula com posto de quantificador igual a 2:
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.