Lições de Lógica

Prévia do material em texto

LIÇÕES DE LÓGICA 
Fascículo I 
 
 Andréa Loparic 
 
 
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, 
inicalmente, apresentar um sistema de dedução natural. O sistema é 
o de Mates, mas, acreditamos, 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. 
 
 
 
Gramática de L (parte 1) 
A linguagem 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 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 . 
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). 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, g21, 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, S11, H21 são predicados de carência 1; F2, B2, H32, G192são predicados de carência 2; A3, F23, H13, G53, 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, 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, B11,…, Z11, A21 … - dos operadores de carência 2: a2, b2,…,t2, a12, b12,…, t12, a22,… etc.. 3. As variáveis e as constantes individuais formam um grupo de símbolos chamados símbolos individuais. 
d) Os símbolos lógicos são oito:  o predicado de igualdade = , também chamado 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 quantifição, a saber: o símbolo da quantificação universal:  , e o símbolo da quantificação existencial:  . 
 
 
 
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 . 
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) F12 j) Q p)  u) P 
 Expressões de L 
Uma expressão do vocabulário de L é uma sequê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 sequê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 cpor meio de uma indução, assim : se  é um símbolo do vocabulário de L,então: a) é uma expressão de L;e b) o resultado de juntarmos  ao final de uma expressão de L é uma 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 e que i é uma ocorrência de  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 . 
Exemplos: a, x, f1a, g2ax, h1f1a, g2f1ah1b, x1, y, f11x, h3f1ah1g2xyg2ab . 
 
Observação: 
 A definição de termo e a segunda definição de expressão de  são dois 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ária 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, h1g2abf3xby têm complexidade 3; 
 etc.. Observe-se que, na definiçao 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 
 
 
 
 
Fórmulas de L 
 
A outra classe de expressões bem formadas de L é constituída pelas fórmulas. Ao definiçã 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 apresentar apenas 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. 
 
 
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 sequê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) F2g1xh2ab i) F1G1x 
b) g2ab=x j) F=G 
c) R l) x=a 
d) h2bh2bh2bb m) G3h2abf1bb 
e) F2ab=x n) a+b=c 
f) xy=z o) x2 
g) f2xy=z p) F1x1 h) F1f2xy q) f1x1 
 
 
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  já introduzidas sintaticamente. As expressões de ganharão significados quando associadas a interpretações, 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 , 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)  UIn. 
 
Como se vê, infinitas interpretações podem ser dadas para a linguagem ; a escolha de uma interpretação é arbitrária e poderá atender a interesses e conveniências nas aplicações e usos de . 
As interpretações podem ser 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 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 anteriormente especificados. 
(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 anteriormente, (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-se a interpretação das constantes individuais, por exemplo, de modo que as constantes individuais sem í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: ’ 
U’ = 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: ” 
U”= 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. 
”(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. 
 
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. 
 
 
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 de 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(g1s2bc)=(g1)[I(s2bc)]= o dobro de 12 =24 I(p2cg1b) = (p2)[I(c),I(g1b)]= I(c),I(g1b)= 7(g1)[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)]=(f1)[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: 
 
 
 
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 uma características importantes dessa linguagem: em primeiro lugar, quando associada a uma interpretaçao, 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(h2ah2ah2aa) b) I(f1g1b) g) I(g1g2af1b) c) I(f1h2bd) h) I(g1f1g1g2ab) d) I(h2af1b) i) I(g1h1g2af1c) e) I(g1f1h1g2ab) j) I(g2g1af1g1b) 
 
 
1.2) Nesta interpretação seria correto escrever, por exemplo: I(s1) = função antecessor? Por quê? 
 
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) = 3, se x>6; 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) h1 h1 g1 h1 a 
 b) g1 h1 g1 h1b 
 
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(b) = Brasil I(l) = Londres I(c) = China I(n) = Nova York I(f) = França I(p) = Paris 
 
Determine a denotação, segundo I, de cada um dos termos abaixo: 
a) h1f b) h1h1b c) h1h1n 
 
 
 
 
 3. Valor de verdade das sentenças atômicas 
