Buscar

Introdução de Lógica para a Cincia da Computao

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 248 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 248 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 248 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

1
Introduçªo à Lógica
para a
CiŒncia da Computaçªo
Jair Minoro Abe
Alexandre Scalzitti
João Inácio da Silva Filho
Introduçªo à Lógica
para a
CiŒncia da Computaçªo
2.001
Jair Minoro Abe
Alexandre Scalzitti
João Inácio da Silva Filho
2001, by Editora Arte & Ciência
Direção Geral
Henrique Villibor Flory
Editor e Projeto Gráfico
Aroldo José Abreu Pinto / Karel H. Langermans
Editoração Eletrônica
Alain Ferreira do Nascimento
Capa
Karel H. Langermans
Dados Internacionais de Catalogação na Publicação (CIP)
(Biblioteca de F.C.L. - Assis - UNESP)
Índice para catálogo sistemático:
1.
2.
3.
Editora Arte & Ciência
Rua Treze de Maio, 71 – Bela Vista
São Paulo – SP - CEP 01327-000
Tel/fax: (0XX11) 257-5871
Na internet: http://www.arteciencia.com.br
Dedico este trabalho ao Rusky (1990-2000)
 que me ensinou muitas coisas,
aprendi muitas coisas,
por uma linguagem não falada.
Jair Minoro Abe
7
Prefácio
Este texto foi elaborado pelos autores tendo por base os diversos
cursos de Lógica que os mesmos têm lecionado nos últimos anos.
A presente monografia é destinada a introduzir o leitor neste fasci-
nante ramo do conhecimento humano que é a moderna Lógica Matemática.
O trabalho foi redigido para atender um número maior de leitores, engloban-
do estudantes de diversas áreas, tais como, Ciência da Computação, Análise
de Sistemas, Processamento de Dados, Inteligência Artificial, as diversas
Engenharias, Matemática, Ciências Biológicas, Economia, Psicologia, Filo-
sofia, Direito, enfim todo estudioso interessado no assunto.
A Lógica se converteu nos últimos anos em disciplina de primeira
necessidade para os diversos cursos, e isto não é surpreendente, pois,
disse o pensador norte americano W. Quine : “A Lógica é o denominador
comum das Ciências Especiais ...”.
Não se exige, praticamente, pré-requisito algum para sua leitura; com
efeito, a exposição do texto está detalhada tanto quanto possível com notas
explicativas referente a pontos “delicados” do desenvlvimento, procurando
fazer do texto uma leitura agradável. Os tópicos escolhidos cobrem o que
hodiernamente denominamos de “núcleo” da Lógica Clássica.
Complementou-se com algumas aplicações nas diversas áreas.
Um comentário ao neófito em Lógica: não se lê um livro de lógica
como se lê um livro de romance, i.e., sua leitura muitas vezes não é conveni-
ente que se faça de maneira linear; também sugere-se ao leitor que faça os
inúmeros exercícios propostos para um entendimento salutar dos conceitos
vistos. Aqui se aplica vivamente um pensamento de Confúcio: “se ouço,
esqueço; se vejo, gravo; se faço, compreendo ...”
O tomo que vem a lume é apenas uma primeira versão que pretende-
mos futuramente aprimorá-lo e enriquecê-lo. Para tanto, contamos com as
sugestões e críticas construtivas por parte dos leitores.
Os Autores.
9
SUMÁRIO
PREFÁCIO
1 – INTRODUÇÃO................................................................................................9
0.1– Nota Histórica......................................................................................9
0.2– O que é Lógica ?.................................................................................10
0.3– Ciência e Lógica.................................................................................11
0.4– Aspectos da lógica atual..................................................................13
1– INTRODUÇÃO AO CÁLCULO PROPOSICIONAL
1.1– Introdução..........................................................................................15
1.2– Os paradoxos.....................................................................................15
1.3– Linguagens artificiais........................................................................20
1.4– A linguagem universal da lógica.....................................................22
1.5– Conectivos lógicos e tabelas-verdade...........................................22
1.6– Fórmulas atômicas e fórmulas.........................................................37
1.7– Árvore de composição de uma fórmula - árvore de
decomposição............................................................................................38
1.8– Tabela-verdade de uma fórmula......................................................49
1.9- Tautologias.........................................................................................65
1.10– Árvore de refutação........................................................................70
1.11– Inferência lógica..............................................................................82
1.12– Regra de eliminação de parêntesis................................................93
1.13– A notação polonesa de fórmulas..................................................94
1.14– Forma normal disjuntiva.................................................................95
1.15– Uma axiomatização da lógica proposicional..............................101
2- O CÁLCULO DE PREDICADOS..................................................................117
2.1– Lógica e gramática...........................................................................117
2.2– Um sistema formal para a lógica de predicados..........................125
2.3– Estrutura dedutiva...........................................................................128
2.4– Semântica..........................................................................................138
3– ALGUNS ASPECTOS DE PROGRAMAÇÃO EM LÓGICA E PROLOG
3.1– Introdução........................................................................................145
3.2– A proposta da programação em lógica........................................146
3.3– Cláusula de Horn.............................................................................147
3.4– Considerações preliminares...........................................................148
3.5– Cláusula............................................................................................151
1 0
3.6– Cláusula de programa.....................................................................153
3.7- Cláusula de programa condicional.................................................154
3.8- Cláusula de programa incondicional.............................................155
3.9– Cláusula gol......................................................................................156
3.10- Cláusula vazia..................................................................................157
3.11- Cláusula de Horn.............................................................................157
3.12– Programs lógicos e teoremas.......................................................159
3.13– Computação de gols......................................................................161
3.14– Substituições e unificadores........................................................170
3.15– Substituições..................................................................................171
3.16– Instância de uma substituição...........................................................
3.17– Composição de substituições.....................................................172
3.18– Variante...........................................................................................172
3.19– Proposições....................................................................................173
3.20- Substituição mais geral.......................................................................
.3.21– Unificadores...................................................................................173
3.22– Unificador mais geral – umg........................................................174
3.23– Algoritmo de unificação.....................................................................
3.24– Resolvente......................................................................................180
3.25– SLD-derivação.................................................................................182
3.26– SLD-refutação.................................................................................1833.27– Um pouco de PROLOG.................................................................190
3.28– A notação PROLOG.......................................................................190
3.29– A estratégia PROLOG...................................................................192
3.30– Interpretador PROLOG.................................................................193
3.31– Assuntos relacionados à programação em lógica....................196
4– CIRCUITOS LÓGICOS DE CHAVEAMENTO
4.1– A álgebra da lógica.........................................................................199
4.2– Negação lógica – circuito não......................................................202
4.3– Conjunção lógica – circuito E.......................................................204
4.4- Disjunção lógica – circuito OR......................................................205
4.5– Exemplos de aplicações.................................................................207
5– PORTAS LÓGICAS.......................................................................................215
5.1– As portas lógicas básicas..............................................................216
5.2– Porta lógica inversora.....................................................................216
5.3– Porta lógica E...................................................................................217
5.4– Porta lógica NÃO-E (NAND)........................................................217
5.5– Porta lógica OU...............................................................................218
5.6– Porta lógica NÃO-OU (NOR)........................................................219
5.7– Combinação de portas lógicas......................................................220
5.8– Exemplos de aplicação...................................................................207
APÊNDICE
1.Algumas estruturas algébricas...........................................................233
2.Lógica proposicional e álgebra de Boole..........................................235
3.Modelos de Herbrand..........................................................................236
4.A lógica clássica .................................................................................240
REFERÊNCIAS BIBLIOGRÁFICAS.....................................................245
1 1
1 INTRODUÇÃO
1.1 - Nota Histórica
A Lógica, ao que tudo indica, foi descoberta por Aristóteles (384-322
a.C.). Os registros se encontram em seu famoso livro “ da Metafísica”.
Após sua descoberta, ela permaneceu praticamente intacta por mais de dois
mil anos, sendo retocada em detalhes de pouca importância. E. Kant chegou
mesmo a asseverar que a ciência descoberta pelo Estagirita se constituía
numa ciência acabada: a lógica não havia dado nenhum passo para diante e
nenhum para trás (desde sua introdução).
Não obstante, grandes mudanças começaram a ocorrer notadamente
com G. Boole (1815-1864), A. De Morgan (1806-1871) e contemporâneos com
a introdução da simbolização na Lógica. Boole, na realidade, estava estu-
dando as “Leis do Pensamento Humano”. Houve, porém, alguns precurso-
res dessa mudança, como G. Leibniz (1646-1716) e J.H. Lambert (1728-1777).
Outras investigações de caráter mais filosófico foram efetuadas por G. Frege
(1848-1925), contribuindo enormemente para o desenvolvimento da lógica
de predicados. Porém, o grande avanço propriamente dito foi estabelecido
com a publicação da monumental obra “Principia Mathematica”, em três
volumes, de A. N. Whitehead e B. Russell no alvorecer deste século. Pode-
se mesmo dizer que a moderna Lógica Matemática teve início com a publica-
ção da referida obra. Aliás, não seria exagero, se afirmarmos, como A. N.
Whitehead disse, que a lógica atual está para a lógica aristotélica como a
matemática moderna está para a aritmética das tribos primitivas.
No entanto, as décadas posteriores aguardavam mais novidades. K.
Gödel, na época um jovem lógico austríaco, mostrou que não pode haver
uma sistematização completa da Aritmética. Isto quer dizer que, intuitiva-
mente e sem rigor, há proposições aritméticas que dizem: “sou verdadeiro,
porém indemonstrável”. Desse resultado, Gödel deduziu outro: que, se a
Aritmética for consistente, sua consistência não pode ser demonstrada “den-
tro” da teoria, ou seja, há que se recorrer à teorias que a englobem, mais
gerais, e, portanto, mais inseguras que a original. Tais resultados são conhe-
cidos como “teoremas de incompleteza de Gödel”. Como se sabe, os resulta-
dos de Gödel representaram o limiar de uma nova era na moderna Lógica
Matemática. Suas reflexões são de longo alcance, deixando muitas questões
sobre os fundamentos da disciplina para as décadas posteriores.
Outra contribuição de envergadura foi efetuada pelo lógico polonês
A. Tarski. Constitui na matematização do conceito de verdade como corres-
pondência. Tal concepção de verdade remonta Aristóteles: “dizer do que
não é que é, e dizer do que é, que não é, é falso. E, dizer do que não é, que não
1 2
é, e dizer do que é, que é, é verdadeiro”. Noutras palavras, verdade é aquilo
que é e falso, aquilo que não é. Note que o conceito de verdade repousa no
verbo ser. Antes de Tarski, a idéia de verdade era utilizado livremente no
discurso matemático e inúmeras contradições haviam aparecido nas teorias
matemáticas.
Outra enorme revolução que a lógica experimentou neste século foram
alguns resultados de independência de certos postulados da teoria dos
conjuntos obtidas por P. Cohen. No início da década de sessenta, Cohen
mostrou, por exemplo, que um dos axiomas mais discutidos, o Axioma da
Escolha, era independente dos demais postulados da teoria dos conjuntos.
Também Cohen demonstrou a independência de outros postulados signifi-
cativos da teoria dos conjuntos. Cohen foi agraciado com a medalha “Fields”
(o prêmio de maior prestígio em Matemática) por suas perquirições.
Como a Matemática constitui prolongamento natural da teoria dos
conjuntos, segue-se que há patentemente Matemáticas alternativas em rela-
ção à Matemática Clássica. Grosso modo, teorias dos conjuntos em que
valem certos postulados como o Axioma da Escolha, Hipótese do Contínuo,
e outros denominam-se Teoria dos Conjuntos Cantorianas. Teorias em que
não valem essas condições, chamam-se Não-Cantorianas. Logo, podemos
falar em Matemáticas Cantorianas e Não-Cantorianas. As Matemáticas Não-
Cantorianas ganharam relevo sobretudo com os resultados de Solovay na
década de setenta. Solovay considerou um modelo de teoria dos conjuntos
no qual não vale a forma geral do Axioma da Escolha e, se obtém resultados
que diferem muito da Matemática Cantoriana. Por exemplo, prova-se que na
reta real, todo subconjunto é Lebesgue mensurável (intuitivamente que todo
conjunto de números reais pode ser “medido”), ou, que num espaço de
Hilbert, todo operador é limitado, e por conseguinte, contínuo. Porém, esses
resultados modificam profundamente a maneira de se ver as teorias físicas,
pois, como é sabido, teorias físicas têm, em sua maioria, bases em certas
estruturas conjuntistas. Advém, então, a indagação: qual a teoria dos con-
juntos que melhor retrata as teorias físicas? Além disso, qual é o significado
físico quando uma mesma teoria física é considerada em teorias de conjun-
tos distintas?
Todas essas questões estão sendo pesquisadas intensamente. Tal
situação se mostra absolutamente nova, pois, o investigador que vai aplicar
a Lógica possui em mãos agora Matemáticas alternativas, situação esta muito
distinta de um passado recente. Aliás, a Matemática que era una até então,
cederá fatalmente à diversidade.
1.2 - O que é Lógica ?
O que é Lógica?
Talvez seja esta a primeira curiosidade que advém à mente do leitor.
Preliminarmente, observemos que o público não especialista costuma em-
pregar o termo “lógica” em várias acepções: por exemplo, costumamos ouvir
expressões como “a lógica do amor”, “a lógica do técnico de futebol”, “a
lógica do presidente”, e assim por diante. Convém ressaltarmos que, apesar
do uso do termo“lógica” nesses exemplos não ser destituído totalmente de
1 3
sentido, tais contextos são inadequados quando tratamos do termo “lógi-
ca” que adquire hodiernamente. Uma definição popular de lógica é: Lógica é
o estudo das inferências (raciocínios) válidos. Tal definição não está incor-
reta, porém, ela não é adequada se observarmos o que a Lógica é
modernamente. Por exemplo, a Teoria dos Modelos, um ramo importante da
Lógica atualmente, dificilmente se enquadraria nessa definição. Outra defini-
ção que encontramos em algumas obras de Lógica é a seguinte: Lógica é o
estudo do raciocínio feito pelos matemáticos... Comentamos uma definição
que nos parece mais adequada: Lógica é o que os lógicos cultivam ou o que
está nos tratados de Lógica. Ou seja, para bem compreendermos o que é
lógica, é necessário seu cultivo sistemático. O leitor deve ter percebido que
não existe uma definição satisfatória de Lógica. Tal questão pertence à Filo-
sofia que trata, entre outras coisas, de temas que não possuem resposta
cabal. Esta situação se afigura constrangedora, pois vamos estudar Lógica
sem poder saber exatamente o que ela é ...
1.3 - Ciência e Lógica
Entre as várias indagações que o homem se faz, uma das mais signifi-
cativas e recorrentes diz respeito ao conhecimento. E é justamente no campo
da ciência que se dá a investigação e a busca desse conhecimento. Seríamos
parciais se disséssemos que isto ocorre apenas no campo científico ou aca-
dêmico. Essa busca, na verdade, acontece na maioria das atividades que
envolvem o ser humano. Existem métodos de apreensão da realidade nos
campos religioso, político, social, entre outros. Mesmo assim, a ciência (e o
método científico) ocupa um papel cada vez mais importante em todos esses
campos. Mas, nos perguntamos, o que é ciência? Ou, em outros termos, com
o que se preocupa o cientista em sua investigação? Por exemplo, um biólogo
está buscando o que?
Uma resposta adequada e definitiva é difícil, mas, em princípio, diría-
mos que todo cientista está buscando compreender algum fenômeno, enten-
der e explicar uma parte da nossa realidade.
O biólogo que, por exemplo, esteja buscando conhecimento sobre
moscas. Neste caso, a porção da realidade que ele pretende captar, compre-
ender (e depois transmitir a outras pessoas, à comunidade) seria algum as-
pecto relativo à vida da mosca, ou algo assim. O médico pesquisador, por
exemplo, que busca investigar o mecanismo interno de certas doenças, a
tuberculose, o câncer, etc. Já o psicanalista, que se preocupa em compreen-
der o psiquismo das pessoas. Enfim, cada cientista está, então, tentando
entender e explicar certas porções de nossa realidade.
Passaríamos, então, para um segundo ponto, que seria o caminho
percorrido na busca dessa compreensão da realidade. É sabido que, em
tempos mais remotos, alguns cientistas usaram uma boa dose de misticismo
nas suas ponderações, porém, hoje dificilmente uma tal atitude seria aceita
ou encorajada no campo científico. Diríamos que o cientista utiliza aquele
que é um dos atributos mais importantes do ser humano para empreender
sua investigação, a razão. A ciência só se concretiza em virtude e através da
razão humana, sendo definida, justamente, como uma atividade racional.
Teríamos assim uma primeira relação importante: ciência e razão.
1 4
Mas afinal, perguntaríamos novamente, o que é razão? Não pretende-
mos abusar da paciência do leitor, mas responder tal questão não é simples,
sendo porém necessário que consideremos um importante aspecto da ques-
tão. A questão fundamental a ser percebida, para a nossa discussão, é que a
razão humana se materializa, se corporifica sempre em algum contexto
lingüístico. Poderíamos praticamente dizer que não há razão sem linguagem,
o que ilustra a importância da Teoria da Linguagem para a ciência. Pois bem,
perguntemos neste ponto, ao biólogo, que linguagem estará ele utilizando
para investigar seu objeto de estudo, as mosquinhas? Talvez ele se surpre-
enda com a pergunta, mas provavelmente dirá, a língua portuguesa, ou seja,
a linguagem natural que aprendemos desde tenra idade. Talvez muitos dos
cientistas diriam o mesmo: a linguagem natural!
Voltemos aos lógicos e perguntemos a eles: qual é a porção da reali-
dade que o lógico busca compreender? Que linguagem estará ele empregan-
do para isso? Vejamos um objeto lógico que a maioria das pessoas certamen-
te conhece muito bem, os números naturais: 0, 1, 2, 3, ..., n, ... (sim! números
são entidades lógicas). Além dos números, a maioria das pessoas sabe so-
mar e multiplicar números, sabe também, comparar números, e assim por
diante.
Uma peculiaridade interessante numa investigação em Lógica. Um
biólogo que quer estudar as moscas, sabe onde ir buscá-las. Um médico
também sabe em que espaço se encontram as doenças que quer investigar,
em seres vivos. Mas, e quanto ao número 2, onde será que ele se encontra?
Uma questão como essa, que pode parecer irrelevante à primeira vista, tem
desdobramentos interessantes. Indague o leitor a si mesmo se o número 2
existe de fato ou não. Acreditamos que um matemático convencional não
poria dúvidas quanto à existência do número 2, mas certamente teria dificul-
dades em justificá-la. Para aguçarmos um pouco mais essa questão, o leitor
está certo de que este livro, que está diante dele, existe mesmo? É claro que
sim! diria. Se pedíssemos uma argumentação que justificasse essa certeza,
talvez uma resposta suficiente aos olhos do senso comum seria: Eu estou
vendo, tocando! Ou seja, justificaria a existência do livro pelos sentidos
usuais que os seres humanos são dotados. Infelizmente, não estaríamos
satisfeitos com essa argumentação. O tato pode falhar, a visão nos engana
freqüentemente. Logo, em termos racionais, os sentidos não são capazes de
nos fornecer fundamentos para a certeza absoluta da existência do livro. Se
o leitor aplicasse essa argumentação a ele próprio, as coisas ficariam ainda
piores. O leitor tem certeza absoluta que existe? O que pode parecer estra-
nho, mas inatacável, nessa linha de argumentação, é que não conseguimos
legitimar a existência das coisas somente por argumentos lógicos. Um dos
mais belos desenvolvimentos em cima desse argumento é devido ao mate-
mático e filósofo francês René Descartes, resumido na frase “penso, logo
existo”. Porém, o que podemos concluir daí é que existe pensamento, não o
ser.
Assim, necessitamos de uma postura para vermos as coisas. A maio-
ria absoluta dos lógicos e cientistas em geral adota a postura platônica
(muitas vezes inconscientemente). Grosso modo, Platão acredita na existên-
cia de dois mundos:
1) O mundo físico (em que vivemos) e
1 5
2) O mundo das entidades ideais.
Para nos familiarizarmos com o segundo mundo tomemos o exemplo
clássico da circunferência. Alguém consegue desenhar uma circunferência
perfeita? Acreditamos que o leitor tenha respondido não. Porém, para Platão
a circunferência perfeita existe, porém não no nosso mundo físico e sim no
mundo das entidades ideais. Além disso, Platão diz que as circunferências
do mundo físico são cópias imperfeitas da circunferência perfeita, do mundo
ideal. Todas as entidades lógicas estão no mundo das entidades ideais. Os
objetos são atemporais e não temos o conceito de espaço em tal mundo.
Nesse sentido, podemos dizer que o número 2 sempre existiu e sempre vai
existir independentemente da existência do homem e, além disso, não se
encontra em lugar algum.
Decorre daí, em particular, que a Lógica (ou Matemática) é a mesma
para todos. Platão nos diz também que o único acesso ao mundo das entida-
des ideais é feita através de nosso intelecto, e segundo ele, esta é a razão
pela qual poucos o conhecem, e que a nossa relação com tais entidades é de
descoberta (e não de criação, por exemplo). Os poucos que não seguem a
postura platônica são vistos como excêntricos, porém existem adeptos de
outras correntes, em número menor.
1.4 - Aspectos da Lógica Atual
As principais áreas de pesquisa em lógica clássica na atualidade po-
dem ser classificadasnas seguintes:
1. Sintaxe lógica: nesta área estudam-se certos constructos lingüísticos
formalizados, as linguagens artificiais. Estas servem para traduzir problemas
lógicos referentes ás linguagens da matemática e das ciências empíricas.
Também pode-se estudar questões ligadas ás linguagens naturais. Por meio
desta ferramenta, pode-se axiomatizar teorias, etc. e, como observamos ante-
riormente, obteve-se resultados extremamente fecundos como os teoremas
de incompleteza de Gödel.
2. Teoria de modelos: aqui se estudam as inter-relações existentes
entre as linguagens artificiais e certas estruturas conjuntistas às quais elas
se referem. Os contornos atuais deste ramo se devem a A. Tarski e A.
Robinson. Um dos resultados mais importantes da teoria de modelos foi a
matematização do conceito de verdade feita por Tarski, dando-se assim, uma
contribuição de profundo significado filosófico. Um dos resultados surpre-
endentes que o próprio Tarski observou foi de que a classe das proposições
verdadeiras é mais abrangente que a classe das proposições demonstráveis
em teorias matemáticas fortes e consistentes. A teoria de modelos possui
atualmente as mais variadas aplicações, por exemplo, em ciências empíricas
e na metodologia da ciência.
3. Teoria da recursão: grosso modo, a teoria da recursão trata do que é
exeqüível mecanicamente, computacionalmente, sem recurso á “inteligên-
cia”. Foram introduzidas certas máquinas ideais atualmente conhecidas como
máquinas de Turing (outros contemporâneos foram A. Church e E. Post).
1 6
Todos os grandes computadores da atualidade (inicialmente projetados e
construídos por J. von Neumann por volta de 1950) são realizações físicas da
máquina de Turing. São conhecidos resultados deveras interessantes na
teoria da recursão; atualmente uma das questões mais atraentes é a investi-
gação do que é computável, em particular, o problema conhecido como P =
NP. Não convém falar dele aqui por ser demasiado técnico.
4. Fundamentos da matemática: aqui um dos tópicos de pesquisa é a
obtenção de sistemas lógicos potentes capazes de fundamentar a matemáti-
ca clássica, investigar alguns de seus axiomas, analisando suas conseqüên-
cias tanto matemáticas quanto seu significado do ponto de vista das aplica-
ções. Alguns desses sistemas investigados são a teoria das categorias,
teoria dos topos, teoria dos tipos e outros sistemas. O interessante é que tais
sistemas extremamente fortes servindo de análise a própria matemática, en-
contraram aplicações em ciência da computação e Inteligência Artificial.
5. Lógica algébrica: a lógica serviu de catalisador deste ramo da mate-
mática pura. Todo sistema lógico é no fundo uma certa estrutura algébrica;
por exemplo, o cálculo proposicional clássico constitui numa álgebra de
Boole, que por sua vez é uma estrutura mais básica: ela constitui num anel de
Boole. Muitos problemas em lógica ou matemática, ou mesmo em ciência da
computação, podem ser melhor tratados como certas estruturas algébricas.
6. Aplicações da lógica em matemática: este tópico estuda-se aplica-
ções de técnicas da lógica para a solução de problemas em matemática. Por
meio deste expediente foram resolvidas algumas questões relevantes em
álgebra e topologia Também não teceremos mais comentários por ser uma
tema demasiado técnico.
Exercício 1. Responda sucintamente.
1. Dar algumas definições usuais do que é Lógica. A Lógica é
uma Ciência? Discutir de forma breve.
2. O que é postura platônica ?
3. Comente o por quê a lógica clássica esteve estagnada por
mais de dois milênios.
4. Quando pode ser considerado o início da lógica moderna ?
5. Quem foi o introdutor dos símbolos em lógica ?
6. O que é teoria dos conjuntos Cantoriana ?
7. A matemática que você viu até agora é feita em que teoria de
conjuntos ?
8. Qual é o prêmio de maior prestígio em matemática ?
9. Por quê não existe prêmio Nobel em Matemática ?
10. Quais são algumas das principais áreas de pesquisa em Lógi-
ca Clássica na atualidade ?
1 7
2. INTRODUÇÃO AO CÁLCULO
PROPOSICIONAL
2.1 - Introdução
Neste capítulo trataremos alguns conceitos elementares da lógica
proposicional, de uma maneira intuitiva. Isto não nos impede, entretanto, de
sermos rigorosos em nosso tratamento. O cálculo proposicional é o estudo
da linguagem proposicional. Ela estuda basicamente cinco símbolos:
1. Negação: ¬
2. Conjunção: ^
3. Disjunção: ∨
4. Implicação: →
5. Bi-implicação: ↔
2.2 Os paradoxos
Os paradoxos ou antinomias foram objeto de estudos e inquietações
por parte de filósofos e lógicos, desde os tempos da Antiga Grécia. Sem
muito rigor, os paradoxos podem ser classificados em paradoxos semânticos
e paradoxos lógicos. Vejamos alguns.
Paradoxos semânticos.
1)Paradoxo do mentiroso.
Dentre os paradoxos desta categoria, destaca-se aquele descoberto
pelo filósofo grego Eubúlides de Mileto (384-322 a.C.) conhecido popular-
mente como o paradoxo do mentiroso. Eubúlides foi professor de Demóstenes,
contemporâneo e declarado inimigo de Aristóteles.
Teçamos algumas considerações sobre esse assunto.
Inicialmente, trata-se do senso comum que toda sentença declarativa
da língua portuguesa ou é verdadeira ou é falsa, nunca ambas simultanea-
mente. Suponhamos, por exemplo, que, num quadro negro, se escreva a
seguinte (única) frase :
Verifica-se, neste caso, prontamente, que a sentença S1 constitui uma
S1 : ‘A sentença escrita neste quadro contém oito palavras’.
1 8
sentença verdadeira, pois S1, contém efetivamente, oito palavras.
Consideremos agora esta outra sentença:
S2 : ‘A sentença escrita neste quadro contém onze palavras’.
Evidentemente trata-se de uma sentença falsa pois S2 contém oito
palavras e não onze.
Passemos a considerar agora esta terceira sentença, de interesse para
nosso argumento:
S3 : ‘A sentença escrita neste quadro é falsa’.
Constitui S3 uma sentença verdadeira ou falsa ?
Analisemo-la: observemos, preliminarmente, que S3 se trata de uma
sentença declarativa, legítima do ponto de vista gramatical e, pelo exposto,
ou S3 é verdadeira,
ou S3 é falsa.
Se S3 for verdadeira, é verdadeira S3 - é verdadeiro que ‘A sentença
escrita neste quadro é falsa’ - e, portanto, concluímos que S3 é falsa.
Analogamente, se S3 é falsa, é falsa S3 - é falso que ‘A sentença
escrita neste quadro é falsa’ - logo, deduzimos que S3 é verdadeira.
Por conseguinte, S3 é verdadeira se e somente se S3 é falsa !
Tal é o paradoxo do mentiroso. Ressaltamos que esta antinomia é de
difícil solução, e constitui, até agora, um genuíno paradoxo.
2) Paradoxo do cartão
Proposto pelo matemático britânico P. Jourdain, em 1913: suponha-se
que numa das faces de um cartão esteja escrita a frase
Pergunta-se, a sentença escrita em cada um dos lados do cartão é
verdadeira ou falsa ? E a resposta é que cada uma das sentenças é verdadeira
se, e somente se, for falsa.
3) Paradoxo de Grelling
Proposto em 1908 por Leonhard Nelson e Kurt Grelling, da seguinte
maneira: definimos os adjetivos como autológicos, se a propriedade que ele
denota pode ser atribuída a ele mesmo. Assim, os adjetivos “curto” e
“proparoxítona” são autológicos, enquanto os adjetivos que não possuem
tal propriedade de denotarem atributos que não sejam aplicados a si própri-
os, chamam-se heterológicos. “Longo”, “oxítona” e “verde” são, portanto,
adjetivos heterológicos. Consideremos agora o adjetivo “heterológico”. Se
“heterológico” for heterológico, então ele é autológico. Se “heterológico”
 
