Lógica de primeira ordem

Lógica de primeira ordem—também conhecida como lógica de predicados, lógica quantificacional e cálculo de predicados de primeira ordem—é uma coleção de sistemas formais usados em matemática, filosofia, lingüística e ciência da computação. A lógica de primeira ordem usa variáveis quantificadas sobre objetos não lógicos e permite o uso de sentenças que contêm variáveis, de modo que, em vez de proposições como "Sócrates é um homem", pode-se ter expressões na forma & #34;existe x tal que x é Sócrates e x é um homem", onde "existe" é um quantificador, enquanto x é uma variável. Isso a distingue da lógica proposicional, que não usa quantificadores ou relações; nesse sentido, a lógica proposicional é o fundamento da lógica de primeira ordem.

Uma teoria sobre um tópico, como a teoria dos conjuntos, uma teoria para grupos ou uma teoria formal da aritmética, geralmente é uma lógica de primeira ordem junto com um domínio especificado de discurso (sobre o qual as variáveis quantificadas variam), finitamente muitas funções desse domínio para si mesmo, muitos predicados finitos definidos nesse domínio e um conjunto de axiomas que se acredita serem válidos sobre eles. Às vezes, "teoria" é entendido em um sentido mais formal como apenas um conjunto de sentenças na lógica de primeira ordem.

O adjetivo "primeira ordem" distingue a lógica de primeira ordem da lógica de ordem superior, na qual existem predicados tendo predicados ou funções como argumentos, ou na qual a quantificação sobre predicados ou funções, ou ambos, é permitida. Nas teorias de primeira ordem, os predicados são frequentemente associados a conjuntos. Em teorias de ordem superior interpretadas, os predicados podem ser interpretados como conjuntos de conjuntos.

Existem muitos sistemas dedutivos para lógica de primeira ordem que são sólidos (ou seja, todas as declarações prováveis são verdadeiras em todos os modelos) e completos (ou seja, todas as declarações que são verdadeiras em todos os modelos são prováveis). Embora a relação de consequência lógica seja apenas semidecidível, muito progresso foi feito na demonstração automatizada de teoremas na lógica de primeira ordem. A lógica de primeira ordem também satisfaz vários teoremas metalógicos que a tornam passível de análise na teoria da prova, como o teorema de Löwenheim-Skolem e o teorema da compacidade.

A lógica de primeira ordem é o padrão para a formalização da matemática em axiomas e é estudada nos fundamentos da matemática. A aritmética de Peano e a teoria dos conjuntos de Zermelo-Fraenkel são axiomatizações da teoria dos números e da teoria dos conjuntos, respectivamente, em lógica de primeira ordem. Nenhuma teoria de primeira ordem, no entanto, tem força para descrever de forma única uma estrutura com um domínio infinito, como os números naturais ou a reta real. Os sistemas de axiomas que descrevem completamente essas duas estruturas (ou seja, sistemas de axiomas categóricos) podem ser obtidos em lógicas mais fortes, como a lógica de segunda ordem.

Os fundamentos da lógica de primeira ordem foram desenvolvidos independentemente por Gottlob Frege e Charles Sanders Peirce. Para uma história da lógica de primeira ordem e como ela passou a dominar a lógica formal, ver José Ferreirós (2001).

Introdução

Enquanto a lógica proposicional lida com proposições declarativas simples, a lógica de primeira ordem cobre adicionalmente predicados e quantificação.

Um predicado pega uma entidade ou entidades no domínio do discurso e avalia como verdadeiro ou falso. Considere as duas sentenças "Sócrates é um filósofo" e "Platão é um filósofo". Na lógica proposicional, essas sentenças são vistas como não relacionadas e podem ser denotadas, por exemplo, por variáveis como p e q. O predicado "é um filósofo" ocorre em ambas as sentenças, que têm uma estrutura comum de "a é um filósofo". A variável a é instanciada como "Sócrates" na primeira frase, e é instanciado como "Platão" na segunda frase. Enquanto a lógica de primeira ordem permite o uso de predicados, como "é um filósofo" neste exemplo, a lógica proposicional não.

Relacionamentos entre predicados podem ser declarados usando conectivos lógicos. Considere, por exemplo, a fórmula de primeira ordem "se a é um filósofo, então a é um estudioso". Esta fórmula é uma declaração condicional com "a é um filósofo" como sua hipótese, e "a é um estudioso" como sua conclusão. A verdade desta fórmula depende de qual objeto é denotado por a, e das interpretações dos predicados "é um filósofo" e "é um estudioso".

Os quantificadores podem ser aplicados a variáveis em uma fórmula. A variável a na fórmula anterior pode ser quantificada universalmente, por exemplo, com a sentença de primeira ordem "Para cada a, se a é um filósofo, então a é um estudioso". O quantificador universal "para cada" nesta frase expressa a ideia de que a afirmação "se a é um filósofo, então a é um estudioso" vale para todas as escolhas de a.

A negação da sentença "Para todo a, se a é um filósofo, então a é um estudioso" é logicamente equivalente à sentença "Existe a tal que a é um filósofo e a não é um estudioso". O quantificador existencial "existe" expressa a ideia de que a afirmação "a é um filósofo e a não é um estudioso" vale para alguma escolha de a.

Os predicados "é um filósofo" e "é um estudioso" cada um leva uma única variável. Em geral, os predicados podem assumir várias variáveis. Na sentença de primeira ordem "Sócrates é o professor de Platão", o predicado "é o professor de" leva duas variáveis.

Uma interpretação (ou modelo) de uma fórmula de primeira ordem especifica o que cada predicado significa e as entidades que podem instanciar as variáveis. Essas entidades formam o domínio do discurso ou universo, que geralmente é necessário para ser um conjunto não vazio. Por exemplo, em uma interpretação com o domínio do discurso constituído por todos os seres humanos e o predicado "é um filósofo" entendida como "foi o autor da República", a frase "Existe a tal que a é um filósofo" é visto como verdadeiro, como testemunha Platão.

Existem duas partes principais da lógica de primeira ordem. A sintaxe determina quais sequências finitas de símbolos são expressões bem formadas na lógica de primeira ordem, enquanto a semântica determina os significados por trás dessas expressões.

Sintaxe

Alfabeto

Ao contrário das línguas naturais, como o inglês, a linguagem da lógica de primeira ordem é completamente formal, de modo que pode ser determinado mecanicamente se uma determinada expressão está bem formada. Existem dois tipos principais de expressões bem formadas: termos, que representam objetos intuitivamente, e fórmulas, que expressam intuitivamente declarações que podem ser verdadeiras ou falsas. Os termos e fórmulas da lógica de primeira ordem são sequências de símbolos, onde todos os símbolos juntos formam o alfabeto da linguagem. Como acontece com todas as linguagens formais, a natureza dos próprios símbolos está fora do escopo da lógica formal; eles são frequentemente considerados simplesmente como letras e símbolos de pontuação.

É comum dividir os símbolos do alfabeto em símbolos lógicos, que sempre têm o mesmo significado, e símbolos não-lógicos, cujo significado varia de interpretação. Por exemplo, o símbolo lógico ∧ ∧ Não. sempre representa "e"; nunca é interpretado como "ou", que é representado pelo símbolo lógico ∨ ∨ - Sim.. No entanto, um símbolo de predicado não-lógico como Phil(x) pode ser interpretado para significar "x é um filósofo, "x é um homem chamado Philip", ou qualquer outro predicado unário dependendo da interpretação à mão.

Símbolos lógicos

Símbolos lógicos são um conjunto de caracteres que variam de acordo com o autor, mas geralmente incluem o seguinte:

• Símbolos de Quantifier: Gerenciamento de contas para quantificação universal, e Detalhe para quantificação existencial
• Conectivos lógicos: ∧ para conjunção, ∨ para disjunção, → por implicação, ↔ para bicondicional, ? para a negação. Alguns autores usam CPQ em vez de → e EPQ em vez de ↔, especialmente em contextos onde → é usado para outros fins. Além disso, a ferradura ⊃ pode substituir →; a barra tripla ) pode substituir ↔; um til (~), Np, ou Fp pode substituir ?; um bar duplo ‖ ‖ - Sim., +Sim., ⋀ ⋀ pq{displaystyle bigwedge pq}, ou APQ pode substituir ∨e um ampersand >, KPQ, ou o ponto médio ) pode substituir ∧, especialmente se estes símbolos não estão disponíveis por razões técnicas. (Os símbolos acima mencionados CPQ, EPQ, Np, APQ, e KPQ são usados na notação polonesa.)
• Parentheses, suportes e outros símbolos de pontuação. A escolha de tais símbolos varia dependendo do contexto.
• Um conjunto infinito de variáveis, muitas vezes denotado por letras minúsculas no final do alfabeto x, Sim., zangão.,... Os subscritos são frequentemente utilizados para distinguir variáveis: x₀, x₁, x₂,...
• Um símbolo de igualdade (às vezes, símbolo de identidade) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = (ver § Igualdade e seus axiomas abaixo).

Nem todos esses símbolos são necessários na lógica de primeira ordem. Qualquer um dos quantificadores junto com negação, conjunção (ou disjunção), variáveis, colchetes e igualdade são suficientes.

Outros símbolos lógicos incluem o seguinte:

• Constantes da verdade: T, V ou ? para "verdade" e F, O, ou : para "false" (V e O são da notação polonesa). Sem tais operadores lógicos de valência 0, estas duas constantes só podem ser expressas usando quantificadores.
• Conectivos lógicos adicionais como o acidente vascular cerebral Sheffer, DPQ (NAND) e exclusivo ou, JPQ.

Símbolos não lógicos

Símbolos não lógicos representam predicados (relações), funções e constantes. Costumava ser uma prática padrão usar um conjunto fixo e infinito de símbolos não lógicos para todos os propósitos:

• Para cada inteiro n≥ 0, há uma coleção de n-ary, ou n- Não.lugar, símbolos predicados. Porque eles representam relações entre n elementos, eles também são chamados símbolos de relação. Para cada aridade n, há um suprimento infinito deles:

  Pⁿ₀, Pⁿ₁, Pⁿ₂, Pⁿ₃,