Já vimos o que é uma sentença atômica: uma fórmula atômicaque 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. 
(f1) = 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(). 
 
 
(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(q)=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. 
 
 
 
 
 
 
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(f1) = x-1, se x é ímpar; x+1, se é par 
I(g1) = função quadrado I(g1) = 2, se x<7; 8, se x7 
I(h1) = função cubo I’(h1) = função identidade 
 I(g2) = função soma I’(g2) = função projeção do primeiro 
I(h2) = função produto I’(h2) = função projeção do segundo 
I(F1) = conjunto dos primos I’(F1) = {1, 3, 5} 
I(G1) = conjunto dos pares I’(G1) = {2, 3, 4, 5, 6} 
I(R2) = relação ser divisível por I’(R2) = relação menor que 
I(M2) = relação menor que I’(M2) = {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 
 
 
 
 
 
Gramática de L (parte 2) 
Retornamos à gramática para apresentar a definição de fórmula de . 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 a equivalência também é chamada bi-condicional ou bi-implicação. Exemplos: Como sabemos, as expressões abaixo são fórmulas atômicas: F2ab a = x G2f1ay1 H3x2g2aby 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 
a = x 
a = x (F2ab  a = x) (P  H3x2g2aby) (a = x  y = f1z) (P  a = x) (((F2ab  a = x)  P) (a = x  (F2ab  a = x)) (G2f1ay1  y = f1z) y (P  H3xg2aby) 
 
z (a = x  y = f1z) 
 (P  a = x) 
 y (G2f1ay1  y = f1z) x y (P  H3xg2aby) 
x a = x 
 x a = x 
  y (G2f1ay1  y = f1z) (P  y = f1z) 
y P ((P  a = x)  F2ab) 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. 
 
 
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=F1y l) P   P 
c) h2xy=f1a m) x y z (x=y  x=z) 
d) (F2ax  (x=a  y F1h1y)) n)  x  y x=y 
e)  f1x=h2xy o)   x f1x=x 
f) ( P  y P) p)  (x x=f1a  y F1y) 
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 estenúmero deve haver um único conectivo binário ainda não-numerado; numere-o também com este número. 
 
 
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: Cx [] = n. Assim: a) as fórmulas atômicas têm complexidade 0 (zero); e b) Cx [] = Cx [] + 1 c) Cx [ * ] = Cx [] + Cx [] + 1, para *  {, , , } d) Cx [Q§] = Cx [] + 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. 
 
 
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: 1)  é a própria ; 2) existe uma subfórmula de  de uma das seguintes formas: a)  b) ( * ’) c) (’ * ) d) Q§; onde *  {, , , } e Q  {, }. Exemplo: Seja  a fórmula: x (y (H2xy  R2ax)  F1x). Então, são as seguintes as subfórmulas de : (1) x (y (H2xy  R2ax)  F1x) (2) (y (H2xy  R2ax)  F1x) (3) y (H2xy  R2ax) (4) F1x 
(5) y (H2xy  R2ax) (6) (H2xy  R2ax) (7) H2xy (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 . 
 
 
 
 Á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 exatemente 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. 
 
 
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) 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: 
a) x (F1x  G1x) b) x (F1x  G1x) y 2xy) c)  (x F2xy  (z (H2zx  G2xz)   G2xz)) d) x (y (H2xy  F2h1ab)  (Q  (F2xz  H2ag2xb))) Á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 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. EXERCÍCIO: Construa a árvore molecular de: 
a) ((x F1x  F1a)  x (F1a  F1x)) b) ((F1a  G1b)   ( x F1x  (F1a  G1b))) c) (((F1a   x G1x)  (G1a  x G1x))  x (G1a  F1x)) d)( (x y R2xy  x (F1a  F1x))  (F1a   x y R2xy)) 
 
 
Vamos agora analisar os dois distintos modos segundo os quais uma variável pode ocorrer numa fórmula. 
Ocorrência ligada 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: 
 
