Embed Size (px)
Citation preview
LIÇÕES DE LÓGICA
Fascículo I
Andréa Loparic
2
Sumário 1.Nota Introdutória.................................................................. 4 2. Gramática de L (Parte 1) ..................................................... 6 2.1 Vocabulário de L.................................................................... 6 2.2. Expressões de L.................................................................... 10. 2.3. Termos de L......................................................................... 10 2.4. Fórmulas de L ...................................................................... 12 3. Semântica de L (Parte 1)...................................................... 14 3.1. Interpretações para L............................................................ 14 3.2. Denotação de um termo fechado............................................. 17 3.3. Valor de verdade das sentenças atômicas................................. 21 4. Gramática de L (Parte 2) ......................................................24 4.1. Definição de fórmula de L.......................................................24 4.2. Complexidade de uma fórmula................................................ 27 4.3. Árvore de geração de α.......................................................... 29 4.4. Árvores moleculares ............................................................. 31 4.5. Ocorrência ligada ou livre de uma variável numa fórmula ...........32 4.6. Sentenças de L..................................................................... 33 4.7. Componentes sentenciais básicos de uma sentença................... 34 4.8. Sentenças CS....................................................................... 35 5. Semântica proposicional....................................................... 37 5.1. Conceitos fundamentais da semântica proposicional................... 47 5.2. Aplicação dos conceitos proposicionais à linguagem L................ 56 6. Semântica de L (Parte 2) ..................................................... 59 6.1 Definição de verdade para sentenças de L................................. 61 6.2. Conjunto Solução de uma fórmula........................................... 63 6.3. Significado formal de uma fórmula...........................................69 6.4. Diagramas para uma fórmula α (com uma só variável livre) ....... 71 6.5. Diagramas para fórmulas compostas por duas fórmulas
nas quais ocorre uma mesma variável livre.............................. 74 6.6. Algumas conseqüências da extensionalidade da designação........ 84 6.7. Conjunto solução para fórmulas contendo sentenças
como subfórmulas................................................................. 85 6.8. Algumas equivalências e algumas implicações........................... 87 6.9. Relações: fórmulas com duas variáveis ξ e ξ’............................ 89 6.10. Com duas variáveis quantificadas só é possível
expressar 12 significados formais distintos............................... 98 6.11. Algumas equivalências entre sentenças.................................. 102
3
6.12. Sentenças universais – alguns paradigmas............................. 105 6.13. Expressão de universos e conjuntos finitos............................. 106 6.14. Expressão de outras propriedades de relações binárias............. 109 6.15 Conceitos semânticos fundamentais da
lógica de primeira ordem..................................................... 111 6.16. Traduções da linguagem natural para
a linguagem formal e vice-versa........................................... 117
4
Nota introdutória Este é o primeiro fascículo de uma série de três. Foi concebido como um
primeiro curso de Lógica Formal destinado a estudantes da área de
Humanas, em especial, a estudantes de Filosofia. A lógica aqui estudada é
o Cálculo de Predicados com Identidade e Símbolos Operacionais . Neste
primeiro texto, estudamos a gramática e a semântica desse sistema lógico.
Como se pode bem observar, nosso texto se aproxima em vários pontos do
livro “Lógica Elementar” de Benson Mates, que adotamos por vários anos
como livro texto de cursos que ministramos: com efeito, definições básicas
da gramática e da semântica seguem as mesmas linhas que as encontradas
no capítulo 9 do livro de Mates. Procuramos desenvolver no nosso texto
conceitos e métodos que complementem, aprofundem ou facilitem tanto a
compreensão da construção da linguagem como a do alcance de sua
semântica. Em particular, acreditamos serem especialmente interessantes
as construções das árvores de formação e das árvores moleculares, na
parte da sintaxe, e o desenvolvimento da temática do significado formal e
dos conjuntos-solução, bem como o uso de diagramas, na compreensão da
semântica de primeira ordem.
Dois outros fascículos das “Lições de Lógica” estão sendo escritos. No
segundo, apresentaremos alguns sistemas dedutivos para o Cálculo de
Predicados com Identidade. Pretendemos, inicialmente, apresentar um
sistema de dedução natural. O sistema é o de Mates, mas, acreditamos,
5
pudemos dar-lhe uma apresentação mais fácil de ser aceita e
compreendida. Além disso, o significado de cada regra é discutido assim
como o papel que cada uma delas exerce, enquanto integrante de um
sistema que é completo, com respeito à semântica estudada no capítulo I.
Ao lado desse sistema, apresentaremos também um sistema do tipo
axiomático; um terceiro, que usa tableaux analíticos; e, finalmente, um
sistema que trabalha com seqüentes. No terceiro fascículo, inicialmente
apresentaremos alguns metateoremas; entre eles, o teorema da
extensionalidade dos termos, os teoremas da correção e completude,
compacidade e uma forma simples do teorema de Löwenheim Skolem.
Finalmente, estudaremos algumas propriedades de teorias de primeira
ordem e examinaremos alguns exemplos particularmente interessantes,
entre os quais, algumas aritméticas de primeira ordem.
6
Gramática de L (parte 1)
A linguagem L que iremos estudar é a linguagem da Lógica de Predicados
de Primeira Ordem, com identidade e símbolos operacionais. Ela será
introduzida da seguinte maneira: em primeiro lugar, apresentaremos um
vocabulário, especificando todos os símbolos que integram as expressões
da linguagem.
Os símbolos serão apresentados juntamente com suas categorias
gramaticais – por essa razão dizemos que se trata de um vocabulário
categorial. Note-se que esse vocabulário terá uma característica
especialmente importante: a de ser um vocabulário decidível ; isso significa
que dado um símbolo, pode-se verificar, de forma mecânica e em tempo
finito, se se trata de um símbolo desse vocabulário e, em caso positivo, a
que categoria gramatical o símbolo pertence. Apresentemos, então, o
vocabulário da linguagem L.
Vocabulário de L
O vocabulário de L é formado pelas seguintes categorias de símbolos:
a) variáveis;
b) símbolos interpretáveis • nominais, • verbais;
c) símbolos lógicos • predicado de igualdade, • conectivos, • símbolos de quantificação;
d) símbolos auxiliares de pontuação.
a) As variáveis são letras minúsculas entre ‘u’ e ‘z’, com ou sem índices inferiores (subscritos).
7
Exemplos: x, y, z1, x2, w7, x123
b) Temos aqui dois grandes grupos:
i) Os símbolos interpretáveis nominais são minúsculas de ‘a’ a ‘t’, com ou sem índices inferiores (subscritos) e com ou sem índices superiores (sobrescritos).
• Os símbolos interpretáveis nominais sem sobrescritos são ditos saturados e são chamadas constantes individuais. Exemplos: a, b, a1, c2, m, n5 etc..
• Os símbolos interpretáveis nominais com sobrescritos são ditos insaturados; o sobrescrito indica o seu grau de insaturação ou carência. Eles são chamados símbolos funcionais de carência n (onde n é o seu sobrescrito) ou operadores de carência n. Exemplos: f1, g2
1, h31, são operadores de carência 1;
f2, g2, h12, h22, operadores de carência 2;
f3, g3 etc., operadores de carência 3;
etc..
ii) Os símbolos interpretáveis verbais são maiúsculas com ou sem subscrito e com ou sem sobrescrito.
• Os símbolos interpretáveis verbais sem sobrescritos são ditos saturados e são chamados letras sentenciais, ou ainda predicados
de carência 0. Exemplos: P, Q, R1, A, B3, S15, etc..
• Os símbolos interpretáveis verbais com sobrescrito são ditos insaturados; o sobrescrito indica o seu grau de insaturação ou sua carência. Ele são chamados predicados de carência n, onde n é seu sobrescrito. Exemplos: F1, G1, S1
1, H21 são predicados de carência 1;
F2, B2, H32, G19
2são predicados de carência 2;
A3, F23, H13, G5
3, R3 são predicados de carência 3; etc.. Observações:
1. Os subscritos e sobrescritos que podem afetar símbolos das categorias a),
e b) são números inteiros positivos. Eles não são considerados símbolos,
8
mas sim, partes de símbolos. Dessa forma, x1 é um único símbolo, assim
como a12,, f21, h13 etc..
2. Os subscritos cumprem unicamente a função de aumentar a quantidade de
símbolos disponíveis em cada categoria. Assim, há uma quantidade infinita
de símbolos em cada uma delas. Além disso, eles induzem uma ordem
alfabética em cada categoria ou subconjunto:
ordens alfabéticas segundo as categorias
- das variáveis: u, v, x,…, z, u1, v1,…, z1, u2, …
- das constantes individuais: a, b,…, t, a1, b1,…, t1, a2, …
- das letras sentenciais: A, B,…, Z, A1, B1,…, Z1, A2, ...
- dos operadores de carência 1: a1, b1,…, t1, a11, b11,…, t11, a21, …
- dos predicados de carência 1: A1, B1,…, Z1, A11, B1
1,…, Z11, A2
1 …
- dos operadores de carência 2: a2, b2,…, t2, a12, b1
2,…, t12, a2
2,…
etc..
3. As variáveis e as constantes individuais formam um grupo de símbolos
chamados símbolos individuais.
c) Os símbolos lógicos são oito: • o predicado de igualdade = ; também chamado de símbolo lógico
da identidade; • cinco conectivos, a saber: o conectivo unário da negação: ¬
quatro conectivos binários: conjunção: ∧ , disjunção: ∨ , condicional: → , bi-condicional: ↔ ;
• dois símbolos de quantificação, a saber: o símbolo da quantificação universal: ∀ , e o símbolo da quantificação existencial: ∃ .
9
Observação:
As notações usadas para os símbolos lógicos não são unificadas na literatura.
Apresentamos, abaixo, alguns exemplos de notações alternativas para os
conectivos, usadas por vários autores:
Conectivos Notações alternativas
Negação − , ~
Conjunção . , &
Condicional ⊃
Bi-condicional ≡
(Esses símbolos, no entanto, não fazem parte do nosso vocabulário; assim,
não pertencem à linguagem aqui apresentada.)
d) Os símbolos de pontuação são os dois parênteses: ( , ) . Há como constituir uma linguagem de primeira ordem que não os utiliza, mas não é o que faremos aqui.
EXERCÍCIO
Classifique os símbolos abaixo, com respeito ao vocabulário de L.
a) f2 f) h21v l) F2 q) ∀1
b) z1 g) x2 m) h1 r) m
c) a1 h) > n) y2 s) b3 d) A1 i) + o) y2 t) ≡ e) F
12 j) Q p) ∧ u) P
10
Expressões de L
Uma expressão do vocabulário de L é uma seqüência finita de símbolos do vocabulário de L. Assim, se σ1, σ2, …, σn são símbolos do vocabulário de L, a seqüência formada pelo símbolo σ1, seguido do símbolo σ2, seguidos ... , seguidos do símbolo σn é uma expressão do vocabulário de L.
Mais rigorosamente, podemos definir as expressões de L assim: se σ é um símbolo de L, então σ é uma expressão de L e o resultado de acrescentarmos σ ao final de uma expressão de L é expressão de L.
Se σ1σ2…σn é uma expressão e para algum i, 1≤i≤n, σ é σi , dizemos
que σ ocorre em σ1σ2…σn . Se σ ocorre mais de uma vez numa dada expressão, as diferentes ocorrências de σ são contadas da esquerda para a direita: falamos na primeira, na segunda, na terceira ocorrência de σ na expressão, e assim por diante.
Nem todas as expressões do vocabulário de L são expressões
gramaticais ou expressões bem formadas de L. As expressões bem formadas de L compõem 2 grupos: os termos e as fórmulas.
Termos de L.
O conjunto dos termos de L pode ser assim definido: a) um símbolo individual é um termo de L, b) se ϕn é um operador de carência n e τ1,…,τn são termos de L,
então a expressão ϕnτ1,…,τn é um termo de L. Exemplos: a, x, f1a, g2ax, h1f1a, g2f1ah1b, x1, y, f1
1x, h3f1ah1g2xyg2ab são termos.
Observação:
A definição de termo, assim como a segunda definição de expressão de L,
são exemplos de um tipo de definição muito comum em lógica: a definição
por indução. Um conjunto indutivamente definido contém dois tipos de
elementos: os elementos originais ou básicos; e os elementos que são
gerados por meio de um número finito de aplicações de um certo número de
regras de geração. Assim, podemos associar aos elementos gerados um
número que corresponde à quantidade de aplicações de regras necessário
11
para a sua geração; e, aos elementos originais, associamos o número 0. O
número assim associado a cada elemento de um conjunto indutivamente
definido é, então, dito o grau de complexidade do elemento ou geração do
elemento.
No caso dos termos:
• a, x, b1 são exemplos de termos originais ou básicos, ou seja, termos de
complexidade 0 ou de geração 0;
• f1a, g2ab, h3xbc são termos de complexidade 1;
• g2f1ab, h3abg2xy são termos de complexidade2;
• f2g2abh1a, f1f1f1b, h2g2abf3xby têm complexidade 3;
• etc..
Observe-se que, na definição de termo, há uma única regra de geração dos
termos complexos. Como essa regra prescreve que se tome um operador de
carência n seguido de n termos para formar um novo termo, e como os
termos básicos [condição a)] não contêm operadores, a complexidade de um
termo pode ser medida pelo número de ocorrência de operadores nesse
termo.
Os termos podem ser ainda classificados em dois grupos: termos abertos ou fechados. Os termos abertos são aqueles que contêm ocorrências de variáveis (pelo menos uma ocorrência de variável); os termos fechados não contêm ocorrências de variáveis.
EXERCÍCIO
Quais das expressões são termos do Cálculo de Predicados? Quais são termos fechados?
a) f2a1f1b f) g2xh3abf1c
b) g3abf3abc g) a2b2abc
c) g3af1f2bc h) af1b
d) ¬ f2ab i) h3af1xh2ab
e) f2aP1x j) ∀x f1x=f1y
12
Fórmulas de L
A outra classe de expressões bem formadas de L é constituída pelas fórmulas. A definição completa de fórmula é também uma definição por indução. Primeiramente, definimos um conjunto básico de fórmulas, ditas fórmulas atômicas. Essas são as fórmulas de complexidade 0. Em seguida, são dadas regras de obtenção de fórmulas mais complexas a partir de fórmulas menos complexas.
Fórmulas atômicas
Nessa primeira fase de estudo da gramática, vamos nos limitar a
apresentar a definição de fórmula atômica. A definição indutiva completa de fórmula será introduzida posteriormente.
Há 3 tipos de fórmula atômica, a saber: i. uma letra sentencial é uma fórmula atômica; ii. um predicado de carência n seguido de n termos é uma fórmula
atômica; iii. uma expressão formada pelo predicado lógico da igualdade entre
dois termos é uma fórmula atômica.
Assim, se Π representa uma letra sentencial, Πn, um predicado de carência n e τ1, τ2,…, τn, termos de L, uma fórmula atômica tem uma das seguintes formas:
i. Π; ii. Πnτ1,…, τn ; iii. τ1=τ2.
Como os termos, as fórmulas atômicas também se subdividem em
abertas e fechadas. Fórmulas atômicas abertas são as que contêm ocorrência de variáveis, as fechadas são as que não contêm tais ocorrências. As fórmulas atômicas fechadas são chamadas sentenças
atômicas.
13
Observe-se que se uma variável ocorre numa fórmula atômica, essa
ocorrência se dá dentro de um termo que figura como parte dessa fórmula. Assim:
• fórmulas atômicas do tipo i são sentenças atômicas; • fórmulas do tipo Πnτ1,…, τn são sentenças se e só se τ1,…,τn forem
termos fechados; • fórmulas atômicas do tipo τ1=τ2 são sentenças se e só se τ1 e τ2
forem termos fechados.
Observe-se, ainda, que o símbolo = é um predicado lógico; assim, é um símbolo do tipo verbal e, nesse sentido, integra a classe dos símbolos verbais ou predicativos, juntamente com as letras sentenciais e predicados de carência n. A seguinte característica distingue, então, os termos das fórmulas atômicas: enquanto os termos são formados exclusivamente por símbolos nominais, uma fórmula atômica conterá necessariamente uma ocorrência de um símbolo verbal. Do ponto de vista gráfico, enquanto um termo é uma seqüência de letras minúsculas, a fórmula atômica conterá um símbolo que não é uma letra minúscula: poderá ser uma maiúscula ou o sinal de igualdade.
EXERCÍCIO
Classifique as expressões abaixo em termos (fechados ou abertos), fórmulas atômicas (fechadas ou abertas) ou expressões mal formadas.
a) F2g1xh
2ab i) F
1G1x
b) g2ab=x j) F=G
c) R l) x=a
d) h2bh
2bh
2bb m) G
3h2abf
1bb
e) F2ab=x n) a+b=c
f) xy=z o) x2
g) f2xy=z p) F
1x1
h) F1f2xy q) f
1x1
14
Semântica de L (parte 1)
Vamos interromper, nesse momento, o estudo da sintaxe para introduzir alguns conceitos que nos possibilitarão atribuir significados a algumas expressões de L já introduzidas sintaticamente. As expressões de L ganharão significados quando associadas a interpretações e de acordo com regras que formularemos em seguida.
1. Interpretações para L
Uma interpretação I para L é dada por:
• um conjunto não-vazio de objetos quaisquer, UI, dito universo de
discurso de I; • uma função ℑ que associa significados aos símbolos interpretáveis
de L, conforme as seguintes estipulações: i) a cada constante individual κ, ℑ associa um objeto de UI — ou
seja: ℑ(κ) ∈ UI; ii) a cada operador de carência n, ϕn, ℑ associa uma operação n-
ária em UI — ou seja: ℑ(ϕn): UIn ∆ UI;
iii)a cada letra sentencial, Π, ℑ associa um dos dois valores de verdade, o verdadeiro (V) ou o falso (F) — ou seja: ℑ(Π) ∈ {V, F};
iv)a cada predicado de carência n, Πn, ℑ associa uma relação n-ária entre objetos de UI — ou seja: ℑ(Πn) ⊂ UI
n.
Como se vê, infinitas interpretações podem ser dadas para a linguagem L; a escolha de uma interpretação é arbitrária e poderá atender a interesses e conveniências nas aplicações e usos de L.
As interpretações podem ser ditas completas ou incompletas. Uma interpretação é completa se a cada objeto do universo uma constante estiver associada; caso contrário, é incompleta. Em outras palavras, como as constantes individuais desempenham o papel de nomes de objetos, numa interpretação incompleta há objetos no universo de discurso que não são
15
nomeados por constantes individuais. Em universos de cardinal finito ou enumerável, as interpretações podem ser completas (embora nem sempre devam ser), pois o conjunto das constantes individuais é enumerável; mas, em universos de cardinal maior que o dos números naturais, as interpretações são necessariamente incompletas.
Observe-se, ainda, que um princípio é fundamental na construção de interpretações: cada símbolo interpretável é associado a uma única significação; no entanto, nada impede que dois distintos símbolos sejam associados a uma mesma significação. Resumindo: numa mesma interpretação, pode haver sinonímia; o que não pode haver é equivocidade.
Exemplo de uma interpretação: I
UI: conjunto dos números naturais {0, 1, 2, ... }
ℑ(a) = 0; ℑ(b) = 5; ℑ(c) = 7;
as demais constantes individuais denotam o número 1.
ℑ(f1) = função “sucessor”; ℑ(g1) = função “quadrado”;
ℑ(h1) = função “dobro”;
ℑ(s2) = função “soma”; ℑ(p2) = função “produto”;
ℑ(d2) = função que associa a cada par <m,n>:
m-n, se m≥n; 0, se m < n;
as demais funções n-árias são interpretadas pelas funções “projeção do
primeiro argumento”, i.e. ℑ(ϕn (m1, ..., mn)) = m1, para todo símbolo funcional
n-ário ϕn outro que os acima relacionados.
ℑ(A) = V; ℑ(B1) = V;
as demais letras sentenciais são associadas ao F.
ℑ(F1) = {0, 2, 4, 6,…} (conjunto dos números naturais pares);
ℑ(G1) = conjunto dos números naturais primos;
ℑ(H1) = {2, 71, 245, 1024, 3258, 10999};
ℑ(R2) = relação “menor que”;
ℑ(D2) = relação “divisível por”;
Os demais símbolos de predicado são associados ao conjunto vazio; i.e., para
cada predicado Πn não mencionado acima, ℑ(Πn) = ∅.
Claramente, a interpretação acima é uma interpretação incompleta pois há objetos no seu universo que não são designados por constantes – por exemplo, o número 2. Uma interpretação completa com o mesmo universo poderia ser obtida a partir da interpretação acima, alterando a interpretação das constantes individuais de modo que as constantes individuais sem
16
índices inferiores denotem o 0; e que cada constante com índice inferior denote o número correspondente a esse índice.
Outro exemplo de interpretação: I’
UI’ = conjunto das pessoas humanas
ℑ’(a) = Aristóteles; ℑ’(n) = Napoleão Bonaparte; ℑ’(p) = Dom Pedro II; ℑ’(k)
= Kant; as demais constantes são associadas à Princesa Isabel.
ℑ’(f1) = função que associa a cada primeiro humano, ele próprio; e a cada um
dos demais, o seu pai; vamos nos permitir dizer: função “pai”;
ℑ’(m1) = função “mãe”, definida analogamente à função “pai”, acima.
ℑ’(F1) = conjunto dos filósofos; ℑ’(B1) = conjunto dos brasileiros;
ℑ’(M1) = conjunto das mulheres; ℑ’(R2) = relação “mais velho que”;
ℑ’(S2) = relação “casado com”; ℑ’(C2) = relação “conterrâneo de”;
ℑ’(P2) = relação “professor de”. Todas as letras sentenciais são associadas ao V; todos os símbolos funcionais
não mencionados são associados à função “projeção do primeiro argumento”;
todos os símbolos de predicado não mencionados são associados ao conjunto
vazio.
Um terceiro exemplo de interpretação: I”
UI” = conjunto dos países e cidades do mundo
ℑ”(a) = Argentina; ℑ”(b) = Brasil; ℑ”(c) = Cuba; ℑ”(d) = Dinamarca;
ℑ”(e) = Espanha; ℑ”(f) = França; ℑ”(b1) = Brasília; ℑ”(b2) = São Paulo;
ℑ”(b3) = Porto Alegre; ℑ”(b4) = Rio de Janeiro; ℑ”(b5) = Campinas;
ℑ”(b6) = Recife; ℑ”(f1) = Paris; ℑ”(o1) = Buenos Aires. As demais constantes
individuais são associadas à Inglaterra.
ℑ”(f1) = função que associa: a cada cidade, ela própria, e
a cada país, sua capital;
ℑ”(g1) = função que associa a cada cidade, o país a que pertence, e a cada
país, ele próprio;
Todos os demais símbolos funcionais são associados à função projeção do
primeiro argumento.
Todas as letras sentenciais sem índices inferiores são associadas ao V; todas as
letras sentenciais com índices inferiores são associadas ao F.
17
ℑ”(F1) = conjunto dos países; ℑ”(G1) = conjunto das capitais;
ℑ”(H1) = conjunto das cidades com mais de 1.000.000 de habitantes;
ℑ”(B1) = conjunto das cidades brasileiras; ℑ”(R2) = ser “mais populoso que”;
ℑ”(C2) = ser “uma cidade de”. Todos os demais símbolos de predicado são
associados a ∅.
EXERCÍCIOS 1) Construa uma interpretação I cujo universo seja { 1, 2, 3, 4 }, destacando:
I(a) I(f1) I(F1) I(A) I(b) I(g2) I(G2) I(B)
2) Dê exemplo de interpretação, destacando I(a), I(c), I(m), I(f1), I(g2), I(F1), I(G1).
a) Tomando como universo UI = {1, 2, 3, 4, 5}. b) Tomando como universo o conjunto dos seres humanos. c) Tomando como universo o conjunto dos brasileiros.
3) Dê exemplo de:
a) uma interpretação completa;
b) uma interpretação incompleta.
2. Denotação de um termo fechado
O conjunto dos termos fechados já foi definido anteriormente. No entanto, ele pode ser indutivamente obtido pelas condições que se seguem:
1)uma constante individual é um termo fechado;
2)se τ1, …,τn são termos fechados e ϕn é um símbolo funcional de carência n, então ϕnτ1…τn é um termo fechado.
18
Para definir a denotação de um termo fechado τ, de acordo com uma interpretação qualquer I, usaremos a estratégia sugerida pela definição acima: definiremos a denotação de um termo fechado simples, obtido pela cláusula 1) e, em seguida, diremos como calcular a denotação de um termo ϕnτ1…τn , obtida pela cláusula 2), a partir das denotações de τ1, …, τn . Para abreviar a expressão “a denotação de τ segundo I”, usaremos a notação: δI(τ).
Definição da denotação de um termo fechado ττττ 1) se τ é uma constante individual, δI(τ)=ℑ(τ); 2) se τ é ϕnτ1…τn , δI(τ)=ℑ(ϕn)[δI(τ1), …, δI(τn)].
Exemplos:
Seja I a primeira interpretação dada como exemplo. Então:
δI(a)=0 δI(b)=5 δI(c)=7 δI(d)=1
δI(f1a)= ℑ(f1)[δI(a)] = o sucessor de 0 =1
δI(s2bc)= ℑ(s2)[δI(b), δI(c)] =5+7=12
δI(h1s2bc)= ℑ(h1)[δI(s2bc)] = o dobro de 12 =24
δI(p2ch1b)= ℑ(p2)[δI(c),δI(h
1b)] = δI(c) × δI(h1b)= 7×ℑ(h1)[δI(b)] =
= 7 × o dobro de 5 = 7 × 10 = 70
Seja, agora, I a interpretação anteriormente denotada por I”. Então:
δI(a)= a Argentina δI(b)= o Brasil
δI(f1b)= ℑ(f1)[δI(b)] = ℑ(f
1)[Brasil]= Brasília
Analogamente,
δI(f1a)=Buenos Aires δI(b5)=Campinas
δI(g1b5)=Brasil δI(f1g1b5)=Brasília Observe-se que cada termo fechado denota, segundo uma interpretação, um único objeto do universo. Isso se prova facilmente por uma indução baseada na definição de denotação de termos fechados; examinemos as duas cláusulas:
19
1) τ é uma constante individual; então δI(τ)=ℑ(τ); ora ℑ(τ) é necessariamente um objeto do universo de ℑ(τ);
2) τ é ϕnτ1…τn ; então δI(τ)=ℑ(ϕn)[δI(τ1), …, δI(τn)]; ora, se δI(τ1), …, δI(τn), que são termos de menor complexidade, denotarem objetos do universo de ℑ, digamos, tomados nessa ordem, eles constituem uma n-upla de objetos do universo, <o1, …, on>; ora, ℑ(ϕn) é uma operação n-ária; portanto, quando aplicada à n-upla de objetos do universo, resulta em um objeto do universo; assim a denotação de ϕnτ1…τn segundo ℑ é sempre um objeto do universo de ℑ.
A propriedade que acabamos de demonstrar responde por duas características importantes dessa linguagem: em primeiro lugar, quando associada a uma interpretação, os termos denotam de forma unívoca; em segundo lugar todos os termos denotam: não há termos que se comportem como “o atual rei da França” – para citar o famoso exemplo de Russell.
EXERCÍCIOS
1) Seja I uma interpretação tal que:
UI = {1, 2, 3, ...}
I(f1) = função sucessor
I(g1) = função quadrado I(a) = 1
I(h1) = função cubo I(b) = 2
I(g2) = função soma I(c) = 3
I(h2) = função produto I(d) = 5
1.1) Determine:
a) δI(f1b) f) δI(h
2ah
2ah
2aa)
b) δI(f1g1b) g) δI(g
1g2af
1b)
c) δI(f1h2bd) h) δI(g
1f1g1g2ab)
d) δI(h2af
1b) i) δI(g
1h1g2af
1c)
e) δI(g1f1h1g2ab) j) δI(g
2g1af1g
1b)
1.2) Nesta interpretação seria correto escrever, por exemplo: I(s1) =
função antecessor? Por quê?
20
2) Seja I uma interpretação tal que:
UI = {1, 2, 3, 4, 5, 6, 7, 8}
I(g1) = x+2, se x<5; 6, nos demais casos;
I(h1) = x-1, se x ≥ 5; 8, nos demais casos
I(a) = 7 I(b)=2
2.1) Dê exemplo de termo cuja denotação, segundo I, seja:
a) 5 b) 8 c) 1 d) 4
2.2) Qual a denotação, segundo I, de: a) h
1 h
1 g
1 h
1 a
b) g1 h
1 g
1 h
1b
3) Seja I uma interpretação tal que:
UI = conjunto dos países e cidades
I(h1) = função que associa a cada cidade, o país a que pertence, e, a cada
país, sua capital
I(a) = Argentina I(l) = Londres
I(b) = Brasil I(n) = Nova York
I(c) = China I(p) = Paris
I(f) = França
Determine a denotação, segundo I, de cada um dos termos abaixo:
a) h1f b) h1h1b c) h1h1n
21
Valor de verdade das sentenças atômicas
Já vimos o que é uma sentença atômica: uma fórmula atômica que não contém variáveis. Mas podemos alternativamente definir as sentenças atômicas da seguinte maneira:
α é uma sentença atômica se e só se: 1) α é uma letra sentencial; 2) Πn é um predicado de carência n, τ1,…,τn são termos fechados e α é Πn
τ1…τn ; 3) τ1 e τ2 são termos fechados e α é τ1=τ2 .
Quando associadas a interpretações, as sentenças são as expressões
destinadas a expressar declarações verdadeiras ou falsas – dizemos que uma sentença receberá, numa interpretação, um valor de verdade, o verdadeiro ou o falso. Apresentamos, agora, as regras que estabelecem como associar valores de verdade a sentenças atômicas de acordo com uma interpretação I.1
1) Se α é a letra sentencial Π, νI(α)=ℑ(Π); 2) se α é Πn τ1…τn , νI(α)=V se e só se <δI(τ1), …, δI(τn)>∈ℑ(Πn); ou seja: se e só se a n-upla formada pelas denotações de τ1,…,τn , tomadas nessa ordem, pertence à relação que I associa a Πn; 3) se α é τ1=τ2, νI(α)=V se e só se δI(τ1)=δI(τ2); ou seja, se as denotações segundo I dos termos τ1 e τ2 são o mesmo objeto.
Exemplos - Considere a interpretação abaixo:
UI = conjunto das pessoas humanas
ℑ(a) = Aristóteles; ℑ(b) = Kant; ℑ(n) = Napoleão Bonaparte; ℑ(p) = Dom
Pedro II; as demais constantes são associadas à Princesa Isabel.
ℑ(p1) = função que associa a cada primeiro ancestral humano, ele próprio; e a
cada um dos demais, o seu pai; vamos nos permitir dizer: função “pai”;
ℑ(m1) = função “mãe”, definida analogamente à função “pai”, acima.
1 A expressão “o valor de verdade de α segundo I” é abreviada por νI(α).
22
ℑ(F1) = conjunto dos filósofos; ℑ(B1) = conjunto dos brasileiros; ℑ(M1) =
conjunto das mulheres; ℑ(R2) = relação “mais velho que”; ℑ(S2) = relação
“casado com”; ℑ(C2) = relação “conterrâneo de”; ℑ(P2) = relação “professor
de”.
Todas as letras sentenciais são associadas ao V; todos os símbolos funcionais
não mencionados são associados à função “projeção do primeiro argumento”;
todos os símbolos de predicado não mencionados são associados ao conjunto
vazio.
De acordo com essa interpretação, vejamos quais são os valores de verdade de
algumas sentenças:
νI(P)=V νI(B1)=V
νI(F1a)=V, pois δI(a)=Aristóteles, ℑ(F1)=conjunto dos filósofos, e Aristóteles
pertence ao conjunto dos filósofos.
νI(B1c)=V, pois ℑ(c)=Princesa Isabel, ℑ(B1)=conjunto dos brasileiros, e a
Princesa Isabel era brasileira.
νI(B1n)=F, pois Napoleão não pertence ao conjunto dos brasileiros.
νI(C2an)=F, pois <Aristóteles, Napoleão> não pertence à relação
“conterrâneo de”.
νI(R2pq)=V, pois < Pedro II, Princesa Isabel > pertence à relação “mais
velho que”.
νI(F1p1p1q)=F, pois δI(p1p1q) ∉ ℑ(F1); ou seja, o avô paterno da Princesa
Isabel não era filósofo.
νI(p1q=p)=V, pois os termos p1q e p têm em I a mesma denotação; ou seja,
δI(p1q)=δI(p)=Pedro II.
νI(m1p1a=m1b)=F, pois a avó paterna de Aristóteles não é a mesma pessoa
que a mãe de Kant.
Como vemos, o valor de verdade de uma sentença atômica segundo uma interpretação fica perfeitamente determinado pela interpretação, uma vez que é estabelecido por meio de regras precisas formuladas em função das denotações dos termos envolvidos e dos conjuntos e relações atribuídos aos predicados pela interpretação em causa.
23
EXERCÍCIO
Sejam I e I' interpretações tais que :
UI = conjunto dos números naturais UI’ = {0,1, 2, 3, 4, 5, 6, 7, 8, 9}
I(a) = 1 I’(a) = 6
I(b) = 2 I’(b) = 7
I(c) = 0 I’(c) = 2
I(d) = 5 I’(d) = 3
I(f1) = função sucessor I(f
1) = x-1, se x é ímpar; x+1, se é par
I(g1) = função quadrado I(g
1) = 2, se x<7; 8, se x≥7
I(h1) = função cubo I’(h
1) = função identidade
I(g2) = função soma I’(g
2) = função projeção do primeiro
I(h2) = função produto I’(h
2) = função projeção do segundo
I(F1) = conjunto dos primos I’(F
1) = {1, 3, 5}
I(G1) = conjunto dos pares I’(G
1) = {2, 3, 4, 5, 6}
I(R2) = relação ser divisível por I’(R
2) = relação menor que
I(M2) = relação menor que I’(M
2) = {⟨4,3⟩, ⟨2,5⟩, ⟨7,8⟩}
Calcule o valor de verdade, segundo I e segundo I’, das sentenças abaixo:
a) F1a g) a=f1b
b) R2ab h) f1a=h2ab
c) R2ba i) h2f1bb=g1g1g2ab
d) M2af1b j) g2bb=h2bb
e) M2g1ah2ab l) F1g2h1f1bb
f) G1h2ab
24
Gramática de L (parte 2)
Retornamos à gramática para apresentar a definição de fórmula de L. Veremos que essa será também uma definição indutiva, dada em dois passos:
1º passo: especificação de um conjunto básico ou original; 2º passo: formulação das regras que permitem obter elementos mais
complexos a partir de elementos menos complexos.
Definição de fórmula
1) As fórmulas atômicas são fórmulas; 2) Se α e β são fórmulas e § é uma variável, então,
a) ¬ α é uma fórmula; b) (α ∧ β), (α ∨ β), (α → β), (α ↔ β) são fórmulas; c) ∀§α e ∃§α são fórmulas.
Dizemos que:
¬ α é a negação de α; (α ∧ β) é a conjunção de α e β; α e β são ditos os conjuntivos de (α ∧ β); (α ∨ β) é a disjunção de α e β; α e β são ditos os disjuntivos de (α ∨ β); (α → β) é a implicação de β por α; α é dito o antecedente, β o conseqüente
de (α → β); (α ↔ β) é a equivalência entre α e β.
Observação:
A implicação também é chamada condicional; e a equivalência também é chamada bi-condicional ou bi-implicação.
25
Exemplos:
Como sabemos, as expressões abaixo são fórmulas atômicas:
F2ab a = x G2f1ay1 H3x2g2aby P y = f1z
Portanto, são fórmulas. Aplicando reiteradamente as regras de obtenção de
fórmulas mais complexas, construímos as fórmulas abaixo:
¬F2ab
¬a = x ∀z (¬a = x ∧ y = f1z)
¬¬a = x ¬ (P ∨ ¬¬a = x)
¬¬¬a = x ∃y (G2f1ay1 → y = f1z)
(F2ab ∧ a = x) ∃x ∀y (P ∧ H3xg2aby)
(P ∧ H3x2g2aby) ∀x a = x
(¬a = x ∧ y = f1z) ¬ ∀x a = x
(P ∨ ¬¬a = x) ¬ ∃y (G2f1ay1 → y = f1z)
((F2ab ∧ a = x) ∨ ¬P) (P ↔ ¬y = f1z)
(¬¬¬a = x ∨ (F2ab ∧ a = x)) ∃y P
(G2f1ay1 → y = f1z) ((P ∨ ¬¬a = x) → ¬F2ab)
∀y (P ∧ H3xg2aby) etc.
As expressões da forma Q§, onde Q ∈ {∀, ∃} e § é uma variável, são ditas quantificadores. ∀§ é um quantificador universal com respeito à variável § e ∃§, um quantificador existencial com respeito a §.
Exemplos: ∀x ∃y ∀x1
Atenção: Quantificadores não são fórmulas!!!
Observação:
Na prática, os símbolos auxiliares de pontuação às vezes não são escritos, quando
pertencem a um conetivo binário que foi o último usado na composição da
fórmula; mas isso se trata apenas de um recurso de abreviação de escrita.
Teoricamente, os parênteses pertencem à fórmula mais complexa formada a partir
de duas mais simples por um dos conectivos binários [∧, ∨, →, ↔]. Assim, cada
conectivo binário é usado com um par próprio de parênteses.
26
EXERCÍCIO Classifique as expressões abaixo como termos, fórmulas ou
expressões mal formadas. No caso das fórmulas, diga se são atômicas, gerais ou moleculares.
a) x=y j) (a=a ∨ x=x)
b) F1x=F
1y l) P ∧ ¬ P
c) h2xy=f
1a m) ∃x ∃y ∃z (x=y → x=z)
d) (F2ax → (x=a ∧ ∃y F
1h1y)) n) ¬ ∃x ¬ ∃y x=y
e) ¬ f1x=h
2xy o) ¬ ¬ ∀x f
1x=x
f) (¬ P → ∃y P) p) ¬ (∀x x=f1a ↔ ∃y F
1y)
g) ∀x ∃y (x=y ∧ ∀z (z=x ∨ z=y)) q) ¬ x = ¬ y
h) ∃x y x=y r) ∃z (F2az ↔ (P ↔ ¬ P))
i) ∃a (a=x ∨ a=b)
Na leitura de uma fórmula complexa, pode ser de especial importância a identificação de cada par de parênteses e de cada conectivo binário correspondente ao par. Para tanto, podemos usar o algoritmo abaixo descrito:
Algoritmo de ordenação e emparelhamento dos parênteses numa fórmula.
1) Numere, da esquerda para a direita em ordem crescente cada um dos parênteses que abrem que ocorrem em α. Se n é o número mais alto obtido, então repita n vezes o procedimento 2, abaixo:
2) Da esquerda para a direita, procure o primeiro dos parênteses que
fecham ainda não numerados; no segmento que antecede este símbolo, procure o número mais alto ainda não usado; numere o símbolo com este número; no interior do par de parênteses com este número deve haver um único conectivo binário ainda não-numerado; numere-o também com este número.
27
Por meio deste algoritmo, procedemos a um emparelhamento dos
parênteses, assim como a uma associação de cada par deles ao conectivo binário correspondente.
Observemos que se esse algoritmo não puder ser corretamente levado
a termo, a expressão em questão não é uma fórmula. Assim, a boa aplicação desse algoritmo constitui uma condição necessária (mas não suficiente) da correção gramatical de uma fórmula que contém conectivos binários. Complexidade de uma fórmula
Como vimos, as fórmulas podem ser atômicas ou geradas a partir de
atômicas por meio da aplicação sucessiva de regras de introdução de quantificadores e/ou conectivos.
Podemos ordenar o conjunto das fórmulas de acordo com o número de
aplicações das regras de geração das mesmas, ou seja de acordo com a sua complexidade. Como cada aplicação introduz um conectivo ou um símbolo de quantificação, dizemos que a complexidade de uma fórmula α é o número de ocorrências de conectivos e/ou quantificadores em α; se n é esse número, escrevemos: Cpl [α] = n. Assim:
a) as fórmulas atômicas têm complexidade 0 (zero); e b) Cpl [¬α] = Cpl [α] + 1 c) Cpl [α * β] = Cpl [α] + Cpl [β] + 1, para * ∈ {∧, ∨, →, ↔} d) Cpl [Q§α] = Cpl [α] + 1, para Q ∈ {∀, ∃}
Se α tem complexidade maior que 0 (zero) então α é de uma das
seguintes formas: ¬β, (β1 * β2), Q§β; ou seja, o símbolo mais à esquerda de α é um dos seguintes quatro: ¬, (, ∀, ∃. Nos primeiros dois casos, dizemos que α é molecular; nos últimos dois, que α é geral.
28
Exemplos:
a) Estas três fórmulas são moleculares:
¬F1x , (P → (∀xF1x ∨ Q)), ¬∀x∃yR2xy
b) E estas são gerais:
∀x¬F1x, ∃y(H2xy ∨ R2ay), ∃x∀yR2xy
Introduzimos, agora, a noção de subfórmula de uma fórmula. Dizemos que β é subfórmula de uma fórmula α se: β é a própria α; existe uma subfórmula de α de uma das seguintes formas:
a) ¬β b) (β * β’) c) (β’ * β) d) Q§β;
onde * ∈ {∧, ∨, →, ↔} e Q ∈ {∀, ∃}. Exemplo: seja α: ∀x (¬∃y (H2xy → R2ax) ↔ F1x). As subfórmulas de α são as
seguintes:
(1) ∀x (¬∃y (H2xy → R2ax) ↔ F1x) (5) ∃y (H2xy → R2ax) (2) (¬∃y (H2xy → R2ax) ↔ F1x) (6) (H2xy → R2ax) (3) ¬∃y (H2xy → R2ax) (7) H2xy (4) F1x (8) R2ax Explicação: (1) é subfórmula de α porque é a própria α; como (1) é da forma
∀§(2), (2) é subfórmula de α; como (2) é da forma ((3) ↔ (4)), (3) e (4) são
subfórmulas de α; como (3) é da forma ¬(5), (5) é subfórmula de α; como (5) é
da forma ∃§(6), (6) é subfórmula de α; como (6) é da forma ((7) → (8)), (7) e (8)
são subfórmulas de α. Veremos, em seguida, como construir o que chamamos árvore de geração ou árvore de subfórmulas de uma fórmula α.
29
Árvore de geração ou árvore de subfórmulas de α
Seja α uma fórmula. Para construir a árvore de subfórmulas (árvore de geração) de α, procedemos da seguinte maneira:
1) Emparelhamos todos os parênteses que porventura ocorram em α, associando-os a seus respectivos conectivos binários. 2) O nó inicial da árvore é formado pela própria α; 3) Seja β a fórmula que ocorre em um nó da árvore; então: se β é atômica, o nó é dito terminal; se β não é atômica, então, se o primeiro símbolo que ocorre em β é: 3.1) ¬ : adicionamos mais um nó com a expressão que se segue; 3.2) ( : acrescentamos dois novos nós com as expressões que se
encontram entre ‘ ( ’ e o conectivo * e entre * e ‘ ) ’ — ‘ ( ’ , *, ‘ ) ’ são associados ao mesmo número. 3.3) Q : acrescentamos um novo nó com o que se segue à variável § que
está imediatamente depois de Q.
A árvore estará terminada após n passos, onde n é a complexidade da fórmula α. Observe-se que as condições 3.1), 3.2) e 3.3) são regras de decomposição que correspondem exatamente ao inverso das regras de complexificação da definição de fórmula. Exemplo: Árvore de geração de ∀x (F1x → ¬(G1x ∨ P))
Os nós terminais da árvore são: F1x, G1x, P.
30
Outro exemplo: Árvore de ¬((∃x a = x ∨ R2ax) ∧ ∀y ¬(a = y → R2xy))
Note-se que uma expressão é uma fórmula se e só se tiver uma árvore de
subfórmulas assim construída, contendo fórmulas atômicas nos seus terminais.
Note-se, ainda, que a árvore de uma dada fórmula α tem uma certa
configuração gráfica que corresponde à estrutura gramatical de α. Assim a árvore
do exemplo acima tem a seguinte configuração:
1
2
3 4
5 6 7
8 9
10 11
Nessa árvore, os nós (8), (6), (10) e (11) são nós terminais. Como em qualquer
árvore, (1) é o nó inicial.
Um ramo de uma árvore é uma seqüência de nós que vai do nó inicial a um nó terminal. Dessa forma, uma árvore terá tantos ramos quantos sejam os seus terminais. No exemplo, os quatro ramos são:
a) (1), (2), (3), (5), (8) b) (1), (2), (3), (6) c) (1), (2), (4), (7), (9), (10) d) (1), (2), (4), (7), (9), (11)
31
Observemos, ainda, que, se uma ocorrência de β e uma ocorrência de β’ estiverem num mesmo ramo, β’ é subfórmula de β se e só se a ocorrência de β preceder a de β’ no ramo.
Assim, no exemplo anterior, observa-se claramente que: (8) é subfórmula de (5), mas não de (6); (5) e (6) são subfórmulas de (3), mas (7) não é subfórmula de (3); e todas as onze fórmulas são subfórmula de (1). EXERCÍCIO: Construa a árvore de geração de cada uma das fórmulas abaixo:
a) ∀x (F1x → G
1x)
b) (∃x (F1x ∧ G
1x) → ∀y Ρ
2xy)
c) ¬ (∀x F2xy → (∃z (H
2zx ∧ G
2xz) ↔ ¬ G
2xz))
d) ∀x (¬∃y (H2xy → F
2h1ab) ∨ (Q → ¬ ¬ (F
2xz ∧ H
2ag
2xb)))
Árvores moleculares Um outro tipo de árvore que pode ser definida é a árvore molecular de
uma fórmula. A árvore molecular difere da árvore de subfórmula por não admitir decomposição por quantificadores; assim, seus terminais serão atômicos ou gerais.
A definição da construção de uma árvore molecular pode ser obtida a
partir da definição da construção de árvore de subfórmulas, eliminando-se a cláusula 3.3. Portanto, é a seguinte a árvore molecular de ¬((∃x a = x ∨ R2ax) ∧ ∀y¬(a = y → R2yx)):
E a árvore molecular de ∀x (F1x → ¬(G1x ∨ P)) tem apenas um nó,
constando, assim, apenas dessa mesma fórmula.
32
EXERCÍCIO: Construa a árvore molecular de:
a) ((∀x F1x → F
1a) ∨ ∀x (F
1a → F
1x))
b) ((F1a ↔ G
1b) → ¬ (¬ ∀x F
1x → (F
1a ∨ G
1b)))
c) (((F1a ∧ ¬ ∀x G
1x) ∨ (G
1a ∧ ∀x G
1x)) → ∀x (G
1a → F
1x))
d)(¬ (∀x ∀y R2xy ↔ ∀x (F
1a → F
1x)) → (F
1a ∨ ¬ ∀x ∀y R
2xy))
Vamos agora analisar os dois distintos modos segundo os quais uma variável pode ocorrer numa fórmula. Ocorrência ligada ou livre de uma variável numa fórmula
Dizemos que uma ocorrência de uma variável § numa fórmula α é ligada se ela se dá numa subfórmula de α da forma ∀§β ou ∃§β. Se a ocorrência de § em α não é ligada, ela se diz livre. Exemplos: Na fórmula ‘(∀x(F2xy → G1x) ∨ ∃yR2yx)’, a variável ‘x’ tem quatro
ocorrências. As três primeiras são ligadas porque se dão dentro da subfórmula
‘∀x(F2xy → G1x)’ e a última é livre; a variável ‘y’ tem três ocorrências; a primeira é
livre, as demais são ligadas, pois se dão dentro da subfórmula ‘∃yR2yx’.
Observemos que uma ocorrência de uma variável § numa fórmula α é
ligada (ou livre) se e somente se ela for ligada (ou livre) no respectivo terminal da árvore molecular de α.
Analisemos mais um exemplo:
As duas primeiras ocorrências de ‘x’ se dão no terminal ‘∀x(R2xa ∧ F1y)’;
portanto, são ligadas; a última se dá no terminal ‘∃z(R2xz ∨ ∀yG1y)’; portanto, é
livre. A primeira ocorrência de ‘y’ se dá em ‘∀x(R2xa ∧ F1y)’; assim, é livre; as
demais se dão em ‘∃z(R2xz ∨ ∀yG1y)’; ora essa fórmula tem a subfórmula ‘∀yG1y’,
onde se dão as ocorrências; então elas são ligadas. Claramente, as ocorrências de
‘z’ são todas ligadas.
33
EXERCÍCIO:
Nas fórmulas abaixo, classifique as ocorrências das variáveis como livres ou ligadas.
a) ∀x (F2xy → ∃y (y=a → (∀z F
1z ∨ h
2zy=x)))
b) (¬ h2xy=a ∨ ∀z (∃y h
2yz=x → ∃y z=y))
c) ¬((∃x a = x ∨ R2ax) ∧ ∀y(a = y → R2yx)): Sentenças de L
Podemos, agora, definir o conceito de sentença de L Uma sentença de L é uma fórmula de L onde nenhuma ocorrência de
variável é livre. Toda sentença é também chamada de fórmula fechada.
Observação
Nas fórmulas atômicas todas as ocorrências de variáveis são livres. Assim, as
sentenças atômicas são fórmulas atômicas que não contêm variáveis. As
ocorrências ligadas de variáveis só aparecem em fórmulas complexas que
contêm quantificadores.
Exemplos de sentenças:
P F1a R2ab ¬R2cb
∀xF1x ∃x(F1x ∨ G1x) ∀x∃yR2xy (∀xF1x → F1a)
(P ∧ Q) (∃xFx → ∀y(∃zR2yz → ∃wR2wy)) ∀z(P ∧ Q)
Uma relação importante entre as sentenças de L e suas árvores
moleculares é a seguinte: uma fórmula α é uma sentença se e somente se todos os terminais de sua árvore molecular são sentenças. Essa propriedade decorre claramente do fato de que na decomposição molecular nenhum quantificador é eliminado.
34
EXERCÍCIO:
1) Seja α a fórmula ¬ ∃x (∀y (F2af
1y ∨ ¬ ∃z f
1z=a) ↔ H
1f1a). Indique:
a) os termos fechados que ocorrem em α; b) as subfórmulas atômicas que ocorrem em α; c) as subfórmulas de α que são sentenças gerais.
2) Identifique, entre as expressões abaixo, as fórmulas; a seguir, (i) classifique-as como atômicas, gerais ou moleculares, e (ii) identifique as que são sentenças.
a) F1x m) F1x=F1y b) F1xa n) (∃x ∀y G2xy → ∀y ∃x G2xy) c) G2af1b o) (∀x F1x ↔ ¬ F1x) d) ∀x F1x p) ∀x (F1x ↔ ¬ F1x) e) ∀x F1a q) (¬ P ∨ ∀x P) f) ¬ ∀x F1x ∨ F1a r) (∀x F1x) ∧ (∀x G1x) g) (∀x F1x → F1a) s) (x=y → f1x=f1y) h) ¬ (x=y) t) (h2xy=z → ¬ (∀x F1x ∨ ∃y y=z)) i) ∀x F1y u) ¬ ∀x ∀y (h2xf1y=x ∧ ¬ H2yx) j) (h1x ∨ g1y) v) ¬ ∀x ¬ ¬ ∀y (F2xy ↔ f1x=h2yx) l) ∀x (x=y ∨ f1x=z) x) 5+4=9
Componentes sentenciais básicos de uma sentença Seja α uma sentença. Dizemos que β é um componente básico de α se β ocorre pelo menos uma vez como terminal da árvore molecular de α. Exemplo:
Tomemos a árvore molecular de (∃xF1x → (¬∀yR2ya ∨ (¬∃xF1x ∨ F1a)))
Os componentes básicos são: ∃xF1x, ∀yR2ya, F1a
35
Tomemos, como novo exemplo, a árvore molecular de
((∀x(G1a ∧ F1x) → ∃y(¬F1a ∨ G1y)) ↔ (∃yG1y → (F1a ∨ ∀xG1x))).
Os componentes básicos são: ∀x(G1a ∧ F1x), ∃y(¬F1a ∨ G1y), ∃yG1y, F1a,
∀xG1x.
Observe-se que, embora a sentença ‘G1a’ seja uma subfórmula de α que é
uma sentença, ‘G1a’ não é um componente básico de α, pois não ocorre nem uma
vez como terminal da árvore molecular de α.
Sentenças CS
Seja α uma sentença formada apenas com letras sentenciais e/ou conectivos. Então α é dita uma fórmula CS ou uma sentença CS. Nesse caso, a noção de fórmula e de sentença coincidem, uma vez que não pode haver variáveis em α. A expressão ‘CS’ abrevia ‘cálculo sentencial’. O cálculo sentencial é um subcálculo do Cálculo de Predicados e será estudado proximamente.
As sentenças CS foram aqui definidas a partir das fórmulas do cálculo
dos predicados. No entanto, podemos dar diretamente uma definição indutiva para elas, como se segue:
1) As letras sentenciais são sentenças CS; 2) Se α e β são sentenças CS, então
a) ¬α é uma sentença CS; b) (α * β) é uma sentença CS, para * ∈ {∧, ∨, →, ↔}.
36
Seja, agora, α uma sentença qualquer. Dizemos que β é uma CS-associada de α se β pode ser obtida a partir de α pela substituição de cada componente básico de α por uma (distinta) letra sentencial. Exemplos:
1) Seja α a sentença ((¬∀xF1x → ∃y∀xR2xy) ∨ (∀xF1x ∧ R2ab)).
Seus componentes básicos são: ∀xF1x, ∃y∀xR2xy, R2ab.
Substituindo-os pelas letras sentenciais: P, Q, R, obtemos a CS-associada:
((¬P → Q) ∨ (P ∧ R)).
Obviamente, se houvéssemos escolhido as letras A, B, C, obteríamos uma outra
CS-associada: ((¬A → B) ∨ (A ∧ C)).
2) Seja α: ∀x((F1x ∧ G1x) → ∃yR2xy). Como α é seu único componente básico,
qualquer letra sentencial é uma CS-associada de α.
3) Seja α: ¬(∀x(F1x → (G1a ∧ H1a)) ↔ (¬G1a → (G1a ∨ ∃xF1x))). Os componentes
básicos de α são: ∀x(F1x → (G1a ∧ H1a)), G1a, ∃xF1x. Então, uma CS-associada de
α é a sentença: ¬(P ↔ (¬Q → (Q ∨ R))), por exemplo.
Observemos que se β é CS-associada de α, as árvores moleculares de α e β têm a mesma estrutura. De fato, podemos dizer que β exibe a estrutura molecular de α.
EXERCÍCIO:
Para cada uma das sentenças abaixo:
1) construa sua árvore de composição molecular; 2) identifique seus componentes sentenciais básicos; 3) construa uma CS-associada. a) ((∀x F
1x → F
1a) ∨ ∀x (F
1a → F
1x))
b) ((F1a ↔ G
1b) → ¬ (¬ ∀x F
1x → (F
1a ∨ G
1b)))
c) (((F1a ∧ ¬ ∀x G
1x) ∨ (G
1a ∧ ∀x G
1x)) → ∀x (G
1a → F
1x))
d) (¬ (∀x ∀y R2xy ↔ ∀x (F
1a → F
1x)) → (F
1a ∨ ¬ ∀x ∀y R
2xy))
e) (∀x F1x ∨ ∀x ¬ F
1x)
f) ((∀x ∀y R2xy ∧ ¬ ∃x (F
1x ∧ G
1x)) → (∀x ∀y R
2xy →∃x F
1x))
g) ((∃x F1x → ¬ (R
2ab ∨ ∀x F
1x)) → (R
2ab → (¬ ∃x F
1x ∨ ¬ ∀x F
1x)))
37
Semântica Proposicional
Vamos, por um momento, deixar de lado a linguagem L para estudarmos a semântica de seu fragmento proposicional, i.e., a semântica clássica do conjunto das sentenças CS.
Seja, então, S o conjunto das sentenças CS; seja W2 um conjunto de
dois objetos distintos, doravante designados por V e F e chamados, respectivamente, o Verdadeiro e o Falso. Uma valoração bivalente é uma função qualquer do conjunto S no conjunto {V, F}. Assim, a função que associa o V a todas as sentenças de S é uma valoração bivalente; assim como aquela que associa o V a todas as atômicas e F às demais sentenças; ou, ainda, a que associa o V a todas as sentenças nas quais ‘P’ ocorre e F às demais – para apresentar apenas três exemplos de valoração bivalente.
Observação: Neste livro estudamos a chamada lógica simbólica clássica, que
trabalha apenas com um grupo especial de valorações bivalentes. Outras lógicas,
ditas polivalentes, podem considerar outros tipos de valorações e admitir um
conjunto maior, finito ou até mesmo infinito, de valores de verdade.
Podemos agora definir as valorações bivalentes aceitas pela
semântica proposicional clássica: as valorações booleanas. Uma valoração booleana é uma valoração bivalente ν tal que, para quaisquer α, β ∈ S, temos que:
a) ν [¬α] = V se e só se ν [α] = F b) ν [(α ∧ β)] = V se e só se ν [α] = ν [β] = V c) ν [(α ∨ β)] = V se e só se ν [α] = V ou ν [β] = V d) ν [(α → β)] = V se e só se ν [α] = F ou ν [β] = V e) ν [(α ↔ β)] = V se e só se ν [α] = ν [β].
Como vemos, as valorações booleanas atribuem arbitrariamente valores às letras sentenciais, enquanto os valores atribuídos às sentenças complexas são univocamente determinados pelos valores atribuídos aos componentes mais simples. Em vista disso, uma valoração booleana é totalmente determinada pelos valores que atribui às letras sentenciais de S. Isso se deve ao fato de que, em vista da definição acima, cada uma das
38
cinco formas de fórmulas complexas é definida, por meio de condições necessárias e suficientes, como uma função (ou operação) cujos argumentos e valores estão em {V, F}. Em outras palavras, cada um dos conectivos é definido como a expressão de uma função de verdade
bivalente.
Observação: A definição de todos os conectivos como funções de verdade
bivalentes é característica da lógica proposicional clássica. Outras lógicas podem
definir alguns de seus conectivos como relações de verdade que não dependem
funcionalmente apenas dos valores de verdade de suas subfórmulas. Assim, já
podemos destacar duas características básicas da lógica proposicional clássica: 1)
trabalha apenas com dois valores de verdade; 2) seus conectivos expressam
funções de verdade.
Assim, a negação representa a função de {V, F} em {V, F} definida pela tabela:
Argumento Valor α ¬α
V F
F V
Os quatro conectivos binários expressam funções de {V, F}2 em {V, F}
definidas pelas tabelas abaixo:
Argumentos Valores
α β (α ∧ β) (α ∨ β) (α → β) (α ↔ β) V V V V V V
V F F V F F
F V F V V F
F F F F V V
Vamos, neste momento, abrir espaço para uma pequena incursão na teoria das funções de verdade. De modo geral, uma função de verdade n-ária é uma operação n-ária no conjunto {V, F} ou seja, uma função f: {V, F}n ⇒ {V, F}.
39
Podemos verificar que há quatro funções de verdade unárias (abaixo indicadas por f11, f21, f31, f41):
f11 f2
1 f3
1 f4
1
V V V V V F V F
F V F F F V F F
(tautologia) (identidade) (negação) (contradição)
Essas quatro funções recebem os nomes que aparecem acima entre parênteses. Podemos observar que, pelo que foi estabelecido anteriormente, nas valorações booleanas o conectivo ‘¬’ expressa a função f31, acima.
As funções de verdade binárias são dezesseis, as ternárias são 256;
de modo geral, o número das funções de verdade n-árias é dado por 22n.
Vamos relacionar, em seguida, as 16 funções de verdade binárias. Para economizar espaço, usaremos uma mesma tabela, com quatro linhas, uma para cada combinação de valores dos argumentos e dezesseis colunas, uma para cada função binária, aqui denotadas por f12 ... f162:
f12 f2
2 f3
2 f4
2 f5
2 f6
2 f7
2 f8
2 f9
2 f10
2 f11
2 f12
2 f13
2 f14
2 f15
2 f16
2
V V V V V V F V V V F F F V F F F F
V F V V V F V V F F V V F F V F F F
F V V V F V V F V F V F V F F V F F
F F V F V V V F F V F V V F F F V F
Podemos observar que:
‘∧‘ expressa a função f122 ‘∨‘ expressa a função f22 ‘→‘ expressa a função f42 ‘↔‘ expressa a função f82
Entre as funções unárias e binárias, f31, f2
2, f42, f8
2, e f122 são as
funções diretamente expressáveis na linguagem que adotamos aqui. As
40
outras, no entanto, são também expressáveis por meio de composição, a partir dessas cinco. Assim, por exemplo, a função f5
2 é obtida pela composição de f31 com f122, como se vê na tabela abaixo:
f122 f3
1 f122
V V V F
V F F V
F V F V
F F F V
Na verdade, é possível mostrar que qualquer função de verdade n-ária
pode ser obtida por meio de composição reiterada, a partir de algumas funções unárias e binárias, tomadas como primitivas. Um resultado conhecido é que, com a função f52, é possível compor qualquer função n-ária de verdade; e o mesmo vale para a função f152. Também podemos obter todas as funções de verdade usando os elementos do conjunto {f3
1, f122}; o mesmo vale pare os conjuntos {f31, f22} e {f3
1, f42}. Como podemos expressar f31, f122, f22, f42 na nossa linguagem, para cada função de verdade n-ária, teremos na nossa linguagem uma fórmula, contendo n letras sentencias, que expressa essa função.
Observação: Quando uma linguagem tem a capacidade de expressar
qualquer função de verdade, diz-se que ela é funcionalmente completa. Uma
demonstração da completude funcional da nossa linguagem pode ser encontrada
no Anexo I.
Para exemplificar, sejam α, β, γ fórmulas quaisquer. Então:
1) As quatro funções unárias podem ser expressas pelas fórmulas (α ∨ ¬α),
α, ¬α, (α ∧ ¬α), como mostra a tabela abaixo:
f21 f3
1 f11 f4
1 α ¬α (α ∨ ¬α) (α ∧ ¬α) V F V F
F V V F
2) a) A função f12 pode ser expressa por ((α ∨ ¬α) ∨ (β ∨ ¬β));
41
b) As funções f122, f132, f14
2 e f152 podem ser expressas por (α ∧ β),
(α ∧ ¬β), (¬α ∧ β), (¬α ∧ ¬β), como mostra a tabela:
f122 f13
2 f142 f15
2
α β ¬α ¬β (α∧β) (α∧¬β) (¬α∧β) (¬α∧¬β) V V F F V F F F
V F F V F V F F
F V V F F F V F
F F V V F F F V
c) As funções f62, f7
2, f82, f9
2, f102, f11
2 podem assim ser expressas:
d) As funções f22, f3
2, f42 e f5
2 podem ser expressas pelas negações das
fórmulas que expressem f152, f14
2, f132, f12
2, respectivamente.
e) A função f162 pode ser expressa pela negação de uma fórmula que
expresse f12.
3) Não vamos aqui examinar cada uma das funções n-árias para n > 2.
Apenas como exemplo, consideremos duas funções ternárias, g e h, tais
que:
g recebe o valor V para a trinca {V, F, V} e recebe o F nos demais casos;
h recebe V para {V, F, V} e para {F, F, F} e recebe F nos demais casos.
Então ((α ∧ ¬β) ∧ γ) e (((α ∧ ¬β) ∧ γ) ∨ ((¬α ∧ ¬β) ∧ ¬γ)) expressam,
respectivamente, as funções g e h, como se vê na tabela abaixo:
g h
α β γ ¬α ¬β ¬γ (α∧¬β) (¬α∧¬β) ((α∧¬β)∧γ) ((¬α∧¬β)∧¬γ) (((α∧¬β)∧γ)∨((¬α∧¬β)∧¬γ))
V V V F F F F F F F F
V V F F F V F F F F F
V F V F V F V F V F V
V F F F V V V F F F F
F V V V F F F F F F F
F V F V F V F F F F F
F F V V V F F V F F F
F F F V V V F V F V V
f62 f7
2 f82 f9
2 f102 f11
2
α β ¬α ¬β (α∧(β∨¬β)) ((α∨¬α)∧β)) (α↔β) ¬(α↔β) ((α∨¬α)∧¬β) (¬α∧(β∨¬β)) V V F F V V V F F F
V F F V V F F V V F
F V V F F V F V F V
F F V V F F V F V V
42
Observação: Nos exemplos anteriores, as fórmulas apontadas como
expressões das funções indicadas eram apenas algumas entre classes de
fórmulas que cumprem o mesmo papel. Assim, a função f122, por exemplo,
pode ser expressa por uma infinidade de diferentes fórmulas, entre as quais
figuram: (α ∧ β), ¬(¬α ∨ ¬β), ¬(α → ¬β) etc..
Nossa linguagem dispõe, então, de cinco conectivos que expressam diretamente: uma função unária, f31, e quatro funções binárias, f22, f42, f82, f12
2. Mostremos, agora, que, embora úteis, alguns desses conectivos não seriam, em princípio, necessários. Para isso, sejam:
1) L¬∧: a linguagem que contém letras sentenciais e os conectivos ‘¬‘,
‘∧‘; 2) L¬∨: a linguagem que contém letras sentenciais e os conectivos ‘¬‘,
‘∨‘; 3) L¬→: a linguagem que contém letras sentenciais e os conectivos ‘¬‘,
‘→‘. Mostramos, a seguir, como, em cada uma dessas linguagens,
podemos definir os demais conectivos:
1) Em L ¬∧, (α ∨ β) =df ¬(¬α ∧ ¬β) (α → β) =df ¬(α ∧ ¬β) (α ↔ β) =df (¬(¬α ∧ β) ∧ ¬(α ∧ ¬β))
2) Em L ¬∨, (α ∧ β) =df ¬(¬α ∨ ¬β) (α → β) =df (¬α ∨ β) (α ↔ β) =df ¬(¬(¬α ∨ β) ∨ ¬(α ∨ ¬β))
3) Em L ¬→, (α ∧ β) =df ¬(α → ¬β) (α ∨ β) =df (¬α → β) (α ↔ β) =df ¬((α → β) → ¬(¬α → ¬β))
A razão pela qual usamos os cinco conectivos está ligada ao fato de
que com eles abreviamos muitas fórmulas (veja-se por exemplo o comprimento das definições de uma bi-condicional nas linguagens acima!).
43
Pode, assim, ser mais cômodo trabalhar com um número maior de conectivos. No entanto, em vez de tomar como primitivos os cinco conectivos - ou seja, em vez de adotar a linguagem L ¬,∧,∨,→,↔, poderíamos ter preferido trabalhar com L ¬∧, com L ¬∨ ou com L ¬→.
Retornemos às valorações booleanas. Seja α uma fórmula CS com n
letras sentenciais, Π1,..., Πn. Então: 1) Como todos os conectivos se comportam como funções de verdade,
se conhecermos os valores que uma valoração booleana atribui às letras sentenciais Π1,...,Πn, podemos calcular o valor que ela atribui a cada uma das fórmulas e conectivos; conseqüentemente, podemos calcular o valor de α nessa valoração.
Exemplo: Seja α = (P → (¬Q ∨ R)) e seja ν a valoração que atribui V
a ‘P’ e a ‘Q’ e F a ‘R’.
P Q R ¬Q (¬Q ∨ R) (P → (¬Q ∨ R))
ν V V F F F F
2) Notemos que esse será também o comportamento de qualquer outra valoração ν’ que concorde com ν nas letras sentenciais que ocorrem em α. Podemos, então, enunciar um princípio geral: Para quaisquer valorações booleanas, νννν, νννν’, se elas concordam nos valores que atribuem a cada uma das letras sentenciais que ocorrem em uma sentença CS αααα, então elas concordam no valor que atribuem a αααα.
3) Ora, toda fórmula CS α tem um número finito de letras sentenciais,
digamos, n. Como há apenas dois valores de verdade, existem exatamente 2n combinações de {V, F} em grupos de n, ou seja, há exatamente 2n n-uplas formadas com os valores do conjunto {V, F}. Se quisermos, portanto, estudar o comportamento de uma fórmula no conjunto de todas as valorações booleanas, será suficiente considerarmos 2n valorações que diferem entre si por pelo menos um dos valores atribuídos a uma letra sentencial de α - pois qualquer valoração booleana concordará nas letras sentenciais de α com alguma dessas 2n valorações consideradas.
44
Por exemplo:
Tomemos α = (P ↔ (Q ∨ ¬P)). Como temos duas letras sentenciais
envolvidas, há 22 possibilidades distintas de atribuir os elementos de {V,
F} aos elementos de {P, Q}, esquematizados abaixo:
P Q
1 V V
2 V F
3 F V
4 F F
Cada uma das linhas, de 1 a 4, representa uma atribuição possível dos
valores de {V, F} aos elementos de {P, Q}.
Com respeito ao conjunto {P, Q}, as valorações booleanas dividem-se
portanto em quatro grupos (ou classes de equivalência em {P, Q}), cada
um deles representado por uma das linhas da tabela acima. Nela, a linha 1
representa todas as valorações que atribuem V a ‘P’ e a ‘Q’; a linha 2,
todas as valorações que atribuem V a ‘P’ e F a ‘Q’; e assim por diante.
4) Podemos, então, definir o que é uma tabela de verdade para uma fórmula α. Se todas as letras sentenciais de uma fórmula CS α estão no conjunto {Π1, ..., Πn}, uma tabela de verdade para α é uma construção contendo 1 + 2n linhas tais que: a primeira linha leva a numeração 0 (zero) e contém as letras sentenciais Π1, ..., Πn; essa linha é dita o cabeçalho da tabela. As demais linhas, numeradas de 1 a 2n, contêm as 2n n-uplas que podem ser formadas com os elementos do conjunto {V, F}, obtidas pelo seguinte método:
• a coluna correspondente a Π1, é preenchida por 2n-1
ocorrências de ‘V’ seguidas de 2n-1 ocorrências de ‘F’; • a coluna correspondente a Π2, por 2n-2 ocorrências de ‘V’,
seguidas por 2n-2 ocorrências de ‘F’, por 2n-2 ocorrências de ‘V’ e por 2n-2 ocorrências de ‘F’.
• a coluna correspondente a Πn, por 2n-n ocorrências de ‘V’,
seguidas por 2n-n ocorrências de ‘F’, seguidas por 2n-n
45
ocorrências de ‘V’, … , seguidas por 2n-n ocorrências de ‘F’; ou seja, essa coluna é formada por um ‘V’, seguido por um ‘F’, por outro ‘V’, por outro ‘F’,..., até a linha de número 2n
que conterá um ‘F’.
O procedimento acima poderia ainda ser resumido pela seguinte receita: para obter a coluna da i-ésima letra sentencial, Πi, onde 1 ≤ i ≤ n, preenchemos a coluna com 2n-i ocorrências de ‘V’ seguidas por 2n-i ocorrências de ‘F’; aplicando 2i-1 vezes este procedimento, preencheremos as 2n vagas da coluna.
Assim, por exemplo, se as letras sentenciais são os elementos do conjunto
{P, Q, R}, construímos:
0 P Q R
1 V V V
2 V V F
3 V F V
4 V F F
5 F V V
6 F V F
7 F F V
8 F F F
A linha 0 é o cabeçalho da tabela.
A coluna 1 foi obtida por 21-1 (i.e. 20, i.e. 1) aplicações do procedimento:
escrever 23-1 vezes o ‘V’ e 23-1 vezes o ‘F’.
A coluna 2 foi obtida por 22-1 (i.e. 21, i.e. 2) aplicações do procedimento:
escrever 23-2 vezes o ‘V’ e 23-2 o ‘F’.
A coluna de ‘R’ foi obtida por 23-1 (i.e. 22, i.e. 4) aplicações do
procedimento: escrever 23-3 (i.e. 1) vezes o valor ‘V’ e 23-3 vezes o valor
‘F’.
46
5) Numa tabela de verdade para α podemos, então, calcular o comportamento de α em todas as valorações booleanas. Para tanto, basta construir a tabela e ir estendendo o cabeçalho até que todas as subfórmulas de α nele constem. Em seguida, procedemos ao cálculo do comportamento das subfórmulas de α segundo as regras para os conectivos definidas pelas valorações booleanas.
Exemplo: Seja α a fórmula (((¬P ∧ Q) → (S → R)) ∨ Q).
Analogamente, seja Γ um conjunto finito de fórmulas CS e T uma tabela de verdade que contém em seu cabeçalho todas as letras sentenciais que ocorrem nos elementos de Γ. Então dizemos que T é uma tabela de verdade adequada para Γ ou, simplesmente, que T é uma tabela para Γ.
EXERCÍCIOS:
1) Construa, para cada um dos conjuntos de fórmulas abaixo, uma tabela adequada para ele.
a) {P ,Q, ¬(P → (P↔Q)) }
b) {(P ↔ (Q ∧ R)), (S v ¬R), (P ∧ Q) }
2) Às vezes dizemos que duas fórmulas CS são equivalentes se elas expressam a mesma função de verdade. Segue-se daí que ‘P’e ‘Q’ são fórmulas equivalentes? Explique a questão e as dificuldades envolvidas.
0 P Q R S ¬P (¬P ∧ Q) (S → R) ((¬P ∧ Q) → (S → R)) (((¬P ∧ Q) → (S → R)) ∨ Q)
1 V V V V F F V V V
2 V V V F F F V V V
3 V V F V F F F V V
4 V V F F F F V V V
5 V F V V F F V V V
6 V F V F F F V V V
7 V F F V F F F V V
8 V F F F F F V V V
9 F V V V V V V V V
10 F V V F V V V V V
11 F V F V V V F F V
12 F V F F V V V V V
13 F F V V V F V V V
14 F F V F V F V V V
15 F F F V V F F V V
16 F F F F V F V V V
47
Introduziremos, a seguir, quatro conceitos básicos para o cálculo sentencial: os conceitos de modelo verifuncional de um conjunto de fórmulas CS; o de tautologia; o de consistência verifuncional; e o de conseqüência tautológica.
Conceitos fundamentais da semântica proposicional
Seja Γ um conjunto de fórmulas CS e α uma sentença CS. 1) Dizemos que uma valoração booleana ν é um modelo
verifuncional de Γ se ν atribui o valor de verdade V a todos os elementos de Γ.
Exemplo:
Seja Γ o conjunto {(P ↔ (¬Q ∧ R)), (P ∨ Q), (S → ¬R)}. Então, qualquer
valoração booleana que dê o valor V a ‘P’ e a ‘R’, e o valor F a ‘Q’ e a ‘S’ é
um modelo verifuncional de Γ, como se pode ver no cálculo abaixo:
P Q R S ¬Q ¬R (¬Q ∧ R) (P ↔ (¬Q ∧ R)) (P ∨ Q) (S → ¬R)
V F V F V F V V V V
2) Dizemos que um conjunto de fórmulas CS Γ é verifuncionalmente consistente se Γ tiver pelo menos um modelo verifuncional. Assim, o conjunto Γ do exemplo acima é um conjunto verifuncionalmente consistente. Observe-se que há conjuntos que não são verifuncionalmente consistentes, i.e. que não têm nenhum modelo, i.e.: não há nenhuma valoração booleana que atribua o valor V a cada um dos seus elementos Exemplos:
O conjunto {P, ¬P} não é verifuncionalmente consistente, pois nenhuma
valoração booleana atribui V a ‘P’ e V a ‘¬P’. Analogamente, o conjunto {P,
48
(P → ¬Q), Q} não é verifuncionalmente consistente, pois toda valoração
booleana que atribui V a ‘P’ e a ‘Q’ atribui F a ‘(P → ¬Q)’.
Se o conjunto Γ é finito, podemos usar uma tabela de verdade adequada para Γ com o intuito de testar a consistência verifuncional de Γ: Γ será consistente se houver uma mesma linha da tabela na qual todos os elementos de Γ recebem V; uma linha como essa representa uma classe de equivalência de valorações booleanas que são modelos de Γ.
Tomemos, por exemplo, o conjunto {(P ∨ Q), (Q → ¬R), (¬P → R)}:
0 P Q R ¬P ¬R (P ∨ Q) (Q → ¬R) (¬P → R)
1 V V V F F V F V
2 V V F F V V V V x
3 V F V F F V V V x
4 V F F F V V V V x
5 F V V V F V F V
6 F V F V V V V F
7 F F V V F F V V
8 F F F V V F V F
Como vemos, as linhas 2, 3, 4 satisfazem a condição estipulada; assim,
cada uma delas representa uma classe de modelos verifuncionais de Γ.
Dizemos, ainda, que uma sentença α é verifuncionalmente compatível com o conjunto de sentenças Γ, se α é verdadeira em algum modelo de Γ, ou seja, se o conjunto Γ ∪ {α} é verifuncionalmente consistente.
49
Observações:
a) Para qualquer valoração booleana ν, a sentença abaixo é verdadeira: para
todo α ∈ ∅, ν (α) = V. Ou seja, qualquer valoração booleana é modelo
verifuncional do conjunto vazio. Assim, ∅ é um conjunto consistente
verifuncionalmente.
b) O conjunto de todas as sentenças CS é um conjunto inconsistente, uma
vez que contém fórmulas e suas negações.
3) Dizemos que uma fórmula CS é uma tautologia se α recebe o
valor de verdade V em todas as valorações booleanas. Assim, α é uma tautologia se e só se a coluna correspondente a α, numa tabela de verdade que contenha todas as letras sentenciais de α, é formada apenas por ocorrências de ‘V’.
Há um resultado simples e importante concernindo às tautologias: seja α uma fórmula, Π uma letra sentencial que ocorre em α e seja α’ a fórmula que resulta de α pela substituição de todas as ocorrências de Π por ocorrências de β (indicamos essa última condição escrevendo: α’ = αΠ/β); nesse caso: se α for uma tautologia, então α’ também será uma tautologia. É fácil compreender por que essa afirmação vale. Se α’ não fosse uma tautologia, existiria uma valoração booleana ν’ que falsificaria α’; seja agora ν a valoração booleana que atribui a Π o valor que ν’ atribui a β e que concorda com ν’ nos valores atribuídos às demais letras sentenciais de α; então, ν(α) = ν(α’) = F. Assim, se existe ν’ tal que ν’(α’) = F, então existe ν tal que ν(α) = F. Portanto, se não existe ν tal que ν(α) = F, também não existe ν’ tal que ν’(α’) = F, ou seja: se α é tautologia, então α’ também é tautologia. Por causa do resultado que acabamos de expor, em vez de dar exemplos de fórmulas que são tautologias, costumamos apresentar esquemas de fórmulas tautológicas, i.e. esquemas cujas especificações são, todas, tautologias. Assim, por exemplo, o esquema ‘(α ∨ ¬α)’ é um esquema tautológico: todas as fórmulas da forma desse esquema, i.e. todas as fórmulas obtidas pela especificação da fórmula α, como ‘(P ∨ ¬P)’, ((P ∧ Q) ∨ ¬(P ∧ Q)) etc., são tautologias.
50
Há infinitos esquemas tautológicos. Alguns deles, no entanto, por serem simples e representarem leis lógicas fundamentais, recebem nomes especiais. Vamos apresentar três grupos de esquemas tautológicos.
Grupo I: Equivalências Tautológicas
(¬¬α ↔ α) Dupla negação
((α * β) ↔ (β * α)) Comutação para * ∈ {∧, ∨, ↔}
(((α * β) * γ) ↔ (α * (β * γ)) Associação para * ∈ {∧, ∨, ↔}
((α → β) ↔ (¬β → ¬α)) Contraposição
(¬(α * β) ↔ (¬ α ° ¬β)) de Morgan, onde se * = ∧ então ° = ∨
(¬(¬α * ¬β) ↔ (α ° β)) e se * = ∨ então ° = ∧
((α ° (β * γ)) ↔ ((α ° β) * (α ° γ))) Distributiva, onde se * = ∧ então ° = ∨
se * = ∨ então ° = ∧
((α * α) ↔ α) Contração onde * ∈ {∧, ∨}
(((α ∧ β) → γ) ↔ (α → (β → γ))) Exportação/Importação
((α → β) ↔ ¬(α ∧ ¬β)) Definição da implicação em L ¬∧
((α → β) ↔ (¬ α ∨ β)) Definição da implicação em L ¬∨
((α ∧ β) ↔ ¬(α → ¬β)) Definição da conjunção em L ¬→
((α ∨ β) ↔ (¬α → β)) Definição da disjunção em L ¬→
((α * (α * β)) ↔ (α * β)) Absorção para * ∈ {∧, ∨}
((α * (α ° β)) ↔ α) onde se * = ∧ então ° = ∨
se * = ∨ então ° = ∧
((α ↔ β) ↔ ((α → β) ∧ (β → α))) Definições da equivalência
((α ↔ β) ↔ ((α * β) ° (¬α * ¬β))) onde se * = ∧ então ° = ∨
((α ↔ β) ↔ ¬((α * β) ° (¬α * ¬β))) se * = ∨ então ° = ∧
((α ↔ β) ↔ (¬α ↔ ¬β))
(¬(α ↔ β) ↔ (¬α ↔ β) Negações de equivalentes
51
Grupo II: Implicações Tautológicas
(α → (β → α)) Prefixação por implicação
((α ∧ β) → α) Eliminação do primeiro conjuntivo
((α ∧ β) → β) Eliminação do segundo conjuntivo
(α → (α ∨ β)) Introdução do primeiro disjuntivo
(β → (α ∨ β)) Introdução do segundo disjuntivo
(¬α → (α → β)) Lei de Duns Scott 1
(α → (¬ α → β)) Lei de Duns Scott 2
((α → β) → ((α → ¬β) → ¬α)) Lei de Redução ao Absurdo (Introd.)
((¬α → β) → ((¬α → ¬β) → α)) Lei de Redução ao Absurdo (Elimin.)
(α → (β → (α ∧ β))) Introdução da conjunção
((α → γ) → ((β → γ) → ((α ∨ β) → γ))) Eliminação da disjunção
((α → ¬α) → ¬α) Redução de casos
((¬α → α) → α) Redução de casos
Grupo III:
(α ∨ ¬α) Lei do Terceiro Excluído
¬(α ∧ ¬α) Lei da Não Contradição
(α → α) Lei da Identidade Proposicional
Ao lado das tautologias, consideremos aquelas fórmulas CS que são falsas em qualquer valoração booleana (como, por exemplo, as especificações do esquema ‘(α ∧ ¬α)’. Tais fórmulas são ditas contradições. Se, agora, representarmos por um esquema tautológico e por um esquema contraditório, teremos, ainda, a possibilidade de formular os seguintes esquemas de leis proposicionais:
52
( ↔ ¬ ) ((α ∧ ) ↔ α ) ((α ∨ ) ↔ ) ((α ∧ ) ↔ ) ((α ∨ ) ↔ α) ((α → ) ↔ ) ((α → ) ↔ ¬α) (( → α) ↔ α) (( → α) ↔ )
4) Dizemos que uma fórmula α é conseqüência tautológica de um conjunto de sentenças Γ, se todo modelo verifuncional de Γ atribui o valor V a α.
Exemplo:
‘Q’ é uma conseqüência tautológica do conjunto {P, (P → Q)} pois: se ν é
um modelo de {P, (P → Q)}, então ν(P) = V e ν((P → Q)) = V; nesse caso,
necessariamente, ν(Q) = V.
Contra-exemplo:
‘Q’ não é uma conseqüência tautológica de {P, (Q → P)}, pois existe uma
valoração booleana ν tal que ν(P) = V e ν((Q → P)) = V, mas ν(Q) = F;
assim, ν é modelo de {P, (Q → P)}, mas falsifica ‘Q’.
Uma propriedade análoga à que expressamos acima, quando falamos das tautologias, vale para a relação de conseqüência tautológica. Seja ΓΠ/β o resultado da substituição de todas as ocorrências da letra sentencial Π nos elementos de Γ por ocorrências da fórmula CS β. Então a seguinte propriedade vale para todo conjunto de fórmulas CS Γ e quaisquer fórmulas CS α, β:
53
se αααα é conseqüência tautológica de ΓΓΓΓ, então ααααΠΠΠΠ/ββββ é conseqüência tautológica de ΓΓΓΓΠΠΠΠ/ββββ.
A justificação dessa propriedade é semelhante à justificação apresentada no caso das tautologias. Ela nos motiva, igualmente, a falar em esquemas da conseqüência tautológica.
Enunciamos, abaixo, algumas propriedades da relação de conseqüência tautológica (usaremos a notação Γ α para abreviar a sentença ‘α é conseqüência tautológica de Γ’).
(1) ∅ α se e só se α é uma tautologia; (2) se α ∈ Γ então Γ α; (3) se Γ α e Γ⊂∆ então ∆ α; (4) Γ (α ∧ ¬α) se e só se Γ é verifuncionalmente inconsistente; (5){α} β se e só se (α → β) é uma tautologia; (6) {α1, ..., αn} β se e só se (((α1 ∧ ...) ∧ αn) → β) é uma tautologia.
Em virtude da propriedade (6), podemos sempre decidir se uma fórmula β é conseqüência tautológica de um conjunto finito {α1, ..., αn} de fórmulas. Para isso é suficiente tomar a conjunção generalizada dos elementos do conjunto como antecedente de uma condicional cujo conseqüente é β e testar esta fórmula numa tabela de verdade: se for tautológica, β é conseqüência tautológica de {α1, ..., αn}; se não for, cada linha em que a implicação é falsa corresponde a uma classe de valorações que são modelos de {α1,...,αn} e falsificam β.
Casos importantes de relação de conseqüência tautológica a) Para cada um dos esquemas ( ↔ ’) de equivalências
tautológicas dadas na seção anterior temos: {E} E’ e {E’} E;
b) Para cada um dos esquemas (E → E’) de implicações tautológicas dadas na seção anterior temos: {E} E’;
c) (E1 → (E2 → ... → (En → E’) ...)) é um esquema tautológico se e só se {E1, E2, ..., En} E’.
54
Destaquemos alguns exemplos importantes:
{α, (α → β)} β Modus Ponens
{¬β, (α → β)} ¬α Modus Tollens
{(α → β), (β → γ)} (α → γ) Silogismos Hipotético
{(α ∨ β), ¬α} β Silogismo Disjuntivo
{(α ∨ β), ¬β} α Silogismo Disjuntivo
{α, ¬α} β Duns Scott
(α → γ), (β → γ), (α ∨ β)} γ Prova por Casos
Observações:
Quando queremos saber se β é conseqüência tautológica de um conjunto
finito de fórmulas {α1, ..., αn}, se não quisermos construir toda a tabela para
{α1, ..., αn} ∪ {β}, podemos proceder de uma das seguintes maneiras:
a) Considerar todas as linhas que verificam todos os elementos de
{α1, ..., αn} e verificar se β é verdadeira em todas elas (caso em que β
será conseqüência tautológica de {α1, ..., αn});
c) Considerar todas as linhas que falsificam β e verificar se alguma delas é
modelo de {α1, ..., αn} (caso em que β não é conseqüência tautológica
{α1, ..., αn}) ou se nenhuma delas é modelo de {α1, ..., αn} (caso em que
β é conseqüência tautológica de {α1, ..., αn}).
EXERCÍCIOS
1) Construa a tabela de verdade de:
a) (A → ((B ∧ ¬ B) → ¬ A)) b) ((A ∧ (B ∨ C)) ↔ ¬ B) c) (((A ∧ ¬ B) ↔ (C ∨ ¬ D)) → ¬ (A ∨ C))
55
2) Quais das sentenças abaixo são tautologias? Justifique a resposta.
a) ((A → (B ↔ C)) → (A ∧ B)) f) ((¬ A → B) → ¬ (A ∧ B)) b) ((¬ B → A) → (¬B → ¬ A)) g) (¬ (B ↔ (C ∨ ¬ B)) ∨ (C → B)) c) ((A ∨ B) ∨ (A ∨ ¬ C)) h) (((¬ A ∨ ¬ B) ∨ (A → B)) → (B ∨ A)) d) ((A ∧ B) ∨ ¬ A) i) ((P ↔ (R ∨ S)) → (P ∨ (R → ¬ S))) e) ((A ∨ ¬ ¬ B) → (C → (A → B)))
3) Sejam:
α1 = ((A → (B ↔ C)) → (A ∧ B)) α5 = ((A ∨ ¬ ¬ B) → (C → (A → B))) α2 = (( ¬ B → A) → (¬B → ¬ A)) α6 = ((¬ A → B) → ¬ (A ∧ B)) α3 = ((A ∨ B) ∨ (A ∨ ¬ C)) α7 = (A → (B → C)) α4 = ((A ∧ B) ∨ ¬ A) α8 = ((A → B) ∧ (A ∧ ¬ C))
3.1) Quais dos conjuntos abaixo são verifuncionalmente consistentes?
a) {α1, α2, α4, α5} c) {α3, α4, α5} b) {α2, α3, α4, α6} d) {α6, α7, α8}
3.2) Verifique se:
a) α7 é conseqüência tautológica de {α3, α6}; b) α4 é verifuncionalmente equivalente a α2 ; c) α8 é verifuncionalmente incompatível com α7 ; d) α1 é conseqüência tautologica de {α1, α6}.
3.3) Dê exemplo de uma sentença não pertencente a {α1, ..., α8} que seja conseqüência tautológica de {α3, α4, α6}, mas não seja conseqüência tautológica de {α1, α6}.
56
Aplicação dos conceitos proposicionais à linguagem L
Vamos retornar à linguagem L do Cálculo de Predicados para aplicar os conceitos proposicionais que acabamos de estudar. Para tanto, seja Γ um conjunto de sentenças de L, α uma sentença de L e h uma função de sentenças básicas (i.e. atômicas e gerais) em letras sentenciais. Então:
• αh indicará o resultado da substituição de cada componente básico
β, de α, por h(β); • Γh indicará o resultado da substituição de cada componente básico
β, que ocorra nos elementos de Γ, por h(β). Assim, αh é uma CS-associada de α, pela associação h e Γh num
conjunto de CS-associadas dos elementos de Γ, pela associação h.
Nessas condições: - dizemos que uma valoração ν é um modelo verifuncional de Γ se para alguma função de sentenças básicas em letras sentenciais, h, ν[β]=ν[h(β)] e ν é um modelo verifuncional de Γh . - dizemos que Γ é verifuncionalmente consistente se tem pelo menos um modelo verifuncional; - dizemos que α é tautológica se para algum h (como acima) αh é tautológica; - dizemos que α é conseqüência tautológica de Γ se, para algum h (como acima), Γh
αh.
Observemos que: Para algum h, αh é tautologia se e só se para toda h’, αh’ é tautologia; e Para algum h, αh é conseqüência tautológica de Γh se e só se para todo h’, αh’ é conseqüência tautológica de Γh’.
57
Assim, se quisermos saber se α é uma tautologia, tomamos uma CS-associada de α e testamos essa sentença CS numa tabela de verdade. O resultado obtido é aplicável a α. Da mesma forma, se quisermos saber se um conjunto finito {α1, ..., αn} tem como conseqüência tautológica β, encontramos um conjunto se sentenças CS-associadas de α1, ..., αn, β (segundo uma mesma associação) e testamos se a associada de β é conseqüência tautológica das associadas de {α1, ..., αn}. Dessa forma,
{(∀xF1x → ¬G1a), ∀xF1x} ¬G1a pois {P, (P → ¬Q} ¬Q
‘(∀xF1x ∨ ¬∀xF1x)’ é uma tautologia
pois ‘(P ∨ ¬P)’ é uma tautologia.
Da mesma forma, ‘{(∃xF1x → ¬(F1a ∨ G1b)), ¬F1a, (G1b → ∀xF1x)}’ é verifuncionalmente consistente, pois {(P → ¬(Q ∨ R)), ¬Q, (R → S)} é verifuncionalmente consistente, uma vez que toda valoração booleana ν tal que ν(P) = ν(Q) = F e ν(R) = ν(S) = V, por exemplo, verifica ‘(P → ¬(Q ∨ R))’, ‘¬Q’ e ‘(R → S)’. EXERCÍCIOS
1) Considere cada um dos seguintes conjuntos de sentenças:
Γ1 = {((∃x∃y R
2xy → ∀x (R
2xa → x=a)) → ∃x∃y R
2xy), ∀x (∃y R
2xy → ∃y R
2yx),
¬ ∃x∃y R2xy}
Γ2 = {∀x ∀y (R
2xy → x=y), ∃x ∀y R
2xy, ∃x ∃y ¬ x=y}
Γ3 = {∀x ∀y (R
2xy → (G
1x ∧ H
1y)), ¬ ∃x (G
1x ∧ H
1x), ∃x ∃y R
2xy}
Γ4 = {(∃x F
1x → ∀x G
1x), (∀x G
1x → ∀x (G
1x → H
1x)),
¬ ((∃x F1x ∨ ∀x G
1x) → ∀x (G
1x → H
1x))}
Γ5 = {¬ ∃x ∃y (R
2xy ∧ R
2yx), ∀x ∀y (¬ x=y → (R
2xy ∨ R
2yx))}
58
1.1) Quais deles são verifuncionalmente consistentes?
1.2) Quais das sentenças abaixo são conseqüências tautológicas de Γ3 ?
a) (¬ ∃x (G1x ∧ H
1x) → ¬ (¬∀x ∀y (R
2xy → (G
1x ∧ H
1y)) ∨ ¬ ∃x ∃y R
2xy))
b) (∃x ∃y R2
xy ∧ ∀x ∀y (R2
xy → (G1
x ∧ H1
y)))
c) (¬ ∃x (G1
x ∧ H1
x) ↔ ¬ ∃x ∃y R2
xy)
1.3) Dê exemplo de sentença que não seja conseqüência tautológica de Γ1.
59
Semântica de L (parte 2)
Para retornar à semântica do cálculo dos predicados e dar uma definição de verdade para as sentenças da linguagem - isto é, formular as condições gerais para que uma sentença qualquer α receba o valor de verdade V numa interpretação ℑ qualquer - precisamos introduzir alguns conceitos preliminares.
1. Constante específica para α. Seja α uma fórmula; dizemos que k é a constante específica para α se k é a primeira constante individual, na ordem alfabética, que não ocorre em α.
Exemplos:
Fórmulas Constante Específica
F2xa b
∀x (R2xb ∨ G1a) c
(∃yR2xy → ¬G2bc) a
Observemos que a constante específica é uma função, uma vez que a ordem
alfabética é fixa, que cada fórmula é finita (podendo, portanto, conter apenas
um número finito de constantes) e que há infinitas constantes individuais no
vocabulário.
2. Seja α uma fórmula, § uma variável, τ um termo. Denotaremos que α§/τ o resultado da substituição de todas as ocorrências livres de § em α por ocorrências de τ.
Exemplos:
§ τ α α§/τ
1 y a (F1y ∧ ∀z∃x (R2zy → S2xy)) (F1a ∧ ∀z∃x (R2za → S2xa))
2 x f1a (∃xF1x ∨ ∀yR2xy) (∃xF1x ∨ ∀yR2f1ay)
3 y b (∃xF1x ∨ ∀yR2xy) (∃xF1x ∨ ∀yR2xy)
4 z w (F2zz → ∃x∃zR2xz) (F2ww → ∃x∃zR2xz)
60
Observe-se que, no exemplo 3), α§/τ = α, pois não há ocorrências livres de § em
α. Assim, vacuamente, α é o resultado da substituição de todas as ocorrências
livres de § em α por τ (em nada importa qual é τ).
3. Seja α uma fórmula contendo, no máximo, § como variável livre, seja k a constante específica para α. Então a sentença α§/k é dita a instância específica de α. Note-se que:
a) o conceito de instância específica, uma vez que é definido para as fórmulas com, no máximo, uma variável livre, §, é uma função: cada fórmula desse tipo tem uma e só uma instância específica.
b) As instâncias específicas são necessariamente sentenças. Pois, se α tem, no máximo, § como variável livre, temos 2 casos:
- § ocorre em α; então § não ocorre em α§/k , assim, α§/k não tem variáveis livres;
- § não ocorre em α; então α é sentença e α§/k = α.
Como vemos, nos dois casos, α§/k é sentença.
4. Seja, agora, ℑ uma interpretação, ρ uma constante individual. Dizemos que ℑ’ é uma ρ-variante de ℑ se ℑ’ e ℑ diferem, no máximo no que atribuem a ρ. Assim, se ℑ e ℑ’ são ρ-variantes, Uℑ = Uℑ’; para toda letra sentencial Π, ℑ(Π) = ℑ’(Π); para todo predicado n-ário Πn, ℑ(Π n) = ℑ’(Πn); para todo símbolo funcional ϕn, ℑ(ϕn) = ℑ’(ϕn); para toda constante individual σ, se σ ≠ ρ, ℑ(σ) = ℑ’(σ).
O conceito de ρ-variante foi definido de tal forma que cada interpretação seja ρ-variante de si mesma; assim, dada uma interpretação ℑ, ele terá tantas ρ-variantes quantos são os objetos no seu universo. Além disso, se ℑ’ e ℑ” são ρ-variantes de ℑ, obviamente ℑ’ e ℑ” são ρ-variantes uma da outra.
Podemos, agora, enunciar as condições gerais de verdade para as sentenças de L.
61
Definição de Verdade para as sentenças de L
Seja ℑ uma interpretação. O valor de verdade associado por ℑ a uma sentença α, de L, em símbolos, vℑ(α) é definido por indução na complexidade de α, (indicada por “Cx (α)”):
- (base) Cx (α) = 0; então α é uma sentença atômica e vℑ(α) já foi definido na parte I. - (passo indutivo) Cx (α) > 0. Então, temos 7 casos: 1) α = ¬β; então vℑ(α) = V se e só se vℑ(β) = F; 2) α = (β∧γ); então vℑ(α) = V se e só se vℑ(β) = vℑ(γ) = V; 3) α = (β∨γ); então vℑ(α) = V se e só se vℑ(β) = V ou vℑ(γ) = V; 4) α = (β→γ); então vℑ(α) = V se e só se vℑ(β) = F ou vℑ(γ) = V; 5) α = (β↔γ); então vℑ(α) = V se e só se vℑ(β) = vℑ(γ); 6) α = ∀§β; então vℑ(α) = V se e só se vℑ’(β§/k) = V, para toda ℑ’
k-variante de ℑ, onde k é a constante específica para β; 7) α = ∃§β; então vℑ(α) = V se e só se vℑ’(β§/k) = V, para alguma
ℑ’ k-variante de ℑ, onde k é a constante específica para β;
Se vℑ(α) ≠ V, então vℑ(α) = F.
Observações gerais:
I - Pelas condições 1-5, verificamos imediatamente que as valorações acima
definidas são valorações booleanas. Então, uma valoração induzida por uma
interpretação é uma valoração booleana que respeita as condições de verdade para
as fórmulas atômicas dadas na 1ª parte e as condições de verdade 6-7 para as
fórmulas gerais. Assim, toda vℑ é uma valoração booleana, mas nem toda
valoração booleana é uma vℑ. Esse fato pode ser representado pelo gráfico :
valorações quaisquer valorações booleanas valorações induzidas por interpretações
62
II- Enquanto as condições 1-5 estabelecem que o valor de verdade de uma
sentença é determinado pelos valores de verdade das suas subfórmulas imediatas,
no caso das condições 6-7 isso não se dá. A razão para tal está no fato de que, por
um lado, se ¬β e (β ∗ γ) são sentenças, β e γ são sentenças (para ∗ ∈ {∧, ∨, →,
↔}); mas, por outro, se ∀§β e ∃§β são sentenças, não se segue que β seja uma
sentença: § pode ocorrer livre em β! No entanto, se ∀§β e ∃§β são sentenças, β§/k
é necessariamente uma sentença - e de menor complexidade!
III) Observemos o que ocorre com a sentença β§/k mencionada nas condições 6-7.
Como k é a constante específica para β, k ocorre em β§/k onde e só onde a variável
§ ocorre em β. Quando passamos de uma interpretação k-variante para outra, k é
o único símbolo interpretável de β§/k cujo significado é alterado; assim, não há
alteração nos significados de nenhum dos símbolos interpretáveis de β; então, com
a variação das diferentes interpretações k-variantes da interpretação dada, está-se
percorrendo o universo dessa interpretação com a constante k. Em outras
palavras, estão sendo considerados os valores possíveis da variável § nessa
interpretação - que são os objetos do seu universo.
Tomemos um exemplo.
Seja β uma fórmula ‘R2xa’ e seja ℑ uma interpretação cujo universo é o conjunto
{1, 2, 3}, ℑ(a) = 1 e ℑ(R2) = {(1,2), (2,1), (3,2), (1,1)}. Então, α§/k será ‘R2ba’ e
há 3 ‘b’-variantes; ℑ, ℑ’ e ℑ” tais que ℑ(b) = 1, ℑ’(b) = 2, ℑ”(b) = 3. Ora, vℑ(R2ba)
= V (pois (1,1) ∈ ℑ(R2)), vℑ’ (R2ba) = V (pois (2,1) ∈ ℑ(R2)) e vℑ” (R2ba) = F (pois
(3,1) ∉ ℑ(R2)). Dizemos, então, que 1, 2, 3 são valores possíveis da variável ‘x’;
que 1 e 2 são valores de ‘x’ que satisfazem ‘R2xa’, que 3 é um valor que não
satisfaz ‘R2xa’. Como os valores de uma variável são sempre objetos de um
universo, dizemos também que 1 e 2 são objetos que satisfazem ‘R2xa’ e 3 é um
objeto que não satisfaz ‘R2xa’, na interpretação dada. Se um objeto satisfaz uma
fórmula numa interpretação, ele é também dito uma solução para a fórmula.
IV - Notemos ainda que, no enunciado das condições de verdade para α, exigimos
que α fosse uma sentença. Ora, quando α é ∀§β ou ∃§β, pode ocorrer que § não
ocorra livre em β. Nesse caso, β já é uma sentença e β§/k = β; e, para toda
interpretação ℑ estará definido vℑ(β); como k não ocorre em β§/k, teremos, então
que vℑ‘ (β§/k) = vℑ(β§/k) = vℑ(β), para todo ℑ’ k-variante de ℑ. Dessa forma, nesse
caso, há duas possibilidades: ou vℑ‘(β§/k) = V, para qualquer ℑ’ k-variante de ℑ - e
isso acontece se vℑ(β) = V; ou vℑ‘ (β§/k) = F, para qualquer ℑ’ k-variante de ℑ - se
vℑ(β) = F. Segue-se, então que, se β é uma sentença, temos só 2 possibilidades: ou
63
qualquer objeto satisfaz β§/k ou nenhum objeto satisfaz β§/k. Segue-se daí que, se
β é uma sentença, vℑ(∀§β) = vℑ(∃§β) = vℑ(β), para qualquer interpretação.
V- Em alguns dos comentários feitos acima, usamos, intuitivamente, o
seguinte fato: o valor de verdade de uma sentença numa interpretação depende
apenas do universo de interpretação e do significado que ela atribui aos símbolos
interpretáveis que ocorrem nessa sentença - sendo, portanto, irrelevantes os
significados dos demais símbolos interpretáveis. A demonstração rigorosa desse
fato costuma ser feita em um segundo curso, mais avançado.
Conjunto Solução de uma fórmula
Para definir, de modo geral, conceitos já introduzidos em exemplos, seja α uma fórmula contendo, no máximo, § como variável livre; seja k a constante específica para α e ℑ uma interpretação. Então,
1) Para qualquer objeto o ∈ Uℑ, o é um objeto que satisfaz α na
interpretação ℑ se e somente se, para a ℑ’ k-variante de ℑ tal que ℑ’(k)=o, temos que vℑ‘ (α§/k) = V. Se o é um objeto que satisfaz α em ℑ, o
é uma solução para α em ℑ.
2) O conjunto solução de α em ℑ - em símbolos, CSolℑ(α) - é o subconjunto de Uℑ que contém todos os objetos que satisfazem α em ℑ.
De 1) e 2) segue-se que, se k é a constante específica para α, para qualquer ℑ’ k-
variante de ℑ, ℑ’(k) ∈ CSolℑ(α) se e só se vℑ‘ (α§/k) = V.
Se denotarmos por Cpl CSolℑ(α) o complemento, com respeito a Uℑ, do CSolℑ(α),
temos que ℑ’(k) ∈ Cpl CSolℑ(α) se e só se ℑ’(k) ∉ CSolℑ(α), se e só se vℑ‘ (α§/k) = F,
se e só se vℑ‘ (¬α§/k) = V. Portanto, podemos concluir: CSol ℑℑℑℑ(¬¬¬¬αααα) = Cpl CSolℑℑℑℑ(αααα)
Observemos que mesmo se α for uma sentença, i. é, se § não ocorrer
em α, podemos falar em um CSol(α); nesse caso, no entanto, teremos: CSol(αααα)=Uℑℑℑℑ,
se vℑℑℑℑ(αααα) = V; e CSol (αααα) = ∅∅∅∅, se vℑℑℑℑ(αααα) = F.
64
Suponhamos, agora, que nas fórmulas do conjunto {α, β} ocorra, no máximo, a variável § como variável livre. Examinemos, então, quais serão os conjuntos solução das fórmulas da forma (α∗β), para ∗ ∈ {∧, ∨, →, ↔}. Obviamente, a constante específica para cada uma das quatro fórmulas será a mesma, digamos k. Verificamos que:
CSol ℑℑℑℑ(αααα∧∧∧∧ββββ) = CSol ℑℑℑℑ(αααα) ∩∩∩∩ CSol ℑℑℑℑ(ββββ),
pois, para qualquer ℑ’ k-variante de ℑ, temos que ℑ’(k) ∈ CSol ℑ(α∧β), se e só se vℑ‘
((α∧β)§/k) = V, se e só se vℑ‘ (α§/k ∧β§/k) = V, se e só se vℑ‘ (α§/k) = vℑ’ (β§/k) = V,
se e só se ℑ’(k) ∈ CSolℑ(α) e ℑ’(k) ∈ CSolℑ(β), se e só se ℑ’(k) ∈ CSolℑ(α) ∩ CSolℑ(β).
CSolℑℑℑℑ(αααα∨∨∨∨ββββ) = CSolℑℑℑℑ(αααα) ∪∪∪∪ CSolℑℑℑℑ(ββββ),
pois, como (α∨β)§/k = (α§/k ∨ β§/k), temos que vℑ‘ ((α∨β)§/k) = vℑ‘ (α
§/k ∨ β§/k);
assim, vℑ‘ ((α∨β)§/k) = V se e só se vℑ‘ (α§/k) = V ou vℑ’ (β
§/k) = V; portanto,
ℑ’(k)∈CSolℑ(α∨β), se e só se ℑ’(k) ∈ CSolℑ(α) ou ℑ’(k) ∈ CSolℑ(β).
CSolℑℑℑℑ(αααα→→→→ββββ) = Cpl CSolℑℑℑℑ(αααα) ∪∪∪∪ CSolℑℑℑℑ(ββββ),
pois, como (α→β)§/k = (α§/k → β§/k), temos que vℑ‘ ((α→β)§/k) = V se e só se vℑ‘
(α§/k → β§/k) = V, se e só se vℑ‘ (α§/k) = F ou vℑ’ (β§/k) = V;
por conseguinte, ℑ’(k)∈CSolℑ((α→β)§/k) se e só se ℑ’(k) ∉ CSolℑ(α) ou ℑ’(k)∈CSolℑ(β),
se e só se ℑ’(k)∈Cpl CSolℑ(α) ∪ CSolℑ(β).
CSolℑℑℑℑ(αααα↔↔↔↔ββββ) = (CSolℑℑℑℑ(αααα) ∩∩∩∩ CSolℑℑℑℑ(ββββ)) ∪∪∪∪ (Cpl CSolℑℑℑℑ(αααα) ∩∩∩∩ Cpl CSolℑℑℑℑ(ββββ)).
Isso pode ser mostrado de forma análoga, levando-se em consideração o fato de
que vℑ‘ ((α↔β)§/k) = V se e só se vℑ‘ (α§/k) = vℑ’ (β§/k) = V ou vℑ‘ (α§/k) = vℑ’ (β§/k) =
F.
Suponhamos, agora, que a variável § ocorre livre em α mas não ocorre livre em β. Nesse caso, β é uma sentença e, como vimos (p.63): se vℑ(β) = V, CSolℑ(β) = Uℑ e se vℑ(β) = F, CSolℑ(β) = ∅. Segue-se então que:
Caso 1: vℑ(β) = V [e CSolℑ(β) = Uℑ]:
- CSolℑ(α∧β) = CSolℑ(β∧α) = Uℑ ∩ CSolℑ(α) = CSolℑ(α);
- CSolℑ (α∨β) = CSolℑ(β∨α) = Uℑ ∪ CSolℑ(α) = Uℑ;
- CSolℑ(α→β) = Cpl CSolℑ(α) ∪ CSolℑ(β) = Cpl CSolℑ(α) ∪ Uℑ = Uℑ;
- CSolℑ(β→α) = Cpl CSolℑ(β) ∪ CSolℑ(α) = ∅ ∪ CSolℑ(α) = CSolℑ(α);
- CSolℑ(α↔β) = CSolℑ(β↔α) = CSolℑ(α).
65
Caso 2: vℑ (β) = F [e CSolℑ(β) = ∅]:
- CSolℑ(α∧β) = CSolℑ(β∧α) = ∅ ∩ CSolℑ(α) = ∅;
- CSolℑ(α∨β) = CSolℑ(β∨α) = ∅ ∪ CSolℑ(α) = CSolℑ(α);
- CSolℑ(α→β) = CplCSolℑ(α) ∪ CSolℑ(β) = CplCSolℑ(α) ∪ ∅ = CplCSolℑ(α);
- CSolℑ(β→α) = Cpl CSolℑ(β) ∪ CSolℑ(α) = Uℑ ∪ CSolℑ(α) = Uℑ;
- CSolℑ(α↔β) = CSolℑ(β↔α) = Cpl CSolℑ(α).
Examinamos, acima, as composições moleculares. Vejamos o que acontece no caso da aplicação de um quantificador, Q§’ a α. Temos dois casos a examinar:
Caso 1: §’ ≠ §;
como § é a única variável que pode ocorrer livre em α e §‘ não ocorre em α,
᧑/k = α; portanto, CSolℑ (∀§‘α) = CSolℑ (∃§‘α) = CSolℑ (α)
Caso 2: §’ = §;
então ∀§‘α e ∃§‘α são sentenças, logo, CSolℑ(α)=Uℑ se e somente se
vℑ(∀§α)=V; CSolℑ(α) ≠ Uℑ se e só se vℑ (∀§α) = F; CSolℑ(α) ≠ ∅ se e só se
vℑ(∃§α)=V e CSolℑ(α) = ∅ se e só se vℑ (∃§α) = F
As afirmações feitas para o caso 2, acima, podem ser justificadas passo a passo a partir da definição de verdade. No caso da sentença universal, 1. vℑ(∀§α) = V se e só se vℑ ‘(α§/k) = V para toda ℑ’ k-variante de ℑ. 2. Ora, um objeto o∈Uℑ é solução para α se e só se vℑ’(α§/k) = V para a ℑ’ k-variante de ℑ tal que ℑ’(k) = o. 3. Portanto, vℑ’ (α§/k) = V para toda ℑ’ k-variante de ℑ se e só se todo objeto o∈Uℑ é solução para α. 4. Logo, vℑ(∀§α) = V se e só se todo objeto de Uℑ é solução para α; ou seja, se e só se CSolℑ(α) = Uℑ
Por outro lado, no caso da sentença existencial, 1. vℑ(∃§α) = V se e só se vℑ ‘ (α§/k) = V para alguma ℑ’ k-variante de ℑ. 2. Ora, um objeto o∈Uℑ é solução para α se e só se vℑ’(α§/k) = V para a ℑ’ k-variante de ℑ tal que ℑ’(k) = o. 3. Portanto, vℑ’ (α§/k) = V para alguma ℑ’ k-variante de ℑ se e só se algum objeto o∈Uℑ é solução para α.
66
4. Logo, vℑ(∃§α) = V se e só se algum objeto de Uℑ é solução para α; ou seja, se e só se CSolℑ(α) ≠ ∅. Convém, ainda, explicitar aqui o que ocorre com as negações dessas duas sentenças: No caso de uma negação de sentença universal, ¬∀§α, temos: 1. vℑ(¬∀§α) = V se e só se vℑ(∀§α) = F. 2. Já vimos que vℑ(∀§α) = V se e só se CSolℑ(α) = Uℑ. 3. Portanto, vℑ(∀§α) = F se e só se CSolℑ(α) ≠ Uℑ. 4. Logo, vℑ(¬∀§α) = V se e só se CSolℑ(α) ≠ Uℑ. Por outro lado, no caso da negação de uma existencial, ¬∃§α temos: 1. vℑ(¬∃§α) = V se e só se vℑ(∃§α) = F. 2. Já vimos que vℑ(∃§α) = V se e só se CSolℑ(α) ≠ ∅. 3. Portanto, vℑ(∃§α) = F se e só se CSolℑ(α) = ∅. 4. Logo, vℑ(¬∃§α) = V se e só se CSolℑ(α) = ∅.
EXERCÍCIOS
1) Sejam ℑ e ℑ’ interpretações tais que:
Uℑ = {1, 2, 3, 4, 5} Uℑ’ = {1, 2, 3, 4, 5, ...}
ℑ(F1) = {1, 2, 3} ℑ’(F
1) = conjunto dos ímpares
ℑ(G1) = {1, 3, 4} ℑ’(G
1) = {3, 7, 18}
ℑ(P1) = {2} ℑ’(P
1) = conjunto dos primos
ℑ(R2) = relação maior que ℑ’(R
2) = relação menor que
ℑ(M2) = {⟨1,2⟩, ⟨2,1⟩, ⟨3,2⟩} ℑ’(M
2) = relação múltiplo de
ℑ(f1) = função que associa a ℑ’(f
1) = função sucessor
qualquer objeto o 2
ℑ(g1) = 1, se x é par; ℑ’(g
1) = função quadrado
2, se x é ímpar
ℑ(s2) = função projeção do segundo ℑ’(s
2) = função soma
ℑ(a) = 1 ℑ’(a) = 1
ℑ(b) = 5 ℑ’(b) = 2
67
1.1) Determine, em ℑ e em ℑ’, o valor de verdade de:
a) ¬ R2ab g) ¬ (R
2ab ∧ R
2ba)
b) (M2ab ∧ ¬ P
1b) h) (M
2af
1b → M
2f1bf
1a)
c) (R2ab ∨ f
1a=b) i) ¬ (P
1a ∨ P
1b)
d) (f1a=b ↔ f
1b=a) j) (¬ P
1a ∨ P
1
b)
e) (P1b → R
2ba) l) ¬ (a=b → b=a)
f) (R2ab → (¬P
1b → P
1b)) m) ( ( a=b ∧ ¬ b=f
1a) ↔ ¬ a=b)
1.2) Determine, em ℑ e em ℑ’, o conjunto solução de:
a) ¬ F1x f) (G1f1x ∨ ¬ G1x)
b) F1f1x g) (F1x → G1x)
c) ¬ R2xa h) (G1x → F1x)
d) (R2xa ∧ f1x=b) i) ¬ (F1x ∧ G1x)
e) ¬ G1x j) ¬ (F1x ∨ G1x)
1.3) Sendo α cada uma das fórmulas do exercício anterior e § a variável 'x', determine, em ℑ e em ℑ’, o valor de verdade de ∀§ α e ∃§ α.
1.4) Determine, em ℑ e em ℑ’, o valor de verdade de: a) ∀x F1x e) ¬ ∀x G1x i) ∃x (F1x ∨ G1x)
b) ∀x ¬ F1x f) ¬ ∀x ¬ G1x j) ∃x (R2xa ∧ G1x)
c) ∃x G1x g) ¬ ∃x ¬ F1x k) ∃x (R2xb ∨ R2ax)
d) ∃x ¬ G1x h) ∃x (F1x ∧ G1x) l) ∀x (F1x → R2ax)
1.5) Em ℑ’, dê exemplo de uma fórmula cujo conjunto solução seja:
a) {2} b) {1, 3} c) {3, 7} d) {4, 6, 8, 10, 12, ...} e) UI’
1.6) Em ℑ, dê exemplo de uma fórmula cujo conjunto solução seja:
a) {4, 5} b) {3} c) {5} d) {4} e) { }
2) Seja ℑ uma interpretação tal que:
Uℑ = conjunto dos seres humanos
ℑ(a) = Pedro I ℑ(b) = Princesa Isabel ℑ(c) = Pedro II ℑ(f1) = função o pai de
ℑ(B1) = conjunto dos brasileiros ℑ(M
1) = conjunto das mulheres
ℑ(S2) = relação mais velho que ℑ(I
2) = relação irmão de
2.1) Indique os conjuntos solução, em ℑ, das seguintes fórmulas.
a) S2xa i) a=f
1x
b) S2ax j) a=f
1f1x
68
c) (S2ax ∧ B
1x) l) (M
1x ∧ f
1x=c)
d) x=a m) (S2ax ∧ S
2xb)
e) (x=a ∨ x=b) n) (¬ B1x ∧ ¬ M
1x)
f) (x=a ∧ x=b) o) ((M1x ∧ B
1x) ∧ ¬ S
2xa)
g) ¬ (S2xa ∨ S
2ax) p) (¬ B
1x ∧ B
1x)
h) x=f1b
2.2) Indique o valor de verdade, segundo ℑ, das seguintes sentenças:
a) ∃x S2xa e) ∀x ¬ S
2xx
b) ∀x S2xa f) ∃x ((B
1x ∧ ¬ M
1x) ∧ I
2xa)
c) ∃x (f1x=c ∧ M
1x) g) ∀x ((M
1x ∧ B
1x) ↔ x=b)
d) ∀x (x=f1b → B
1x) h) ∃x ((M
1x ∧ B
1x) ∧ S
2cx)
3) Seja ℑ uma interpretação tal que:
Uℑ = conjunto dos países e cidades ℑ(P1) = conjunto dos países
ℑ(E1) = conjunto dos que estão na Europa
ℑ(A1) = conjunto dos que estão na América
ℑ(R2) = relação fazer fronteira com ℑ(S
2) = relação ser mais populoso que
ℑ (h1) = função que associa a cada cidade o país a que pertence, e, a cada
país, sua capital
ℑ(a) = Argentina ℑ(l) = Londres
ℑ(b) = Brasil ℑ(n) = Nova York
ℑ(c) = China ℑ(p) = Paris
ℑ(f) = França
Determine o valor de verdade, segundo ℑ, das sentenças abaixo:
a) ∀x (R2xa → R
2xb) e) (∀x ((A
1x ∧ P
1x) → S
2h1nx) ∧ ∃y S
2yh
1n)
b) ∃x (R2xb ∧ ¬ R
2xf) f) ∀x (E
1x ↔ ¬ A
1x)
c) ∀x (R2ax → (¬ R
2xf ∧ ¬ x=c)) g) ∃x (E
1x ∧ (h1x=p ∨ h
1x=l))
d) ∃x (¬ P1
x ∧ S2xh
1b) h) h
1p=h
1h1f
69
Significado formal de uma fórmula SF (α) : são as condições satisfeitas por toda a interpretação ℑ tal que vℑ(α)=V. A sentença afirma tais condições. Quando a sentença é verdadeira, essas condições se realizam. Portanto, a sentença expressa uma situação que é comum a todas as interpretações ℑ tais que vℑ(α)=V. Assim,
a) Significado Formal de sentenças atômicas - Sentenças atômicas podem ter a forma Π (onde Π é letra sentencial), Πnτ1...τn (onde Πn é um predicado n-ário e τ1,...,τn são termos fechados) ou τ1 = τ2 .
SF (Π) : I (Π) = V - O significado formal de uma sentença como Π, é simplesmente
a afirmação de que Π é verdadeira.
SF (Πnτ1...τn): [δI (τ1), ... , δI (τn)] ∈ I(Πn) – ou seja: a n-upla formada pelos objetos
denotados pelos termos τ1,.... τn , tomados nessa ordem, pertence à relação
n-ária que a interpretação em causa associa ao predicado n-ário Πn
SF (τ1 = τ2): δI (τ1) é a mesma que δI (τ2) – ou seja: na interpretação em questão, os
termos τ1 e τ2 denotam o mesmo objeto.
b) Significado Formal de sentenças moleculares Sejam α e β sentenças; sentenças moleculares são da forma ¬α, (α ∧ β), (α ∨ β), (α → β) e (α ↔ β).
SF (¬α) : negação do SF (αααα) , pois são as condições que uma interpretação I deve
cumprir para que νI (¬α)=V, portanto, para que νI (α) = F.
SF (α ∧ β): SF (αααα) e SF (ββββ), pois para que uma interpretação I seja modelo de (α ∧ β),
ela deve ser modelo de (α) e deve ser modelo de (β).
SF (α ∨ β): SF (αααα) ou SF (ββββ), pois para que uma interpretação I seja modelo de
(α ∨ β), ela deve ser modelo de (α) ou deve ser modelo de (β).
SF (α → β): negação do SF (αααα) ou SF (ββββ), pois para que uma interpretação I seja
modelo de (α → β), ela deve ser tal que ou ela não é modelo α, ou ela deve
ser modelo de (β).
SF (α ↔ β): SF (αααα) se e só se SF (ββββ), i.e., ou bem SF (α) e SF (β), ou bem negação do
SF (α) e negação do SF (β), pois para que uma interpretação I qualquer
seja modelo de (α ↔ β), ou bem ela é modelo de (α) e modelo de (β), ou
bem ela é tal que νI (α) = F e νI (β) = F.
70
Resumindo: O significado formal de uma sentença molecular é uma função dos
significados formais de suas partes; e essa função é a indicada pelo conectivo em
causa.
c) Significado Formal de sentenças gerais – sentenças da forma ∀§ β ou ∃§ β.
SF(∀§ β): CSolℑ(β)=UI - ou seja, qualquer objeto do universo da interpretação é uma
solução para β;
SF (∃§ β): CSolℑ (β) ≠ ∅ - ou seja, há soluções para β no universo da interpretação
71
Diagramas para uma fórmula α com uma só variável livre.
Suponhamos que α é uma fórmula com apenas uma variável livre. Representemos graficamente o universo da interpretação (Uℑ) do seguinte modo:
O universo será dividido entre os objetos que estão em CSolℑ(α) e os que não estão em CSolℑ(α). Ilustremos essa divisão desenhando no quadrado que representa o universo uma circunferência delimitando duas regiões. A região I corresponderá a CSolℑ(α) e a região II, ao seu complemento CplCSolℑ(α), ou seja, como vimos, o CSolℑ(¬α) I II Ora, com respeito à distribuição dos objetos no universo, quatro distintas situações podem ocorrer, uma vez que cada uma das duas regiões pode ou não conter objetos. Podemos, então, distinguir quatro situações: a) A região I é vazia. b) A região I não é vazia. c) A região II é vazia. d) A região II não é vazia. Vejamos, agora, como podemos representar graficamente tais situações e expressá-las por meio de sentenças formais. Nas figuras que se seguem, pintaremos de cinza uma região para significar que nela não há elementos. Por outro lado, um ponto ou um traço no interior de uma região serve para indicar que nela há elementos. As duas notações são, portanto, contraditórias com respeito a uma mesma região. Ora, como estabelecemos antes, se α é a fórmula que divide o universo nas duas regiões, a região I é exatamente o CSolℑ(α); por outro lado, sabemos
72
que νℑ(∃§α) = V se e somente se νℑ’(α§/k) = V em alguma ℑ’ k-variante de ℑ, ou seja, algum objeto do universo da interpretação for uma solução para α. Para referir isto em termos de conjunto solução, νℑ (∃§α) = V se e somente se CSolℑ(α) não for vazio, ou, ainda, se a região I não for vazia – situação b), acima. a) A região I é vazia: CSolℑ(α) = ∅ ; ¬∃§α b) A região I não é vazia: CSolℑ(α) ≠ ∅ ∃§α • c) A região II é vazia: CSolℑ(¬α) = ∅ ¬∃§¬α d) A região II não é vazia: CSolℑ(¬α) ≠ ∅ ∃§¬α
•
73
Os quatros diagramas ilustram os significados formais das quatro sentenças. Abstratamente, podemos falar nos significados formais (SF) destas quatro sentenças - a saber,
a) CSolℑ(α) = ∅; ou, ainda, Cpl CSolℑ(¬α) = ∅; b) CSolℑ(α) ≠ ∅; ou, ainda, Cpl CSolℑ(¬α) ≠ ∅; c) Cpl CSolℑ(α) = ∅; ou, ainda: CSolℑ(¬α)= ∅; d) Cpl CSolℑ(α) ≠ ∅; ou, ainda: CSolℑ(¬α) ≠ ∅.
Vamos analisar agora algumas equivalências, iniciando pela terceira situação (afirmação c). Aqui dizemos que a região II é vazia, ou seja, que ¬∃§¬α (ver representação no diagrama acima). Ora, isto é o mesmo que dizer que ∀§α: com as k-variantes, percorremos o universo e vemos que qualquer objeto pertence ao conjunto solução de α [CSolℑ(α)]. Por outro lado, afirmar que a região I é vazia (afirmação a), i.e., que ¬∃§α é o mesmo que dizer: o complemento do CSolℑ(α) é o próprio Uℑ. Ou seja, que CSolℑ(¬α) é o universo: ∀§¬α. Qualquer que seja o objeto, ele é uma solução para o complemento do CSolℑ(α). Ora, dizer tal coisa é dizer o contrário do que diz a afirmação b: que a região I não é vazia. Portanto, afirmar que a região I não é vazia (afirmação b), ∃§α, é o mesmo que negar que o complemento do CSolℑ(α) é o universo: ¬∀§¬α, ou seja, é dizer que não é verdade que todo objeto é solução para o complemento de α. Finalmente, dizer que nem todo objeto está no CSolℑ(α) i.e. que a região II não é vazia, ∃§¬α (afirmação d), é o oposto da afirmação de que a região II é vazia. Portanto, é equivalente a ¬∀§α. De forma esquemática, podemos resumir:
Sentenças Significado Formal
∀§¬α ¬∃§α Cpl CSolℑ(α) = Uℑ , ou CSolℑ(α) = ∅
¬∀§¬α ∃§α Cpl CSolℑ(α) ≠ Uℑ , ou CSolℑ(α) ≠ ∅
∀§α ¬∃§¬α CSolℑ(α) = Uℑ , ou Cpl CSolℑ(α) = ∅
¬∀§α ∃§¬α CSolℑ(α) ≠ Uℑ , ou Cpl CSolℑ(α) ≠ ∅
74
Diagramas para fórmulas compostas por duas fórmulas nas quais ocorre uma mesma variável livre Vejamos agora o conjunto solução e o significado formal de fórmulas que contêm α e β, onde α e β são fórmulas com uma mesma e única variável livre que efetivamente ocorre em ambas. Lembremos que fórmulas abertas têm conjunto solução, enquanto sentenças - fórmulas fechadas - têm significado formal. Para representarmos por via de diagrama as fórmulas α e β, podemos pensar que as duas fórmulas dividem o universo da interpretação - UI - em quatro partes: α β II I III IV Podemos representar cada região (I, II, III e IV) por meio de uma fórmula:
Região Fórmula
I (α ∧ β) II (α ∧ ¬β) III (¬α ∧ β) IV (¬α ∧ ¬β)
Com respeito a cada uma dessas regiões, pode-se fazer as quatro afirmações que vimos antes - que a região é vazia, que não é vazia, que é o universo, que não é o universo. Estas são as quatro sentenças que podemos formar a respeito dessas regiões usando os quantificadores:
75
a) ∃§(α ∧ β) ¬∀§¬ (α ∧ β) • b) ¬∃§ (α ∧ β) ∀§¬ (α ∧ β) c) ∃§¬ (α ∧ β) ¬∀§ (α ∧ β) A afirmação ‘c’ diz respeito à II ∪ III ∪ IV. O “trilho” é usado para representar um objeto que pode percorrer essa região - sem que tenhamos que saber necessariamente onde exatamente o objeto está. d) ¬∃§¬ (α ∧ β) ∀§ (α ∧ β)
76
Algumas equivalências básicas, que não são tautológicas, mas que são devidas também ao significado dos quantificadores, são as seguintes: ∃§α ⇔ ¬∀§¬ α ¬∃§ α ⇔ ∀§¬ α ∃§¬ α ⇔ ¬∀§α ¬∃§¬ α ⇔ ∀§α A partir do diagrama que divide o universo em quatro regiões distintas, podemos pensar em representar mais outras regiões: e) Regiões I e II. Fórmula: α. α β f) Regiões: I e III. Fórmula: β. α β III g) Regiões: I e IV, i.e. I ∪ IV. Fórmula: (α ↔ β). α β
O sinal ‘⇔‘ é usado aqui para abreviar: ‘tem o mesmo significado formal que’.
I II
I
I IV
77
h) Regiões: II e III. Fórmula:(α ↔ ¬β) ou (¬α ↔ β) ou ¬(α ↔ β)
α β II III i) Regiões: II e IV. Fórmula: ¬β. α β II IV j) Regiões: III e IV. Fórmula: ¬α. α β III IV k) Regiões: I, II e III. Fórmula: (α v β). α β II I III
78
l) Regiões: I, II e IV. Fórmula: (α v ¬β). α β II I IV m) Regiões: I, III e IV. Fórmula: (¬α v β). α β I III IV n) Regiões: II, III e IV. Fórmula: (¬α v ¬β). α β II III IV Observemos que, de modo geral temos sempre: CSolℑ (¬α) = Cpl CSol ℑ(α) CSol ℑ (α ∧ β) = CSol ℑ(α) ∩ CSol ℑ(β) CSol ℑ (α ∨ β) = CSol ℑ(α) ∪ CSol ℑ (β)
79
Examinemos agora, mais cuidadosamente, os conjuntos solução correspondentes a fórmulas condicionais. Vamos determinar, passo a passo, o conjunto solução de (α → β): Um objeto que satisfaz (i.e. é solução para) a fórmula (α → β) será aquele tal que
νℑ’ (α → β)§/k = V, quando ℑ’(k)= e k é a constante própria para (α → β).
Como § ocorre em α e β, (α → β)§/k é o mesmo que (α§/k → β§/k ).
Ora, νℑ’ (α§/k → β§/k ) = V quando ℑ’(k)= e:
ou bem o objeto não é uma solução para α,
ou bem o objeto é uma solução para β.
Assim, ℑ’(k) é uma solução para (α → β) se e somente se ℑ’(k) não é uma solução
para α ou ℑ’(k) é uma solução para β.
Objetos que não são solução para α estão nas regiões III e IV do diagrama; as
soluções para β estão nas regiões I e III.
O conjunto solução, então, de (α → β) é formado pela união de I, III e IV.
Agora que sabemos qual o conjunto solução da fórmula (α → β), vejamos o que
significa a sentença ∀§(α → β).
SF (∀§(α → β)) : CSolℑ(α → β) = Uℑ
Isto é dizer que não há objetos que estejam em α e que não estejam em β: α β CSolℑ(α) ⊂ CSolℑ(β) II I III IV É o mesmo que dizer que ¬∃§(α ∧ ¬β). Portanto:
SF (¬∃§ (α ∧ ¬β)) é o mesmo que SF (∀§(α → β)), ou seja, as duas sentenças são
equivalentes.
80
Ao afirmar que o conjunto solução de α é subconjunto do conjunto solução
de β, nós não estamos nos comprometendo com a existência de objetos em α.
Estamos afirmando, isto sim, a inexistência de objetos na região II. A sentença é
vacuamente verdadeira sempre que CSolℑ(α) = ∅.
A forma da sentença ∀§(α → β) é a de uma universal restrita: algo do tipo
“todo A é B”; sentenças como essa podem ser vacuamente verdadeiras.
Vamos comparar agora a sentença ∀§(α → β) com a sentença ∃§ (α → β). A
implicação com um quantificador existencial é muito mais rara e tem um
significado formal totalmente diferente. O significado formal de ∃§ (α → β) é que
existe um objeto na região I, ou III, ou IV. É um significado formal pobre, pois diz
muito pouco; por isso mesmo, uma sentença assim é pouco usada. O seu
significado formal é equivalente ao de ¬∀§¬ (α → β) e ao de ¬∀§(α ∧ ¬β). SF (∃§ (α → β)) = SF (¬∀§¬ (α → β)) = SF (¬∀§(α ∧ ¬β)) α β II I III IV A sentença ∃§ (α → β) não significa que “algum A é B”. Para dizermos que
“algum A é B”, usamos ‘∧’ : ∃§(α ∧ β). SF (∃§(α ∧ β)) : CSolℑ(α) ∩ CSolℑ(β) ≠ ∅ α β •
OBSERVAÇÃO: o significado formal de ∀§(α ∧ β) é o de que o universo da
interpretação é a interseção de CSolℑ(α) e CSolℑ(β).
81
Para sabermos qual o significado formal de ∀§ (α → ¬β), convém começar
procurando uma solução para a fórmula (α → ¬β): um objeto que ou bem não é α,
ou bem não é β. Então não seria uma solução para (α → ¬β) um objeto que fosse
ao mesmo tempo α e β. Ora, a aplicação do universal à fórmula diz que qualquer
objeto do universo é solução para ela. Logo, não podemos ter no universo objetos
que são ao mesmo tempo α e β. As soluções para esta fórmula estarão nas regiões
II, III ou IV - só não podendo estar na região I. Portanto, o significado formal da
sentença acima é dado por: SF (∀§ (α → ¬β)) : CSolℑ(α) ∩ CSolℑ(β) = ∅ α β
E qual será o conjunto solução de uma fórmula do tipo (α ↔ β)? A região que
corresponde ao CSolℑ(α ↔ β) é a I e a IV. Portanto, se dissermos que ∀§ (α ↔ β),
estamos afirmando que as regiões II e III são vazias:
SF ∀§(α ↔ β) : CSolℑ(α) = CSolℑ(β) α β II III I IV
Podemos dizer então que CSolℑ(α) e CSolℑ(β) são coextensivos ou seja, eles são o
mesmo conjunto; i.e. α e β são duas fórmulas que têm o mesmo conjunto solução.
Como é possível expressar a igualdade entre conjuntos, então também
podemos expressar a sua distinção, negando a fórmula acima:
SF (¬∀§ (α ↔ β)) : CSolℑ(α) ≠ CSolℑ(β)
82
Em outras palavras, há pelo menos um objeto em α que não está em β ou
há pelo menos um objeto em β que não está em α.
Para ilustrar, tomemos uma interpretação tal que:
Uℑ = {0, 1, 2, 3, ...}
ℑ(F1) = pares ℑ(G1) = primos
ℑ(R2) = relação menor que ℑ(a) = 0
ℑ(f1) = operação sucessor ℑ(b) = 2
ℑ(s2) = operação soma ℑ(p2) = operação produto
Na tabela a seguir, indicamos os conjuntos solução de algumas fórmulas nessa
interpretação: α Conjunto Solução de α em I F1x Pares, i.e. {0, 2, 4, 6, ...}
G1x primos, i.e. {2, 3, 5, 7, 11, ...}
(F1x ∧ G1x) CSolℑ(F1x) ∩ CSolℑ(G1x), i.e. pares ∩ primos: {2}
(F1x ∨ G1x) CSolℑ(F1x) ∪ CSolℑ(G
1x), i.e. pares ∪ primos: {0, 2, 3, 4, 5, 6, 7, ...}
¬F1x Cpl CSolℑ(F1x), i.e. ímpares: {1, 3, 5, 7, 9, ...}
¬G1x Cpl CSolℑ (G1x), i.e. não primos: {0, 1, 4, 6, 8, 9, ...}
(F1x → G1x) Cpl CSolℑ(F1x) ∪ CSolℑ(G1x), i.e. ímpares ∪ primos: {1, 2, 3, 5, ...}
(G1x → F1x) Cpl CSolℑ(G1x) ∪ CSolℑ(F
1x), i.e. não primos ∪ pares: {0, 1, 2, 4, 6, ...}
Examinemos agora o valor de verdade de algumas sentenças nessa mesma
interpretação:
Sentença Significado interpretado em ℑ Valor de
Verdade segundo ℑ
∀x (Fx ∧ Gx) {pares} ∩ {primos} = Uℑ F
∃x (Fx ∧ Gx) {pares} ∩ {primos} ≠ ∅ V
∀x (Fx ∨ Gx) {pares} ∪ {primos} = Uℑ F(2) ∃x (Fx ∨ Gx) {pares} ∪ {primos} ≠ ∅ V
∀x Rxa {nos < 0} = Uℑ F
2 Existe pelo menos um objeto no universo da interpretação que não é nem par nem primo - viz. 9. Há mais de um que não é nem par nem primo, mas para falsificar esta sentença é suficiente que um objeto do universo não o seja.
83
∀x Rax {nos > 0} = Uℑ F(3) ∃x Rxa {nos < 0} ≠ ∅ F
∃x Rax {nos > 0} ≠ ∅ V
∃x(¬Fx ∨ ¬Gx) {ímpares} ∪ {não primos} ≠ ∅ V(4)
∀x b = x {2} = Uℑ F
∀x (x = b ∨ (¬Fx ∨ ¬Gx)) {2} ∪ {ímpares} ∪ {não primos} = Uℑ V
∀x (x = b ∧ (¬Fx ∨ ¬Gx)) {2} ∩ {{ímpares} ∪ {não primos}} = Uℑ F(5) ∃x (Rbx ∧ Gx) {nos >2} ∩ {primos} ≠ ∅ V
∀x ((Rbx ∧ Gx) → ¬Fx) {primos maiores que 2} ⊂ {ímpares}, ou todo primo maior que 2 é ímpar
V(6)
EXERCÍCIOS Dê exemplo de uma sentença formal que, no contexto da interpretação dada na página anterior, declare que: a) A soma de dois ímpares é sempre par b) Nenhum sucessor de ímpar é impar c) Nem todo ímpar maior que 3 é primo d) O cubo de dois é múltiplo de quatro e) Há um certo par que não é um sucessor f) Todo número par é divisível por dois g) Alguns números pares são divisíveis por pelo menos dois distintos ímpares h) Se um número é primo, então seus únicos fatores são ele próprio e a unidade.
3 Somente o número 0 (zero) não é solução da fórmula; mas então o CSolℑ(α) ≠ UI.
4 Das leis de equivalência tautológica de De Morgan, segue-se que a fórmula (¬Fx ∨ ¬Gx) é equivalente à fórmula ¬(Fx ∧ Gx). O complemento desta fórmula é tudo menos {2}; portanto o seu CSolℑ pode ser reescrito como sendo o Uℑ - {2}.
5 Esta interseção resulta em um conjunto vazio.
6 ((Rbx ∧ Gx) → ¬Fx) é tautologicamente equivalente a (¬(Rbx ∧ Gx) ∨ ¬Fx). O CSolℑ desta fórmula é o Cpl {{números maiores que 2} ∩ {primos}} ∪ {ímpares}, ou seja, {(2) ∪ {não primos}} ∪ {ímpares}, i.e. o universo da interpretação.
84
Algumas conseqüências da extensionalidade da designação Interrompemos o estudo de casos de conjuntos solução e significados formais de certos esquemas paradigmáticos de fórmulas para chamar a atenção para uma propriedade do nosso cálculo que pode ser assim formulada: as funções significativas atribuídas aos símbolos do nosso vocabulário pelas interpretações têm um caráter estritamente extensional. Em particular, a função semântica de uma constante individual é unicamente a de remeter a um objeto do universo. Daí decorrem algumas conseqüências importantes. As demonstrações rigorosas de tais conseqüências excedem os objetivos deste estudo; podemos, no entanto, prosseguir neste momento contando apenas com a compreensão intuitiva das mesmas. Por enquanto, vamos então simplesmente aceitar que, para qualquer fórmula α com uma única variável livre, §, para quaisquer constantes individuais k’, k’’ que não ocorram em α, para qualquer interpretação ℑ:
E1) se ℑ’ é uma k’-variante de ℑ , se ℑ’’ é uma k’’-variante de ℑ e ℑ’(k’) =
ℑ’’(k’’), então vℑ’(α§/k’) = vℑ’’(α§/k’’);
E2) se ℑ’ é uma k’-variante de ℑ, ℑ’(k’) é uma solução para α se e só se
vℑ’(α§/k’) = V;
E3) vℑ(∀§α) = V se e só se vℑ’(α§/k’) = V para toda ℑ’ k’-variante de ℑ - da
mesma forma, vℑ(∃§α) = V se e só se vℑ’(α§/k’) = V para alguma ℑ’ k’-variante
de ℑ . Note-se que o pressuposto é apenas que k’ não ocorre em αααα;
assim k’ não precisa ser a constante específica para αααα!
Seja agora β uma sentença e k uma constante qualquer que não ocorra em β. Então,
E4) para qualquer ℑ’ k-variante de ℑ, vℑ’ (β§/k) = vℑ’ (β) = vℑ (β);
em particular, se k for a constante específica para β, para qualquer ℑ’ k-variante de ℑ, o objeto denotado por ℑ’(k) será uma solução para β se e só se vℑ(β) = V! Assim, se vℑ(β) = V, qualquer objeto de Uℑ será uma solução para β; e se vℑ(β) = F, nenhum objeto de Uℑ será uma solução para β. Portanto,
85
E5) se vℑ (β) = V, CSolℑ(β)= Uℑ ; se vℑ (β) = F, CSolℑ(β)= ∅.
Algumas afirmações feitas nas próximas páginas estarão assentadas nos enunciados E1 - E5 que acabamos de formular. Fórmulas contendo sentenças como subfórmulas Seja agora ℑ uma interpretação, α uma fórmula contendo uma única variável livre e β uma sentença. Observemos inicialmente que a constante específica para as fórmulas da forma (α * β) ou (β * α) , onde * é um conectivo binário qualquer, é sempre a mesma; seja k essa constante e seja k’ a constante específica de α (note-se que k e k’ podem ser distintas!). Vamos examinar agora os conjuntos solução em ℑ de algumas fórmulas da forma (α * β) ou da forma (β * α). 1. conjunções:
1a) CSolℑ(α ∧ β)
i) se β é verdadeira em ℑ, CSolℑ(α ∧ β)= CSolℑ(α)
ii) se β é falsa em ℑ, CSolℑ(α ∧ β)= ∅
Explicação: Um objeto será uma solução para esta fórmula se e somente se
vℑ’(α∧β)§/k = V na ℑ’ k-variante de ℑ na qual k o designa; como β é uma
sentença, vℑ’(α ∧ β)§/k = vℑ’ (α§/k ∧ β) e vℑ’ (β) = vℑ(β) ; então,
i) se β é verdadeira em ℑ, vℑ’ (α§/k ∧ β) = V se e só se vℑ’ (α
§/k ) =V; e,
como k não ocorre em α, de acordo com E2 acima, isso se dá se e só se
ℑ’(k) é uma solução para α ;
ii) se β é falsa em ℑ, vℑ’ (α§/k ∧ β) = F para qualquer ℑ’ k-variante, logo,
não haverá solução em ℑ para (α ∧ β).
1b) CSolℑ(β ∧ α) = CSolℑ(α ∧ β)
Explicação: análoga à anterior, levando-se em consideração o caráter
comutativo da conjunção .
86
2. disjunções:
2a) CSolℑ(α v β)
i) se β é verdadeira em ℑ, CSolℑ(α v β)= Uℑ
ii) se β é falsa em ℑ, CSolℑ(α v β)= CSolℑ(α)
Explicação: Um objeto será uma solução para esta fórmula se e somente se
vℑ’(αvβ)§/k = V na ℑ’ k-variante de ℑ na qual k o designa; como β é uma
sentença, vℑ’(α v β)§/k = vℑ’ (α§/k v β) e
i) se β é verdadeira em ℑ (e, assim, em ℑ’), vℑ’ (α§/k v β) = V em todas
as k-variantes de ℑ! Portanto, qualquer objeto de Uℑ é uma solução
para (α v β).
ii) se β é falsa em ℑ (e, assim, em ℑ’), um objeto será uma solução
para esta fórmula se e só se, na ℑ’ k-variante de ℑ na qual k o
designa, vℑ’(α v β)§/k = V; e isso se dá se e só se vℑ’(α§/k v β) = V, o
que acontece se e somente se vℑ’(α§/k) ; ou seja, de acordo com E2
acima, se o objeto for uma solução para α.
2b) CSolℑ(β v α) = CSolℑ(α v β)
Explicação: análoga à anterior, levando-se em consideração o caráter
comutativo da disjunção .
3. implicações: as implicações não são comutativas! Assim, consideraremos separadamente os dois casos, que têm conjuntos solução bem distintos. O caso que merece mais cuidado é aquele onde a fórmula α figura no antecedente, ou seja, o caso 3a) abaixo:
3a) CSolℑ(α → β)
i) se β é verdadeira em ℑ, CSolℑ(α → β)= Uℑ
ii) se β é falsa em ℑ, CSolℑ(α → β)= CSolℑ(¬α)
Explicação: Um objeto será uma solução para esta fórmula se e somente se
vℑ’(α→ β)§/k = V na ℑ’ k-variante de ℑ na qual k o designa; como β é uma
sentença, vℑ’(α→β)§/k = vℑ’ (α§/k → β) e
87
i) se β é verdadeira em ℑ (e, assim, em ℑ’), vℑ’ (α§/k →β) = V em todas
as k-variantes de ℑ! Portanto, qualquer objeto de Uℑ é uma solução
para (α → β).
ii) se β é falsa em ℑ (e, assim, em ℑ’), vℑ’ (α§/k →β) = V se e só se
vℑ’ (α§/k )= F; e isso se dá, de acordo com E2 acima, quando ℑ’(k)
não é uma solução para α; em outras palavras, quando ℑ’(k) está no
complemento do CSolℑ(α), ou seja, quando ele é uma solução para
¬α!
3a) CSolℑ(β → α)
i) se β é verdadeira em ℑ, CSolℑ(β → α) = CSolℑ(α)
ii) se β é falsa em ℑ, CSolℑ(β → α) = Uℑ
Explicação: Um objeto será uma solução para esta fórmula se e somente se
vℑ(β→α)§/k = V na ℑ’ k-variante de ℑ na qual k o designa; como β é uma sentença,
vℑ’ (β → α)§/k = vℑ’ (β → α§/k) e
i) se β é verdadeira em ℑ (e, assim, em ℑ’), vℑ’ (β → α§/k) = V se e só
se vℑ’ (α§/k )= V e isso se dá, de acordo com E2 acima, quando ℑ’(k)
é uma solução para α;
ii) se β é falsa em ℑ (e, assim, em ℑ’), vℑ’ (β → α§/k) = V em todas as
k-variantes de ℑ! Portanto, qualquer objeto de Uℑ é uma solução
para (β → α).
Algumas equivalências e algumas implicações Como já vimos anteriormente, duas sentenças do cálculo de predicados são ditas logicamente equivalentes, se têm o mesmo significado formal. Claramente, se duas sentenças são logicamente equivalentes, as duas recebem o mesmo valor de verdade numa mesma interpretação. Por outro lado, dizemos que uma sentença implica logicamente uma outra se não existe interpretação que verifique a primeira e falsifique a segunda. Quando duas sentenças são equivalentes, tanto a primeira implica a segunda, quanto a segunda implica primeira. A relação de implicação entre duas sentenças é, portanto, mais fraca que a de equivalência. Se uma primeira sentença implica uma segunda sem que as duas sejam
88
equivalentes, então ocorre que a segunda não implica a primeira. Pelo que já foi exposto, podemos afirmar a existência de relações de equivalência e de implicação entre alguns pares de sentenças. I – Sejam α e β duas fórmulas com § como única variável livre; Vamos usar o símbolo ‘⇔‘ para expressar a equivalência e ⇒ para a implicação, no sentido acima indicado:
∀§ (α ∧ β) ⇔ ( ∀§ α ∧ ∀§ β)
Explicação: CSolℑ(α ∧ β) =Uℑ se e só se (CSol ℑ(α) ∩ CSol ℑ(β))=Uℑ e isso se dá
se e só se CSol ℑ(α) = Uℑ e CSol ℑ(β)=Uℑ.
∃§ (α v β) ⇔ ( ∃§ α v ∃§ β)
Explicação: CSolℑ(α v β) ≠ ∅ se e só se (CSol ℑ(α) ∪ CSol ℑ(β)) ≠ ∅ e isso se dá
se e só se CSol ℑ(α) ≠ ∅ ou CSol ℑ(β) ≠ ∅.
(∀§ α v ∀§ β) ⇒ ∀§ (α v β)
Explicação: se CSolℑ(α) =Uℑ ou CSolℑ(β) =Uℑ então, nos dois casos, temos que
(CSol ℑ(α) ∪ CSol ℑ(β))=Uℑ.
∃§ (α ∧ β) ⇒ ( ∃§ α ∧ ∃§ β)
Explicação: se há um objeto em (CSol ℑ(α) ∩ CSol ℑ(β)) então há um objeto em
CSol ℑ(α) e há um objeto em CSol ℑ(β).
EXERCÍCIO: 1. Suponha que α e β têm, ambas, uma única variável livre §;
a) explique por que não são equivalentes e dê exemplo de uma interpretação que verifique uma das sentenças mas não a outra:
i) ∃§ (α ∧ β) e ( ∃§ α ∧ ∃§ β)
ii) ∀§ (α v β) e (∀§ α v ∀§ β)
iii) ∀§ (α → β) e (∀§ α → ∀§ β)
89
Relações: Fórmulas com duas variáveis ξ e ξ’: Seja α uma fórmula com duas variáveis livres, § e §’. Tomemos
como paradigma de α uma fórmula do tipo ‘R2xy’. Queremos analisar os significados formais de sentenças obtidas aplicando a α quantificadores nas suas variáveis livres. Para tanto, partamos do significado formal da sentença ‘R2ab’. SF (Rab) : <δI (a), δI (b)> ∈ I(R2) Se considerarmos agora as fórmulas abertas (1) R2xb e (2) R2ay, podemos associar a cada uma delas o seu conjunto solução: 1. CSolℑ (R2xb): conjunto dos objetos tais que, se um deles for denotado por ‘a’
em uma I’ ‘a’-variante, R2ab será verdadeira segundo I’. Pode-se indicar esse
conjunto solução assim:
CSolℑ (R2xb) :{o ∈ UI : < o, δI (b) > ∈ I(R2)} , onde o é uma variável
metalingüïstica para os elementos de UI.
2. CSolℑ (R2ay) : conjunto dos objetos tais que, se um deles é denotado por ‘b’
em uma I’ ‘b’-variante, R2ab será verdadeira segundo I’. Dessa forma, podemos
escrever:
CSolℑ (R2ay) :{ o ∈ UI : <δI (a), o > ∈ I(R2)}
Aplicando, agora, um quantificador na variável livre dessas duas fórmulas, obteremos as quatro seguintes sentenças: (1.A) ∃xR2xb (1.B) ∀xR2xb (2.A) ∃yR2ay (2.B) ∀yR2ay. No que se segue, usaremos as notações ℜℜℜℜ, a, b como alternativas para I(R2), I(a),
I(b); ‘D(ℜℜℜℜ)’ indicará o domínio, CD(ℜℜℜℜ), o contradomínio de ℜℜℜℜ. Nesta exposição,
para facilitar a compreensão, usaremos o verbo “ver” como leitura ilustrativa da
relação ℜℜℜℜ; assim, se o par (a, b) estiver na relação ℜℜℜℜ diremos que a vê b ou que b
é visto por a.
90
Passemos ao exame do significado formal das quatro sentenças. (1.A) SF (∃xR2xb) : b ∈ CD(ℜℜℜℜ). Explicação: na relação ℜℜℜℜ há um par formado com b, onde este é o segundo
elemento do par - ou seja, b é visto por algum objeto do universo de interpretação.
Isso quer dizer que b está no contradomínio da relação, ou seja, b ∈ CD(ℜℜℜℜ).
(2.A) SF (∃yR2ay) : a ∈ D(ℜℜℜℜ). Explicação: na relação ℜℜℜℜ há um par formado com a, onde este é o primeiro
elemento do par - ou seja, a vê algum objeto do universo de interpretação, ou
ainda, a se relaciona por ℜℜℜℜ com algum objeto. Isso significa que a está no domínio
da relação, ou seja, a ∈ D (ℜℜℜℜ).
Posso distinguir em ℜ, além do domínio e do contradomínio, dois outros conjuntos: o dos mirantes (Mr) e o dos focos (Fc) de ℜ. Dizer que a relação ℜ tem mirante é dizer que há um x tal que para todo y, R2xy - é como se disséssemos que há um ponto que “vê” todos os pontos (inclusive ele próprio). Dizer que ℜ tem foco é dizer que há um y tal que para todo x, R2xy - é como se disséssemos que há um ponto que “visto” todos os pontos (inclusive ele próprio).
Por exemplo: Se ℜ é a relação menor ou igual, e o universo da interpretação os
números naturais, o número 0 (zero) é mirante de ℜ - dito de outro modo,
Mr (ℜ) = {0}. Contudo, se ℜ é ainda a relação menor ou igual, neste mesmo
universo, que é infinito, a relação não tem foco, pois não existe um número maior
do que todos os outros. Posso escrever isso assim: Fc (ℜ) = ∅. Mas, se o universo
da interpretação fosse outro, digamos UI = {0, 1, 2, ..., 9} (um universo finito) e
ℜ fosse ainda a relação menor ou igual, Fc (ℜ) = {9}.
Examinemos agora o significado formal das sentenças, mencionadas acima, (1.B) ∀xR2xb e (2.B) ∀xR2ax: (1.B) SF (∀xR2xb) : b ∈ Fc (ℜ) A sentença diz que qualquer objeto é solução para R2xb – ou, na nossa forma
ilustrativa de falar, que b é visto por todos os objetos. Isso quer dizer que b é um
foco de ℜ, ou seja que b pertence ao conjunto dos focos da relação.
91
(2.B) SF (∀yR2ay) : a ∈ Mr(ℜ) A sentença diz que qualquer objeto é solução para R2ay – ou: que a vê todos os
objetos. Sendo assim, a é um mirante da relação, a pertence ao conjunto dos
mirantes de ℜ
Observe-se agora que em cada uma das quatro sentenças ocorre uma constante individual. Se a trocamos por uma variável “nova” na sentença, obteremos uma fórmula com uma variável livre. Mais especificamente, se, em cada uma das quatro sentenças que acabamos de examinar, substituirmos a constante individual que nelas ocorre por uma variável nova (por exemplo, ‘a’ por ‘x’, ‘b’ por ‘y’), obteremos as seguintes fórmulas abertas: 1.A’. ∃xR2xy 1.B’. ∀xR2xy 2.A’. ∃yR2xy 2.B’. ∀yR2xy Como sabemos, fórmulas abertas têm conjuntos solução. Vejamos quais são os conjuntos solução que correspondem a essas fórmulas: 1.A’. CSolℑ (∃xR2xy) : CD(ℜ)
Qualquer objeto que esteja no contradomínio da relação (ℜ) é uma solução para ∃xR2xy. Assim, seu conjunto solução é o contradomínio de ℜ. 2.A’. CSolℑ (∃yR2xy) : D(ℜ)
Qualquer objeto que esteja no domínio da relação (ℜ) é uma solução para ∃yR2xy. Assim, seu conjunto solução é o domínio de ℜ. 1.B’. CSolℑ (∀xR2xy) : Fc(ℜ) Uma solução para essa fórmula deverá ser um objeto tal que todos os objetos se relacionam com ele, ou ainda, na nossa linguagem ilustrativa, um objeto visto por todos – ou seja, um foco da relação. Logo, o conjunto solução dessa fórmula será o conjunto dos focos da relação.
92
2.B’. CSolℑ (∀yR2xy) : Mr(ℜ) Uma solução para essa fórmula deverá ser um objeto que se relaciona com todos os objetos, ou, na nossa linguagem ilustrativa, um objeto que vê todos – um mirante da relação. Logo, o conjunto solução dessa fórmula será o conjunto dos mirantes da relação. Para representar graficamente esses conjuntos, comecemos por lembrar que ℜ ⊂ UI
2 , (e que UI2 = UI × UI). No desenho abaixo, cada elipse
é uma representação do universo, cada ponto representa um objeto, cada linha ligando um objeto em uma das elipses a um objeto na outra indica que o par formado por esses dois objetos pertence à relação. Tomemos, como exemplo, um universo com cinco objetos e uma relação contendo três pares – o objeto que aparece mais acima e à esquerda relaciona-se consigo mesmo e com um outro; e o objeto que aparece na linha inferior à direita relaciona-se com o que aparece na mesma linha à esquerda: UI UI . . . . . . . . . . Representamos abaixo um mirante da relação R2: . . . . . . . . . . E um foco seria representado graficamente do seguinte modo:
. . . .
. . . . . .
93
Cada uma das fórmulas abertas acima mencionadas determina um conjunto, a saber, o seu conjunto solução. Ora, a cada uma delas podemos aplicar um quantificador e obter uma das oito diferentes sentenças, abaixo: 1.A.a. ∃y∃x R2xy 1.A.b. ∀y∃x R2xy 1.B.a. ∃y∀x R2xy 1.B.b. ∀y∀x R2xy 2.A.a. ∃x∃y R2xy 2.A.b. ∀x∃y R2xy 2.B.a. ∃x∀y R2xy 2.B.b. ∀x∀y R2xy Já examinamos os conjuntos solução das quatro fórmulas abertas que geraram estas oito sentenças; podemos, agora, determinar o significado formal de cada uma delas. 1.A. a. SF (∃y∃x R2xy) : CD (ℜ) ≠ ∅
Se há objetos no CD (ℜ), há pelo menos um par na relação ℜ; então essa sentença significa que a relação não é vazia, SF (∃y∃x R2xy) : ℜ ≠ ∅ 1.A. b. SF (∀y∃x R2xy) : CD (ℜ) = UI Dizer que o contradomínio de uma relação é universal é diferente de dizer que a relação é ela mesma universal. Quando o contradomínio é o universo, cada objeto do universo aparece pelo menos uma vez como segundo elemento de um par da relação; e quando a relação é universal, todos objetos do universo se relacionam com todos por esta relação. 1.B. a. SF (∃y∀x R2xy) : Fc (ℜ) ≠ ∅
A relação tem um foco, ou seja, existe um objeto com o qual todos os objetos se relacionam. Quando isso se dá, o domínio da relação é universal – mas nem sempre, quando o domínio é universal, a relação tem um foco. 1.B. b. SF (∀y∀x R2xy) : Fc(ℜ)= UI
Neste caso, todos os objetos são focos da relação, ou seja, cada um dos objetos é tal que todos se relacionam com ele; mas, nesse caso, a
94
relação ℜ é universal; na nossa linguagem ilustrativa, se o conjunto dos focos é UI, todos objetos são vistos por todos. Então, SF(∀y∀x R2xy):ℜ=UI
2 2.A. a. SF (∃x∃y R2xy) : D (ℜ) ≠ ∅
Não é difícil compreender que, nesse caso, a relação não é vazia, pois só há objetos no domínio se também houver no contradomínio, i.e, se houver pelo menos um par na relação- em outras palavras, se ℜ ≠ ∅. Já tivemos oportunidade de ressaltar que duas sentenças que têm o mesmo
significado formal são ditas equivalentes; em qualquer interpretação considerada,
duas sentenças equivalentes terão o mesmo valor de verdade. Observamos então
que as sentenças ∃y∃x R2xy (1.A.a.) e ∃x∃y R2xy (2.A.a) têm o mesmo
significado formal; portanto, são equivalentes.
2.A. b. SF (∀x∃y R2xy) : D (ℜ) = UI
Dizer que o domínio de uma relação é universal é dizer que, para cada objeto do universo, existe um com o qual esse objeto forma um par. Isso não é o mesmo que afirmar que o contradomínio é universal, nem que a relação é universal! 2.B. a. SF (∃x∀y R2xy) : Mr (ℜ) ≠ ∅ Existe um objeto que se relaciona com todos – a relação tem pelo menos um mirante. Note-se que quando existe mirante, o contradomínio é universal; mas a recíproca não vale – ou seja, o contradomínio pode ser universal sem que a relação tenha um mirante! 2.B. b. SF (∀x∀y R2xy) : Mr (ℜ) = UI Se todos os objetos são mirantes, todos se relacionam com todos, ou seja, a relação é universal. Essa sentença significa, portanto, que ℜ=UI
2 . Verificamos então que as sentenças ∀y∀x R2xy (1.B. b.) e ∀x∀y R2xy (2.B. b.) têm o mesmo significado formal e são, assim, sentenças equivalentes
95
Aplicando quantificadores, construímos oito diferentes sentenças a partir da fórmula inicial ‘R2xy’ e vimos que com elas obtemos a expressão de seis significados formais distintos. Podemos agora retomar estes seis significados formais distintos e pensar em suas negações: Negação de 1.A. a.: ¬∃y∃x R2xy SF (¬∃y∃x R2xy): CD(ℜ) = ∅
Se o contradomínio de uma relação é vazio, então a relação mesma também é vazia. Portanto, SF (¬¬¬¬∃∃∃∃y∃∃∃∃x R2xy) : ℜℜℜℜ = ∅∅∅∅
Negação de 2.A. a.: ¬∃x∃y R2xy SF (¬∃x∃y R2xy) : D (ℜ) = ∅
Do mesmo modo, se o domínio de uma relação é vazio, a relação é um conjunto vazio. Assim, SF (¬¬¬¬∃∃∃∃x∃∃∃∃y R2xy) : ℜℜℜℜ = ∅∅∅∅
As duas negações acima, a saber, ¬∃y∃x R2xy e ¬∃x∃y R2xy, também são ditas equivalentes, pois têm o mesmo significado formal. Negação de 1.B. b.: ¬∀y∀x R2xy SF (¬∀y∀x R2xy): Fc (ℜ) ≠ UI
Há um par de objetos do universo que não está na relação R2; pois há pelo menos um objeto que não é visto por todos (e, portanto, também há pelo menos um objeto que não vê todos). Assim, SF (¬¬¬¬∀∀∀∀y∀∀∀∀x R2xy) : ℜℜℜℜ ≠≠≠≠ UI
2 Negação de 2.B. b.: ¬∀x∀y R2xy SF (¬∀x∀y R2xy) : Mr (ℜ) ≠ UI
Ou ainda, SF (¬¬¬¬∀∀∀∀x∀∀∀∀y R2xy) : ℜℜℜℜ ≠≠≠≠ UI2
As duas negações acima, por sua vez, também têm ambas o mesmo significado formal, i.e. as sentenças ¬∀y∀x R2xy e ¬∀x∀y R2xy são equivalentes. Com as quatro novas sentenças, obtemos, então, dois novos significados formais.
96
OBSERVAÇÃO:Se há dois quantificadores seguidos e eles são da mesma quantidade, a ordem em que eles aparecem não importa. Generalizando: se numa sentença ocorre uma seqüência de quantificadores do mesmo tipo (todos existenciais ou todos universais), qualquer permutação desses quantificadores nos dá uma sentença equivalente. Observe-se que isso só vale se entre dois quantificadores da seqüência não houver negação. Assim, por exemplo, a equivalência vale para ∴x∴y∴zRxyz e ∴z∴x∴yRxyz, para ¬∴z∴x∴yRxyz e ¬∴z∴y∴xRxyz, mas não vale para ∴x∴y¬∴zRxyz e ∴z∴y¬∴xRxyz; vale para ∀x∀y∀z¬Rxyz e ∀z∀x∀y¬Rxyz, mas não para ∀x¬∀y∀zRxyz e ∀z¬∀x∀yRxyz. Vale para ∀y∴x∴zRxyz e ∀y∴z∴xRxyz mas não para ∴x∀y∴zRxyz e ∴z∴x∀yRxyz.
Negação de 1.A. b.: ¬∀y∃x R2xy SF (¬∀y∃x R2xy) : CD(ℜ) ≠ UI Negação de 1.B. a.: ¬∃y∀x R2xy SF (¬∃y∀x R2xy) : Fc (ℜ) = ∅ Negação de 2.A. b.: ¬∀x∃y R2xy SF (¬∀x∃y R2xy) : D (ℜ) ≠ UI Negação de 2.B. a.: ¬∃x∀y R2xy SF (¬∃x∀y R2xy) : Mr(ℜ) = ∅ Vimos que, usando dois quantificadores aplicados a fórmulas com duas variáveis
livres, obtínhamos os seguintes seis significados formais distintos, expressos por
fórmulas com dois quantificadores:
1. ℜ ≠ ∅ ∃x∃yR2xy 2. D(ℜ) = UI ∀x∃yR2x 3. CD (ℜ) = UI ∀y∃xR2xy 4. Fc (ℜ) ≠ ∅ ∃y∀xR2xy 5. Mr (ℜ) ≠ ∅ ∃x∀yR2xy 6. ℜ= UI
2 ∀x∀yR2xy
Agora podemos listar mais seis afirmações, distintas destas seis primeiras, que são
expressas pelas negações das afirmações acima: 7. ℜ = ∅ ¬∃x∃yR2xy 8. D (ℜ) ≠ UI ¬∀x∃yR2xy 9. CD (ℜ) ≠ UI ¬∀y∃xR2xy 10. Fc (ℜ) = ∅ ¬∃y∀xR2xy 11. Mr (ℜ) = ∅ ¬∃x∀yR2xy 12. ℜ ≠ UI
2 ¬∀x∀yR2xy
97
Já vimos que, se ℜ≠∅ é o significado formal de uma fórmula α, então esse significado determina as condições para que uma qualquer interpretação atribua V a α. Por exemplo, como o significado formal de ∃x∃yR2xy é ℜ≠∅, para que ∃x∃yR2xy seja V numa interpretação I, basta que I(R2) ≠ ∅. Ou seja, que haja um par em I(R2). Portanto, qualquer uma das interpretações abaixo, verifica ∃x∃yR2xy: UI = naturais UI’ = {0,1,2} UI’’ = naturais I(R2) = < I’(R2) = < I’’(R2) = {(1,4), (32,3)} Os exemplos acima (I(R2), I’(R2) e I’’(R2) ) são exemplos de relações que, nos seus respectivos universos, verificam ∃x∃yR2xy. Vejamos outro exemplo. Como o significado formal de ∀x∃yR2xy é D(ℜ)=UI, qualquer interpretação para R onde todo objeto do universo vê algum objeto verificará ∀x∃yR2xy. Por exemplo, UI = naturais UI’’’ = {0,1,2} UI’’’’ = {1,2,3} I(R2) = < I’’’(R2) = ≤ I’’’’(R2) = {(1,2), (2,1), (1,1), (3,3)}
Mas a interpretação I’ tal que UI’ = {0,1,2} e I’(R2) = < não verifica ∀x∃yR2xy pois, como 2 não é menor que nenhum número de UI’, 2∉D(ℜ). Com isso, temos uma prova de que ¬∃x∃yR2xy e ∀x∃yR2xy não são equivalentes. É possível fazer uma prova como essa para as 12 sentenças acima.
EXERCÍCIO: construir exemplos de uma relação R2 que ilustrem cada uma das doze sentenças acima, mostrando que os doze significados formais são distintos. É importante observar que, embora nenhuma das doze sentenças seja equivalente a uma outra, pode ser que uma implique outra. Mas, se isso ocorrer, o inverso não ocorre. Ou seja, toda interpretação que verifica ∀x∀yR2xy obviamente também verifica ∃x∃yR2xy, por exemplo, mas nem toda interpretação que verifica ∃x∃yR2xy verifica ∀x∀yR2xy.
98
Com duas variáveis quantificadas só é possível expressar 12 significados formais distintos Vamos lembrar agora qual foi o processo de obtenção das sentenças que estamos analisando aqui: i. R2xy ii. Q§R2xy iii. Q’§’ Q§ R2xy Portanto, podemos pensar agora em (1) ¬R2xy, em (2) ¬Q§ R2xy e em (3) ¬ Q’§’ Q§ R2xy. Já vimos o caso (3), mas não vimos ainda os casos (1) e (2). Se considerarmos que a forma de uma sentença do tipo que estamos analisando é ___ Q’§’ ___ Q§ ___ R2xy onde ‘___’ representa o espaço em que pode figurar, ou não, uma negação, para cada fórmula α deste tipo, há 23 possibilidades de combinação de símbolos. Isto significa que, se quisermos analisar o conjunto das fórmulas deste tipo, teremos que analisar, a partir de uma α, sessenta e quatro (64) fórmulas que são tipograficamente distintas, usando-se os símbolos [¬], [Q’§’], [Q§] e [R2xy], sendo que o símbolo [¬] irá ocorrer no máximo três vezes em cada uma (sem considerarmos ocorrências de dupla negação). Essas sessenta e quatro sentenças só são capazes de expressar os doze significados formais distintos que vimos acima. Seja α uma fórmula da forma S β, onde β é uma fórmula contendo, no máximo duas variáveis livres, § e §’, e S é uma seqüência composta por quantificadores (Q, Q’) em § e §’ e negações, de tal maneira que S contém pelo menos um Q em § e um Q’ em §’. Por enquanto, vamos pensar em dois quantificadores e várias negações. O significado formal de α está em um dos doze significados possíveis vistos acima (1 - 12). A prova dessa afirmação só é vista num curso mais avançado, mas é possível dar uma indicação do que faz isso ser assim.
99
Dizemos que duas sentenças, α e α’, são equivalentes se e somente se para toda interpretação I temos que νI (α) = νI (α’). Há determinados casos de equivalências que podemos demonstrar para toda e qualquer interpretação I usando a definição de verdade. Por exemplo: (i) νI (α) = νI (¬¬α) em qualquer interpretação I. Portanto, α é equivalente a ¬¬α. (ii) νI (∃§α) = νI (¬∀§¬ α) em qualquer interpretação I. Portanto, ∃§ α é equivalente a ¬∀§¬ α. Demonstração desta equivalência:
1. vI(∃ξα) = V sse CSolℑ(α) ≠ ∅ - pois é esse o significado formal de ∃ξα.
2. Ora, CSolℑ(α) ≠ ∅ sse existe um objeto o∈UI tal que o∉ Clp CSolℑ (α).
3. Isso ocorre sse Cpl CSolℑ(α) ≠ UI.
4. Mas, se Cpl CSolℑ(α)≠UI, existe um objeto que não pertence ao CSolℑ(¬α), ou seja,
CSolℑ(¬α) ≠ UI.
5. Nesse caso, vI(∀ξ¬α)=F.
6. Logo, vI(¬∀ξ¬α)=V.
(Provamos que se vI(∃ξα)=V, então vI(¬∀ξ¬α)=V. Falta provar que se
vI(∃ξα)=F, então vI(¬∀ξ¬α)=F.)
7. Se vI(∃ξα)=F, CSolℑ(α)=∅; pois, como o significado formal de ∃ξα é CSolℑ(α)≠∅,
se vI(∃ξα)=F, CSolℑ(α)=∅.
8. Portanto, nenhum objeto o∈UI é solução para α.
9. Logo, Cpl CSolℑ(α)=Uℑ.
10. Como Cpl CSolℑ(α)=Uℑ é o significado formal de ∀ξ¬α, vℑ (∀ξ¬α)=V.
11. Portanto, vℑ (¬∀ξ¬α)=F.
Assim, provamos que se vℑ(∃ξα)=V, então vℑ(¬∀ξ¬α)=V (linhas 1-6) e que
se vℑ(∃ξα)=F, então vℑ(¬∀ξ¬α)=F (linhas 7 a 11). Com isso, provamos que vℑ
(∃ξα)=V se e somente se vℑ (¬∀ξ¬α)=V.
100
(iii) νI (∀§ α) = νI (¬∃§¬ α) em qualquer interpretação I. Ou seja, ∀§ α é equivalente a ¬∃§¬ α. A demonstração desta equivalência é análoga à feita em (ii). Fica como
exercício.
Observação: Uma vez provadas essas equivalências, segue-se uma
importante conseqüência: não é necessário que tenhamos na nossa linguagem os
dois quantificadores, ‘∀‘ e ‘∃‘. A linguagem não perderia nada em seu poder de
expressão se dispuséssemos de um deles apenas (e da negação, é claro!).
A partir da equivalência (ii) (ou seja, do fato de que ∃§ α é equivalente a ¬∀§¬ α) e sabendo que a negação de uma fórmula é equivalente à negação da sua equivalente, temos que: (iv) ¬∃§α é equivalente a ¬¬∀§¬ α, ou seja, ¬∃§α é equivalente a ∀§¬ α. Por este mesmo raciocínio, sabemos, a partir da equivalência (iii) (ou seja, do fato de que ∀§α é equivalente a ¬∃§¬ α ) que (v) ¬∀§α é equivalente a ¬¬∃§¬ α, ou seja, ¬∀§α é equivalente a ∃§¬ α. Agora, tomemos uma fórmula α do tipo S β - i.e. β é uma fórmula contendo no máximo duas variáveis livres, § e §’, onde S é uma seqüência composta por quantificadores Q§ e Q’§’ e por negações, tomados em uma ordem qualquer. Obtemos a fórmula S’β, cortando de S qualquer número par m (m>0) de ocorrências seguidas de ‘¬‘. 1. Obtemos, em tantos passos quantos forem necessários, uma fórmula S’β
da seguinte maneira: consideramos cada ocorrência de ‘¬‘ em S’; a partir da ocorrência que está mais à direita na fórmula, vamos trocando ‘Q’§’¬’ ‘ por ‘¬Q§’ ’ e eliminando as duplas negações eventuais.
101
Exemplos:
a) ¬∀x¬¬∃y¬¬ R2xy equivale a
¬∀x∃y R2xy pela regra (i) aplicada duas vezes.
Assim, SF (¬∀x¬¬∃y¬¬ R2xy) = SF (¬∀x∃yR2xy) : D (ℜ) = UI
b) ∃x¬¬¬∀y¬ R2xy equivale a
∃x¬∀y¬ R2xy pela regra (i). Mas isto equivale a
∃x¬¬∃y R2xy pela regra (iv). Isto equivale a
∃x∃yR2xy pela regra (i).
Assim, SF (∃x¬¬¬∀y¬ R2xy) = SF (∃x∃yR2xy) : ℜ ≠ ∅.
c) ¬∃x¬∀y¬ R2xy equivale a
¬∃x¬¬∃y R2xy pela regra (iv). Isto equivale a
¬∃x∃y R2xy pela regra (i).
Então, SF (¬∃x¬∀y¬ R2xy) = SF (¬∃x∃yR2xy) : ℜ = ∅.
Vimos que tínhamos 64 sentenças diferentes do tipo S β, ao considerarmos todas diferentes possibilidades de combinação de símbolos em S β, usando no máximo três negações (‘¬’). São sessenta e quatro, uma vez que partimos de oito sentenças (1Aa, 1Ab,... até 2Bb) e cada uma delas dá origem a oito sentenças, quando temos a possibilidade de acrescentar uma negação antes de um ou dois dos quantificadores e/ou da fórmula que a eles se segue . Assim, ___ Q’§’ ___ Q§ ___ R2xy é a forma das sentenças que podem ser engendradas, onde ‘___’ é o lugar em que ‘¬’ pode aparecer. Tomemos como exemplo a seguinte fórmula:
∃x∃y R2xy Esta gera oito possibilidades de fórmulas fechadas usando-se a negação: 1) ∃x ∃y R2xy 5) ¬∃x ∃y R2xy 2) ∃x ∃y ¬ R2xy 6) ¬∃x ∃y ¬R2xy 3) ∃x ¬∃y R2xy 7) ¬∃x ¬∃y R2xy 4) ∃x ¬∃y ¬ R2xy 8) ¬∃x ¬∃y ¬R2xy
102
No entanto, dadas as regras (i)-(v) acima, podemos sempre “trazer a negação para fora”. Por exemplo: 6) ¬∃x∃y¬R2xy é equivalente a ¬∃x¬∀yR2xy, que é equivalente a ¬¬∀x∀yR2xy que, por sua vez, é equivalente a ∀x∀yR2xy. Que isso possa ser feito em todos os 64 casos não será provado aqui, mas os exemplos nos dão uma indicação de como isso pode ser feito. Por outro lado, se usarmos mais do que uma negação em cada vaga ‘___’, a sentença igualmente recai sobre um dos doze significados vistos, já que podemos “cortar” dupla negação e aplicarmos as outras regras. Algumas equivalências entre sentenças: Seja α uma sentença. Seja β uma sub-fórmula de α. Seja γ uma fórmula tal que (i) β e γ tem as mesmas variáveis livres §1,..., §n e (ii) (β§1,..., §n/k1,...,kn ↔ γ §1,..., §n/k1,...,kn) é uma equivalência tautológica. Então, SF[α]=SF[αβ/γ]. Por exemplo: como ((F1x→G1x)x/a ↔ ¬(F1x∧¬G1x)x/a),
SF[∀x(F1x→G1x)] = SF[∀x¬(F1x∧¬G1x)].
É importante, portanto, ter em mente algumas equivalências
tautológicas.
(¬¬α ↔ α)
((α→β) ↔ (¬β→¬α))
((α∧β) ↔ ¬(¬α∨¬β))
((α∨β) ↔ ¬(¬α∧¬β))
((α→β) ↔ (¬α∨β)
((α→β) ↔ ¬(α∧¬β))
((α∧β) ↔ ¬(α→¬β))
((α∨β) ↔ (¬α→β))
103
Vejamos em mais detalhe por que, por exemplo, SF[∀x(F1x→G1x)] = SF[∀x(¬(F1x∧¬G1x)]: 1. Para qualquer interpretação I, vℑ(∀x(F1x→G1x))=V se e só se
CSolℑ[(F1x→G1x)]=Uℑ.
2. Para qualquer interpretação I, para qualquer objeto o de Uℑ, o∈ CSolℑ[(F1x→G1x)]
se e só se vℑ’[(F1a→G1a)]=V para a I’ a-variante de I tal que I’(a)=o.
3. Ora, como ((α→β)↔¬(α∧¬β)) é um esquema tautológico, temos que
vℑ’[(F1a→G1a)]=V para a I’ a-variante de I tal que I’(a)=o se e só se
vℑ’[¬(F1a∧¬G1a)]=V para a I’ a-variante de I tal que I’(a)=o.
4. Mas vℑ’[¬(F1a∧¬G1a)]=V para a I’ a-variante de I tal que I’(a)=o se e só se o∈
CSolℑ[¬(F1x∧¬G1x)].
5. Ou seja, o∈ CSolℑ[(F1x→G1x)] se e só se o∈ CSolℑ[¬(F1x∧¬G1x)].
6. Como isso vale para qualquer objeto o∈UI, para qualquer interpretação I,
CSolℑ[(F1x→G1x)] = Uℑ se e só se CSolℑ[(¬(F
1x∧¬G1x)] = Uℑ.
Equivalências pela “distribuição do quantificador” Sejam α e β duas fórmulas com uma única variável livre §. Há duas possibilidades: (i) § ocorre livre em α e β; (ii) § ocorre livre em uma das duas mas não em ambas. (i) Se § ocorre livre em α e β, temos as seguintes equivalências: SF[∀§(α∧β)] = SF[(∀§α∧∀§β)] SF[∃§(α∨β)] = SF[(∃§α∨∃§β)] SF[∃§(α→β) = SF[(∀§α→∃§β)] (ii) Suponha agora que § ocorre livre em β, mas não em α. (Para marcar essa diferença, escreveremos β§, ao invés de β.) Vamos analisar o SF de sentenças do tipo Q§(α ∗ β§). Temos três casos: Caso 1) ∗ ∈ {∧, ∨} :
Q § (α ∗ β§) é equivalente a (α ∗ Q § β§)
104
Ou seja,
SF[∀§(α∧β§)] = SF[(α∧∀§β§)] SF[∃§(α∧β§)] = SF[(α∧∃§β§)]
SF[∀§(α∨β§)] = SF[(α∨∀§β§)] SF[∃§(α∨β§)] = SF[(α∨∃§β§)]
Caso 2) ∗ ∈ {→} :
Q§(α ∗ β§) equivale a (α → Q§β§)
e Q§(β§ ∗ α) equivale a (Q’§β§ → α) - onde se Q é ∀, Q’ é ∃; se Q é ∃, Q’ é ∀
Ou seja,
SF[∀§(α→β§) = SF[(α→∀§β§)] SF[∃§(α→β§) = SF[(α→∃§β§)]
SF[∀§(β§→α) = SF[(∃§β§→α)] SF[∃§(β§→α) = SF[(∀§β§→α)]
Caso 3) ∗ ∈ {↔}
Não há uma equivalência interessante para Q§(α ∗ β§) neste caso. Pode-se pensar que (1) Q§(α ↔ β§) é equivalente a Q§((α → β§) ∧ (β§ → α)).
(2) Se Q é ∀, ∀§(α ↔ β§) equivale a ∀§((α → β§) ∧ (β§ → α)) ,
(3) que equivale a (∀§(α → β§) ∧ ∀ξ(β§ → α)) , pelo primeiro caso de
equivalência que acabamos de ver;
(4) esta última sentença equivale, por sua vez, a ((α→∀§β§)∧(∃§β§→α)) pelo
segundo caso de equivalência que vimos, acima.
(2’) Se Q é ∃, ∃§(α ↔ β§) equivale a ∃§((α → β§) ∧ (β§ → α)) ,
(3’) como o ‘∃‘ não é “distribuído” na conjunção, devemos tomar outra
equivalência. ∃§((α → β§) ∧ (β§ → α)) equivale a ∃§((α ∧ β§) ∨ (¬α ∧ ¬β§)),
(4’) que por sua vez equivale a (∃§(α ∧ β§) ∨ ∃§(¬α ∧ ¬β§)), pelo primeiro caso
que vimos;
(5’) esta última equivale a ((α ∧ ∃§β§) ∨ (¬α ∧ ∃§¬β§)), também pelo primeiro
caso.
Temos assim: SF[∀§(α↔β§)] = SF[((α→∀§β§)∧(∃§β§→α))] SF[ ∃§(α↔β§)] = SF[((α∧∃§β§)∨(¬α∧¬∀§β§))]
105
Sentenças universais – alguns paradigmas Vamos nos deter um pouco no estudo da forma geral de um tipo de sentença muito comum: as ditas “universais restritas”, ou seja, sentenças que afirmam uma propriedade qualquer de um certo conjunto de objetos que constituem um subconjunto do universo de discurso em questão. Mais precisamente, essas sentenças afirmam que algo vale para todos os objetos que satisfazem uma certa condição. A forma geral dessas sentenças é, então, a seguinte: Para qualquer objeto do universo, se ele satisfaz a condição α, então pode-se afirmar que vale para ele a atribuição β. Como já vimos, isso se expressa pelo esquema: ∀§ ( α → β ) , onde α e β são fórmulas nas quais § ocorre como única variável livre. Ora, a condição em causa pode ser formulada como uma condição para objetos tomados isoladamente, mas às vezes também pode se constituir numa condição para objetos tomados dois a dois, três a três, e assim por diante. Em outras palavras, a condição pode ser formulada para qualquer n-upla que esteja numa certa relação n-ária. Nesse caso, a fórmula α , que expressa essa relação – ou seja, a condição a ser preenchida pela n-upla – deve ser uma fórmula com n variáveis livres; e o esquema terá a forma:
∀§1∀§2 ...∀§n ( α → β )
Por outro lado, a fórmula β terá no máximo §1§2...§n como variáveis livres; mas, ao contrário de α, não é necessário que todas essas variáveis ocorram livres em β. Nesse último caso, os quantificadores que ocorrem em α mas não em β podem ser trazidos para dentro do parêntesis – mas, como já vimos, mudando sua quantidade. Por exemplo, vamos supor que §2 ocorra em α mas não em β. Nesse caso, ∀§1∀§2∀§3 ...∀§n ( α → β ) também pode ser escrita pela equivalente:
∀§1∀§3 ...∀§n (∃§2α → β )
106
Por exemplo, suponhamos que, numa interpretação cujo universo é um dado conjunto de pessoas, tenhamos o predicado binário M2 para a relação ”mãe de” e o predicado unário A1 para o conjunto dos que têm mais de 50 anos; se quisermos expressar a afirmação (possivelmente falsa, mas isso aqui não tem importância) “Todas as bisavós (em linhagem materna) têm mais de 50 anos” , podemos escrever, alternativamente, ∀x∀y∀z∀w(((Mxy ∧ Myz) ∧ Mzw) → Ax) ou
∀x (∃y∃z∃w ((Mxy ∧ Myz) ∧ Mzw) → Ax) ou ainda
∀x∀y∀z ((Mxy ∧ Myz) ∧ ∃w Mzw) → Ax), para dar apenas três exemplos, dentre várias outras fórmulas equivalentes. Expressão de universos e conjuntos finitos Vamos agora mostrar como podemos, com auxílio do predicado da identidade, caracterizar universos ou conjuntos finitos. Na verdade, podemos expressar os seguintes tipos de afirmação (e, obviamente, suas negações)
1) Há pelo menos n objetos no universo; 2) Há, no máximo, n objetos no universo; 3) Há exatamente n objetos no universo; 4) Há pelo menos n objetos que satisfazem α; 5) Há, no máximo, n objetos que satisfazem α; 6) Há exatamente n objetos que satisfazem α;
107
onde α é uma fórmula com uma variável livre, §. Vamos aqui escrever αi para a fórmula que resulta da substituição de todas as ocorrências livres de § em α por ocorrências de §i. Para n=1: A afirmação 1 não precisa ser feita; trata-se de um pressuposto da semântica. Por força dessa mesma razão, 2) e 3) têm, nesse caso, o mesmo significado, que pode, alternativamente, ser expresso por: ∃x ∀y x=y ou ∀x ∀y x=y . Note-se que esse é um caso em que a quantificação existencial e a quantificação universal de uma fórmula têm o mesmo significado formal! As sentenças seguintes podem ser assim expressas: 4) ∃ § α (há pelo menos um objeto no CSolℑ (α) ) 5) ∀§ ∀§1 ((α ∧ α1)�§=§1) (há no máximo um objeto no CSolℑ (α) ) 6) ∃ § (α ∧ ∀§1 (α1�§=§1) ) (há exatamente um objeto no CSolℑ (α) )
Para n=2 Há pelo menos dois objetos no universo ∃§1 ∃§2 ¬ §1=§2 Há no máximo dois objetos no universo ∃§1 ∃§2 ∀§ (§=§1 v §=§2) ou ∀§1 ∀§2 ∀§ ((§=§1 v §=§2) ∨ §1=§2)
Obs: Aqui também temos um caso onde os dois primeiros quantificadores podem ser ambos universais ou ambos existenciais – mas o terceiro, ao contrário, precisa ser universal!
Há exatamente dois objetos no universo ∃§1 ∃§2 (¬§1=§2 ∧ ∀§ (§=§1 v §=§2))
108
Há pelo menos dois objetos no CSolℑ(α)
∃§1 ∃§2 (¬§1=§2 ∧ (α1 ∧ α2)) Há no máximo dois objetos no CSolℑ(α)
∀§1 ∀§2 ∀§3 ((( α1 ∧ α2) ∧ α3) �(( §1=§2 v §1=§3) v §2=§3)) , ou Há exatamente dois objetos no CSolℑ(α)
∃§1 ∃§2 ((¬§1=§2 ∧ (α1 ∧ α2)) ∧ ∀§ (α �(§= §1 v §= §2))) Generalizando, para n>2, Há pelo menos n objetos no universo ∃§1∃§2...∃§n (¬§1=§2 ∧(...(¬§1=§n ∧ (¬§2=§3 ∧ (...¬§n-1=§n)...)...) Há no máximo n objetos no universo ∀§1...∀§n-1∀§n∀§(§=§1 v...(§=§n-1 v §=§n)...) ou ∃§1... ∃§n-1∃§n∀§(§=§1 v...(§=§n-1 v §=§n)...) Há exatamente n objetos no universo ∃§1∃§2... ∃§n ((¬§1=§2 ∧(...(¬§1=§n ∧ (¬§2=§3 ∧ (...¬§n-1=§n)...)...) ∧ ∧ ∀§ (§1=§2 v (§1=§2 v (...v §=§n)...))) Há pelo menos n objetos no CSolℑ(α)
∃§1∃§2...∃§n ((¬§1=§2 ∧(...(¬§1=§n ∧ (¬§2=§3 ∧ (...¬§n-1=§n)...)...) ∧ ∧ (α1∧ (α2 ∧... (αn-1 ∧ αn)...)))) Há no máximo n objetos no CSolℑ(α)
∀§1...∀§n-1∀§n∀§(α ∧ (α1∧ (α2 ∧...(αn-1 ∧ αn)...)) � (§=§ v... (§=§n-1 v §=§n)...) Há exatamente n objetos no CSolℑ(α) ∃§1∃§2...∃§n (((¬§1=§2 ∧(...(¬§1=§n ∧ (¬§2=§3 ∧ (...¬§n-1=§n)...)...)... ∧ ... ∧ (α1∧ (α2 ∧...(αn-1 ∧ αn)...)))) ∧ ∀§(α � (§= §1 v(§= §2 v(...v §= §n)))))
109
Com a identidade, podemos ainda expressar vários significados interessantes. Com a sentença: ∀x ∃y (R2xy ∧ ∀z (R2xz � y = z)), por exemplo, podemos dizer que uma relação binária é uma função! De um modo geral, para dizer que uma determinada fórmula, α, contendo §1,§2,...,§n,§’ como únicas variáveis livres, expressa uma operação n-ária, com §1,§2,...,§n, como argumentos e §’ como valor, usamos a fórmula: ∀§1...∀§n-1∀§n∃§’ (α ∧ ∀§’’ (α §’/§’’ � §’= §’’)) onde §’’ não ocorre em α e α §’/§’’ é o resultado da substituição de todas as ocorrências de §’ por ocorrências de §’’. Expressão de outras propriedades de relações binárias
Já vimos como podemos expressar várias propriedades de relações binárias, tais como ser ou não vazia, ser ou não universal, ter ou não domínio ou contradomínio universal, ter ou não foco ou mirante, ser ou não uma operação. Há algumas outras propriedades ainda que podem ser formalmente expressas. Para facilitar a leitura, trabalharemos com exemplos paradigmáricos da linguagem. Seja, então, ‘R’ um predicado interpretado por uma relação binária R 1) R é reflexiva : ∀x Rxx – todo objeto do universo relaciona-se consigo mesmo por R
2) R é irreflexiva: ∀x ¬ Rxx – nenhum objeto do universo relaciona-se consigo mesmo por R Observe-se que essa afirmação é distinta da afirmação de que R não é reflexiva, ou seja, que há um objeto que não se relaciona consigo mesmo, e que corresponde à negação de 1).
R é simétrica: ∀x ∀y( Rxy � Ryx) - dado um par qualquer, se ele está na relação, o par inverso também está.
110
3) R é assimétrica: ∀x ∀y( Rxy � ¬ Ryx) - dado um par qualquer, se ele está na relação, o par inverso não está. 4) R é anti-simétrica: ∀x ∀y(¬ x=y � (Rxy � ¬ Ryx)) - dado um par de objetos distintos, se ele está na relação, o par inverso não está. 5) R é conexa : ∀x ∀y (¬ x=y � (Rxy v Ryx)) - dado um par de objetos distintos, ou ele ou seu inverso está na relação R
6) R é fortemente conexa : ∀x ∀y (Rxy v Ryx) - dado um par qualquer, ou ele ou seu inverso está na relação R
7) R é transitiva: ∀x ∀y ∀z ((Rxy ∧ Ryz) � Rxz) - se um mesmo objeto aparece num par da relação como segundo elemento e em outro par da relação como primeiro elemento, então o par cujo primeiro elemento é o primeiro elemento do primeiro par e cujo segundo elemento é o segundo elemento do segundo par sempre estará também nessa relação,
8) R é intransitiva: ∀x ∀y ∀z ((Rxy ∧ Ryz) � ¬Rxz) - se um mesmo objeto aparece num par da relação como segundo elemento e em outro par da relação como primeiro elemento, então o par cujo primeiro elemento é o primeiro elemento do primeiro par e cujo segundo elemento é o segundo elemento do segundo par nunca estará nessa relação,
9) R é euclidiana: ∀x ∀y ∀z ((Rxz ∧ Ryz) � (Rxy v Ryx)) - se dois objetos aparecem como primeiros elementos em pares que têm o mesmo segundo elemento, então eles também formam um par da relação.
111
Conceitos semânticos fundamentais da lógica de primeira ordem Vamos, agora, introduzir os conceitos centrais da semântica da lógica de primeira ordem. Poderíamos até mesmo dizer que tudo o que foi adiantado até aqui visou poder chegar à definição rigorosa desses conceitos. A) MODELO (de primeira ordem) Uma interpretação I é modelo de um conjunto de sentenças Γ se, para todo α ∈ Γ, νI (α) = V. O conceito de modelo é um conceito que se aplica a conjuntos de sentenças. Porém, por uma licença de linguagem, dizemos também que uma interpretação I é modelo de α (i.e.da sentença α) para significar que I é modelo do conjunto unitário {α}. Observemos que um modelo de um conjunto é também um modelo verifuncional do mesmo, mas nem todo modelo verifuncional é um modelo (de primeira ordem). B) CONSISTÊNCIA Um conjunto de sentenças Γ é consistente se Γ tem pelo menos um modelo. Se Γ não tem modelo, Γ é dito inconsistente. Examinemos alguns exemplos: (1) Γ = {∀x (F1x → G1x), ∃y R2ya, ∃x¬ G1x} SF (∀x (F1x → G1x)) : CSolℑ (F1x) ⊂ CSolℑ (G1x) SF (∃y R2ya) : ℑ (a) ∈ CD ℑ(R2) SF (∃x¬ G1x) : CSolℑ (G1x) ≠ UI Modelo de Γ (exemplo):
UI = {1} I(F1) = ∅ I(G1) = ∅ I(R2) = {(1, 1)} I(a) = 1
112
(2) Γ = {∀x (F1x → G1x), ∃x F1x, ¬∃x G1x} SF (∀x (F1x → G1x)) : CSolℑ (F1x) ⊂ CSolℑ (G1x) SF (∃x F1x) : CSolℑ (F1x) ≠ ∅ SF (¬∃x G1x) : CSolℑ (G1x) = ∅
Esse conjunto não tem modelo pois não é possível realizar simultaneamente as três condições acima.
Claramente, se um conjunto é consistente, ele é verifuncionalmente
consistente; a recíproca, contudo, não vale; por exemplo, o conjunto
acima, embora inconsistente, é verifuncionalmente consistente.
C) COMPATIBILIDADE: Uma sentença α é dita compatível com Γ se e somente se Γ ∪ {α} é um conjunto consistente. D) VALIDADE:
Temos três situações possíveis no que diz respeito aos modelos de uma sentença α: 1º) toda interpretação é modelo de α; 2º) nenhuma interpretação I é modelo de α. 3º) algumas interpretações são modelos de α e outras não são; 1º) No primeiro caso, dizemos que a sentença é válida. Assim, uma sentença α é válida se e somente se νI (α) = V para toda interpretação I. Por exemplo, são válidas as sentenças (∀xF1x → F1a) a = a (∀xF1x → ∃xF1x) ∀x∀y (x = y → y = x) (∀x (F1x → G1x) → (∃xF1x → ∃xG1x)) (∃xF1x ↔ ¬∀x¬F1x) (∀xF1x ∨ ¬∀xF1x) (∃x∀y x = y ↔ ∀x∀y x = y)
113
Observação: O conceito de sentença válida é diferente do conceito de sentença
tautológica. Uma sentença α é válida se toda interpretação é modelo de α. A
correlação que se pode fazer entre ser válida e ser tautológica é a de que toda
tautologia é uma sentença válida, mas nem toda sentença válida é tautologia. O
conjunto das valorações booleanas é um conjunto maior do que o conjunto das
valorações segundo uma interpretação I qualquer. Portanto, há um número maior
de sentenças válidas do que de sentenças tautológicas. O conceito de sentença
válida, portanto, é mais amplo que o de sentença tautológica.
Se toda interpretação é modelo de α, então a sentença α, válida, é tal que uma interpretação I particular não precisa satisfazer nenhuma exigência para ser modelo de α. Como o significado formal de uma sentença é o conjunto de condições que uma interpretação deve preencher para ser modelo da sentença, o significado formal de uma sentença válida é
vazio. Uma sentença válida não diz nada especificamente sobre as interpretações que são seus modelos. Ao afirmar uma sentença como α, i.e. válida, então, afirmamos algo, em um certo sentido, trivial - não trazemos com ela nenhuma descrição de uma situação particular, ela nada nos diz sobre como as coisas deveriam ser. Ela se verifica em qualquer universo de discurso, e como quer que ele seja estruturado e associado ao vocabulário. SF (α), quando α é válida : nenhum ou vazio 2º) α é contra-válida Dizemos que uma sentença α é contra-válida se nenhuma interpretação é modelo de α. Sentenças contra-válidas7 são sentenças que não podem, portanto, ser realizadas, pois estipulam condições que não podem ser satisfeitas. A negação de uma sentença contra-válida, evidentemente, é uma sentença válida. Uma sentença contra-válida é tal que uma interpretação deveria satisfazer condições impossíveis para ser modelo da sentença; por isso, SF (α), quando α é contra-válida : impossível
7 Sentenças contra-válidas são chamadas também de inconsistentes ou de contraditórias.
114
3o) α tem modelo em algumas interpretações e não em outras Este é o caso mais comum. É usual aqui perguntar pelo significado formal de α, pois a partir dele temos informações sobre as interpretações que são modelos de α. Relembrando, SF (α) : são as condições satisfeitas por interpretações que são modelos de α. A sentença afirma tais condições. Quando a sentença é verdadeira, essas condições se realizam; portanto, elas expressam uma situação que é comum a todos os modelos da sentença. Assim,
a) Significado Formal de sentenças atômicas - Sentenças atômicas podem ter a forma Π (onde Π é letra sentencial), Πnτ1...τn (onde Πn é um predicado n-ário e τ1,...,τn são termos fechados) ou τ1 = τ2 .
SF (Π) : I (Π) = V - O significado formal de uma sentença como Π, é simplesmente
a afirmação de que Π é verdadeira.
SF (Πnτ1...τn): [δI (τ1), ... , δI (τn)] ∈ I(Πn) – ou seja: a n-upla formada pelos objetos
denotados pelos termos τ1,.... τn , tomados nessa ordem, pertence à relação
n-ária que a interpretação em causa associa ao predicado n-ário Πn
SF (τ1 = τ2): δI (τ1) é a mesma que δI (τ2) – ou seja: na interpretação em questão, os
termos τ1 e τ2 denotam o mesmo objeto.
b) Significado Formal de sentenças moleculares Sejam α e β sentenças; sentenças moleculares são da forma ¬α, (α ∧ β), (α ∨ β), (α → β) e (α ↔ β).
SF (¬α) : negação do SF (αααα) , pois são as condições que uma interpretação I deve
cumprir para que νI (¬α)=V, portanto, para que νI (α) = F.
SF (α ∧ β): SF (αααα) e SF (ββββ), pois para que uma interpretação I seja modelo de (α ∧ β),
ela deve ser modelo de (α) e deve ser modelo de (β).
SF (α ∨ β): SF (αααα) ou SF (ββββ), pois para que uma interpretação I seja modelo de
(α ∨ β), ela deve ser modelo de (α) ou deve ser modelo de (β).
SF (α → β): negação do SF (αααα) ou SF (ββββ), pois para que uma interpretação I seja
modelo de (α → β), ela deve ser tal que ou ela não é modelo α, ou ela deve
ser modelo de (β).
115
SF (α ↔ β): SF (αααα) se e só se SF (ββββ), i.e., ou bem SF (α) e SF (β), ou bem negação do
SF (α) e negação do SF (β), pois para que uma interpretação I qualquer
seja modelo de (α ↔ β), ou bem ela é modelo de (α) e modelo de (β), ou
bem ela é tal que νI (α) = F e νI (β) = F.
Resumindo: O significado formal de uma sentença molecular é uma função dos
significados formais de suas partes; e essa função é a indicada pelo conectivo em
causa.
c) Significado Formal de sentenças gerais – sentenças da forma ∀§ β ou ∃§ β.
SF(∀§ β): CSolℑ(β)=UI - ou seja, qualquer objeto do universo da interpretação é uma
solução para β;
SF (∃§ β): CSolℑ (β) ≠ ∅ - ou seja, há soluções para β no universo da interpretação
E) CONSEQÜÊNCIA Uma sentença α é conseqüência (em primeira ordem) de um conjunto Γ de sentenças (escrevemos ΓÆ α), se não existe nenhuma interpretação I tal que I é modelo de Γ e νI (α) = F. Por exemplo: Γ : {∀x (R2xx → (G1x ∨ F1x)), (∃x G1x → ∃x F1x), ∃x∀y R2xy} α : ∃x F1x 1)SF [∀x (R2xx → (G1x ∨ F1x))]: Se um objeto se relaciona consigo
mesmo por R, então este objeto ou bem é I(G1) ou bem é I(F1).
2) SF [(∃x G1x → ∃x F1x)]: Se CS (Gx) ≠ ∅, então CS (Fx) ≠ ∅. 3) SF [∃x∀y R2xy]: Mir I(R2) ≠ ∅ Nesse caso, a sentença α é conseqüência do conjunto Γ.
Justificação: Como o conjunto I(R2) tem mirantes (3), há pelo menos um objeto no domínio de I(R2) que se relaciona com todos objetos do universo - inclusive consigo mesmo. Se há pelo menos um objeto que se relaciona consigo mesmo por I(R2), então, por (1) este objeto ou bem é I(G1) ou bem é I(F1). Se é I(F1), então νI (∃x F1x) = V; se é I(G1), então,
116
por (2), CS (Fx) ≠ ∅, i.e. νI (∃x F1x) = V. Portanto, qualquer modelo de Γ verifica α; por isso, Γ Æ α. Note-se que, como as condições booleanas valem para as valorações segundo interpretações, toda sentença que é conseqüência tautológica de um conjunto é conseqüência (em primeira ordem) desse conjunto. A recíproca não vale: uma sentença pode ser conseqüência de um conjunto mesmo não sendo conseqüência tautológica desse conjunto. OBSERVAÇÃO: CONCEITOS EXISTENCIAIS E UNIVERSAIS.
Os conceitos de consistência, compatibilidade, não-validade e de não-
conseqüência são conceitos existenciais - que podem ser provados exibindo-se um
exemplo, no caso, um exemplo de uma interpretação. Já os de inconsistência, da
incompatibilidade, validade e conseqüência são conceitos universais; só se pode
provar semanticamente que eles se aplicam a sentenças e/ou conjuntos por via
argumentativa, i.e. pela exposição de um argumento. A presença desses conceitos
universais pode também ser estabelecida por um método finitário, baseado apenas
em aspectos sintáticos das fórmulas, que será estudado a seguir (no segundo
fascículo): o método dedutivo.
117
Traduções da linguagem natural para a linguagem formal e vice-versa: A definição de verdade é um conceito muito rico, pois dele tiramos as noções de conjunto solução, significado formal, conseqüência, validade... A partir da definição de verdade podemos também pensar em traduções. A tradução tem limites bem claros: nós temos, por um lado, a linguagem natural e, por outro, a linguagem lógica; a linguagem lógica tem uma semântica extensional - e, além disso, uma fórmula só tem significado pleno quando interpretada. Sentenças na linguagem lógica têm um significado segundo uma interpretação particular qualquer - interpretação esta que tem um UI , que é um conjunto de objetos bem delimitado. Todas propriedades expressas na interpretação são subconjuntos ou relações do UI; as funções da interpretação igualmente são definidas neste UI , assim como os nomes dos objetos. A linguagem lógica tem como expressar as funções de verdade, a identidade e a quantificação. Contudo, há sentenças da linguagem natural cuja estrutura não tem tradução para linguagem do cálculo de predicados clássico. Um exemplo é a sentença “Não é possível que S.” Lógicas modais, não-clássicas, trabalham com expressões como “não é possível que”, mas não a lógica aqui estudada. O problema é que uma expressão desse tipo não tem um comportamento funcional: não basta saber que S é falso para saber o valor de verdade de “não é possível que S”. O valor de verdade da sentença não depende apenas do valor de verdade de sua parte, S; ou seja, "não é possível que" não é um conectivo funcional. Esta é a razão pela qual não pode ser expressa na linguagem lógica clássica. A linguagem lógica clássica é capaz de expressar qualquer
função de verdade, mas não é capaz de expressar conectivos proposicionais que não são funções de verdade. Seja S uma sentença e τ um termo qualquer que ocorre em S. τ pode ocorrer direta ou indiretamente em S.
118
Ocorrência direta de τ: se, ao substituirmos τ por τ’, em S (sendo δ (τ) = δ (τ’)), não houver risco de que, com isto, o valor de verdade da sentença S seja alterado, a ocorrência foi direta. Ocorrência indireta de τ: Se, ao substituirmos τ por τ’, (sendo δ (τ) = δ (τ’)), o valor de verdade da sentença S fica comprometido e pode ser alterado, a ocorrência foi indireta. Exemplos: 1. Ocorrência direta: τ1 = João τ2 = Maria τ3 = o filho mais velho de Pedro Seja S a sentença "João casou com Maria" e suponhamos que δ (τ1)=δ (τ3) (ou seja, que João é o filho mais velho de Pedro). Então S τ1/τ2 é a sentença "O filho mais velho de Pedro casou com Maria". Ora, é claro que a substituição não pode comprometer o valor de verdade da sentença, ou seja, que ν (S) = ν (S τ1/τ2) 2. Ocorrência indireta: τ1 = João τ2 = Maria τ3 = o filho mais velho de Pedro τ4 = Antônio S* = Antônio acha que João casou com Maria. S* τ1/τ2 = Antônio acha que o filho mais velho de Pedro casou com Maria. Ainda que suponhamos verdadeira a igualdade δ (τ1) = δ (τ3), ν (S*) não é necessariamente igual a ν (S* τ1/τ2); Antônio pode, por exemplo, ignorar que os dois termos designam uma mesma pessoa. Em S*, não é só extensão - é a intensão que também está envolvida.
119
Quando a ocorrência do nome é indireta, não só a extensão do nome importa, mas também importa a forma de acesso ao objeto. Não há nessa nossa linguagem lógica como trabalhar com conectivos do tipo “acha que”. A linguagem do Cálculo de Predicados de Primeira Ordem não tem meios para trazer a intensionalidade para dentro de si. A tradução se faz segundo uma determinada interpretação dada. Dependendo de qual é esta interpretação, será possível ou não fazer a tradução com maior ou menor explicitação da estrutura da sentença. É preciso, portanto, que se saiba quais são os significados disponíveis em cada interpretação. O modo usual de se mostrar como fazer traduções é a análise de exemplos tomados como paradigmas. OBSERVAÇÃO: Neste momento, não nos interessa o valor de verdade das
afirmações traduzidas - afinal, sentenças falsas também podem ser traduzidas.
Tomemos uma interpretação I tal que: UI = {0, 1, 2, ...} I(F1) = pares I(G1) = primos I(R2) = relação menor que I(f1) = função sucessor I(s2) = soma I(p2) = produto I(a) = 0 I (b) = 5 I(c ) = 2 Exemplos de sentenças, verdadeiras e falsas, na linguagem natural e traduzidas para linguagem lógica, segundo esta I:
120
Linguagem Natural Linguagem Lógica
Todos são pares. ∀xF1x
Todos os números naturais são ímpares.
∀x¬F1x
Os números naturais são primos. ∀xG1x Estas sentenças, acima, são chamadas universais irrestritas ou totais: predica-se de cada objeto do universo uma certa propriedade. - Há sentenças na linguagem natural que são do tipo “Todos os primos são ímpares”. Em outras palavras, diz-se aqui que é condição suficiente para ser ímpar, ser primo. Ou seja, que para qualquer número, se ele é primo, então ele é ímpar, i.e. há uma condição a ser satisfeita (ser primo) para que se aplique a propriedade (ser ímpar). Esta sentença é uma sentença do tipo ∀x (G1x → F1x). Este tipo de sentença é chamado de uma universal restrita; ela tem a seguinte forma: ∀x ( _____ → _____ ) Na primeira posição (‘___’), está a restrição ou condição e, na segunda, a propriedade que se atribui. Uma sentença como ∀x (G1x ∧ ¬F1x) não tem restrição: ela diz que para qualquer objeto do UI , ele é primo e ele é ímpar, i.e. que CS (G1x) ∩ CompCS (F1x) = UI. - Para traduzir da linguagem natural uma sentença como “Todos primos maiores que dois são ímpares”
121
é preciso notar, em primeiro lugar, que esta é uma sentença que tem uma dupla restrição. A forma geral dela é a de uma universal restrita, i.e. ‘∀x ( ___ → ___ )’. A restrição é: ser um primo maior do que dois. Como é que podemos dizer/traduzir que “Cinco é um primo maior que 2”? Em linguagem lógica, seria (G1b ∧ R2cb) Portanto, a restrição (ser um primo maior que 2), pode ser expressa por (G1x ∧ R2cx) pois o conjunto solução desta fórmula, segundo essa interpretação I, é o conjunto dos números que são primos e que são maiores que dois. Já sabemos que o conjunto solução da fórmula ¬F1x é o conjunto dos ímpares. Assim, a fórmula que diz que todos primos
maiores que dois são ímpares pode ser traduzida para linguagem lógica como ∀x ((G1x ∧ R2cx) → ¬F1x) Esta sentença não afirma que haja (exista) um objeto que satisfaça o seu antecedente ou o seu conseqüente, ou seja, que haja primos maiores que dois ou que haja ímpares. Agora, se tomarmos uma sentença em linguagem lógica, também devemos ser capazes de traduzi-la, segundo a interpretação dada, para linguagem natural. Vejamos o que diz a sentença ∀x ((G1x ∧ R2cx) ∧ ¬F1x) Esta sentença diz que “Todos objetos do UI são primos, são maiores que dois e são ímpares”.
122
Uma sentença como esta, ao contrário da anterior, implica a existência dos objetos a que ela se refere - quer dizer, esta sentença afirma que os objetos são de tal e tal modo, enquanto que a sentença anterior diz que se algum objeto tiver tais e tais características, então este objeto é de tal e tal maneira. Outros exemplos de tradução para a linguagem formal segundo a mesma interpretação: a) Todo número maior que dois é menor que cinco. ∀x (R2cx → R2xb) b) Todo primo par é menor que cinco. ∀x ((F1x ∧ G1x) → R2xb) c) Todo primo é ímpar ou menor que cinco. ∀x (G1x → (¬F1x ∨ R2xb)) Vejamos agora as traduções usando o quantificador existencial (‘∃’): d) Algum número natural é primo . ∃x G1x e) Alguns números naturais são ímpares. ∃x ¬F1x f) Alguns ímpares são primos. ∃x (¬F1x ∧ G1x) g) Alguns primos ímpares são menores que 10 ∃x ((¬F1x ∧ G1x) ∧ R2xp2bc ) Os exemplos seguintes envolvem dois quantificadores h) Nenhum primo par é maior que algum primo ímpar ¬∃x∃y(((G1x ∧ F1x) ∧ (G1y ∧ ¬ F1y)) ∧ R2yx)
123
i) Não existe o maior primo ∀x(G1x → ∃y (G1y ∧ R2xy)) j) Há um primo par menor que qualquer primo ímpar ∃x((G1x ∧ F1x) ∧ ∀y ((G1y ∧ ¬F1y)→R2xy)) l) Se o produto de dois números é par, pelo menos um deles é par ∀x∀y(F1p2xy → (F1x v F1y))