A sen tença escrita no verso 
deste ca rtão é verdade ira . 
A sen tença escrita no verso 
deste ca rtão é fa lsa . 
1 9
não for heterológico, ou seja, autológico, ele é heterológico. Por conseguin-
te, o adjetivo “heterológico” é, simultaneamente, heterológico e não
heterológico.
4) Paradoxo de Berry
Proposto em 1906. Existe um número finito de símbolos (letras, sinais
de pontuação, etc.) na língua portuguesa. Então, existe um número finito de
expressões em nossa língua que contem menos de 200 símbolos, mesmo
contando as repetições. Há, portanto, um número finitode inteiros positivos
que podem ser denotados por expressões da língua portuguesa que contem
menos de 200 símbolos. Agora consideremos k como sendo “o menor intei-
ro positivo que não se consegue denotar numa expressão em português
com menos de 200 símbolos”. Ora, a expressão em itálico acima tem menos
de 200 símbolos, e é a própria expressão do inteiro positivo k.
5) Paradoxo do barbeiro.
Numa pequena cidade do interior vive um barbeiro, muito conhecido
dos moradores da cidade, que barbeia todas (e somente aquelas) pessoas
moradoras da cidade que não se barbeiam sozinhas. Ora, o barbeiro é um
morador da cidade. Coloca-se a questão: quem faz a barba do barbeiro ?
É óbvio que:
ou ele se barbeia,
ou ele não se barbeia.
Portanto, como o leitor se apercebe, um tal barbeiro se barbeia se e
somente se ele não se barbeia. Adotando-se a Lógica Clássica, tal barbeiro
não existe.
6) Paradoxo do exame
Numa segunda-feira, certa professora informa seus alunos de que eles
terão um exame nos próximos quatro dias, mas que não deverão saber o dia
exato, a não ser no momento de prestar o exame. Os alunos, então, raciocina-
ram assim: o exame não pode ocorrer na sexta-feira (o quarto dia), pois, em
caso contrário, eles saberiam de antemão, na quinta-feira, depois das aulas,
que ele seria na sexta-feira, quebrando-se, assim, o acordo de ser surpresa.
De modo análogo, não pode ser na quinta-feira. Nem na quarta-feira, nem na
terça-feira. Logo, não pode haver exame nas condições formuladas pela mes-
tre. Porém, esta, digamos na quarta-feira, pode aplicar o exame, satisfazendo
as condições impostas.
7) Paradoxo dos insociáveis
Os habitantes de uma comunidade formam entre si vários tipos de
associações ou clubes. Um habitante pode pertencer a mais de um clube.
Cada clube tem o nome de um habitante. Não existem dois clubes diferentes
com o nome do mesmo habitante. E toco habitante tem um clube com seu
nome. Não é necessário que uma pessoa seja membro do clube que leva seu
nome. Se a pessoa é membro do clube que leva seu nome, ela é chamada de
uma pessoa sociável. Se a pessoa não é membro do clube que tem seu nome,
ela é então chamada de uma pessoa insociável. É possível formar um clube
contendo todos os insociáveis da comunidade?
2 0
Paradoxo semiótico.
Seja A o conjunto dos números naturais de 1 a 12, inclusive, A = {1, 2,
..., 11, 12}. Imaginemos um sistema de notação N para eles. Usaremos os
numerais 1, 2, ... , 8 e 9 e sinais 0, 1, 2, ... , 9, 10, 11 e 12, para denotá-los, como
usualmente, e mais o signo j.
O signo j denotará o menor elemento de A que no sistema de notação
N não pode ser denotado por um único símbolo. N aparenta ser, sem sombra
de dúvida, um sistema de notação cordial. Porém, vejamos o que ocorre com
o número 10. Suponhamos que 10 seja denotável por um único símbolo de N;
então esse símbolo obviamente só pode ser j, e 10 não é denotável por um
único símbolo de N, de conformidade com a definição de j. Admitamos,
então, que 10 não seja denotável por um único símbolo de N; daí advém que
10 é o menor número de A que não pode ser denotado por um único símbolo
e que, em conseqüência, deve ser denotado por j. A conclusão é a de que 10
é denotável por um único símbolo de N se, e somente se, não o for. Adotan-
do-se a Lógica Clássica, o sistema notacional N não existe.
Paradoxo da Física Quântica.
O paradoxo a seguir acha-se ligado á dualidade onda-corpúsculo do
elétron. No chamado experimento dos dois orifícios, enviam-se elétrons so-
bre um anteparo, passando por um obstáculo, onde há dois orifícios conve-
nientemente colocados, e o feixe de elétrons produz no anteparo configura-
ções de interferência, comprovando o caráter ondulatório. Porém, se colo-
carmos um detetor de partículas logo após qualquer um dos orifícios, tudo
se passa como se o feixe fosse composto de partículas, que atravessam o
obstáculo, normalmente, através dos orifícios. Logo, o elétron é onda e cor-
púsculo ao mesmo tempo. O físico acata a solução de Copenhague: mantém-
se que nada se pode conhecer do interfenômeno.
Paradoxos lógicos.
Os paradoxos desta categoria, diferentemente dos semânticos, envol-
vem certas noções lógicas, principalmente relacionadas coma teoria intuiti-
va das coleções.
1)Paradoxo de Russell1
Vejamos inicialmente o chamado Paradoxo de Russell. A exposição um
tanto quanto detalhada possui o fito de relembrar alguns conceitos funda-
mentais da teoria intuitiva de conjuntos.2
Dentro da posição platônica subjacente à teoria dos conjuntos, um
dos princípios básicos que regem essa teoria, de conteúdo bastante eviden-
te, é o seguinte:
Princípio da separação (ou da compreensão): Toda propriedade P
determina um certo conjunto, a saber, o conjunto formado pelos objetos que
possuem a propriedade P e apenas por eles.
Exemplo. Consideremos a propriedade de ser homem. Ela determina o
1 Descoberto independentemente por E. Zermelo.
2 Uma exposição da teoria elementar de conjuntos pode ser vista em [Abe &
Papavero 92].
2 1
conjunto
{x | x é um homem} = conjunto dos homens.
Exemplo. Se P ≡ser satélite natural da Terra. Então:
{x | x é um satélite natural da Terra } = {Lua}
Exemplo. Seja P ≡ pessoas que sonham e não-sonham simultaneamen-
te. Então:
{x | x é uma pessoa que sonha e não sonha simultaneamente} = ∅
Como dissemos há pouco, é bastante intuitivo que, dada uma propri-
edade qualquer, ela determina o conjunto dos elementos que satisfazem a
referida propriedade.
O princípio em questão, porém, na realidade, é incompatível com a
lógica elementar clássica. Isto foi constatado em 1902 pelo renomado lógico
inglês Bertrand Russell, e o paradoxo por ele descoberto leva o nome de
antinomia (ou paradoxo) de Russell. Vamos agora expô-lo:
Inicialmente, observemos que existem conjuntos X tais que X não é
membro de si mesmo, isto é:
X ∉ X
Exemplo. O conjunto de todos os homens, por não ser um homem,
não é membro de si mesmo.
Exemplo. Dado o conjunto A = {0, 1, 2}, é evidente que A ∉ A.
Observemos, também, que existem ‘conjuntos’ X tais que são mem-
bros de si mesmos, isto é, X ∈ X.
Exemplo. O ‘conjunto’ de todos os conjuntos, por ser um conjunto, é
obviamente membro de si mesmo.
Exemplo. Um caso interessante é o seguinte: seja o ‘conjunto’
A = {B | o número de elementos de B é maior ou igual a 3}.
Existem muitos conjuntos com pelo menos 3 elementos:
B1 = {0, 1, 2, 3}
B2 = conjunto das bananas de São Paulo
B3 = {a, b, c, d, e}
B4 = conjunto dos planetas de nosso sistema solar, etc.
Logo, A possui mais do que 3 elementos e, consequentemente, A ∈ A.
Exemplo. Seja a um objeto. Formemos o conjunto dos objetos distin-
tos de a,
{x| x ¹ a}. Obviamente tal conjunto é distinto de a e, por conseguinte,
pertence a ele mesmo.
Consideremos, agora, o seguinte conjunto:
R = {X | X ∉ X}.
2 2
Por um princípio da Lógica Clássica (Princípio do Terceiro Excluído),
ou R ∈ R ,
ou R ∉ R.
Se R ∈ R, concluímos que R ∉ R.
Se R ∉ R, concluímos que R ∈ R.
Logo, R ∈ R se e somente se R ∉ R.
Tal é a famosa antinomia de Russell.
Historicamente, o desgosto que causou a descoberta da antinomia de
Russell entre os especialistas em Lógica Matemática foi bem expresso por G.
Frege em 1903, num apêndice ao segundo volume de seu Grundgesetze:
“Nada pior praticamente pode acontecer a um autor científico do que
ver uma das fundações de seu edifício ser abalada depois de ter terminado
a obra. Fui colocado nessa posição por uma carta contendo o paradoxo de
Mr. Bertrand Russell exatamente quando a impressão deste segundo volume
estava quase pronta ... Solatium miseris, socios habuisse malorum. Eu tam-
bém tenho este consolo, se é que é consolo; pois todos aqueles que em suas
demonstrações empregaram extensões de conceitos, classes, conjuntos, in-
clusive sistemas de Dedekind, estão nesta mesma posição. Não é só uma
questão de meu método particular de colocar as fundações, mas trata-se de
saber se alguma fundamentação lógica para a Matemática é possível ...”
(Frege, 1964).
2) Paradoxo de Cantor
Por exigir um resultado da Teoriados Conjuntos, que é o Teorema de
Cantor, o paradoxo será apresentado de modo resumido, em suas idéias
principais. Mas, antes disso, cumpre colocar a idéia básica do Teorema de
Cantor, a de que o número de elementos de um conjunto qualquer é sempre
menor que o número de elementos do conjunto formado por todos os seus
subconjuntos. Em linguagem simbólica: #A < #2A. Vamos ao paradoxo, en-
tão: seja C o conjunto de todos os conjuntos. Portanto, cada subconjunto
de C é também um membro de C. Assim, o conjunto potência de C é
subconjunto de C. Em linguagem da teoria dos conjuntos, 2C ⊂ C. Mas, 2C
⊂ C implica em #2C ≤ #C, o que é absurdo, de acordo com o Teorema de
Cantor, segundo o qual, #C < #2C .
3) Paradoxo de Burali-Forti
Proposto em 1897, esse paradoxo exige uma familiarização do leitor
com a Teoria dos Números Ordinais. Em linhas gerais, ele é análogo ao
paradoxo de Cantor, visto acima. Não faria sentido apresentá-lo neste texto,
a não ser resumidamente, por tratar de um conteúdo por demais específico
da matemática. Em linhas gerais, o paradoxo seria o seguinte: dado qualquer
número ordinal, existe um outro número ordinal maior que ele. Mas o número
ordinal determinado pelo conjunto de todos os números ordinais é o maior
número ordinal existente.
2.3 Linguagens artificiais
Os poucos exemplos de paradoxos semânticos colocam em relevo o
2 3
fato de qualquer linguagem natural, como por exemplo, a língua portuguesa,
não pode ser adequada ao tratamento rigoroso da lógica. Mais ainda, admi-
tindo-se certas leis básicas da lógica clássica, toda linguagem universal,
como tem a capacidade de referir-se a si própria, sem quaisquer restrições,
leva inevitavelmente a contradições. Isto foi observado no início deste sé-
culo pelo renomado lógico polonês Alfred Tarski. Necessitamos, então, cons-
truir uma linguagem que possibilite o tratamento da lógica. Uma tal lingua-
gem será usualmente chamada de linguagem artificial (de artefato) ou lingua-
gem formal (de forma).
A consideração de linguagens artificiais nos obriga a pensar certas
questões. Ao termos uma linguagem artificial em tela, automaticamente, te-
mos uma linguagem que diz respeito a ela. A essa linguagem damos a deno-
minação de meta-linguagem. Observamos, então, que para construirmos a
linguagem artificial em questão (que denominaremos de linguagem objeto),
obviamente serão empregados os recursos oferecidos pela meta-linguagem.
Esta observação é fundamental, porquanto veremos posteriormente que, no
caso da consideração da linguagem proposicional, por exemplo, faremos
uso, além da linguagem portuguesa, de porções da própria Matemática e de
noções ditadas pelo “senso comum”. À primeira vista, parece que nos enre-
damos num círculo vicioso, porém, à medida em que o leitor se familiarize
com os conceitos desenvolvidos notará que não há tal inconveniente.
Figura 1
Logo, ao considerarmos uma linguagem-objeto, necessitamos de uma
espécie de pano de fundo. Mais pormenorizadamente, tal pano de fundo é
qualquer modelo (ou, o que dá no mesmo, a própria teoria) de teoria dos
conjuntos (Cantoriana). Mais ainda, freqüentemente utilizamos uma aritmé-
tica usual e, portanto, uma meta-matemática na meta-linguagem. O leitor
zeloso, notará então que o estudo feito em tais linguagens artificiais será
feito olhando-se de “fora”, ou seja, todos os resultados que puderem ser
observados, serão observados de um lugar que não é o mesmo onde eles
efetivamente ocorrem. Por conseguinte, tratar-se-ão de meta-teoremas. Uma
importante observação, feita a partir disso, é a de que quase sempre estamos
trabalhando e realizando meta-matemática. Daí, o que chamaríamos, licenci-
osamente, de uma equação fundamental:
Matemática = Meta-Matemática !!
Esta situação é ilustrada magnificamente por Nietzsche: “ ... a frontei-
 
 
L
L in
Linguagem Objeto
Meta-linguagem
(Teoria dos conjuntos
Cantoniana)Linguagem Proposicional
2 4
ra da Ciência possui uma infinidade de pontos. Todo homem nobre e
talentoso, antes de atingir a metade de sua carreira, defronta-se com al-
gum ponto da fronteira que desafia sua compreensão, independentemente
de saber como a região pode ser inteiramente mapeada. Quando o pesqui-
sador, levado à periferia, compreende como a Lógica, neste lugar, curva-se
sobre si mesma e morde a própria cauda, fica perplexo com uma nova
espécie de percepção: uma percepção trágica que requer, para se tornar
tolerável, o remédio da arte.”
Por exemplo, havia você percebido que os Teoremas que aprendeu
sobre Geometria ou Cálculo Diferencial e Integral são, na realidade, meta-
teoremas?
Exercício 1. Discutir pelo menos dois paradoxos semânticos da lin-
guagem natural, não vistos no texto, mostrando, então, a inadequação do
uso das linguagens naturais para o desenvolvimento de teorias lógicas.
Exercício 2. Pesquise sobre “teoremas” da Geometria Euclidiana e
determine se estes são realmente teoremas ou meta-teoremas da Geometria
Euclidiana.
2.4 – A linguagem universal da lógica
A linguagem da teoria dos conjuntos constitui na linguagem univer-
sal da lógica.
Exercício 1. Dê exemplos de linguagens artificiais. Qual é a linguagem
universal da Lógica?
2.5 - Conectivos lógicos e tabelas-verdade
No estudo da linguagem proposicional, apesar de ser formal, invoca-
remos muitas vezes proposições da língua portuguesa, com o fito de ameni-
zar a exposição. Esperamos que o leitor se aperceba de um rigor saudável
que estará subjacente às discussões que se seguem, apesar de consciente-
mente cometer tal heresia.
As sentenças que estão em tela são as ditas sentenças declarativas.
Tais sentenças são sentenças, como o próprio nome diz, que declaram (afir-
mam) algo. Portanto, o que afirmam é passível de ser considerada ou como
verdadeira, ou como falsa. Vejamos alguns exemplos.
Exemplo 1. Exemplos de sentenças declarativas.
1. A neve é branca. (verdadeira)
2. 2 + 2 = 5 (falsa)
3. Há cinco milhões de grãos de areia na lua. (ninguém contou os
grãos; mas sabemos ou que é verdade, ou que é falsa (provavelmente falsa)).
Daqui em diante, toda sentença (declarativa) que trabalharmos é ou
verdadeira ou falsa, mas nunca ambas simultaneamente. Daí a lógica clássica
ser chamada de lógica bivalente. Existem várias notações para designarmos
os valores-verdade ou valores-lógicos das sentenças.
2 5
Adotaremos neste texto a notação booleana:
“1” designa o valor-verdade “verdadeiro”
“0” designa o valor-verdade “falso”
1) Negação
Dada a proposição A podemos considerar a proposição ( A) denomi-
nada a negação de A. Como a proposição A ou é verdadeira ou falsa, a
tabela-verdade da negação toma então a seguinte forma:
Tabela-verdade da negação.
A ( ¬A)
1 0
0 1
A proposição A é verdadeira se e somente se sua negação (¬A) é falsa.
Exemplo 2.
1. Seja A ≡ (2 + 2 = 4) (no caso, verdadeira). Então ( ¬A) ≡ ( ¬(2 + 2 = 4))
constitui uma sentença falsa. Na aritmética comum, costuma-se escrever a
última expressão como 2 + 2 ≠ 4.
2.Seja B ≡ (2 ∈ {1, 3, 5}) (no caso, falsa). Logo, (¬B) ≡ ( ¬(2 ∈ {1, 3, 5})
constitui uma sentença verdadeira. Na linguagem da Teoria dos Conjuntos
(ver [Abe & Papavero, 92]), a última expressão é usualmente escrita como 2
∉ {1, 3, 5}.
Mesmo na linguagem comum, a tabela-verdade se aplica:
Exemplo 3. Seja A ≡ “A neve é branca” (verdadeira). Sua negação é
(¬A) ≡ “A neve não é branca” (falsa).
Também, A ≡ “A cidade de São Paulo é pequena” (falsa). Sua negação
é (¬A) ≡ “A cidade de São Paulo não é pequena” (verdadeira).
Algumas negações delicadas.
Exemplo 4. Vejamos algumas negações de sentenças:
1. A ≡ “Todo homem é mortal”
Qual é a negação de A ? O mais simples é escrever
(¬A) ≡ “Nem todo homem é mortal” ou “ Não é que todo homem é
mortal”. Porém, há outras sentenças equivalentes que queremos chamar a
atenção: dizer “Nem todo homem é mortal” é o mesmo que dizer “Existem
homens que não são mortais” ou “Há homens imortais”.
2. A ≡ “Existem pessoas inseguras”
Qual é a negação de A ? O mais simples é escrever
(¬A) ≡ “Não existem pessoas inseguras”. Porém,esta é equivalente a
escrever “Todas as pessoas não são inseguras” (pense bem !) ou “Todas as
pessoas são seguras”.
3. A ≡ “Todos os animais mamíferos são animais vertebrados”.
(¬A) ≡ “Nem todos os animais mamíferos são animais vertebrados” ou
2 6
“Não é que todos os animais mamíferos são animais vertebrados”. Ou ainda,
“Existem animais mamíferos que não são animais vertebrados” ou “Há ani-
mais mamíferos que são animais invertebrados”.
4. A ≡ “Existem pessoas que se preocupam em ética”.
(¬A) ≡ “Não existem pessoas que se preocupam em ética” ou “Não
existem pessoas que se preocupam em ética”. Ou ainda, “Todas as pessoas
não se preocupam com a ética”
5. A ≡ “Todo número par é divisível por dois”
(¬A) ≡ “Nem todo número par é divisível por dois” ou “Não é que todo
número par é divisível por dois”. Ou ainda, “Existem números pares que não
são divisíveis por dois” ou “Há números pares que indivisíveis por dois”.
Exercício 1. Faça o que se pede.
1. Em cada item são dadas duas sentenças. Responda se a segunda
frase é ou não é a negação da primeira. Caso não seja, determine essa nega-
ção.
a) Estou feliz. Não estou feliz.
b) Todos os elefantes são cor-de-rosa. Um elefante não é cor-de-rosa.
c) Alguns cavalos são brancos. Alguns cavalos são pretos.
d) Todos os cavalos são pretos. Alguns cavalos são brancos.
e) O sol está brilhando. O sol não está brilhando.
f) Estou certo. Estou errado.
g) Nenhum homem é um elefante. Algum homem é um elefante.
h) Todos os tomates são vermelhos. Todos os tomates são amarelos.
i) Algumas vezes estou certo. Todas as vezes estou certo.
j) Há sempre alguém na portaria. Nem sempre há alguém na portaria.
2. Em cada sentença abaixo, determine a respectiva negação.
a) Hoje é sábado. b) Lógica é fácil.
c) Esta sala está muito fria. d) É falso que a vida é bela.
e) Não é verdade que não se sabe que fez isso. f) Existem políticos trabalhadores.
g) Todas as ruas da cidade estão esburacadas. h) Toda ação provoca uma reação.
i) Não vou viajar. j) Irei a outro lugar.
3. Em cada item são dadas duas sentenças. Responda se a segunda
frase é ou não é a negação da primeira. Caso não seja, determine a respectiva
negação.
a) Todos os estudantes são responsáveis. Alguns estudantes são irresponsáveis.
b) A neve é branca. A neve não é branca.
c) Ele é rico. Ele é pobre.
d) Eu creio na honestidade. Ninguém é honesto.
e) Nenhum homem é uma ilha. Algum homem é uma ilha.
 f) Todos os livros são interessantes Um livro não é interessante.
 g) Há sempre alguém feliz. Nem sempre há alguém feliz.
 h) Alguns estudantes são responsáveis. Alguns est. são irresponsáveis.
 i) Todos os exercícios são instrutivos. Todos os exercícios são fáceis.