• Para cada inteiro n≥ 0, há infinitamente muitos n- Sim. símbolos de função:

  f ⁿ₀, f ⁿ₁, f ⁿ₂, f ⁿ₃,

Quando a aridade de um símbolo de predicado ou símbolo de função é clara a partir do contexto, o sobrescrito n geralmente é omitido.

Nesta abordagem tradicional, existe apenas uma linguagem de lógica de primeira ordem. Essa abordagem ainda é comum, especialmente em livros de orientação filosófica.

Uma prática mais recente é usar diferentes símbolos não lógicos de acordo com a aplicação que se tem em mente. Portanto, tornou-se necessário nomear o conjunto de todos os símbolos não lógicos usados em uma determinada aplicação. Esta escolha é feita através de uma assinatura.

Assinaturas típicas em matemática são {1, ×} ou apenas {×} para grupos, ou {0, 1, +, ×, <} para campos ordenados. Não há restrições quanto ao número de símbolos não lógicos. A assinatura pode ser vazia, finita ou infinita, até incontável. Assinaturas incontáveis ocorrem, por exemplo, em provas modernas do teorema de Löwenheim–Skolem.

Embora as assinaturas possam, em alguns casos, implicar como os símbolos não lógicos devem ser interpretados, a interpretação dos símbolos não lógicos na assinatura é separada (e não necessariamente fixa). As assinaturas dizem respeito à sintaxe e não à semântica.

Nesta abordagem, todo símbolo não lógico é de um dos seguintes tipos:

• A símbolo de predicado (ou símbolo de relação) com alguns valencia (ou ar!, número de argumentos) superior ou igual a 0. Estes são muitas vezes denotados por letras maiúsculas como P, Q e R. Exemplos:
  • Em P(x), P é um símbolo predicado de valência 1. Uma interpretação possível é "x é um homem".
  • Em Q(x,Sim.), Q é um símbolo predicado de valência 2. Possíveis interpretações incluem "x é maior do que Sim."e"x é o pai de Sim.".
  • Relações de valência 0 podem ser identificadas com variáveis proposicionais, que podem representar qualquer declaração. Uma interpretação possível de R é "Socrates é um homem".
• A símbolo de função, com alguma valência maior ou igual a 0. Estes são muitas vezes denotados por letras minúsculas roman tais como f, g e h. Exemplos:
  • f(x) pode ser interpretado como "o pai de x". Na aritmética, pode ser "x". Na teoria dos conjuntos, pode ser para "o conjunto de poder de x".
  • Na aritmética, g(x,Sim.) pode ficar parado "x+Sim.". Na teoria dos conjuntos, pode ser para "a união de x e Sim.".
  • Símbolos de função da valência 0 são chamados símbolos constantes, e muitas vezes são denotados por letras minúsculas no início do alfabeto, como um, b) e c. O símbolo um pode representar Sócrates. Na aritmética, pode ser para 0. Na teoria dos conjuntos, pode ser para o conjunto vazio.

A abordagem tradicional pode ser recuperada na abordagem moderna, simplesmente especificando o "custom" assinatura para consistir nas sequências tradicionais de símbolos não lógicos.

Regras de formação

