UNIDADE I

SUMRIO

PREFCIO02

UNIDADE I03

CAPTULO I A Lgica e o cotidiano03

O TRUQUE DAS CARTAS03

O PROBLEMA DO LEITE03

O PARADOXO DO QUEIJO03

A LGICA DO DIA-A-DIA04

CAPTULO II A Lgica e sua histria05

A RAZO E A LGICA05

A LGICA12

A LGICA MATEMTICA13

A HISTRIA DA LGICA13

SITEOGRAFIA16

UNIDADE II17

CAPTULO I Noes de Lgica Matemtica17

CLCULO PROPOSICIONAL17

A LGEBRA DOS CONJUNTOS 20

TAUTOLOGIA E CONTRA -TAUTOLOGIA24

CAPTULO II A Falcia54

DEFINIO54

CAPTULO III A Lgica Fuzzy57

HISTRICO57

INTRODUO58

TEORIA DOS CONJUNTOS TRADICIONAIS59

TEORIA DOS CONJUNTOS FUZZY62

LGICA FUZZY64

PROPOSIES FUZZY64

SITEOGRAFIA69

Prefcio

Se... ento..., Se e somente se, portanto, logo, caso contrrio, segue-se que...

So alguns dos termos que comea a fazer parte do dia a dia do estudante de nvel superior quando inicia sua graduao em matemtica.

Na sua grande maioria, na qual eu mesmo me incluo, estes termos no so claramente explicados pelos professores e quase somos forados a engoli-los, aceit-los e qui compreende-los. O prprio professor mais vtima que algoz, pois tambm foi obrigado a digeri-los sob a presso tcita de que se no conseguisse teria claramente errado de rea.Este curso tem como objetivo principal proporcionar, a todos aqueles que esto em contato com a matemtica, a percepo e aprofundamento na sua base lgico-racional. Podendo ento estruturar-se em compreenso mais apurada do passo a passo que constitui a linguagem desta bela cincia.

Veremos tambm que a lgica est no nosso dia-a-dia, em nossa linguagem, na forma de compreendermos o mundo que nos cerca e que o seu estudo nos trar benefcios como, por exemplo a organizao de nossas vidas.

Bem-vindos ao mundo do verdadeiro ou falso ou ser que existe uma outra possibilidade?

Prof. Henrique ReffertUNIDADE I

Captulo 1 A Lgica e o cotidianoIntroduo

O truque das cartas

Escolher dentre seis cartas que aparecem no vdeo apenas uma. Observe que ela vai ser retirada sem que de antemo se saiba qual foi a que voc escolheu. Qual a lgica por detrs do truque?Problema do leiteO Sr. Arquiticlnio leiteiro tinha oito litros de leite e precisava repartir metade para o Sr. Agronopolos e metade para a D. Bereniatriz. Mas ele s dispunha de 3 vasilhas, uma de oito litros, onde estava o leite, e outras duas vazias, uma de cinco e outra de trs litros. Usando somente essas vasilhas, como ele poder fazer a separao desse leite para os seus fregueses?O Paradoxo do queijo

Vamos mostrar o fato de que para queijos com furos quanto mais queijo tivermos, menos queijo teremos.

A Lgica do dia-a-dia Algoritimizando a vida. muito comum escutarmos no nosso dia-a-dia que determinado fato lgico ou que algo no faz sentido, por exemplo:Esperar para atravessar uma avenida muito movimentada quando o sinal fica vermelho para os carros algo muito lgico, mas ver uma galinha esperar para atravessar a mesma via aps o sinal ficar vermelho algo inesperado.

A lgica est associada ao senso comum, necessidade de poder controlar situaes, compreender um fato, saber como atuar para esperar determinado resultado, enfim, a lgica est o tempo todo em nosso cotidiano.

Voltemos mais uma vez situao de atravessar uma via. Podemos querer convencer uma criana de que se deve aguardar o sinal ficar vermelho para os carros, para que se possa atravessar a mesma. Siga o dilogo abaixo:

Pai, por que ns no podemos atravessar a rua mesmo no sinal verde.

Teobaldozinho, se atravessarmos quando ele estiver verde, ento a probabilidade de sermos atropelados maior.

Nesta conversa, observamos um caso tpico de raciocnio lgico com uma sentena do tipo se..., ento...

Aprofundando um pouco mais a situao de atravessarmos uma rua poderemos at algoritimizar o processo.(Construir com os estudantes o algortimo de atravessar uma rua)

DINMICA

Formar vrias equipes e escolher uma situao para cada equipe para ser algoritimizada.Captulo 2 A Lgica e sua histria A Razo e a LgicaOs vrios sentidos da palavra razoEm nossa vida cotidiana usamos a palavra razo em muitos sentidos. Dizemos, por exemplo, eu estou com a razo, ou ele no tem razo, para significar que nos sentimos seguros de alguma coisa ou que sabemos com certeza alguma coisa. Tambm dizemos que, num momento de fria ou de desespero, algum perde a razo, como se a razo fosse alguma coisa que se pode ter ou no ter, possuir e perder, ou recuperar, como na frase: Agora ela est lcida, recuperou a razo.

Falamos tambm frases como: Se voc me disser suas razes, sou capaz de fazer o que voc me pede, querendo dizer com isso que queremos ouvir os motivos que algum tem para querer ou fazer alguma coisa. Fazemos perguntas como: Qual a razo disso?, querendo saber qual a causa de alguma coisa e, nesse caso, a razo parece ser alguma propriedade que as prprias coisas teriam, j que teriam uma causa.

Assim, usamos razo para nos referirmos a motivos de algum, e tambm para nos referirmos a causas de alguma coisa, de modo que tanto ns quanto as coisas parecemos dotados de razo, mas em sentido diferente.

Esses poucos exemplos j nos mostram quantos sentidos diferentes a palavra razo possui: certeza, lucidez, motivo, causa. E todos esses sentidos encontram-se presentes na Filosofia.

Por identificar razo e certeza, a Filosofia afirma que a verdade racional; por identificar razo e lucidez (no ficar ou no estar louco), a Filosofia chama nossa razo de luz e luz natural; por identificar razo e motivo, por considerar que sempre agimos e falamos movidos por motivos, a Filosofia afirma que somos seres racionais e que nossa vontade racional; por identificar razo e causa e por julgar que a realidade opera de acordo com relaes causais, a Filosofia afirma que a realidade racional.

muito conhecida a clebre frase de Pascal, filsofo francs do sculo XVII: O corao tem razes que a razo desconhece. Nessa frase, as palavras razes e razo no tm o mesmo significado, indicando coisas diversas. Razes so os motivos do corao, enquanto razo algo diferente de corao; este o nome que damos para as emoes e paixes, enquanto razo o nome que damos conscincia intelectual e moral.

Ao dizer que o corao tem suas prprias razes, Pascal est afirmando que as emoes, os sentimentos ou as paixes so causas de muito do que fazemos, dizemos, queremos e pensamos. Ao dizer que a razo desconhece as razes do corao, Pascal est afirmando que a conscincia intelectual e moral diferente das paixes e dos sentimentos e que ela capaz de uma atividade prpria no motivada e causada pelas emoes, mas possuindo seus motivos ou suas prprias razes.

Assim, a frase de Pascal pode ser traduzida da seguinte maneira: Nossa vida emocional possui causas e motivos (as razes do corao), que so as paixes ou os sentimentos, e diferente de nossa atividade consciente, seja como atividade intelectual, seja como atividade moral.

A conscincia a razo. Corao e razo, paixo e conscincia intelectual ou moral so diferentes. Se algum perde a razo porque est sendo arrastado pelas razes do corao. Se algum recupera a razo porque o conhecimento intelectual e a conscincia moral se tornaram mais fortes do que as paixes. A razo, enquanto conscincia moral, a vontade racional livre que no se deixa dominar pelos impulsos passionais, mas realiza as aes morais como atos de virtude e de dever, ditados pela inteligncia ou pelo intelecto.

Alm da frase de Pascal, tambm ouvimos outras que elogiam as cincias, dizendo que elas manifestam o progresso da razo. Aqui, a razo colocada como capacidade puramente intelectual para conseguir o conhecimento verdadeiro da Natureza, da sociedade, da Histria e isto considerado algo bom, positivo, um progresso.

Por ser considerado um progresso, o conhecimento cientfico visto como se realizando no tempo e como dotado de continuidade, de tal modo que a razo concebida como temporal tambm, isto , como capaz de aumentar seus contedos e suas capacidades atravs dos tempos.

Algumas vezes ouvimos um professor dizer a outro: Fulano trouxe um trabalho irracional; era um caos, uma confuso. Incompreensvel. J o trabalho de beltrano era uma beleza: claro, compreensvel, racional. Aqui, a razo, ou racional, significa clareza das idias, ordem, resultado de esforo intelectual ou da inteligncia, seguindo normas e regras de pensamento e de linguagem.

Todos esses sentidos constituem a nossa idia de razo. Ns a consideramos a conscincia moral que observa as paixes, orienta a vontade e oferece finalidades ticas para a ao. Ns a vemos como atividade intelectual de conhecimento da realidade natural, social, psicolgica, histrica. Ns a concebemos segundo o ideal da clareza, da ordenao e do rigor e preciso dos pensamentos e das palavras.

Para muitos filsofos, porm, a razo no apenas a capacidade moral e intelectual dos seres humanos, mas tambm uma propriedade ou qualidade primordial das prprias coisas, existindo na prpria realidade. Para esses filsofos, nossa razo pode conhecer a realidade (Natureza, sociedade, Histria) porque ela racional em si mesma.

Fala-se, portanto, em razo objetiva (a realidade racional em si mesma) e em razo subjetiva (a razo uma capacidade intelectual e moral dos seres humanos). A razo objetiva a afirmao de que o objeto do conhecimento ou a realidade racional; a razo subjetiva a afirmao de que o sujeito do conhecimento e da ao racional. Para muitos filsofos, a Filosofia o momento do encontro, do acordo e da harmonia entre as duas razes ou racionalidades.Origem da palavra razo

Na cultura da chamada sociedade ocidental, a palavra razo origina-se de duas fontes: a palavra latina ratio e a palavra grega logos. Essas duas palavras so substantivos derivados de dois verbos que tm um sentido muito parecido em latim e em grego.

Logos vem do verbo legein, que quer dizer: contar, reunir, juntar, calcular. Ratio vem do verbo reor, que quer dizer: contar, reunir, medir, juntar, separar, calcular.

Que fazemos quando medimos, juntamos, separamos, contamos e calculamos? Pensamos de modo ordenado. E de que meios usamos para essas aes? Usamos palavras (mesmo quando usamos nmeros estamos usando palavras, sobretudo os gregos e os romanos, que usavam letras para indicar nmeros).

Por isso, logos, ratio ou razo significam pensar e falar ordenadamente, com medida e proporo, com clareza e de modo compreensvel para outros. Assim, na origem, razo a capacidade intelectual para pensar e exprimir-se correta e claramente, para pensar e dizer as coisas tais como so. A razo uma maneira de organizar a realidade pela qual esta se torna compreensvel. , tambm, a confiana de que podemos ordenar e organizar as coisas porque so organizveis, ordenveis, compreensveis nelas mesmas e por elas mesmas, isto , as prprias coisas so racionais.

Desde o comeo da Filosofia, a origem da palavra razo fez com que ela fosse considerada oposta a quatro outras atitudes mentais:

1. ao conhecimento ilusrio, isto , ao conhecimento da mera aparncia das coisas que no alcana a realidade ou a verdade delas; para a razo, a iluso provm de nossos costumes, de nossos preconceitos, da aceitao imediata das coisas tais como aparecem e tais como parecem ser. As iluses criam as opinies que variam de pessoa para pessoa e de sociedade para sociedade. A razo se ope mera opinio;

2. s emoes, aos sentimentos, s paixes, que so cegas, caticas, desordenadas, contrrias umas s outras, ora dizendo sim a alguma coisa, ora dizendo no a essa mesma coisa, como se no soubssemos o que queremos e o que as coisas so. A razo vista como atividade ou ao (intelectual e da vontade) oposta paixo ou passividade emocional;

