revisão de lógica


Sintaxe e Semântica da Linguagen da Lógica Clássica de Primeira Ordem com Igualdade


 

Sintaxe

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

Símbolos lógicos:

    (a) conectivos lógicos; Ø (negação), Ú (disjunção), ® (condicional material), Ù (conjunção), «  (bicondicional)

    (b) símbolos auxiliares de pontuação: (parênteses e vírgula);

    (c) variáveis individuais: uma coleção infinita e enumerável de variáveis individuais, que serão denotadas por x, y, z, w;

    (d) quantificadores: quantificador universal " (para todo, qualquer que seja) e o quantificador existencial: $ (existe, algum);

    (e) o símbolo de igualdade: =.


Símbolos não lógicos:

    (a) constantes individuais (uma coleção eventualmente vazia);

    (b) símbolos para predicados, ou de propriedades e relações (cada um de uma certa aridade n >0);

    (c) símbolos funcionais, ou símbolos de operações (uma coleção eventualmente vazia, mas, havendo tais símbolos, cada um de uma certa aridade n >0).


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) uma constante individual: e
(b) símbolos funcionais:  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. Em LG, há um único símbolo funcional unário, ' e um único binário,
*.


Interpretação intuitiva

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á claro à 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. É importante observara que há linguagens infinitárias, que permitam haver expressões bem formadas (fórmulas) contendo uma infinidade de símbolos. Porém não trataremos delas aqui.

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  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, A→B, 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 4
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.
4. Faça a distinção entre ocorrências livres e ligadas de variáveis em um termo e em uma fórmula. Dê exemplos.


Exercícios 5

  1. (a) Diga o que significa uma fórmula  a implicar tautologicamente uma fómula b. (b) Verifique se ¬(¬A → (B  → A)) implica tautologicamente ¬B → (A v B). (c) O que significa dizer que um conjunto de fórmula  implica tautologicamente uma dada fórmula? (d) Pode uma sentença ou um conjunto de sentenças implicar tautologicamente uma contradição?

  2. (a) Verifique se Γ = { ¬(¬B Ù A), ¬A v ¬C, ¬B → C } é consistente (ou seja, há uma valoração v tal que v(a) = V para toda a em Γ ). (b) Mostre que Γ = { A, ¬A} é inconsistente.

  3. Relacione as colunas (não basta indicar, é preciso mostrar as equivalências):

( a )    ¬A v (B → A)                         (    ) ¬B v A

( b )    A  →  ¬B                                (    )   A → B

( c )     ¬(A Ù ¬B)                              (    )   A →  (¬B v A)

  1. Simbolize adequadamente e verifique se o argumento seguinte é válido (a conclusão deve ser conseqüência tautológica do conjunto das premissas):

“Se 2 é primo, então é o menor primo. Se 2 é o menor primo, então 1 não é primo. 1 não é primo. Portanto, 2 é primo. ”

 

  1. Considere a linguagem LAR da aritmética elementar cujos  símbolos não lógicos são uma constante individual 0, um símbolo  funcional unário S e dois símbolos funcionais binários + e ∙. Pede-se: (a) dizer o que são termos e o que são fórmulas de LAR. (b) Classifique como termo, fórmula atômica, fórmula geral (molecular) ou como nenhuma delas cada uma das expressões seguintes: (i) S0 +  SSx, (ii) SS0 = Sx  + SS0, (iii) "x "y (x∙ Sy = y x + x), (iv) 0 + (Sx = y) = S0 + SS0.

  2. Explique direitinho a Redução ao Absurdo e dê um exemplo. (veja "Os alicerces da lógica proposicional clássica")


O significado da expressão  'Primeira ordem'

Na definição de fórmula vista acima, dissemos que "xA, $xA são fórmulas. Repare que x é uma variável individual. Assim, a definição de fórmula impõe que os quantificadores apliquem-se somente a variáveis individuais, ou seja, linguagens de primeira ordem quantificam somente sobre indivíduos do domínio, e não sobre suas propriedades ou coleções. Isso é, em essência, o que caracteriza tais linguagens como sendo de primeira ordem. Um exemplo pode ser importante aqui; o Princípio de Indução diz, informalmente, que se P é uma propriedade que se aplica a números naturais então:

    (i) se 0 tem esta propriedade (fato que escrevemos assim: P(0))
    (ii) sempre que um número natural tem a propriedade P, o seu sucessor também a tem

