Sobre Lógica de Primeira Ordem (pt. 1)

~ Gabriel Rodrigues Rocha

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 \mathscr{L} = (\mathscr{V}, \Omega, \mathscr{Z}, \mathscr{I}) de forma semelhante ao CP. \mathscr{V} = (\Sigma, \Delta, \Psi) é  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 \mathscr{V} são:

  • Variáveis ou Constantes (\Sigma): Símbolos que representam intuitivamente elementos de um conjunto qualquer. Por exemplo, a, b, x, y, x_1, x_2, y_3, 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 (\Delta): Correspondem a transformações de variáveis ou constantes e são usualmente representadas pelos símbolos f, g, h. 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 n pode ser escrita como f^n e f(x_1, x_2, \ldots, x_n) em que todo x_i, i \in \mathbb{N} é uma variável.
  • Predicados ou Relações (\Psi): São representados por letras maiúsculas, usualmente R, P, Q e, como funções, podem usar um sobrescrito para indicar a aridade – se R é um predicado n-ário, podemos escrever R^n 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 P^2 um predicado binário: podemos escrever P(x,y) ou x P y. 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.

\Omega contém os símbolos “lógicos” da LPO: \{ \neg, \land, \lor, \longrightarrow, \longleftrightarrow, \exists, \forall, (, ), =, ','\}. 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 \exists e \forall 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 \forall x L(x) (podemos ler “para todo x, L(x)), em que x é um elemento do conjunto de todos os mamíferos e  L(x) significa “se alimenta de leite”. Já a frase “existe algum mamífero que bota ovos” pode ser escrita na LPO como \exists x O(x) em que x novamente é um elemento do conjunto de todos os mamíferos e O(x) 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 L e O são apenas predicados unários e x é 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 \mathscr{A} = \Sigma \cup \Delta \cup \Psi \cup \Omega é 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 \mathscr{A} da LPO é definido como:

  • Um elemento c \in \Sigma ou
  • f(x_1, \ldots, x_n) em que f \in \Delta é uma função n-ária e x_i \in \Sigma, i \in \mathbb{N} são variáveis ou constantes.

Através de termos, podemos definir fórmulas atômicas:

  • t_1 = t_2, em que t_1 e t_2 são termos de \mathscr{A} ou
  • R(t_1, \ldots, t_n), em que R \in \Psi é um predicado n-ário e t_1, \ldots, t_n são termos de \mathscr{A}.

Fórmulas são construídas da seguinte maneira:

  1. Toda fórmula atômica é fórmula;
  2. Se \phi é fórmula, \neg \phi é fórmula;
  3. Se \phi e \psi são fórmulas, então \phi \land \psi é fórmula;
  4. Se \phi é fórmula e x é variável, então \exists x \phi é fórmula.

Os símbolos \lor, \longrightarrow, \longleftrightarrow são definidos conforme vimos aqui e \forall x \phi é definido como \neg \exists x \neg \phi. Também poderíamos ter feito o contrário e definir \exists x \phi como \neg \forall \neg \phi. A nova ordem de precedência dos símbolos lógicos é a seguinte:

\neg > \land > \lor > \exists \ge \forall > \longrightarrow > \longleftrightarrow

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 \forall x P(x, y) de um vocabulário \mathscr{V} = (\{x,y\}, \emptyset, \{P^2\}) – a meta-variável x está quantificada, logo é ligada, enquanto y é livre por não estar quantificada. No entanto, se alterarmos a fórmula para \forall x \exists y P(x,y), ambas meta-variáveis x e y estão ligadas. Escrevemos \phi(x_1, \ldots, x_n) para dizer que \phi é uma fórmula com as variáveis x_i, i \in \mathbb{N} – se essas variáveis forem todas ligadas, dizemos que \phi é 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 M de um vocabulário \mathscr{V} = (\Sigma, \Delta, \Psi) é composta de um conjunto U (chamado de universo da estrutura) de forma que:

  • Cada variável e constante x \in \Sigma é atribuida a um elemento em U;
  • Cada função f^n \in \Delta n-ária é atribuida a uma função f' : U^n \rightarrow U;
  • Cada predicado P^n \in \Psi n-ário é atribuido a uma relação R \subseteq U^n.

A estrutura M também pode ser chamada de \mathscr{V}-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 M_1 = \langle A | M^1, L^1 \rangle em que o conjunto A corresponde ao conjunto de todos os animais, o predicado unário M^1 significa “é mamífero” e o predicado L^1 significa “bebe leite”. A frase corresponderia à fórmula \forall x (M(x) \longrightarrow L(x)). 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 \mathscr{V} a uma estrutura M: considere um termo t em \mathscr{V}, dizemos que o valor atribuído t_m de t em M é:

  • a \in U_m, em que a é uma meta-variável U_m denota o universo da estrutura M, se t é a;
  • c \in U_m, se t foi associado à constante c;
  • f_m({t_1}_m, \ldots, {t_n}_m) se t é f(t_1, \ldots, t_n), em que cada {t_i}_m, i \in \mathbb{N} é o valor resultante de uma atribuição a cada termo.

Dizemos que uma fórmula \phi é verdadeira em uma estrutura M se:

  • \phi é da forma t_1 = t_2 e {t_m}_1 = {t_m}_2, ou seja, a interpretação dos termos t_1 e t_2 é igual na estrutura M;
  • \phi é da forma P(t_1, \ldots, t_2) em que P é um predicado n-ário, se a n-tupla é subconjunto de {U_m} ^ n – ou seja, P é atribuído a uma relação em M;
  • \phi é da forma \neg \psi se \psi é falsa em M;
  • \phi é da forma {\psi}_1 \land {\psi}_2 se ambas fórmulas {\psi}_1 e {\psi}_2 são verdadeiras em M;
  • \phi é da forma \exists x \psi(x) e existe um “subconjunto” de M chamado de M_c de forma que \psi(c) é verdadeira em M_c, em que c é um elemento de M_c.

Por fim, se uma fórmula \phi é verdadeira em M, dizemos que M modela \phi e podemos escrever M \models \phi para denotar esse fato. De modo similar, se \Gamma é um conjunto de fórmulas da LPO verdadeiras em uma estrutura M_{\Gamma}, escrevemos M_{\Gamma} \models \Gamma. Se uma fórmula \phi é verdadeira em todas estruturas, ou seja, qualquer estrutura é modelo para ela, dizemos que \phi é uma tautologia e escrevemos \models \phi.

Vamos ver alguns exemplos de estruturas comuns para vocabulários da LPO.

  • Grafos:

Um grafo G é um par ordenado (V, E) em que V = \{v_1, v_2, v_3, \ldots\} é o conjunto de seus vértices e E = \{(v_i, v_j), \ldots\} é o conjunto de suas arestas. Podemos interpretar o grafo G como a estrutura \langle V|R^2 \rangle, ou seja, o universo é composto pelo vértices deG e R é uma relação binária interpretada como a existência de aresta – dizemos que G \models R(a,b) se há uma aresta entre os vértices a e b de G, ou seja, (a,b) \in E. Em geral, dizemos que um grafo G modela uma fórmula \Phi (dentro da estrutura em que estamos considerando) se a fórmula “corresponde” ao G.

  •  Bancos de dados relacional:

Podemos interpretar uma tabela T com n colunas como a estrutura \langle A|R^n \rangle, em que o conjunto universo A é compostos pelos atributos de cada linha das n colunas de T e a relação n-ária R é interpretada como as linhas da tabela T.

One thought on “Sobre Lógica de Primeira Ordem (pt. 1)”

Leave a comment