2 7
 j) Algumas vezes me engano. Todas as vezes me engano.
4. Em cada sentença abaixo, determine a respectiva negação.
a) Há alunos na sala. b) Esta aula é muito importante.
c) Algumas pessoas gostam de chocolate. d) Todos votaram nele.
e) Ninguém foi ao aniversário. f) Existem pessoas estudiosas.
g) É falso que esta moeda é verdadeira. h) Todas as pessoas são felizes.
i) Há uma pedra no meio do caminho. j) Se fosse fácil, já estaria feito.
k) Há sempre alguém no saguão. l) Sempre há alguém no saguão.
m) Não é o caso de não ser reprovado. n) É o caso de ser aprovado.
5. Em cada item são dadas duas sentenças. Responda se a segunda
frase é ou não é a negação da primeira. Caso não seja, determine essa nega-
ção.
a) Estudo e trabalho. Não estudo nem trabalho.
b) O sol brilha e o ar está quente. O sol não brilha ou o ar não está quente.
c) Estou certo e você está errado. Estou errado ou você está certo.
6. Em cada sentença abaixo, determine a respectiva negação.
a) Hoje é feriado ou domingo. b) A sala e o quarto estão escuros.
c) A rua está esburacada e mal iluminada. d) Se for feriado ou domingo, vou viajar.
e) Se for feriado e o tempo estiver ensolarado, vou viajar.
2) Conjunção
Dadas as proposições A e B podemos considerar a nova proposição
(A ∧ B), a conjunção de A e B.
A veracidade ou falsidade da proposição (A ∧ B) depende da veraci-
dade ou falsidade da proposição A e da proposição B. Logo, a tabela-verda-
de de (A ∧ B) possui quatro possibilidades de valores-verdade para A e B.
1. A é verdadeira e B também é verdadeira.
2. A é verdadeira e B é falsa.
3. A é falsa e B é verdadeira.
4. A é falsa e B também é falsa.
Postulamos que a proposição (A ∧ B) é verdadeira se e somente se
ambas as proposições A e B são verdadeiras. A proposição (A ∧ B) é falsa se
e somente se uma das proposições A ou B for falsa.
As considerações acima podem ser esquematizadas como se segue:
Tabela-verdade da conjunção:
2 8
A B (A ∧ B)
1 1 1
1 0 0
0 1 0
0 0 0
Exemplo 5. Consideremos as seguintes proposições:
1) [(2 + 4 = 4) ∧ (1 ≤ 2)] Esta proposição é verdadeira
 verdadeira verdadeira