Disso, resulta que

    (iii) Todo número natural tem a propriedade P.

Parece 'natural' que escrevamos este princípio assim, usando uma variável P que percorre a coleção das propriedades dos números naturais:

"P(P(0) Ù "x (P(x) → P(Sx)) → "xP(x)

Acontece que esta não é uma expressão de LAR, devido ao que se explicou acima (os 'indivíduos' são os números naturais, e não pode haver quantificação sobre propriedades de tais números). A expressão acima é bem formada, no entanto, em uma linguagem de segunda ordem, na qual quantificação sobre propriedades ou coleções de indivíduos é permitida. Nas linguagens de segunda ordem, além de variáveis individuais, há variáveis para predicados (unários, binários etc), e a definição de fórmula deve ser adequadamente estendida. Nas linguagens de terceira ordem, quantifica-se também sobre propriedades de propriedades (ou sobre coleções de coleções), etc. A diferença entre se usar uma linguagem de primeira ordem ou uma de 'ordem superior' pode nada significar para você neste momento mas, acredite, isso leva a resultados muito importantes.

Um outro exemplo de uma expressão de uma linguagem e segunda ordem, e que tem importância filosófica de destaque é a seguinte, que é usualmente associada ao Princípio da Identidade dos Indiscerníveis, de Leibniz (PII). Este princípio diz, resumidamente, que não há entidades que difiram solo numero; se não são a mesma entidade, então há uma propriedade que as diferencia, ou seja, uma propriedade que uma delas tem e a outra não. O PII é formulado da seguinte maneira: para todos x e y, se eles concordam em todas as suas propriedades, então são a mesma entidade. Se x e y são variáveis individuais e se F é uma variável que percorre as propriedades desses indivíduos, o PII pode ser escrito assim:

"x"y("F(F(x) ↔ F(y)) → x = y).


Exemplo simples de uma linguagem de Segunda Ordem

Você entenderá melhor a distinção entre primeira e outras ordens por meio de um exemplo mais elaborado. Vamos descrever uma linguagem de segunda ordem que chamaremos de L2. Os símbolos de L2 são os seguintes:

a) conectivos lógicos usuais: negação, conjunção, disjunção, condicional material, bicondicional

b) quantificadores: universal e existencial

c) variáveis  individuais: x, y, z, ...

d) variáveis para predicados: X, Y, Z, ....(cada um de uma certa aridade)

e) constantes individuais: a, b, c,...

f) constantes para predicados: P, Q, R,...(cada um de uma certa aridade)

Temos então termos de primeira ordem (variáveis e constantes individuais) e de segunda ordem (variáveis e constantes para predicados). A fórmulas são definidas assim: se F é termo de segunda ordem de peso n e se t1, t2, ..., tn são termos individuais, então F(t1,...,tn) é uma fórmula atômica. Suponha que P é unário e que Q é binário. Então, repare que P(R) não é uma fórmula, bem como Q(X,Y), e nem P(P). (Justifique essa afirmativa). Ademais, a negação de uma fómula é uma fórmula, bem como são fórmulas a conjunção e a disjunção de duas fórmulas, uma fórmula implicar materialmente uma fórmula (eventualmente ela mesma), e uma fórmula ser equivalente (bicondicional) a uma fórmula (eventualmente ela mesma). Com relação aos quantificadores, dizemos expressões da forma "xA e $xA são fórmulas, para A uma fórmula qualquer, bem como expressões da forma "XA e $XA, para X uma variável de segunda ordem. Ou seja, permitimos agora que os quantificadores se apliquem a variáveis para predicados, o que não ocorre nas linguagens de primeira ordem (que têm unicamente predicados constantes, e não variáveis).