3. crena religiosa, pois, nesta, a verdade nos dada pela f numa revelao divina, no dependendo do trabalho de conhecimento realizado pela nossa inteligncia ou pelo nosso intelecto. A razo oposta revelao e por isso os filsofos cristos distinguem a luz natural - a razo - da luz sobrenatural - a revelao;

4. ao xtase mstico, no qual o esprito mergulha nas profundezas do divino e participa dele, sem qualquer interveno do intelecto ou da inteligncia, nem da vontade. Pelo contrrio, o xtase mstico exige um estado de abandono, de rompimento com a atividade intelectual e com a vontade, um rompimento com o estado consciente, para entregar-se fruio do abismo infinito. A razo ou conscincia se ope inconscincia do xtase.Os princpios racionais

Desde seus comeos, a Filosofia considerou que a razo opera seguindo certos princpios que ela prpria estabelece e que esto em concordncia com a prpria realidade, mesmo quando os empregamos sem conhec-los explicitamente. Ou seja, o conhecimento racional obedece a certas regras ou leis fundamentais, que respeitamos at mesmo quando no conhecemos diretamente quais so e o que so. Ns as respeitamos porque somos seres racionais e porque so princpios que garantem que a realidade racional.

Que princpios so esses? So eles:

Princpio da identidade, cujo enunciado pode parecer surpreendente: A A ou O que , . O princpio da identidade a condio do pensamento e sem ele no podemos pensar. Ele afirma que uma coisa, seja ela qual for (um ser da Natureza, uma figura geomtrica, um ser humano, uma obra de arte, uma ao), s pode ser conhecida e pensada se for percebida e conservada com sua identidade.

Por exemplo, depois que um matemtico definir o tringulo como figura de trs lados e de trs ngulos, no s nenhuma outra figura que no tenha esse nmero de lados e de ngulos poder ser chamada de tringulo como tambm todos os teoremas e problemas que o matemtico demonstrar sobre o tringulo, s podero ser demonstrados se, a cada vez que ele disser tringulo, soubermos a qual ser ou a qual coisa ele est se referindo. O princpio da identidade a condio para que definamos as coisas e possamos conhec-las a partir de suas definies.

Princpio da no-contradio (tambm conhecido como princpio da contradio), cujo enunciado : A A e impossvel que seja, ao mesmo tempo e na mesma relao, no-A. Assim, impossvel que a rvore que est diante de mim seja e no seja uma mangueira; que o cachorrinho de dona Filomena seja e no seja branco; que o tringulo tenha e no tenha trs lados e trs ngulos; que o homem seja e no seja mortal; que o vermelho seja e no seja vermelho, etc.

Sem o princpio da no-contradio, o princpio da identidade no poderia funcionar. O princpio da no-contradio afirma que uma coisa ou uma idia que se negam a si mesmas se autodestroem, desaparecem, deixam de existir. Afirma, tambm, que as coisas e as idias contraditrias so impensveis e impossveis.

Princpio do terceiro-excludo, cujo enunciado : Ou A x ou y e no h terceira possibilidade. Por exemplo: Ou este homem Scrates ou no Scrates; Ou faremos a guerra ou faremos a paz. Este princpio define a deciso de um dilema - ou isto ou aquilo - e exige que apenas uma das alternativas seja verdadeira. Mesmo quando temos, por exemplo, um teste de mltipla escolha, escolhemos na verdade apenas entre duas opes - ou est certo ou est errado - e no h terceira possibilidade ou terceira alternativa, pois, entre vrias escolhas possveis, s h realmente duas, a certa ou a errada.

Princpio da razo suficiente, que afirma que tudo o que existe e tudo o que acontece tem uma razo (causa ou motivo) para existir ou para acontecer, e que tal razo (causa ou motivo) pode ser conhecida pela nossa razo. O princpio da razo suficiente costuma ser chamado de princpio da causalidade para indicar que a razo afirma a existncia de relaes ou conexes internas entre as coisas, entre fatos, ou entre aes e acontecimentos.Pode ser enunciado da seguinte maneira: Dado A, necessariamente se dar B. E tambm: Dado B, necessariamente houve A.

Isso no significa que a razo no admita o acaso ou aes e fatos acidentais, mas sim que ela procura, mesmo para o acaso e para o acidente, uma causa. A diferena entre a causa, ou razo suficiente, e a causa casual ou acidental est em que a primeira se realiza sempre, universal e necessria, enquanto a causa acidental ou casual s vale para aquele caso particular, para aquela situao especfica, no podendo ser generalizada e ser considerada vlida para todos os casos ou situaes iguais ou semelhantes, pois, justamente, o caso ou a situao so nicos.

A morte, por exemplo, um efeito necessrio e universal (vlido para todos os tempos e lugares) da guerra e a guerra a causa necessria e universal da morte de pessoas. Mas imprevisvel ou acidental que esta ou aquela guerra aconteam. Podem ou no podem acontecer. Nenhuma causa universal exige que aconteam. Mas, se uma guerra acontecer, ter necessariamente como efeito mortes. Mas as causas dessa guerra so somente as dessa guerra e de nenhuma outra.

Diferentemente desse caso, o princpio da razo suficiente est vigorando plenamente quando, por exemplo, Galileu demonstrou as leis universais do movimento dos corpos em queda livre, isto , no vcuo.

Pelo que foi exposto, podemos observar que os princpios da razo apresentam algumas caractersticas importantes:

no possuem um contedo determinado, pois so formas: indicam como as coisas devem ser e como devemos pensar, mas no nos dizem quais coisas so, nem quais os contedos que devemos ou vamos pensar;

possuem validade universal, isto , onde houver razo (nos seres humanos e nas coisas, nos fatos e nos acontecimentos), em todo o tempo e em todo lugar, tais princpios so verdadeiros e empregados por todos (os humanos) e obedecidos por todos (coisas, fatos, acontecimentos);

so necessrios, isto , indispensveis para o pensamento e para a vontade, indispensveis para as coisas, os fatos e os acontecimentos. Indicam que algo assim e no pode ser de outra maneira. Necessrio significa: impossvel que no seja dessa maneira e que pudesse ser de outra.Ampliando nossa idia de razo

A idia de razo que apresentamos at aqui e que constitui o ideal de racionalidade criado pela sociedade europia ocidental sofreu alguns abalos profundos desde o incio do sculo XX.

Aqui, vamos apenas oferecer alguns exemplos dos problemas que a Filosofia precisou enfrentar e que levaram a uma ampliao da idia da razo.

Um primeiro abalo veio das cincias da Natureza ou, mais precisamente, da fsica e atingiu o princpio do terceiro-excludo. A fsica da luz (ou ptica) descobriu que a luz tanto pode ser explicada por ondas luminosas quanto por partculas descontnuas. Isso significou que j no se podia dizer: ou a luz se propaga por ondas contnuas ou se propaga por partculas descontnuas, como exigiria o princpio do terceiro-excludo, mas sim que a luz pode propagar-se tanto de uma maneira como de outra.

Por sua vez, a fsica atmica ou quntica abalou o princpio da razo suficiente. Vimos que esse princpio afirma que, conhecido A, posso determinar como dele necessariamente resultar B, ou, conhecido B, posso determinar necessariamente como era A que o causou. Em outras palavras, conhecido o estado E de um fenmeno, posso deduzir como ser o estado E2 ou E3 e vice-versa: conhecidos E3 e E2 posso dizer como era o estado E. Ora, a fsica dos tomos revelou que isso no possvel, que no podemos saber as razes pelas quais os tomos se movimentam, nem sua velocidade e direo, nem os efeitos que produziro.

Esses dois problemas levaram a introduzir um novo princpio racional na Natureza: o princpio da indeterminao. Assim, o princpio da razo suficiente vlido para os fenmenos macroscpicos, enquanto o princpio da indeterminao vlido para os fenmenos em escala hipermicroscpica.

Um outro problema veio abalar o princpio da identidade e da no-contradio. A fsica sempre considerou que a Natureza obedece s leis universais da razo objetiva sem depender da razo subjetiva. Em outras palavras, as leis da Natureza existem por si mesmas, so necessrias e universais por si mesmas e no dependem do sujeito do conhecimento.

Contudo, a teoria da relatividade mostrou que as leis da Natureza dependem da posio ocupada pelo observador, isto , pelo sujeito do conhecimento e, portanto, para um observador situado fora de nosso sistema planetrio, a Natureza poder seguir leis completamente diferentes, de tal modo que, por exemplo, o que o espao e o tempo para ns poder no ser para outros seres (se existirem) da galxia; a geometria que seguimos pode no ser a que tenha sentido noutro sistema planetrio; o que pode ser contraditrio para ns poder no ser para habitantes de outra galxia e assim por diante.

Um outro problema, tambm atingindo os princpios da razo, foi trazido pela lgica. O lgico alemo Frege apresentou o seguinte problema: quando digo a estrela da manh a estrela da tarde estou caindo em contradio e perdendo o princpio da identidade. No entanto, estrela da manh o planeta Vnus e estrela da tarde tambm o planeta Vnus; dessa perspectiva, no h contradio alguma no que digo. preciso, ento, distinguir em nosso pensamento e em nossa linguagem trs nveis: o objeto a que ns nos referimos, os enunciados que empregamos e o sentido desses enunciados em sua relao com o objeto referido. Somente dessa maneira podemos manter a racionalidade dos princpios da identidade, da no-contradio e do terceiro-excludo.

Enfim, um outro tipo de problema foi trazido com o desenvolvimento dos estudos da antropologia, que mostraram como outras culturas podem oferecer uma concepo muito diferente da que estamos acostumados sobre o pensamento e a realidade. Isso no significa, como imaginaram durante sculos os colonizadores, que tais culturas ou sociedades sejam irracionais ou pr-racionais, e sim que possuem uma outra idia do conhecimento e outros critrios para a explicao da realidade.

Como a palavra razo europia e ocidental, parece difcil falarmos numa outra razo, que seria prpria de outros povos e culturas. No entanto, o que os estudos antropolgicos mostraram que precisamos reconhecer a nossa razo e a razo deles, que se trata de uma outra razo e no da mesma razo em diferentes graus de uma nica evoluo.

Indeterminao da Natureza, pluralidade de enunciados para um mesmo objeto, pluralidade e diferenciao das culturas foram alguns dos problemas que abalaram a razo, no sculo XX. A esse abalo devemos acrescentar dois outros. O primeiro deles foi trazido por um no-filsofo, Marx, quando introduziu a noo de ideologia; o segundo tambm foi trazido por um no-filsofo, Freud, quando introduziu o conceito de inconsciente.

A noo de ideologia veio mostrar que as teorias e os sistemas filosficos ou cientficos, aparentemente rigorosos e verdadeiros, escondiam a realidade social, econmica e poltica, e que a razo, em lugar de ser a busca e o conhecimento da verdade, poderia ser um poderoso instrumento de dissimulao da realidade, a servio da explorao e da dominao dos homens sobre seus semelhantes. A razo seria um instrumento da falsificao da realidade e de produo de iluses pelas quais uma parte do gnero humano se deixa oprimir pela outra.

A noo de inconsciente, por sua vez, revelou que a razo muito menos poderosa do que a Filosofia imaginava, pois nossa conscincia , em grande parte, dirigida e controlada por foras profundas e desconhecidas que permanecem inconscientes e jamais se tornaro plenamente conscientes e racionais. A razo e a loucura fazem parte de nossa estrutura mental e de nossas vidas e, muitas vezes, como por exemplo no fenmeno do nazismo, a razo louca e destrutiva.

Fatos como esses - as descobertas na fsica, na lgica, na antropologia, na histria, na psicanlise - levaram o filsofo francs Merleau-Ponty a dizer que uma das tarefas mais importantes da Filosofia contempornea deveria ser a de encontrar uma nova idia da razo, uma razo alargada, na qual pudessem entrar os princpios da racionalidade definidos por outras culturas e encontrados pelas descobertas cientficas.

