Linguagens de Primeira Ordem - Resumo


Procure o professor ou a monitoria se tiver dúvidas.


Uma linguagem de primeira ordem, que denotaremos por L, encerra as seguintes categorias de símbolos:

1. Símbolos lógicos: (a) conectivos lógicos; (b) símbolos auxiliares (parênteses e vírgula); (c) variáveis individuais: x, y, z, w (eventualmente com sub-índices quando necessário); (d) quantificadores: " (para todo, qualquer que seja) e $ (existe); (e) o símbolo de igualdade.
2. Símbolos não lógicos: (a) constantes individuais (uma coleção eventualmente vazia); (b) símbolos para predicados (cada um de uma certa aridade); (c) símbolos funcionais (uma coleção eventualmente vazia, mas, havendo tais símbolos, cada um de uma certa aridade).

Nos exemplos a seguir, indicaremos unicamente os símbolos não lógicos.

Exemplo 1. LAR (linguagem da Aritmética Elementar, ou Aritmética de Primeira Ordem).
(a) constantes individuais: uma só, 0.
(b) símbolos para predicados: um só símbolo binário, <.
(c) dois símbolos funcionais binários, + e · e um símbolo funcional unário, S.

Exemplo 2. LZF (linguagem para a teoria de conjuntos Zermelo-Fraenkel)
Não há constantes individuais e nem símbolos funcionais, mas um só símbolo para predicado binário,
Î.

Exemplo 3. LG (linguagem para a teoria de grupos)
(a) constante individual: e
(b) símbolos funcionais: um único símbolo funcional unário, ' e um único binário,
*.

Bom, aqui, uma explicação. Um símbolo funcional de aridade n pode ser visto como um símbolo de predicados de aridade n + 1. Assim, podemos dizer que em LG não teremos símbolos de predicados, mas somente os símbolos funcionais acima exibidos. Porém, + e · denotariam então predicados de aridade 3.


Interpretação intuitiva

(veja mais detalhes aqui)

Lembre que, por meio de L, objetivamos 'falar' dos indivíduos de um determinado conjunto não vazio D (dito domínio ou universo do discurso), de suas relações,  bem como desejamos operar com eles (notadamente se se tratarem de entidades matemáticas, como números ou funções). Assim, temos o seguinte:

a) As constantes individuais funcionam como nomes de elementos distinguidos de D. Por exemplo, em LAR a constante 0 denota um elemento bem determinado do domínio; se este for (como em geral se supõe que seja) o conjunto N dos números naturais, então 0 geralmente denota o número natural zero.

b) Os símbolos para predicados têm a seguinte interpretação: os unários (de aridade 1) representam 'propriedades' dos elementos de D; os binários, relações binárias entre os elementos de D (por exemplo, em LAR o símbolo < pode representar a relação 'menor que' entre números; em LZF, Î em geral representa a relação de pertinência --podem haver outras intepretações para cada um dos símbolos; isso ficará calrp à frente); os de aridade 3 representam relações ternárias sobre elementos de D (por exemplo, a relação 'estar entre', que se aplica entre pontos em geometria) e assim por diante.

c) Os símbolos funcionais representam funções ou operações sobre D; os unários, funções unárias (por exemplo, em LAR o símbolo S pode ser visto como denotando uma função que associa a cada número natural n o seu sucessor Sn; em uma outra linguagem, poderia haver um símbolo unário interpretado como uma função que associa a cada elemento x de um certo domínio de números racionais, por exemplo, o seu oposto -x); os binários representam operações binárias entre elementos de D (em LAR,   + e · usualmente representam as operações de adição e de multiplicação respectivamente), e assim por diante.

Os símbolos lógicos têm sempre uma interpretação, digamos, 'fixa'; as variáveis individuais denotam elementos arbitrários de D, e os conectivos têm sua interpretação habitual. Os quantificadores serão tratados abaixo.


Termos e Fórmulas


De posse do vocabulário de L, o que objetivamos agora é descrever fatos acerca dos elementos de D. Assim, necessitamos 'aprender a escrever' por meio de L. Inicialmente, uma definição. Uma expressão de L é uma seqüência finita de símbolos de L (escritos na horizontal, da esquerda para a direita, etc.).  Algumas expressões de K denotam elementos de D, e são de interesse. Tais expressões denominam-se termos de L. Os termos de  LAR são os seguintes: as variáveis individuais, a constante 0, expressões da forma Su, u + v, u · v, para u e v termos de LAR. Os únicos termos de LZF são as suas variáveis individuais. Os termos de LG são: as variáveis individuais, o símbolo e e as expressões da forma u' e u * v, para u e v termos.

De maneira geral, os termos de uma linguagem arbitrária L são dados pela seguinte definição indutiva: (a) as variáveis individuais e as constantes individuais são termos; (b) se f é um símbolo funcional de aridade n e se u1,...,un são n termos, então f(u1,...,un) é um termo; (c) não há outros termos.

Note que, no caso de LAR, em conformidade com a definição precedente, deveríamos escrever +(u,v) e ·(u,v) em vez de u + v, u · v, que são meramente notações abreviadas para termos. O mesmo se dá com as outras linguagens mencionadas. (Tome cuidado com isso; veja se entendeu direito. Caso tenha dúvida, procure o professor ou a monitoria).

Quanto às fórmulas (nome abreviado para 'expressões bem formadas do ponto de vista da gramática de L'), daremos inicialmente a definição geral para uma linguagem arbitrária L, para depois vermos alguns exemplos. As fórmula de L são dadas pela seguinte definição indutiva: (a) Se u e v são termos, então u = v é uma fórmula (atômica); (b) se u1,...,un são termos e P é um símbolo de predicados de aridade n, então P(u1,...,un) é uma fórmula (atômica); (c) se A e B são fórmulas (já obtidas) e x uma variável individual, então ¬A, AÙB, A v B, AB, A↔B, "xA, $xA são fórmulas; (c) não há outras fórmulas.

Estaremos assumindo aqui uma convenção para o uso de parênteses, que não evidenciaremos. Assumiremos que você já sabe como trabalhar com isso.

Por exemplo, em LAR as expressões seguintes são fórmulas: "x$y(x=y) e $x(x=SSS0). Em LZF, temos, por exemplo: "x"y$z"t(tÎz ↔ t = x v t = y). Em LG, temos: "x(x * e = x).


Exercícios


1. Para a linguagem LAR, classifique cada uma das expressões seguintes como um termo, uma fórmula atômica, uma fórmula ou como nenhum dos casos: (a) "x "y (x + y = y + x); (b) 0 + x; (c) SS0 · S0 = SS0; (d) (x = 0) + SS0.
2. Escreva cada uma das sentenças abaixo em LAR:  (a) Para todo número natural n, o sucessor de n não é zero; (b) Para todos números naturais M e n, se m e n têm o mesmo sucessor, então eles são o mesmo número natural; (c) Zero não é o sucessor de nenhum número natural; (d) Para todo número natural n, a soma de n com zero é igual a n; (e) Para quaisquer números naturais m e n, tem-se que m é menor do que m, ou m é menor do que m ou eles são iguais; (f) Não há número natural menor do que zero.
3. O Algoritmo da Divisão (AD) diz que para quaisquer números naturais m e n, com n diferente de zero, existem   números naturais u e v únicos tais que m = n·u + v com v menor do que n. Escreva o AD em LAR.


Procure o professor ou a monitoria se tiver dúvidas.



Universidade Federal de Santa Catarina
Grupo Multidisciplinar de Estudos em Lógica e Fundamentos da Ciência-UFSC/CNPq