<índice> : "
| <índice> "
<variável> : "x" <índice><constante constante> : "c" <índice><função unary> : "f1" <índice><função binária> : "f2" <índice><função ternary> : "f3" <índice><predicados indesejáveis> : "P1" <índice><predicado binário> : "p2" <índice><ternary predicado> : "P3" <índice><termo> : <variável> | <constante constante> | <função unary> "(<termo> ")"
| <função binária> "(<termo> ", <termo> ")"
| <função ternary> "(<termo> ", <termo> ", <termo> ")"
<fórmula atômica> : "TRUE"
| "FALSE"
| <termo> "=" <termo>| <predicados indesejáveis> "(<termo> ")"
| <predicado binário> "(<termo> ", <termo> ")"
| <ternary predicado> "(<termo> ", <termo> ", <termo> ")"
<fórmula> : <fórmula atômica> | "¬" <fórmula>| <fórmula> "Claude" <fórmula>| <fórmula> "Faça" <fórmula>| <fórmula> "⇒" <fórmula>| <fórmula> """ <fórmula>| "()" <fórmula> ")"
| "∀" <variável> <fórmula>| "∃" <variável> <fórmula>

As regras de formação definem os termos e fórmulas da lógica de primeira ordem. Quando termos e fórmulas são representados como sequências de símbolos, essas regras podem ser usadas para escrever uma gramática formal para termos e fórmulas. Essas regras são geralmente livres de contexto (cada produção tem um único símbolo no lado esquerdo), exceto que o conjunto de símbolos pode ser infinito e pode haver muitos símbolos iniciais, por exemplo, as variáveis no caso de termos.

Termos

O conjunto de termos é definido indutivamente pelas seguintes regras:

• Variáveis. Qualquer símbolo variável é um termo.
• Funções. Se f é um n- símbolo de função saudável, e )₁, )_n são termos, então f()₁,)_n) é um termo. Em particular, símbolos denotando constantes individuais são símbolos de função nulo, e assim são termos.

Apenas expressões que podem ser obtidas por um número finito de aplicações das regras 1 e 2 são termos. Por exemplo, nenhuma expressão envolvendo um símbolo de predicado é um termo.

Fórmulas

O conjunto de fórmulas (também chamado de fórmulas bem formadas ou WFFs) é definido indutivamente pelas seguintes regras:

• Predicar símbolos. Se P é um n- símbolo de predicado e )₁, )_n são termos então P()₁,)_n) é uma fórmula.
• Igualdade. Se o símbolo de igualdade é considerado parte da lógica, e )₁ e )₂ são termos, então )₁ = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = )₂ é uma fórmula.
• Negação. Se φ φ - Sim. é uma fórmula, então ? ? φ φ {displaystyle lnot varphi } é uma fórmula.
• Conectivos binários. Se φ φ - Sim. e ? ? - Sim. são fórmulas, então (φ φ → → ? ? {displaystyle varphi rightarrow psi }) é uma fórmula. Regras semelhantes aplicam-se a outros conjuntivos lógicos binários.
• Quantifiers. Se φ φ - Sim. é uma fórmula e x é uma variável, então Gerenciamento de contas Gerenciamento de contas xφ φ {displaystyle forall xvarphi ? (para todos x, φ φ - Sim. detenções) e Detalhe Detalhe xφ φ {displaystyle existe xvarphi } (há x tal que φ φ - Sim.) são fórmulas.

Apenas expressões que podem ser obtidas por um número finito de aplicações das regras 1–5 são fórmulas. As fórmulas obtidas das duas primeiras regras são ditas como fórmulas atômicas.

Por exemplo,

Gerenciamento de contas Gerenciamento de contas xGerenciamento de contas Gerenciamento de contas Sim.(P(f(x))→ → ? ? (P(x)→ → Q(f(Sim.),x,zangão.))){displaystyle forall xforall y(P(f(x)))rightarrow neg (P(x)rightarrow Q(f(y),x,z))}

é uma fórmula, se f é um símbolo de função unary, P um símbolo predicado unary, e Q um símbolo de predicado ternary. No entanto, Gerenciamento de contas Gerenciamento de contas xx→ → {displaystyle forall x,xrightarrow } não é uma fórmula, embora seja uma cadeia de símbolos do alfabeto.

O papel dos parênteses na definição é garantir que qualquer fórmula só possa ser obtida de uma maneira - seguindo a definição indutiva (ou seja, há uma árvore de análise única para cada fórmula). Esta propriedade é conhecida como legibilidade única das fórmulas. Existem muitas convenções para onde os parênteses são usados nas fórmulas. Por exemplo, alguns autores usam dois-pontos ou pontos finais em vez de parênteses, ou alteram os lugares em que os parênteses são inseridos. A definição particular de cada autor deve ser acompanhada de uma prova de legibilidade única.

Esta definição de uma fórmula não suporta a definição de uma função if-then-else ite(c, a, b), onde "c" é uma condição expressa como uma fórmula, que retornaria "a" se c for verdadeiro e "b" se for falso. Isso ocorre porque predicados e funções só podem aceitar termos como parâmetros, mas o primeiro parâmetro é uma fórmula. Algumas linguagens construídas na lógica de primeira ordem, como SMT-LIB 2.0, adicionam isso.

Convenções de notação

Por conveniência, foram desenvolvidas convenções sobre a precedência dos operadores lógicos, para evitar a necessidade de escrever parênteses em alguns casos. Essas regras são semelhantes à ordem das operações em aritmética. Uma convenção comum é:

• ? ? - Sim. é avaliado primeiro
• ∧ ∧ Não. e ∨ ∨ - Sim. são avaliados em seguida
• Quantifiers são avaliados em seguida
• → → - Sim. é avaliado por último.

Além disso, pontuação extra não exigida pela definição pode ser inserida—para facilitar a leitura das fórmulas. Assim a fórmula

? ? Gerenciamento de contas Gerenciamento de contas xP(x)→ → Detalhe Detalhe x? ? P(x){displaystyle lnot forall xP(x)to existe xlnot P(x)}

pode ser escrito como

(? ? Não.Gerenciamento de contas Gerenciamento de contas xP(x)])→ → Detalhe Detalhe xNão.? ? P(x)].{displaystyle (lnot [forall xP(x)])to existe x[lnot P(x)].}

Em alguns campos, é comum usar notação infixa para funções e relações binárias, ao invés da notação prefixada definida acima. Por exemplo, em aritmética, normalmente se escreve "2 + 2 = 4" em vez de "=(+(2,2),4)". É comum considerar fórmulas em notação infixa como abreviaturas para as fórmulas correspondentes em notação prefixada, cf. também estrutura de termos vs. representação.

As definições acima usam notação infixa para conjuntivos binários, como → → - Sim.. Uma convenção menos comum é a notação polonesa, na qual se escreve → → Não., ∧ ∧ - Sim. e assim por diante na frente de seus argumentos em vez de entre eles. Esta convenção é vantajosa em que permite que todos os símbolos de pontuação sejam descartados. Como tal, a notação polonesa é compacta e elegante, mas raramente usada na prática porque é difícil para os seres humanos ler. Na notação polonesa, a fórmula

Gerenciamento de contas Gerenciamento de contas xGerenciamento de contas Gerenciamento de contas Sim.(P(f(x))→ → ? ? (P(x)→ → Q(f(Sim.),x,zangão.))){displaystyle forall xforall y(P(f(x)))rightarrow neg (P(x)rightarrow Q(f(y),x,z))}

torna-se "∀x∀y→Pfx¬→ PxQfyxz".

Variáveis livres e vinculadas

Em uma fórmula, uma variável pode ocorrer grátis ou Ligação (ou ambos). Uma formalização desta noção é devido a Quine, primeiro o conceito de ocorrência variável é definido, então se uma ocorrência variável é livre ou vinculada, então se um símbolo variável global é livre ou vinculado. Para distinguir diferentes ocorrências do símbolo idêntico x, cada ocorrência de um símbolo variável x em uma fórmula φ é identificado com a substring inicial de φ até o ponto em que disse a instância do símbolo x aparece.^p.297 Então, uma ocorrência de x é dito para ser ligado se essa ocorrência de x está dentro do escopo de pelo menos um de qualquer Detalhe Detalhe x{displaystyle existe x} ou Gerenciamento de contas Gerenciamento de contas x{displaystyle forall x}. Finalmente, x está ligado em φ se todas as ocorrências de x em φ estão ligados.^pp.142--143

Intuitivamente, um símbolo de variável é livre em uma fórmula se em nenhum ponto for quantificado:^pp.142--143 em ∀y P(x, y), a única ocorrência da variável x é livre enquanto o de y está vinculado. As ocorrências de variável livre e limitada em uma fórmula são definidas indutivamente como segue.

Fórmulas atômicas

Se φ é uma fórmula atômica, então x ocorre livre em φ se e somente se x ocorre em φ. Além disso, não há variáveis vinculadas em qualquer fórmula atômica.

Negação

x ocorre livre em ¬φ se e somente se x ocorre livre em φ. x ocorre ligado em ¬φ se e somente se x ocorre ligado φ

Conectivos binários

x ocorre livre em (φ → ?) se e somente se x ocorre livre em qualquer φ ou ?. x ocorre ligado em (φ → ?) se e somente se x ocorre ligado em qualquer φ ou ?. A mesma regra se aplica a qualquer outra conjuntiva binária no lugar de →.

Quantifiers

x ocorre livre em Gerenciamento de contasSim. φ, se e somente se x ocorre livre em φ e x é um símbolo diferente de Sim.. Também, x ocorre ligado Gerenciamento de contasSim. φ, se e somente se x o Sim. ou x ocorre ligado φ. A mesma regra detém com Detalhe no lugar de Gerenciamento de contas.

Por exemplo, em ∀x ∀y (P(x) → Q(x,f(x),z)) , x e y ocorrem apenas vinculados, z ocorrem apenas livres e w não ocorre porque não ocorre na fórmula.

Variáveis livres e ligadas de uma fórmula não precisam ser conjuntos disjuntos: na fórmula P(x) → ∀ x Q(x), a primeira ocorrência de x, como argumento de P, é livre enquanto o segundo, como argumento de Q, é vinculado.

Uma fórmula na lógica de primeira ordem sem ocorrências de variáveis livres é chamada de frase de primeira ordem. Estas são as fórmulas que terão valores de verdade bem definidos sob uma interpretação. Por exemplo, se uma fórmula como Phil(x) é verdadeira deve depender do que x representa. Mas a sentença ∃x Phil(x) será verdadeira ou falsa em uma dada interpretação.

Exemplo: grupos abelianos ordenados

Em matemática, a linguagem de grupos abelianos ordenados tem um símbolo de constante 0, um símbolo de função unária −, um símbolo de função binária + e um símbolo de relação binária ≤. Então:

• As expressões +(x, Sim.) e + (x, +Sim.,zangão.) termos. Estes são geralmente escritos como x + Sim. e x + Sim. - Sim. zangão..
• As expressões +(x, Sim.) = 0 e ≤(+(x, +Sim.,zangão.), +(x, Sim.) são fórmulas atômicas. Estes são geralmente escritos como x + Sim. = 0 e x + Sim. - Sim. zangão. ≤ x + Sim..
• A expressão (Gerenciamento de contas Gerenciamento de contas xGerenciamento de contas Gerenciamento de contas Sim.Não.≤ ≤ ⁡ ⁡ (+⁡ ⁡ (x,Sim.),zangão.)→ → Gerenciamento de contas Gerenciamento de contas xGerenciamento de contas Gerenciamento de contas Sim.+⁡ ⁡ (x,Sim.)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0)](forall xforall y,[mathop {leq } (mathop {+} (x,y),z)to forall x,forall y,mathop {+} (x,y)=0)} é um fórmula, que é geralmente escrito como Gerenciamento de contas Gerenciamento de contas xGerenciamento de contas Gerenciamento de contas Sim.(x+Sim.≤ ≤ zangão.)→ → Gerenciamento de contas Gerenciamento de contas xGerenciamento de contas Gerenciamento de contas Sim.(x+Sim.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0).{displaystyle forall xforall y(x+yleq z)to forall xforall y(x+y=0). ? Esta fórmula tem uma variável livre, zangão..

Os axiomas para grupos abelianos ordenados podem ser expressos como um conjunto de frases na língua. Por exemplo, o axioma afirmando que o grupo é comutativo é geralmente escrito (Gerenciamento de contas Gerenciamento de contas x)(Gerenciamento de contas Gerenciamento de contas Sim.)Não.x+Sim.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Sim.+x].(forall x)(forall y)[x+y=y+x].}

Semântica

Uma interpretação de uma linguagem de primeira ordem atribui uma denotação a cada símbolo não lógico (símbolo de predicado, símbolo de função ou símbolo constante) nessa linguagem. Também determina um domínio de discurso que especifica o alcance dos quantificadores. O resultado é que cada termo recebe um objeto que representa, cada predicado recebe uma propriedade de objetos e cada sentença recebe um valor de verdade. Dessa forma, uma interpretação fornece significado semântico aos termos, predicados e fórmulas da linguagem. O estudo das interpretações das linguagens formais é chamado de semântica formal. O que se segue é uma descrição da semântica padrão ou tarskiana para a lógica de primeira ordem. (Também é possível definir a semântica do jogo para a lógica de primeira ordem, mas, além de exigir o axioma da escolha, a semântica do jogo concorda com a semântica tarskiana da lógica de primeira ordem, portanto, a semântica do jogo não será elaborada aqui.)

Estruturas de primeira ordem

A forma mais comum de especificar uma interpretação (especialmente em matemática) é especificar uma estrutura (também chamada de modelo; veja abaixo). A estrutura consiste em um domínio de discurso D e uma função de interpretação I mapeando símbolos não lógicos para predicados, funções e constantes.

O domínio do discurso D é um conjunto vazio de "objetos" de algum tipo. Intuitivamente, dada uma interpretação, uma fórmula de primeira ordem torna-se uma declaração sobre esses objetos; por exemplo, Detalhe Detalhe xP(x){displaystyle existe xP(x)} afirma a existência de algum objeto em D para o qual o predicado P é verdade (ou, mais precisamente, para o qual o predicado atribuído ao símbolo predicado P pela interpretação é verdadeira). Por exemplo, pode-se tomar D para ser o conjunto de inteiros.

Símbolos não lógicos são interpretados da seguinte forma:

• A interpretação de um n- símbolo de função é uma função de Dⁿ para D. Por exemplo, se o domínio do discurso é o conjunto de inteiros, um símbolo de função f de arity 2 pode ser interpretado como a função que dá a soma de seus argumentos. Em outras palavras, o símbolo f está associado à função Eu...(f)(f)} que, nesta interpretação, é adição.

• A interpretação de um símbolo constante (um símbolo de função da aridade 0) é uma função de D⁰ (um conjunto cujo único membro é o tupla vazio) D, que pode ser simplesmente identificado com um objeto em D. Por exemplo, uma interpretação pode atribuir o valor Eu...(c)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =10.(c)=10} ao símbolo constante cNão..

• A interpretação de um n-ary predicate símbolo é um conjunto de n-tuples de elementos de D, dando os argumentos para os quais o predicado é verdadeiro. Por exemplo, uma interpretação Eu...(P)(P)} de um símbolo predicado binário P pode ser o conjunto de pares de inteiros tal que o primeiro é menos do que o segundo. De acordo com esta interpretação, o predicado P seria verdade se seu primeiro argumento é menos do que seu segundo argumento. Equivalentemente, símbolos predicados podem ser atribuídos funções de valor booleano a partir de Dⁿ para ()Rue,fumEu...Se?{displaystyle {mathrm {true,false} }}.

Avaliação de valores de verdade

Uma fórmula avalia a verdadeira ou falsa dada uma interpretação e uma atribuição variável μ que associa um elemento do domínio do discurso com cada variável. A razão pela qual uma tarefa variável é necessária é dar significados a fórmulas com variáveis livres, como Sim.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =x- Sim.. O valor da verdade desta fórmula muda dependendo se x e Sim. denota o mesmo indivíduo.

Primeiro, a atribuição variável μ pode ser estendida a todos os termos da linguagem, com o resultado de que cada termo mapeia para um único elemento do domínio do discurso. As seguintes regras são usadas para fazer essa atribuição:

• Variáveis. Cada variável x avalia para μ(x)
• Funções. Termos e condições )1,...... ,)n{displaystyle t_{1},ldotst_{n}} que foram avaliados em elementos D1,...... ,DnNão. d_{1},ldotsd_{n}} do domínio do discurso, e um n- símbolo de função f, o termo f()1,...... ,)n){displaystyle f(t_{1},ldotst_{n})} avalia para (Eu...(f))(D1,...... ,Dn)(I(f))(d_{1},ldotsd_{n})}.

Em seguida, cada fórmula recebe um valor de verdade. A definição indutiva usada para fazer essa atribuição é chamada de esquema T.

• Fórmulas atômicas (1). Uma fórmula P()1,...... ,)n){displaystyle P(t_{1},ldotst_{n})} está associado ao valor verdadeiro ou falso dependendo se ⟨ ⟨ v1,...... ,vn)) ∈ ∈ Eu...(P){displaystyle langle v_{1},ldotsv_{n}rangle in I(P)}, onde v1,...... ,vn{displaystyle v_{1},ldotsv_{n}} são a avaliação dos termos )1,...... ,)n{displaystyle t_{1},ldotst_{n}} e Eu...(P)(P)} é a interpretação de PNão. P., que por suposição é um subconjunto de DnNão. D^{n}}.
• Fórmulas atômicas (2). Uma fórmula )1= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =)2Não. t_{1}=t_{2}} é atribuído verdadeiro se )1Não. t_{1}} e )2Não. t_{2}} avaliar para o mesmo objeto do domínio do discurso (veja a seção sobre igualdade abaixo).
• Conectivos lógicos. Uma fórmula no formulário ? ? φ φ {displaystyle neg varphi }, φ φ → → ? ? {displaystyle varphi rightarrow psi }, etc. é avaliado de acordo com a tabela de verdade para o conjuntivo em questão, como na lógica proposicional.
• quantificadores existenciais. Uma fórmula Detalhe Detalhe xφ φ (x)(x)} é verdade de acordo com M e μ μ - Sim. se existe uma avaliação μ μ ?- Sim. das variáveis que só diferem μ μ - Sim. sobre a avaliação x e tal que φ é verdadeiro de acordo com a interpretação M e a tarefa variável μ μ ?- Sim.. Esta definição formal capta a ideia de que Detalhe Detalhe xφ φ (x)(x)} é verdade se e somente se houver uma maneira de escolher um valor para x tal que φ(x) está satisfeito.
• quantificadores universais. Uma fórmula Gerenciamento de contas Gerenciamento de contas xφ φ (x){displaystyle forall xvarphi (x)} é verdade de acordo com M e μ μ - Sim. se φ(x) é verdade para cada par composto pela interpretação M e alguma tarefa variável μ μ ?- Sim. que difere de μ μ - Sim. apenas no valor de x. Isso capta a ideia de que Gerenciamento de contas Gerenciamento de contas xφ φ (x){displaystyle forall xvarphi (x)} é verdade se cada escolha possível de um valor para x causas φ(x) ser verdade.

Se uma fórmula não contém variáveis livres, e assim é uma frase, então a atribuição de variável inicial não afeta seu valor de verdade. Em outras palavras, uma frase é verdadeira de acordo com M e μ μ - Sim. se e somente se for verdade de acordo com M e todas as outras tarefas variáveis μ μ ?- Sim..

Existe uma segunda abordagem comum para definir valores de verdade que não depende de funções de atribuição de variáveis. Em vez disso, dada uma interpretação M, primeiro adiciona-se à assinatura uma coleção de símbolos constantes, um para cada elemento do domínio do discurso em M; digamos que para cada d no domínio o símbolo constante c_d é fixo. A interpretação é estendida para que cada novo símbolo constante seja atribuído ao seu elemento correspondente do domínio. Um agora define a verdade para fórmulas quantificadas sintaticamente, como segue:

• Quificadores existenciais (alterados). Uma fórmula Detalhe Detalhe xφ φ (x)(x)} é verdade de acordo com M se houver algum D no domínio do discurso tal que φ φ (cD)(c_{d})} Detém. Aqui. φ φ (cD)(c_{d})} é o resultado da substituição c_D para cada ocorrência livre de x em φ.
• quantificadores universais (alternação). Uma fórmula Gerenciamento de contas Gerenciamento de contas xφ φ (x){displaystyle forall xvarphi (x)} é verdade de acordo com M se, para cada D no domínio do discurso, φ φ (cD)(c_{d})} é verdade de acordo com M.

Esta abordagem alternativa fornece exatamente os mesmos valores de verdade para todas as sentenças que a abordagem por meio de atribuições de variáveis.

Validade, satisfazibilidade e consequência lógica

Se uma frase φ avaliar para verdadeiro sob uma dada interpretação M, um diz que M satisfaz φ; isto é denotado M⊨ ⊨ φ φ Não. MvDash varphi }. Uma sentença é satisfatível se houver alguma interpretação sob a qual é verdade. Isto é um pouco diferente do símbolo ⊨ ⊨ - Sim. da teoria do modelo, onde M⊨ ⊨ φ φ Não. MvDash phi } denota satisfação em um modelo, ou seja, "há uma atribuição adequada de valores em MNão.'s domínio para símbolos variáveis de φ φ - Sim.".

A satisfação de fórmulas com variáveis livres é mais complicada, porque uma interpretação por si só não determina o valor da verdade de tal fórmula. A convenção mais comum é que uma fórmula φ com variáveis livres x1Não. x_{1}}, xnNão. x_{n}} é dito para ser satisfeito por uma interpretação se a fórmula φ permanece verdadeira, independentemente de que indivíduos do domínio do discurso são atribuídos a suas variáveis livres x1Não. x_{1}}, xnNão. x_{n}}. Isso tem o mesmo efeito de dizer que uma fórmula φ é satisfeita se e somente se o seu fechamento universal Gerenciamento de contas Gerenciamento de contas x1...... Gerenciamento de contas Gerenciamento de contas xnφ φ (x1,...... ,xn){displaystyle forall x_{1}dots forall x_{n}phi (x_{1},dotsx_{n}) ? está satisfeito.

Uma fórmula é logicamente válida (ou simplesmente válida) se for verdadeira em todas as interpretações. Essas fórmulas desempenham um papel semelhante às tautologias na lógica proposicional.

Uma fórmula φ é uma consequência lógica de uma fórmula ψ se toda interpretação que torna ψ verdadeiro também torna φ verdadeiro. Neste caso diz-se que φ é logicamente implicado por ψ.

Algebrizações

Uma abordagem alternativa para a semântica da lógica de primeira ordem procede através da álgebra abstrata. Esta abordagem generaliza as álgebras de Lindenbaum-Tarski da lógica proposicional. Existem três maneiras de eliminar variáveis quantificadas da lógica de primeira ordem que não envolvem a substituição de quantificadores por outros operadores de termo de ligação variável:

• Álgebra cilíndrica, por Alfred Tarski e colegas;
• Álgebra poliádica, por Paul Halmos;
• Predicar a lógica do funtor, principalmente devido a Willard Quine.

Essas álgebras são todas redes que estendem adequadamente a álgebra booleana de dois elementos.

Tarski e Givant (1987) mostraram que o fragmento da lógica de primeira ordem que não tem sentença atômica no escopo de mais de três quantificadores tem o mesmo poder expressivo que a álgebra de relações. Este fragmento é de grande interesse porque é suficiente para a aritmética de Peano e para a maioria da teoria axiomática dos conjuntos, incluindo o ZFC canônico. Eles também provam que a lógica de primeira ordem com um par ordenado primitivo é equivalente a uma álgebra de relação com duas funções de projeção de pares ordenados.

Teorias, modelos e classes elementares de primeira ordem

Uma teoria de primeira ordem de uma assinatura particular é um conjunto de axiomas, que são sentenças que consistem em símbolos dessa assinatura. O conjunto de axiomas geralmente é finito ou recursivamente enumerável, caso em que a teoria é chamada de efetiva. Alguns autores exigem que as teorias também incluam todas as consequências lógicas dos axiomas. Os axiomas são considerados válidos dentro da teoria e deles podem ser derivadas outras sentenças válidas dentro da teoria.

Uma estrutura de primeira ordem que satisfaz todas as sentenças em uma dada teoria é chamada de modelo da teoria. Uma classe elementar é o conjunto de todas as estruturas que satisfazem uma teoria particular. Essas classes são um assunto principal de estudo na teoria do modelo.

Muitas teorias têm uma interpretação pretendida, um determinado modelo que é levado em consideração ao estudar a teoria. Por exemplo, a interpretação pretendida da aritmética de Peano consiste nos números naturais usuais com suas operações usuais. No entanto, o teorema de Löwenheim-Skolem mostra que a maioria das teorias de primeira ordem também terá outros modelos não padronizados.

Uma teoria é consistente se não for possível provar uma contradição a partir dos axiomas da teoria. Uma teoria é completa se, para cada fórmula em sua assinatura, essa fórmula ou sua negação é uma consequência lógica dos axiomas da teoria. O teorema da incompletude de Gödel mostra que as teorias de primeira ordem eficazes que incluem uma porção suficiente da teoria dos números naturais nunca podem ser consistentes e completas.

Domínios vazios

A definição acima exige que o domínio do discurso de qualquer interpretação não seja vazio. Existem configurações, como lógica inclusiva, em que domínios vazios são permitidos. Além disso, se uma classe de estruturas algébricas inclui uma estrutura vazia (por exemplo, há um poset vazio), essa classe só pode ser uma classe elementar na lógica de primeira ordem se domínios vazios forem permitidos ou se a estrutura vazia for removida da classe.

Existem várias dificuldades com domínios vazios, no entanto:

• Muitas regras comuns de inferência só são válidas quando o domínio do discurso é necessário para ser nada. Um exemplo é a regra afirmando que φ φ ∨ ∨ Detalhe Detalhe x? ? {displaystyle varphi lor existe xpsi } implica Detalhe Detalhe x(φ φ ∨ ∨ ? ? ){displaystyle existe x(varphi lor psi)} quando x não é uma variável livre em φ φ - Sim.. Esta regra, que é usada para colocar fórmulas em forma normal prenex, é som em domínios vazios, mas sem som se o domínio vazio é permitido.
• A definição de verdade em uma interpretação que usa uma função de atribuição variável não pode funcionar com domínios vazios, porque não há funções de atribuição variável cujo intervalo está vazio. (Similarly, não se pode atribuir interpretações a símbolos constantes.) Esta definição de verdade requer que se deve selecionar uma função de atribuição variável (μ acima) antes que os valores de verdade para fórmulas atômicas pares possam ser definidos. Então o valor da verdade de uma sentença é definido como sendo o seu valor de verdade sob qualquer atribuição variável, e é provado que esse valor de verdade não depende de qual atribuição é escolhida. Esta técnica não funciona se não houver nenhuma função de atribuição; deve ser alterada para acomodar domínios vazios.

Assim, quando o domínio vazio é permitido, muitas vezes deve ser tratado como um caso especial. A maioria dos autores, no entanto, simplesmente exclui o domínio vazio por definição.

Sistemas dedutivos

Um sistema dedutivo é usado para demonstrar, em uma base puramente sintática, que uma fórmula é uma consequência lógica de outra fórmula. Existem muitos desses sistemas para lógica de primeira ordem, incluindo sistemas dedutivos no estilo de Hilbert, dedução natural, cálculo de seqüências, método tableaux e resolução. Estes compartilham a propriedade comum de que uma dedução é um objeto sintático finito; o formato desse objeto e a forma como ele é construído variam muito. Essas próprias deduções finitas são freqüentemente chamadas de derivações na teoria da prova. Eles também são freqüentemente chamados de provas, mas são completamente formalizados ao contrário das provas matemáticas de linguagem natural.

Um sistema dedutivo é bom se qualquer fórmula que pode ser derivada no sistema for logicamente válida. Por outro lado, um sistema dedutivo é completo se toda fórmula logicamente válida for derivável. Todos os sistemas discutidos neste artigo são sólidos e completos. Eles também compartilham a propriedade de que é possível verificar efetivamente se uma dedução supostamente válida é realmente uma dedução; tais sistemas de dedução são chamados de efetivos.

Uma propriedade chave dos sistemas dedutivos é que eles são puramente sintáticos, de modo que as derivações podem ser verificadas sem considerar qualquer interpretação. Assim, um argumento sólido está correto em todas as interpretações possíveis da linguagem, independentemente de essa interpretação ser sobre matemática, economia ou alguma outra área.

Em geral, a consequência lógica na lógica de primeira ordem é apenas semidecidível: se uma sentença A implica logicamente uma sentença B, então isso pode ser descoberto (por exemplo, procurando por uma prova até que uma seja encontrada, usando algum som eficaz, sistema de prova completo). No entanto, se A não implica logicamente B, isso não significa que A implica logicamente a negação de B. Não há procedimento efetivo que, dadas as fórmulas A e B, sempre decida corretamente se A implica logicamente B.

Regras de inferência

Uma regra de inferência afirma que, dada uma fórmula específica (ou conjunto de fórmulas) com uma certa propriedade como hipótese, outra fórmula específica (ou conjunto de fórmulas) pode ser derivada como conclusão. A regra é sólida (ou preservadora da verdade) se preserva a validade no sentido de que sempre que qualquer interpretação satisfizer a hipótese, essa interpretação também satisfará a conclusão.

Por exemplo, uma regra comum de inferência é a regra de substituição. Se t é um termo e φ é uma fórmula possivelmente contendo a variável x, então φ[t/x ] é o resultado da substituição de todas as instâncias livres de x por t em φ. A regra de substituição afirma que para qualquer φ e qualquer termo t, pode-se concluir φ[t/x] de φ desde que nenhuma variável livre de t torna-se vinculado durante o processo de substituição. (Se alguma variável livre de t se torna vinculada, então para substituir t por x é necessário primeiro alterar as variáveis vinculadas de φ para diferir das variáveis livres de t.)

Para ver por que a restrição de variáveis vinculadas é necessária, considere a fórmula logicamente válida φ dada por Detalhe Detalhe x(x= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Sim.)(x=y)}, na assinatura de (0,1, +, ×,=) de aritmética. Se ) é o termo "x + 1", a fórmula φ[)/Sim.É. Detalhe Detalhe x(x= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =x+1)(x=x+1)}, que será falso em muitas interpretações. O problema é que a variável livre x de ) ficou ligado durante a substituição. A substituição pretendida pode ser obtida por renomear a variável delimitada x de φ a algo mais, diga zangão., de modo que a fórmula após substituição é Detalhe Detalhe zangão.(zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =x+1){displaystyle existe z(z=x+1)}, que é novamente logicamente válido.

A regra de substituição demonstra vários aspectos comuns das regras de inferência. É inteiramente sintático; pode-se dizer se foi corretamente aplicado sem apelar para qualquer interpretação. Possui limitações (definidas sintaticamente) sobre quando pode ser aplicado, que devem ser respeitadas para preservar a correção das derivações. Além disso, como costuma acontecer, essas limitações são necessárias devido às interações entre variáveis livres e ligadas que ocorrem durante as manipulações sintáticas das fórmulas envolvidas na regra de inferência.

Sistemas estilo Hilbert e dedução natural

Uma dedução em um sistema dedutivo estilo Hilbert é uma lista de fórmulas, cada uma das quais é um axioma lógico, uma hipótese que foi assumida para a derivação em questão ou segue de fórmulas anteriores através de uma regra de inferência. Os axiomas lógicos consistem em vários esquemas de axiomas de fórmulas logicamente válidas; estes abrangem uma quantidade significativa de lógica proposicional. As regras de inferência permitem a manipulação de quantificadores. Os sistemas típicos de estilo Hilbert têm um pequeno número de regras de inferência, juntamente com vários esquemas infinitos de axiomas lógicos. É comum ter apenas modus ponens e generalização universal como regras de inferência.

Os sistemas de dedução natural se assemelham aos sistemas de estilo Hilbert, pois uma dedução é uma lista finita de fórmulas. No entanto, os sistemas de dedução natural não possuem axiomas lógicos; eles compensam adicionando regras adicionais de inferência que podem ser usadas para manipular os conectivos lógicos nas fórmulas da prova.

Cálculo sequencial

O cálculo de seqüentes foi desenvolvido para estudar as propriedades dos sistemas de dedução natural. Em vez de trabalhar com uma fórmula por vez, ele usa sequentes, que são expressões da forma

A1,...... ,An? ? B1,...... ,Bk,{displaystyle A_{1},ldotsA_{n}vdash B_{1},ldots B_{k},

Onde um₁,..., A_n, B₁,..., B_k são fórmulas e os símbolos virados ? ? - Sim. é usado como pontuação para separar as duas metades. Intuitivamente, um sequente expressa a ideia de que (A1∧ ∧ ⋯ ⋯ ∧ ∧ An)(A_{1}land cdots land A_{n})} implica (B1∨ ∨ ⋯ ⋯ ∨ ∨ Bk)(B_{1}lor cdots lor B_{k})}.

Método Tableaux

Uma prova de tableaux para a fórmula proposicional ((a ∨ ¬b) ∧ b) → a

Ao contrário dos métodos descritos, as derivações no método tableaux não são listas de fórmulas. Em vez disso, uma derivação é uma árvore de fórmulas. Para mostrar que uma fórmula A é provável, o método tableaux tenta demonstrar que a negação de A é insatisfável. A árvore da derivação tem ? ? A- Sim. em sua raiz; os ramos da árvore de uma forma que reflete a estrutura da fórmula. Por exemplo, para mostrar que C∨ ∨ DNão. Clor D. é insatisfável exige mostrar que C e D são cada um insatisfável; isso corresponde a um ponto de ramificação na árvore com pai C∨ ∨ DNão. Clor D. e crianças C e D.

Resolução

A regra de resolução é uma única regra de inferência que, juntamente com a unificação, é sólida e completa para a lógica de primeira ordem. Assim como no método tableaux, uma fórmula é provada mostrando que a negação da fórmula é insatisfatória. A resolução é comumente usada na prova automatizada de teoremas.

O método de resolução funciona apenas com fórmulas que são disjunções de fórmulas atômicas; fórmulas arbitrárias devem primeiro ser convertidas para esta forma através de Skolemization. A regra de resolução afirma que a partir das hipóteses A1∨ ∨ ⋯ ⋯ ∨ ∨ Ak∨ ∨ C{displaystyle A_{1}lor cdots lor A_{k}lor C. e B1∨ ∨ ⋯ ⋯ ∨ ∨ BEu...∨ ∨ ? ? C{displaystyle B_{1}lor cdots lor B_{l}lor lnot C}, a conclusão A1∨ ∨ ⋯ ⋯ ∨ ∨ Ak∨ ∨ B1∨ ∨ ⋯ ⋯ ∨ ∨ BEu...{displaystyle A_{1}lor cdots lor A_{k}lor B_{1}lor cdots lor B_{l}} pode ser obtido.

Identidades comprováveis

Muitas identidades podem ser provadas, o que estabelece equivalências entre fórmulas particulares. Essas identidades permitem reorganizar fórmulas movendo quantificadores em outros conectivos e são úteis para colocar fórmulas na forma normal prenex. Algumas identidades prováveis incluem:

? ? Gerenciamento de contas Gerenciamento de contas xP(x)⇔ ⇔ Detalhe Detalhe x? ? P(x){displaystyle lnot forall x,P(x)Leftrightarrow exists x,lnot P(x)}

? ? Detalhe Detalhe xP(x)⇔ ⇔ Gerenciamento de contas Gerenciamento de contas x? ? P(x){displaystyle lnot existe x, P(x)Leftrightarrow forall x,lnot P(x)}

Gerenciamento de contas Gerenciamento de contas xGerenciamento de contas Gerenciamento de contas Sim.P(x,Sim.)⇔ ⇔ Gerenciamento de contas Gerenciamento de contas Sim.Gerenciamento de contas Gerenciamento de contas xP(x,Sim.){displaystyle forall x,forall y,P(x,y)Leftrightarrow forall y,forall x,P(x,y)}

Detalhe Detalhe xDetalhe Detalhe Sim.P(x,Sim.)⇔ ⇔ Detalhe Detalhe Sim.Detalhe Detalhe xP(x,Sim.){displaystyle existe x,exists y,P(x,y)Leftrightarrow exists y,exists x,P(x,y)}

Gerenciamento de contas Gerenciamento de contas xP(x)∧ ∧ Gerenciamento de contas Gerenciamento de contas xQ(x)⇔ ⇔ Gerenciamento de contas Gerenciamento de contas x(P(x)∧ ∧ Q(x)){displaystyle forall x,P(x)land forall x,Q(x)Leftrightarrow forall x,(P(x)land Q(x)}

Detalhe Detalhe xP(x)∨ ∨ Detalhe Detalhe xQ(x)⇔ ⇔ Detalhe Detalhe x(P(x)∨ ∨ Q(x)){displaystyle existe x, P(x)lor existe x, Q(x)Leftrightarrow exists x, (P(x)lor Q(x))}

P∧ ∧ Detalhe Detalhe xQ(x)⇔ ⇔ Detalhe Detalhe x(P∧ ∧ Q(x))Não. Pland exists x, Q(x)Leftrightarrow exists x, (Pland Q(x))} (onde) xNão. não deve ocorrer livre em PNão. P.)

P∨ ∨ Gerenciamento de contas Gerenciamento de contas xQ(x)⇔ ⇔ Gerenciamento de contas Gerenciamento de contas x(P∨ ∨ Q(x))Não. Plor forall x,Q(x)Leftrightarrow forall x,(Plor Q(x))} (onde) xNão. não deve ocorrer livre em PNão. P.)

Igualdade e seus axiomas

Existem várias convenções diferentes para usar a igualdade (ou identidade) na lógica de primeira ordem. A convenção mais comum, conhecida como lógica de primeira ordem com igualdade, inclui o símbolo de igualdade como um símbolo lógico primitivo que é sempre interpretado como a relação de igualdade real entre os membros do domínio do discurso, tal que o "dois" determinados membros são o mesmo membro. Essa abordagem também acrescenta certos axiomas sobre igualdade ao sistema dedutivo empregado. Esses axiomas de igualdade são:

• Reflexão. Para cada variável x, x = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = x.
• Substituição de funções. Para todas as variáveis x e Sim., e qualquer símbolo de função f,

  x = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Sim. → f(... x,... f(... Sim.,...).

• Substituição de fórmulas. Para quaisquer variáveis x e Sim. e qualquer fórmula φ(x), se φ' é obtido substituindo qualquer número de ocorrências livres de x em φ com Sim., tal que estes permanecem ocorrências livres de Sim., então

  x = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Sim. → (φ → φ').

Estes são esquemas de axiomas, cada um dos quais especifica um conjunto infinito de axiomas. O terceiro esquema é conhecido como Lei de Leibniz, "o princípio da substitutividade", "a indiscernibilidade dos idênticos", ou "o propriedade de substituição". O segundo esquema, envolvendo o símbolo de função f, é (equivalente a) um caso especial do terceiro esquema, usando a fórmula

x = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Sim. →f(... x,... zangão. → f(... Sim.,... zangão.).

Muitas outras propriedades de igualdade são consequências dos axiomas acima, por exemplo:

• Simetria. Se x = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Sim. então Sim. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = x.
• Transição. Se x = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Sim. e Sim. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = zangão. então x = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = zangão..

Lógica de primeira ordem sem igualdade

Uma abordagem alternativa considera a relação de igualdade como um símbolo não lógico. Esta convenção é conhecida como lógica de primeira ordem sem igualdade. Se uma relação de igualdade for incluída na assinatura, os axiomas de igualdade devem agora ser adicionados às teorias em consideração, se desejado, em vez de serem considerados regras de lógica. A principal diferença entre este método e a lógica de primeira ordem com igualdade é que uma interpretação pode agora interpretar dois indivíduos distintos como "iguais" (embora, pela lei de Leibniz, satisfaçam exatamente as mesmas fórmulas sob qualquer interpretação). Ou seja, a relação de igualdade pode agora ser interpretada por uma relação de equivalência arbitrária no domínio do discurso que é congruente com respeito às funções e relações da interpretação.

Quando esta segunda convenção é seguida, o termo modelo normal é usado para se referir a uma interpretação onde nenhum indivíduo distinto a e b satisfaz a = b. Na lógica de primeira ordem com igualdade, apenas modelos normais são considerados e, portanto, não há termo para um modelo diferente de modelo normal. Quando a lógica de primeira ordem sem igualdade é estudada, é necessário corrigir as declarações de resultados, como o teorema de Löwenheim-Skolem, para que apenas modelos normais sejam considerados.

A lógica de primeira ordem sem igualdade é frequentemente empregada no contexto da aritmética de segunda ordem e outras teorias de aritmética de ordem superior, onde a relação de igualdade entre conjuntos de números naturais é geralmente omitida.

Definindo igualdade dentro de uma teoria

Se uma teoria tem uma fórmula binária A(x,y) que satisfaz a reflexividade e a lei de Leibniz, a teoria é dito ter igualdade, ou ser uma teoria com igualdade. A teoria pode não ter todas as instâncias dos esquemas acima como axiomas, mas sim como teoremas deriváveis. Por exemplo, em teorias sem símbolos de função e um número finito de relações, é possível definir a igualdade em termos das relações, definindo os dois termos s e t para ser igual se qualquer relação for inalterada ao alterar s para t em qualquer argumento.

Algumas teorias permitem outras definições ad hoc de igualdade:

• Na teoria de ordens parciais com um símbolo de relação ≤, pode-se definir S = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ) para ser uma abreviatura para S ≤ ) ∧ ) ≤ S.
• Em teoria definida com uma relação ∈, pode-se definir S = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ) para ser uma abreviatura para Gerenciamento de contasx (S ∈ x ↔ ) ∈ x) LUXEMBURGOx (x ∈ S ↔ x ∈ )). Esta definição de igualdade satisfaz automaticamente os axiomas da igualdade. Neste caso, deve-se substituir o axioma habitual da extensão, que pode ser declarado como Gerenciamento de contas Gerenciamento de contas xGerenciamento de contas Gerenciamento de contas Sim.Não.Gerenciamento de contas Gerenciamento de contas zangão.(zangão.∈ ∈ x⇔ ⇔ zangão.∈ ∈ Sim.)⇒ ⇒ x= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Sim.]{displaystyle forall xforall y[forall z(zin xLeftrightarrow zin y)Rightarrow x=y]}, com uma formulação alternativa Gerenciamento de contas Gerenciamento de contas xGerenciamento de contas Gerenciamento de contas Sim.Não.Gerenciamento de contas Gerenciamento de contas zangão.(zangão.∈ ∈ x⇔ ⇔ zangão.∈ ∈ Sim.)⇒ ⇒ Gerenciamento de contas Gerenciamento de contas zangão.(x∈ ∈ zangão.⇔ ⇔ Sim.∈ ∈ zangão.)]{displaystyle forall xforall y[forall z(zin xLeftrightarrow zin y)Rightarrow forall z(xin zLeftrightarrow yin z)]}, o que diz que se x e Sim. têm os mesmos elementos, então eles também pertencem aos mesmos conjuntos.

Propriedades metalógicas

Uma motivação para o uso da lógica de primeira ordem, em vez da lógica de ordem superior, é que a lógica de primeira ordem tem muitas propriedades metalógicas que as lógicas mais fortes não possuem. Esses resultados dizem respeito a propriedades gerais da própria lógica de primeira ordem, em vez de propriedades de teorias individuais. Eles fornecem ferramentas fundamentais para a construção de modelos de teorias de primeira ordem.

Integridade e indecidibilidade

O teorema da completude de Gödel, provado por Kurt Gödel em 1929, estabelece que existem sistemas dedutivos sólidos, completos e eficazes para lógica de primeira ordem e, portanto, a relação de consequência lógica de primeira ordem é capturada por provabilidade finita. Ingenuamente, a afirmação de que uma fórmula φ implica logicamente uma fórmula ψ depende de todo modelo de φ; esses modelos serão, em geral, de cardinalidade arbitrariamente grande e, portanto, a consequência lógica não pode ser efetivamente verificada verificando todos os modelos. Entretanto, é possível enumerar todas as derivações finitas e buscar uma derivação de ψ a partir de φ. Se ψ for logicamente implícito por φ, tal derivação será eventualmente encontrada. Assim, a consequência lógica de primeira ordem é semidecidível: é possível fazer uma enumeração efetiva de todos os pares de sentenças (φ,ψ) de modo que ψ seja uma consequência lógica de φ.

Ao contrário da lógica proposicional, a lógica de primeira ordem é indecidível (embora semidecidível), desde que a linguagem tenha pelo menos um predicado de aridade pelo menos 2 (além da igualdade). Isso significa que não há procedimento de decisão que determine se fórmulas arbitrárias são logicamente válidas. Este resultado foi estabelecido independentemente por Alonzo Church e Alan Turing em 1936 e 1937, respectivamente, dando uma resposta negativa ao Entscheidungsproblem proposto por David Hilbert e Wilhelm Ackermann em 1928. Suas provas demonstram uma conexão entre a insolubilidade do problema de decisão para first- lógica de ordem e a insolubilidade do problema da parada.

Existem sistemas mais fracos do que a lógica de primeira ordem completa para a qual a relação de consequência lógica é decidível. Isso inclui lógica proposicional e lógica de predicados monádicos, que é a lógica de primeira ordem restrita a símbolos de predicados unários e sem símbolos de função. Outras lógicas sem símbolos de função que são decidíveis são o fragmento protegido da lógica de primeira ordem, bem como a lógica de duas variáveis. A classe Bernays-Schönfinkel de fórmulas de primeira ordem também é decidível. Subconjuntos decidíveis da lógica de primeira ordem também são estudados no âmbito das lógicas descritivas.

Teorema de Löwenheim–Skolem

O teorema de Löwenheim–Skolem mostra que se uma teoria de primeira ordem de cardinalidade λ tem um modelo infinito, então ela tem modelos de toda cardinalidade infinita maior ou igual a λ. Um dos primeiros resultados na teoria do modelo, implica que não é possível caracterizar a enumerabilidade ou a incontabilidade em uma linguagem de primeira ordem com uma assinatura contável. Ou seja, não existe fórmula de primeira ordem φ(x) tal que uma estrutura arbitrária M satisfaça φ se e somente se o domínio do discurso de M for contável (ou, no segundo caso, incontável).

O teorema de Löwenheim–Skolem implica que estruturas infinitas não podem ser categoricamente axiomatizadas na lógica de primeira ordem. Por exemplo, não existe uma teoria de primeira ordem cujo único modelo seja a reta real: qualquer teoria de primeira ordem com modelo infinito também possui um modelo de cardinalidade maior que o contínuo. Como a linha real é infinita, qualquer teoria satisfeita pela linha real também é satisfeita por alguns modelos não padronizados. Quando o teorema de Löwenheim-Skolem é aplicado a teorias de conjuntos de primeira ordem, as consequências não intuitivas são conhecidas como paradoxo de Skolem.

O teorema da compacidade

O teorema da compacidade afirma que um conjunto de sentenças de primeira ordem tem um modelo se e somente se cada subconjunto finito dele tem um modelo. Isso implica que, se uma fórmula é uma consequência lógica de um conjunto infinito de axiomas de primeira ordem, então ela é uma consequência lógica de algum número finito desses axiomas. Este teorema foi provado primeiro por Kurt Gödel como consequência do teorema da completude, mas muitas provas adicionais foram obtidas ao longo do tempo. É uma ferramenta central na teoria de modelos, fornecendo um método fundamental para a construção de modelos.

O teorema da compacidade tem um efeito limitante sobre quais coleções de estruturas de primeira ordem são classes elementares. Por exemplo, o teorema da compacidade implica que qualquer teoria que tenha modelos finitos arbitrariamente grandes tem um modelo infinito. Assim, a classe de todos os grafos finitos não é uma classe elementar (o mesmo vale para muitas outras estruturas algébricas).

Há também limitações mais sutis da lógica de primeira ordem que são implícitas pelo teorema da compactação. Por exemplo, na ciência da computação, muitas situações podem ser modeladas como um gráfico direcionado de estados (nodos) e conexões (bordas direcionadas). Validar tal sistema pode exigir mostrar que nenhum estado "mau" pode ser alcançado a partir de qualquer estado "bom". Assim, procura-se determinar se os bons e maus estados estão em diferentes componentes conectados do gráfico. No entanto, o teorema da compactação pode ser usado para mostrar que os gráficos conectados não são uma classe elementar na lógica da primeira ordem, e não há fórmula φ(x,Sim.) da lógica de primeira ordem, na lógica dos gráficos, que expressa a ideia de que há um caminho de x para Sim.. A conectividade pode ser expressa na lógica de segunda ordem, no entanto, mas não com apenas quantificadores de conjuntos existenciais, como Σ Σ 11Não. Sigma _{1}^{1}} também gosta de compactação.

Teorema de Lindström

Per Lindström mostrou que as propriedades metalógicas discutidas na verdade caracterizam a lógica de primeira ordem no sentido de que nenhuma lógica mais forte também pode ter essas propriedades (Ebbinghaus e Flum 1994, Capítulo XIII). Lindström definiu uma classe de sistemas lógicos abstratos e uma definição rigorosa da força relativa de um membro dessa classe. Ele estabeleceu dois teoremas para sistemas deste tipo:

• Um sistema lógico satisfazendo a definição de Lindström que contém lógica de primeira ordem e satisfaz tanto o teorema de Löwenheim-Skolem quanto o teorema de compactação devem ser equivalentes à lógica de primeira ordem.
• Um sistema lógico satisfazendo a definição de Lindström que tem uma relação de consequência lógica semidecida e satisfaz o teorema de Löwenheim-Skolem deve ser equivalente à lógica de primeira ordem.

Limitações

Embora a lógica de primeira ordem seja suficiente para formalizar grande parte da matemática e seja comumente usada na ciência da computação e em outros campos, ela tem certas limitações. Isso inclui limitações em sua expressividade e limitações dos fragmentos de línguas naturais que ela pode descrever.

Por exemplo, a lógica de primeira ordem é indecidível, o que significa que um algoritmo de decisão som, completo e terminante para a provabilidade é impossível. Isso levou ao estudo de fragmentos decidíveis interessantes, como C₂: Lógica de primeira ordem com duas variáveis e quantificadores de contagem Detalhe Detalhe ≥ ≥ n{displaystyle exists ^{geq n. e Detalhe Detalhe ≤ ≤ n{displaystyle exists ^{leq n..

Expressividade

O teorema de Löwenheim–Skolem mostra que se uma teoria de primeira ordem tem qualquer modelo infinito, então ela tem modelos infinitos de cada cardinalidade. Em particular, nenhuma teoria de primeira ordem com um modelo infinito pode ser categórica. Assim, não há teoria de primeira ordem cujo único modelo tenha como domínio o conjunto dos números naturais, ou cujo único modelo tenha como domínio o conjunto dos números reais. Muitas extensões da lógica de primeira ordem, incluindo lógicas infinitas e lógicas de ordem superior, são mais expressivas no sentido de que permitem axiomatizações categóricas dos números naturais ou números reais. Essa expressividade tem um custo metalógico, no entanto: pelo teorema de Lindström, o teorema da compacidade e o teorema descendente de Löwenheim-Skolem não podem ser válidos em nenhuma lógica mais forte que a de primeira ordem.

Formalizando linguagens naturais

A lógica de primeira ordem é capaz de formalizar muitas construções quantificadoras simples em linguagem natural, como "todas as pessoas que vivem em Perth vivem na Austrália". Assim, a lógica de primeira ordem é usada como base para linguagens de representação do conhecimento, como FO(.).

Ainda assim, existem características complicadas da linguagem natural que não podem ser expressas na lógica de primeira ordem. "Qualquer sistema lógico que seja apropriado como um instrumento para a análise da linguagem natural precisa de uma estrutura muito mais rica do que a lógica de predicados de primeira ordem".

Restrições, extensões e variações

Existem muitas variações da lógica de primeira ordem. Algumas delas não são essenciais no sentido de que apenas mudam a notação sem afetar a semântica. Outros mudam o poder expressivo de forma mais significativa, estendendo a semântica por meio de quantificadores adicionais ou outros novos símbolos lógicos. Por exemplo, lógicas infinitas permitem fórmulas de tamanho infinito, e lógicas modais adicionam símbolos para possibilidade e necessidade.

Idiomas restritos

A lógica de primeira ordem pode ser estudada em linguagens com menos símbolos lógicos do que os descritos acima.

• Porque... Detalhe Detalhe xφ φ (x)(x)} pode ser expresso como ? ? Gerenciamento de contas Gerenciamento de contas x? ? φ φ (x){displaystyle neg forall xneg varphi (x)}e Gerenciamento de contas Gerenciamento de contas xφ φ (x){displaystyle forall xvarphi (x)} pode ser expresso como ? ? Detalhe Detalhe x? ? φ φ (x){displaystyle neg existe xneg varphi (x)}, qualquer um dos dois quantificadores Detalhe Detalhe {displaystyle exists } e Gerenciamento de contas Gerenciamento de contas - Sim. pode ser descartado.
• Desde então φ φ ∨ ∨ ? ? {displaystyle varphi lor psi } pode ser expresso como ? ? (? ? φ φ ∧ ∧ ? ? ? ? ){displaystyle lnot (lnot varphi land lnot psi)} e φ φ ∧ ∧ ? ? {displaystyle varphi land psi } pode ser expresso como ? ? (? ? φ φ ∨ ∨ ? ? ? ? ){displaystyle lnot (lnot varphi lor lnot psi)}Ou ∨ ∨ - Sim. ou ∧ ∧ - Sim. pode ser descartado. Em outras palavras, é suficiente ter ? ? - Sim. e ∨ ∨ - Sim.ou ? ? - Sim. e ∧ ∧ - Sim., como os únicos conjuntivos lógicos.
• Da mesma forma, é suficiente ter apenas ? ? - Sim. e → → Não. como conectivos lógicos, ou ter apenas o traço Sheffer (NAND) ou o operador de seta Peirce (NOR).
• É possível evitar inteiramente símbolos de função e símbolos constantes, reescrevendo-os através de símbolos de predicado de uma maneira apropriada. Por exemplo, em vez de usar um símbolo constante 0{displaystyle ;0} um pode usar um predicado 0(x)(x)} (interpretado como x= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0{displaystyle ;x=0}), e substituir todos os predicados como P(0,Sim.){displaystyle ;P(0,y)} com Gerenciamento de contas Gerenciamento de contas x(0(x)→ → P(x,Sim.)){displaystyle forall x;(0(x)rightarrow P(x,y)}. Uma função como f(x1,x2,...,xn)(x_{1},x_{2},...,x_{n})} será igualmente substituído por um predicado F(x1,x2,...,xn,Sim.){displaystyle F(x_{1},x_{2},...,x_{n},y) ? interpretado como Sim.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =f(x1,x2,...,xn)(x_{1},x_{2},...,x_{n})}. Esta mudança requer adicionar axiomas adicionais à teoria à mão, de modo que as interpretações dos símbolos predicados usados têm a semântica correta.

Restrições como essas são úteis como uma técnica para reduzir o número de regras de inferência ou esquemas de axiomas em sistemas dedutivos, o que leva a provas mais curtas de resultados metalógicos. O custo das restrições é que se torna mais difícil expressar declarações em linguagem natural no sistema formal em questão, porque os conectivos lógicos usados nas declarações em linguagem natural devem ser substituídos por suas definições (mais longas) em termos da coleção restrita de conectivos lógicos. Da mesma forma, as derivações nos sistemas limitados podem ser mais longas do que as derivações nos sistemas que incluem conectivos adicionais. Há, portanto, um compromisso entre a facilidade de trabalhar dentro do sistema formal e a facilidade de provar resultados sobre o sistema formal.

Também é possível restringir as aridades dos símbolos de função e dos símbolos de predicado, em teorias suficientemente expressivas. Pode-se, em princípio, dispensar inteiramente funções de aridade maior que 2 e predicados de aridade maior que 1 em teorias que incluem uma função de emparelhamento. Esta é uma função de aridade 2 que pega pares de elementos do domínio e retorna um par ordenado contendo-os. Também é suficiente ter dois símbolos predicados de aridade 2 que definem funções de projeção de um par ordenado a seus componentes. Em ambos os casos, é necessário que os axiomas naturais para uma função de emparelhamento e suas projeções sejam satisfeitos.

Lógica multiordenada

As interpretações comuns de primeira ordem têm um único domínio de discurso sobre o qual todos os quantificadores variam. A lógica de primeira ordem com várias ordenações permite que as variáveis tenham ordenações diferentes, que possuem domínios diferentes. Isso também é chamado de lógica de primeira ordem digitada e as classificações chamadas de tipos (como no tipo de dados), mas não é o mesmo que teoria de tipo de primeira ordem. A lógica de primeira ordem multiordenada é freqüentemente usada no estudo da aritmética de segunda ordem.

Quando há apenas muitos tipos finitos em uma teoria, a lógica de primeira ordem de muitos tipos pode ser reduzida para a lógica de primeira ordem única. Apresenta-se na teoria uni-sorted um símbolo de predicado unary para cada tipo na teoria de muitos-sorted, e adiciona um axiom dizendo que esses predicados unary particionar o domínio do discurso. Por exemplo, se houver dois tipos, um adiciona símbolos predicados P1(x)(x)} e P2(x)(x)} e o axioma

Gerenciamento de contas Gerenciamento de contas x(P1(x)∨ ∨ P2(x))∧ ∧ ? ? Detalhe Detalhe x(P1(x)∧ ∧ P2(x)){displaystyle forall x(P_{1}(x)lor P_{2}(x))land lnot exists x(P_{1}(x)land P_{2}(x))}.

Então os elementos satisfazendo P1Não. P_{1}} são pensados como elementos do primeiro tipo, e elementos satisfazendo P2{displaystyle P_{2}} como elementos do segundo tipo. Pode-se quantificar sobre cada tipo usando o símbolo de predicado correspondente para limitar o intervalo de quantificação. Por exemplo, para dizer que há um elemento do primeiro tipo satisfazendo fórmula φ(x), um escreve

Detalhe Detalhe x(P1(x)∧ ∧ φ φ (x)){displaystyle existe x(P_{1}(x)land varphi (x))}.

Quantificadores adicionais

Quantificadores adicionais podem ser adicionados à lógica de primeira ordem.

• Às vezes é útil dizer que "P(x) para exatamente um x", que pode ser expresso como ∃!x P(x). Esta notação, chamada quantificação de singularidade, pode ser tomada para abreviar uma fórmula como Detalhex (P(x) Gerenciamento de contasSim. (P(Sim.) → (x = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Sim.).
• Lógica de primeira ordem com quantificadores extras tem novos quantificadores Qx,..., com significados como "há muitos x tal que...". Veja também os quantificadores de ramificação e os quantificadores do plural de George Boolos e outros.
• quantificadores de peso são frequentemente usados no estudo da teoria dos conjuntos ou aritmética.

Lógica infinita

A lógica infinita permite sentenças infinitamente longas. Por exemplo, pode-se permitir uma conjunção ou disjunção de infinitas fórmulas, ou quantificação de infinitas variáveis. Frases infinitamente longas surgem em áreas da matemática, incluindo topologia e teoria de modelos.

A lógica infinita generaliza a lógica de primeira ordem para permitir fórmulas de comprimento infinito. A maneira mais comum pela qual as fórmulas podem se tornar infinitas é por meio de conjunções e disjunções infinitas. No entanto, também é possível admitir assinaturas generalizadas nas quais os símbolos de função e relação podem ter infinitas aridades, ou nas quais os quantificadores podem vincular infinitamente muitas variáveis. Como uma fórmula infinita não pode ser representada por uma string finita, é necessário escolher alguma outra representação de fórmulas; a representação usual neste contexto é uma árvore. Assim, as fórmulas são, essencialmente, identificadas com suas árvores de análise, e não com as strings que estão sendo analisadas.

As lógicas infinitárias mais comumente estudadas são denotadas como L_αβ, onde α e β são números cardinais ou o símbolo ∞. Nesta notação, a lógica de primeira ordem comum é L_ωω. Na lógica L_∞ω, conjunções ou disjunções arbitrárias são permitidas na construção de fórmulas, e há um fornecimento ilimitado de variáveis. De forma mais geral, a lógica que permite conjunções ou disjunções com menos de κ constituintes é conhecida como L_κω. Por exemplo, L_ω1ω permite conjunções e disjunções contáveis.

O conjunto de variáveis livres em uma fórmula de L_κω pode ter qualquer cardinalidade estritamente menor que κ, mas apenas um número finito delas pode estar no escopo de qualquer quantificador quando uma fórmula aparece como uma subfórmula de outra. Em outras lógicas infinitárias, uma subfórmula pode estar no escopo de infinitos quantificadores. Por exemplo, em L_κ∞, um único quantificador universal ou existencial pode ligar arbitrariamente muitas variáveis simultaneamente. Da mesma forma, a lógica L_κλ permite a quantificação simultânea sobre menos de λ variáveis, bem como conjunções e disjunções de tamanho menor que κ.

Lógicas não clássicas e modais

• Lógica intuicionista de primeira ordem usa cálculo proposicional intuicionista em vez de clássico; por exemplo, ¬φ não precisa ser equivalente a φ.
• Primeira ordem lógica modal permite descrever outros mundos possíveis, bem como este mundo contingentemente verdadeiro que habitamos. Em algumas versões, o conjunto de mundos possíveis varia dependendo de qual possível mundo habita. Lógica Modal tem extra operadores modais com significados que podem ser caracterizados informalmente como, por exemplo, "é necessário que φ" (verdade em todos os mundos possíveis) e "é possível que φ" (verdade em algum mundo possível). Com a lógica padrão de primeira ordem temos um único domínio e cada predicado é atribuído uma extensão. Com a lógica modal de primeira ordem temos uma função de domínio que atribui a cada mundo possível seu próprio domínio, de modo que cada predicado recebe uma extensão apenas relativa a esses mundos possíveis. Isso nos permite modelar casos em que, por exemplo, Alex é um filósofo, mas pode ter sido um matemático, e pode não ter existido. No primeiro mundo possível P(um) é verdade, no segundo P(um) é falso, e no terceiro mundo possível não há um no domínio.
• Lógicas fuzzy de primeira ordem são extensões de primeira ordem de lógicas fuzzy proposicionais em vez de cálculo proposicional clássico.

Lógica de ponto fixo

A lógica de ponto fixo estende a lógica de primeira ordem adicionando o fechamento sob os pontos fixos mínimos de operadores positivos.

Lógica de ordem superior

A característica da lógica de primeira ordem é que os indivíduos podem ser quantificados, mas não os predicados. Por isso

Detalhe Detalhe um(Phil.(um)){displaystyle existe a({text{Phil}}(a)}

é uma fórmula legal de primeira ordem, mas

Detalhe Detalhe Phil.(Phil.(um)){displaystyle existe {text{Phil}}({text{Phil}}(a)})

não é, na maioria das formalizações da lógica de primeira ordem. A lógica de segunda ordem estende a lógica de primeira ordem adicionando o último tipo de quantificação. Outras lógicas de ordem superior permitem a quantificação de tipos ainda mais elevados do que a lógica de segunda ordem permite. Esses tipos superiores incluem relações entre relações, funções de relações para relações entre relações e outros objetos de tipo superior. Assim, o "primeiro" na lógica de primeira ordem descreve o tipo de objetos que podem ser quantificados.

Ao contrário da lógica de primeira ordem, para a qual apenas uma semântica é estudada, existem várias semânticas possíveis para a lógica de segunda ordem. A semântica mais comumente empregada para lógica de segunda ordem e de ordem superior é conhecida como semântica completa. A combinação de quantificadores adicionais e a semântica completa para esses quantificadores torna a lógica de ordem superior mais forte do que a lógica de primeira ordem. Em particular, a relação de consequência lógica (semântica) para a lógica de segunda ordem e de ordem superior não é semidecidível; não existe um sistema de dedução eficaz para a lógica de segunda ordem que seja sólido e completo sob a semântica completa.

A lógica de segunda ordem com semântica completa é mais expressiva do que a lógica de primeira ordem. Por exemplo, é possível criar sistemas de axiomas em lógica de segunda ordem que caracterizem exclusivamente os números naturais e a reta real. O custo dessa expressividade é que as lógicas de segunda ordem e de ordem superior têm menos propriedades metalógicas atraentes do que a lógica de primeira ordem. Por exemplo, o teorema de Löwenheim-Skolem e o teorema de compacidade da lógica de primeira ordem tornam-se falsos quando generalizados para lógicas de ordem superior com semântica completa.

Prova automatizada de teoremas e métodos formais

A prova automatizada de teoremas refere-se ao desenvolvimento de programas de computador que pesquisam e encontram derivações (provas formais) de teoremas matemáticos. Encontrar derivações é uma tarefa difícil porque o espaço de busca pode ser muito grande; uma busca exaustiva de todas as derivações possíveis é teoricamente possível, mas computacionalmente inviável para muitos sistemas de interesse em matemática. Assim, funções heurísticas complicadas são desenvolvidas para tentar encontrar uma derivação em menos tempo do que uma busca cega.

A área relacionada de verificação automatizada de provas usa programas de computador para verificar se as provas criadas por humanos estão corretas. Ao contrário dos complicados provadores de teoremas automatizados, os sistemas de verificação podem ser pequenos o suficiente para que sua correção possa ser verificada manualmente e por meio de verificação automatizada de software. Essa validação do verificador de prova é necessária para dar confiança de que qualquer derivação rotulada como "correta" realmente está correto.

Alguns verificadores de prova, como o Metamath, insistem em ter uma derivação completa como entrada. Outros, como Mizar e Isabelle, pegam um esboço de prova bem formatado (que ainda pode ser muito longo e detalhado) e preenchem as peças que faltam fazendo buscas de prova simples ou aplicando procedimentos de decisão conhecidos: a derivação resultante é então verificada por um núcleo pequeno "kernel". Muitos desses sistemas destinam-se principalmente ao uso interativo por matemáticos humanos: são conhecidos como assistentes de prova. Eles também podem usar lógicas formais que são mais fortes do que a lógica de primeira ordem, como a teoria dos tipos. Como uma derivação completa de qualquer resultado não trivial em um sistema dedutivo de primeira ordem será extremamente longa para um ser humano escrever, os resultados geralmente são formalizados como uma série de lemas, para os quais as derivações podem ser construídas separadamente.

Os provadores de teoremas automatizados também são usados para implementar a verificação formal na ciência da computação. Nesse cenário, os provadores de teoremas são usados para verificar a exatidão de programas e de hardware, como processadores, em relação a uma especificação formal. Como essa análise é demorada e, portanto, cara, geralmente é reservada para projetos nos quais um mau funcionamento teria graves consequências humanas ou financeiras.

Para o problema de verificação de modelo, algoritmos eficientes são conhecidos para decidir se uma estrutura finita de entrada satisfaz uma fórmula de primeira ordem, além dos limites de complexidade computacional: consulte Verificação de modelo § Lógica de primeira ordem.