Esse alargamento duplamente necessrio e importante. Em primeiro lugar, porque ele exprime a luta contra o colonialismo e contra o etnocentrismo - isto , contra a viso de que a nossa razo e a nossa cultura so superiores e melhores do que as dos outros povos. Em segundo lugar, porque a razo estaria destinada ao fracasso se no fosse capaz de oferecer para si mesma novos princpios exigidos pelo seu prprio trabalho racional de conhecimento.

A LgicaA Lgica uma cincia de ndole matemtica e fortemente ligada Filosofia. J que o pensamento a manifestao do conhecimento, e que o conhecimento busca a verdade, preciso estabelecer algumas regras para que essa meta possa ser atingida. Assim, a lgica o ramo da filosofia que cuida das regras do bem pensar, ou do pensar correto, sendo, portanto, um instrumento do pensar. A aprendizagem da lgica no constitui um fim em si. Ela s tem sentido enquanto meio de garantir que nosso pensamento proceda corretamente a fim de chegar a conhecimentos verdadeiros. Podemos, ento, dizer que a lgica trata dos argumentos, isto , das concluses a que chegamos atravs da apresentao de evidncias que a sustentam. O principal organizador da lgica clssica foi Aristteles, com sua obra chamada rganon. Ele divide a lgica em formal e material.

Um sistema lgico um conjunto de axiomas e regras de inferncia que visam representar formalmente o raciocnio vlido . Diferentes sistemas de lgica formal foram construdos ao longo do tempo quer no mbito estrito da Lgica Terica, quer em aplicaes prticas na computao e em Inteligncia artificial.

Tradicionalmente, lgica tambm a designao para o estudo de sistemas prescritivos de raciocnio, ou seja, sistemas que definem como se "deveria" realmente pensar para no errar, usando a razo, dedutivamente e indutivamente. A forma como as pessoas realmente raciocinam estudado noutras reas, como na psicologia cognitiva.

Como cincia, a lgica define a estrutura de declarao e argumento e elabora frmulas atravs das quais estes podem ser codificados. Implcita no estudo da lgica est a compreenso do que gera um bom argumento e de quais os argumentos que so falaciosos.

A lgica filosfica lida com descries formais da linguagem natural. A maior parte dos filsofos assumem que a maior parte do raciocnio "normal" pode ser capturada pela lgica, desde que se seja capaz de encontrar o mtodo certo para traduzir a linguagem corrente para essa lgica.

A Lgica matemtica

Lgica Matemtica o uso da lgica formal para estudar o raciocnio matemtico-- ou, como prope Alonzo Church (*Introduction to Mathematical Logic* (Princeton, New Jersey:Princeton University Press,1956; dcima edio, 1996),'lgica tratada pelo mtodo matemtico'. No incio do sculo XX, lgicos e filsofos tentaram provar que a matemtica, ou parte da matemtica, poderia ser reduzida lgica.(Gottlob Frege, p.ex., tentou reduzir a aritmtica lgica; Bertrand Russell e A. N. Whitehead, tentaram reduzir toda a matemtica ento conhecida lgica -- a chamada 'lgica de segunda ordem'.) Uma das suas doutrinas lgico-semnticas era que a descoberta da forma lgica de uma frase, na verdade, revela a forma adequada de diz-la, ou revela alguma essncia previamente escondida. H um certo consenso que a reduo falhou -- ou que precisaria de ajustes --, assim como h um certo consenso que a lgica -- ou alguma lgica -- uma maneira precisa de representar o raciocnio matemtico. Cincia que tem por objeto o estudo dos mtodos e princpios que permitem distinguir raciocnios vlidos de outros no vlidos;

A Histria da lgica

A histria da lgica documenta o desenvolvimento desta em vrias culturas e tradies. Enquanto muitas culturas tenham usado complicados sistemas de raciocnio, somente na China, ndia e Grcia os mtodos de raciocnio tiveram um desenvolvimento sustentvel. Embora as datas sejam incertas, especialmente no caso da ndia, possvel que a lgica emergiu nos trs pases por volta do sculo 4 a.C. A lgica moderna (ver lgica) descende da tradio grega, mas tambm h influncias de filsofos islmicos e de lgicos europeus da era medieval que tiveram contato com a lgica aristotlica.

Lgica na China

Mozi, Mster Mo, um contemporneo de Confcio, creditado como o fundador da escola Mohista, cujo os ensinamentos lidavam com os problemas relacionados com a inferncia e com as condies das concluses corretas. Em particular, uma das escolas que cresceu alm do Mohismo, os the Logicians?, so creditados por alguns estudiosos como sendo umas das primeiras escolas a investigar a lgica formal. Infelizmente, por causa da violncia e da leis da dinastia Qin, essa linha de investigao desapareceu da China at a introduo da filosofia indiana pelos BudistasLgica na ndia

Os Nyaya Sutras do Akasapada Gautama so os centros da escola da Nyaya, uma das seis escolas ortodoxas da filosofia Hindu. Esta escola criou um rgido esquema de cinco membros de inferncia envolvendo uma premissa inicial: uma razo, um exemplo, uma aplicao e uma concluso. A filosofia idealista Budista foi a maior oponente dos Nayaykas. Nagarjuna, o fundador da Madhyamika caminho do meio desenvolveu uma anlise conhecida como catuskoti ou tetralema. Mas foi com Dgnaga e o seu sucessor Dharmakirti que a lgica budista atingiu seu pice. A base da analise deles a definio da necessidade de uma deduo lgica, vyapti, tambm conhecida como concomitncia ou pervasion?. Para esse fim uma doutrina chamada apoha ou diferenciao foi desenvolvido. As dificuldades envolvidas neste sistema, em parte, estimulou a escola dos neo-escolsticos de Navya-Nyaya, que introduziu a anlise formal da inferncia no sculo XVI.

Lgica na Grcia

Na Grcia, duas importantes tradies emergiram. A Lgica estica com as suas razes em Euclides de Megara, um pupilo de Scrates, e baseada na lgica proposicional que talvez foi a mas prxima da lgica moderna. Entretanto, a tradio que sobreviveu para mas tarde influenciar outras culturas foi a lgica aristotlica, o primeiro tratado grego sobre a sistematizao da lgica. Na inspeo de Aristteles sobre os silogismo h quem diga que existe uma interessante comparao com o esquema de inferncia dos indianos e com a menos rgida discurso chinesa.

Atravs do latim na Europa, e outras lnguas mas ao oeste, como rabe e armnio, a tradio aristotlica era considerada uma codificao superior das leis do raciocnio. Somente no sculo XIX, com o maior familiaridade com a cultura clssica indiana e um conhecimento mais profundo da China que essa percepo mudou.

Lgica na filosofia islmica

Aps a morte de Muhamed, a lei islmica desempenho uma forte influncia na formao dos padres dos argumentos, o que permitiu uma argumentao romanceada no Kalan, mas essa influncia foi amenizada por algumas idias da filosofia grega que surgiram com o crescimento dos filsofos Mutazilah que tentaram combinar a lgica e o racionalismo da filosofia grega com a doutrina islmica e mostrar que as duas esto inerentemente interligadas. A influncia dos tratados gregos sobre os filsofos islmicos foi crucial na aceitao da lgica grega pela Europa medieval, e os comentrios de Averris sobre o rganon teve um papel importante no subseqente desenvolvimento da lgica medieval europia.

Apesar da sofisticao lgica de Al-Ghazali, o crescimento da escola Asharite lentamente sufocou os tratados em lgica do mundo islmico.

Lgica medieval

Lgica medieval (tambm conhecida como lgica escolstica) a lgica aristotlica desenvolvida na era medieval no perodo de 1200-1600 d.C. Esta tradio foi fundamentada atravs de textos como o Tractatus do Pedro da Espanha (sculo XIII), cuja verdadeira identidade desconhecida. Toms de Aquino foi o filsofo que ousou mudar a antiga concepo tradicional, baseada em Plato e Agostinho, concebendo uma viso aristotlica, e desenvolvendo a escoltica tomista.

Essa antiga tradio tambm recebeu diversas consideraes diferentes no sculo XIV com as obras de William de Ockham (1287-1347) e Jean Buridan.

Os ltimas obras dessa tradio so Lgica de John Poinsot (1589-1644, tambm conhecido como John de St Thomas), e o Discusses Metafsicas de Francisco Suarez (1548-1617).

Lgica tradicional

Esta tradio comeou com o livro Lgica, ou a arte do pensamento ou Port-Royal Logic de Antoine Arnauld e Pierre Nicole. Publicado em 1662, esse livro foi a mais influente introduo em lgica at o inicio do sculo 20. Port-Royal Logic apresenta ao leitor uma doutrina cartesiana (onde uma proposta uma combinao de idias ao invs de termos) com uma estrutura que deriva da lgica aristotlica e medieval. O livro teve oito edies entre 1664 e 1700. Ele foi reimpresso em ingls ate o fim do sculo XIX.

A descrio das proposies que Locke faz em Uma Tese a Respeito do Entendimento Humano a mesma do Port-Royal. Proposies verbais, que so palavras, so signos que representam nossas idias, juntando-as ou separando-as em sentenas verdadeiras ou falsas. Ento estas preposies consistem em juntar ou separar esse signos de acordo com as coisas que eles representam para concordar ou discordar. (Lock, Uma Tese a Respeito do Entendimento Humano, IV. 5 6)

Obras que se enquadram nessa tradio incluem Isaac Watts Lgica: Ou, o Correto Uso da Razo (1725), Lgica de Richard Wately (1826), e uma das ltimas grande obras dessa tradio Um Sistema Lgico de John Stuart Mill (1843).

O advento da lgica moderna

Historicamente, Ren Descartes, deve ter sido o primeiro filsofo a utilizar as tcnicas algbricas como meio de explorao cientfica. A idia de um clculo do raciocnio tambm foi cultivada por Gottfried Wilhelm Leibniz.

Gottlob Frege no (Begriffschrift, ou ideografia) criou um sistema de representao simblica para representar formalmente a estrutura dos enunciados lgicos e suas relaes, e a inveno do clculo dos predicados. Esta parte da decomposio funcional da estrutura interna das frases (substituindo a velha dicotomia analtica sujeito-predicado, herdada da tradio lgica aristotlica, pela oposio matemtica funo-argumento) e da articulao do conceito de quantificao (implcito na lgica clssica da generalidade), tornando assim possvel a sua manipulao em regras de deduo formal. (os enunciados "para todo o x", "existe um x" que denotam operaes de quantificao sobre variveis lgicas tm a sua origem no seu trabalho fundador, ex: "Todos os humanos so mortais" se torna "Todos os X so tais que, se x um humano ento x mortal.").

Ao contrrio de Aristteles, e mesmo de Boole, que procuravam identificar as formas vlidas de argumento, a preocupao bsica de Frege era a sistematizao do raciocnio matemtico, ou dito de outra maneira, encontrar uma caracterizao precisa do que uma demonstrao matemtica. Frege havia notado que os matemticos da poca freqentemente cometiam erros em suas demonstraes, supondo assim que certos teoremas estavam demonstrados, quando na verdade no estavam. Para corrigir isso, Frege procurou formalizar as regras de demonstrao, iniciando com regras elementares, bem simples, sobre cuja aplicao no houvesse dvidas. O resultado que revolucionou a lgica, foi a criao do clculo de predicados (ou lgica de predicados).

Em 1889 Giuseppe Peano publicou seus nove axiomas, que mas tarde cinco destes vieram a ser conhecido com axiomas de Peano e, destes cinco, um veio a ser a formalizao do princpio da induo matemticaSiteografiahttp://www.cefetgo.br/pensar/PAGES/convite/cnvt/und02/m01.htmhttp://pt.wikipedia.org/wiki/L%C3%B3gicahttp://enciclopedia.tiosam.com/enciclopedia/enciclopedia.asp?title=Hist%C3%B3ria_da_l%C3%B3gicahttp://www.vestibular1.com.br/UNIDADE IICaptulo 1 Noes de Lgica Matemtica

CLCULO PROPOSICIONALComo primeira e indispensvel parte da Lgica Matemtica temos o CLCULO PROPOSICIONAL ou CLCULO SENTENCIAL ou ainda CLCULO DAS SENTENAS.

CONCEITO DE PROPOSIO

PROPOSIO: sentenas declarativas afirmativas (expresso de uma linguagem) da qual tenha sentido afirmar que seja verdadeira ou que seja falsa.

A lua quadrada. A neve branca. Matemtica uma cincia.

No sero objeto de estudo as sentenas interrogativas ou exclamativas.

OS SMBOLOS DA LINGUAGEM DO CLCULO PROPOSICIONAL

VARIVEIS PROPOSICIONAIS: letras latinas minsculas p,q,r,s,.... para indicar as proposies (frmulas atmicas) .Exemplos: A lua quadrada : p A neve branca : q

CONECTIVOS LGICOS: As frmulas atmicas podem ser combinadas entre si e, para representar tais combinaes usaremos os conectivos lgicos :

: e , : ou , : se...ento , : se e somente se , : no

Exemplos:

A lua quadrada e a neve branca. : p q (p e q so chamados conjunctos)

A lua quadrada ou a neve branca. : p q ( p e q so chamados disjunctos)

Se a lua quadrada ento a neve branca. : p q ( p o antecedente e q o conseqente)

A lua quadrada se e somente se a neve branca. : p q

A lua no quadrada. : p

SMBOLOS AUXILIARES : ( ) , parnteses que servem para denotar o "alcance" dos conectivos;

Exemplos:

Se a lua quadrada e a neve branca ento a lua no quadrada. : ((p q) p)

A lua no quadrada se e somente se a neve branca. : (( p) q))