Como vimos acima, uma linguagem de segunda ordem é bem mais forte que uma de primeira ordem, no entanto, as maravilhas não vão muito longe. Pode-se descrever lógicas de segunda ordem mediante axiomas adequados, e estudar a sua meta-teoria. O problema é que alguns dos princiais teoremas que você verá como valendo para a lógica de primeira ordem, não valem para a lógica de segund aordem, como Compacidade, Löwenheim-Skolem e a Completude. Isso faz com que não se possa erigir uma Teoria de Modelos sensata para essas lógicas. Alguns dos maiores avanços filósoficos do século XX se assentam no estabelecimento desses fatos, que deve ser conhecido por qualquer pessoa que tenha uma formação filosófica razoável.

Seguindo esse raciocínio, podemos ergir linguagens de terceira ordem, quarta ordem, ou da ordem que desejarmos. A Teoria dos Tipos de Bertrand Russell generaliza isso tudo, mas foge aos objetivos dessas notas. Veja aqui.


Exercícios 6

1. Suponha uma linguagem de segunda ordem na qual P é um predicado unário e que Q é binário. Justifique porque  P(R), Q(X,Y) e P(P) não são fórmulas.

2. Acompanhe: um dos axiomas da lógica de segunda ordem é chamado de Axioma da Separação, e diz informalmente que toda fórmula corresponde a um predicado (ou seja, tudo o que podemos dizer por meio de uma fórmula, podemos fazê-lo por meio de uma propriedade ou relação), que podemos expressar assim: se F(t1,..,tn) é uma fórmula, então $X"x1..."xn(F(x1,...,xn) « X(x1,...,xn)). Ou seja, os objetos que satisfazem a fórmula são exatamente os mesmos que satisfazem o predicado. Vamos tomar um caso particular de uma fórmula com uma única variável livre, F(x). O axioma fica, neste caso:  $X"x(F(x) « X(x)). Suponha agora que a restrição na definição de fórmula (a saber, de que F(t1,...,tn) é uma fórmula atômica unicamente para t1, ..., tn termos individuais) não fosse respeitada. Isso permitiria que fossem fórmulas também expressões da forma F(T1,...,Tn)., para os Tj termos de segunda ordem, e as restrições indicadas no exercício anterior não precisariam ser obedecidas, e aquelas expressões poderiam ser fórmulas, bem como em particular ØX(X) seria uma fórmula. Se isso ocorresse, o Axioma da Separação teria que permitir também esas fórmulas, ficando assim formulado (para fórmulas com somente uma variável): $X"Y(F(X) « X(Y)), para toda fórmula F(X). Coloquemos então a fórmula ØX(X) no axioma fomulado desse modo, obtendo $X"Y(ØX(X) « X(Y)). Vamos chamar de R ao predicado que o axioma postula existir, em homenagem a Russell. Obtemos então "Y(ØR(X) « R(Y)). Como isso teria que valer para qualquer Y, valeria em particular para Y sendo R, donde ØR(R) « R(R). Por meio de regras simples, obtém-se uma contradição: ØR(R)ÙR(R), que expressa o célebre Paradoxo de Russell. Como você deve perceber, a restrição feita na definição de fórmula não foi à toa.


Importante

Lembre (e não esqueça mais) das equivalências  seguintes:

"xA ↔ ¬$x ¬A

 $xA ↔¬"x¬A.

(A → B) ↔ (¬A Ú B)

(A → B) ↔ ¬(A  Ù  ¬B)

(A Ù B) ↔  ¬(¬A Ú  ¬B)  

(A  Ú B) ↔  ¬(¬A  Ù  ¬B)  


Exercícios 7

1. Usando as abreviações acima, escreva as expressões equivalentes a:

(a) $x ¬A

(b) ¬$x A

(c) "x¬A.

(d) ¬"xA.

2.Considere as seguintes sentenças:

(a) Alguns S são P; 

(b) Nenhum S é P.

 Pede-se:

(1) escreva (a) sem usar o quantificador universal;

(2) escreva (a) sem usar o quantificador existencial;

(3) escreva (b) sem usar o quantificador universal;

(4) escreva (b) sem usar o quantificador existencial.