2) [(2 + 4 = 4) ∧ (1 ≥ 2)] Esta proposição é falsa
 verdadeira falsa
3) [(2 + 4 ≠ 4) ∧ (1 ≤ 2)] Esta proposição é falsa
 falsa verdadeira
4) [(2 + 4 ≠ 4) ∧ (1 ≥ 2)] Esta proposição é falsa
 falsa falsa
Observação. Convém frisar algumas diferenças entre os conectivos
∧ (lógico) e “e” (da língua portuguesa). Na linguagem proposicional, se A e
B são fórmulas, então (A ∧ B) e (B ∧ A) são logicamente equivalentes. Com
efeito, vejamos os exemplos seguintes:
a) (2 + 2 = 4 ∧ 1 ≤ 2) e
b) (1 ≤ 2 ∧ 2 + 2 = 4)
possuem o mesmo significado.
Na linguagem natural, porém, nem sempre isto ocorre. Vejamos os
seguintes exemplos:
a) Sejam A ≡ ‘João é inteligente’ e B ≡ ‘João lê as obras de Platão’. (A ∧ B)
representa a sentença ‘João é inteligente e João lê as obras de Platão’. (B ∧
A) a sentença ‘João lê as obras de Platão e João é inteligente’. O senso
comum nos indica que (A ∧ B) e (B ∧ A) se eqüivalem.
b) Sejam agora A ≡ ‘Maria casou’ e B ≡ ‘Maria teve um filho’. (A ∧ B)
representaria a sentença ‘Maria casou e Maria teve um filho’. (B ∧ A) a
sentença ‘Maria teve um filho e Maria casou’. Neste caso, note-se, não há
uma equivalência entre as sentenças (A ∧ B) e (B ∧ A). Na linguagem natural
insinua-se quase sempre uma certa seqüência temporal (e às vezes uma
implicação de causalidade).
A observação se aplica também aos demais conectivos.
Exercício 2. Faça o que se pede.
1. Em cada item são dadas duas sentenças. Escreva a conjunção delas.
a) A ≡ João estuda. B ≡ Não estudo.
b) A ≡ O sol brilha. B ≡ O ar não está quente.
c) A ≡ Estou certo. B ≡ Estou errado.
2. Em cada sentença abaixo, determine a respectiva negação.
a) Hoje é feriado e domingo. b) A sala e o quarto estão escuros.
c) A rua está esburacada e mal iluminada. d) Clarissa vai á praia e tomar sol.
e) Ela é bonita e inteligente.
2 9
3. Admitindo-se o senso comum, diga se são verdadeiras ou falsas.
a) O sol brilha e a nuvem é verde.
b) 2 + 2 = 4 e ¬ = {¬}
c) Curitiba é a capital do Paraná e Paris é a capital da França.
4. Obtenha a negação das seguintes proposições:
a) Bianca não estuda e é mal educada.
b) Está chovendo e fazendo frio.
c) Chiquinho é esperto e atento.
3) Disjunção
Dadas as proposições A e B podemos considerar a nova proposição
(A ∧ B), a conjunção de A e B.
Postulamos que a proposição (A ∨ B) é verdadeira se e somente se
uma das proposições (ou ambas) A ou B são verdadeiras. A proposição (A ∨
B) é falsa se e somente se quando ambas proposições A e B for falsa.
As considerações acima podem ser esquematizadas como se se-
gue:
Tabela-verdade da disjunção:
A B (A ∨ B)
1 1 1
1 0 1
0 1 1
0 0 0
Exemplo 6. Consideremos as seguintes proposições:
1) [(2 + 4 = 4) ∧ (1 ≤ 2)] Esta proposição é verdadeira
 verdadeira verdadeira