DEFINIO DE FRMULA :

1. Toda frmula atmica uma frmula.2. Se A e B so frmulas ento (A B) , (A B) , (A B) , (A B) e ( A) tambm so frmulas.3. So frmulas apenas as obtidas por 1. e 2. .

Os parnteses sero usados segundo a seguinte ordem dos conectivos: , , , , .

Com o mesmo conectivo adotaremos a conveno pela direita.

Exemplo: a frmula p q r p q deve ser entendida como (((p q) ( r)) ( p ( q)))

AS TABELAS VERDADE

A lgica clssica governada por trs princpios (entre outros) que podem ser formulados como segue:

Princpio da Identidade: Todo objeto idntico a si mesmo.

Princpio da Contradio: Dadas duas proposies contraditrias (uma negao da outra), uma delas falsa.

Princpio do Terceiro Excludo: Dadas duas proposies contraditrias, uma delas verdadeira.

Com base nesses princpios as proposies simples so ou verdadeiras ou falsas - sendo mutuamente exclusivos os dois casos; da dizer que a lgica clssica bivalente.

Para determinar o valor (verdade ou falsidade) das proposies compostas (moleculares), conhecidos os valores das proposies simples (atmicas) que as compem usaremos tabelas-verdade :

1.Tabela verdade da "negao" : ~p verdadeira (falsa) se e somente se p falsa (verdadeira).

p~p

VF

FV

2. Tabela verdade da "conjuno" : a conjuno verdadeira se e somente os conjunctos so verdadeiros.

pqp q

VVV

VFF

FVF

FFF

3. Tabela verdade da "disjuno" : a disjuno falsa se, e somente, os disjunctos so falsos.

pqp q

VVV

VFV

FVV

FFF

4. Tabela verdade da "implicao": a implicao falsa se, e somente se, o antecedente verdadeiro e o conseqente falso.

pqp q

VVV

VFF

FVV

FFV

5. Tabela verdade da "bi-implicao": a bi-implicao verdadeira se, e somente se seus componentes so ou ambos verdadeiros ou ambos falsos

pqp q

VVV

VFF

FVF

FFV

Exemplo: Construir a tabela verdade da frmula : ((p q) ~p) (q p)pq ((p q) ~p) (q p)

VVV F FVV

VFV F FVF

FVV V VFF

FFF V VFF

NMERO DE LINHAS DE UMA TABELA-VERDADE: Cada proposio simples (atmica) tem dois valores V ou F, que se excluem. Para n atmicas distintas, h tantas possibilidades quantos so os arranjos com repetio de 2 (V e F) elementos n a n. Segue-se que o nmero de linhas da tabela verdade 2n. Assim, para duas proposies so 22 = 4 linhas; para 3 proposies so 23 = 8; etc.

Exemplo: a tabela - verdade da frmula ((p q) r) ter 8 linhas como segue :

pqr((p q) r )

VVVV V

VVFV F

VFVF V

VFFF V

FVVF V

FVFF V

FFVF V

FFFF V

NOTA: "OU EXCLUSIVO" importante observar que "ou" pode ter dois sentidos na linguagem habitual: inclusivo (disjuno) ("vel") e exclusivo ( "aut") onde p q significa ((p q) (p q)).

pq((p q) (p q))

VV V F F V

VF V V V F

FV V V V F

FF F F V F

A LGEBRA DOS CONJUNTOS

O Clculo Proposicional e a lgebra dos Conjuntos possuem estruturas semelhantes.Toda frmula do Clculo Proposicional determina uma operao correspondente entre conjuntos :

a negao ( ) corresponde complementao ( ),

a conjuno ( ) corresponde interseco ( ) ,

a disjuno ( ) corresponde unio ( ).

As variveis proposicionais podem servir como variveis simbolizando conjuntos na nova expresso.

Exemplo: (( p q) p)corresponde a (( p q ) p)

Podemos expressar, as operaes entre conjuntos atravs dos DIAGRAMAS DE EULER-VENN (John Venn 1834-1923) que so teis na verificao de propriedades de operaes entre conjuntos, mas no devem ser considerados instrumentos de prova matemtica rigorosa. Verifique seu conhecimento com estas operaes considerando 2 conjuntos e, em seguida, com 3 conjuntos.

1.COMPLEMENTAO : pque corresponde NEGAO :p

p~ p

1VF

2FV

onde as linhas (1) e (2) da tabela correspondem s regies (1) e (2) do diagrama respectivamente.

2.UNIO : p q que corresponde DISJUNO: p q p q

pqp q

1VVV

2VFV

3FVV

4FFF

as linhas (1), (2), (3) e (4) da tabela correspondem s regies (1), (2), (3) e (4) do diagrama respectivamente.A regio hachurada no diagrama corresponde s linhas da tabela onde a frmula p q assume valor V.

3. INTERSECO : p q que corresponde CONJUNO: p q p q

pqp q

1VVV

2VFF

3FVF

4FFF

A regio hachurada do diagrama corresponde linha (1) da tabela, onde a frmula pq assume valor V.

A figura abaixo forma um Diagrama de Venn apropriado para trs conjuntos. Temos 8 regies que correspondem, respectivamente, s 8 linhas da tabela-verdade ao lado do diagrama :

pqr

1VVV

2VVF

3VFV

4VFF

5FVV

6FVF

7FFV

8FFF

Exemplo: O diagrama de Venn abaixo corresponde frmula ((p q) r) e expresso (p q) r. O valor V da frmula (ltima coluna) corresponde regio 2 do diagrama de Venn.

pqr((p q) r )

VVVF V V V

VVFV V F F

VFVF F V V

VFFF F V F

FVVF F V V

FVFF F V F

FFVF F V V

FFFF F V F

TAUTOLOGIA E CONTRA -TAUTOLOGIA TAUTOLOGIA ou FRMULA LOGICAMENTE VLIDA : Frmula que possui apenas valor V em sua tabela verdade. Exemplo : p p

p pp p

1VF V

2FV V

CONTRA-TAUTOLOGIA ou FRMULA LOGICAMENTE FALSA: Frmula que possui apenas valor F em sua tabela verdade. Exemplo : p p

p pp p

1VF F

2FV F

pqp q

1VVV

2VFF

3FVV

4FFV

CONTINGENTE ou INDETERMINADA: Frmula que possui valores V e F em sua tabela verdade.Exemplo : p q

REGRAS DE INFERNCIA.: A frmula implica tautologicamente a frmula e indicamos se e somente se a frmula uma tautologia .

RegrasFrmulas AtmicasFrmulas Compostas

Modus PonensMPp (p q) qA, A B / B

Modus TollensMT q ( p q ) p B, A B / A

Silogismo HipotticoSH(p q) ( q r) (p r)A B, B C / A C

Silogismo DisjuntivoSD(p q) p q A, A B / B

SimplificaoSMp q pA B / A

AdioADp p qA / A B