Assim, 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, são livres. 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. EXERCÍCIO: Nas fórmulas abaixo, classifique as ocorrências das variáveis como livres ou ligadas. a) x (F2xy  y (y=a  (z F1z  h2zy=x))) b) ( h2xy=a  z (y h2yz=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 é umafórmula de L onde nenhuma ocorrência de variável é livre. 
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ó aparece\m 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. EXERCÍCIO: 
1) Seja  a fórmula  x (y (F2af1y   z f1z=a)  H1f1a). 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;  é 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 
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 *  {, , , }. 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 F1x  F1a)  x (F1a  F1x)) 
b) ((F1a  G1b)   ( x F1x  (F1a  G1b))) 
c) (((F1a   x G1x)  (G1a  x G1x))  x (G1a  F1x)) 
d) ( (x y R2xy  x (F1a  F1x))  (F1a   x y R2xy)) 
e) (x F1x  x F1x) 
f) ((x y R2xy  x (F1x  G1x))  (x y R2xy x F1x)) 
g) ((x F1x  (R2ab  x F1x))  (R2ab  (x F1x  x F1x))) Podemos ainda encarar esse tipo de associação de uma maneira mais geral e dizer que uma função CS é uma função biunívoca que associa a cada sentença atômica ou geral uma letra sentencial. Assim, poderemos falar de um conjunto de sentenças CS associado a um conjunto de sentenças da linguagem. Na prática, quando temos um conjunto finito de sentenças, encontramos uma classe de CS associadas substituindo por letras sentenciais os componentes básicos que venham a ocorrer em qualquer uma das sentenças do conjunto. Por exemplo: Consideremos o conjunto: 
{((F1aG1b)(xF1xF1a)), (xF1xxF1x), G1b } 
As sentenças atômicas e gerais que ai ocorrem são: F1aG1b, xF1x e 
xF1x, .às quais podemos associar, nessa ordem, P, Q, R e S. Um conjunto de CS associadas a esse conjunto será, assim, o conjunto: 
 {((PQ)(RP)), (RS), Q }. 
Exercício: Construir um conjunto de CS associadas ao conjunto formado pelas sentenças a) c) e f) do exercício anterior. 
Futuramente veremos que haverá uma aplicação particularmente interessante dessa técnica. 
Semântica Proposicional 
 
 
Vamos, por um momento, deixar de lado a linguagem  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 binária. Observação: Neste livro estudamos a chamada lógica simbólica clássica, que trabalha apenas com um grupo especial de valorações bivalentes: aquelas em que, para cada conectivo, há uma condição de verdade necessária e suficiente formulada em termos de suas subfórmulas imediatas. Certas lógicas não-clássicas têm definições de verdade bivalentes, mas nem todas as condições de verdade para tipos de fórmulas são condições necessárias e suficientes; certas vezes, ainda, levam em consideração outros fatores, além dos valores veritativos de suas subfórmulas. Outras lógicas, ainda, ditas polivalentes, podem 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 cinco formas de fórmulascomplexas é 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 cujos argumentos são os valores de verdade de suas subfórmulas imediatas. Assim, a negação representa uma função de verdade unária (com um só argumento): a função do conjunto {V, F} no conjunto {V, F} definida pela tabela: 
Argumento Valor   V F F V 
Os quatro conectivos binários expressam funções de verdade com dois argumentos; são, assim, funções de {V, F}2 em {V, F} ( ou seja, de {<V,V>,<V,F>,<F,V>,<F,F>} em {V, F}, definidas por condições de verdade que podem ser expressas pelas seguintes tabelas: 
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}. 
Podemos verificar que há quatro funções de verdade unárias 
(abaixo indicadas por f1, f2, f3, f4): 
 f1 f2 f3 f4 
V V V F F 
F V F V 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 f3, 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, 
aqui denotadas por g1 ... g16: 
 g1 g2 g3 g4 g5 g62 g7 g8 g9 g10 g11 g12 g13 g14 g15 g16 
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 g122 ‘‘ expressa a função g22 ‘‘ expressa a função g42 ‘‘ expressa a função g82 
Entre as funções unárias e binárias, f3, g2, g4, g8, e g12 são as funções diretamente expressáveis na linguagem que adotamos aqui. As outras, no entanto, são também expressáveis por meio de composição, a partir dessas cinco. Assim, por exemplo, a função g5 é obtida pela composição de f3 com g12, como se vê na tabela abaixo: 
 
 g12 f3 g12 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 g5, é possível compor qualquer função n-ária de verdade; e o mesmo vale para a função g15. Também podemos obter todas as funções de verdade usando os elementos do conjunto {f3, g12}; o mesmo vale pare os conjuntos {f3, g2} e {f3, g4}. Como podemos expressar f3, g12, g2, g4 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: 
 
f2 f3 f1 f4 
  (  ) (  ) 
V F V F 
F V V F 
2) a) A função f1 pode ser expressa por ((  )  (  )); 
 b) As funções g2, g3, g4 e g5 podem ser expressas por (  ), (  ), (  ), (  ), como mostra a tabela: 
 
c) As funções g6, g7, g8, g9, g10, g11 podem assim ser expressas: 
 