2) [(2 + 4 = 4) ∧ (1 ≥ 2)] Esta proposição é verdadeira
 verdadeira falsa
3) [(2 + 4 ≠ 4) ∧ (1 ≤ 2)] Esta proposição é vardadeira
 falsa verdadeira
4) [(2 + 4 ≠ 4) ∧ (1 ≥ 2)] Esta proposição é falsa
 falsa falsa
Na linguagem natural,muitas vezes o conectivo “ou” possui idéia de exclu-
são:
“Bianca vai ao supermercado ou vai á escola”. Neste caso, é claro que Bianca
vai fazer uma coisa ou outra, mas não ambas simultaneamente.
O conectivo que leva em conta a observação anterior chama-se
disjunção exclusiva.
3 0
Exercício 3. Faça a tabela-verdade da disjunção exclusiva.
Em Lógica, como se observou, uma disjunção é verdadeira quando
uma das proposições constituintes é verdadeira ou, também, quando ambas
são verdadeiras simultaneamente.
Exercício 4. Faça o que se pede.
1. Sejam as proposições A ≡ “O livro é interessante” e B ≡ “O livro é caro”.
Fornecer uma sentença na linguagem natural que descreva cada uma das
simbolizações abaixo:
 a) (¬A) b) (A ∧ B) c) (A ∨ B) d) (B ∨ (¬A))
 e) ((¬A) ∧ (¬B))