3. Considere uma linguagem L que contenha como símbolo não lógico unicamente um símbolo de predicado binário P. Interprete P(x,y) como 'x ama y'. Expresse as seguintes frases nessa linguagem: (a) Todos amam alguém. (b) Alguém é amado por alguém. (c) Alguém ama a todos. (d) Há alguém que é amado por todos. (e) Todos amam todos. (f) Ninguém ama a todos.

4. Recorde o que significam variáveis livres e ligadas em uma fórmula. Dê exemplos de fórmulas das linguagens acima em que haja ocorrências de variáveis livres e de variáveis ligadas. Dê um exemplo de uma fórmula de LAR na qual a variável x ocorra tanto livre quanto ligada. Diga o que são sentenças (fórmulas fechadas) de L.

5. Verifique que uma formulação equivalente ao PII acima é a seguinte: "x"y(x ≠ y $F((F(x) Ù ¬F(y)) v  (F(y) Ù ¬F(x)))).

6. Explique porque na definição de fórmula em uma linguagem de segunda ordem não podemos permitir que haja fórmulas do tipo P(P) para P um predicado unário.

7. Explique com suas palavras a distinção entre linguagens de primeira ordem e de segunda ordem.


Semântica

O conceito de fórmula é um conceito sintático, pois considera unicamente a forma das expressões (seqüências finitas de símbolos da linguagem), sem fazer referência aos significado dos termos envolvidos. Na contraparte semântica de uma linguagem (por exemplo, de uma linguagem de primeira ordem), damos atenção às expressões e  aos seus significados, ou interpretações. Conceitos semânticos são aqueles que são considerados fazendo-se referência não somente à forma das expressões de uma linguagem, mas também aos seus significados.

No que se segue, daremos atenção a uma linguagem genérica de primeira ordem que denotaremos por L. Claro está que o que for dito adapta-se às linguagens particulares com as quais temos trabalhado. É conveniente lembrar também que L visa 'falar' de um conjunto não vazio de indivíduos, de suas propriedades e relações, bem como em eventualmente 'operar' com eles, notadamente no caso de conjuntos de objetos matemáticos. Este domínio (ou universo) do discurso, que chamaremos de D, é o domínio percorrido pelas variáveis individuais de L. Assim, se x, y, z, ... são tais variáveis, cada uma delas denota um indivíduo (arbitrário) de D. Os outros símbolos não lógicos de L têm a seguinte interpretação: os predicados unários denotam subconjuntos de D. Lembrando que tais predicados podem ser vistos como representando propriedades dos elementos do domínio, o conjunto associado a um predicado unário é dito ser a sua extensão, ou seja, é entendido como representando a coleção dos indivíduos do domínio que têm a propriedade descrita pelo predicado. Os predicados binários (de aridade 2) são associados a relações binárias sobre D, ou seja, a subconjuntos de DxD (o produto cartesiano de D por D). De maneira geral, a predicados n-ários associam-se relações n-árias sobre D, ou seja, subconjuntos de Dx...xD (o produto cartesiano de D por D n vezes). Os símbolos funcionais unários associam-se a funções de D em D; os binários, a funções de DxD em D (ou seja, operações binárias sobre D) e, de maneira geral, os n-ários a funções n-árias sobre D.

Assim, uma interpretação para L, grosso modo, consiste em um domínio não vazio D de entidades sobre o qual as variáveis individuais atuam, e uma atribuição de entidades definidas com referência a este domínio para cada uma das constantes não lógicas de L nos moldes descritos acima. Se chamarmos de I a interpretação considerada de L, designaremos por I(X) à entidade que corresponde ao símbolo não-lógico X. Vamos considerar agora seqüências infinitas de elementos de D (isso é feito para que os detalhes técnicos se tornem mais simples). Como supusemos que as variáveis de L estão arranjadas em uma lista infinita x1, x2,..., então  cada seqüência associa um indivíduo de D a cada variável de L. Assim, dada uma fórmula qualquer a e uma seqüência s = <s1, s2,...> de elementos de D, cada uma das variáveis livres de a fica associada a um indivíduo de D por meio da seqüência s. Isso é importante para que possamos definir o que consiste dizer que uma seqüência s satisfaz uma fórmula a com respeito a uma interpretação I. Inicialmente, definimos uma função que associa a cada termo t de L um elemento s(t) de D como segue: 