d) As funções g12, g13, g14 e g15 podem ser expressas pelas negações das fórmulas que expressem g5, g4, g3, g2, respectivamente. 
e) A função g16 pode ser expressa pela negação de uma fórmula que expresse g1. 
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 
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 g12, 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, f3, e quatro funções binárias, g2, g4, g8, g12. Mostremos, agora, que, embora úteis, alguns desses conectivos não seriam, em princípio, necessários. Para isso, 
sejam: 
1) L: a linguagem contendo letras sentenciais e os conectivos ‘‘, ‘‘; 
2) L: a linguagem contendo letras sentenciais e os conectivos ‘‘, ‘‘; 
3) L: a linguagem contendo 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!). É, assim, 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 usar 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ãoelas 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. 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 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’. 
 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  dele 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). 
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 
 
 
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. 
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 veritativamente 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, (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  é compatível com o conjunto de sentenças , se  é verdadeira em algum modelo de , ou seja, se o conjunto    é verifuncionalmente consistente. 
 
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, numa tabela de verdade que contenha todas as letras sentenciaisde , a coluna correspondente a  é formada apenas por ocorrências de ‘V’. Há um resultado simples e importante concernindo as 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, existeria 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. 
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 
 
Grupo II: Implicações Tautológicas 
 
(  (  )) Prefixação por implicação 
((  )  ) Eliminação do segundo conjuntivo 
((  )  ) Eliminação do primeiro conjuntivo 
(  (  )) Introdução do segundo disjuntivo 
(  (  )) Introdução do primeiro 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: 
 
 
(   ) ((  )   ) ((  )  ) ((  )  ) ((  )  ) ((  )  ) ((  )  ) ((  )  ) ((  )  ) 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 ((P  Q)) = 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 , : 
Se  é conseqüência tautológica de , / é 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 da seção anterior valem: {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’. 
Destaquemos alguns exemplos importantes: 
{, (  )}  Modus Ponens {, (  )  Modus Tollens {(  ), (  )} (  ) Silogismos Hipotético {(  ), }  Silogismo Disjuntivo {(  ), }  Silogismo Disjuntivo {, } T  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)) 
 
 
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 é tautologicamente equivalente a 2 ; c) 8 é tautologicamente 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}. 
 
Aplicação dos conceitos proposiciomais à 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,  é 
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’. 
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; e 
 (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 há valorações booleanas que verificam ‘(P  (Q  R))’, ‘Q’ e ‘(R  S)’; por 
exemplo, consideremosa valoração , tal que (P) = (Q) = F e (R) = (S) = V; 
essa valoração é um modelo desse conjunto.. 
 
EXERCÍCIOS 
 
 
1) Considere cada um dos seguintes conjuntos de sentenças: 
 1 = ((xy R2xy  x (R2xa  x=a)) xy R2xy), x (y R2xy  y R2yx),  xy R2xy} 
 2 = {x y (R2xy  x=y), x y R2xy, x y  x=y} 3 = {x y (R2xy  (G1x  H1y)),  x (G1x  H1x), x y R2xy} 4 = {(x F1x  x G1x), (x G1x x (G1x  H1x)), ((x F1x  x G1x) x (G1x  H1x))} 
 5 = { x y (R2xy  R2yx), x y ( x=y (R2xy  R2yx))} 
4.1) Quais deles são verifuncionalmente consistentes? 
4.2) Quais das sentenças abaixo são conseqüências tautológicas de 3 ? 
a) ( x (G1x  H1x)   (x y (R2xy  (G1x  H1y))   x y R2xy)) 
b) (x y R2xy  x y (R2xy  (G1x  H1y))) 
c) ( x (G1x  H1x)  x y R2xy) 
4.3) Dê exemplo de sentença que não seja conseqüência tautológica de 1. 
 
 
Semântica de L (parte 2) 
Para retornar à semântica do cálculo dos predicados e formular 
uma definição de verdade para as sentenças da linguagem - isto é, 
estabelecer as condições gerais para que uma sentença  receba o valor de 
verdade V numa interpretação  - 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) 
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 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 é definida 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 . 
Definição de Verdade para as sentenças de 
Seja  uma interpretação. O valor de verdade associado por  a uma sentença , de , em símbolos, v() é definido por indução na complexidade de , (indicada por “Cx ()”): 
- (base) Cx () = 0; então  é atômica e v() 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,