ChristianQ.Pinedoii Fundamentos da MatemticaA minha esposa: KarynSiebertA meus lhos: Milagros,Andr,Matheus,NykolaseKevyn.iiiiv Fundamentos da MatemticaTtulo do originalFundamentos da MatemticaPrimeira Edio, janeiro de 2008Direitos exclusivos para lngua portuguesa:GEPEMUFT - CAMPUS DE ARAGUANA519.5Pinedo. Christian Quintana, 1954 -FundamentosdaMatemtica/ChristianJosQuintanaPinedo: Uni-versidadeFederaldoTocantins. CampusdeAraguana, CursodeCincias-Habilitao plena em Matemtica, 2007.250 p. il. 297mmI. Lgica matemtica. Christian Q. Pinedo. II. Srie. III. TtuloCDD 519.5 ed. CDUAraguana - TO - 2007SUMRIONotaes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xPrefcio. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi1 LGICA MATEMTICA 11.1 EVOLUO DA LGICA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.1 Introduo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.2 Evoluo da lgica.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 UMA CLASSIFICAO DA LGICA . . . . . . . . . . . . . . . . . . . . . . . . 41.2.1 Lgica Indutiva. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2.2 Lgica Dedutiva. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2.3 O que a lgica no .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2.4 O que a lgica matemtica? . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 ENUNCIADOS. PROPOSIES. . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3.1 Noo de raciocnio. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.2 Noo de verdade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3.3 Enunciados abertos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3.4 Composio de proposies. . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3.5 Conectivos lgicos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.3.6 Argumento: Indutivo. Dedutivo. . . . . . . . . . . . . . . . . . . . . . . . 161.3.7 Tabela-verdade de uma proposio composta. . . . . . . . . . . . . . . . . 171.3.8 Construo de umatabela verdade. . . . . . . . . . . . . . . . . . . . . 17Exerccios 1-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.4 TAUTOLOGIA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271.4.1 Tautologias elementares. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291.4.2 Implicao lgica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311.4.3 Equivalncia lgica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33Exerccios 1-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351.5 LGEBRA DE PROPOSIES . . . . . . . . . . . . . . . . . . . . . . . . . . . 391.5.1 Propriedades da conjuno. . . . . . . . . . . . . . . . . . . . . . . . . . . 391.5.2 Propriedades da disjuno. . . . . . . . . . . . . . . . . . . . . . . . . . . 411.5.3 Propriedades da disjuno e conjuno. . . . . . . . . . . . . . . . . . . . 421.5.4 Mtodo dedutivo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44vvi Fundamentos da Matemtica1.5.5 Reduo do nmero de conectivos. . . . . . . . . . . . . . . . . . . . . . . 451.5.6 Princpio de dualidade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49Exerccios 1-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51Miscelnea 1-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552 TEORIA DA DEMONSTRAO 592.1 ARGUMENTO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602.1.1 Argumento: Dedutivo. Indutivo. . . . . . . . . . . . . . . . . . . . . . . . 602.1.2 Premissas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612.1.3 Inferncia.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622.1.4 Concluso. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622.1.5 A Implicao em detalhes. . . . . . . . . . . . . . . . . . . . . . . . . . . . 632.1.6 Validade de um argumento. . . . . . . . . . . . . . . . . . . . . . . . . . . 642.1.7 Condicional associada a um argumento. . . . . . . . . . . . . . . . . . . . 672.1.8 Reconhecendo Argumentos. . . . . . . . . . . . . . . . . . . . . . . . . . . 672.1.9 Argumentos consistentes fundamentais. . . . . . . . . . . . . . . . . . . . 682.2 INFERNCIA LGICA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 692.2.1 Regras de inferncia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 692.2.2 Principais regras de inferncia lgica.. . . . . . . . . . . . . . . . . . . . . 702.2.3 Vericao com o uso de tabela-verdade. . . . . . . . . . . . . . . . . . . . 742.2.4 Vericao sem o uso de tabela-verdade. . . . . . . . . . . . . . . . . . . . 75Exerccios 2-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772.3 DEMONSTRAO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 812.3.1 Demonstraes diretas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 822.3.2 Demonstraes indiretas. . . . . . . . . . . . . . . . . . . . . . . . . . . . 852.4 FUNES PROPOSICIONAIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 992.4.1 Funo proposicional. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 992.4.2 Raiz de uma funo proposicional. . . . . . . . . . . . . . . . . . . . . . . 992.5 QUANTIFICADORES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1002.5.1 Negao de quanticadores. . . . . . . . . . . . . . . . . . . . . . . . . . . 1022.5.2 Ambigidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104Exerccios 2-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105Miscelnea 2-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1093 CONJUNTOS 1113.1 ESTUDO AXIOMTICO DA TEORIA DE CONJUNTOS . . . . . . . . . . . . 1123.1.1 Conceitos primitivos.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1153.1.2 Axioma de extenso. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1193.1.3 Axioma de especicao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1203.1.4 Denies de classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1203.1.5 Conjunto Innito. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1213.1.6 Classe: Vazia. Universal . . . . . . . . . . . . . . . . . . . . . . . . . . . 122Christian Jos Quintana Pinedo vii3.1.7 Axioma do par no ordenado. . . . . . . . . . . . . . . . . . . . . . . . . . 1233.1.8 Incluso de conjuntos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1243.1.9 Axioma das potncias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1263.1.10 Conjunto: Potncia. Disjunto. . . . . . . . . . . . . . . . . . . . . . . . . . 1273.1.11 Diagramas: De Venn-Euler. Linear. . . . . . . . . . . . . . . . . . . . . . . 1283.1.12 Complemento de um conjunto. . . . . . . . . . . . . . . . . . . . . . . . . 129Exerccios 3-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1313.2 OPERAES COM CONJUNTOS . . . . . . . . . . . . . . . . . . . . . . . . . 1353.2.1 Unio de conjuntos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1353.2.2 Interseo de conjuntos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1373.2.3 Diferena de conjuntos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1403.2.4 Diferena simtrica de conjuntos. . . . . . . . . . . . . . . . . . . . . . . . 1423.3 LGEBRA DE CONJUNTOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1433.3.1 Leis da lgebra de conjuntos. . . . . . . . . . . . . . . . . . . . . . . . . . 1433.3.2 Princpio de dualidade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1443.3.3 Famlia de conjuntos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1453.3.4 Axioma das unies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1453.3.5 Operaes generalizadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1473.3.6 Axioma do conjunto vazio. . . . . . . . . . . . . . . . . . . . . . . . . . . . 149Exerccios 3-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1514 RELAES 1554.1 OUTRAS CLASSES DE CONJUNTOS . . . . . . . . . . . . . . . . . . . . . . . 1554.1.1 Propriedade denida sobre um conjunto. . . . . . . . . . . . . . . . . . . . 1564.1.2 Quanticadores. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1574.2 CONJUNTO PRODUTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1584.2.1 Par ordenado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1584.2.2 Produto cartesiano. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1594.2.3 Diagonal de um produto cartesiano. . . . . . . . . . . . . . . . . . . . . . 1614.2.4 Relaes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1614.2.5 Domnio e Imagem de uma relao. . . . . . . . . . . . . . . . . . . . . . . 1624.2.6 Diagramas de coordenadas. . . . . . . . . . . . . . . . . . . . . . . . . . . 1634.2.7 Grco de uma relao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1644.3 TIPOS DE RELAES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1644.3.1 Relao binria. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1644.3.2 Relao reexiva. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1654.3.3 Relao simtrica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1654.3.4 Relao anti-simtrica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1664.3.5 Relao transitiva. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1674.3.6 Relao de equivalncia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1674.3.7 Relao inversa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169Exerccios 4-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171viii Fundamentos da Matemtica4.4 CLASSES DE EQUIVALNCIA . . . . . . . . . . . . . . . . . . . . . . . . . . . 1754.4.1 Conjunto quociente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1754.4.2 Partio de um conjunto. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1764.5 APLICAO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1774.5.1 Domnio e Imagem de uma aplicao. . . . . . . . . . . . . . . . . . . . . 1794.5.2 Axioma de substituio. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1794.5.3 Grco de uma aplicao. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1814.5.4 Denio formal de aplicao. . . . . . . . . . . . . . . . . . . . . . . . . . 1824.5.5 Aplicao biunvoca, sobrejetiva e bijetiva. . . . . . . . . . . . . . . . . . . 1824.5.6 Composio de aplicaes. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1834.5.7 Imagem inversa de uma aplicao. . . . . . . . . . . . . . . . . . . . . . . 1854.5.8 Aplicao inversa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1854.6 CARDINALIDADE DE UM CONJUNTO. . . . . . . . . . . . . . . . . . . . . . 1874.6.1 Conjuntos enumerveis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1884.6.2 Paradoxo de Cantor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190Exerccios 4-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191Miscelnea 4-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1955 NMEROS NATURAIS 1975.1 CONJUNTO INDUTIVO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1985.1.1 Axioma de Innitude. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1995.2 NMEROS NATURAIS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2005.2.1 Induo matemtica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2025.2.2 Adio de nmeros naturais. . . . . . . . . . . . . . . . . . . . . . . . . . . 2035.2.3 Relao de ordem em N . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2055.2.4 Multiplicao de nmeros naturais. . . . . . . . . . . . . . . . . . . . . . . 2085.2.5 Potncia inteira de um nmero natural. . . . . . . . . . . . . . . . . . . . 211Exerccios 5-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2135.3 PROPRIEDADES ADICIONAIS EM N . . . . . . . . . . . . . . . . . . . . . . . 2155.3.1 Multiplicidade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2155.3.2 Divisibilidade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2155.3.3 Relao entre om.m.c. em.d.c.. . . . . . . . . . . . . . . . . . . . . . . . 2215.3.4 Propriedades adicionais de divisibilidade. . . . . . . . . . . . . . . . . . . 221Exerccios 5-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227Miscelnea 5-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2306 OPERAES BINRIAS 2336.1 RELAO DE ORDEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2346.1.1 Relao de ordem parcial. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2346.1.2 Relao de ordem total. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2356.2 LIMITES: Superior. Inferior. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2366.2.1 Supremo. nmo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236Christian Jos Quintana Pinedo ix6.2.2 Elementos: Maximal. Minimal. . . . . . . . . . . . . . . . . . . . . . . . . 2376.3 LEIS DE COMPOSIO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2386.3.1 Lei de composio interna. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2386.3.2 Isomorsmo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2396.3.3 Lei de composio externa. . . . . . . . . . . . . . . . . . . . . . . . . . . 2406.4 OPERAES BINRIAS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2416.4.1 Operao binria univocamente denida. . . . . . . . . . . . . . . . . . . . 2426.4.2 Sistema matemtico. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2426.4.3 Classicao dos sistemas matemticos. . . . . . . . . . . . . . . . . . . . 243Exerccios 6-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246ndice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250x Fundamentos da MatemticaNOTAESSeo negao 1.3.5 conjuno 1.3.5 disjuno inclusiva 1.3.5 disjuno exclusiva 1.3.5 condicional 1.3.5 bicondicional. 1.3.5p1, p2, , pn q argumento de premissasp1, p2, , pn e concluso q 2.1.4 quanticador universal 2.5 quanticador existencial 2.5N conjunto dos nmeros inteiros 3.1.1Z conjunto dos nmeros inteiros 3.1.1 conjunto dos nmeros racionais 3.1.11 conjunto dos nmeros reais 3.1.1C conjunto dos nmeros complexos 3.1.1 classe vazia 3.1.6U classe universal 3.1.6 incluso de conjuntos 3.1 incluso prpria de conjuntos 3.1T(A) conjunto potncia deA 3.4(UA complemento deA em U 3.26 unio de conjuntos 3.6 interseo de conjuntos 3.7 diferena simtrica de conjuntos 3.2.4AB produto cartesiano deA comB 4.21 : A B aplicao 1 deA emB 4.17m [ n m dividen 5.3.2m [ n m no divide an 5.3.2A B A isomorfo comB 6.3.2PREFCIOConsiderando que a matemtica uma cincia formal no emprica, os fatores que incidemno problema do conhecimento para o aprendizado da matemtica muito complexo, este temana verdade um dos grandes desaos para os pesquisadores da didtica geral.Amaioriadosestudantesdetodososnveisdoensino, dizemqueaprendermatemticadifcil, no obstante poucas vezes busca-se uma explicao do porque no aprendem as cinciasexatas os alunos?Osalunosnoaprendemmatemtica, porquenosabemrelacionarconhecimentosqueseensinam na escola com os problemas que se apresentam na vida real. Alm disto, a maioria dosestudantes optaram por aprender matemtica pelo modo mecanicistaque o pior de todos osmtodos.Outro grave problema que o aprendizado no signicativo. Estas notas pretendem motivaraosestudantesparaque, comaajudadalgicamatemtica elesejacapazdeachar estesrelacionamentosentreos diferentesesquemas doaprendizado, edestemodotenhaumaboaestrutura cognitiva.Umainquietudebastantenaturalnoalunointeressadoemumcursodelgicamatemticaadeaprenderademonstrar. Pormdemoraementenderoqueumademonstraoemmatemtica,isto se deve ao fato que o aluno no tem claro o que demonstrar nesta cincia.Somente tem a preparao regular na manipulao mecnica de alguns conceitos matemticos;o estudante carece de esprito analtico.Confundeosdesenvolvimentosformalistas, mecanicistaseamemorizaocomoraciocniocorreto. Precisamente essa falta de esprito analtico o que provoca um rechao anlise deconceitos e mtodos bsicos da matemtica, como por exemplo, o mtodo da reduo ao absurdo,o conceito de limite e o principio da induo matemtica.Considero que se uma pessoa aprende lgica matemtica, saber relacionar estes conhecimen-tos, com as outras reas para deste modo criar conhecimento.Estaobrarepresentaoesforodesntesesnaseleodeumconjuntodenotasdeauladexixii Fundamentos da MatemticaFundamentos daMatemticaI deumCursodeLicenciaturaemMatemtica, sobaLgicaMatemtica eTeoriadeConjuntos teis quandoumestudantecomeaaestudar estacin-cia. Oobjetivodestetrabalhoorientarametodologiaparaqueoleitorpossaraciocinarmatematicamente e interpretar a soluo de sentenas matemticas.Cada captulo se inicia com os objetivos que se pretende alcanar; os exerccios apresentadosesto classicados de menor a maior diculdade.Avariedadedos problemas eexerccios propostos pretendetransmitir minhaexperinciaprossional durante muitos anos de exerccio como Consultor em Matemtica Pura e Aplicada,assim como professor de Ensino Superior, com atuao na graduao e ps-graduao da docnciauniversitria.Estas notas servem como pr-requisito ao estudo de uma disciplina de estruturas algbricas,onde os conceitos de grupos, anis e corpos so estudados desde um ponto de vista da teoria deconjuntos.Fico profundamente grato pela acolhida desde trabalho e pelas contribuies e sugestes dosleitores.Christian Quintana Pinedo.Pato Branco - PR, Janeiro de 2007Nasquestesmatemticasnosecompreendeaincertezanemadvida,assimcomo tambm no pode-se estabelecer distines entre verdades mdias e verdades degrau superior.David Hilbert1ACincia, pelocaminhodaexatido, stemdois olhos: AMatemticaeaLgica.De Morgan21OPh. Dr. DavidHilbert nasceuemKnigsberg(Prussia) em1862, foi matemticoexcepcionalmenteabrangente e talentoso, fez contribuies lgica matemtica, fsica-matemtica, teoria da relatividade, teoriacintica dos gases, equaes integrais, etc. Faleceu em Gttingen (Alemanha) em1943.2AugustusDeMorgannasceucego(deumolho)emMadrasem1806, erabastanteversadoemlosoaehistria da matemtica. Escreveu sobre lgebra,clculo diferencial,lgica e teoria das probabilidades. Morganfaleceu em Londres em1871Captulo 1LGICA MATEMTICAAristtelesAristteles nasceu em Estagira em 384 a.C. e faleceu em Calcis(Eubea), em 322a.C. Estudou com Plato durante vinte anos e lecionouna Academia que Plato fundou.Depoisdeviajarporvriospases, voltouaAtenas, ondeabriuumaescoladeFilosoa, quecompetiucomseriedadeeexitocomaAcademia de seu mestre.Esteve bastante ligado com Alexandre o Grande (356 323 a.C.),de quem havia sido conselheiro, razo pela qual, morte de este, teveque abandonar Atenas, onde no pode mais ingressar .Aristteles representa o ponto mximo da cincia e losoaclssica, as quais contribuiu como pensador excepcional e comopesquisadoraudaciosoesistemtico. da quepraticamentetodassuas obras esto relacionadas com a cincia da natureza, alm da lg-ica,dametafsica,datica,dapoltica,daretricaedapotica,algoassimcomoumaenciclopdiadosaber de sua poca.1.1 EVOLUO DA LGICA1.1.1 Introduo.Podemos pensar a lgica como o estudo do raciocnio correto. O raciocnio o processo deobterconclusesapartirdesuposiesoufatos. Oraciocniocorretooraciocnioondeasconcluses seguem-se necessria e inevitavelmente das suposies ou fatos.A lgica procura estudar as coisas da mente, e no as coisas reais. Por exemplo, quando dize-mos: arco-ris bonito, sol distante, praia suave so classicaes que damos s coisas. Aplicamoslgica na losoa, matemtica, computao, fsica entre outros.Nalosoaparadeterminarseumcertoraciocniovlidoouno, poisumafrasepodeterdiferentesinterpretaes, noobstantealgicapermitesaberosignicadocorreto. Nasmatemticas para demonstrar teoremas e inferir resultados corretos que podam ser aplicados naspesquisas. Na computao para determinar se um determinado programa correto ou no, nafsica para obter concluses de experimentos. Em geral a lgica aplicamos nas tarefas do dia-dia,12 Fundamentos da Matemticaqualquer trabalho que realizarmos tem um procedimento lgico.A lgica somente mais uma teoria do pensamento;Aristteles considerado o criador dalgica, porem o nome lgica veio bem depois.No incio ela no tinha um nome.Para Aristteles,a lgica seria um modo a ser usado para as pessoas poderem raciocinar com segurana (evitandoerrar).Observe um exemplo da lgica dedutiva de Aristteles:Todo planeta quadrado.A Terra um planeta.Logo, a Terra quadrada. lgica dedutiva pelo fato que ao comear com algumas informaes, pode-se chegar a umaconcluso (deduzir!); esta investigao chamada de Silogismo.Esta lgica no se preocupa com o fato de a Terra ser quadrada, mesmo que se saiba que ela redonda. Pouco importa, ela aceita a informao que lhe foi dada. Mas exige que o raciocnioesteja correto. Preocupa-se com a forma: A=B, ento, B=A. Ela no presta ateno aocontedo: Aou Bpodem ser planetas, burros, plantas, etc. Por isso, esta lgica formal (deforma) e dedutiva (de deduo).Anossalgicaformaldedutivafuncionaassim: apartirdeumaseqnciadeoraesver-dadeiraschegamosaumaconclusoverdadeira; algicasempreutilizaumalinguagemexata(smbolos, sinais). Isso simplica e facilita seu estudo.Aristteles tambm elaborou a argumentao lgica indutiva.A baleia, o homem e o cozinho so mamferos.A baleia, o homem e o cozinho mamam.Logo, os mamferos mamam.Ou seja, de enunciados singulares chegamos a um universal.Mais tarde, Bacon e Stuart Mill aprofundaram esses ensinamentos e dividiram a lgica emtrs reas:1. Formal: Aquela que acabamos de explicar.2. Transcendental: Estalgicaestudaascondiesquedobaseaonossoconhecimento.Kant explicou que o intelecto tende a colocar todo em ordem, cada tijolinho no lugar. Alis,cada pessoa j possui uma lgica natural ao interpretar e classicar o que ela vivencia.3. Matemtica: Oslsofosdesenvolveramalgicamatemticahpoucotempo(Frege,Peano, Russell e outros). Ela origina frmulas de outras frmulas, puro raciocinio. Soregras e mais regras inventadas, como jogos de cartas.Hegel, no entanto, achava que a lgica referia-se ao pensamento e realidade; disse que:todo o que racional real, e todo o que real racional .Christian Jos Quintana Pinedo 3A lgica uma cincia, uma arte, um jogo; todo se passa como em um tabuleiro de xadrez.Mas vejamos tambm um outro tipo de lgica, a que considera a verdade (o contedo). Elaconsidera o desconhecido, a dvida, a opinio, a certeza. chamada de lgica material. Ela no aceita o fato se algum diz que a Terra quadrada.Temos alguns conceitos nesta lgica:Ignorncia a falta do conhecimento.Dvida a indeciso entre uma armao e uma negao.Opinio uma opo que envolve a dvida.Certeza um rme apego verdade.A verdade pode gerar muita discusso e barulho. Anal, como podemos saber o que mesmoa verdade?Os cticos, por exemplo, acham que no podemos armar nada; pois todo incerto.J quem segue o dogmatismo considera que a razo humana pode conhecer a verdade. E hmuitas outras posies sobre a verdade: positivistas, idealistas e outras.O importante saber que a verdade varia conforme os muitos sistemas loscos. Isso podeser potico. Existem verdades e a lgica utiliza a que deseja utilizar. A lgica material defendea verdade na qual acredita de perigos como o sosma.Sosma um raciocnio errado com a aparncia de verdadeiro, tem a inteno de conduzirao erro; observe o raciocnio:Maria Alice bonita.Maria Clara bonita.Logo, todas as Marias so bonitas.Voc j imaginou o que seria se no existisse lgica nas coisas?J imaginou se nada zessesentido?Hoje, a lgica fundamental em nossa sociedade. Dizemos que ela est na informtica,no ensino, na matemtica, na medicina, etc.Logo, o resumo de todo isto, que podemos considerar como sendo vlida a seguinte denio.Denio 1.1. Lgica.Dene-selgicacomoacinciadaargumentao, prova, reexoouinferncia. Elalhepermitir analisar um argumento ou raciocnio e deliberar sobre sua veracidade. A lgica no umpressupostoparaaargumentao,claro;masconhecendo-a,mesmoquesupercialmente,torna-se mais fcil evidenciar argumentos invlidos.1.1.2 Evoluo da lgica.1.1.2.1 Perodo Aristotlico (390 a.C. a1.840 d.C.)A histria da lgica tem incio com o lsofo grego Aristteles de Estagira (384 322 a.C.)(hoje Estavo) na Macednia. Aristteles criou a cincia da lgica cuja essncia era a teoria dosilogismo(certa forma de argumento vlido). Seus escritos foram reunidos na obra denominada4 Fundamentos da MatemticaOrganon (InstrumentodaCincia). NaGrcia, distinguiram-seduasgrandesescolasdelgica, a:Peripatticaque derivava da escola fundada por Aristteles, e a;Esticafundada por Zeno (326 264 a.C.).A escola Estica foi desenvolvida por Crisipo (280 250 a.C.) a partir da escola Megriafundada por Euclides, (seguidor de Scrates). Segundo Kneale (O Desenvolvimento da lgica),houvedurantemuitosanoscertarivalidadeentreosPeripatticoseosMegrios, istotalveztenhaprejudicadoodesenvolvimentodalgica, emboranaverdadeasteoriasdestasescolasfossem complementares.Gottfried Wilhelm Leibniz (1646 1716) merece ser citado, apesar de seus trabalhos teremtido pouca inuncia nos 200 anos seguidos e s foram apreciados e conhecidos no sculo XIX .1.1.2.2 Perodo Booleano (1840 a1910)Inicia-se com George Boole (1815 1864) e Augustus de Morgam (1806 1871). Publicaramos fundamentos da chamada lgebradalgica,respectivamente com Mathematical AnalysisofLogic eFormal Logic. GotlobFrege(1848 1925)umgrandepassonodesenvolvimentoda lgica com a obra Begrisschriftde 1879. As idias de Frege s foram reconhecidas peloslgicos mais ou menos a partir de1905. devido a Frege o desenvolvimento da lgica que seseguiu. Giuseppe Peano (18581932) e sua escola com Burali Forti, Vacca, Pieri, Pdoa, Vailati,etc. Quase toda a simbologia da matemtica se deve a essa escola italiana.1.1.2.3 Perodo Atual (1910 )Com Bertrand Russell (18721970) e Alfred North Whitehead (1861-1947) se inicia o perodoatual da lgica, com a obra Principia Mathematica. David Hilbert (1862 1943) e sua escolaalem com Von Neuman, Bernays, Ackerman e outros. Kurt Gdel (1906-1978) e Alfred Tarski(1902 1983) com suas importantes contribuies. Surgem as lgicas no-clssicas: N.C.A. daCosta (Universidade de So Paulo) com as lgicas paraconsistentes, L. A. Zadeh (Universidadede Berkeley-USA) com a lgica fuzzye as contribuies dessas lgicas para a Informtica, nocampo da Inteligncia Articial com os Sistemas Especialistas.Hojeasespecialidadessemultiplicameaspesquisasemlgicaenglobammuitasreasdoconhecimento.1.2 UMA CLASSIFICAO DA LGICA1.2.1 Lgica Indutiva.til no estudo da teoria da probabilidade, no ser abordada.Christian Jos Quintana Pinedo 51.2.2 Lgica Dedutiva.Que pode ser dividida em :Lgica Clssica: Considerada como o ncleo da lgica dedutiva. o que chamamos hojede Clculodepredicadosdeprimeiraordem com ou sem igualdade e de alguns de seussubsistemas. Trsprincpios(entreoutros)regemalgicaclssica: Daidentidade. Dacontradio; e. Do terceiro excludo os quais sero abordados mais adiante.Lgicas Complementares da Clssica: Complementam de algum modo a lgica clssicaestendendo o seu domnio. Estas so: lgica modal, lgica dentica, lgica epistmica entreoutras.Lgicas No-clssicas: Assimcaracterizadas por desconsiderar algumoualgunsdosprincpios da lgica clssica. Sendo estas: lgicaparacompleta e lgicaintuicionista (des-consideram o princpio do terceiro excludo); lgica paraconsistente (desconsidera o princ-pio da contradio); lgica no-altica (desconsidera o terceiro excludo e o da contradio);lgicano-reexiva(desconsideraoprincpiodaidentidade); lgicaprobabilstica, lgicapolivalente, lgica fuzzy entre outras.1.2.3 O que a lgica no .Vale fazer alguns comentrios sobre o que a lgica no .Primeiro: A lgica no uma lei absoluta que governa o universo. Muitas pessoas, no passado,concluram que se algo era logicamente impossvel (dada a cincia da poca), ento seriasempre literalmente impossvel. Acreditava-se tambm que a geometria euclidiana era umalei universal; anal, era logicamente consistente. Mas sabemos que tais regras geomtricasno so universais.Segundo: A lgica no um conjunto de regras que governa o comportamento humano. Pessoaspodem possuir objetivos logicamente conitantes. Por exemplo:Pedro quer falar com o Coordenador do Curso de Matemtica.O Coordenador Carlos.Logo, Pedro quer falar com Carlos.Infelizmente, pode ser que Pedro tambm deseje, por outros motivos, evitar contato comCarlos, tornando seu objetivo conitante. Isso signica que a resposta lgica nem sempre praticvel.1.2.4 O que a lgica matemtica?Tem-se tentado caracterizar a matemtica ao longo dos tempos, quer quanto a seu contedo,ou a sua forma e mtodos; acontece que a matemtica constantemente est evoluindo com novasteorias, assim mais proveitoso caracterizar estes conhecimentos matemticos quanto naturezade seus contedos.6 Fundamentos da MatemticaNo inicio do sculo XIX tentou-se caracterizar as matemticas como uma cincia da quanti-dade, embora esta concepo ainda perdure na mente da maioria das pessoas esta errada. Como desenvolvimento de novas teorias como, por exemplo: Teorias algbricas ou de ordens; estru-turas topolgicas, a moderna teoria da medida, a teoria dos conjuntos, etc. Todas estas novasteorias foram se impondo de modo natural, de modo que a nes do sculo XIX muitas disciplinasmatemticas so denominadas pela idia de estrutura de tal modo que desde que N. Bourbaki1comeou a publicar seu tratado lments de Mathmatique em 1939, a matemtica concebidacomo a cincia das estruturas.Os lgicos prossionais preferem desenvolver e aplicar a lgica matemtica a deni-la, mas,quandoinstados, encaramsuaatividadecomorelativaessencialmenteaumouaoutrodosaspectos seguintes:Aspecto explicativo: Algicamatemticaumsosticadoinstrumentodaanliseeulte-riorformalizaodefragmentosdosdiscursoscoloquiaisdascincias, emparticularnamatemtica (competindo parcialmente com a lingstica geral).Aspecto calculativo: Algicamatemticaconsideradacomoinstrumentodoclculoformaldestinado a substituir a argumentao indutiva e formal que consiste na:a) Demonstrao de uma proposio q a partir de certas hipteses p ?b) No demonstrao de q a partir de p ?c) Indecibilidade do problema da demonstrabilidade de q a partir de p ?Os ramos da lgica matemtica, organizam-se pelo seus aspectos em cinco ramos com suasespecicaesprpriasinterligadosentresimasaber: i)Teoriadademonstrao; ii)Teoriados conjuntos; iii) Teoria dos modelos; iv) Teoria da computabilidade; v) Lgica matemticaintuicinista/construtivista.1.3 ENUNCIADOS. PROPOSIESTodos ns usamos a lgica no dia-dia, s vezes sem nos darmos conta disso.Exemplo 1.1.Seu pai lhe diz:SevoctirardezemFsicaeMatemtica, lhedarei umpresente. Vocsabeque no basta tirar dez apenas em Fsica ou apenas em Matemtica. Para ganhar opresente, necessrio tirar 10 nas duas disciplinas.Se por outro lado ele dissesse:SevoctirardezemFsicaouMatemtica, lhedareiumpresente; abastariatirar dez em uma das matrias.1NicolasBourbaki (1936 ): Seunomeestescritoemgrego, suanacionalidadefrancesaesuahistriamuito curiosa [9]. um dos matemticos mais inuentes do sculoXX, existem muitas lendas sobre eleChristian Jos Quintana Pinedo 7Esse foi um exemplo simples da utilizao da lgica. Muitos outros poderiam ser listados.O que os matemticos zeram foi dar um aspecto matemtico lgica, alm de aprimor-la.Mas a idia fundamental antiga.As, pessoas, emgeral, pretendemraciocinar agir logicamente, nodia-dia, nos estudos,falando de poltica, futebol, de seus projetos ou do futuro da humanidade.Noentanto, algicaquefundamentaosraciocnioseasaesraramenteexplicadaousubmetida a crticas. Ela incorporada de forma inconsciente a partir, sobretudo, do aprendizadoda lngua natural e parece to bem partilhado por todos que poucos se julguem carentes de lgicaou considerem necessrio estud-la.Por outrolado, muitofreqente ouvirmos dizer que estudar matemticadesenvolveoraciocnio lgico. Apesar de esta relao no ser totalmente certa, a percepo da estreita relaoentre a matemtica e lgica, entre a lgica e linguagem, entre a linguagem e o pensamento con-tribui bastante para esclarecer muitas razes pelas quais estudamos certos assuntos sobre todomatemtica.Na linguagem natural utilizamos frasesde vrios tipos:Declarativas:Fredy escritor.Todos os gatos so pardos.Existem estrelas maiores que o Sol.Imperativas:Segure rme!No faa isso.Procure a entrada.Interrogativas:Quando ser a prova de Fundamentos?Quantos peruanos trabalham na Coordenao de Matemtica?Exclamativas:Que loira bem gelada!Parabns a voc!No sero objeto de estudo as sentenas imperativas, interrogativas ou exclamativas.1.3.1 Noo de raciocnio.A noo de raciocnio est presente em todos os estudos da lgicaFreqentemente quando falamos de lgica, pensamos em razo. Segundo a denio de nossalinguagem, arazoafaculdadequetemoserhumanodeavaliar, julgareponderaridiasuniversais.8 Fundamentos da MatemticaEntendemos como raciocinar ao fato de utilizar da razo para conhecer, para julgar da relaodas coisas. Assim, raciocnio o ato ou efeito de raciocinar.Oraciocnioargi aspremissasqueinferemresultadosexatosecoincidentescomelas, epretende, no melhor dos casos, ser o resultado de um processo orgnico de issoque chamamoscrebro humano.1.3.2 Noo de verdade.O mtodo que usamos para saber se uma situao verdadeira o que chamamos de linguagemveritativo, a parte da linguagem clssico que utiliza os termos de verdade, falsidade, etc.Existe duvidas entre os mesmos especialistas, quais as regras que deve-se utilizar em nossaprpria linguagem. Por isso no deveremos desvalorizar ou negar o critrio que tem as pessoasem comum do conceito de verdade. Ao perguntar a uma pessoa o que verdade? com certezaser uma pergunta bastante difcil de responder, isto devido ao fato que o conceito de verdade uma tarefa de anlise losca e no de levantamento de dados.Para a verdade, no existe um critrio geral que a obtenha como aplicvel a todos os casos,porm que so sempre parciais e conveis.Estamos interessados somente na pergunta do verdadeiro aplicado a o que dizemos, e no aobjetos, pessoas, etc. Deste modo a verdade sim podemos deni-la e teorizar-la. No dependede conhecimentos necessrios (embora sim vice-versa)Denio 1.2. Enunciado.Um enunciado qualquer frase ou orao.Exemplo 1.2.a) A Lua um satlite da Terra.b) 3 + 2 = 1 + 4c) x + 3 = 5d) Scrates o mestre de Plato.e) 8 um nmero primo.f) O rio Paran.Aqui estamos utilizando o conceito de identidade,expresso pelo smbolo de igualdade (=);isto claro no exemplo b). Nos enunciados a),d) ee) o no predicativo como quandodizemos Scrates mortal, mas sim um idntica a . . ., podendo escrever na forma:a) A Lua = um satlite da Terra.d) Scrates = mestre de Plato.e) 8 = um nmero primo.1.3.2.1 Classicao da pergunta: O que verdade?1oQuais so os enunciados que so verdadeiros ou falsos?Aqui, os enunciados so os portadores da verdade.Christian Jos Quintana Pinedo 92oQue tm que acontecer para que um enunciado seja verdadeiro?Aqui se pede uma denio de um enunciado verdadeiro.3oComo temos certeza que o enunciado verdadeiro?Aqui se pergunta pelo conhecimento. Pergunta-se como averiguar se um enunciado ver-dadeiro e onde o critrio de verdade um processo.Emnossasinvestigaessobrealinguagemnatural, interessa-nosaquelaquealcanaumacompreensomaisclaradesuasestruturaslgicasetraduzi-lasposteriormenteparaumalin-guagem matemtica.Consideremosinicialmenteasfrasesdeclarativas, jqueelaspodemserclassicadascomoverdadeiras(v) ou falsas(f); estas sentencias na matemtica so chamadas de proposio.Denio 1.3. Proposio.Proposio todo enunciado que exprime um pensamento de sentido completo, isto , aquelepensamento que admite um, e somente um, dos valores: verdadeiro (v) ou falso (f).Conclui-se que, as proposies devem satisfazer os dois princpios fundamentais:1. Uma alternativa s pode ser verdadeira ou falsa.2. Uma alternativa no pode ser verdadeira e falsa.As proposies denotam-se com as letras minsculasp, q, r, s, t,, tambm chamadas devariveis proposicionaisExemplo 1.3.a) p : O nmero 2 menor que 3. (v)b) q : 3 < (v)c) r : 7 1 = 2 + 4 5 (f)d) s : A Terra uma estrela. (f)e) t : Existem prefeitos que so honestos. (v)Portanto, as proposies so sentenas declarativas armativas (expresso de uma linguagem)da qual tenha sentido armar que seja verdadeira ou que seja falsa.A lua quadrada. (f)A neve branca. (v)Matemtica uma cincia. (v)Denio 1.4. Axioma.Dene-se axioma, como uma proposio que se admite como verdadeira porque dela se podemdeduzir as proposies de uma teoria ou de um sistema lgico ou matemtico.10 Fundamentos da MatemticaA lgica matemtica adota como regras fundamentais do pensamento os dois seguintes ax-iomas.Axioma 1.1. Do terceiro excludo.Toda proposio, ou verdadeira ou falsa; isto , verica-se sempre um destes dois casos enunca um terceiro.Axioma 1.2. Da no contradio.Uma proposio no pode ser verdadeira e falsa ao mesmo tempo.Assim, a lgica matemtica bivalente.1.3.3 Enunciados abertos.Se, naproposiop: 5>4substitumosonmero5pelaletrax, temosqueaexpressox> 4, o qual chamado de enunciado aberto, pois, dependendo do valor numrico que assumea varivelx podemos atribuir valores de verdade (v) ou falsidade (f).Exemplo 1.4.So enunciados abertos.a) x primo de Jos.b) x < y +zc) x 7 = 8Observe que os enunciados abertos so de muita importncia na matemtica,pois quase atotalidade de enunciados matemticos (problemas) utilizam uma ou mais variveis.1.3.4 Composio de proposies.1.3.4.1 Proposio composta.Ao utilizarmos a linguagem, combinamos idias simples, ligamos proposies atravs de conec-tivosque permitem obter outras proposies.A composio de proposiesconsiste em, dadas uma ou duas proposies, obter uma novaproposio mediante o uso de palavras, denominadas conectivos lgicos.So conectivos lgicos as palavras e, no, ou, se, . . . ento, . . . se, e somente se,. . .Uma proposio simples, tambm chamada de proposio atmicae as proposies com-postas de proposio molecularOvalordeverdadedeumaproposiocompostadeterminadopelovalordeverdadedecadaumadasproposiessimplesedemodocomoelasestoligadas(peloconectivo-lgico)para formar a proposio composta.Osparnteses( )queservemparadenotaroalcance dosconectivos; sochamadosdesmbolos auxiliares.Christian Jos Quintana Pinedo 111.3.5 Conectivos lgicos.1.3.5.1 Negao. Jdissemosqueumaproposioppodeserverdadeiraoufalsa, nohavendooutrapossi-bilidade. Alfred Tarski2foi um dos maiores lgicos de todos os tempos, criador da teoria dosmodelos (moderna teoria semntica).A negao de uma proposiop escreve-se p e se l: nopou falso quep, ou no verdade quepe; outra proposio que nega se cumpra a proposiop.A negao de uma proposio, no arma que acontea o contrario, a Tabela(1.1) mostra ovalor verdade para a proposiop.p pv ff vTabela 1.1: Negao da proposiopExemplo 1.5.Suponha a proposiop: 12 um nmero mpar; logo a proposio p: No verdade que12 seja nmero mpar.Observe que p somente negap, e no arma o oposto de aquilo que armap.Exemplo 1.6.Suponha a proposio p: Lima a capital do Per (v). p: Lima no a capital do Per (f). p: No verdade que Lima a capital do Per (f).Exemplo 1.7.Seja a proposiop: Maria bonita, logo p: No verdade que Maria seja bonita.Aproposio pnoarmaqueMariasejafeia, poisdofatoserbonitaaofatoserfeiaexistem outras possibilidades:bonita feia. .outras possibilidadesDiscutir o seguinte exemplo:Exemplo 1.8. Paradoxo3da frase.Seja a proposio: p: Esta frase falsa.Se p (f), entop: No verdade que esta frase falsa. uma frase verdadeira.2Alfred Tarski (1902 1983), autor de um dos primeiros livros de introduo lgica moderna3Uma declarao essencialmente contraditria baseada em um pensamento vlido de suposies lgicas.12 Fundamentos da MatemticaSe p (v), ento p: No verdade que esta frase falsa, tambm uma frase verdadeira.Observao 1.1.a)Negar uma proposiop no apenas armar algo diferente do quep arma,ou algo comvalor lgico diferente. Por exemplo, a proposio.q : Lima a capital de Per (v), no a negao de p : Braslia a capital de Per (f).b)Sendo verdadeira uma proposiop, a sua negao falsa e vice-versa; como conseqncia,a negao da proposio p arma o mesmo quep, isto , a negao da negao dep logicamente equivalente ap. Escrevemos p p ( l-se; logicamente equivalente).A tabela-verdadeao lado, resume o armado.p p pv f vf v f1.3.5.2 Conjuno. Chama-se conjuno das proposiesp e q proposio representada porp q, cujo valorlgico verdadeiro (v) somente quando as duas proposiesp eq sejam ambas verdadeiras, e; falsa (f) nos demais casos.A notaop q se lp e q, e o valor lgico denido pela seguinte tabela-verdade.p q p qv v vv f ff v ff f fTabela 1.2: Conjuno dep e qA Tabela(1.2) prev todas as possibilidades para o valor lgico de uma proposio compostaa partir dos valores lgicos das componentes e dos conectivos lgicos, chamada tabela-verdadeda proposio composta. O conectivo lgico traduz a idia de simultaneamente.convenientediferenciarentreoe queusamosnadeterminaodaconjunop e qoe na utilizao da linguagem do dia-dia. O mesmo texto permitira diferenciar um do outro.Assim por exemplo quando se diz: Seja a proposiop e q entende-se claramente que o eest determinando sua funo lgica; no outro caso quando se diz: Sejam as proposiespe qfazemos uso do eno sentido da linguagem do dia-a-dia.Exemplo 1.9.a)Curitibaencontra-seemSoPaulo eSoPaulotemumapopulaopredominantementelatina. Esta proposio falsa (f), pois as duas proposies simples so falsas. Trata-se deuma proposio composta falsa (f), uma vez que a primeira proposio falsa (independentedo valor lgico da segunda proposio)Christian Jos Quintana Pinedo 13b)Platoeragrego e Pilatos romano. Estaproposio verdadeira(v), pois as duasproposies simples so verdadeiras.Exemplo 1.10.Consideremos p : 2 + 8 > 5 e q : 8 > 6 , ento, temos as quatro possibilidades:2 + 8 > 5 8 > 6esta proposio composta (v)2 + 8 > 5 8 6esta proposio composta (f)2 + 8 5 8 > 6esta proposio composta (f)2 + 8 5 8 6esta proposio composta (f).1.3.5.3 Disjuno inclusiva. Chama-se disjuno das proposiesp e q proposio compostap q, cujo valor lgico falso (f), quando ambas as proposiespe q sejam falsas; e, nos demais casos verdadeira (v).A notaop q se lp ouq e o valor lgico denido pela seguinte tabela-verdade:p q p qv v vv f vf v vf f fTabela 1.3: Disjuno inclusiva dep e qMostra-se na Tabela(1.3) todas as possibilidades de ocorrer na proposio compostap q.Exemplo 1.11.Se p: 4 + 7 = 11 e q : 15 3 = 12 ento temos as quatro possibilidades:4 + 7 = 11 15 3 = 12esta proposio composta (v)4 + 7 = 11 15 3 ,= 12esta proposio composta (v)4 + 7 ,= 11 15 3 = 12esta proposio composta v)4 + 7 ,= 11 15 3 ,= 12esta proposio composta (f)Discuta o seguinte exemplo:Exemplo 1.12. Paradoxo da existncia de Deus.Mostre que Deus existe.Demonstrao.Sejam as proposies: p :Deus existe; e q : esta frase falsa; logo p q :Deus existe ouesta frase falsaSuponhamos ao menos uma das proposies seja verdadeira, logo a frase p q verdadeira.Para o caso que simultaneamente pe q sejam falsas, ento a frase p q falsa. Comoq falso ento pela Tabela(1.3) segue que p q verdadeira.Portanto Deusexiste.14 Fundamentos da MatemticaObservao 1.2.Na linguagem do dia-a-dia, a palavraou tem dois sentidos:1op : Mrio motoristaou professor.2oq : Carlos gachoou paulista.Da proposiop podemos obter as proposies: Mrio motorista, assim como Mrio professor, podendo ser ambas verdadeiras ento temos que Mrio motorista e professor.Mas na proposioq, temos as proposies Carlos gacho, e a outra Carlos paulistasendo verdadeira somente uma de elas que exclua o valor verdade da outra; no possvel ocorrerCarlos gachoe paulistaNa proposio p, a disjuno inclusiva; e, na proposio q a disjuno exclusiva. O smbolo indica o conectivo lgico exclusivo e sua tabela-verdadeindica-se na Tabela(1.4).p q pqv v fv f vf v vf f fTabela 1.4: Disjuno exclusiva dep e q1.3.5.4 Condicional. Chama-se proposio condicional das proposies peq (nessa ordem) proposio compostap q, cujovalorlgicofalso(f), quandopsejaverdadeiroe qfalso, nosdemaiscasosaproposio verdadeira (v).p q p qv v vv f ff v vf f vTabela 1.5: Condicional dep e qA notaop q se l sep, entoq. Seu valor lgico denido pela tabela- verdade(1.5).Na proposiop q, a proposiop chamada de antecedente(hipteses) e a proposioqde conseqente(tese).Exemplo 1.13.Sejam as proposies p: 3 + 2 = 5 e q: 3 < 5, ento temos as quatro possibilidades:Se 3 + 2 = 5 3 < 5esta proposio composta (v)Se 3 + 2 = 5 3 5esta proposio composta (f)Se 3 + 2 ,= 5 3 < 5esta proposio composta (v)Se 3 + 2 ,= 5 3 5esta proposio composta (v)Christian Jos Quintana Pinedo 15As proposies condicionais so importantes na matemtica, e tem varias maneiras diferentesde enuncia-las, assim por exemplo,p q podemos entender como uma das seguintes formas: p implicaq. p condio suciente paraq Para quep necessrio queq. q condio necessria parap Sep, tambmq. q cada vez quep q sep. q sempre quep.Toda implicao est associada a outras trs proposies, elas so: a recproca, a inversa e acontra-recproca.Suponha temos a proposio composta: p q. Podemos obter outras proposies com-postas relacionadas comp e q, sendo estas de muita utilidade na teoria da demonstrao.Recproca: q p.Inversa: p q.Contra-recproca: q p.Exemplo 1.14.Escreva a recproca, a inversa e contra-recproca de cada uma das seguintes proposies:i)Se 7 7 = 0, ento 7 = 7.ii)Se a termina em zero, ento a mltiplo de 2.iii)Sex = y, entox +y par.Soluo.(i)Temos p : 7 7 = 0 e q : 7 = 7, a proposio da forma p q.Recproca: Se 7 = 7, ento 7 7 = 0. da forma: q pInversa: Se 7 7 ,= 0, ento 7 ,= 7. da forma: p qContra-recproca: Se 7 ,= 7, ento 7 7 ,= 0 da forma: q p.Soluo.(ii)Temos p : a termina em zero e q : a mltiplo de 2, a proposio da forma p q.Recproca: Se a mltiplo de 2, ento a termina em zero.Inversa: Se a no termina em zero, ento a no mltiplo de 2.Contra-recproca: Se a no mltiplo de 2, ento a no termina em zero.Soluo.(iii)16 Fundamentos da MatemticaTemos p : x = y e q : x +y par.Recproca: Sex +y par, entox = y.Inversa: Sex ,= y, entox +y no par.Contra-recproca: Sex +y no par, entox ,= y.1.3.5.5 Bicondicional. Chama-se proposio bicondicional das proposies p eq proposio composta p q, cujovalor lgico verdade (v) quandop eq so ambas verdadeiras ou ambas falsas; e, falsa (f) nosdemais casos.A notaop q se l: p se, e somente se4,q; o valor lgico denido pela seguinte tabela-verdade(Tabela(1.6):p q p qv v vv f ff v ff f vTabela 1.6: Bicondicional dep e qUma proposio bicondicional obtm-se por denio como a conjuno de uma condicionale sua recproca; isto p q equivalente a (p q q p).1.3.6 Argumento: Indutivo. Dedutivo.Nossoprincipal objetivoserainvestigaodavalidadedeargumentos. Argumentarapresentar uma proposio como sendo uma conseqncia de uma o mais proposies.Denio 1.5. Argumento.Chamamosdeargumentoaumconjuntodeproposiesoperadasporconectivoslgicos, asquais uma proposio a concluso e as demais so premissas5.Isto, umargumentoconstitudopelasproposiesp1, p2, , pnchamadaspremissas,nas quais nos baseamos segundo os conectivos lgicos para garantir uma proposioq chamadaconcluso.Os argumentos esto tradicionalmente divididos em dedutivose indutivos.Denio 1.6. Argumento dedutivo.Diz-se que um argumento dedutivo quando, sendo suas premissas verdadeiras, a concluso tambm verdadeira.Premissa:Premissa:Concluso:Todo homem mortal.Joo homem.Joo mortal.Esses argumentos sero objeto de estudo para a compreenso de teorias matemticas.4A frase se, e somente se devida a A. Tarski5Cada uma das proposies de um silogismo que serve de base concluso.Christian Jos Quintana Pinedo 17Denio 1.7. Argumento indutivo.Diz-se que um argumento indutivo quando, a verdade das premissas no basta para assegurara verdade da concluso.Premissa:Premissa:Concluso: comum aps a chuva car nublado.Est chovendo.Ficar nublado.As premissas ea concluso deumargumento,formuladas emuma linguagem estruturada,permitemqueoargumentopossaterumaanliselgicaapropriadaparaavericaodesuavalidade.1.3.7 Tabela-verdade de uma proposio composta.Dadas varias proposies p, q, r,podemos combina-las pelos, conectivos lgicos , , ,, e construir proposies compostas, tais como:P(p, q) : p (p q)Q(p, r) : (p r) rR(p, r, s) : (p s r) (s (p s))Observao 1.3.1oSe voc tiver n proposies simples, o nmero de linhas que resultam de todas as combinaesde verdade (v) e falsidade (f) 2n.Assim, casonumatabela-verdade estivermostrabalhandocomtrsproposiessimples,ento teramos nessa tabela-verdade23= 8 linhas.2oUma proposio composta, tambm chamada funo-verdade.3oSe voc tiver n proposies simples, ento existem 22nproposies compostasdiferentes.Por exemplo, dadas as proposiesp e q, ento podemos obter 222= 24= 16 proposiescompostas diferentes a saber:p q p q p q p q p p p p p p p q p q p q p q p q p q p p p p p p1.3.8 Construo de umatabela verdade.Suponha temosa construira tabela-verdadepara a proposioP(p, q): (p q),logoteremos a considerar o seguinte roteiro da Tabela(1.7):a)Forma-se em primeiro lugar, o par de colunas correspondentes s duas proposies simples pe q (coluna 1a);b)logo em seguida forma-se a coluna para q (coluna 2a);c)depois forma-se a coluna parap q (coluna 3a);18 Fundamentos da Matemticad)nalmente a coluna relativa aos valores lgicos da proposio composta P(p,q): (p q)(coluna 4a).p q q p q (p q)v v f v fv f v v ff v f f vf f v v f1a2a3a4aTabela 1.7:Tambm podemos considerar o seguinte roteiro (Tabela (1.8)):a)Formam-se as primeiras colunas correspondentes s duas proposies simplesp e q (coluna1a);b)em seguida direita, traa-se uma coluna para cada uma dessas proposies e para cada umdos conectivos que guram na proposio composta dada (colunas 2a,3ae 4a);c)logo, em certa ordem, completam-se essas colunas, escrevendo em cada uma delas os valoreslgicos correspondentes, no modo abaixo indicado (coluna 5a).p q (p q)v v f v v f vv f f v v v ff f v f f f vf f f f v v f1a5a2a4a3a2aTabela 1.8:Os valores lgicos da proposio composta dada encontram-se na coluna completada escritapor ltimo (5a).Exemplo 1.15.Construir tabela-verdade da proposio: P(p, q) : (p q) (q p).Soluo.Utilizando o roteiro sugerido temos:p q (p q) (q p)v v f v v v f f v v vv f v v f f v v f f vf v v f f v v v v f ff f v f f f v f f v f1a4a2a3a2a5a4a2a3a2aChristian Jos Quintana Pinedo 19Exemplo 1.16.Construir tabela-verdade da proposio: P(p, q) : (p q) ( p q).Soluo.Utilizando o roteiro sugerido temos:p q (p q) ( p q)v v f v fv f v v vf v f v vf f f v v1a2a1aProblema 1.3.1.Miguel,PedroeHumbertotmduasocupaescadaum,motorista,contrabandista,pintor,jardineiro, barbeiro e msico.Dados:1. O motorista ofendeu o msico rindo do seu cabelo comprido;2. o msico e o jardineiro s gostavam passear com Miguel;3. o pintor comprou do contrabandista um relgio da Sua;4. o motorista paquerava a irm do pintor;5. Pedro devia cinco mil reais ao jardineiro;6. Humberto venceu Pedro e ao pintor jogando xadrez;Que ocupao tem Miguel ?Soluo. melhor resolver considerando uma tabela com todos os dados de dupla entrada e descar-tando possibilidades de no ocorrer X, como mostramos a seguir.Motor. Msico Contra. Barbe. Jardine. PintorMiguel X X X Ok. X Ok.Pedro X Ok. Ok. X X XHumberto Ok. X X X Ok. XObservando o quadro conclumos que Miguel o barbeiro.Problema 1.3.2.Numdeterminadoprdioexistem4andares. Ocupadospor: umadvogado, umconstrutor,um contador e um dentista. H no prdio: um condicionador de ar, uma geladeira, um rdio e20 Fundamentos da Matemticaum televisor. Trabalha tambm o seguinte pessoal: um scio, um encarregado de relaes pblicas(atendente), uma secretria e um oce-boy. Chamam-se Alberto, Benedito, Camargo e David,mas aqui no esto relacionados na ordem de prosses acima citada. Sabendo-se que:O que ocupa a 1oandar tem um oce-boy;no 3oandar existe um rdio;o advogado e o construtor trabalham prximos;oconstrutornuncapassapeloandardodentista,masAlbertotemquepassarpeloandarde Benedito, quando vai falar com a secretria;David tem sua sala um andar depois do contador;asalaondetemasecretria, caacimadasaladeBeneditoeembaixodoquetemageladeira;o advogado possui um condicionador de ar;na sala onde existe o televisor, seu proprietrio tem um encarregado de relaes pblicas,que namora a secretria;o construtor trabalha no andar embaixo do contador;Quem quem?Soluo.Recomenda-separaasoluodeproblemasdestetipoumatabeladeduplaentradacomomostraremos a seguir.Aps da anlise com os dados do enunciado chegamos seguintes concluso:Andares Empregados Eletrnicos Prosso Nome1oOce-boy Cond. de ar Advogado Alberto2oEncarregado Tv Construtor Benedito3oSecretria Rdio Contador Camargo4oScio Geladeira Dentista DavidAssim temos de acordo com a tabela completada acima:Advogado de nome Alberto, tem um oce boy, um condicionado de ar e ocupa a primeirasala;Oconstrutortemumencarregadodasrelaespblicas, dispedeTv,ocupaasegundasala e seu nome Benedito;O contador tem uma secretria, um rdio, ocupa a terceira sala e seu nome Camargo;O dentista tem um scio, uma geladeira ocupa a quarta sala e chama-se David.Christian Jos Quintana Pinedo 21Problema 1.3.3.Apslanartrsdadossobreamesa,Rodrigosomouosnmerosdassuasfacessuperiorese encontrou o nmero 10. Em seguida, ele multiplicou os mesmos 3 nmeros e encontrou comoresultado 30. Qual o produto dos nmeros das faces inferiores desses dados?Observao: Num dado, a soma dos nmeros de 2 faces opostas sempre igual a 7.Soluo.Como o produto dos 3 nmeros das faces superiores igual a 30, estes 3 nmeros s podemser 1, 6 e 5 ou 2, 3 e 5, j que 30 = 235 e que os nmeros nas faces de um dado noso maiores que 6. Das 2 possibilidades que enunciamos apenas a que composta pelos nmeros2, 3e5 tem a soma dos 3 nmeros iguais a 10. Encontrado que os nmeros das faces superioresso 2,3 e 5, de imediato se chega aos nmeros das faces inferiores: 5,4 e 2, respectivamente.Assim, o produto procurado 5 4 2 = 40.Problema 1.3.4.Mrio mente as segundas, teras e quartas-feiras, e fala a verdade nos demais dias da semana.Paula mente apenas as quintas, sextas e aos sbados. Num certo dia, foram feitas as armaes:por Mrio, ontem foi meu dia de mentir;por Paula, ontem foi tambm meu dia de mentir.Qual o dia da semana em que foram feitas estas armaes?Soluo.Note que se Mrio e Paula fazem a mesma armao, ou ambos falam a verdade, ou ambosmentem, ou um deles fala a verdade enquanto o outro mente. Mas no h dia da semana em queambos mentem, o que nos leva a descartar esta hiptese.Para ambos falarem a verdade, o nico dia possvel de isso acontecer no domingo, j quenos outros dias da semana, um dos dois, ou Mrio ou Paula, mente.Restaentoqueumfalouaverdadeenquantoooutromentiu. Masseumdelesfalouaverdadequandodissequeontemfoi diadementir, entoessediaspodeserquinta-feiraoudomingo.Como j vimos que domingo um dia impossvel de ambas as armaes ocorrerem, o diada semana em que foram feitas estas armaes foi quinta-feira.Problema 1.3.5.A cada dois anos no perodo de 1858a1864 nasceu um compositor famoso. Claude Debussynasceu na Frana, Gustav Mahler nasceu na ustria, Giacomo Puccini nasceu na Itlia e RichardStrauss na Alemanha. Debussy no era o mais velho, Puccini era 2 anos mais velho que Mahler,Strauss era mais novo que Debussy. Descubra o ano no qual nasceu cada compositor.Soluo.Antes de tudo, vamos identicar as 3 armaes que o enunciado nos trouxe:i)Debussy no era o mais velho.ii)Puccini era 2 anos mais velho que Mahler.iii)Strauss era mais novo que Debussy.22 Fundamentos da MatemticaPor (ii). conclumos que Puccini nasceu e logo em seguida (2 anos depois) veio Mahler. ComoStrauss era mais novo que Debussy (iii) mas Debussy no era o mais velho (i), Debussy no podeternascidoantesdePuccini, poisnestecasoseriaomaisvelhodetodos. Dadoisto, anicaalternativa que h a seguinte: primeiro nasceu Puccini, em seguida Mahler, depois Debussy epor m Strauss.Problema 1.3.6. Malba Than.TrspessoasnumbarzeramumadespesaqueimportouemR$9, 00paracadauma,total-izandoR$27, 00. Todavia, cada uma deu ao garomR$10, 00. Por falta de troco, este devolveuR$5, 00. Destes, tiraram-se R$3.00, que lhe deram como gorjeta. Ento, como sobraram R$2, 00?Soluo.OsR$2, 00 correspondem ao abatimento feito pelo garom.Problema 1.3.7.Trsestudantes,Alberto,BernardoeCarlostempornamoradasaAna,BeatrizeClaudia,no necessariamente nessa ordem. Em uma festa que assistiram estas seis pessoas compraramrifas de preos diferentes cada uma. Cada pessoa comprou tantos boletos como reais gastou essamesma pessoa por rifa.Albertocomprou23rifasmaisqueBeatrizeBernardocomprou11maisqueAna. Cadahomem gastou 63 reais mais que sua namorada. Qual era o nome da namorada de cada um?Soluo.Suponha um homem compram boletos am reais cada um; logo ele gastoum2reais.De modo anlogo, suponha cada mulher compra n boletos a n reais cada um; logo ela gastoun2reais.Da relao m2n2= 63 segue que (m+n)(mn) = 63 e como 63 = 163 = 321 = 79,pode acontecer:m+n = 63 m+n = 21 m+n = 9mn = 1 mn = 3 mn = 7De onde obtemos trs pares de valores parame n: 32 e 31, 12 e 9 por ltimo 8 e 1.Como Alberto comprou 23 boletos mais que Beatriz, e Bernardo 11 mais que Ana, ento:Alberto = 32 Ana =1Bernardo = 12 Beatriz = 9Carlos = 8 Claudia = 31Portanto os casais so: Alberto casado com Claudia, Bernardo casado com Beatriz e Carloscasado com Ana.Christian Jos Quintana Pinedo 23Exerccios 1-11. Dasfrasesseguintes, assinalequaissoproposies, atribuindo-lhesovalorlgicocorre-spondente:1. Per e Brasil.2. Brasil foi campeo mundial de futebol em 1982.3. As diagonais de todo paralelogramo so de comprimentos iguais.4. O triplo de 6.5. Que horas so ?6. Todo quadrado um retngulo.7. (a +b)2= a2+b28. 2 < 59. As diagonais de alguns paralelogramos so de comprimentos iguais.10. senx = sen(2+x)11. 1 + 2 + 3 + +n =n(n + 1)212. Quadrados e tringulos.13. 0, 5 e 5 so razes da equaox325x = 014. 1 + 3 + 5 + 7 + 9 + (2n 1) = n215. Todo tringulo um polgono.2. Sejam as proposies: p : A vaca foi para o brejo; q: O boi seguiu a vaca.Forme frases na linguagem natural, que correspondam s proposies seguintes:1. p 2. q 3. p q 4. p q5. p q 6. p q 7. (p q) 8. (p q)9. p q 10. p q 11. ( q) 12. p q3. Considere as proposies: p : Esta frio; q: Esta chovendo.Traduzir para a linguagemnatural as seguintes proposies:1. p 2. p q 3. p q 4. p q5. p q 6. p q 7. p q 8. p q9. (p q) p 10. p q 11. ( q) 12. ( p) q4. Considere as proposies: p : Pedro alto; q: Pedro jogador de basquete. Escrevaem forma simblica cada uma das seguintes proposies:1. Pedro no alto.24 Fundamentos da Matemtica2. Pedro no jogador de basquete.3. No verdade que Pedro no seja alto.4. No verdade que Pedro jogador de basquete.5. Pedro alto e jogador de basquete.6. Pedro alto ou jogador de basquete.7. Pedro alto e no jogador de basquete.8. Pedro no alto e jogador de basquete.9. Pedro no alto ou no jogador de basquete.10. No verdade que, Pedro alto e jogador de basquete.11. No verdade que, Pedro alto ou jogador de basquete.12. No verdade que, Pedro no alto ou no jogador de basquete.13. Pedro no alto, nem jogador de basquete.5. Sejam: p: Londres a capital da Inglaterra.q: A torre Eiel situa-se em Londres.r: O meridiano de Greenwich passa por Londres.Traduza para a linguagem natural cada uma das proposies abaixo e determine o respec-tivo valor lgico:1. p 2. q r 3. p r 4. q5. p q 6. q p 7. r 8. p r9. q p 10. p q 11. q p 12. (p q)6. Determine todos os valores lgicos para a proposio p qa partir dos valores lgicosdep e q.7. Construa a tabela-verdadepara cada uma das seguintes proposies:1. (p q) 2. p q.8. Mostre que a proposiop q q uma contradio.9. O verso da uma folha a pgina oposta que se observa. Que pgina corresponde ao versodo verso da pgina que se observa?10. Oavessodeumablusa, oladocontrrioaoquesev. Oqueoavessodoavessodoavesso da blusa?O que o avesso do avesso da blusa?11. Traduzir para a linguagem simblica as seguintes proposies matemticas:1. Sex > 0 entoy = 32. Sex +y = 6 entoz< 0.Christian Jos Quintana Pinedo 253. Sex = 6 oux = 5, entox211x + 30 = 0.4. Sex211x + 30 = 0 entox = 6 oux = 55. Sez> 5 entox ,= 1 ex ,= 2.6. Sey = 4 ex < y entox < 5.12. Determine a recproca, inversa e contra-recproca de cada uma das seguintes proposiescondicionais.1. Se v paralelo a wento w paralelo a v .2. Duas retas se interceptam se no so paralelas.3. Se o Oscar se licenciar ele vai procurar emprego ou inscrever-se num curso de mestrado.4. Se a Virgnia se licenciar e se inscrever num curso de mestrado ento a sua licenciaturano de Matemtica.5. Se a Virgnia se licenciar com boa mdia em Matemtica ela vai ter uma bolsa para seinscrever num curso de mestrado.6. Aprovar em lgebra uma condio necessria para o Belo se licenciar.7. Uma condio suciente para um tringulo satisfazer o Teorema de Pitgoras ser umtringulo retngulo.8. Umacondionecessriaparadoistringulosseremsemelhantesquetenhamladosiguais.9. Um tringulo equiltero s se os seus trs ngulos so iguais ou os seus trs lados soiguais.10. Trs pontos esto sobre a mesma circunferncia s se no forem colineares.13. Quem tem olhos azuis?Em um grupo de trs pessoas duas delas tem olhos escuros e a outra olhos azuis, as pessoasque tem olhos escuros mentem, e a pessoa de olhos azuis sempre diz a verdade. Em umaconversa cada uma diz:Marta: Eu tenho olhos azuis.Clara: Marta mentiu quando disse ter olhos azuis.Rita: Clara quem tem olhos azuis.14. Assinale uma concluso correta.Uma pessoa pode ser boa ou ruim. A mesma pessoa pode ser estudante ou trabalhadora.Masestapessoaestudanteeruim. Logoestapessoanopodeser: a)Estudanteetrabalhadora; b) Boa e trabalhadora; c) Trabalhadora e ruim.15. Trs senhoras, Dona Branca, Dona Rosa e Dona Violeta, passeavam pelo parque, quandoDona Rosa disse:26 Fundamentos da MatemticaNo curioso que estejamos usando vestidos das cores branca, rosa e violeta,embora nenhuma de ns esteja usando vestido de cor igual a seu prprio nome.Uma simples coincidncia, respondeu a senhora com o vestido violeta.Qual a cor do vestido de cada senhora?16. ConsidereaTerracomoumaesferaperfeitaeimagineamenorcordadecomprimentoentorno do Equador. Corta-se essa corda em um ponto, adicione-se a ela um metro lineardecordaecoloque-anovamenteentornodoEquador. ExistirumaseparaoentreoEquador e a corda aumentada, entorno de toda a Terra (ver Figura(1.1)). O Equador daTerra mede aproximadamente 40000 km.Figura 1.1: Figura 1.2:Intuitivamente, de quanto essa separao aproximadamente? (S se pede uma respostaaproximada, segundo a intuio) .a) Menos de 1mm. b) Entre 1mm. e 2cm. c) Pouco mais de 15cm.17. Considere uma laranja e imagine a menor corda de comprimento entorno do equador dalaranja. Corta-seessacordaemumponto, adicione-seaelaummetrolineardecordaecoloque-anovamenteentornodoequador. Existirumaseparaoentreoequadordalaranja e a corda aumentada, entorno de toda a laranja (ver Figura(1.2))Intuitivamente, de quanto essa separao aproximadamente? (S se pede uma respostaaproximada, segundo a intuio)a) Mais de 60cm. b) Entre 60 cm e 19cm. c) Menos de 16cm.18. So apresentadas trs caixas a voc. Somente uma delas contm ouro, o outras duas estovazias. Cada caixa tem uma pista sobre seu contedo s uma mensagem est contando averdade as outras duas esto mentindo.Qual caixa tem o ouro?O ourono est aquiO ourono est aquiO ouro estna segunda caixaChristian Jos Quintana Pinedo 271.4 TAUTOLOGIAOs conectivos lgicos, do mesmo modo que servem para construir proposies compostas apartirdeproposiessimples, tambmsoutilizadosparaobteresquemaslgicos muitomascomplexos a partir de proposies compostas.Em geral o conectivo de menor hierarquia, logo seguem e , esses conectivos tem amesma hierarquia; logo o de maior hierarquia. Porem,cada conectivo pode ser de maiorhierarquia, quando o indica o parnteses de coleo.Lembre que os parnteses () servem para denotar o alcancedos conectivos.Exemplo 1.17.Se a lua quadrada e a neve branca ento a lua no quadrada. Na linguagem simblicaescrevemos: p q p.A lua no quadrada se, e somente se, a neve branca. Na linguagem simblica escrevemos: p qDada uma proposio composta, os valores-verdade de esta proposio so os que correspon-dem aos valores do conectivo de maior hierarquia presente na proposio.Exemplo 1.18.A frmula p q r p q deve ser entendida como:((p q) ( r)) (p ( q))Denio 1.8. Tautologia.Chama-se tautologia toda proposio composta quando, depois de procurar a ltima coluna desua tabela-verdade achamos somente a letra (v).Deoutromodo, tautologiatodaproposiocomposta P(p, q, r,)cujovalorlgicosempre verdade (v), quaisquer que sejam os valores lgicos das proposies simples p, q, r,.Exemplo 1.19.A proposio p p tautologia.p p p pv f vf v vExemplo 1.20.Determine a tabela-verdade para a seguinte proposio: P(p , q) : ((p q) q) pSoluo.p q ((p q) q) pv v v f f v vv f v v v v vf v v f f v ff f f f v v f1o3o2o5o4o28 Fundamentos da MatemticaPara obter a tabela-verdadeseguimos o seguinte roteiro:1oAplicamos o valor-verdade da disjuno para as proposiesp e q.2oAplicamos a negao proposioq.3oAplicamos a valor-verdade s colunas 1oe 2o.4oEscrevemos novamente valor-verdade para a proposiop.5oAplicamos o valor-verdade da implicao s colunas 3oe 4o.Observe-se nesta proposio composta que o conectivo da implicao o de maior hierarquiae na 5acoluna todas as linhas tem o valor-verdade (v), logo a proposio uma tautologiaDenio 1.9. Contradio.Chama-se contradio toda proposio composta quando, depois de procurar a ltima colunade sua tabela-verdade achamos somente a letra (f).De outro modo, contradio toda proposio composta P(p, q, r,) cujo valor lgicosempre falso (f), quaisquer que sejam os valores lgicos das proposies simples p, q, r,.Portanto, P(p, q, r,)umatautologiase, esomentese, P(p, q, r,)umacontradio.Exemplo 1.21.A proposio p p uma contradio.p p p pv f ff v fExemplo 1.22.Determine a tabela-verdade para a proposio: P(p) : ((p p) p)Soluo.p ((p p) p)v f v v v v vf f f f f v f6o1o3o2o5o4oPortanto, a proposio: P(p) : ((p p) p) uma contradioDenio 1.10. Contingncia.Chama-se contingncia toda proposio composta quando, depois de procurar a ltima colunade sua tabela-verdade achamos uma mistura de linhas com a letra (v) ou (f).Deoutromodo, umacontingnciatodaproposiocompostaquenotautologianemcontradio. As contingncias tambm so chamadas de proposies contingentes ou proposiesindeterminadas.Christian Jos Quintana Pinedo 29Exemplo 1.23.Determine a tabela-verdade para a proposio: P(p, q, r): ((p q) r)Soluo.Observe que o conectivo de maior hierarquia .p q r ((p q) r)v v v v v f fv v f f v v vv f v v f f fv f f v f f vf v v v f f ff v f v f f vf f v v f f ff f f v f f vPortanto, a proposio: P(p, q, r): ((p q) r) uma contingncia1.4.1 Tautologias elementares.1. Leis da equivalncia.(a) p p . . . reexiva.(b) (p q) (q p) . . . simetria.(c) ((p q) (q r)) (p r) . . . transitividade.2. Lei do terceiro excludo.p p3. Lei do silogismo hipottico.((p q) (q r)) (p r)4. Lei do silogismo disjuntivo.((p q) p) q5. Lei do absurdo.(a) ( q (p p)) q(b) ( q (p p)) q(c) (( q p) ( q p)) q6. Lei de no contradio. (p p)7. Lei comutativa.30 Fundamentos da Matemtica(a) Para a conjuno: (p q) (q p)(b) Para a disjuno: (p q) (q p)(c) Para a bicondicional: (p q) (q p)8. Lei associativa.(a) Para a conjuno: (p (q r)) (p q) r)(b) Para a disjuno: (p (q r)) (p q) r)9. Lei distributiva.(a) (p (q r)) ((p q) (p r))(b) (p (q r)) ((p q) (p r))10. Leis de Morgan.(a) (p q) ( p q)(b) (p q) ( p q)11. Dupla negao. (p) p12. Adio.p (p q)13. Simplicao.(a) (p q) p(b) (p q) p14. Modus Ponens.((p q) p) q15. Modus Tollens.(( q p) p) q16. Idempotente.(a) (p p) p(b) (p p) p17. Transposio (ou de contraposio).(p q) ( q p)18. Implicao material.(p q) ( p q)Christian Jos Quintana Pinedo 3119. Equivalncia material.(a) (p q) ((p q) (q p))(b) (p q) ((p q) ( p q))20. Dilema construtivo.((p q) (r s) (p r)) (q s)21. Dilema destrutivo.((p q) (r s) ( q s)) ( p r)22. Exportao.(a) ((p q) r) (p (q r))(b) ((p1 p2 pn) r) (p1 p2 pn1) (pnr))1.4.2 Implicao lgica.Denio 1.11.Dizemos que uma proposio P(p, q, r,) implica, logicamente outra proposio Q(p, q, r,)se, sempre queP(p,q,r,) seja verdadeira (v), entoQ(p,q,r,) tambm verdadeira (v).Exemplo 1.24.Sejam P(p, q): p q e Q(p, q): p q, temos que:p q p q p qv v v vv ff v v vf f v vp q P(p, q) Q(p, q)v v vv ff v vf f vLogo a proposioP(p, q) implica logicamente a Q(p, q).Exemplo 1.25.Mostre que a proposio P(p, q): p (p q) implica logicamente proposio Q(p, q):p q.Soluo.p q p (p q) p qv v v vv ff v v vf f v vp q P(p, q) Q(p, q)v v vv ff v vf f v32 Fundamentos da MatemticaExemplo 1.26.Determineseaproposio R(p, q): p q implicalogicamenteaproposio S(p, q):p q.Soluo.p q p q p qv v v vv ff v v ff f v vp q R(p, q) S(p, q)v v v v vv ff v v f ff f v v vObserveaterceiralinhada tabela-verdade, averdadedeR(p, q)noimplicaaverdadedeS(p, q).Portanto a proposio R(p, q), no implica logicamente a proposio S(p, q).Propriedade 1.1.AproposioP(p1, p2, , pn)implicalogicamenteaproposioQ(p1, p2, , pn), seesomente se a condicional P(p1, p2, , pn) Q(p1, p2, , pn) tautologia.Demonstrao.Condio necessria. ()SeP(p1, p2, , pn) implica logicamente a proposioQ(p1, p2, , pn), ento no ocorreque os valores na mesma linha da tabela verdade sejam simultaneamente (v) e (f) nessa ordem;logo a valor verdade na coluna da tabela da proposio P(p1,p2, ,pn) Q(p1,p2, ,pn)somente (v), assim esta condicional tautologia.Condio suciente. ()Seacondicional P(p1, p2, , pn) Q(p1, p2, , pn)tautologia, istonaltimacolunadesua tabela-verdadetemossomentealetra(v), entonoocorrequeosvaloressi-multneos correspondentes mesma linha sejam (v) e (f) nessa ordem. Portanto a proposioP(p1, p2, , pn) implica logicamente Q(p1, p2, , pn).Exemplo 1.27.Mostre que a proposio p implica logicamente a proposio q em cada um dos seguintes casos:a) p : > 2; q : tan 6=33b) p : sen3=32; q : 8 >32c) p : 12 mltiplo de 4; q : 6 divisvel por 2.Soluo.(a), (b), (c)A proposiop verdadeira;q verdadeira; logop q verdadeira; assimp implica logica-mente a proposioq.Christian Jos Quintana Pinedo 331.4.3 Equivalncia lgica.Denio 1.12.DizemosqueumaproposioP(p, q, r,)logicamenteequivalenteaoutraproposioQ(p, q, r,), se a tabela-verdade destas duas proposies so idnticas.Indica-se que a proposioP(p, q, r,) equivalente proposioQ(p, q, r,) com anotaoP(p, q, r,) Q(p, q, r,)Observe que, no caso das proposies P(p, q, r,) e Q(p, q, r,) ambas serem tautologiasou contradies, ento so equivalentes.Exemplo 1.28.As proposiesP(p, q): p p q e Q(p, q): p q so equivalentes.Com efeito, observe a tabela-verdadep q p p q p qv v v vv f f ff v v vf f v vExemplo 1.29.As proposiesR(p, q): p q e S(p, q): (p q) (q p) so equivalentes.Observe a tabela-verdadep q p q (p q) (q p)v v v vv f f ff v f ff f v vLogo as proposiesR(p, q) e S(p, q) so logicamente equivalentes.Exemplo 1.30.Consideremos a proposiop qassim como sua recprocaq p, sua inversa p qesua contra-recproca q p.Da seguinte tabela-verdade:p q p q q p q p p qv v v v v vv f f f v vf v v v f ff f v v v vPodemos observar que as proposies p e q p so logicamente equivalentes, assimcomo as proposiesq p e p q.34 Fundamentos da MatemticaExemplo 1.31.Suponha estamos a demonstrar que:Sex2 nmero mpar, entox nmero mpar.Podemosconsideraraproposiop : x2nmerompar, e q : xnmerompar entotemos que vericar a validade da proposiop q. De o fato serem as proposiesp q e q p logicamente equivalentes ser suciente mostrar que:Sex no nmero mpar, entox2no nmero mpar.Denio 1.13.a)Chama-se negao conjunta das proposiesp e q proposio p q, e denotamosp q.b)Chama-se negao disjunta das proposiesp e q proposio p q,e denotamosp q.Da Denio(1.13) resulta que: a) p q p q, e b) p q p q.Exemplo 1.32.Determine a tabela-verdade da proposio: (p q) (p q).Soluo.p q (p q) (p q)v v f v fv f f v vf v f v vf f v f v1o201oPequeno dicionrio de heursticaAnalogia: uma espcie de semelhana. Objetos semelhantes coincidem uns com os outros emalgum aspecto; objetos anlogos coincidem em certas relaes de suas respectivas partes.Considere a incgnita: Esteumvelhoconselho. Correspondeaoditadolatinorespicenem, isto , olhe para o m.Condicionante: uma das principais partes de um problema a demonstrar.Corolrio: umteoremaquesedemonstrafacilmentepeloexamedeoutroteoremaqueseacabadedemonstrar. Apalavradeorigemgregaesuatraduomaisliteral seriagalardoou recompensa.Decomposio:Decompe-se o todo em suas partes e recombinam-se as partes num todo maisou menos diferente.Christian Jos Quintana Pinedo 35Exerccios 1-21. Analisar os seguintes enunciados e:1. Determine quais so proposies.2. Determine quais so enunciados abertos.3. Determine quais no so nem proposies nem enunciados abertos.4. Determine o valor verdadedas proposies.(a) 7 + 12 = 19(b) Voc estudante de matemtica?(c) 15 < 4(d) x + 4 = 10(e) Cantor revolucionou o pensamento matemtico.(f) x 2 < 8(g) Cantor, Burali Forti e B. Russell estudaram o problema dos paradoxos na matemtica.(h) x +y 2(i) x engenheiro.(j) Pedro engenheiro ou Pedro matemtico,(k) x + 2 = 5 se, e somente se,x = 4(l) Escute com ateno.(m) Todo retngulo um quadrado.2. Sejam as seguintes proposies: p: 3+5 = 5 e q: 83 = 5. Traduzir para a linguagemdo dia-a-dia as seguintes proposies:1. p 2. p q 3. p q4. q q 5. p q 6. p q7. p q 8. p q 9. p q p3. Considere as seguintes proposies: p: Jorge mdico, q: Jorge dentista, r: Pedro engenheiro.1. Escrever cada uma das seguintes proposies em forma simblica:(a) Jorge mdico e Pedro engenheiro.(b) Se Jorge mdico ou Pedro engenheiro, ento Jorge no dentista.(c) Jorge no mdico, porem Pedro no engenheiro.(d) Se Pedro engenheiro e Jorge no dentista, ento Jorge no mdico.2. Escrever em forma de orao o signicado das seguintes proposies:36 Fundamentos da Matemtica1. p q 2. ( p q) r 3. p q4. r (p q) 5. ( p q) (p q) 6. (p p q)4. Para cada uma das seguintes proposies, elimine os parnteses segundo as convenes:1. (p q) (( p) r) 2. ( p) (q (( r) s))3. p ((( q) (r s)) (p q)) 4. ((p ( q) r) s) (( p) r)5. Vericar quais as frmulas : tautologia, contradio ou contingncia.1. p p q 2. (p q) (q r) (p r)3. (p q) (q p) 4. p ( p q)5. (p q) ( p q) 6. (p p q)6. Sejam as proposies p: Pedro rico e q: Fredy feliz. Traduzir para a linguagemcorrente as seguintes proposies:1. p q 2. p q 3. p q4. q p 5. q 6. ( p q)7. p (p q) p 8. (p q) p 9. (p q) p q7. Vericar as seguintes tautologias:1. p p p 2. ( p) p 3. (p q) r p (q r)4. (p q) p q 5. p p p 6. (p q) r p (q r)7. p (p q) p 8. (p q) p 9. (p q) p q10. p (p q) p 11. p p r 12. p (q r) (p q) (p r)13. ( q p p) q 14. (p q) q 15. p (q r) (p q) (p r)8. Vericar se o conjunto de proposies da cada item tautologia:1. Pedro bom e Pedro ruim acarreta que Paris a capital de Chile. Braslia a capitaldo Brasil ou Braslia no a capital de Brasil.2. Se Alberto materialista, Alberto ateu. Se Alberto ateu, ento Alberto material-ista.3. Se Joo no encontrou Pedro ontem, ento, ou Pedro o assassino ou Joo morreu. SePedro no o assassino,ento Joo no encontrou Pedro ontem eo assassinato foi meia noite. Se o assassinato foi meia noite,ento,Pedro o assassino ou Joomorreu. Pedro o assassino.9. Mostre que, sep ep q so tautologias, entoq tautologia. Sugesto: Supor queq noseja tautologia.Christian Jos Quintana Pinedo 3710. Mostre que:1. q implica logicamentep q.2. q implica logicamentep q p.3. p q no implica logicamentep q.4. p no implica logicamentep q.5. p q no implica logicamentep.11. Mostrar que: ((x = y x < 4) x 4) x = y12. Mostrar que: ((x ,= 0 x = y) x ,= y) x = 013. Mostre que as proposiesp e q so equivalentes em cada um dos seguintes casos:1. p : 2 + 6 = 8 q : (2 + 6)2= 642. p : sen2= 1 q : cos 2= 03. p : 30= 1 q : < 44. p : x mpar q : x + 2 mpar6.5. p : a b q : b a6. p : a|b q : b|a7. p : O tringuloABC retngulo emA q : BC2= AB2+AC214. Exprimir a bicondicionalp q em funo dos conectivos lgicos , e.15. Mostre mediante tabela-verdadeas seguintes equivalncias lgicas:1. p (p q) p 2. p (p q) p3.(q (p q)) (p q) 4. ((p q) (p r)) (p (q r))5. ((p q) (p r)) (p (q r)) 6. (p (p q)) (p q)16. Mostre que as proposies: x = 5 x 3 e (x < 3 x = 5) no so equivalentes.17. Provequeostrsconectivos , e podemosescreveremfunodoconectivo doseguinte modo:1. p (p p) 2. p q (p q) (p q)3. p q (p p) (q q)18. Provequeostrsconectivos , e podemosescreveremfunodoconectivo doseguinte modo:1. p (p p) 2. p q (p p) (q q)3. p q (p q) (p q)6Lembre que a denio de nmero par ou mpar somente para inteiros Z38 Fundamentos da Matemtica19. Determine a negao lgica das seguintes proposies:1. Estudo lgica, ou esta prova fcil.2. No estudo lgica, e esta prova no fcil.3. Se voc se comportar bem ento, levo voc ao circo.4. Se voc no se comportar bem ento, no levo voc ao circo.5. Se voc se comportar bem ento, no levo voc ao circo.6. Se comporte bem e no levo voc ao circo.7. 3 < x8. "ser branco"20. Resolva o seguinte enigma:Um viajante pede a mo da lha do sulto. Para t-la o sulto diz ao viajante:Destas cinco escravas, voc tem que deduzir a cor dos olhos da segunda e daterceira. As cinco tero os olhos vendados de forma que voc no seja capaz dev-las. Trs tm olhos verdes, duas tm olhos azuis.As de olhos verdes sempre mentem, as de olhos azuis sempre dizem a verdade.Voc pode fazer somente trs perguntas para elas.Ah! esqueci, se voc comete um engano, voc morrer por sua insolncia.Viajante : De que cor so seus olhos?Escrava 1: bla, bla, bla . . . (responde em um idioma incompreensvel para ele)Viajante : Que falou tua companheira?Escrava 2: Ela falou que tem olhos verdes.Viajante : Que falhou a primeira e de que cor so os olhos da segunda?Escrava 3: A primeira diz ter olho azul, e a segunda tem olho verde.Concluso : O viajante caso com a princesa.21. Tenho trs pares de sapatos: S1, S2e S3; um par preto,um par marrom e o outro branco, no necessariamente nesta ordem. Somente uma das armaes verdadeira: i)S1 preto; ii) S2 no preto; iii) S3 no branco.Quais as cores dos sapatosS1, S2e S3 nessa ordem?Christian Jos Quintana Pinedo 391.5 LGEBRA DE PROPOSIESTrata-se nesta seo de um conjunto de operaes lgicas que podemos realizar, com a uti-lizao dos conectivos da conjuno, disjuno, negao, implicao e bicondicional.1.5.1 Propriedades da conjuno.Consideremosp, q, r, s e tproposiessimples, entooconectivolgicodaconjunosatisfaz as seguintes propriedades:a) p p p . . . idempotente.b) p q q p . . . comutativa.c) (p q) r p (q r) . . . associativa.d) p t p sempre quet verdadeira (v) . . . propriedade depe) p s s sempre ques falsa (f) . . . propriedade desDemonstrao. a)Na seguinte tabela-verdade observe que as linhas das proposiesp pe p so idnticas, ea bicondicionalp p p uma tautologia.p p p pv v v vf f v fAssim, tanto,p p quanto p so proposies logicamente equivalentes.Demonstrao. b)Comefeito, observandoascolunasdatabela-verdadeparaasproposiespqeqpmediante o conectivo obtemos uma tautologia.p q p q q pv v v v vv f f v ff v f v ff f f v fLogo, tanto,p q quanto q p so proposies logicamente equivalentes.Demonstrao. c)Temos que a tabela-verdade para a proposio (p q) r p (q r) uma tautologia.40 Fundamentos da Matemticap q r (p q) r p (q r)v v v v v vv v f f v fv f v f v fv f f f v ff v v f v ff v f f v ff f v f v ff f f f v fFica mostrado que,tanto (p q) r quanto p (qr) so proposies logicamenteequivalentes.Demonstrao. d) (Propriedade da identidade).Somentenocasodasproposies tverdadeira(v)esfalsa(f)temosqueasproposiesp t p e p s p so tautolgicas.Com efeito, temos as tabela-verdadeseguintes:p t p t pv v v v vf v f v fp s p s sv f f v ff f f v fEstas propriedades exprimem det e s so respectivamente o elemento neutro e o elementoabsorvente da conjuno.Exemplo 1.33. Propriedade idempotente.i) x ,= 3 x ,= 3 x ,= 3ii) a 8 a 8 a 8Exemplo 1.34. Propriedade comutativa.i) x ,= 7 x = 5 x = 5 x ,= 7ii) a 6 a 15 a 15 a 6iii) y 6 y 1 1 y y 6Exemplo 1.35. Propriedade associativa.i) (x ,= 7 x = 5) x 12 x ,= 7 (x = 5 x 12)ii) (a 6 a 15) a ,= 7 a 6 (a 15 a ,= 7)Exemplo 1.36. Propriedade da identidade.i) a ,= 3 [ a [ 0 a ,= 3ii) x ,= 3 [ x [< 2 [ x [< 2Christian Jos Quintana Pinedo 411.5.2 Propriedades da disjuno.Sejamp, q, r, s e t proposies simples, ento o conectivo lgico da conjuno satisfaz asseguintes propriedades:a) p p p . . . idempotente.b) p q q p . . . comutativa.c) (p q) r p (q r) . . . associativa.d) p t t sempre quet verdadeira (v) . . . propriedade detp s p sempre ques falsa (f) . . . propriedade depDemonstrao. a)Na seguinte tabela-verdade as proposies ppe p so idnticas, e a bicondicional pp p uma tautologia.p p p pv v v vf f v fDemonstrao. b)Comefeito, observandoascolunasdatabela-verdadeparaasproposiespqeqpmediante o conectivo obtemos uma tautologia.p q p q q pv v v v vv f v v vf v v v vf f f v fDemonstrao. c)Temos que a tabela-verdade para a proposio (p q) r p (q r) uma tautologia.p q r (p q) r p (q r)v v v v v vv v f v v vv f v v v vv f f v v vf v v v v vf v f v v vf f v v v vf f f f v fDemonstrao. d)Somentenocasodasproposies tverdadeira(v)esfalsa(f)temosqueasproposiesp t t e p s p so tautolgicas.Com efeito, temos as tabela-verdadeseguintes:42 Fundamentos da Matemticap t p t tv v v v vf v v v vp s p s pv f v v vf f f v f