EliminaoEL(p (q r) ) q p r B , (A (B C) / A C

Prova por CasosCS(p r) ( q r) (p q) rA C, B C / (A B ) C

EQUIVALNCIAS TAUTOLGICAS : As frmulas e so tautologicamente equivalentes e indicamos se e somente se a frmula uma tautologia

Comutativap q q pp q q p

Associativa(p q) r p (q r)(p q) r p (q r)

Idempotentep p pp p p

Propriedades de Vp V pp V V

Propriedades de Fp F Fp F p

Absorop ( p r ) pp (p r) p

Distributivasp (q r) (p q ) (p r)p (q r) (p q ) (p r)

Distributivasp (q r) (p q) (p r)p (q r) (p q) (p r)

Leis de De Morgan (p q) p q (p q) p q

Def. implicaop q ~p qp q ( p q)

Def. bicondicionalp q (p q) ( q p)p q (~p q) (~q p)

Negao ( p) p

Contraposiop q q p

Exportao( )Importao ( )(p q) r p ( q r )

Troca de Premissasp (q r ) q ( p r )

Exemplo : Dadas as frmulas A: p (q r) e B : (q r ) p vamos verificar que A B ou ainda que A / B. Basta verificar, com o uso das tabelas verdade, que A B tautologia. p q r ( p (q r)) ( (q r ) p)

VVVVVV

VVFFVF

VFVFVF

VFFFVF

FVVVVV

FVFVVV

FFVVVV

FFFVVV

Neste exemplo, A B pois A B tautologia.

As TAUTOLOGIAS so infinitas e desempenham um importante papel nos processos de deduo no Clculo Proposicional como veremos em prximos tpicos.

FORMAS NORMAIS CONJUNTIVA E DISJUNTIVA

Algumas EQUIVALNCIAS TAUTOLGICAS dadas acima nos permitem transformar qualquer frmula em uma frmula logicamente equivalente, que no contenha os conectivos e , transformando-a em uma FORMA NORMAL CONJUNTIVA (FNC) ou em uma FORMA NORMAL DISJUNTIVA (FND) como segue:

1. substitui-se frmulas: A B por A B e A B por ( A B) ( B A)2. elimina-se a negao que precede os parnteses substituindo-se:(A B) por A B e (A B) por A B .3. eliminam-se as negaes mltiplas substituindo ( A) por A.4. elimina-se o alcance dos conectivos substituindo

para obter a FNC : A (B C) por (A B) (A C)para obter a FND : A (B C) por (A B) (A C)

Deste modo, uma frmula est em FORMA NORMAL CONJUNTIVA: FNC ou em FORMA NORMAL DISJUNTIVA: FND se, e somente se:

1. No mximo contm os conectivos, , .2. A negao no tem alcance sobre os conectivos e .3. No aparecem negaes sucessivas.4. O conectivo no tem alcance sobre na FNC e, o conectivo no tem alcance sobre na FND.

Exemplos: FNC : ( p q) (r s p) FND : p (q r) ( s p)

Exemplo: Determine uma FND e uma FNC equivalente frmula ((p q) q) ( r q) .

1.((p q) q) ( r q)Frmula dada

2. ((p q) q) ( r q)1. Def. de Implicao

3.( (p q) q) (r q)2. De Morgan

4.( p q) q (r q )3. Negao e De Morgan

5.( p q) q (r q )4.FND

6.(( p q) ( q q)) (r q)5. Distributiva

7.(( p q) V) (r q)6. Tautologia

8.( p q) ( r q)7. Propriedade de V

9.( p q r) ( p q q)8. Distributiva

10.( p q r) ( p q )9. Idempotente e FNC

PROBLEMA DE POST

Como j observamos podemos construir a tabela verdade de uma frmula conhecidos os valores verdade das frmulas que a compem. O problema recproco se coloca : para toda tabela verdade, existe uma frmula que a determina? Este problema conhecido como PROBLEMA DE POST (Emil Leon Post 1888-1995) e pode ser resolvido obtendo-se uma FNC ou uma FND que satisfaa a tabela verdade dada.

Para se obter uma FND:

1. Observamos todas as linhas da tabela que possuem V na ltima coluna;2. Construimos para cada uma destas linhas as conjunes correspondentes;3. Fazemos a disjuno destas conjunes obtendo uma frmula em FND que satisfaz a tabela verdade.

Exemplo: Determine uma frmula que satisfaa a tabela verdade abaixo: p q ?VVV(p q)

VFF

FVF

FFV( p q)

Resposta: Frmula obtida (p q) ( p q) FND

Para se obter uma FNC:

1. Observamos todas as linhas da tabela que possuem F na ltima coluna;2. Construimos para cada uma destas linhas as disjunes correspondentes;3. Fazemos a conjuno destas disjunes obtendo uma frmula em FNC que satisfaz a tabela verdade.

Exemplo: Determine uma frmula que satisfaa a tabela verdade abaixo: p q ?VVV

VFF p q

FVF p q

FFV

Resposta: Frmula obtida ( p q) (p q) FNC

As FND e FNC obtidas como acima so completas ou seja, em cada disjuncto (FND) ou em cada conjuncto (FNC) todas as variveis proposicionais esto presentes.

NOES DE LGEBRA BOOLEANA

"Uma das caractersticas da investigao cientfica procurar padres ou semelhanas entre fenmenos observados"(livro I). Vimos que o Clculo Proposicional e a Teoria dos Conjuntos possuem algumas propriedades em comum ou sejam so estruturas matemticas que, juntamente com operaes ou relaes entre seus objetos obedecem certas regras." Podemos comparar uma estrutura matemtica a um esqueleto humano pois, embora as aparncias externas das pessoas sejam diferentes, a forma e a disposio dos ossos so as mesmas."(livro I). Assim, vamos definir, uma estrutura matemtica, lgebra Booleana, que incorpora as propriedades bsicas do Clculo Proposicional e da Teoria dos Conjuntos, ou seja, um outro modelo de uma mesma estrutura matemtica. O conceito de lgebra Booleana foi formulado pelo matemtico ingls George Boole por volta de 1850.

Por LGEBRA BOOLEANA entendemos um conjunto B={p, q, r , ..} junto com duas operaes binrias + e em B, uma operao singular em B e dois elementos distintos 0 e 1 de B tais que valem as seguintes propriedades: (para todo p , q , r em B ) :

Associativa(p + q) + r = p + (q + r)(p q) r = p (q r)

Comutativap + q = q + pp q = q p

Idempotentep + p = pp p = p

Absoro(p q) + p = p(p + q) p = p

Distributivap + (q r) = (p + q) (p + r)p (q + r) = (p q) + (p r)

Propriedades do 0p + 0 = pp 0 = 0

Propriedades do 1p + 1 = 1p 1 = p

Quaisquer que seja p em B, existe p em B tal quep + p = 1p p = 0

Indicamos uma lgebra Booleana por [ B , + , , , 0 , 1 ].

- A operao p q pode ser denotada simplesmente por pq eliminando o operador .

- normal a seguinte terminologia na lgebra Booleana :p q : encontro de p e q.p + q : juno de p e q.p : complemento de p.0 : elemento zero.1 : elemento unitrio.

Uma expresso booleana, uma frmula e uma expresso na lgebra do conjuntos,so correspondentes se substituimos , + , , = , 0 , 1 respectivamente por ~ , , , , F , V ou ainda por , , , = , , U(considerando-se p , q ,.. como: elementos de B , variveis proposicionais ou conjuntos respectivamente).

Exemplo: (p + (q r)) corresponde a ( p (q r)) ou ainda a (p (q r))

Para formalizar as semelhanas entre o Clculo Proposicional e a lgebra Booleana, notemos que o conjunto das proposies uma lgebra de Boole em relao conjuno, disjuno e negao.

APLICAES DE LGEBRA BOOLEANA : MAPA DE KARNAUGH

De modo sucinto podemos dizer que o MAPA DE KARNAUGH, idealizado em 1950 por MauriceKarnaugh, um mtodo de simplificao de expresses lgicas fundamentado em teoremas da lgebra Booleana e utilizando representaes grficas. Utilizando o mapa de Karnaugh podemos simplificar frmulas ou expresses booleanas em FND COMPLETA, sem o uso direto de propriedades para obter tais simplificaes.

REPRESENTAO GRFICA : Temos as seguintes representaes grficas (mapas), de acordo com o nmero de variveis (aqui representadas por letras maisculas) das expresses: (no que se segue entende-se AB como A B)a) Duas variveis:

AA

B

B

b) Trs variveis :

ABABABAB

C

C

c) Quatro variveis :

ABABABAB

CD

CD

CD

CD

Em cada mapa:

Os quadrados de cima e os de baixo so adjacentes; os da esquerda e os da direita so adjacentes.Os quadrados adjacentes diferem apenas por uma varivel .Cada quadrado indicar um DISJUNCTO da FNDCOMPLETA que est sendo representada.Cada DISJUNCTO ser representado escrevendo 1 no respectivo quadrado.

Exemplos:Representar a expresso ABC + ABC + ABC AB AB AB AB

C 1 1

C 1

Representar a expresso AB+ AB + AB A A

B 1

B 1 1

Podemos construir Mapas de Karnaugh para 5 ou mais variveis passando para representaes grficas tridimensionais tornando-se inadequado.

SIMPLIFICAO : Para simplificar procedemos do seguinte modo:

1. Agrupar , traando ovais ao redor de todos os "1" para formar grupos de 2n "1" adjacentes.2. Nenhum "1" pode ficar fora dos grupos formados. Se necessrio, agrup-lo sozinho.3. Quanto maior o grupo, mais simplificada ficar a expresso.4. Se necessrio, um "1" pode ser agrupado mais de uma vez. Nunca agrup-lo se no houver necessidade.5. A varivel que se repetir em cada grupo permanece na expresso. A varivel que no se repete eliminada.

Exemplos:a) Simplificando a expresso ABC + ABC + ABC obtemos a expresso ABC + BC

b) Simplificando a expresso AB+ AB + AB obtemos A+ B

c) Simplifique usando um applet apropriado para 4 variveis.

APLICAES DE LGEBRA BOOLEANA : LGEBRA DOS CIRCUITOS

A introduo de uma lgebra Booleana no estudo dos circuitos deve-se ao matemtico americano CLAUDE ELWOOD SHANNON (1916-2001) (A Symbolic Analysis of Relay and Switching Circuits - 1938). De modo sucinto mostraremos esse tipo de relacionamento com a Clculo Proposicional e a lgebra Booleana.

Um interruptor um dispositivo ligado a um ponto de um circuito, que pode assumir um dos dois estados, "fechado" ou "aberto". No estado "fechado" (que indicaremos por 1) o interruptor permite que a corrente passe atravs do ponto, enquanto no estado "aberto" (que indicaremos por 0) nenhuma corrente pode passar pelo ponto.

1.Circuito com um interruptor p: p

A indicao "fechado" ou "aberto" do interruptor ser conhecida com a indicao de p=1 ou p=0 respectivamente.

2.Circuito com dois interruptores p e q:

Em paralelo indicado por p + q p

q Neste caso no passa corrente se e somente p=0 e q=0 ou seja, esto ambos "abertos" o que corresponde no Clculo Proposicional tabela verdade da disjuno p q .

Em srie indicado por p q ou pq p q

Neste caso passa corrente se e somente se p=1 e q=1 ou seja, esto ambos "fechados" o que corresponde no Clculo Proposicional tabela verdade da conjuno p q .

Circuitos acoplados contraditrios: quando um abre o outro fecha e reciprocamente correspondendo tabela verdade da negao.Circuitos acoplados equivalentes: se comportam do mesmo modo correspondendo tabela verdade da bi-implicao p q .

Exemplo : A expresso booleana correspondente ao esquema abaixo :(( p q) + ((p q) + q)) = pq + pq + qSimplificando a expresso:(( p q) + ((p q) + q)) = ( p q) + q = q (por absoro) representamos o circuito simplificado obtido :

Exemplo : A expresso e um circuito correspondente frmula( p q) r p q r ser : p + q +r

Exemplo : Um comit tem 3 membros . Um projeto passa se e somente se o presidente vota a favor e obtm maioria. Projetar um circuito de modo que cada membro vote a favor apertando um boto e tal que a luz se acenda se o projeto for aprovado.

Soluo: Sendo P o presidente e A e B os outros dois membros, a tabela verdade abaixo corresponde s informaes dadas onde 1 representa a aprovao do projeto.

Obtendo a FND correspondente temos (P A B) + (P A B ) + (P A B) que simplificando por Mapa de Karnaugh temos PA + PB = P ( A + B) sendo simples a representao do circuito.

P A B ?

1111

1101

1011

1000

0110

0100

0010

0000

VALIDADE DE ARGUMENTO

No incio deste roteiro, mencionamos que nosso principal objetivo a investigao da validade de ARGUMENTOS:Conjunto de enunciados dos quais um a CONCLUSO e os demais PREMISSAS.

Vamos verificar como podemos proceder na investigao de certos argumentos de modo formal.

DEFINIO: Chamamos ARGUMENTO uma seqnciaA1 , A2 ,A3 ,... , An , B (n 0) de frmulas onde os Ai (0 i n) chamam-se premissas e a ltima frmula B, concluso.

DEFINIO: Um ARGUMENTO A1 , A2 ,A3 ,... , An , B VLIDO se e somente se, sendo as premissas verdadeiras a concluso B tambm verdadeira, ou ainda, se e somente se, a frmula

A1 A2A3 ... An B uma tautologia que ser indicado como segueA1 , A2 , A3 ,... , An | B que se l :"A1 , A2 , A3 ,... , An acarretam B" ou, "B decorre de A1 , A2 , A3 ,... , An " ou,"B se deduz de A1 , A2 , A3 ,... , An" ou ainda, "B se infere de A1 , A2 , A3 ,... , An ."

VALIDADE DE UM ARGUMENTO: VERIFICAO POR TABELA VERDADE.

Com o uso das tabelas verdade suficiente verificar se a frmulaA1 A2A3 ... An B tautologia.

Exemplo: O argumento p, q r, r, q vlido pois a frmula(p (q r) r ) q uma tautologia.O que verificamos nas linhas onde as premissas so verdadeiras que a concluso tambm verdadeira(tabela verdade abaixo, linha 4).

pqrpq r r q

VVVVVFF

VVFVFVF

VFVVVFV

VFFVVVV

FVVFVFF

FVFFFVF

FFVFVFV

FFFFVVV

VALIDADE DE UM ARGUMENTO: DEMONSTRAO

Podemos verificar a validade de um argumento atravs de mtodos de demonstrao :

1. DEMONSTRAO DIRETA2. DEMONSTRAO INDIRETA - CONDICIONAL3. DEMONSTRAO INDIRETA - POR ABSURDO4. DEMONSTRAO INDIRETA RVORE DE REFUTAO

1. DEMONSTRAO DIRETAConsiste em demonstrar ou deduzir a concluso B a partir das premissas A1 , A2 , A3 ,... , An , aplicando as EQUIVALNCIAS TAUTOLGICAS e as REGRAS DE INFERNCIA .

Exemplo : Demonstrar a validade do argumento p, q r , r , qDemonstrao :1. p premissa2. q r premissa3. r premissa4. q Concluso (2 e 3 : Modus Tollens)

Exemplo :Demonstrar a validade do argumento p q , q r , r s , s pDemonstrao :1. p q premissa2. q r premissa3. r s premissa4. p r 1.2. Silogismo Hipottico5. r s 3. Def. de implicao6. p s 4.5. Silogismo Hipottico7. s p 6. Contraposio8. s p Concluso 7. Negao

2. DEMONSTRAO INDIRETA - CONDICIONAL