2. Sejam as sentenças: A ≡ “A neve é branca” e B ≡ “O sol é um astro”.
Determinar o valor-verdade das sentenças abaixo:
 a) [A ∧ (¬B)] b) [¬(A ∨ B)] c) [(¬A) ∨ B] d) [(¬A) ∧ (¬B)]
e) [A ↔ (¬B)]
3. Em que casos as sentenças abaixo são falsas? (Em cada item estude todas
as possibilidades)
a) Ela é mineira e ele é paraense.
b) Ela é mineira ou ele é paraense.
c) É falso que ela é mineira e ele é paraense.
d) É falso que ela é mineira e é falso que ele é paraense.
4. Sejam as expressões A ≡ “O céu é azul”, B ≡ “Deus existe” e C ≡ “O Sol
gira em torno da Terra”. Fornecer uma sentença na linguagem natural que
descreva cada uma das afirmações abaixo:
a) (¬A) b) (A ∧ B) c) ((A ∨ B) ∧ C)
d) (B ∨ (¬C)) e) [(¬A) ∧ (¬B)] f) [¬((¬A) ∨ C)]
g) [¬(A ∨ (¬¬B))] h) (C ∧ (¬B))
5. Escreva as sentenças em linguagem simbólica abaixo utilizando os
conectivos ¬, ∧ e ∨.
a) Não é verdade que Galileu esteja certo.
b) A água não pode ser simultaneamente líquida e sólida.
c) O seguro da casa inclui incêndio ou roubo.
d) Compro ou não compro.
e) Não estudarei hoje, mas estudarei amanhã e quarta-feira.
6. Determinar a tabela verdade das sentenças abaixo, sendo
A ≡ ∅ = {∅}, B ≡ ∅ = ∅, C ≡ {∅} = {{∅}}:
a) [A ∧ (¬C)] b) [¬(B ∨ C)]
c) [(¬B) ∧ (¬C)] d) [¬(A ∧ (¬B))]
f) [¬[(¬A) ∧ (¬B)]] g) [A ∨ (¬(A ∧ C))]
3 1
7. Em que casos as sentenças abaixo não são falsas? (Estude todas as
possibilidades)
a) A Terra gira e Maria gosta de José.
b) Passarei em lógica ou 2 + 2 = 4.
c) É falso que ela gosta dele e é falso que ele gosta dela.
d) É falso que ela gosta dele e ele gosta dela.
8. Entendemos por disjunção exclusiva ao tipo de disjunção em que as
sentenças não podem ocorrer simultaneamente, como no exemplo “Ela está
alegre ou não está alegre”. Definir, nos casos abaixo se o ou corresponde à
disjunção inclusiva ou exclusiva.
a) Eu menti ontem ou mentirei amanhã.
b) Meu time é o campeão deste ano ou não é o campeão deste ano.
c) Ela se formou em 1993 ou em 1998.
d) Com sol ou com chuva, você trabalhava.
e) O terno é de Bentinho ou de Escobar.
4) Implicação
Dadas as proposições A e B podemos considerar a nova proposi-
ção (A → B), a implicação de B por A.
A proposição A chama-se antecedente da implicação (A → B) e B
chama-se o conseqüente da implicação (A → B).
Postulamos que a proposição (A → B) é falsa se e somente se o
antecedente A é verdadeiro e o conseqüente B é falso. Nos demais casos, a
proposição (A → B) é verdadeira.
As considerações acima podem ser esquematizadas como se se-
gue:
Tabela-verdade da implicação:
A B (A → B)
1 1 1
1 0 0
0 1 1
0 0 1
Exemplo 7. Consideremos as seguintes proposições:
1) [(2 + 4 = 4) ∧ (1 ≤ 2)] Esta proposição é verdadeira
 verdadeira verdadeira
2) [(2 + 4 = 4) ∧ (1 ≥ 2)] Esta proposição é falsa
 verdadeira falsa
3) [(2 + 4 ≠ 4) ∧ (1 ≤ 2)] Esta proposição é verdadeira
 falsa verdadeira
4) [(2 + 4 ≠ 4) ∧ (1 ≥ 2)] Esta proposição é verdadeira
 falsa falsa
3 2
Observação. Teçamos algumas considerações sobre a tabela-verdade refe-
rente à implicação.
1) A tabela é positivamente obscura no uso ordinário. Vejamos alguns exem-
plos.
Leis causais. Quando a implicação lógica é interpretada como causar na
linguagem natural.
1. Sejam as sentenças
A ≡ “Este pote d’água for colocado no fogo no instante t0” e
B ≡ “A água congelará”.
A sentença A só é falsa no caso de o pote não ser colocado no fogo
no instante indicado. Coloquemos o pote no fogo num instante t distinto de
t0. Logo, A é falsa.
Consideremos a sentença
(A → B) ≡ “Se este pote d’água for colocado no fogo no instante t0 então a
água congelará”.
De acordo com a tabela-verdade da implicação, (A → B) é verdadeira, inde-
pendentemente do valor-verdade de B, o que configura uma situação absur-
da !
2. Sejam as sentenças
A ≡ “Se sua sogra chegar em sua casa exatamente no instante t0” e
B ≡ “Você ficará mais inteligente”.
A sentença A só é falsa no caso de sua sogra não chegar em sua
casa exatamente no instante indicado (o que é muito provável). Suponha-
mos que ela venha antes do instante t0. Logo, A é falsa.
Consideremos a sentença
(A → B) ≡ “Se sua sogra chegar em sua casa exatamente no instante t0 então
você ficará mais inteligente”.
De acordo com a tabela-verdade da implicação, (A → B) é verdadei-
ra, independentemente do valor-verdade de B, o que configura uma situação
absurda (convenhamos) !
Situações em que o antecedente não é um fato.
Consideremos a sentença:
Exemplo 8. A sentença ‘Se João Guimarães Rosa não tivesse escri-
to nenhuma obra literária, então não teria havido inflação em nenhuma época
em nosso país’ é admitidamente falsa, mesmo que o antecedente seja falso.
O mesmo se sucede com a sentença ‘Se Cabral não tivesse desco-
berto o Brasil, então homem não teria chegado á lua’.
2) Uma justificativa favorável que podemos oferecer para a tabela-verdade
da implicação é a seguinte: admitamos ser razoável a tabela-verdade da con-
junção. Para quaisquer sentenças A e B, é, então, razoável considerar a
3 3
sentença ((A ∧ B) → B) como verdadeira, quaisquer que sejam os valores-
verdade de A e B.
Assim, se A e B são ambas verdadeiras, (A ∧ B) é verdadeira, e, por
conseguinte, isto justifica a 1a linha da tabela.
Se A é falsa e B verdadeira, então (A ∧ B) é falsa. Este caso
corresponde à 3a linha da tabela.
Se A e B são ambas falsas, então (A ∧ B) é falsa, o que correspon-
dente à última linha da tabela.
3) Esta observação é citada em [Iséki & Abe 01]: “Temos certeza que o leitor
está perplexo que o valor-verdade de 0 → 0 e 0 → 1 é 1. Uma explicação
adequada é dada no exemplo a seguir. Estamos acostumados a dizer a seguinte
sentença: “se x é divisível por 10, então x é divisível por 2”. Se escrevermos
em símbolos obtemos
 x(x/10 → x/2).