a) se t é uma constante individual, digamos a, então s(t) é o elemento de D que a interpretação considerada associa a a.
b) se t é uma variável individual, digamos xj, então s(t) é o elemento sj da seqüência s.
c) se t é da forma f(t1...tn), com f símbolo funcional n-ário e os t1,...,tn sendo termos, então s(t) é I(f)(s(t1),...,s(tn)).

Então, vem a seguinte definição. Definimos o que significa dizer que  uma seqüência s satisfaz uma fórmula a de L com respeito a uma interpretação I como segue:

(i) se  a é uma fórmula atômica da forma P(t1...tn), onde P é um símbolo de predicado de aridade n, então s satisfaz  a com respeito a I se e somente se <s(t1),...,s(tn)> Î I(P).
(ii) se
a é uma fórmula atômica da forma t1 = t2, então s satisfaz  a com respeito a I se e somente se <s(t1),...,s(tn)> Î D(D), onde D(D) é a diagonal de D, ou seja, o conjunto D(D) = {<x,x> : x ÎD}.
(iii) s satisfaz ¬
b se e somente se s não satisfaz b.
(iv) s satisfaz aÙb se e somente se s satisfaz a e s satisfaz b.
(
v) s satisfaz  avb se e somente se s satisfaz a ou s satisfaz b.
(
vi) s satisfaz a b se e somente se s não satisfaz a ou satisfaz b.
(vii) s satisfaz
"xja se e somente se toda sj-variante de s, ou seja, toda seqüência s' que difira de s no máximo quanto ao elemento sj, é tal que s' satisfaz a.
(viii) s satisfaz $xja se e somente se existe uma sj-variante de s, ou seja, uma seqüência s' que difira de s no máximo quanto ao elemento sj, é tal que s' satisfaz a.

Obviamente, a definição acima pode ser simplificada, desde que alguns conectivos sejam definidos a partir de outros, o mesmo valendo para os quantificadores. Resulta que s satisfaz a b se e somente se s não satisfaz a e não satisfaz b, ou satisfaz a ambas.


Algumas definições importantes são as seguintes:

1. Uma fórmula a é verdadeira para uma interpretação I se e somente se toda seqüência s de elementos do domínio D de I satisfaz a. Escreve-se assim: I ╞ a.
2. Uma fórmula
a é falsa para uma interpretação I se e somente se nenhuma  seqüência s de elementos do domínio D de I satisfaz a. Escreve-se assim: I ╞/ a.
3. Uma interpretação I é um modelo para um conjunto
G de fórmulas se e somente se todas as fórmulas de G são verdadeiras para I (ou relativamente a I).

Claro está que podem haver fórmulas que não sejam nem verdadeiras e nem falsas relativamente a uma interpretação. Por exemplo, a seguinte fórmula da linguagem da aritmética elementar: x + 1 = 2 não é verdadeira e nem falsa de acordo com a interpretação standard dessa linguagem, da qual já falamos antes.

Da definição acima, resultam os seguintes fatos:

1. Uma fórmula é falsa para uma interpretação se e somente se sua negação é verdadeira relativamente a esta interpretação, e reciprocamente.

2. Não pode ocorrer que uma fórmula e sua negação sejam ambas verdadeiras para uma interpretação. Em outras palavras, nenhuma fórmula pode ser verdadeira e falsa para uma interpretação.

3. Se  I ╞ a e se  I ╞ a b, então  I ╞ b.

4. I ╞/ a b se e somente se I ╞ b e I ╞/ a.

5.  I ╞ a se e somente se  I ╞ "xja. Pelo fecho de uma fórmula, entende-se a fórmula obtida prefixando-se por quantificadores universais todas as variáveis que ocorrem livres na fórmula (em ordem descendente de índices). O que este resultado mostra é que uma fórmula é verdadeira para uma interpretação se e somente se o seu fecho o for.

6. Uma instância  de uma fórmula de uma linguagem proposicional é uma fórmula da linguagem L de primeira ordem obtida substituindo-se cada variável proposicional que apareça na fórmula dada por uma fórmula de L. Por exemplo, "xja → ($xia →  "xja) é uma instância da tautologia A → (B → A). Vem então o seguinte fato: toda instância de uma tautologia é verdadeira para qualquer interpretação.