Para demonstrar a validade de argumentos cuja concluso uma frmula condicional do tipo B C , considera-se o antecedente B, como uma premissa adicional e o conseqenteC ser a concluso a ser demonstrada.De fato, sendo:1. A1 , A2 , A3 ,... , An , B , C vlido ento2. A1 , A2 , A3 ,... , An , B | C isto ,3. ((A1 A2 A3 ... An ) B ) C tautologia4. (A1 A2 A3 ... An ) (B C) tautologia (Importao e Exportao) e portanto5. A1 , A2 , A3 ,... , An | B C ou ainda,6. A1 , A2 , A3 ,... , An, B C vlido

Exemplo : Demonstrar a validade do argumento p q , q r , r s , s pDemonstrao :1. p q premissa2. q r premissa3. r s premissa4. s premissa adicional5. r 3.4. Silogismo Disjuntivo6. p r 1.2. Silogismo Hipottico7. r p 6. Contraposio8. p Concluso 5.7. Modus Ponens

3.DEMONSTRAO INDIRETA - POR ABSURDO

Para demonstrar, por absurdo, um argumento A1 , A2 , A3 ,..., An, B considera-se a negao da conclusoB como premissa adicional e conclui-se uma frmula F (frmula falsa do tipo )De fato, sendo:1.A1 , A2 , A3 ,..., An , B | F vlido, temos2.A1 , A2 , A3 ,..., An | B F isto ,3.A1 , A2 , A3 ,..., An | B F (Def. implicao)4.A1 , A2 , A3 ,..., An | B F (Negao)5.A1 , A2 , A3 ,..., An |B (Propriedade de F) ou ainda,6.A1 , A2 , A3 ,... , An , B vlido.

Exemplo : Demonstrar, por absurdo, a validade do argumentop q , q r , r s , s p1.p q premissa2. q r premissa3. r s premissa4. ( s p) premissa adicional5.p r 1.2. Silogismo Hipottico6. r s 3. Def. de implicao7. p s 5.6. Silogismo Hipottico8. s p 7. Contraposio9. ( s p) ( s p) 4. 8. Conjuno10. F DEMONSTRAO INDIRETA RVORE DE REFUTAORVORE DE REFUTAO um mtodo para verificar a validade de um argumento, anlogo demonstrao por absurdo.Para testarmos a validade de um argumento construmos uma lista de frmulas consistindo de suas premissasA1, A2 , A3 ,... ,An e a negao da sua concluso B que formam a RAIZ DA RVORE. A rvore continua abaixo com a construo de seus RAMOS por aplicaes de regras, que sero especificadas abaixo, e gerando novas linhas na rvore. A rvore termina quando as frmulas de seus ramos so: variveis proposicionais, negaes de variveis proposicionais, ou quando encontrarmos em todos os ramos uma frmula F.

Se encontrarmos em todos os ramos da rvore uma frmula F, ento a nossa tentativa de refutao falhou ou seja, o argumento vlido. Se em algum ramo da rvore no foi possvel encontrar uma frmula F, ento refutamos o argumento, isto , o argumento no vlido.

Exemplo: Construir uma rvore de refutao para mostrar que: p q | p

- Escrevemos a premissa e a negao da concluso:1. p q2. p

- Sabemos que p q verdadeira se, e somente se, p e q so ambas verdadeiras; da, podemos substituirp q por p e q gerando as linhas 3. e 4., respectivamente, e MARCANDO ( ) a frmula p q .(Uma frmula marcada no poder mais ser utilizada na construo da rvore!!!)1. p q 2. p3. p4. q

- Como p verdadeira se e somente se p verdadeira, marcamos p e substitumos por p gerando a linha 5. :1. p q 2. p 3. p4. q5. p

- A rvore terminou pois das premissas e da negao da concluso obtivemos variveis proposicionais ou negaes de variveis proposicionais. Por outro lado encontramos nas linhas 3. e 5. uma frmula F, ou seja, nossa tentativa de refutao falhou e portanto o argumento vlido. Isso ser expresso escrevendo um X no final da lista, gerando a linha 6 e fechando o nico ramo da rvore.1. p q 2.p 3. p4. q5. p6. X

A rvore de refutao est completa. A nossa busca para uma refutao do argumento dado falhou e, portanto, o argumento vlido.

Exemplo:Construir uma rvore de refutao para mostrar que : p q, p |q

- Iniciamos a rvore escrevendo a lista de frmulas as premissas e a negao da concluso:1. p q2. p3. q

- Sabemos que p q verdadeira se, e somente se, p verdadeira ou q verdadeira. Para representar esse fato, marcamos p q e ramificamos a rvore, gerando a linha 4 com dois ramos:1. p q 2. p3. q / \4. p q

- A rvore terminou pois das premissas e da negao da concluso obtivemos variveis proposicionais ou negaes de variveis proposicionais. Por outro lado encontramos uma frmula F em um ramo, nas linhas 2. e 4. e no outro ramo, nas linhas 3. e 4., ou seja, nossa tentativa de refutao falhou e portanto o argumento vlido. Isso ser expresso escrevendo um X no final de cada ramo da lista gerando a linha 5 e fechando os dois ramos da rvore.1. p q 2. p3. q / \4. p q5. X X

A rvore de refutao est completa. Como a tentativa de refutao falhou nos dois ramos, o argumento dado vlido.

Exemplo:Construir uma rvore de refutao para verificar a validade do argumento:p q, p | q1. p q2. p3. q

- Temos que q equivalente a q; da, marcamos q e escrevemos q gerando a linha 4. :1. p q2. p3. q 4. q

- Como no exemplo anterior, marcamos p q e ramificamos a rvore gerando a linha 5. com dois ramos:1. p q 2. p3. q 4. q / \5. p q

- A rvore terminou e nos dois ramos no h contradies, ou seja, uma frmula F. Neste caso os ramos no sero fechados e o argumento no vlido.

REGRAS PARA A CONSTRUO DE UMA RVORE DE REFUTAOAs regras para a construo de uma rvore de refutao esto relacionadas com as tabelas verdade j conhecidas. Ao aplicar uma regra em uma frmula da rvore, temos a observar que :

- a frmula ser marcada ( ) para evitar aplicaes repetidas de uma regra em uma mesma frmula.- a aplicao de uma regra deve gerar : uma ou duas linhas, um ramo ou dois ramos conforme a regra, e ser aplicada em todos os ramos abertos (no fechados com X) aos quais a frmula pertence.

Temos as seguintes regras :

1. REGRA DA DUPLA NEGAO () : Uma frmula do tipo A gera uma linha e escrevemos A na linha. Procedemos assim em todos os ramos abertos aos quais a frmula A pertence pois, A verdadeira se e somente se A verdadeira.

2. REGRA DA CONJUNO (): Uma frmula do tipo A B gera duas linhas e escrevemos, em cada linha, as frmulas A e B. Procedemos assim em todos os ramos abertos aos quais a frmula A B pertence pois, A B assume valor V se, e somente, as frmulas A e B so verdadeiras.1. A B 2. A3. B

3. REGRA DA DISJUNO (): Uma frmula do tipo A B gera uma linha e dois ramos e escrevemos, na linha e, em cada ramo, as frmulas A e B respectivamente. Procedemos assim em todos os ramos abertos aos quais a frmula A B pertence pois, A B assume valor V se, e somente, a frmula A verdadeira ou a frmula B verdadeira.1.A B / \2. A B

4. REGRA DA IMPLICAO (): Uma frmula do tipo A B gera uma linha e dois ramos e escrevemos, na linha e, em cada ramo, as frmulas A e B respectivamente. Procedemos assim em todos os ramos abertos aos quais a frmulaA B pertence pois, A B assume valor V se, e somente, a frmula A verdadeira ou a frmula B verdadeira.1. A B / \ A B

5. REGRA DA BI- IMPLICAO () : Uma frmula do tipo AB gera duas linhas e dois ramos e escrevemos nas linhas as frmulas A e B em um ramo e as frmulas A eB no outro ramo. Procedemos assim em todos os ramos abertos aos quais a frmula AB pertence pois, AB assume valor V se, e somente, a frmula(A B) verdadeira ou a frmula ( A B) verdadeira.AB / \2.A A3.B B

6. REGRA DA NEGAO DA CONJUNO ( ): Uma frmula do tipo(A B) gera uma linha e dois ramos e escrevemos, na linha e, em cada ramo, as frmulas A e B respectivamente. Procedemos assim em todos os ramos abertos aos quais a frmula (A B) pertence pois, (A B) assume valor V se, e somente, a frmula A verdadeira ou a frmula B verdadeira. (A B) / \A B

7. REGRA DA NEGAO DA DISJUNO ( ) : Uma frmula do tipo(A B) gera duas linhas e escrevemos, em cada linha, as frmulas A e B. Procedemos assim em todos os ramos abertos aos quais a frmula (A B) pertence pois, (A B) assume valor V se, e somente, as frmulas AeB so verdadeiras. (A B) A B

8. REGRA DA NEGAO DA IMPLICAO () : Uma frmula do tipo(A B) gera duas linhas e escrevemos, em cada linha, as frmulas A e B. Procedemos assim em todos os ramos abertos aos quais a frmula (A B) pertence pois, (A B) assume valor V se, e somente, as frmulas Ae B so verdadeiras. (A B) 2. AB

9. REGRA DA NEGAO DA BI- IMPLICAO (): Uma frmula do tipo(AB) gera duas linhas e dois ramos e escrevemos nas linhas as frmulas A e B em um ramo e as frmulas A e B no outro ramo. Procedemos assim em todos os ramos abertos aos quais a frmula (AB) pertence pois, (AB) assume valor V se, e somente, a frmula (A B) verdadeira ou a frmula (A B) verdadeira.(AB) / \A A3. B B

10. RAMO FECHADO : Um ramo ser fechado se nele existem uma frmula A e sua negao A e escrevemos X no final do ramo.1. A2. A3. X

OBSERVAES:- As regras dadas para construir rvores de refutao se aplicam em cada linha ao conectivo principal da frmula e no a subfrmulas. Por exemplo,1. p q 2. p q 1.() (INCORRETO!!)- No importa a ordem em que as regras so aplicadas; no entanto, mais eficiente aplicar as regras, primeiramente, em frmulas que no resultam em ramificaes.- Cada linha gerada deve ser justificada indicando a respectiva linha de origem na qual foi aplicada a regra e tambm a regra usada.- Frmula na qual foi aplicada alguma regra deve ser marcada ( ) para evitar aplicaes repetidas da mesma.

Exemplos:1.) Verificar, por meio de rvore de refutao, a validade do argumento:p r s, r s q , p q

1. p r s Premissa2. r s q Premissa3. (p q) Negao da Concluso4. p 3.( )5. q 3.( ) / \6. p (r s) 1.( )7. X(6.4) / \8. r s 6. ( ) / \ / \9. (r s) q (r s) q 2.( ) / \ \ / \ \10. r s X r s X ( )11. X ? (9.5) X ? (9.5) (10.8) (10.8)

Temos neste caso dois ramos que no fecharam e, portanto, o argumento no vlido.

2.) Construir uma rvore de refutao para verificar se a frmula(p q) (p q) uma tautologia:

1. ((p q) (p q)) Negao da Concluso2. (p q) 1. ( )3. (p q) 1. ( )4. p 2. ()5. q 2. () / \6. p q 3. ( )7. X X (6.4) (6.5)Todos os ramos esto fechados; assim a frmula vlida, ou seja, uma tautologia.

O CLCULO DE PREDICADOS DE 1a ORDEMO Clculo de Predicados, dotado de uma linguagem mais rica, tem vrias aplicaes importantes no s para matemticos e filsofos como tambm para estudantes de Cincia da Computao.

Podemos observar que nas linguagens de programao conhecidas como PROCEDURAIS (Pascal e outras) , os programas so elaborados para "dizer" ao computador a tarefa que deve ser realizada. Em outras linguagens de programao conhecidas como DECLARATIVAS, os programas reunem uma srie de dados e regras e as usam para gerar concluses. Estes programas so conhecidos como SISTEMAS ESPECIALISTAS ou SISTEMAS BASEADOS NO CONHECIMENTO que simulam em muitos casos a ao de um ser humano. Essas linguagens declarativas inclui predicados, quantificadores , conectivos lgicos e regras de inferncia que, como veremos, fazem parte do Clculo de Predicados.

