Baixe o app para aproveitar ainda mais
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......................................................................................1803.25– SLD-derivação.................................................................................182 3.26– SLD-refutação.................................................................................183 3.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 curiosidadeque 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 únicoacesso 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 classificadas nas 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 finito de 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 Teoria dos 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 se dá 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 somente se, 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
Compartilhar