7. Se a é uma fórmula fechada (sentença) de L, ou seja, uma fórmula sem variáveis livres, então para qualquer interpretação I, tem-se que I ╞ a ou  I ╞ ¬a (isto é,  I ╞/ a).

8. Se t é um termo livre para xj em a(xj), então "xja(xj) → a(t) é verdadeira para todas as interpretações. (este resultado será importante quando virmos os postulados da lógica elementar).

NOTA: Há um modo alternativo de se definir a verdade relativa a uma estrutura, que é por meio das chamadas linguagens diagrama. Para ter uma idéia, veja aqui.


Mais definições importantes:

1. Uma fórmula é logicamente válida se é verdadeira para todas as interpretações. Notação: ╞ a

2. Uma fórmula é satisfatível se existe pelo menos uma interpretação tal que existe uma seqüência s de elementos do domínio da interpretação que satisfaz a fórmula dada.

3. Um conjunto G de fórmulas é satisfatível se e somente se existe pelo menos uma interpretação tal que há pelo menos uma seqüência s de elementos do domínio da interpretação que satisfaz  todas as fórmulas de G.

4. Uma fórmula é contraditória se e somente se é falsa para qualquer interpretação, ou,equivalentemente, se e somente se sua negação for logicamente válida.

5. Uma fórmula a implica logicamente uma fórmula  se e somente se em qualquer interpretação, toda seqüência s que satisfaz a também satisfaz b.

6. Uma fórmula a é implicada logicamente por um conjunto G de fórmulas se e somente se, para qualquer interpretação, toda seqüência s que satisfaz as fórmulas de G também satisfaz a.

7.  a e são logicamente equivalentes  se e somente se uma delas implica logicamente a outra.

Resulta o seguinte:

1.  a implica logicamente  se e somente se a b é logicamente válida.

2. a e são logicamente equivalentes  se e somente se a b é logicamente válida.

3. Se a implica logicamente e a é verdadeira para uma interpretação, então b também é verdadeira para esta mesma interpretação.

4. Se a é implicada logicamente por um conjunto G de fórmulas e se todas as fórmulas de G são verdadeiras para uma certa interpretação, então a também é verdadeira para esta mesma interpretação.


Exercícios 8

1.Diga em que consiste uma interpretação para uma linguagem de primeira ordem que contenha os seguintes símbolos não lógicos: duas constantes individuais a e b; um símbolo de predicados unário P e um binário Q; um símbolo funcional unário f e um binário g. Descreva a semântica desta llinguagem.
2. Dê exemplos de interpretações para cada uma das linguagens exemplificadas acima: LAR, LZF, LG.
3. Diga em que consiste a interpretação 'standard' de LAR. (veja os exercícios abaixo).
4. Seja Γ um conjunto de sentenças de uma linguagem de primeira ordem L. Diga o que é um modelo para Γ. (o conceito de 'fórmula verdadeira' relativamente a uma interpretação é aqui ainda tomado de forma intuitiva).
5. Dê exemplos de pelo menos dois modelos para Γ = {G1, G2, G3}, onde G1, G2 e G3 são os axiomas para grupos vistos em sala.
6. Outros exercícios podem ser buscados no livro de C. A. Mortari já indicado, ou em outro qualquer de acordo com a sua preferência. O importante é que você adquira familiaridade com a terminologia e com as linguagens de primeira ordem.
7. Justifique cada uma das afirmativas abaixo.
    a) Uma fórmula é logicamente válida se e somente se sua negação não é satisfatível.
    b) Uma fórmula é satisfatível se e somente se sua negação não é logicamente válida.
    c)  É impossível que uma fórmula e sua negação sejam ambas logicamente válidas.
    d)  Uma fórmula é contraditória se e somente  se sua negação for logicamente válida.


