Anteriormente vimos sobre uma lógica bem simples, o Cálculo Proposicional (CP), que é capaz encapsular deduções e inferências acerca de fórmulas ou proposições que podem ser verdadeiras ou falsas. Entretanto, o CP não é capaz de tratar de fórmulas que dizem a respeito de elementos de conjuntos, ou seja, não há quantificação – algo particularmente problemático em relação a conjuntos infinitos, como os números naturais, e modelagem do mundo real em geral. Eis então a necessidade da Lógica de Primeira Ordem (LPO). A LPO é dividida essencialmente em sintaxe e semântica, como o CP, e iremos delinear sua sintaxe básica e semântica neste post.
A sintaxe da LPO é composta pelo sistema formal de forma semelhante ao CP.
é uma tripla chamada de vocabulário da LPO e contém todos os símbolos “não-lógicos” da LPO. Os símbolos que compõem
são:
- Variáveis ou Constantes (
): Símbolos que representam intuitivamente elementos de um conjunto qualquer. Por exemplo,
, etc. As variáveis podem ser livres ou ligadas, conforme veremos adiante, e são capazes de representar um único elemento e não coleções de elementos.
- Funções (
): Correspondem a transformações de variáveis ou constantes e são usualmente representadas pelos símbolos
. Podemos usar um sobre-escrito para indicar a aridade das funções e podemos representá-las utilizando parênteses. Por exemplo, uma função de aridade
pode ser escrita como
e
em que todo
é uma variável.
- Predicados ou Relações (
): São representados por letras maiúsculas, usualmente
e, como funções, podem usar um sobrescrito para indicar a aridade – se
é um predicado n-ário, podemos escrever
para especificá-lo. Podemos escrever predicados usando notação de prefixo, como funções, ou caso estejamos tratando de um predicado binário, em notação de infixo. Seja
um predicado binário: podemos escrever
ou
. Formalizaremos posteriormente o conceito de relação.
Note que existem infinitas variáveis, constantes, funções e predicados, logo também existem infinitos vocabulários para a LPO.
contém os símbolos “lógicos” da LPO:
. Observe que a LPO contém todos os conectivos lógicos do CP – de fato, o CP é um “subconjunto” da LPO e alguns autores (e.g. Peter B. Andrews no livro An Introduction to Mathematical Logic and Type Theory) utilizam o termo “Lógica de Grau Zero” como sinônimo do CP. Os símbolos
e
correspondem, respectivamente, aos quantificadores existencial e universal. Vamos considerar alguns exemplos. A frase “todos os mamíferos se alimentam de leite” pode ser escrita na LPO como
(podemos ler “para todo
,
), em que
é um elemento do conjunto de todos os mamíferos e
significa “se alimenta de leite”. Já a frase “existe algum mamífero que bota ovos” pode ser escrita na LPO como
em que
novamente é um elemento do conjunto de todos os mamíferos e
significa “bota ovos”. No entanto, não devemos atrelar significado aos símbolos que estamos usando no momento, pois estamos tratando simplesmente da sintaxe da LPO. Devemos considerar que
e
são apenas predicados unários e
é uma variável (na verdade, uma meta-variável!). O símbolo
corresponde à igualdade conforme estamos acostumados. Algumas descrições da LPO não incluem o símbolo
como um símbolo lógico mas delegam a sua definição à semântica.
O conjunto é chamado de alfabeto ou linguagem da LPO. Agora podemos definir algumas construções básicas da LPO, como termo, fórmula atômica e fórmula.
Um termo de um alfabeto da LPO é definido como:
- Um elemento
ou
em que
é uma função
-ária e
são variáveis ou constantes.
Através de termos, podemos definir fórmulas atômicas:
, em que
e
são termos de
ou
, em que
é um predicado n-ário e
são termos de
.
Fórmulas são construídas da seguinte maneira:
- Toda fórmula atômica é fórmula;
- Se
é fórmula,
é fórmula;
- Se
e
são fórmulas, então
é fórmula;
- Se
é fórmula e
é variável, então
é fórmula.
Os símbolos ,
,
são definidos conforme vimos aqui e
é definido como
. Também poderíamos ter feito o contrário e definir
como
. A nova ordem de precedência dos símbolos lógicos é a seguinte:
Variáveis podem ser livres ou ligadas em fórmulas da LPO. Variáveis livres não estão quantificadas, ou seja, aparecem independentemente de quantificadores em fórmulas lógicas, enquanto variáveis ligadas estão. Considere a fórmula de um vocabulário
– a meta-variável
está quantificada, logo é ligada, enquanto
é livre por não estar quantificada. No entanto, se alterarmos a fórmula para
, ambas meta-variáveis
e
estão ligadas. Escrevemos
para dizer que
é uma fórmula com as variáveis
– se essas variáveis forem todas ligadas, dizemos que
é uma sentença.
Agora já temos conhecimento suficiente acerca da sintaxe da LPO para discutir sobre sua semântica. O valor-verdade das fórmulas da LPO depende do conjunto em que essas fórmulas estão inseridas e da interpretação dos símbolos do vocabulário das fórmulas – ambos itens são o que formam a estrutura do vocabulário. Formalmente, dizemos que uma estrutura de um vocabulário
é composta de um conjunto
(chamado de universo da estrutura) de forma que:
- Cada variável e constante
é atribuida a um elemento em
;
- Cada função
-ária é atribuida a uma função
;
- Cada predicado
-ário é atribuido a uma relação
.
A estrutura também pode ser chamada de
-estrutura e, usualmente, quando fornecemos uma estrutura, a linguagem também é definida “automaticamente”. Vamos retomar nosso exemplo anterior para ver como frases da linguagem natural podem ser mapeadas na LPO de modos diferentes se considerarmos estruturas diferentes.
Consideremos a frase “todo mamífero bebe leite”. Vamos utilizar a estrutura em que o conjunto
corresponde ao conjunto de todos os animais, o predicado unário
significa “é mamífero” e o predicado
significa “bebe leite”. A frase corresponderia à fórmula
. Note que essa fórmula difere daquela que construímos anteriormente, porque alteramos o universo da estrutura. Quando fornecemos a estrutura a um vocabulário, podemos verificar o valor-verdade das fórmulas correspondentes ao vocabulário.
Para formalizar a noção de verdade dentro da LPO, utilizamos o Esquema T – um esquema indutivo que implementa a teoria semântica de verdade de Alfred Tarski. Informalmente, aceitamos que uma fórmula é verdadeira se a sua interpretação no “mundo real” é verdadeira – no caso, o “mundo real” corresponde à estrutura vigente.
Primeiramente temos que definir o que significa atribuir termos a elementos de um vocabulário a uma estrutura
: considere um termo
em
, dizemos que o valor atribuído
de
em
é:
, em que
é uma meta-variável
denota o universo da estrutura
, se
é
;
, se
foi associado à constante
;
se
é
, em que cada
é o valor resultante de uma atribuição a cada termo.
Dizemos que uma fórmula é verdadeira em uma estrutura
se:
é da forma
e
, ou seja, a interpretação dos termos
e
é igual na estrutura
;
é da forma
em que
é um predicado
-ário, se a
-tupla é subconjunto de
– ou seja,
é atribuído a uma relação em
;
é da forma
se
é falsa em
;
é da forma
se ambas fórmulas
e
são verdadeiras em
;
é da forma
e existe um “subconjunto” de
chamado de
de forma que
é verdadeira em
, em que
é um elemento de
.
Por fim, se uma fórmula é verdadeira em
, dizemos que
modela
e podemos escrever
para denotar esse fato. De modo similar, se
é um conjunto de fórmulas da LPO verdadeiras em uma estrutura
, escrevemos
. Se uma fórmula
é verdadeira em todas estruturas, ou seja, qualquer estrutura é modelo para ela, dizemos que
é uma tautologia e escrevemos
.
Vamos ver alguns exemplos de estruturas comuns para vocabulários da LPO.
- Grafos:
Um grafo é um par ordenado
em que
é o conjunto de seus vértices e
é o conjunto de suas arestas. Podemos interpretar o grafo
como a estrutura
, ou seja, o universo é composto pelo vértices de
e
é uma relação binária interpretada como a existência de aresta – dizemos que
se há uma aresta entre os vértices
e
de G, ou seja,
. Em geral, dizemos que um grafo
modela uma fórmula
(dentro da estrutura em que estamos considerando) se a fórmula “corresponde” ao
.
- Bancos de dados relacional:
Podemos interpretar uma tabela com
colunas como a estrutura
, em que o conjunto universo
é compostos pelos atributos de cada linha das
colunas de
e a relação
-ária
é interpretada como as linhas da tabela
.
Num entendi nada, moço
LikeLike