Tambm podemos observar, como expomos abaixo, que existem vrios tipos de argumentos os quais, apesar de vlidos, no possvel justific-los com os recursos do Clculo Proposicional:

1. Todo amigo de Carlos amigo de Jonas. Pedro no amigo de Jonas. Logo, Pedro no amigo de Carlos.

2. Todos os humanos so racionais. Alguns animais so humanos. Portanto, alguns animais so racionais.

A verificao da validade desses argumentos nos leva no s ao significado dos conectivos mas tambm ao significado de expresses como "todo", "algum", "qualquer", etc.

Smbolos da LinguagemPara que possamos tornar a estrutura de sentenas complexas mais transparente necessrio a introduo de novos smbolos na linguagem do Clculo Proposicional, obtendo-se a linguagem do Clculo de Predicados de 1a Ordem.

Nesta nova linguagem teremos, alm dos conectivos do clculo proposicional e os parnteses, os seguintes novos smbolos:

variveis: x,y,z,.....,x ,y ,z ,......constantes : a,b,c,....,a ,b ,c ,......smbolos de predicados: P , Q , R , S ,....quantificadores : (universal) , (existencial)termos: as variveis e as constantes so designadas pelo nome genrico de termos os quais sero designados por t1 , t2 , ...,tn ...

as variveis representam objetos que no esto identificados no Universo considerado ("algum", "algo", etc.);as constantes representam objetos identificados do Universo ("Joo", "o ponto A", etc. );os smbolos de predicados representam propriedades ou relaes entre os objetos do Universo.

Exemplos:

"Maria inteligente" : I(m) ; onde "m" est identificando Maria e "I" a propriedade de "ser inteligente"."Algum gosta de Maria" : G(x,m) ; onde G representa a relao "gostar de" e "x" representa "algum".

De modo geral temos:

P(x) : significa que x tem a propriedade P .(x)P(x): significa que a propriedade P vale para todo x, ou ainda, que todos os objetos do Universo considerado tem a propriedade P.(x)P(x): significa que algum x tem a propriedade P, ou ainda, que existe no mnimo um objeto do Universo considerado que tem a propriedade P.

Notamos que os smbolos de predicados sero unrios, binrios ou n-rios conforme a propriedade que representam envolver, respectivamente um, dois ou mais objetos do universo e dizemos tambm que o smbolo de predicado tem peso 1, peso 2 ... ou peso n.

OBS.: Um smbolo de predicados 0-rio (peso zero) identifica-se com um dos smbolos de predicado; por exemplo: "chove" podemos simbolizar "C".

As frmulas mais simples do Clculo de Predicados de 1a Ordem so chamadas de frmulas atmicas e podem ser definidas como:"Se P for um smbolo de predicado de peso n e se t1 , t2 , ...,tn forem termos ento P(t1 , t2 , ...,tn ) uma frmula atmica."

DEFINIO DE FRMULA:

1.Toda frmula atmica uma frmula.2.Se e forem frmulas ento (), () , ( ) , ( ) e () so frmulas.3.Se for uma frmula e x uma varivel ento (x) e (x) so frmulas.4.As nicas frmulas so dadas por 1. 2. e 3. acima.

Exemplos de frmulas: P(x,a); R(y,b,t); (z)(P(x,a) R(y,b,z)); (x)(P(x,a) R(y,b,t)); (y)(x)R(y,b,t).Assim os argumentos dados no incio podem ser representados simbolicamente como:1. Todo amigo de Carlos amigo de Jonas. Pedro no amigo de Jonas. Logo, Pedro no amigo de Carlos.

(x) (P(x,c) P(x,j)) P(p,j) P(p,c)

onde P(x,y) significa que x amigo de y e c, p, j so constantes que representam Carlos, Pedro e Jonas respectivamente.

2. Todos os humanos so racionais. Alguns animais so humanos. Portanto, alguns animais so racionais.

(x) (P(x) Q(x)) (x) (R(x) P(x)) (x) (R(x) Q(x))

onde P ,Q ,R simbolizam as propriedades de: ser humano, ser racional e ser animal respectivamente.

ESCOPO DE UM QUANTIFICADOR : Se uma frmula e x uma varivel, ento em (x) ou em (x) dizemos que o escopo do quantificador (x) ou (x).

Por exemplo na frmula (y)(x)(R(y,b,t) (z) P(z,a)) temos os seguintes quantificadores e seus respectivos escopos:

(y) : (x)(R(y,b,t) (z) P(z,a))(x) : (R(y,b,t) (z) P(z,a))(z) : P(z,a)

NEGAO DE FRMULAS QUANTIFICADAS: da definio de frmula dada acima podemos perceber que um quantificador universal ou existencial pode ser precedido de uma negao. Vejamos como podemos proceder se for necessrio a eliminao dessa negao.

Consideremos, por exemplo, a frmula (x)P(x) e o conjunto universo U={a,b,c}. evidente que nesse caso temos: (x)P(x) P(a) P(b) P(c).

Podemos considerar ento que :

(x)P(x) (P(a) P(b) P(c)) P(a) P(b) P(c)o qual significa que existe no mnimo um objeto em U tal que P(x) , ou seja ,(x)P(x) (x) P(x) ou ainda de modo geral para uma frmula qualquer temos

(1)(x) (x)

Da equivalncia acima segue imediatamente que :

(2). (x)P(x) (x)P(x)(3). (x)P(x) (x)P(x)(4). (x)P(x) (x)P(x)

ENUNCIADOS CATEGRICOS

Certos enunciados se apresentam freqentemente na Lgica Clssica e tradicionalmente so chamados de Enunciados Categricos.Relacionaremos os quatro enunciados mais comuns que so representados pelas letras A, E, I, O :

A - da forma "Todo P Q" (universal afirmativa)E - da forma "Nenhum P Q" ou "Todo P no Q" (universal negativa)I - da forma "Algum P Q" (particular afirmativa)O - da forma "Algum P no Q" (particular negativa)

simbolizados respectivamente como:

A - (x)(P(x) Q(x))E - (x)(P(x) Q(x))I - (x)(P(x) Q(x))O - (x)(P(x) Q(x))

DIAGRAMAS DE VENN PARA ENUNCIADOS CATEGRICOSSe considerarmos P e Q dados acima como dois conjuntos quaisquer, os enunciados dados podem ser interpretados como segue:

A: "Todo P Q" afirma que todos os elementos de P so elementos de Q, ou seja, que P um subconjunto de Q, isto , P Q .E: "Nenhum P Q" afirma que os conjuntos P e Q no tm elementos em comum, isto , que P Q = ou ainda que P Q.I : "Algum P Q" afirma que os conjuntos P e Q tm pelo menos um elemento em comum, isto , P Q O: "Algum P no Q" afirma que P tem pelo menos um elemento que no est em Q, ou ainda, que P Q .

Estas interpretaes podem ser feitas atravs de Diagramas de Venn, os quais so teis na verificao da validade de argumentos cujas premissas e concluso so enunciados categricos do tipo A, E, I ou O mas no devem ser considerados instrumentos de prova rigorosa.Lembramos que no Clculo Proposicional os diagramas de Venn foram utilizados para estabelecer uma correlao entre as linhas da tabela verdade de uma frmula e as regies do diagrama de Venn correspondente.

Para verificarmos a validade de um argumento, as interpretaes dos enunciados categricos nos Diagramas de Venn sero consideradas como segue:

1. Cada crculo representa uma classe de objeto que quando em branco indica ausncia de informao a respeito do conjunto.2. Crculo hachurado ou regio de um crculo hachurada, representa regio VAZIA de elementos.3. Crculo ou regio de um crculo com X representa regio no vazia de elementos.

Exemplo: Se J representa o predicado "ser jovem" temos os diagramas abaixo:

REPRESENTAO DOS ENUNCIADOS CATEGRICOS

Os enunciados categricos podem ser representados como segue :

ARGUMENTOS CATEGRICOS

VALIDADE DE ARGUMENTOS CATEGRICOS POR DIAGRAMAS DE VENNPara verificarmos a validade de um argumento categrico procedemos como segue:1.Transferimos para o diagrama, formado por trs crculos, as informaes das premissas, iniciando pelos enunciados universais;2.Verificamos se informao dada na concluso esta a representada sem nenhuma condio e de modo nico.3.Se isto ocorre ento o argumento vlido.Vejamos os seguintes exemplos:

Exemplo I.

(1) Todos os cientistas so estudiosos.(2) Alguns cientistas so inventores.(3) Alguns estudiosos so inventores.

A parte hachurada corresponde ao enunciado (1), vazia de elementos; a parte assinalada com X corresponde ao enunciado (2). Dessa forma, as informaes das premissas forem transferidas para o diagrama e a concluso (3) est representada. Portanto o argumento vlido.

Exemplo II.

Todos os brasileiros so felizes.Todos os paulistas so brasileiros.Todos os paulistas so felizes.

Vemos que o argumento vlido pelo diagrama acima.

Exemplo III.

(1) Nenhum estudante velho .(2) Alguns jovens no so estudantes.(3)Alguns velhos no so jovens.

A premissa (1) est representada na regio hachurada e a premissa (2) est marcada com X sobre a linha pois a informao correspondente pode estar presente em duas regies e no temos informao para saber especificamente em qual delas. Desse modo o argumento no vlido pois a concluso no est representada com absoluta certeza.

A validade de um argumento no depende do contedo dos enunciados e sim da sua forma e da relao entre as premissas e a concluso.

RVORES DE REFUTAO

GENERALIZAO PARA O CLCULO DE PREDICADOS DE 1a ORDEM.

No Clculo Proposicional mostramos como as tabelas verdade, as demonstraes e as rvores de refutao podem ser usadas para a verificao da validade de argumentos e de tautologias. Verificaremos no que segue como as rvores de refutao podem ser generalizadas para o Clculo de Predicados de 1a Ordem.

Como anteriormente, as rvores de refutao vo nos permitir verificar a validade de argumentos em um nmero finito de passos. No entanto, esta tcnica no Clculo de Predicados pode no nos fornecer nenhuma resposta em alguns casos como veremos adiante.

A generalizao das rvores de refutao para o Clculo de Predicados de 1a Ordem manter todas as regras anteriormente dadas para o Clculo Proposicional e novas regras sero estipuladas para as frmulas contendo os quantificadores Universal () e Existencial (). Teremos ento, alm das dez regras dadas no clculo Proposicional, as seguintes novas regras :

11. Regra da Negao do Quantificador Universal (): Uma frmula do tipo (x) gera uma linha na qual escrevemos a frmula (x). Procedemos assim em todos os ramos abertos aos quais a frmula (x) pertence.

12. Regra da Negao do Quantificador Existencial() : Uma frmula do tipo (x) gera uma linha na qual escrevemos a frmula (x). Procedemos assim em todos os ramos abertos aos quais a frmula (x) pertence.

13. Regra do Quantificador Existencial ( ) : Uma frmula do tipo (x)(x) gera uma linha na qual escrevemos a frmula (c) onde c uma nova constante que no ocorre em qualquer ramo da rvore e substituir as ocorrncias da varivel x, do quantificador, na frmula . Procedemos assim em todos os ramos abertos aos quais a frmula (x)(x) pertence.

Justificativa: A frmula (x)(x) significa que existe pelo menos um objeto do Universo que tem a propriedade e este ser identificado, sempre, por uma "nova" constante ou seja, uma constante que no ocorre na rvore.

14. Regra do Quantificador Universal () : Uma frmula do tipo (x)(x) gera uma linha na qual escrevemos a frmula (c) onde c qualquer constante que j ocorre em qualquer ramo da rvore e substituir as ocorrncias da varivel x, do quantificador, na frmula . Procedemos assim em todos os ramos abertos aos quais a frmula (x)(x) pertence.

Justificativa: A frmula (x)(x) significa que todos os objetos do universo tem a propriedade . Sendo assim, a regra deve ser aplicada a todas as constantes presentes na rvore e eventualmente para aquelas que surgirem durante a "construo" da rvore como observamos abaixo.

OBSERVAES IMPORTANTES:

1. Como sabemos, as frmulas para as quais so aplicadas as regras, sempre sero "marcadas" (). No entanto, para a regra () do quantificador universal isto no ser obedecido pois, se surgir uma nova constante na rvore por aplicao da regra (), para esta constante dever ser aplicada a regra () em todas as frmulas do tipo (x)(x) da rvore.

2.Somente se nenhuma constante ocorre em algum ramo que podemos introduzir uma nova constante para usar em possveis aplicaes da regra () ao longo do referido ramo.

Exemplo I.: Vamos verificar que a frmula (x)P(x) (x)P(x) vlida por rvore de refutao.

1. ((x)P(x) (x)P(x)) Premissa2. (x)P(x) 1. ()3. (x)P(x) 1. ()4. (x)P(x) 3. ()5. P(a) 2. () (obs.2 acima)6. P(a) 4. ()7. X 5. e 6.

Exemplo II. Verifique a validade do argumento categrico :

Todos os cientistas so estudiosos. - (x)(C(x) E(x))Alguns cientistas so inventores. - (x)(C(x) I(x))Alguns estudiosos so inventores. - (x)(E(x) I(x))

1. (x)(C(x) E(x)) Premissa2. (x)(C(x) I(x)) Premissa3. (x)(E(x) I(x)) Premissa Adicional4. (x) (E(x) I(x)) 3.()5. (C(a) I(a)) 2. () : a nova constante6. (C(a) E(a)) 1.() : a constante que j ocorre7. (E(a) I(a)) 4. () : a constante que j ocorre8. C(a) 5. ()9. I(a) 5. () / \10. C(a) E(a) 6.() / \11. X (10,8) E(a) I(a) 7.()12. X (1,10) X(11,9)

O argumento vlido pois todos os ramos foram fechados.

Exemplo III. Verifique a validade do argumento categrico :

Nenhum estudante velho . (x)(E(x) V(x))Alguns jovens no so estudantes (x)(J(x) E(x))Alguns velhos no so jovens. (x)(V(x) J(x))

1. (x)(E(x) V(x)) Premissa2. (x)(J(x) E(x))Premissa3. (x)(V(x) J(x)) Premissa Adicional4. (x) (V(x) J(x)) 3. ()5. (J(a) E(a)) 2. () : a nova constante.6. (E(a) V(a)) 1. () : a constante que j existe.7. (V(a) J(a))4. () : a constante que j existe8. J(a) 5. ()9. E(a) 5.() / \10. E(a) V(a) 6.() / \ / \11. V(a) J(a) V(a) J(a) 7.()12. / \ / \

O argumento no vlido pois a rvore terminou e temos ramos abertos.

Exemplo IV. (x)(y)P(x,y) , P(a,a)

1. (x)(y)P(x,y) Premissa2. P(a,a) Premissa adicional.3. (y)P(a,y) 1. () : a constante que j existe.4. P(a,b) 3. () : b nova constante.5. (y)P(b,y) 1. () : b constante que j existe.6. P(b.c) 5. () : c nova constante.

Como podemos observar a rvore nunca terminar; infinita. Vamos assumir que o argumento no vlido.

Na verdade no existe um mtodo efetivo que nos permita decidir sempre, e para qualquer argumento do Clculo de Predicados, se tal argumento vlido ou no vlido. Este resultado mostra que o Clculo de Predicados indecidvel. A indecidibilidade do Clculo de Predicados pode ser provada e conhecida como "Tese de Church" . H muitos livros de lgica que abordam este assunto.

Quando verificamos a validade de um argumento estamos verificando se, no caso das premissas serem verdadeiras elas inferem uma determinada concluso. Isto possvel ser feito por vrios mtodos no Clculo Proposicional os quais no todos se generalizam para o Clculo de Predicados como verificamos acima.

DEFINIES:Para estudarmos o Clculo de Predicados sobre outros aspectos algumas definies so importantes e as especificamos abaixo:

OCORRNCIAS LIVRE E LIGADA DE UMA VARIVEL:Uma ocorrncia de uma varivel x numa frmula ligada se x uma varivel de um quantificador na frmula ou x est no escopo de um quantificador (x) ou (x) na frmula. Caso contrrio a ocorrncia de x livre.

VARIVEL LIGADA (LIVRE):Se a ocorrncia de x ligada (livre) numa frmula, dizemos que x varivel ligada (livre) na frmula. Assim uma varivel pode ser livre ou ligada numa mesma frmula.

Exemplo:Na frmula (y)((x)R(y,b,t) (z) P(x,a)) temos cinco variveis que esto numeradas onde: 1 2 3 4 5

1,2,3,4 so ligadas e 5 livre. Vemos que x ocorre livre e ligada na mesma frmula.

SENTENA:Uma frmula em que no h ocorrncias livres de variveis chamamos de sentena.

TERMO LIVRE PARA UMA VARIVEL: Um termo t livre para a varivel y na frmula se, quando se substitui as ocorrncias livres de y por t, as ocorrncias de t em assim obtidas ocorrem livres.

Exemplos:

1. x livre para y em P(y).2. x no livre para y em (x)P(y).3. x livre para x em qualquer frmula.4. qualquer termo livre para x numa frmula se em no h ocorrncia livre de x.

BIBLIOGRAFIA BSICAI. FUNDAMENTOS MATEMTICOS PARA CINCIA DA COMPUTAO Judith L.Gersting - LTC(Livros Tcnicos e Cientficos) - 1995

II. INTRODUCTION TO MATHEMATICAL LOGIC-E. Mendelson -Wadsworth & Brooks/ Cole Mathematics Series - 1987

III. THE LANGUAGE OF FIRST-ORDER LOGIC Jon Barwise and John Etchemendy CSLI Stanford - 1992

BIBLIOGRAFIA COMPLEMENTAR1. NOES DE LGICA MATEMTICA - Abar, C. A . A. P. www.pucsp.br/~logica (roteiro terico)e www.pucsp.br/~abarcaap (exerccios)

2. LGEBRA BOOLEANA E CIRCUITOS DE CHAVEAMENTO E. Mendelson - McGraw Hill - 1977

3. INICIAO LGICA MATEMTICA - E. de Alencar Filho -E.Nobel -1984

4. INTRODUO LGICA MATEMTICA - B.Castrucci - GEEM -1982

5. INTRODUCTION TO METAMATHEMATICS - S.C.Kleene - van Nostrand - 1952

6. LGICA - John Nolt / Dennis Rohatyn - Schaum/McGraw Hill - 1991

7. LGICA - O CLCULO DE PREDICADOS - L.Hegenberg - EDUSP - 1973

8. LGICA - O CLCULO SENTENCIAL - L.Hegenberg - Herder/EDUSP - 1973

9. LGICA DINMICA - T. Barreiro de Nudler -Kapelusz Argentina - 1994

10. LGICA E LGEBRA DE BOOLE - J. Daghlian - Atlas - 1986

11. LGICA MATEMTICA- H. Cyrino e F. Arantes - Papirus 1984

12. A FIRST COURSE IN FUZZY LOGIC Hung T. Nguyen and Elbert A. Walker CRC Press 1997

13. FUZZY LOGIC Daniel Mcneill and Paul Freiberger Touchstone - 1993

14. INTRODUO LGICA - Cezar A. Mortari - Ed. Unesp - 2001

15. INTRODUO LGICA E APLICAES- Abe,J.M. e outros - Ed. Pliade - 1999

16. DISCRETE MATHEMATICS AND ITS APPLICATIONS - Keneth H. Rosen - WCB McGraw-Hill -1999

17. LGICA PARA CINCIA DA COMPUTAO - Joo Nunes de Souza - Ed. Campus - 2002

Profa. Dra. Celina A. A. P. AbarDepto. de Matemtica - PUCSP-2004logica@pucsp.brCaptulo 2 A FalciaDefinio

Uma falcia uma espcie de mentira, um argumento logicamente inconsistente, invlido, ou que falhe de outro modo no suporte eficaz do que pretende provar. Argumentos que se destinam persuaso podem parecer convincentes para grande parte do pblico apesar de conterem falcias, mas no deixam de ser falsos por causa disso. Reconhecer as falcias por vezes difcil.

importante conhecer os tipos de falcia para evitar armadilhas lgicas na prpria argumentao e para analisar a argumentao alheia.

Tipos e Exemplos de falcias(Alguns dos nomes usados esto em latim, com a traduo ao lado.) Argumentum ad antiquitatem (Argumento de antiguidade ou tradio):Afirmar que algo verdadeiro ou bom porque antigo ou "sempre foi assim".

Argumentum ad hominem (Ataque ao argumentador):Em vez de o argumentador provar a falsidade do enunciado, ele ataca a pessoa que fez o enunciado.

Ex: "A afirmao de Joozinho falsa, pois ele um sujeito mal-educado".

Argumentum ad ignorantiam (Argumento da Ignorncia):Ocorre quando algo considerado verdadeiro simplesmente porque no foi provado que falso (ou provar que algo falso por no haver provas de que seja verdade). Note que diferente do princpio cientfico de se considerar falso at que seja provado que verdadeiro.

Ex: "Joozinho diz a verdade, pois ningum pode provar o contrrio."

Non sequitur (No segue):

Tipo de falcia na qual a concluso no segue das premissas.

Ex: " bom acabar com a pobreza neste pas; bom eliminar a corrupo neste pas; Portanto, vamos votar no Joozinho para presidente!"

Argumentum ad Baculum (Apelo Fora):Utilizao de algum tipo de privilgio, fora, poder ou ameaa para impor a concluso.

Ex: "Acredite em Deus, seno queimar eternamente no Inferno."

Argumentum ad populum (Apelo ao Povo): a tentativa de ganhar a causa por apelar a uma grande quantidade de pessoas.

Ex: "A maioria das pessoas acredita em aliengenas, portanto eles existem."

Argumentum ad Verecundiam (Apelo autoridade):Argumentao baseada no apelo a alguma autoridade reconhecida para comprovar a premissa .

Ex: "Se Aristteles disse isto, verdade."

Dicto Simpliciter' (Regra geral):Ocorre quando uma regra geral aplicada a um caso particular onde a regra no deveria ser aplicada.

Ex: "Se voc matou algum, deve ir para a cadeia." (no se aplica a certos casos de profissionais de segurana)

Generalizao Apressada (Falsa induo): o oposto do Dicto Simpliciter. Ocorre quando uma regra especfica atribuda ao caso genrico.

Ex: "Aquele homossexual afeminado. Logo, todos os homossexuais so afeminados."

Falcia de Composio (Tomar o todo pela parte): o fato de concluir que uma propriedade das partes deve ser aplicada ao todo.

Ex: "Este caminho composto apenas por componentes leves, logo ele leve tambm."

Falcia da Diviso (Tomar a parte pelo todo):Oposto da falcia de composio. Assume que uma propriedade do todo aplicada a cada parte.

Ex: "Voc deve ser rico, pois estuda em um colgio de ricos."

Falcia do homem de palha:Consiste em criar idias reprovveis ou fracas, atribuindo-as posio oposta.

Ex: "Meu adversrio, por ser de um partido de esquerda, a favor do comunismo radical, e quer retirar todas as suas posses, alm de ocupar as suas casas com pessoas que voc no conhece."

Cum hoc ergo propter hoc: (falsa causa)

Afirma que apenas porque dois eventos ocorreram juntos eles esto relacionados.

Ex: "O Guarani vai ganhar o jogo de hoje porque hoje quinta-feira e at agora ele ganhou em todas as quintas-feiras em que jogou."

Post hoc ergo propter hoc:Consiste em dizer que, pelo simples fato de um evento ter ocorrido logo aps o outro, eles tm uma relao de causa e efeito.

Ex: "O Japo rendeu-se logo aps a utilizao das bombas atmicas por parte dos EUA. Portanto, a paz foi alcanada devido utilizao das armas nucleares."

Petitio Principii:Ocorre quando as premissas so to questionveis quanto a concluso alcanada.

Ex: "Scrates tentou corromper a juventude da Grcia, logo foi justo conden-lo morte."

Circulus in Demonstrando:Ocorre quando a