(Aqui, a expressão x/a significa que x é divisível por a.) A expressão anterior
é amplamente aceita como verdadeira.. Como x é arbitrário, se fizermos x = 20,
temos 20/10 = 2 e 20/2 = 10 e, por conseguinte, como o antecedente e o
conseqüente são ambos verdadeiros, a expressão como um todo é verdadei-
ra (isto é, o valor verdade de 1 → 1 é associado 1). Se fizermos x = 8, o
antecedente é falso enquanto que o conseqüente é verdadeiro, ou seja temos
o caso 0 → 1; no entanto a expressão como um todo é verdadeira. Finalmen-
te, se fizermos x = 5, tanto o antecedente quanto o conseqüente são falsos,
porém a expressão como um todo é verdadeira.
Esta explicação é conhecida como interpretação do famoso lógico
polonês S. Lesniewski.
Convém ressaltar que nas considerações acima há uma questão
muito importante subjacente, ou seja, contém um problema de metodologia
matemática.
Questões da lógica proposicional levamos para uma estrutura ge-
neralizada denominada lógica de predicados, e ali podemos eleger respostas
adequadas.
Por exemplo, ainda sobre esse procedimento, sabemos que não
podemos efetuar subtrações quaisquer de números naturais. Porém, se es-
tendermos para os números inteiros , obtemos uma boa interpretação para a
subtração. Outro exemplo, o mesmo sedá quando uma equação quadrática
não é solúvel no conjunto dos reais, apelamos para o mundo dos números
complexos onde obtemos uma solução.
De modo geral, a observação importante é que ao considerarmos
uma estrutura básica, vários problemas têm uma resposta adequada em es-
truturas mais gerais.”
Exercício 5. Nas seguintes sentenças dizer qual é o antecedente e
qual é o conseqüente:
1. (2 + 2 = 7 → 2 + 1 = 0)
2. Det(M) = 0 implica que M não é invertível.
3. Se f : ℜ → ℜ é uma função derivável, então f : ℜ → ℜ é uma função
contínua.
3 4
Exercício 6. Dizer se são verdadeiras ou falsas (adote o “bom sen-
so” nos juízos):
1. Se a neve é branca, então Paris é a capital da França.
2. Se Penha é um bairro de São Paulo, então o céu não contém estrelas.
3. Se os planetas giram em torno da terra, então inexistem extra-terráqueos.
4. Se o sol é um planeta inerte, então a terra é uma estrela.
5) Bi-implicação
Dadas as proposições A e B podemos considerar a nova proposi-
ção (A ↔ B), a bi-implicação de A e B.
Postulamos que a proposição (A ↔ B) é verdadeira se e somente se
as proposições A e B possuem o mesmo valor-verdade. A proposição (A ↔
B) é falsa se e somente se as proposições A e B tiverem valores-verdade
trocados.
As considerações acima podem ser esquematizadas como se se-
gue:
Tabela-verdade da bi-implicação:
A B (A ↔ B)
1 1 1
1 0 0
0 1 0
0 0 1
Exemplo 9. Consideremos as seguintes proposições:
1) [(2 + 4 = 4) ∧ (1 ≤ 2)] Esta proposição é verdadeira
 verdadeira verdadeira
2) [(2 + 4 = 4) ∧ (1 ≥ 2)] Esta proposição é falsa
 verdadeira falsa
3) [(2 + 4 ≠ 4) ∧ (1 ≤ 2)] Esta proposição é falsa
 falsa verdadeira
4) [(2 + 4 ≠ 4) ∧ (1 ≥ 2)] Esta proposição é verdadeira
 falsa falsa
Exercício 7. Faça o que se pede.
1. Indiquemos por A ≡ “Está calor” e por B ≡ “É verão”. Escrever em forma
simbólica as seguintes afirmações:
a) É verão somente se está calor.
b) Uma condição necessária para estar calor é que seja verão.
c) Uma condição suficiente para estar calor é que seja verão.
d) Sempre que é verão, faz calor.
e) Nunca é verão, quando está calor.
3 5
2. Dentro do contexto da lógica proposicional, identifique as sentenças abai-
xo quanto a sua veracidade ou falsidade justificando devidamente cada res-
posta dada.
a) (5 + 4 = 9 ∧ 2 ≤ 4), b) (3 + 2 = 6 ∧ 2 + 2 = 4),
c) (5 + 3 = 7 ∨ 4 + 4 = 7), d) (4 + 3 = 7 ∨ 2 + 3 = 4),
e) (2 + 3 = 5 → 2 + 2 = 4), f) (3 + 3 = 5 → 32 ≤ 33),
g) (2 + 4 = 7 → 2 + 2 = 5), h) (3 + 2 = 5 → 2 + 2 = 5),
i) (6 + 2 = 8 ↔ 6 ≤ 8), j) (3 + 3 = 5 ↔ 2 + 2 = 3),
k) (2 + 2 = 3 ↔ 2 + 2 = 4), l) (3 + 4 = 6 ↔3 + 3 = 7),
m) (3 ≤ 2 → 4 ≤ 3), n) (32 ≤ 33 → 4 + 5 = 8),
o) (2 ≤ 3 → (2 + 2 = 4 ∧ 7 + 2 = 9)), l) ((3 ≤ 4 ∧ 4 ≤ 3) →3 + 3 = 7).
A seguir apresentamos algumas leituras que a negação, conjunção,
disjunção, implicação e bi-implicação podem ter na linguagem natural.
(¬A) Não A;
Não se dá que A;
Não é fato que A;
Não é verdade que A;
Não é que A;
Não se tem A.
(A ∧ B) A e B;
A, mas B;
A, embora B;
A, assim como B;
A e, além disso, B;
Tanto A como B;
A e também B;
Não só A, mas também B;
A, apesar de B.
(A ∨ B) A ou B ou ambos.
(A → B) se A, então B;
se A, isto significa que B;
tendo-se A, então B;
quando A, então B;
sempre que A, B;
B, sempre que se tenha A;
B, contanto que A;
A é condição suficiente para B;
B é condição necessária para A;
Uma condição suficiente para B é A;
Uma condição necessária para A é B;
B, se A;
3 6
B, quando A;
B, no caso de A;
A, só se B;
A, somente quando B;
A, só no caso de B;
A implica B,
A acarreta B,
B é implicada por A.
(A ↔ B) A se e só se B;
A se e somente se B;
A quando e somente quando B;
A eqüivale a B;
Uma condição necessária e suficiente
 para A é B;
A é condição necessária e suficiente
 para B