Estas propriedades exprimem det e s so respectivamente o elementoabsorventee o ele-mento neutro da conjuno.Exemplo 1.37. Propriedade idempotente.i) x ,= 3 x ,= 3 x ,= 3ii) a 8 a 8 a 8Exemplo 1.38. Propriedade comutativa.i) x ,= 7 x = 5 x = 5 x ,= 7ii) a 6 a 15 a 15 a 6iii) y 6 y 1 1 y y 6Exemplo 1.39. Propriedade associativa.i) (x ,= 7 x = 5) x 12 x = 5 (x ,= 7 x 12ii) (a 6 a 15) (a ,= 7) a 15 (a 6 a ,= 7)Exemplo 1.40. Propriedade de identidade.i) a ,= 3 [ a [< 1 a ,= 3ii) x ,= 3 [ x [ 2 [ x [ 21.5.3 Propriedades da disjuno e conjuno.Sejamp, q e r proposies simples, temos as seguintes propriedades:1. Absoro.(a) p (p q) p(b) p (p q) p2. Propriedade distributiva.(a) p (q r) (p q) (p r)(b) p (q r) (p q) (p r)3. Negao.(a) ( p) pChristian Jos Quintana Pinedo 434. Leis de Morgan.(a) (p q) (p q)(b) (p q) (p q) Demonstrao da propriedade de absoro.Demonstrao. (a)Temos a seguinte tabela-verdadepara as proposies p (p q) e pp q p (p q) pv v v v vv f v v vf v f v ff f f v fObserve que a bicondicional p (p q) p tautologia, logo as proposies p (p q)e p so logicamente equivalentes.Demonstrao. (b)De modo anlogo, temos a seguinte tabela-verdadepara as proposies p (p q) e pp q p (p q) pv v v v vv f v v vf v f v ff f f v fA bicondicional p (p q) p tautologia, logo as proposies p (q r) e pso logicamente equivalentes. Demonstrao das Leis de Morgan:Demonstrao. (a) e (b)Observe a tabela-verdadepara a bicondicional:p q (p q) p qv v f v fv f v v vf v v v vf f v v vp q (p q) p qv v f v fv f v v ff v v v ff f v v vNasduastabelastemostautologia; logoasproposiesindicadassologicamenteequiva-lentes.As demais demonstraes exerccio para o leitor.Propriedade 1.2. Negao da condicional.Tem-se que a negao da proposio p q logicamente equivalente proposiop q.44 Fundamentos da MatemticaDemonstrao.Com efeito, a mostrar que (p q) p q. Observe a tabela-verdade:p q p q p qv v v v vv f f v ff v v v vf f v v vPor outro lado, a negao da proposiop q a proposio (p q), isto (p q) ( p q) p q p q.Portanto, (p q) p qObservao 1.4.A condicional,p q no satisfaz as propriedades idempotente, comutativa e associativa.Propriedade 1.3. Negao da bicondicional.A negao da proposio p q logicamente equivalente proposio (p q)(p q).Demonstrao.Com efeito temos quep q logicamente equivalente proposio (p q) (qp),isto da seguinte tabela-verdade.p q (p q) (p q) (q p)v v v v vv f f v ff v f v ff f v v vLogo aplicando as regras de Morgan, temos que (p q) ((p q) (q p)) (p q) (q p) ((p q) (q p)).Portanto, (p q) ((p q) (q p)).Observao 1.5.A bicondicional p q no satisfaz a propriedade idempotente, pois obvio que as proposiesp p e p no so logicamente equivalentes.A bicondicional satisfaz as propriedades, associativa e comutativa.1.5.4 Mtodo dedutivo.Todasascondicionaisebicondicionaislgicas, forammostradasmedianteautilizaodetabela-verdade. No que segue estas condicionais e bicondicionais mostraremos pelo mtodo maiseciente chamado mtodo dedutivo.Nestemtododedutivo sodemuitaimportnciaasequivalnciasrelativaslgebradeproposies; por exemplo, para a seguinte proposio (p q) p, temos:((p q) p) ((p q) p) . . . tautologia.Christian Jos Quintana Pinedo 45((p q) p) ((p q) p) . . . lei de Morgan.((p q) p) (p p) q) . . . comutativa.(p p) q) (T q) . . . tautologia.(T q) T . . . tautologia.Portanto, (p q) p logicamente verdadeira; tautologia. Observao 1.6.Denotamos com T as proposies logicamente verdadeiras (tautologias), e com (proposieslogicamente falsas (contradio)Exemplo 1.41.Mostre a implicao: ((p q) p) q (modus ponens) logicamente verdadeira.Demonstrao.(((p q) p) q) . . . hiptese.(((p q) p) q) . . . tautologia.((p p) (q p) q) . . . distributiva.(( (q p) q) . . . contradio.((q p) q) . . . cancelamento. T . . . tautologia.Portanto, ((p q) p) p logicamente verdadeira; tautologia.1.5.5 Reduo do nmero de conectivos.Foram estudados cinco conectivos lgicos, entretanto podemos reduzir esse nmero para dois,entendendo-secomistoquetrsdelespodemserdenidosemfunodedois, conrmando-separa estas novas denies a mesma tabela-verdadeda proposio original.Propriedade 1.4.Entre os cinco conectivos lgicos fundamentais:, , , trs exprimem-se em termos apenas dos seguintes pares:a) e ; b) e ; c) e .Demonstrao. a)1op q (p q) (p q)46 Fundamentos da Matemtica2op q ( p q)3o(p q) ((p q) (q p)) (( p q) ( q p)) (p q) (q p)) ((p q) (q p))Demonstrao. b)1op q (p q) (p q)2op q ( p q) (p q)3o(p q) ((p q) (q p)) ( (p q) ( (p q)))Demonstrao. c)1op q ( (p q)) ( p q)2op q (p q) (p q)3o(p q) ((p q) (q p)) ((p q) (q p)) Observao 1.7.1. Os conectivos , e no se exprimem em termos de e2. O conectivo exprime-se em funo unicamente de pela equivalnciap q ((p q) q)3. Todos os conectivos exprimem-se em termos de um nico ou .Denio 1.14. Forma normal.Diz-sequeumaproposioestanaformanormal (FN) se, esomentese, quandomuito,contm os conectivos , e .Exemplo 1.42.As seguintes proposies esto na forma normal (FN):p q, p q, (p q) (q r)Denio 1.15. Forma normal conjuntiva.Diz-sequeumaproposioestanaformanormal conjuntiva(FNC)se, esomentese, sovericadas as seguintes condies:a)Contm quando muito os conectivos , e ;b) opera sobre as proposies simples; e no tem alcance sobree ;c)no aparecem sinais de negao sucessivos como ;d) no tem alcance sobre, no h expresses do tipop1 (p2 p3).Christian Jos Quintana Pinedo 47Exemplo 1.43.As seguintes proposies esto na forma normal (FNC):p q, p q r, (p q) (q r)Exemplo 1.44.So (FNC) ( p q) (r s p), p q, p q, p, qNo so (FNC) p q, r, p (q r), (p q)Observao 1.8.Para todo proposio composta, possvel determinar uma (FNC) a ela logicamente equiva-lente. Para isso, usamos as seguintes regras:a)Eliminandop q por p q e p q mediante a substituio (p q) (p q).b)Eliminando as negaes repetidas e parnteses precedidos de pelas regras da negao duplae de Morgan.c)Substituem-se:1. p (q r) por (p q) (p r)2. (p q) r) por (p q) (p r)Exemplo 1.45.Seja ((p q) q) (r q); temos:1. ((p q) q) (r q) . . . hiptese.2. ( (p q) q) (r q) . . . lei de Morgan3. ( p q) q) (r q) . . . lei de Morgan, tautologia.4. (( p q) ( q q)) (r q) . . . tautologia.5. ((( p q) ( q q)) r) (( p q) ( q q)) q) . . . tautologia.6. ( p q r) ( q q r) ( p q q) ( q q q)Exemplo 1.46.Determine a (FNC) da proposio (((p q) q) (q r))Soluo. (((p q) q) (q r)) (( (p q) q) ( q r)) ((( p q) q) ( q r)) (( p q) ( q q) ( q r))48 Fundamentos da MatemticaPropriedade 1.5.Uma forma normal conjuntiva (FNC) tautolgica se, e somente se, cada elemento da con-juno uma tautologia, isto cada elemento equivale frmula disjunta formada por p e a negao p.Demonstrao.Efetivamente, secadaelementoequivaleformuladetautologia, entocadaelementotautolgico e dai cada um equivale ap p.Reciprocamente, se cada elemento equivalente tautolgico p p, ento, a conjuno, que a (FNC) tautologia. Denio 1.16. Forma disjuntiva.Diz-sequeumaproposioestanaformanormal disjuntiva(FND)se, esomentese, sovericadas as seguintes condies:a)Contm quando muito os conectivos , e ;b) opera sobre as proposies simples; e no tem alcance sobree ;c)no aparecem sinais de negao sucessivos como ;d) no tem alcance sobre, no h expresses do tipop1 (p2 p3)Exemplo 1.47.As seguintes proposies esto na forma normal disjuntiva (FND):: p q, p ( q r), (p q) (p q r)Exemplo 1.48.So (FND ) p (q r) ( s p), p, p p, q, p qNo so (FND) p, (p q), p (q r).Para todo proposio composta, possvel determinar uma (FND) a ela logicamente equiv-alente. Para isso, usamos as seguintes regras:a)Substituem-sep q por p q e p q por ( q) (p q)b)Utilizando a lei de Morgan, elimina-se o conectivo da negao que precede ao parnteses.c)Eliminam-se as negativas mltiplas.d)Substituem-se:1. p (q r) por (p q) (p r)2. (p q) r) por (p q) (p r)Christian Jos Quintana Pinedo 49Exemplo 1.49.Determinar a (FND) da proposio: (p q) (q p).Soluo.((p q) (q p)) ((( p q) q) (( p q) p) (( p q) (q q) ( p p) (p q))Exemplo 1.50.Determinar a (FND) da proposio: ((p q) q) (r q).Soluo.1. ((p q) q) (r q) . . . hiptese.2. (p q) q (r q) . . . lei de Morgan.3. ( p q) q (r q) . . . lei de Morgan.Propriedade 1.6.Uma frmula normal disjuntiva co