A lógica de primeira ordem (LPO), conhecida também como cálculo de predicados de primeira ordem (CPPO), é um sistema lógico que estende a lógica proposicional (lógica sentencial) e que é estendida pela lógica de segunda ordem.
As sentenças atômicas da lógica de primeira ordem têm o formato P (t1,…, tn) (um predicado com um ou mais "argumentos") ao invés de serem símbolos sentenciais sem estruturas.
O ingrediente novo da lógica de primeira ordem não encontrado na lógica proposicional é a quantificação: dada uma sentença φ qualquer, as novas construções e -- leia "para todo x, φ" e "para algum x, φ", respectivamente—são introduzidas. significa que φ é verdadeiro para todo valor de x e significa que há pelo menos um x tal que φ é verdadeiro. Os valores das variáveis são tirados de um universo de discurso pré-determinado. Um refinamento da lógica de primeira ordem permite variáveis de diferentes tipos, para tratar de diferentes classes de objetos.
A lógica de primeira ordem tem poder expressivo suficiente para formalizar praticamente toda a matemática. Uma teoria de primeira ordem consiste em um conjunto de axiomas (geralmente finito ou recursivamente enumerável) e de sentenças dedutíveis a partir deles. A teoria dos conjuntos de Zermelo-Fraenkel é um exemplo de uma teoria de primeira ordem, e aceita-se geralmente que toda a matemática clássica possa ser formalizada nela. Há outras teorias que são normalmente formalizadas na lógica de primeira ordem de maneira independente(embora elas admitam a implementação na teoria dos conjuntos) tais como a aritmética de Peano.
Definindo a lógica de primeira ordem Um cálculo de predicados consiste em:
regras de formação (definições recursivas para dar origem a fórmulas bem-formadas ou FBFs).
regras de transformação (regras de inferência para derivar teoremas). axiomas.
Os axiomas considerados aqui são os axiomas lógicos que fazem parte do cálculo de predicados. Além disso, os axiomas não-lógicos são adicionados em teorias de primeira ordem específicas: estes não são considerados como verdades da lógica, mas como verdades da teoria particular sob consideração.
Quando o conjunto dos axiomas é infinito, requer-se que haja um algoritmo que possa decidir para uma fórmula bem-formada dada, se ela é um axioma ou não. Deve também haver um algoritmo que possa decidir se uma aplicação dada de uma regra de inferência está correta ou não.
É importante notar que o cálculo de predicados pode ser formalizado de muitas maneiras equivalentes; não há nada canônico sobre os axiomas e as regras de inferência propostos aqui, mas toda a formalização dará origem aos mesmos teoremas da lógica (e deduzirá os mesmos teoremas a partir de um conjunto qualquer de axiomas não-lógicos).
Alfabeto O alfabeto de primeira ordem, , tem a seguinte constituição:
, onde
é um conjunto enumerável de variáveis; é um conjunto de símbolos chamados de constantes; é um conjunto de símbolos ditos sinais funcionais; é um conjunto de símbolos ditos sinais relacionais ou predicativos; é o conjunto de símbolos ditos sinais lógicos; é o conjunto de símbolos de pontuação. As constantes, sinais funcionais e sinais predicativos constituem a coleção de sinais ditos símbolos não lógicos.
Há diversas variações menores listadas abaixo:
O conjunto de símbolos primitivos (operadores e quantificadores) varia frequentemente. Alguns símbolos primitivos podem ser omitidos, substituindo-os com abreviaturas adequadas; por exemplo (P ↔ Q) é uma abreviatura para (P → Q) ∧ (Q → P). No sentido contrário, é possível incluir outros operadores como símbolos primitivos, como as constantes de verdade ⊤ para "verdadeiro" e o ⊥ para "falso" (estes são operadores do aridade 0). O número mínimo dos símbolos primitivos necessários é um, mas se nós nos restringirmos aos operadores listados acima, seria necessário três; por exemplo, o ¬, o ∧, e o ∀ bastariam. Alguns livros mais antigos usam a notação φ ⊃ ψ para φ → ψ, ~φ para ¬φ, φ & ψ para φ ∧ ψ, e uma variedade de notações para os quantificadores; por exemplo, ∀xφ pode ser escrito como (x)φ. A igualdade é às vezes considerada como parte da lógica de primeira ordem; Neste caso, o símbolo da igualdade será incluído no alfabeto, e comportar-se-á sintaticamente como um predicado binário. Assim a LPO será chamada de lógica de primeira ordem com igualdade. As constantes são na verdade funções de aridade 0, assim seria possível e conveniente omitir constantes e usar as funções que tenham qualquer aridade. Mas é comum usar o termo "função" somente para funções de aridade 1. Na definição acima, as relações devem ter pelo menos aridade 1. É possível permitir relações de aridade 0; estas seriam consideradas variáveis proposicionais. Há muitas convenções diferentes sobre onde pôr parênteses; por exemplo, se pode escrever ∀x ou (∀x). Às vezes se usa dois pontos ou ponto final ao invés dos parênteses para criar fórmulas não ambíguas. Uma convenção interessante, mas incomum, é a "notação polonesa", onde se omite todos os parênteses, e escreve-se o ∧, ∨, e assim por diante na frente de seus argumentos. A notação polonesa é compacta e elegante, mas rara e de leitura complexa. Uma observação técnica é que se houver um símbolo de função de aridade 2 que representa um par ordenado (ou símbolos de predicados de aridade 2 que representam as relações de projeção de um par ordenado) então se pode dispensar inteiramente as funções ou predicados de aridade > 2. Naturalmente o par ou as projeções necessitam satisfazer aos axiomas naturais.
Os conjuntos das constantes, das funções, e das relações compõem a assinatura e são geralmente considerados para dar forma a uma linguagem, enquanto as variáveis, os operadores lógicos, e os quantificadores são geralmente considerados para pertencer à lógica. Uma estrutura dá o significado semântico de cada símbolo da assinatura. Por exemplo, a linguagem da teoria dos grupos consiste de uma constante (elemento da identidade), de uma função de aridade 1 (inverso), de uma função de aridade 2 (produto), e de uma relação de aridade 2 (igualdade), que seria omitida pelos autores que incluem a igualdade na lógica subjacente.
Regras de formação As regras de formação definem os termos, fórmulas, e as variáveis livres como segue. O conjunto dos termos é definido recursivamente pelas seguintes regras:
Qualquer constante é um termo (sem variáveis livres). Qualquer variável é um termo (cuja única variável livre é ela mesma). Toda expressão f (t1,…, tn) de n ≥ 1 argumentos (onde cada argumento ti é um termo e f é um símbolo de função de aridade n) é um termo. Suas variáveis livres são as variáveis livres de cada um dos termos ti. Cláusula de fechamento: Nada mais é um termo.
O conjunto das fórmulas bem-formadas (chamadas geralmente FBFs ou apenas fórmulas) é definido recursivamente pelas seguintes regras: Predicados simples e complexos: se P for uma relação de aridade n ≥ 1 e os ai são os termos então P (a1,…,an) é bem formada. Suas variáveis livres são as variáveis livres de quaisquer termos ai. Se a igualdade for considerada parte da lógica, então (a1 = a2) é bem formada. Tais fórmulas são ditas atômicas. Cláusula indutiva I: Se φ for uma FBF, então ¬φ é uma FBF. Suas variáveis livres são as variáveis livres de φ. Cláusula indutiva II: Se φ e ψ são FBFs, então (ψ ∧ φ), (ψφ), (ψ → φ), (ψ ↔ φ) são FBFs. Suas variáveis livres são as variáveis livres de φ e de ψ. Cláusula indutiva III: Se φ for uma FBF e x for um variável, então ∀xφ e ∃xφ são FBFs, cujas variáveis livres são as variáveis livres de φ com exceção de x. Ocorrências de x são ditas ligadas ou mudas (por oposição a livre) em ∀xφ e ∃xφ. Cláusula de fechamento: Nada mais é uma FBF.
Na prática, se P for uma relação de aridade 2, nós escrevemos frequentemente "a P b" em vez de "P a b"; por exemplo, nós escrevemos 1 < 2 em vez de < (1 2). Similarmente se f for uma função de aridade 2, nós escrevemos às vezes "a f b" em vez de "f (a b)"; por exemplo, nós escrevemos 1 + 2 em vez de + (1 2). É também comum omitir alguns parênteses se isto não conduzir à ambigüidade. Às vezes é útil dizer que "P (x) vale para exatamente um x", o que costuma ser denotado por ∃!xP(x). Isto também pode ser expresso por ∃x (P (x) ∀y (P (y) → (x = y))).
Exemplos: A linguagem dos grupos abelianos ordenados tem uma constante 0, uma função unária −, uma função binária +, e uma relação binária ≤. Assim: 0, x, y são termos atômicos + (x, y), + (x, + (y, − (z))) são termos, escritos geralmente como x + y, x + (y + (−z)) = (+ (x, y), 0), ≤ (+ (x, + (y, − (z))), + (x, y)) são fórmulas atômicas, escritas geralmente como x + y = 0, x + y - z ≤ x + y, (∀x ∃y ≤ (+ (x, y), z)) ∧ (∃x = (+ (x, y), 0)) é uma fórmula, escrita geralmente como (∀x ∃y (x + y ≤ z)) ∧ (∃x (x + y = 0)).
Substituição Se t é um termo e φ(x) é uma fórmula que contém possivelmente x como uma variável livre, então φ(t) se definido como o resultado da substituição de todas as instâncias livres de x por t, desde que nenhuma variável livre de t se torne ligada neste processo. Se alguma variável livre de t se tornar ligada, então para substituir t por x é primeiramente necessário mudar os nomes das variáveis ligadas de φ para algo diferente das variáveis livres de t. Para ver porque esta condição é necessária, considere a fórmula φ(x) dada por ∀y y≤x ("x é máximal"). Se t for um termo sem y como variável livre, então φ(t) diz apenas que t é maximal. Entretanto se t é y, a fórmula φ(y) é ∀y y≤y que não diz que y é máximal.O problema de que a variável livre y de t (=y) se transformou em ligada quando nós substituímos y por x em φ(x). Assim, para construir φ(y) nós devemos primeiramente mudar a variável ligada y de φ para qualquer outra coisa, por exemplo a variável z, de modo que o φ(y) seja então ∀z z≤ y. Esquecer desta condição é uma causa notória de erros.
Igualdade Há diversas convenções diferentes para se usar a igualdade (ou a identidade) na lógica de primeira ordem. Esta seção resume as principais. Todas as convenções resultam mais ou menos no mesmo com mais ou menos a mesma quantidade de trabalho, e diferem principalmente na terminologia. A convenção mais comum para a igualdade é incluir o símbolo da igualdade como um símbolo lógico primitivo, e adicionar os axiomas da igualdade aos axiomas da lógica de primeira ordem. Os axiomas de igualdade são
x = x x = y → (…,x,…) = (…,y,…) para qualquer função x = y → ((…,x,…) → (…,y,…)) para qualquer relação (incluindo a própria igualdade)
A próxima convenção mais comum é incluir o símbolo da igualdade como uma das relações de uma teoria, e adicionar os axiomas da igualdade aos axiomas da teoria. Na prática isto é quase idêntico à da convenção precedente, exceto no exemplo incomum de teorias com nenhuma noção de igualdade. Os axiomas são os mesmos, e a única diferença é se eles serão chamados de axiomas lógicos ou de axiomas de teoria. Nas teorias sem funções e com um número finito de relações, é possível definir a igualdade em termos de relações, definindo os dois termos s e t como iguais se qualquer relação continuar inalterada ao se substituir s por t em qualquer argumento. Por exemplo, em teoria dos conjuntos com uma relação ∈, nós definiríamos s = t como uma abreviatura para ∀x (s ∈ x ↔ t ∈ x) ∧ ∀x (x ∈ s ↔ x ∈ t). Esta definição de igualdade satisfaz automaticamente os axiomas da igualdade. Em algumas teorias é possível dar definições de igualdade ad hoc. Por exemplo, em uma teoria de ordens parciais com uma relação ≤ nós poderíamos definir s = t como uma abreviatura para s ≤ t ∧ t ≤ s.
Regras de inferência A regra de inferência modus ponens é a única necessária para a lógica proposicional de acordo com a formalização proposta aqui. Ela diz que se φ e φ → ψ são ambos demonstrados, então pode-se deduzir ψ. A regra de inferência chamada Generalização Universal é característica da lógica de primeira ordem: se , então