3. Escreva as sentenças a seguir em linguagem simbólica, usando sentenças
básicas (ou atômicas), isto é, as sentenças que não podem ser construídas a
partir de outras sentenças.
a) Se Antônio está feliz, a esposa do Antônio não está feliz, e se o Antônio
não está feliz, a esposa do Antônio não está feliz.
b) Ou Antônio virá à festa e Pedro não, ou Antônio não virá à festa e Pedro
se divertirá.
c) Uma condição necessária e suficiente para o rei ser feliz é ele ter vinho,
mulheres e música.
d) Teresa vai ao cinema só se o filme for uma comédia.
4. Traduza as sentenças abaixo, dado o seguinte esquema:
A ≡ Clarissa sorri
B ≡ Clarissa desperta
C ≡ Clarissa vai á praia
D ≡ Clarissa fica indecisa
E ≡ Clarissa sente o sol
a) (B → A)
b) (A → C)
c) ((D ∨ C) → (A ↔ (B ∧ (¬E))))
5. Simbolize as sentenças abaixo, dado o seguinte esquema:
A ≡ o estudante comete erros,
B ≡ há motivação para o estudo,
C ≡ o estudante aprende a matéria.
a) Se o estudante não comete erros, então ele aprende a matéria.
b) Se não há motivação para o estudo, então o estudante não aprende a
matéria.
c) Se há motivação para o estudo, o estudante não comete erros.
d) O estudante aprende a matéria se, e somente se, há motivação para o
estudo.
3 7
6. Simbolize as sentenças abaixo:
a) Ou Capitu é ou não é a criação mais notável de Machado de Assis.
b) Não é verdade que Machado de Assis escreveu ou não escreveu
poesias.
c) Se é fácil ler o que José da Silva escreveu, não é fácil ler o que escreveu
Guimarães Rosa.
7. Escreva as sentenças a seguir em linguagem simbólica, usando formas
simples, isto é, as sentenças que não podem ser construídas a partir de
outras sentenças.
a) Uma condição suficiente para x ser ímpar é x ser primo
b) Uma condição necessária para uma seqüência s convergir é que s seja
limitada.
c) O suborno será pago se, e somente se, a mercadoria for entregue.
d) Judite vencerá o torneio de xadrez, a menos que Tânia vença hoje.
e) Se x é positivo, então x2 é positivo.
8. Traduza as sentenças abaixo, dado o seguinte esquema:
A ≡ ganho um livro
B ≡ ganho uma revista
C ≡ posso ler
D ≡ estou motivado
E ≡ sou aprovado no exame.
a) (C → (A ∨ B))
b) (D → (¬C))
c) (D → ((¬C) ∧ (A ∨ B)))
d) ((¬D) → (E → (A ∨ B)))
e) ((¬D) → (C → (A ∨ B))
f) (((¬C) ∧ A) → (E → (¬D)))
9. Traduza as sentenças abaixo, dado o seguinte esquema:
A ≡ há nuvens,
B ≡ choverá,
C ≡ ventará.
D ≡ fará bom tempo amanhã.
a) (A → B)
b) (A → (¬D))
c) ((¬D) ∧ (B ∧ C))
d) ((¬A) → D)
e) (A ∧ (B ∨ C))
f) ((A ∧ B) ∨ C)
g) (A → (B ∨ C))
h) ((A → B)∨ C)
i) ((A ↔ B) ∧ ((¬C) ∧ D))
j) (A ↔((B ∧ C) ∨ D))
10. Simbolize as sentenças abaixo, dado o seguinte esquema:
A ≡ o estudante comete erros;
3 8
B ≡ há motivação para o estudo,
C ≡o estudante aprende a matéria.
a) Se não há motivação para o estudo, então o estudante comete erros ou
não aprende a matéria.
b) Se o estudante comete erros, então, se não há motivação para o estudo,
o estudante não aprende a matéria.
c) O estudante comete erros; além disso, há motivação para o estudo e o
estudante aprende a matéria.
d) Não há motivação para o estudo se e somente se o estudante comete
erros e não aprende a matéria.
e) Se há motivação para o estudo e o estudante não comete erros, então o
estudante aprende a matéria se há motivação.
11. Simbolize as sentenças abaixo, dado o seguinte esquema:
A ≡ Paulo diminui os erros cometidos,
B ≡ há motivação para o estudo,
C ≡ Paulo aprendeu a matéria,
D ≡ O professor é bom.
a) Se o professor é bom, Paulo aprende a matéria.
b) Se o professor não é bom, não há motivação para estudar.
c) O professor é bom, há motivação para estudar e, além disso, Paulo
aprende a matéria.
d) Paulo não aprendeu a matéria; ele não diminuiu os erros cometidos.
e) Se Paulo não diminuiu os erros cometidos, o professor não era bom ou
não havia motivação para estudar.
f) Paulo aprende a matéria ou diminui os erros cometidos.
g) Paulo diminui os erros cometidos se, e somente se, há motivação para
estudar.
h) Se o professor é bom, então, caso haja motivação para estudar, Paulo
aprenderá a matéria.
i) Paulo diminuirá o número de erros cometidos se, e somentese, não
ocorrer o seguinte: não deixa de haver motivação para o estudo e Paulo
não deixa de aprender a matéria.
12. Simbolize as sentenças abaixo:
a) É fácil compreender as obras de José da Silva, mas não os de Guimarães
Rosa.
b) Se Diana foi ao baile, não é fato que não tenha ido ao baile.
c) Não é fato que Paulo que vá à festa e fique satisfeito.
d) Se o computador auxilia o cientista se, e somente se, altera a sua
programação, então, se altera a programação, é útil.
e) Não se dá o seguinte: não viajamos e não levamos as barracas.
f) Irei á praia salvo se chover.
g) Vou estudar exceto se tiver vontade.
13. Dadas as sentenças atômicas abaixo, escrever por meio de símbolos:
A ≡ “Ela é bonita”
B ≡ “Ela é inteligente”
C ≡ “Ela é rica”
3 9
D ≡ “Ela é jovem”
E ≡ “Ela gosta de mim”
F ≡ “Quero casar com ela”
a) “Ela é pobre”
b) “Ela é rica ou jovem”
c) “Ela é inteligente e anciã”
d) “Não é que ela é burra”
e) “Se ela é rica, então quero casar com ela”
f) “Ela é inteligente, bonita, rica, jovem e ela gosta de mim”
g) “Quero casar com ela, mas ela não gosta de mim”
h) “Uma condição necessária para casar com ela é que ela seja bonita”
i) “Uma condição suficiente para casar com ela é que ela seja rica”
j) “Ela é feia, burra, pobre, anciã, mas quero casar com ela”
k) “Quero casar com ela só se ela gosta de mim”
l) “Se ela é jovem então ela é bonita”
m) “Uma condição necessária e suficiente para casar com ela é que ela
goste de mim”
n) “Quero casar com ela, exceto se ela é burra”
2.6 - Fórmulas atômicas e fórmulas
Como observamos no início deste capítulo, através dos conectivos
lógicos ¬ , ∧, ∨, → e ↔, podemos construir sentenças mais “complexas” a
partir de outras sentenças mais “simples”. Este procedimento é clarificado
pela seguinte regra de formação de sentenças:
Partimos de certas sentenças denominadas fórmulas atômicas1 : p,
q, r, ... Elas desempenham, intuitivamente, o papel de sentenças básicas ou
atômicas da linguagem proposicional.
As sentenças (que daqui em diante receberão o nome de ‘fórmulas’)
em geral são obtidas pela seguinte definição indutiva generalizada:
1. Todas as fórmulas atômicas são fórmulas.
2. Se A e B são fórmulas, então
(¬A),
(A ∧ B),
(A ∨ B),
(A → B) e
(A ↔ B)
são também fórmulas.
3. Uma dada expressão constitui uma fórmula se e somente se foi obtida pela
aplicação de uma das regras (1 ou 2) acima.
Observe-se que os símbolos A e B introduzidos na definição anterior
(item 2) se tratam de variáveis que denotam sentenças quaisquer da linguagem
proposicional. O leitor deve estar atento para o fato de que tais símbolos não
são propriamente símbolos da linguagem em apreço, mas sim símbolos que
estão “fora” da linguagem proposicional. Tais variáveis denominam-se,
costumeiramente, meta-variáveis.
4 0
A cláusula 3 da definição acima é também conhecida como cláusula
maximal e, juntamente com as demais, permite-nos reconhecer quando uma
dada expressão se trata de uma fórmula ou não.
Daqui em diante, usamos também a seguinte terminologia: diz-se
que uma fórmula
(¬A) é do tipo não.
(A ∧ B) é do tipo e
(A ∨ B) é do tipo ou
(A → B) é do tipo implica
(A ↔ B) é do tipo bi-implica.
2.7 - Árvore de composição de uma fórmula. Árvore de decomposição.
Vimos a definição de fórmula no parágrafo anterior. Podemos esquematizá-
la no que chamamos árvore de formação de fórmulas: A, B, C, D indicam
fórmulas atômicas.
A B C D ...
(¬A) (A → B) (B ∧ C) (C ∨ D) (D ↔ D)
(¬(¬A)) ((A ∧ (B ∧ C)) ((C ∨ D) → (B ∧ C)) (¬(D ↔ D))
1 No sentido de sentença indecomponível.
Na árvore acima notamos alguns pontos importantes.
Inicialmente, observemos a 1a linha: partimos de sentenças atômicas
A, B, C, D, ... que constitui a regra 1 da definição de fórmula.
Observemos a 2a linha: aplicamos a regra 2 e obtemos novas fórmu-
las: (¬A), (A → B), (B ∧ C), (C ∨ D), (D ↔ D), dentre outras. Observe que as
fórmulas obtidas seguem estritamente a regra 2, ou seja, por exemplo, em (A
→ B), é absolutamente necessário abrir um parêntesis á esquerda, escrever
a atômica A, escrever o conectivo → e depois escrever a atômica B e
finalmente fechar o parêntesis á esquerda.
Observemos a 3a linha: aplicamos a regra 2 novamente e obtemos
novas fórmulas: (¬(¬A)), ((A ∧ (B ∧ C)), ((C ∨ D) → (B ∧ C)), (¬(D ↔ D)),
entre outros. Novamente atente para a regra 2 que foi aplicada cuidadosa-
mente ás fórmulas anteriormente obtidas.
Finalmente, queremos observar ao leitor que é muito importante
então aplicar corretamente a regra de formação de fórmulas.
A verificação cuidadosa da formação de fórmulas, permite também
imediatamente analisar como uma fórmula foi obtida. Esta tarefa é de
fundamental importância para as discussões deste livro. A seguir, prepare-
○
○
○
○
○
○
○
○
○
○
○
○
○
○
○
○
○
○
○
○
○
○
○
○
○
4 1
mos alguns conceitos para o enquadramento desta noção.
Vamos exibir um processo gráfico para determinar todas as
subfórmulas (i.e., intuitivamente, todas as fórmulas que compõe a fórmula
em questão) de uma dada fórmula. Tal processo faz uso de uma estrutura,
muito utilizada nas diversas áreas das ciências da computação, chamada
árvore, mais precisamente faremos uso somente de árvores binárias. A
seguir, apresentamos graficamente as componentes de uma árvore binária
qualquer, observamos que tal descrição, não tem nenhum caráter formal, é
apenas para nos familiarizarmos com os elementos dessa estrutura.
Acima está a representação gráfica de uma árvore binária genérica,
chamamos de aresta o segmento de reta que “liga” os nós, (ou vértices ). Os
nós ou vértices são de três espécies, o nó a partir da qual toda a árvore é
gerada é chamado de raiz, o nó terminal chamado de folha e os nós interme-
diários chamados de nó interior. Freqüentemente utilizaremos as seguintes
denominações para determinados nós de uma árvore binária nó pai, nó
filho, nó irmão. Tal denominação pode ser vista no diagrama abaixo, referen-
te a árvore anteriormente citada.
4 2
Observações:
 1. Chamamos a estrutura acima de árvore binária, pois cada nó pode ter zero,
um ou no máximo dois filhos.
 2. Podemos também classificar os nós como sucessores e ancestrais, por
exemplo:
Utilizaremos essa estrutura de árvore binária do seguinte modo:
1. Dada uma fórmula qualquer S esta será a raiz da árvore de subfórmulas
de S,
2. Se S é uma fórmula do tipo não, então ela é composta por uma fórmula A,
de tal modo que S = (¬A), logo teremos (¬A)
 A
3. Se S é uma fórmula do tipo e, então ela é composta por duas fórmulas A e
B de tal modo que S = (A ∧ B), logo teremos (A ∧ B).
 A B
4. Se S é uma fórmula do tipo ou, então ela é composta por duas fórmulas A
e B de tal modo que S = (A ∨ B), daí teremos (A ∨ B)
 A B
5. Se S é uma fórmula do tipo implica, então ela é composta por duas fórmu-
las A e B de tal modo que S é dado por (A → B), e teremos (A → B)
 A B
6. Se S é uma fórmula do tipo bi-implica, então ela é composta por duas
fórmulas A e B de tal modo que S é dado por (A ↔ B), e teremos
4 3
 (A ↔ B)
 A B
Cada nó representa uma fórmula, em particular, cada nó “gera” uma
sub-árvore, isto é, cada nó pode ser considerada uma raiz de uma árvore
“menor” que tem como nós os sucessores do respectivo nó raiz.
A construção de uma árvore de subfórmulas a partir de uma fórmu-
la dada, termina quando todas as folhas contiverem somente letras
proposicionais.
É muito importante o leitor ter em mente que uma fórmula é definida
passo a passo e é única a sua construção. Assim, por exemplo, podemos
dizer qual conectivo foi aplicado inicialmente, o segundo, etc., até chegar-
mos ao último. Desse modo, é possível decompor uma fórmula exibindo
todas as suas fórmulas que o compõe. Como

Outros materiais