Exercícios 9
Nestes exercícios, usaremos a linguagem LAR já sua conhecida. Vamos considerar quatro interpretações para ela. O objetivo é que você entenda o que são essas  interpretações e que sentenças de uma linguagem podem ser verdadeiras (no sentido de Tarski, que você já deve ter entendido) em uma interpretação mas falsas em outras. Veja todas elas, pois o exercício 2 é relevante. Os exemplos são tirados de G. S. Boolos, J. P. Burguess e R. C. Jeffrey, Computability and Logic, 4th ed., Cambridge Un. Press, 2003, Cap. 9.

1. Considere as seguintes sentenças de LAR :

(A)  "x$y( x < y Ù ¬$z( x < z  Ù z < y))

(B) "x( x < Sx Ù ¬$z( x < z  Ù z < Sx))

(C) $x( x + x = S0)

(D) $x( x ∙ x = SS0)

Se quiser, defina 1 =def  S0, 2 =def  S1 etc. para facilitar. Considere agora as seguintes interpretações para LAR.

Int.1 (dita interpretação standard, padrão) O domínio é o conjunto dos números naturais, a constante individual 0 denota o número zero, o símbolo funcional unário S é interpretado na 'função sucessor', ou seja, dado um x qualquer, Sx denota x +1, o predicado binário < é interpretado na relação usual 'menor que', e os símbolos funcionais + e ∙ são interpretados como as usuais operações de adição e de multiplicação de números naturais. Verifique agora que (A) afirma que para qualquer número natural, há um 'número natural maior mais próximo', e que (B) diz que o sucessor desse número é o tal. Ambas são verdadeiras para esta interpretação. No entanto, (C) e (D) são ambas falsas. Por quê? (resp.: não há no domínio as entidades que asseveram existir. Justifique.)

Int.2 O domínio é o conjunto Q* dos números racionais não negativos. A constante individual 0 denota o número racional zero, < a usual relação de menor que entre números racionais, Sx adiciona 1 a x  e + e ∙ denotam as usuais operações de adição e de multiplicação de números racionais em  Q*. Verifique agora que (A) e (B) são ambas falsas, mas que (C) é verdadeira. O que dizer de (D)? (resp: é falsa! Justifique.).

Int.3 O domínio é o conjunto D = { 0, 1/2, 1, 1 1/2, 2, 2 1/2, 3, ...} dos inteiros não negativos e  dos 'meio inteiros' não negativos. De novo, a constante 0 denota o zero e os demais símbolos não lógicos são interpretados como no exemplo acima, porém agora dizendo respeito aos elementos de D apenas. Verifique que (A) e (C) são verdadeiras e que (B) e (D) são falsas. Justifique. (DICA: Repare que, pela definição dada de sucessor, S0 = 1, S(1/2) = 1 1/2 , etc, ou seja, o 'sucessor' de um elemento da seqüência não é necessariamente o seguinte a ele na seqüência).

Int 4 Finalmente, o domínio é o conjunto R* dos reais não negativos. Novamente, os símbolos lógicos de LAR são interpretados como no caso anterior, porém agora dizendo respeito aos elementos do domínio em questão. Verifique que todas as sentenças (A)-(D) são verdadeiras. Note que neste caso (D) está afirmando a existência de um número que pode (como em geral é) ser denotado por √2.

2. Tendo em vista os exemplos do exercício anterior, justifique porque não é possível encontrar uma interpretação na qual (A) seja falsa e (B) verdadeira. Isso é precisamente o que se quer dizer com (A) ser conseqüência lógica de (B). Explique isso direitinho, fazendo um texto a respeito. Sugestão: além dos textos já indicados, sobre a conseqüência lógica, leia o parágrafo 1 do Capítulo 2 de da Costa, N. C. A., Ensaio sobre os fundamentos da lógica, São Paulo, Hucitec, 2a. ed., 1994.

3. Se o domínio de uma interpretação é infinito, como podemos mostrar que uma sentença da forma "x F(x) é verdadeira?

4. (Para os que gostam de estudar) Comente sobre as diferenças entre as interpretações objectual e substitucional dos quantificadores. Essa distinção é importante para que se entenda várias coisas em filosofia, como por exemplo as posições de Quine, dentre outros, ou simplesmente para responder o exercício anterior. Veja o livro de S. Haack já indicado ou outros textos de filosofia da lógica.