Introdução à Lógica e Álgebra de Boole

publicação citlci fi H iÓGicA E ÁLGEBRA DE BooiE Diferentemente de textos convencionais este livro adota a estratégia de ensi nar através de exemplos com a utilização de um instrumental lógico que faci lita O 9flÍefldm6flÍ0 B 8 mOdeagem de sistemas reais O uso de ilustrações como meio de exposição proporciona neste texto bases seguras para gene ralizaçoes e para o próprio conhecimento e desenvolvimento da lógica pelo leitor A introdução à Lógica e Álgebra de Boole visa mostrar um exemplo de mode Iomatematico de inumeras e importantes aplicações em diferentes ramos da atividade humana como eletrônica computação e outros O livro resultou de intensa pesquisa e da experiência de magistério do autor Por isso sua forma agradável de apresentar o conteúdo programáticoem vez de uma abordagem orientada para o conhecimento da Matemática pura abstrata o autor optou pela apresentação de um sistema algébrico que repre sentou importante passo no desenvolvimento da eletrônicac computação pneumática e outras aplicaçõesque envolvem até a Pesquisa Operacional n NOTA SOBRE O AUTOR A Jacob Daghlian é licenciado em Matemática pela Faculdade de Filosofia Ciências e Letras da Fundação Santo André onde lecionou ÁlgebraFoi pro fessor de Álgebra Dooleana na Faculdade de Filosofia Ciências e Letras Prof Carlos Pasquale E reitor da Universidade Metodistade São Paulo UMESP e possui larga vivência industrial que lhe permitiu avaliar a importância da matéria ora apresentada A APucAçÃo Livrotexto para as disciplinas LÓGICA MATEMÁTICA e INTRODUÇAO À LOGICA dos cursos de Matemática bacharelado e Tecnologia de Processa mento de Dados Texto complementar para a disciplina CIRCUITOS LOGI COS E OFiGANlZAÇAO DE COMPUTADORES do curso de Ciências da Computação wwwEditoraAt1ascombr 1783522 41255 Dcigh on iz Ú meirum flfifllmwiløfim JACOB DAGHLIAN LOGICQ Q FÍLGEBRQde l3OOLE àsnupa uuuimi LÓG CAE ÁLGEBRA DEBOOLE 4J 4i nIIn l iiir ll ilI I i 3 iIJVJ J 1v 6 I 5z U š f 1Í š 7 Ê É Iuillàmww vbuiiurtivllvwvoau Ê i I i i iI Q 2 í Ê 1f e Ê JACÚE3 DAGIlllAll LÓGMZA E ÀLGEBRA DE BQOLE 4 Edicao SÃO PAULO EDITORA ATLAS SA 2008 1986 by Editora Atlas SA go iI1õ 1 ed 19só 2 ed 19ss3â199o à i 4 ed 1995 12 reimpressão zoos zzliàAfi nsuu Di šIIF WWW H Y J ff vn í1 O ëä gi Capa Paulo Ferreira Leite mmol Composição Style Up Dados Internacionais de Catalogação na Publicação CIP Câmara Brasileira do Livro SP Brasil Daghlian Jacob 1936 Lógica e álgebra de BooleJacob Daghlian 4 ed 12 reimpr São Paulo Atlas 2008 Bibliografia ISBN 9788522412563 1 Álgebra booleana 2 Lógica simbólica e matemática I Título 950876 CDD511324 Índice para catálogo sistemático 1 Álgebra booleana 511324 TODOS OS DIREITOS RESERVADOS É proibida a reprodução total ou parcial de qualquer forma ou por qualquer meio A violação dos direitos de autor Lei ng 961098 é crime estabelecido pelo artigo 184 do Código Penal Depósito legal na Biblioteca Nacional conforme Decreto ni 1825 de 20 de dezembro de 1907 impresso no BrasilPrinted in Brazil Editora Atlas SA Rua Conselheiro Nébias 1384 Campos Elisios 01203904 São Paulo SP Tel 0 11 33579144 PABX wwwEditoraAtlascombr F má E 5 Ui HiIl MJ É as ulMlIâinútiIfimi l nmiwwiumiw 3 i nzvannzum nunwpqwwu4imM4UvflnnH Agradecimentos Antonio Ângelo Fratoni Desenhos do Capítulo 14 Vânia Linda Domingues Datilografia do Capítulo 14 A Carlos Alberto Garcia Calioli in memoriam e Rubener da Silva Freitas Mestres e amigos cujo entusiasmo e incentivo me conduziram ao Magistério nmlflufifl llliIlINiÚII1rflfliløliIIIIUí E un š z W Pela ajuda de dos sábios meus pais Leon e Hripsímé Pelo incen tivo de minha esposa Hulda Pela carinhosa presença de meus filhos Leon e Ricardo Pelos meus irmãos Carlos Luíz e Celi Pela oportunidade de realizar este trabalho Elevo 0 pensamento em gratidão a DEUS Ê 1 É Uullnn eqigfl iiiiivimviiriunnviasiiIo1Il ill HH zl i l al i l muøumi l ii Sumório Prefácio 13 Apresentação 15 1 SISTEMAS DICOTÔMICOS 17 11 Introdução 17 12 Interruptores 18 13 Conjuntos 22 14 Proposições 26 141 Princípios fundamentais da lógica matemática 27 1 42 Tabelaverdade 28 Exu ÍS 29 2 OPERAÇÕES LÓGICAS SOBRE PROPOSIÇÕES 31 21 Negação 32 22 Conjunção 32 23 Disjunção inclusiva ou soma lógica 32 24 Disjunção exclusiva 33 25 Condicional r 34 26 Bicondicional 35 Exercicios 36 z z 1z 7 CONSTRUÇÃO DA TABELAVERDADE 39 FLUXOGRAMAS 77 Iuémiidnu nãulfzz um 1 Exercícios 85 Exerc1c1os 42 l 4 8 OUANTIEICADORES 89 RELAÇOES DE IMPLICAÇAO E DE EOU1vALENc1A4ó 81 Sentença aberta 89 g 41 Deñnições 46 82 Quantificador universal 90 42 Relação de implicação 47 83 Quantificador existencial 91 43 Relação de equivalêncga 47 84 Valores lógicos de sentenças quantificadas 93 44 Equivalências notáveis às 85 biegação de sentenças quantificadas 93 45 Propriedades 51 Exercicios 96 Exercícios 51 9 5 INTRODUÇÃO À ÁLOEBRA DE BOOLE 97 AROUMENTO VÁLIDO 54 91 Operador binário 97 92 Propriedades das operações 97 51 Definiçâ0 54 93 Sistemas algébricos 105 52 Regras de inferência 56 Exefclclosf 114 Exercícios 5 8 10 6 9 FUNÇOES BOOLEANAS 117 TÉCNICAS DEDUTIVAS 62 Exercícios 120 61 Prova direta 62 62 Prova condicional 65 A 1 1 63 Prova bicondicional 67 4 64 Prova indireta ou por redução ao absurdo 68 O REPRESENTAÇAO DAS FUNÇOES BOOLEANAS 122 65 Pwva indireta da forma CndÍÍ0n1 70 111 Diagramas de Venn ou círculos de Euler 122 Exerc1c1os 71 112 Tabelasverdade 123 g 113 Representação geométrica 124 l Exercícios 128 1 1 FORMAS NORMAIS 131 121 Forma normal a n variáveis 131 122 Forma normal disjuntiva 131 123 Forma normal conjuntiva 133 124 Funções na forma binária 134 125 Funções na forma decimal 135 Exercicios 137 13 MINIMIZAÇAO DE FUNÇOES 139 c 131 Método algébrico 139 132 Método do Mapa de Karnaugh 140 133 Método de QuíneMcC1uskey 148 Exercícios 152 14 PORTAS LÓGICAS 154 Bibliografia 166 viirírriäiiwwi Q fiWiuureezirrzàasareriàriiâ J i n1znnPbn0 Prefócio Os últimos 10 anos vêm presenciando um aumento sem precedentes da apli cação da Matemática particularmente da Álgebra no entendimento e solução dos problemas das Ciências da Computação Estruturas algébricas cada vez mais estão sendo empregadas na modelagem e controle de circuitos eletrônicos e de sistemas de informações A Álgebra aplicada à computação vem sendo paulatinamente in troduzida nos currículos das escolas de 20 e 39 graus sob formas diversas É pois com grande satisfação que apresentamos ao leitor este dedicado tra balho do colega Jacob Daghlian Tratase de um livro que surgiu como frutodo intenso trabalho de pesquisas bibliográficas e das experiências do magistério viven ciadas pelo autor no ensino de disciplinas cujos conteúdos abrangem este texto É sabido que os estudantes são mais hábeis quando conhecem a causa pela qual aprendem uma técnica particular e tendem a perder o interesse se os métodos matemáticos são apresentados de maneira puramente abstrata sem aplicações prá ticas Consciente o autor adota a estratégia de ensinar através de exemplos utili Zando o instrumental lógico para o entendimento e a modelagem de sistemas reais O uso de ilustrações familiares como meio de exposição por certo oferecerá base para generalizações e o próprio conhecimento e desenvolvimento da Lógica pelo leitor Devemos deixar claro que não desaprovamos a abordagem orientada exclusi vamente para o conhecimento da Matemática Pura Porém entendemos que quando o trabalho básico inicial estiver bem assentado o aluno terá estímulo para aprofundar os indispensáveis conhecimentos teóricos da Matemática Pura Com esses objetivos o autor produziu um livrotexto claro e compreensível destinado aos cursos introdutórios de Álgebra Aplicada à Computação que certa mente dará os fundamentos para que os leitores caminhem com segurança nos estudos investigações e pesquisas nessa área do conhecimento humano Congratulamonos com o Prof Jacob Daghlian e com a Editora Atlas pela publicação augurando a continuação de empreendimentos desta natureza São Paulo abril de 1986 PROF GILBERTO DE ANDRADE MARTINS z Í zf É M š Apresentoçõo O presente texto originouse das notas de aula do curso que ministramos há alguns anos aos alunos do curso de Matemática da Faculdade de Filosofia Ciên cias e Letras da Fundação Santo André Ao redigilo como primeira razão moveu nos o interesse de entregar aos nossos alunos um texto que contivesse os pontos principais de nosso curso e que superasse a necessidade nesta primeira parte dos estudos de livros estrangeiros de difícil e cara obtenção Outro aspecto importan te que nos levou a este trabalho e nos mantém motivados no seu aprimoramento é a apresentação de um sistema algébrico que representou importante passo no desenvolvimento da eletrônica computação pneumática e outras aplicações que envolvem até a Pesquisa Operacional Sua presença é marcante nos estudos de automatização levando a simplificações com sensíveis reduções de custo tendo dado origem a métodos que representam grande economia de tempo em projetos com os quais possa relacionarse Nada apresentamos de original e em alguns casos incorremos na linguagem característica de queridos mestres como o foi Alcides Boscolo de saudosa memó ria e ainda o é Edgard de Alencar Filho não deixando de mencionar a marcante influência de alguns textos citados na bibliografia Agradecemos o apoio dos colegas bem como as críticas recebidas sendo os erros e imprecisões de nossa inteira responsabilidade Em particular agradecemos ao Prof José Otávio Moreira Campos o incentivo e empenho para a concretização deste trabalho Finalizando prestamos nossa homenagem aos professores que desde o Jar dim da Infância participaram de Jnossa formação dedicandolhes este livro e para evitar omissões citando as diferentes escolas que cu rsamos Jardim da Infância e Primário Academia de Comércio Horácio Berlinck Jaú SP 14 ç 15 Ginásio Ginásio Estadual de Jaú Jaú SP Colégio São Norberto Jaú SP Colégio Dante Alighieri São Paulo SP Cíentffco Escola Preparatória de Cadetes do Exército São Paulo SP Escola Preparatória de Cadetes do Exército Porto Alegre RS Superior Academia Militar das Agulhas Negras Resende RJ Faculdade de Filosofia Ciências e Letras da Fundação Santo André Santo André SP Organização Santamarense de Educação e Cultura OSEC São Paulo SP Especialização Pontifícia Universidade Católica de São Paulo PUC São Paulo SP PósGraduação Instituto Metodista de Ensino Superior IMS São Bernardo do Cam po SP Mestrado em Administração São Paulo 1995 JACOB DAGHLIAN 1 siíiifsfirmfrfi ihhereaariàiézzv ir 1 1 5 i Sistemos Dicotômicos 11 INTRODUÇÃO O mundo em que vivemos apresenta situações com dois estados apenas que mutuamente se excluem algumas das quais tabelamos a seguir 1 7 77 7 7 W 77 7 l 77 7 77 77 F ll 1 l O l I fim Í Ami fíIíÍ7T7JrÚ7ÉF l íi 7 S im Não fz f f 1 ff L z 7ííff z77 ff li 1 Dia Noite Preto or Branco T7 Ylífr 7 Í mf T 7 z Tfwz 1 41 l Ligado ii Desligado oç Há situações como morno e tépido diferentes tonalidades de vermelho etc que não se apresentam como estritamente dicotômicas ou seja com dois estados ex cludentes bem definidos A Lógica começou a desenvolverse com Aristóteles 384322 aC e os an tigos filósofos gregos passaram a usar em suas discussões sentenças enunciadas nas formas afirmativa e negativa resultando assim grande simplificação e clareza com efeito de grande valia em toda a Matemática Por volta de 1666 Gottfried Wilhelm Leibniz 16461716 usou em vários trabalhos o que chamou cacuus rarr0trnator ou ogca mathematíca ou ogrstíca Estas idéias nunca foram teorizadas por Leibniz porém seus escritos trazem a idéia da Lógica Matemática no No século XVIII Leonhard Euler 17071783 introduziu a representaçao gráfica das relações entre sentenças ou proposições mais tarde ampliada por John Venn 18341923 E W Veitch em 1952 e lVl Karnaugh em 1953 Em 1847 Augustus DeMorgan 18061871 publicou um tratado Formaogc envol 17 vendose em discussão pública com o filósofo escocês William Hamilton que nada tinha a ver com o matemático William Rowan Hamilton conhecido por sua aver são à Matemática o qual entre outras coisas escreveu A Matemática congela e embota a mente um excessivo estudo da Matemática incapacita a mente para as energias que a filosofia e a vida requerem George Boole 18151864 ligado pela amizade a Dellorgan interessouse pelo debate entre o filósofo e 0 matemático escrevendo The mathematfcaƒ anaysís of ogic 1848 em defesa de seu amigo mais tarde publicou um livro sobre Álgebra de Boole chamado An investigaron of the laws of thought 1854 e em 1859 escreveu Treatƒse on dífferentíal equa tions no qual discutiu o método simbólico geral O trabalho de George Boole foi ampliado por Lewis Carrol 1896 Whitehead 1898 Huntington 1904 e 1933 Sheffer 1913 e outros Este período de desenvolvimento da Lógica culminou com a publicação do Principfa mathematica por Alfred NorthWhitehead 1861 1947 e Bertrand Russell 18721970 que representou grande ajuda para completar 0 programa sugerido por Leibniz que visava dar uma base lógica para toda a Matemática A Álgebra deBoole embora existindo há mais de cem anos não teve qual quer utilização prática até 1937 quando foi feita a primeira aplicação à análise de circuitos de relés por A Nakashima que não foi bemsucedido pois ao invés de desenvolver a teoria já existente tentou desenvolver a Álgebra Booleana por conceitos próprios Em 1938 Claude E Shannon mostrou em sua tese de mestra do no Departamento de Engenharia Elétrica do MIT Massachusetts Institute of Technology a aplicação da Algebra de Boole na análise de circuitos de relés usandoa com rara elegância o que serviu de base para o desenvolvimento da teo ria dos interruptores O assunto deste curso ainda que elementar visa mostrar as aplicações da Álgebra de Boole ou Algebra Lógica não só no processamento automático de dados computação como também na automatização da produção industrial mediante a utilização desta teoria aplicada aos fluidos 12 INTERRUPTORES 1 fi T É aê lrIälrrrfHliiiiiiiiêiiz É r â z F É 1 1 I 1 T ä P i Í 1 H i 1 f Por conveniência representaremos os interruptores da seguinte maneira 3 fz Neste caso somente conheceremos o estado do interruptor se tivermos a indi cação de que a 1 ou a 0 Conhecendose o estado de um interruptor a pode remos denotar também por a qualquer outro interruptor que apresente o mesmo estado de a isto é aberto quando a está aberto e fechado quando a está fechado Um interruptor aberto quando a está fechado e fechado quando a está aber to chamase complemento inverso ou negação de a e denotase por a Sejam a e b dois interruptores ligados em parae0 Numa ligação em parale Io só passará corrente se pelo menos um dos interruptores estiver fechado isto é apresentar o estado 1 Denotaremos a ligação de dois interruptores a e b em para lelo por a b Então a lí Sejam a e b dois interruptores ligados em série Numa ligação em série só passará corrente se ambos os interruptores estiverem fechados isto é se a b 1 Denotaremos a ligação de dois interruptores a e b em série por a b ou simples mente ab Então abi 3 b ab Assim considerando os estados possíveis de serem assumidos pelos interrupto res nas ligações em série e em paralelo podemos notar que 0O O CD D CJ 01 10 11 ab Uaa 1 Q DIDÇj Í Chamamos interruptor ao dispositivo ligado a um ponto de um circuito a3 elétrico que pode assumir um dos dois estados fechado 1 ou aberto 0 Quan Íz a 0 a a do fechado o interruptor permite que a corrente passe através do ponto enquan a 1 1 a to aberto nenhuma corrente pode passar pelo ponto I Todas estas equações podem ser verificadas priado As ligações de Fiepresen taçao 8 aberto e a fechado UAC a 0 Oocrco 0 1a desenhandose o circuito apro a b C são a b Cl 8 8 b 3 c respectivamente Os circuitos estão ambos abertos se a 0 ou b c 0 e estão ambos fechados se a 1 e b 10u c 1 logo suas ligações são iguais Então abcabac As ligações de l lr B di Hfl são a b c e a b a c respectivamente Oscircuitos estão ambos abertos se a O e b O ou c 0 e ambos fechados se a 1 ou b c 1logo suas ligações são iguais Então abcabac Vejamos alguns exemplos 79 Exemplo Determinar a ligação do seguinte circuito Solução a rza1 1 n p b c n p 29 Exemplo Desenhar os circuitos cujas ligações são al DD1rl bll Iv Soluçao al vl v D QD 3 3 um vi Áz 1 gv s 2 zr ã 1 fr rqfliniiaiiurvmz bl EXE RCÍCIOS 1 Dar as expressões algébricas dos circuitos desenhados al 1lí1 Ç b Y 4 7 Z xani1 l 4 r b c ai Y l l l Z V i r t w z l e o X fl 1it z a ih T7 añ Zz b 7 í a z c b 9 hl l 3 b 3 b a b C J a 3 b b dzc b d 1 lll b 1 a c 4íI i 1 j l r L a b c l 2 Desenhar os circuitos cujas ligações são dadas pelas expressões alrqrl blmDQr imnpq dllvlü el f f fl lrqllpql gl lDqlrqrl hiabcabcabc i pqsrrs qprss l Atençáo O leitor não deve passar às páginas seguintes sem que se sinta perfeitamente capaz e desembaraçado nos dois tipos de exer po e os erros cometidos cícios das seqüências acima Tente de novo marcando o tem l 7 i 13 CONJUNTOS Sejam a b c conjuntos de pontos tomados num espaço E dado Na fi gura abaixo o retângulo é o nosso espaço E e as figuras internas são os conjuntos 22 8 a 0 1 23 fvvzišé sv v av 1 rf f s r H a c l a b c E a b c l a b c 1 4 i vl V â i 7 1 ffz1Í1 zÍÊÊlI 1 i1zzzéfaàefz z1ezrfff1 zzff 1 azízrrzzaí ffzrTérff ze l L fzfÇ I J z jIzfƒI1 byJ Í l zií7šífófiëflfëf 1 Í4äÍ22fã ff7z l 1 zõéóíwuzXz z l f f 1 if ffz f 3 b 1 ffíz4fãÊfÉaÃáçáfefâf 1 f ííífízfffzzzf C ÊsliÉis763íÍirfé Í ÍÍIfíí55 1z J li vfzzíyzfZzfzyíztfááifz fft64 Iízfl1iyfi if ff fx mà zvzyíyfzf m1 F z 7 z ff 1f l 5 fffff fmIF Í z f fi2fí6fffzz zrz f fzz zfzzz 1 a Í 1 zƒfz j Vf 7 zy1 ol z z r J I r l C ll fÂÍfÍ 1íT Pféiieííâ 2 Íz 3f f fr f 3 br C K f Í T 7zf 1 Ff m T T 7 T ll I 1 z 1Ézz6fgÍff ii ífz 2ízz ls x 1Íf se W Denotaremos por a b o conjunto de todos os pontos que pertencem só ao conjunto a ou só ao conjunto b ou a ambos Dizemos que a b é a união de a com b O conjunto de pontos comuns a ambos isto é que pertencem a a e b será denotado por a b Dizemos que a b é a intersecção de a e b que pode ser deno tada também por ab l l ø 1 Í A 1 i p l J i l a b a b a b Seja a o conjunto de todos os pontos do espaço considerado que não per tencem a a Dizemos que a é o complemento de a Chamaremos conjunto vazio e o denotaremos por 0 o conjunto que não contém pontos denotaremos por 1 o conjunto de todos os pontos que é o conjun to universo 7 7 7 z fézff1 5f11Í K fi Í 1 J I f Á z l rfí irá ar l r l 221 5 ff7ff1íí zf íf12íázgzfé y rfigzfâ 1 ffyzlz fé2 V z zaa6fruz s Xlff 3 z Z ZÍ4 1 Á u 1 x Ls tQ vt S c f Para dois conjuntos quaisquer a e b do universo 1 valem as igualdades Podemos verificar sua validade construindo os diagramas apropriados por exemplo pelos círculos de Euler ou diagramas de Venn Outros resultados podem 00 01 10 11 aa Q oo zo ab a0 a1 mU ID m0Jm 1 a ser obtidos para três conjuntos quaisquer a b e c 19 Exemplo UmC3 0 1 Mostrar mediante diagramas apropriados que Solução š É a C b bcaba 1 c mC3UQCDGO 8 2 is 2 lliifl71flii ii 29 Exemplo Í Solução 8bCl abac Q 4 Q F Cl l I D Cir Dr pqr llustrar pelos cfrculos de Euler a expressão pr pqr I O I É m m Á ii lllli É a DF m í a bc Will 3P Exemplo C É O i Dar a expressao da região hachurada no diagrama l a iiIiir zjiilÊlii ilãrrlifliii llllljflil lllilili viii ll liliiliiir r ill mi l z1 4 lí illll 1 S0lUã0 X V Z xr yr Z 24 a b 3 C i ii J i 1 Í ir 1 1 Lfl F i I iii ll il âi iili iiiç l fl il fz il ÉLi li i fiz P iii 1 lgie il iiI lili rlil i 1 ilirií lifoi llli i ll i lll i iii l l ÍiTFZFÊÍá EXERCÍCIOS 1 Desenhar os diagramas de EulerVenn para mostrar alJq bl i1q cl piri dl i1ilr el li2qlr fl lDqlr 2 Dar as expressões correspondentes aos conjuntos hachurados jlliliilllllllllll W ill l lliiliiilillll l ll 7 7 A1 Í m mm ígÉE 5 I í í 3 Usando círculos de Euler mostrar que al lrqli ci bl ilirilii cl DlP 14 Pnoeosiçoes oo Chamamos conceito primitivo aquele conceito que aceitamos sem defini ção Enquadraremos neste caso o conceito de proposição G D0Í3flÍ0z 0300 def niremos Entretanto nada impedeque conheçamos suas qualidades lembrando que proposçáo é uma sentença declarativa afirmativa e que deve exprimir um pensamento de sentido completo podendo ser escrita na forma Slmbvlwã OU flfl linguagem usual Então são proposições a tg L 1 b3rr o c O México fica na América do Norte Dizemos que o valor lógico de uma proposição é a verdade 1 se a propo sição é verdadeira ê a falsidade 0 se a proposÇã0 É fãSfl POI 0BmPl0 a O Japão fica na África à bl 0 BWil Qaflh0U 3 CPa 9 M99 de 1970 M Uma proposição não pode ser simultaneamente verdadeira e faIsa 27 O valor lógico da proposição 8 é a falsidade 0 9 da Df0D0SÍÇã0 bl É 8 verdade 1 As proposições podem ser simples ou compostas Proposição simples é a que não contém nenhuma outra proposição como parte integrante de si mesma lndi caremos tais proposições por letras minúsculas de nosso alfabeto da seguinte forma p Carlos é careca q É dos carecas que elas gostam mais O número 16 é quadrado perfeito log 1 0 Ul IU I p o no I I A proposrçao composta e formada por duas ou mais proposiçoes re aciona das pelos conectivos e ou e se então ou impIíca Serão indicadas por letras maiúsculas P O R Exemplo 4 Sejam p 1 2 3 q 2 É 1 duas proposições no caso ambas de valor 1 Podemos formar as proposições compostas Ppq123e2afi1 O pq123ou21 R pq123implica21 Observações a Quando for conveniente indicar que uma proposição composta P é formada pelas proposições simples p q r escreveseP p q r b As proposições componentes de uma proposição composta podem ser elas mesmas proposições compostas A c As proposições compostas sãotambém chamadas fórmulas proposi cronas lndicaremos o vaor lógico de uma proposição simples p por Vp Assim se p é verdadeira Vp 1 e se p é falsa Vp 0 No caso de uma proposição composta P indicase por Vp Nas proposiçäs abaixo p O sol ê verde Vp 0 q Um hexágono tem 9 diagonais Vq 1 r 2 é raiz da equação xz 3x 4 0 Vr 0 141 Princípios fundamentais da lógica matemática a Princrjoio da Nãocontradição 28 l 5 T bl Princiivio do Terceiro Excluído bl Ppqf Toda proposição ou é só verdadeira ou só falsa nunca ocorrendo um tercei ro caso T T P q i f li 0 f De acordo com esses principios podemos afirmar que toda proposiçao K Í 1 1 l admite umeum só dos vaores 10 lã ii 1 1 O zç O O i H Í Í Í WÍ Í Í 1 Chamamse conectivos lógicos palavras ou expressoes que se usam para for T 1 ii 1 f q 1 H 1 li ij li l mar novas proposiçoes a partir de proposiçoes dadas Damos abaixo algumas pro 2 0 0 À 1 i Q posições compostas por diferentes conectivos grifados T J r P O número 4 é quadrado perfeito e o número 3 é impar l 3 0 1 l 0 I p O O triângulo ABC é retângulo ou isósceles É F T Fl Se João estuda então sabe a matéria 1 4 1 0 À 1 1 il U1 e O e ga 1e o f rfffff 7 142 Tabelaverdade ir lr 6 i 1 o z 1 T q Pelo Principio do Terceiro Excluído toda proposição tem Vlp 1 ou F T 0 7 Ê 1 1 E O I ff i 1 L fif 0 fa11i1 11 Ê i L eu ll i O sp 1 1 1 Apresentaremos sem demonstrar o seguinte teorema ii l i Nas composições o valor lógico de qualquer proposição composta depende Í ç o número de proposições componentes unicamente dos valores lógicos das proposições simples componentes ficando por 1 eles unívocamente determinado Usaremos como meio auxiliar na construção das i tabelasverdade o diagrama da árvore que se vê ao lado das tabelasNasituaçao i Exemplos ç atual os números que aparecem na primeira coluna tem apenas a finalidade de a Dada pg n 1 e a tabemverdade terá 21 2 unhas indicar 0 número de linhas para cada exemplo apresentado T T s bl Dada Plpq n 2 e a tabelaverdade terá 22 4 linhas Para as proposições compostas veremos que o número das componentes D cl Dada Plpqrl n 3 e a tabelaverdade terá 23 8 linhas simples determina o número de linhas das tabelasverdade Exemplos o al Plpql exe Rcrcios l Í i l í FfÊ O Q t 1 Determinar o valor lógico 1 ou Ol de cada uma das seguintes proposições 10 E O 1 al O número 11 é primo Vla N O TJ O fi i Q dl sec2 32 1 tgz 32 Vd l g bl senz 25 T cos225 1 Vb i 3 1 O 1 1 cl O hexaed ro regular tem 8 arestas Vlcl l 4 T 1 1 q 1 el iogaâ 1 vie i Teorema O número de linhas de uma tabeaverdade é dado por 2 onde n é I sflfiuuffIlv l l rfzzfffiufz l I l l i l xuuIIII l 1 J J l J il i f loga1 0 f z gi semi 30 CQS2 30 2 h senz g cosz g 1 i log 2 3 log 2 log 3 j Todo número divisível por 5 termina em O l O par x é igual a x Vlgl Vlhl Vlíl Vlil V zz lO dl ll l m Ç 2 1 š mg Operoçoes Logicos sobre ol cosxl cosx V0 vipi z Proposiçoes Dl 2 0 Escrever cinco proposições de valor lógico igual a 1 Escrever cinco proposições falsas Estudaremos as operações do cálculo proposicional também chamadas operações lógicas 21 NEGAÇÃO Seja p uma proposição Denotaremos a proposição composta pelo modifica dor NÃO por p e lêse não p Então Vp O falsidade quando Vp 1 verdade e Vp 1 verdade quando Vp O falsidade O valor lógico da negação de uma proposição p é definido pela tabelaver dade ø que nos dá 1 0 0 1 Então dadas as proposições abaixo vem al p145 1 p1455 O VlDlO bl qt João é estudante O q João não é estudante 1 VlCil l 31 Outras maneiras de exprimir uma negação O valor lógico da disjunção inclusiva de duas proposições é definido pela Não e verdade que João é estudante tabelaVefdadei É falso que João é estudante 22 CONJUNÇÃO l A conjunção de duas proposições p e q é uma proposição verdadeira quando Vp f Vq 1 e falsa nos demais casos isto é só é verdadeira quando ambas as componentes forem verdadeiras Chamamos p 1 q a conjunção de p e q e lêse np e qn L D 1iD1 O O z O 1 101 EiE ee E i  3 1 111 Então dadas as proposições abaixo vem O valor lógico da conjunção de duas proposições é definido pela tabela É verdade 1 to qri ao oiol ET lL i rácz4 1 i l1 1 1111 zzlzzzz V il Então dadas as proposições abaixo vem al pzsen É i 1 1 qcos01 1 Vlpql l bl r ogz21 1 s 22 O Vr s0 23 DISJUNÇÃO INCLUSIVA OU SOMA LÓGICA l A disjunção de duas proposições p e q é uma proposição falsa quando Vp Vq 0 e verdadeira nos demais casos ou seja quando pelo menos uma das componentes é verdadeira Chamamos este conectivo disfunção inclusiva ou soma lógica denotaremos a disjunção de p e q por p Q 8 lêS62 D OU Q l1olo Q 11 al pTr3 0 1 J q936 1 1 Í VlDql 1 0 110 bpzí1 lol qz22 io Vleql0 24 DISJUNÇÃO EXCLUSIVA l vííÍíííÍííui1 íÍríÍ A palavra ou tem dois sentidos no caso anterior temos a disfunção inclusi va que exemplíficamos a seguir P Joao é estudante ou mecânico indicando que pelo menos uma das proposições p João é estudante q Joao é mecânico é verdadeira podendo ambas ser verdadeiras Joao é estudante e mecânico Por outro lado temos o caso em que isto não ocorre é disfunção exclusiva definida a seguir A disfunção exclusiva de duas proposições p e q é uma proposição verda deira somente quando Vp Vq e falsa quando Vlpl Vq ou seja quando p e q são ambas falsas ou ambas verdadeiras Denotaremos a disjunção exclusiva de p e q por p q e lêse p ou q mas não ambas zfzrz l J 33 I l ului çl l tt i l l il J l i J J O valor lógico da disjunção exclusiva é definido pela tabelaverdade U Q O O ii E O 1J ao O ú Í á O Então dadas as proposições abaixo vem al prr3 q32 Vpql1 bl ptr3 qsen2 1 vli1ilo 25 coNoicioiiAiz r 0 ll 0 0 g2 Í ll P ÇDQQÀ CUS 2 ii l Í Í O Vlpql0 26 BICONDICIONAL l O bicondicional de duas proposições p e q é uma proposição verdadeira quando Vp Vq e falsa quando Vlpl VCll Denotaremos o bicondicional de p e q porp q e lêse p se e somente se q Convém notar que o bicondicional não é uma operação original mas dupla aplicação do conectivo l O valor lógico do bicondicional de duas proposições é definido pela tabela verdade V l i i ip qq OO OO OO i fz f r z z z a fzzz ii In í 1 O condicional de duas proposições p e q é uma proposição falsa quando ii l fl zz Vp 1 e Vq 0 sendo verdadeira nos demais casos Representase o condi V cional de p e q por p q e lêse se p então q A proposição p é chamada an EÍäz dadas 35 PYODOSÍÇÕBS flb3l0z Vem tecedente e a proposição q é o conseqüente do condicional 3 p í é um número nacona 1 1 valor lógico do condicional de duas proposições é definido pela tabela Qí 1 ll verdade WP ql 1 z bi rIT E 2 ioi p q ií 1 iii ca ci niL Vipql0 Então dadas as proposições abaixo vem bl P T ff O 1ul í r 1L zbunnl o c Daremos de maneira breve a ordem de precedência a ser observada entre as operações estudadas que é a seguinte al c al pztgg1 1 d qsen0O 1 VÍP ql 1 a identificação da forma da proposição composta conforme mostramos a seguir 3 Esta ordem de precedencia entre os conectivos tem a finalidade de permitir Assim p q r é da forma bicondicional a proposição p q q r C 3 2 ou sen90 tg45 é da forma condicional ao passo que p lq C1 rl é composta por disjun d se l 1 I O então sen90 1 ção Portanto a correta colocação de parênteses quando for o caso é de extrema e 3 1 30 z 3 importância P 1 f 1 4 i 3 še gl tgn 1 se e somente se senrr 0 h Não é verdade que 12 é um número impar EXERCICIOS 1 1 2435 Á it jl sen 0 O ou 1 Sejam as proposições p João joga futebol e q João joga tenis Escrever na Iin guagem usual as seguintes proposições A 5 Sabendo que Vp 1 e Vq 0 determinar o valor lógico de cada uma das a p q proposiçoesz bl ia Q al ia Q cl iv q bl rq dlri elri el lpl dl is Q fl lp ql z el pai fl D lp ql 2 Dadas as proposições pMaria é bonita e q Maria é elegante escrever na lingua H gem simbólica as seguintes proposições 6 Determinar Vp em cada um dos seguintes casos sabendo que cos 0 1l al Maria é bonita e elegante al Vlql bl Maria é bonita mas não é elegante A b Vq Çl Não é verdade que Maria não é bonita ou elegante Cl Vlql dl Maria não é bonita nem elegante dl Vlql el Maria é bonita ou não é bonita e elegante ç 9 Vq f E falso que Maria não é bonita ou que não é elegante f Vq OOOOO DCDCDCDID 8 Vlp ql 0 Vpq 0 Vlpil VlFil vlwral Vipql 59o 3 Classificar as prapasicõss compostas abai0 como soniuncão disiuflsäo con 7 Determinar vlpl e vlql em cada um dos seguintes cases sabendo que dicional bicondicional ou negação 3 Wp q 1 al lp 1 ql bl Vlrsral 1 blpqrl 0lVlPQl1 clpqrl dlVlDQl0 e Vlrilo e Vpq0 e Vpq 1 s Vlpql1 dl i2qr t fl lDolrsl hl Dlq rl il lrlarl1s filPf pqr bl lrrrs t cl lp lr bl senrr 0 e cosir 0 sl 4 Determinar o valor lógico de cada uma das seguintes proposições dl CI lp S el327 e 551o llpHllqpl fl lDCillrrs ll ll ei lp qq r 5 V 8 Para que valores lógicos de pe q se tem Vlp ql Vlp q gn D Q rn S z 9 Se Vp Vlql 1 e Vrl Vlsl 0 determinar os valores lógicos das seguin tes proposições úfnfàflfrflfiwiwiiduiudw i l OÍÍÍÍÍO 2 l 1 l i r l l 9 Ci lo sll i lh ila lrsll il lDfllqsl l f l il D lq sli lrsl ll Cl lllSllDqll ml lPlllirlls A que os dados forem insuficientes ãllJlQl b d Vl0 bi ip Lii fff Z V 0 Construçoo do Tobeloverdode Cl D q r s sabendo que VlDl 0 dl D Q sl sabendo que Vlpl 1 1 al lp fl q sl sabendo que Vq 0 fl D rl s sabendo que Vlrl 1 Determinar os valores lógicos das proposições abaixo justificando os casos em i 3 9 p r 5 sabendo que yr 1 Para se construir a tabelaverdade de uma proposição composta dada proce h lp 1 ql r sabendo que Vq 1 dese da seguinte maneira Ê lp fll p pl Sabend que Vlp 0 al determinase o número de linhas da tabelaverdade que se quer cons ll D Cl rl sabendoque Vq O e Vlrl 1 trur J bl observase a precedência entre os conectivos isto é determinase a for ma das proposições que ocorrem no problema c aplicamse as definiçoes das operaçoes logicas que o problema exigir l l i l r rf I I fl e i ij 1 l i z i i l l l l Vejamos alguns exemplos 19 Exemplo Construir a tabelaverdade da proposição Ppq p q Solução J çp 11iDqlPql cio CJO OC3 OOO eo Considerando as linhas da tabelaverdade temos Pl00l í Pl01l P10l j 38 Pl11l o e para todas as linhas da tabelaverdade vem P00011011l O conjunto V 00011011 é o conjunto de todos os valores possiveis de serem assumidos pelas proposições componentes de PlPCll e considerando que a cada elemento de V corresponde um e somente um dos valores de 01 dire 1 mos que Pieeiz v 01 l ou seja a tabelaverdade de Ppq é uma aplicação de V em 01 O mesmo se dá A â z l T 1 com proposições compostas por um número maior de proposições componentes S 5 l 29 Exemplo Construir a tabelaverdade da proposição HmwommpY 1 i Solução 39 Exemplo Construir a tabelaverdade da proposição 1101 A HmmdDrqf Solução lp T I q r r p r q r pr q r ser fr f f Cl l L cocc oooo CJOOO CDOOOH OIOQOOO O L l zz zzzzz r No caso de três proposições componentes temos i O Pl000l Pl100l O O P Q pq mqY arco lqttm wqYhDYl O Pioo1i Piio1i A O OOO QaaaL L 1uinq lurm V P010l P110l P011l1 Pl111l V P000001010011100101110111 01110010 l O uiI d niÁ 1 1 i i l O OC A o T J Fazendo V 000001010011100101110111 ou seja V é o conjun procedendo de maneüa anáwga ao exempm anteñor temos toxde todos os valores possiveis de serem assumidos pelas proposiçoes componen P00l Pl01l P10l P11l ss Q Há outros métodos para construção de tabelasverdade porém nos restrin f ppq ip q q r D r 40 giremos ao método utilizado nos exemplos dados P tes de Ppqrl mediante raciocinio análogo ao caso de Ppq temos HmmdflWQ0 Então a tabelaverdade de Ppqrl é uma aplicação de V em 01 ou P00011 01 1 1110 49 Exemplo uIÚddddul i l Oííëííí J fI Enño determinar PO0011011 consiste em construir a tabela verdade para a É V P proposição dada e responder na forma indicada nos exemplos dados Cn5tr a tablaledade da pp5Ça l 41 l l III Q Soluçao F zzzz M1 rf 1 1 i ufrud i i P fi ffrrriHallfl lplefllfl rCDOC3O OODCD OOC3 QQa QzhO DOOe n diiz I r QIgl niJ F Q IL O ca O íí I Neste caso temos P000l P001l P010l P011l P100lP101lP110lP111l1 Pooooo1o1oo111oo1o111o11111111111 Quando o valor lógico de uma proposição composta for sempre a verdade 1 quaisquer que sejam os valores lógicos das proposições componentes temos uma tautologia Quando o valor lógico de uma proposição composta for sempre a falsidade 0 temos uma contradição E finalmente quando na tabelaverdade de uma proposição composta ocorrem os valores 0 e 1 temos uma continfincía ou indeterminação EXE RCÍCIOS 1 Construir as tabelasverdade das proposições seguintes al lDll O bl loil cl PQPq dl islçiil el lnqliq fl aiai ia sl liilrii hl lrqlpq Íl DIqr jl prqr ll pplqr ml lDqrllDlqrl O 2 Determinar P00011011l em cada um dos seguintes casos el Pim lDql bl Pim ri i i el Plan lp il lp ql dl Ppq D ql lp ql el Pliml lp ql lp q Determinar P000001010 011 100101 110111 em cada um dos seguintes 035052 al Ppqrl is r q I I I bl Piqrl p ri pr cl PlDqrl ln ql lp rl Determinar P101l em cada um dos seguintes casos al Plpirl 0 lq rl bl Ppqrl ln rl la rl cl Ppqrl lr lp qll lr lp dl Ppqrl ln Q rll lp f Cl Sabendo que Vlpl Vrl cada uma das proposições al ia ri r s bi ieiizfi cl DqlDrls dl lpqllrslDs Sabendo que os valores lógicos das proposiçoes p q r e s sao respectivamente 1 1 O e 0 determinar o valor lógico de cada uma das proposiçoes al Drirlr bl lDsl srll cl lrDllDrl dl lprllDrl Dizer quais as proposições que satisfazem às tabelas verdade abaixo bl 7 cl Qi í 1 e Vq Vlsl 0 determinar o valor logico de Bariri Brpri BIGP prra Crri Ciri qip Dpq Dpq nenhuma delas E nenhuma delas E nenhuma delas 8 Determinar as proposições compostas por conjunção que satisfazem a cada uma Í só das tabelas verdade indicadas l ioo L p ql A l B C W ñ D E CD CD ÍÍ QI e CD e CDC3 3 úl ÉCD É 1 CD L i 9 Determinar as proposições compostas por disjunção que satisfazem a cada uma das tabelas verdade indicadas JI 7 iun ÍLY l 1 P Í L zi Al B i C ih 3 Í4lF Q L3Q C s CD CDCD A4iz Lni L CD CD CD l 1 i xl L 10 Determinar as proposições compostas por condicional que satisfazem a cada uma das tabelas verdade indicadas notre ff r rf i 1 P T Q AQQ O Aab ir CDCDCD e Lie1 A CD4 CDCD li a p q Ap q Ap q 11 Determinar quais das seguintes proposiçoes são tautologias contradiçoes ou contingências alDDql bl pqlpql el nalqlqroll dl lprolqlrn el iilrql fl i1qlpral el Dlicilr hl pqlprirl il lClDllDCil ff rbd AT B i Cl DT E i zl jJ uvu i É nl l il X fl l l l l i Ú 1 1 fl ll l J 46 i J l Reloções de lmplicoçõo e de l I A 0 quvoenco O estudo das relações de implicação e de equivalência de grande importân cia na Lógica será feito de maneira suscinta como convém ao nosso estudo Antes porém definiremos alguns conceitos introdutórios 41 DEFINIÇÕES a Duas proposiçoes sao ditas independentes quando em suas tabelasverdade ocorrem as quatro alternativas L Exemplo ne flOC mí bl Dizemos que duas proposições são dependentes quando em suas tabelasverda de uma ou mais alternativas não ocorrem Exemplo 1 ff ff mf 7 po q p OIO s1 Não ocorre a alternativa 10 l entrepeqp IsJL lr Neste caso dizemos que existe uma relação entre as proposições p e q p Examinaremos as relações simples quando uma alternativa não ocorre e as rela ções duplas quando duas alternativas não ocorrem 42 RELAÇÃO DE IMPLICAÇÃO Dizse que uma proposição p implica uma proposição q quando em suas ta belasverdade não ocorre 10 nessa ordem Notaçâo p i q Observaçao importante Não confundir os símbolos e L pois enquanto o primeiro re presenta uma operaçao entre proposições dando origem a uma nova pro posição o segundo indica apenas uma relação entre duas proposições dadas Exemplo Verificar se pi q p Solução 3 Q r fl 31 1 ÓQ Comparando as tabelasverdade p e q p verificamos que não ocorre 10 nessa ordemll numa mesma linha Portanto pí q p 43 RELAÇÃO DE EQUIVALÊNCIA Dizse que uma proposição p é equivalente a uma proposição q quando em suas tabelasverdade não ocorrem 10 nem 07 Natação p q Leis comutativas al D Q fi D Observacão importante b p q q p emplo Verificar se p q í p q ução pq ln ril L L L CDO OOC3 DOO CDO Vale para os simbolos r e a mesma observação feita para Ê É À e al ii 1liqlii co oLz l l l bl Verificar como exercício Leis associativas CJ ai Ê Ê Comparando as tabelas verdade de p q e D GI l VflfICflm0S Clie 030 orre 10 nem 01 numa mesma linha Portanto p q D Q l al L p De maneira pratica verifica se que duas proposiçoes dadas sao equivalentes qflfando suas tabelas verdade forem iguais 4 4 EouivAiÉivciAs NoTÁvEis pla negação D l p 1à J is idempotentes 3 ln ii i z ailqrllirqlr binlqrllicir TT Ê Í r qr pq pq r I m7 i i l 1 i l i l l if Ç l l l l l Lia l CDOCDCD oooo c SQLe ciniluuuflíiflwnllÔunflc IÃczfl b Verificar como exercicio Leis de De Morgan al ln il P q bl lirql 0 Qi ln ql al D1 É ql oc OCD Lfi bl Verificar como exercicio DOO ÇA Destas tabelas tiramos as seguintes equivalências notáveis Leis distributivas alp lirlli qlp l blpm rMpqllpn E I qr lqr E O zzi lp ql i iq Dl iq pl ln Ci 4 5 PROPRIEDADES o T ca o o nf O O O O A condição necessária e suficiente para que p í q é que o condicional p q seja uma tautologia CDO O nI nl C QDO DOO CJOCD Í O zinL o i xlanl OC 1 Demonstração luÃlnnlíí oo OIO 5 co oo Iai úN i bl Verificar como exercicio Bicondicional p q í p q q p A condição é necessária p í ql p 1I ql Se p í q não ocorre 10 logo o condicional p q é uma tautolo gia A condição é suficiente p L q p í ql Se p T q não ocorre em sua tabelaverdade a alternativa 10 logo p q cqd bl A condição necessária e suficiente para que p i q é que p q seja uma tautologia pHi Di i0 lnql cir Demonstraçãoanáloga à anterior OO Qa QQin EXERCÍCIOS i Dizer se entre as seguintes proposições lráimpIicação ou equivalência quando tomadas aos pares Condicionais 6 P Q blq0 c pq dlqi2 elo Q b q p contrapositivo c q p reciproca do condicional d p q reciproca do contrapositivol L E qnmep riipi Mostrar que a q p q bl qliir C Dq não implica p q d pnão implica p q el DQlp oo oci o cado 7 77 f p Verificar mediante tabelasverdade as seguintes equivalências z iif bi lp qll É p C ffíI dliiiqíPl 3 pqeI1llDl f pqríCfP gpqplíD hipliqlP i iiJ1DCl Í qpqíDQ ii ipqllifli miipqllDflfDQf nl IDqllílíffl Dada as proposições abaixo escrever as proposições equivalentes usando as equivalências notáveis indicadas al Dupla ne93Çã lp 1ll lli qll P Q bl Leis idempotentes P i ip ql Dql ipi lpqll C Leis comutativas lp ql ls rl IP5l p Sl Ip I fl d Leis de De Morgan lo flIl ip q r sll lo ql f Q Leis associativas r IP ql pr IfS Irll iipq lprl lDsl f Leis distributivas s lp ql piiq fr irsll g Contrapositivoz D Ci rl D ql r iv1llrsl h Condicional D lq rl D ci rl lp fil il B icondicional llnql l1i ill llp ql rl lrr si ril l 1 5 l l l l l l E J l i 3 i i l i J 5 Argumento dlido 51 DEFINIÇÃO i Chamase argumento válido toda seqüência de proposições pj pz pn1 n E N na qual sempre queas premisms pj p pn são verdadeiras a conclusão pn1 também é verdade e tal que a conjunção das n primeiras implica a última P1 Então para testar a validade de um argumento procedese da seguinte ma al constróise a tabelaverdade de pj pz p3 pn tb constróise a tabelaverdade de pn1 V Cl comparamse as tabelas se na mesma linha ocorrer 10 nesta ordemll não há implicação m e o argumento é falho se na mesma linha l não ocorrer 10 haverá implicação il e o argumento é vál ido Observação A seqüência das proposições pode apresentarse nas seguintes formas P1 P2 Pa Dn Dn1 P2 Pa Dn í Pn1i I p1rp2rp3r flrpflr pIII1fl 19 Exemplo Testar a validade do argumento p q q p Solução Temos ppq l323Cl V P330 Devemos verificar se nas condições da definição pl pg í p3 isto é lp fil Qí D Procedendo conforme o critério já estabelecido temos u Q lplol Q ligqlql P 1 o OO n Ê Q Na 29 linha as premissas são verdadeiras e a conclusão é falsa Na 4 linha as premissas e a conclusão são verdadeiras A 2 linha contradiz a definição de validade sempre que as premissas são verdadeiras a conclusão deve ser verdadeira Ocorre 10 Portanto pql qgàp e o argumento é falho O leitor deve ter notado na tabela a repetição da coluna correspondente à última proposição da seqüência p para evitar que na verificação da ocorrência ou não numa mesma linha dos valores 10 não se incorra em erro verificando a implicação iiiiiq em vez de verificar lo ql Q o que seria a forma correta 20 Exemplo Testar a validade do argumento pq pl q Solução Devemos verificar se nas condições da definição lDCll Díq Construindoas tabelasverdade correspondentes temos ri ci pZiq lrnli oo o OOO s Neste argumento somente a 29 linha tem ambas as premissas verdadeiras Como a conclusão é também verdadeira não ocorre 10 Portanto pq p q e o argumento é válido 52 REGRAS DE iNiERENciA As regras de inferência são argumentos válidos simples União U É a implicação D q 1 p q Modus Ponens MP P í qi P 56 E É a implicação p q p í q Modus Tollens MT D r Ci fi 1 l T É a implicação p ql q í p sl Adição Al D E a implicaçaoz í D q ri D Ci l i l i Simplificação IS pá q E a implicação p q í p Silogismo Hipotético SH pHqqír rzz É a implicação p q q r 1 p Silogismo Disjuntivo SD D CI D l III l I ii q É a implicação p q p í q Regras do Bicondicional BIC al D pqiq p É a implicação p q q p ip q pq À bl fípzzz za zz z E a implicaçao pq pq qp Dilema Construtivo DC Pi i I r qzrz sz É a implicaçao p q r s p r q S qs Dilema Destrutivo DD DHi rs qs ef b se É a implicação lp ql lr sl i IQ sl ri p r 57 l l l iI Ji l i l l l J l J Ú i l l 3 l i Dupla Negação DN Í I Regra da Absorção RA ii 5 É a implicação p q f p p q ilrq Simplificação Disjuntiva S J I J É ri l Úfix CD CDe ro O Oo i l i i ea L i z z xw v lhr OO 58 t l l D pp ou p É a implicaçao pl p ou p í p pr I E E a implicaçao pr pr í p EXE RCÍCIOS 1 Testar a validade dos seguintes argumentos ëlllílQ bltrrt55 pq ii 1 2 Dados os conjuntos de valores lógicos iAi I iai I ici ioi CD qual deles torna o seguinte argumento válido J l i T f f f f fea D j Q l premíssal premissa ji conclusão HJ 7 ici IInl i O O zz l z z i Z l 3 Dado o argumento I P li YPTTTP l ÍW E CL p q 1 premissa premissa conclusao l ii zz z zi 1 z l I i i i 1 i 1 1 1 oo OO oo l l w l l l qual dos conjuntos de valores lógicos abaixo torna esse argumento válido iAi 1 iaiz icil ioii me 7 1 ff 4liff fff 4 3Q 4 Mediante o uso de tabelasverdade testar a validade dos argumentos al ri D T lrl ii bl Dq pq ieq C rlpr lo ql ql dl 6 b c b a a el nqli1iriJliDilir fl iriririrCif 5 Dar os nomes de cada um dos seguintes argumentos al Cidle ii E 59 bl fflbdl iii f ci lp ql lq r lp ql qr dldabl ab e r5 lsl r fl la bl ca 6 labl lca gl bc bcd hl ab A bc ac i ai b c a bc ab il albc 3 izi z ll a c d 9 ldel ac llo ill r l I nla c 6 T 61 ol la ut bl c lã bl C Disltrl ltrl s l Completar cada um dos seguintes argumentos validos al lr Dl tm Q lql bl albc af cl la bl b cl ab d ar br C e aíbc ard ml fliDql i i iNø u u 61 PROVA DIRETA Dizse que uma proposição q é formalmente dedutível conseqüência de s certas proposições dadas premissas quando e somente quando for possivel for 4 mar uma seqüência de proposições pj pg p3 pn de tal modo que i al Dn ë exatamente qq s E bl para qualquer valor de i i 1 23 nl Di ou é uma daspremissas Í f Provar r SI dadas as premissas J ou constitui a conclusão de um argumento válido formado a partir Í I S Q das proposições que a precedem na seqüência Escrevese P1 P2 pf ou izrzizDn1 lí Pnlql Pn1 Pnlflll i A proposição q no caso de ser formalmente dedutível chamase teorema e a Í seqüência formada chamase prova ou demonstração do teorema É 1 õ 5 cl ou seia q lql 63 Vejamos alguns exemplos zj q 19 Exemplo Provar s dadas as premissas 2 t q Demonstração 6 3 q z s Tecnicos Dedutivos 9P9Z mQQ1 fflos Justificação da passagem 4 I Q I 29 Exemplo Í 2tq 3 tr Demonstração l95 ralimÁadi4ä ui iz ix Ff U I D D É O0 róQr1m 5 LfblíúÊiihiiieàilitixA1ë4fuzos iefm4ir Justificação das passagens 4 ou sejas qq premissa premissa premissa Modus Ponens 1 e 2 Modus Ponens 3 e 4 cqd ou seja t q t í q conforme se pode verificar q pela lista das regras de inferência premissa premissa premissa s1 DN4 MT2 e 5 MP3 e 6 A 7 cqd 39 ExemPIo 1 I I Í t í q r ir 1 l Im 6 ou seja tq q tz Inicialmente por razões de conveniência passemos as proposições dadas za ara a forma simbólica Nosso roblema reduzirseá ao se uinte P 9 t ri tt fd 7 r ou seja lt rl t í r Provar a dadas as premissas I r v És 8 OU Seia r Í r s r 5 z ii É E5 Na indicação das regras de inferência utilizadas na demonstração de um teo rema MP 3 e 6 significam que a regra Modus Ponens foi aplicada entre as propo sições de n95 3 e 6 da seqüência o mesmo ocorrendo com as demais abreviações I l V 1 I Observações 1 i I al Qualquer tautologia pode ser incluida na seqüência após qualquer proposição 4i já colocada I Í i De fato seja oi uma proposição qualquer já escrita na seqüência e B uma tau 1 4 J T115 tologia É claro que o argumento ido pois sei Q 2 PÉ Of 5 fiz Iv Í I l 5 não ocorre 10 l í fi zz iii i 1 I gi l7ifiiif si i1X bl Se oi for uma proposição já colocada na seqüência e 3 for outra sentença tal que 3 í oi então seguindose a oi podese colocar B X De fato sendo B í oi temos B oi Logo ii â oi pode entrar na 24a seqüência por ser uma tautologia Mas zEB Logo or B pode ser inclui da na seqüência E finalmente podese escrever B pela regra do Modus Ponens v 11 Provar x O dadas as seguintes premissas l gil A 1 1 ab 2 b ic 3 c Demonstração ab V 535I nicr oo bneo MT 2 e 3 a MT1 e 4 DN 5 cqd 49 Exemplo Provar a dadas as premissas P9 I aíc crm mr i Demonstração a c opoiçn5niwio 3 CUUC1 c m m r r SD 3e4 ml DN 5 c MT2e6 a MT1 e 7 a DN8 cqd 62 PROVA coNoicioNAi 1 X 0 então X Y H Seja provar cri dadas as premissas p pz p3 pn Fazendo aconjun 2 X z V então X Z çao das premissas igual a P tratase de mostrar que é valido o argumento P 1 3 se z lí oz i isto é ígB Tratase de validar esse argumento Ocorrendo a 65 L 1 l C D I r validade temos P TÔ oz Bi ou P oi fi A letra grega 1 SODFB 0 simbolo do condicional indica tratarse de uma tautologia Princípio da Exportacao Para mostrar este principio utilizaremos a equivalência notável p q í p q Então temos Pllur5âe4awnPmmâàin a 5 í P oil 3 í P oz B Portantose P oiB for tautologia isto é se P oií B ou seja se for possivel deduzir B de P oi tam bém será uma tautologia a proposição equivalente e portanto P 15 la 5 é dedutível de P Dessas considerações seguese a técnica da prova condicional pa ra demonstrar a validade do argumento cuja conclusão tem forma condicional oi 143 introduzse oi como premissa provisória indicada por DD e deduzse B 19 Exemplo 1 z Provar r p dadas as premissas 10Q 2 r q Demonstração 9i91zi UQ É DCl P q p PP MP 2 e 3 MT 1 e 4 Prova Condicional de 3 a 5 cqd 29 Exemplo Provar c A d dadas as premissas 1 b c 2 d b Demonstrafio 1 b fc D š 2 ld b P 66 3 c r pp 4 C DN3 5W M1164 6 d PT De Morgan 2 7 d SD5e6 8 cd PC 3a 7 cqd 39 Exemplo Provar a Ab dadas as premissas 1 39 2 jígrhr I ab Demonstração 1 3 jg p 2 lg lI p 3 jb p 4 a g pp 5 3 j A 4 A9 Meias 7 Í9 hr EquivaIência2 9h As 9 9 h DN 8 Ui Mr7z9 1Lb soseio 12ab PC4a11 cqd 63 PROVA BICONDICIONAL I A r va p o de um argumento cuia conclusao e uma proposiçao da forma bicon erlslfäzlfialsa 5 semelhante a prova condicional com a diferenca de que é feita partes istintas Entao dada uma proposição Q 5 prmeO prova se oz fi memo ez 3 5e9uir PTOVG 59 5 oi concluindose pela validade do argu Exemplo Provar a v dadas as premissas t8 2 vt am 4 vm Demonstraçao 1 t a v i a m v m UOUU 3 pp rn MP 3 E 53 SD 4 e 78 V PC 53 78 V 3 V 12 DP MP 2 e 5b 3 MP 1 e 6b V 3 PC 5b 7b iaW Va U 8a 8b 3 V Equivalência 9 6 4 PROVA INDIRETA OU POR REDUÇÃO AO ABSURDO Observamos inicialmente que de uma contradiáo podese dedLi2I QUHÍQUEV P A proposiçao De fato seja a contradição p P B 0 Uma Pf0D0fl0 CIUHÍQUGY Temos cqd U U5 U um nI U um D D Un ff ff nu í f oiço A O É 45iooo Q 5flhaBb Q j r ij P1 Q cn U il I à i e I 1 1 4 ifi i xi 5 j ê 2 1 vá Ir Ii 1 C zz 11 É 1 r g ê J Seja agora provar a a partir das premissas pl pz pg pn seqüência essa que chamaremos P Consideramos as premissas P e oi e procuremos deduzir oi a partir delas isto é vejamos se P ai i oz A proposição oz é formalmente dedutível de f Poi se PozíaistoéPoiaMas 1 r P oi oi í P la oz Principio da Exportação Ora essa última proposiçãoconstitui uma tautologia se ocorrer a seguinte implicação P í la Hx isto éPi oicr oi crL a aioz a oi Pia e P aioi Então para mostrar a validade de um argumento por prova ou demonstra ção indireta introduzse a negação da conciusão como premissa provisória e de duzse uma contradição por exemplo q q 19 Exemplo Provar r dadas as premissas z zz 1pr 2 r q 3 lo ql Demonstração pr Pf9P91ñUÍõQ1õ š QE UTD Iíq ql p PD MP 2e4 De Morgan 3 DN 5 SD 68 7 MP1e8 Prova indireta de 4 a 10 cqd 1C1dfuff zururIdlV øvf u4e9 Observação l n 1 Ip q n 2 p q Equivalência n 1 t contradi ao r r pará Pf0V3 f P Da mesma forma como encon ramos a Ç I n 3 p q De Morgan n 2 l pp deremos encontrar a contradição q q para provar p como verem0S HO BemP 0 n 4 S 3 da D n ocurada ode envolver ou nao a nSm3 letra a seguir Isto e a contradiçao pr p n 5 q S n 3 proposição a ser provada 29 Exemplo Provar p dadas as premissas l r ooo 1 1 Demonstraçao 9I99 cio1 o5DDD Qš l aq 1 I 65 PROVA INDIRETA DA FORMA CONDICIONAL 1 Provar t dadas as premissas UUO DP DN4 MP2e5 SD1e6 U3e7 Pl4a8 cqd ri ê ÊI I É 15 Í l l E Para provar a validade de um argumento cuja conclusao e da füfmë 0ndicio 1 p S remis 1 nal p q mediante a demonstração indireta usamos P Q m P Exemplo Provar r q dadas as premissas 1 rs 2 qs Demonstração 5sssflsi ooof3olL firnU EXE RCÍCIOS 4 2 D CI Sa provisória ppl a seguir lp ql iwf eqflivalsflfiifl E P Q l 9d 5 dm 3 5 r r p q Na prática começamos pela hipótese H e pela negação da ÍGSE IT m premissas provisórias H T Provar P I Q W 1 2 I 4 P 70 kn i z za r 4 q r 2 Provar s dadas as premissas 1 t r 2 r 3 ts 3 Provar t s dadas as premissas 1 es 2 j 3ej 7I P D DD DP DN3 SD1e5 MT6e2 DN4 U8e7 Pl3a9 cqd Provar s dadas as premissas 11 PfV3f Í dadas 35 Pfem5535 1 PQf 2p 3tq 4 ts Provar r s dadas as premissas 1 sq 2tíq 3 tr Provar x y 5 dadas as premissas 1 3yi139 2 393y11y2 3 yf2 ou y5 Utilizando a demonstração condicional Provar a h dadas as premissas 1 afg 2i9h 3 Provar t s r dadas as premissas 1 r q 2 t 1 3 s q Provar q t dadas as premissas 1 s r 2 spi 3iQ 4 rrt Utilizando a demonstração indireta Provary 2 x y dadas as premissas 1 yy ou y 2ya2 ou 2 E 3 xy ou yx2 L Í IL z fi çI s z7 i J 5 T f Í n E umzz z J 1 ts 2ft 3 sf Provar e m dadas as premissas 1 sr 2 se 3 rm Provar t sl dadas as premissas 1 rb 2 tsr 3 bs 4 t Utilizando a demonstração indireta do condicional Provar p q dadas as premissas 1 lri r 2 str 3st Provar p q dadas as premissas 1 p q r 2 r Provar p s dadas as premissas 1 lpci r S 2q Utilizando um método dedutrvo de sua escolha Provar p q dadas as premissas 1 P q V I 5 1 2 r s Provar p r dadas as premissas 1ri 2 rq I 3 1 i 3 i cuzi J 3 i J i J Provar s dadas as premissas 1 pq 2 sp 3 qr Provar s dadas as premissas 1 pql lr Stl 2 D q r 3r Provar 2x 12 V 4 dadas as premissas 1 23y24 2 6y4 ou 212 à 3 2126 ou 2x3y24 4 a6 Verificar mediante as regras de inferência a validade dos seguintes argumen ÍOS I Nas demonstrações abaixo justificar as passagens indicadas al 1 2 3 4 DIOJ1 b1 2 3 4 5 6 r r al see gsg bl Si1Dlwilswi cl auulbilbalitalbi H pi rÍiql lp 5 pf S ñQflO cn ie P P l 0 cqd D er sr p I P 8 ef S cqd 1 fr ss JT i F 1 4 à ar 1 r afä 1 2 3 4 ii 10 11 12 13 14 1 2 5cogoiou1iw 1 2 3 4 çoicnui 1 2 3 4 5 6 7 8 abcl cde flbd lfa UUlDU I O c d cd e lp il q r DS st gz mfi to Cl qrf lb Cla aibai a ba mocrU É O abc da db cdb dlabl ab ab c db UUUU cqd OUOU cqd P D PD cqd D P P E hi i1abCl p 2adllâl p 9 d 10 b 11 a ba bcd g0O7U1lrtJJz QI 3o1cUQJQ CL Ç pp cwd 1 riil P 2 sD 3 s il 5 r zl oooo1çD1P Z QE Eqi 11 p 12 srf 3 lbdl1 4 a ld 997S crircrfir sl O 9c 10 d e 11 d 12 e 13 c e 14 ibdil el cqd cqd cqd cqd 4 I z 1 11 i 5 1 YLê T ÍÍ Irr Í I Í z ífl 1 É 7 Fluxogromos O fluxograma constitui um método alternativo para as tabelasverdade na verificação da validade de um argumento no qual se ilustra o raciocinio utilizado Neste método para verificação da validade de um argumento ou prova de um teorema procedese da seguinte maneira 1 consideramse as premissas verdadeiras 2 aplicamse as definições dos conectivos lógicos para determinar o valor lógico da conclusão que deverá ser a verdade 1 para que o argumento seja válido ou o teorema provado Caso ocorram situações em que não se possa determinar o valor lógi co da conclusão ou em que O 1 contradição o argumento é falho O teste de validade de argumentos ou prova de teoremas mediante o uso do fluxograma pode ser feito pelo método direto ou indireto obedecendo às particu laridades de cada uma das técnicas dedutivas já estudadas Vejamos alguns exemplos 19 Exemplo Provar p dadas as premissas 1Dfi 2 q dÔÔÚíífilf 1 ll 1 ll J l lJi l I cwiÍíl ÍíInn SoluÇ30 Í z É l r 1 I Justificação Consideramos as premissas verdadeiras fazendo p Q 1 0 Q 1 2 Como q 1 pela negação temos q 0 1 3 Levandoq 0em pq 1tem0SiP0l 4 Pela definição de condicional p 0 1 se e somente se P 0 A 5 Como p 0 temos p 1 o que mostra ser válido o argumento pois premissas verdadeiras conduzem a uma conclusão verdadeira 1 2 Exemplo Testar a validade do argumento O Solução a LJL Solução abaIb 1 í 2 É 78 Í 1 2 3 4 5 6 Jusziffcâçâa Consideramos as premissas verdadeiras fazendo a b I 1 e a 1 Como a 1 pela negação a 0 Levandoa 0em ab 1 temos0 b 1 Não podemos concluir se b é verdadeira ou falsa pois pela definição de fld0Í0fla Ú 1 1 6 0 O 1 Se b pode ser verdadeira ou falsa então a conclusão b pode também ser verdadeira ou falsa e portanto o argumento é falho 39 Exemplo Provar q dadas as premissas I p q 2 pr 3 r W I rf 1 Justificação Consideramos as premissas verdadeiras fazendo p q 1 p r 1 e r 1 Como r 1 por negação temos r 0 Levando r0empr1temosp 0 1 Pela definição de condicional p O 1 se e somente se p 0 Fazendo p 0 na premissa p q 1 temos O q 1 Pela definição de disjunção O q 1 somente se q 1 Portanto o argumento é válido 49 Exemplo Testar a validade do argumento DTCI pq Solução 3 4 5 Justificação r P 2 I D1 I q1 l O I D0 1 pi l 1 1 Consideremos as premissas verdadeiras fazendo p q 1 e p q 1 2 Pela definição de disjunção se p q 1 então p 1 ou q 1 Se p 1 o argumento é válido pois premissas verdadeiras levam a uma conclusão verdadeira 3 59 Cl 1 substituindo na premissa p q 1 temos p 1 1 4 Pela negação temos p O 1 5 Pela definição de disjunção p O 1 somente se p 1 Portanto o argumento é válido pois premissas verdadeiras levam a uma conclui são verdadeira 59 Exemplo Testar a validade do argumento i1 O I I pqÍ èn 1 1 L i 1 J i 5 És 9uiu iinv Q í 1 E Ii 1 I L i ni rc 1 ar 1 4 À ã i if 16 i VT P8 z A r U l 2 I É fi T ITQ I Z Tjã 5 S z Ê V J i É 1 É ff I Êiizriälnsärm 1 IP z ea na f im ÍA rf 1 šäi 7 i 5 Ícrwãiz  wa mf 1f 1 í I1 T I Solução mw iu 7 1 Inn 1 I piq1I IlDQll 2 3 4 l dq 5 1O1 T pu1 6 I o1 I Justificação 1 Consideremos as premissas verdadeiras fazendo p q 1 0 lp q1 2 Pela negação p q O 0 I I d0 p 3 Pela definição de disjunção se p q O então p 0 e q 0 4 Como p 0 pela negação temos p 1 5 Levando p 1 e q O na premissap q 1 temos 1 0 1 6 Pela definição de condicional 1 O 0 Considerando as premissas i 1 verdadeiras chegamos a uma contradição Portanto o argumento é falho 69 Exemplo Provar p r dadas as premissas 1pq 2 qr Solução Como a conclusão é da forma condicional consideramos o antecedente p verdadeiro e procuraremos mostrar que o conseqüente r é verdadeiro sfiÚÚí1dduIz ííííÍ if Ii l l I l Il ji nniffu1ni Ii ll íílltf ii i J 1 J i 82 1 I p 2 3 l li f il 1 4 0q 5 6 7 Justificação 1 Consideremos as premissas verdadeiras fazendo p q 1 e q r 1 2 Consideremos verdadeiro o antecedente da conclusão premissa pro visória fazendo p 1 3 Como p 1 pela negação temos p 0 4 Levando p 0 na premissa p q 1 temos O q 1 ci1 1r1 i 0 r1 5 Pela definição de disjunção O q 1 somente se q 1 6 Substituindoq 1 em q r1temos1 r 1 1 7 Pela definição de condicional 1 r 1 somente se r 1 Portanto zi a conclusão é verdadeira pois p 1 leva a r 1 e 1 1 1 Não consideramos a possibilidade de a premissa provisória p ser falsa pois se p 0 a conclusão p r seria verdadeira isto é O r 1 ff 79 Exemplo Provar p dadas as premissas 1p1 2 pq Solução Usemos o método indireto z L r I z T ât Hr Z 1 É alii Iv 1 f z z sf z Ê ti 9 F Us às A Ê j Í 1 3 e ÂAÍ IP ÊA ê z I l za 1fÍ ia i1r 1 Ip 2 3 4 5 6 7 q1 Ipíq1 izri Justificação 1 2 3 4 5 6 7 89 Exemplo Consideremos as premissas verdadeiras fazendo p q 1 e p q 1 Consideremos a conclusão falsa negação da conclusão fazendo p O Levando p Oem pq 1 temos 0q 1 Pela negação temos 1 q 1 Pela definição de condicional 1 q 1 somente se q 1 Pela negação q 0 FazendopOeq0empq1temos001 Usando a premissa provisória p 0 chegamos à contradição 0 O 1 Portanto p O é eliminada ficando a outra possibilidade p 1 como soluçao Provar p dadas as premissas I pq 2 qr 3 r Solução Usemos o método indireto i s i izzzi ii 2 1 T 3 4 í 5 6 1 il ni Justificaçao 1 Consideremos as premissas verdadeiras fazendo P Q 1 Q V 1er1 ses UTI Fazendop0empq1temos0q ela definição de disjunção 0 q 1 Sümeflíe 50 Q 1 ela negação r 0 ç Substituindo q 1 e r O em q r 1temos1 01 Usando a premissa provisória p 0 cheQams à C0flÍf3dlÇa0 1 0 1 Portanto p 0 é eliminada ficando a outra possibilidade p 1 C0m0 Consideremos a conclusão falsa fazendo p 0 1 z z à n fiiÍ i fia Í Ê 1 1 2 V ê za Íf 1ÍiÍá fi iÍ fzÍÍszzfÀ fzlâzf 111 úz 1 fJfi i ÍT Qi UI z L I 3 Í z fm J š r 1 2i ii lb mr if 1 iz lr i ir 11 i a soluçao 23 Í Ê J Li I ä 31f E 1 zw lq lfi 2 pz0 4 1 No 3 i iT i 5 q l lfl1 l 6 q0 I  1 l O 1l Justfcaçâo 1 Consideremos as premissas verdadeiras 2 Consideremos a conclusão falsa negação da conclusão 3 Pela definição de condicional p r O somente se p 1 e r O 4 Pela negação temos p 0 5 Fazendor0emqrf1temosq0 1 6 Pela definição de condicional q 0 1 somente se q 0 7 Substituindo p Oeq Oem p q 1tem05z00 1 uiÕÍÍfiJulu i ííííííxz J Usando a premissa provisória p r 0 chegamos a uma contra dÇ50 Ú 0 1 POFÍHHÍO D r 0 é eliminada ficando a outra 9 Exemplo 1 possibilidade p r 1 como solução z Provar p r dadas as premSSflSI 1pq 2 qr Q 1 fiz 1 r i H zzj z 4 f f É Exencfcios 1 s0Uçã0 1 Testar a validade dos argumentos abaixo mediante o uso de fluxogramas Usemoso método indireto z f 3 1 a L gi l Z L r 11 z I TH I I i ú ff lei c é 9 ífi S i al iirlrlq bl pq Dqq p qirp d abCbca Ê A 84 3 p fl p i ql q i 5 r J 1 J l r 5 Aqualdosaru 1 b flip Gi r s qq g110 0ou20 9 m en os a aixo corresponde o fluxograma a a b b a b C 3 b fl nenhum dele í bc bC bc 2xO1x1 2 Mostre atraves do fluxograma usando os metodos direto e indireto que o argumento abaixo tem premissas contraditorias D Cl I 3 Mostre atraves do fluxograma usando os métodos direto e indireto que o iii íí ii ab C Jg argumento abaixo nao contém informaçoes suficientes para deduzir a con clusão 4 Dados os argumentos abaixo a qual deles corresponde o fluxograma pQ qrl p S a1 P 1 Cl bl p p dl nenhum deles Pq DQ PQ qp 6 O uaIfl uxograma corresponde ao argumento pq q r pp ifli i U ex 1 1 ii í 1 Pci1 q1 W 1 s d nenhum deles Í 1 E l 1 lis Í tz rã Y xi Í 1 jlr Q f1z st if 4 if Í ÉTiii í r i Í É nl C s 4z vi aflühàfi I Í lãin Quontificodores i v n 1 g 1 x 1 É W s z z Í 2 É z 1 1i r e 3 i 5 Já 81 SENTENÇA ABERTA Sejam as proposiçoes p35š11 Vp1 q x 5 Q 11 Vq fiësr if Â Í ÂÉ1 fa113 1l 7Pi z r L Í K V2PflE V çä Yz z E 1 ii é Í Ei I iz P ii Jz i V s 1 V 13 I 1 ai fi z H Ji 5 sr 1 1e z rf i 5 H z i 4 L 11 i ÍV g mz va 5 aí 1 Í rf is 1 Y U Z fr 1 5 U í mir z F A proposição p como podemos ver é verdadeira ao passo que nada pode mos afirmar sobre o valor lógico na proposição q Vlq que somente será conhecido quando x for identificado Neste caso dizemos que a proposição q é uma senten ça aberta ou função proposícional Nas sentenças abertas os simbolos x y X e É outros sao chamados variaiveis Chamamos conjunto universo da variável ao conjunto das possibilidades ló gicas que podem substítuir a variável na sentença Denotaremos este conjunto por U Cada elemento de U chamase valor da variável U às vezes é tacitamente im posto pelo contexto mas pode também ser escolhido pelo agente de estudo em questão 19 Exemplo Seja a sentença aberta x 5 Q 11 Podemos impor que o conjunto universo da variável seja N ou Z ou Q ou R ouoconjuntoU 1357 s 29 Exemplo Seja a sentença aberta O planeta X é o maior planeta do Sistema Solar O conjunto universo da variável X é pelo contexto dado pelo conjunto dos planetas conhecidos do Sistema Solar I T vuv vuvv J U Mercurio Venus Terra Marte JUPWGH 5aÍUm Uf3 Net Plutao ur CONJUNTO VERDADE da sentença e o conjunto dos valores da variável para os quais a sentença e verdadeira Denotaremos este conjunto por V v eu lvlplxll 1 onde px e uma sentença aberta na variavel x fíini 1 Exemplo Dada 3 Sentença aberta 5 11 x E Fl determinar seu conjunto verdade Soucão V R lxsáfi 20 Exemplo O conjunto verdade da sentença aberta O planeta X e o maior planeta do Sistema Solar e f V iJupiter 3 Exemplo Determinar o conjunto verdade das seguintes sentenças abertas x1 x513 U Soiucoes aV 678 a 2 ouANTiiicAooi uNivEiisAi Usaremos o simbolo V chamado quantificador universal para exprimir o fato de que para todo x em um dado conjunto a proposição P 9 Verdade ra Uma proposicao do tipo Para todo x P e simbolicamente repfefiemada por V x Pix A proposição Todo inteiro é racional podese escrever 1xxZxO 2 Para todo x sexZ então xEQ 3 Para todo x sexZ então xEO 4 Para cada x sexZ então xE0 5VxxZxE0 6 Qualquer que seja x x E Z x E 0 19 Exemplo Escrever de maneira simbólica a proposição os números do conjunto A são todos os reais SouÇào Rx é real VxxEAx R A Filx 29 Exemplo 1 Simbolizar a proposição Para todo x se x é real então x 6 0 SoIuçáo Qxx EO Rx x é real Vx Rx Qx 39 Exemplo Vxx2 20xER 83 QUANTIFICADOR EXISTENCIAL I No caso de proposições que envolvem expressões do tipo Existe Há pelo menos um Para ao menos um e AIgum usaremos o si7mboIoEI chamado quantificador existencial para exprimir o fato de que para um ou mais elementos de um dado conjunto a proposição Pix é verdadeira Uma proposição do tipo Existe um x tal que Px pode ser escrita simbolicamente Elx Pix As seguintes proposições têm o mesmo significado 3mxN Existe um x tal que x G N Algum número é natural Existe pelo menos um número natural 19 Exemplo Escrever de maneira simbólica a proposição Existe x tal que x2 1 2x Solução A Piz2 1 2 Hx P 29 Exemplo Simbolizar a proposição Existe x E O tal que 0 x 1 Solução x Piizo1eo ElxxGQPx Osquantificadores podem aparecer juntos ou não conforme mostramos nos exemplos abaixo 19 Exemplo Para todo x e para todo y y y x é representada simbolicamente por Vxvy xVY 29 Exemplo Para todo x existe um y tal que x y representase por V x Bv lx y 39 Exemplo Existe um x tal que para todo y y O representase simbolicamente por 3xVV lx V 0 49 Exemplo A Existe um x e existe um y tal que xV é irracional escrevese Elx3Y xV G ll 59 Exemplo Para todo x se x é par então existe um y tal que x 2v é representada 92 simbolicamente porV x x é par Ely x 2V lflík FIES 84 VALORES LÓGICOS DE SENTENÇAS QUANTIFICADAS A sentença Vx Px é verdadeira se e somente se o conjuntoverdade de Px e o conjunto universo forem iguais isto é U V e falsa quando U as V A tabela a seguir nos dará alguns exemplos do que acabamos de definir vPii u vvvPii vo o o Vxx0 01 i 0 Vx2x1 R š Fl l 1v22310 N 0 v22aio  z 1 17 zfzz z V Í f f wii mw f CDCCD fr A sentença Hx Px é verdadeira se e somente se o conjuntoverdade de Px é nãovazio ou seja V 5 D e falsa quando V A Vejamos alguns exemplos através da tabela abaixo flzP UA VHPlÇ 3x x i šlx x O 01 0 ax21 R l n j Í3x2x23x10 N O ãx2x23x10 Z 1 li O fi Sl rQ ÇDsL4 cw 85 NEGAÇAO DE SENTENÇAS QUANTIFICADAS Seja a sentença aberta Px e U a b c d o conjunto universo da va riável x Então Vx Px Pa Pb Pc Pd f e sua negação é dada por V x PxPa Pb Pc Pd Pela lei de DeMorgan VxP 4 lPlaPbPCPld VxPx l I i i i uufnf J 1 l l l z É i i z Á Ê z f ff 1 z Portanto 3U5 3 z i Í V x Px fä 3x Px L V p z p1 Existe pescador que não é mentiroso xnuJJ É 1 É Observação Neste exemplo usamos a equivalência notável p q 19 Exemplo É i Vejamos agora a que equivale a negação da sentença 3x Px Temos Elx P Pa Pb Pic Pld š zf s 39 Exemplo Negar a sentençaV x x 1 5 e sua negação é dada por 9 s 8ã Elx Px â Pa Pb Pc Pd Pela lei de DeMorgan lšlx Plxll f Pla Pbl lPC lPdl V x Px Portanto lšlx P Vx lPx l Vxx15í3xx15 m 3 z 49 Exemplo Negar asentença 3x xa 1 x se 0 Soluçâb ri Elxx21x0 Vxx21xaÉ0 i Vll21x0 VX X2 1 X Pe 0 Vejamos alguns exemplos V l2 1 X 0 Negar a sentença Alguns alunos são estudiosos à n 1 D Ci s z L ej l í i f1 59 Exemplo Soluçao El alguns x alunos Px alunos sao estudiosos É l ai1i 53 Então Negar a sentença V x sengx cosz x 1 Elx 2x é imparl T Ê Sfllvcãbr lVxsen2xcos2 1 Elx2xé lmparí V x senzx cosz x 1 Ex 2x é Ímparl šlx senzx coszx se 1 Vx 2x é par Existem alunos estudiosos 2 Elx Px i E a negação desta sentença equivale a i ia Pi v iPii Svlurãv ou seja l 69 Exemplo if É Í r Negar a sentençaVx Ely x y 11 VxEVxy 113xVyxya11 Todos os alunos nao sao estudiosos 29 Exemplo of D h iii1 5i ljIiIÉgi1l 7 Exemplo Ne9ar a sentença Todos os pescadores são mentirosos Nega 3 sememai 3 V V 0 V 1 7 oluçáb Liz Í Ei fi la v v l oi iv 1 4 7 i Vx šlv l 0 lv 1 7l vavlio y17 5 1 i z i EXERCÍCIOS S 9 Determinar o conjuntoverdade das seguintes sentenças abertas ax1121 b2x513 cx27x120 dx2l0 e 24x3š0 f 15x22x8O gi52i912o CCCCCCC wwuzzuz 3 Escrever simbolicamente as sentenças š a 1 2 então existe x tal que x Q 2 b Todo triângulo é um polígono c Existe x tal que x é primo e x é par d Existe x e existe V tais que xz y e Para todo X se x E N então x E Z z E à Q f Todo poligono regular convexo e inscritivel 1 âfz Dadas as sentenças abertas px 15x2 2x 8 O e q r52 19x 12 0 com U R determinar os valores lógicos de p q e p q Determinar o valor lógico de cada uma das sentenças if3 É 5 3 VX X x R r ii Q CCCCC CC II É U z bl Elx x 3 10 1 2 3 4 5 c Vx x2 3x 2 R d34312x ei a 22 15 1 2 34 ze 55 s f V x xz x 6 1 2 3 Q êi2 31 1 23 Negar as seguintes sentenças a Todos os homens são maus b Existe pescador que não é mentiroso c3xERx252x d Existe y tal que para todo x x y 7 e Para todo x existe y tal que x y 3 zw I Y V À lntroduçoo Õ Álgebra de Boole 91 OPERADOR BINÁRIO Iniciaremos nosso estudo recordando alguns conceitos primitivos de especial interesse que são a noção de conjunto elemento de um conjunto e a relação de pertinência Assim dado um conjunto A 123 dizemos que 1 2 e 3 são ele mentos de A e em conseqüência pertencem ao conjunto A Neste caso podemos escrever 1 E A 2 E A 3 E A que se lê 1 pertence ao conjunto A etc Caso tenhamos um elemento 4 que não pertence ao conjunto A denotamos o fato escrevendo 4 É A que se lê 4 não pertence ao conjunto A X Chamase operador binário ou operação bnaria ii a lei pela qual todo par ordenado de elementos x y leva um terceiro elemento z Notaçâb x ii V z Os l 1 iu Ip u 3 Q Q f sinais aritmeticos sao exemplos de operadores binários 92 PROPRIEDADES DAS OPERAÇÕES P1 Seja X um conjunto Dizemos que X é fechado em relação a ii se x y G X Vx y E X Por exemplo considerando o conjunto Cj de todos os inter ruptores se a b GCentãoa bC ea bC istoéa bea bsãotam bém interruptores e pertencem a C1 a b Chamando C2 o conjunto de todos os conjuntos de pontos se a b E C s então a b G C2 e a b G C2 isto é a união e a interseção de a com b são tam bém conjuntos e conseqüentemente pertencem a C I W É J uuJ J P à P ú  i i I p zm f W mf 11 e 1 z ab h ab Se tomarmos o conjunto C3 de todas as proposições e se a b 6 C3 então a b E C3 e a b E C3 isto é dadas as proposições a João estuda b João trabalha P Temos as seguintes proposições compostas a b João estuda ou trabalha a b João estuda e trabalha Ou mediante as tabelasverdade It í I zzzzw aíb ab ab z t q oo Ç sn OOá O 4 L z zz P2 O operador é oomutativo se x y y V y E x 19EompIo SeabECentãoabbaea bbaistoé V E a b H à ab ba 1 3 bW z zb a z J98 ab b3 f H í E r 4 ií HT az v 1 1 Iz ez wi àLzz z 29 Exemplo P SeabC2entâoabbaeabbaistoé i T se i L zz J ab ba I Ú l W l P H b âa b 1 7 z 7 3b ba 39 Exempio SeabGC3entãoabbaeabba i Podemos verificar esta propriedade mediante as tabelasverdade T T f ff É az b ab flbz5 zbi bz z zzz zz zzzJ I 1 i i 1 F 2 1 Qzz ff ff Y f L LJ L3 I P3 Dizemos que o operador é associativo se y z x y 1 z VyzEX p 19 Exemplo i isto é 306b0Centâoabcabceabcabc Lâi1f aíšlir abc abc aíbc abc abc abc 29 Exemplo SeabcEC2entãoabcablceabcabc isto é ffff ff ff 7 z L Jf ff 1 f 7 f f1Lf 3 8 abc abc 1U7 llII r zzzzzz 7 a Ê a f i Ç b c 1 b c abc abc u 39 Exemplo SeabcGC3entäoabcabiC8ãbCl8bC isto é ID U O bc abc os U 8bc oooca l lr OOCDH o c 1 1 Gíííflnnfií íüííí OO 1 1 on f v Lv ID U O E T bc a lb clab ø QI É o Õ L F nnInnlilL Iff OOOC OOCCD1 l J OCDOC34 DOOGOES ll Í ODOCJOOO1 QOOOQ OOOOOCDOl P4 Um operador edlstributivo sobre El se x y Elz y El x 2 Vx y z EX 19 Exemplo SeabcECentãoabcabaceabab a c isto é 1l T p O Ii 5F l abcl lablla b a f l1 l P a c 101 JC ff 1 abc abac I f nfqInhra i l r 1 f f uuunfuIJz V V V 1 f l z 2ExempIo Se abcC1entãoab cablac8bCl3 bl a cisto é f f fz fff fff ff f f ff 1 T a Í W ff f fff f f JL W amC tamad f f fff ff E WT ll  3 1 z ff ff a W f z fff a bc abac 39 Exemplo if Se abcC3entãoab cabl aCle8lbClã b a cl isto é construindose as tabelasverdade correspondentes a cada caso teremos p OJ U O A bizlsazb acabrao W 1 i 1 t aL OCDOO W ÇDÇj a Lp u DOO OO DO o G O O 102 portanto a lb c 3 b 3 c pois suas tabelas verdade são iguais Analogamente ID U O E Ú bC8lbCla b acaba l F fffiz l Q Lío tg aí 0 O CDCDDOCD4b OOOOAe CDC OOCDCJOHCr ff ff if f z 7 1 1 OOCDCDCD P5 Um elemento e é um elemento neutro para a operacao se e somente S e VxEx 19 Exemplo a ffffif ff 1f f ff a 29 Exemplo 59Í33EC1flIã0a0Oaaea 11aaVaC a ab Dad0aGC2entãoa001aaea 11IaavaEC2 p p L 3 O I 1 a 1fla 103 If fff f l ff 1uf ffffff 1 l l 3 Wa l 1 3 IíffíS fi Ç z Ç zff z fff fiff7ÍfšfJr P rúfíff1fiIf1í5f I2ifi ffffÍ E a 39 Exemplo Dado a5C3então a e e a aaC3 f aii 1 Í1 Nli f lá i34 uz li ÍÍ f lr para ii temos que a disjunção inclusiva ou soma logica é falsa somente quando ambas as prol3osiÇões consideradas forem falsas Então dada Uma PYO É zf f posição a e Vlal 1 Vfimí 3lO 3V3 para ii temos que a conjunção é verdadeira somente quando as propo sições componentes forem verdadeiras logo dada uma proposição a e Vlal 1vem 3 1 a7a EXERCÍCIOS 1 Seja o conjunto C T 1 O Definamos dois operadores binários e El E A pelas tabelas abaixo Para lera primeira tabelajpor exemplo a b tomamos a interseção da linha correspondente a a e coluna correspondente a b onde a e b podem ser quaisquer destes simbolos EntãoO J T e O El l 1 i l lOl lO fl O Ú A l O f f ffff i à 1zf z Í 3 1 1 f f 2ii 1s 1 im 5 Wz1 f r l gÍ Fr flr1l ii Í çte sa Ê fq z z f 2 fz lã z u i lš zzz V àšI É â i Í ú L cr zz z f z z il fff r Q r l O i Ol lIifr OO ffff O i IO al O operador é comutativo é associativo b O operador El é comutativo é associativo c Os operadores e El são distributivos um em relaçao ao outro 2 Dados os operadores aritméticos e I dizer quais dentre eles são ope radores binários no conjunto Z de todos os inteiros 3 Considerando os operadores aritméticos E z dilef lUfl5 dfiflíffi eles são operadores binários no conjunto N dos números naturais 4 Seia 3 b z 32 b2 onde a b G R O operador é fechado é comutati vo é associativo é distributivo em relação a Z É É dSÍfbUtV0 Em Hla ção a admite elemento neutro f if Lf 1 t  5 ÍÍ5 3 I iz 2 Í1Z H zf â f 4 ii lu Tt fr 4 u 5 à i zzízzfizf i 5 Dados os operadores e El distributivos um sobre o outro reduzir ou desen volver as expressões a seguir de modo a apresentálas sob forma diferente a abElc balIllalÍlb c arlalflbl dl alIlblclÍldl e blIlalbElb fl labE1lflCl 93 SISTEMAS ALGÉBRICOS Antes de estudarmos a definição de uma Álgebra de Boole vejamos o que é um sistema algébrico ou uma álgebra abstrata também chamada simplesmente de álgebra Chamamos álgebra abstrata ou sistema algébrico a um conjunto não vazio munido de um ou mais operadores binários sobre ele definidos Denotando por A o conjunto e por e É os operadores definidos sobre A podemos ter A l ou lAlIl l que são álgebras com um operador ou uma operação e A Ill que é uma álgebra com dois operadores ou duas operações Uma álgebra pode satisfazer a alguma a todas ou a nenhuma das proprieda des dos operadores assumindo nomes particulares para os diferentes casos como semigrupo monóide grupo anel corpo espaço vetorial conforme as proprieda des satisfeitas pelo operador ou operadores definidos sobre um conjunto conside rado Não trataremos destes casos em nosso curso para o qual têm especial inte resse os sistemas algébricos chamados Álgebras de Boole que definiremos a seguir l I I Dizemos que o sistema algebrico B e uma Álgebra de Boole quando e somente quando Va b c E B valem os axiomasz AL abB AZ abB A3 abba A4 abba As aszzizzz 105 J l l i ir wzfwffiú l øJ iz 1 J l 1 1 l i J 1 l 1 l A6 albclablacl A7 ElOGBtalqueparacada aEBa00aa A8 31BtalqueparacadaaEBa11aa A9 ParacadaaEBElaEB tal queaa1ea a0 No axioma 9 o elemento achamase complemento de a Uma Álgebra de Boole é dita degenerada quando os elementos neutros para as operações e são iguais isto é 0 1 Consideraremos apenas álgebras não de generadas isto é Âlgebras de Boole nas quais O 1 Vejamos alguns exemplos 19 Exemplo B2 01 é uma Álgebra de Boole cujos operadores são definidos pelas tabelas a seguir Esta álgebra é conhecida como álgebra dos interruptores ou álgebra da co mutação e é a mais útil entre as Âlgebras de Boole É o fundamento matemá tico da análise e projeto dos circuitos de interruptores ou de comutação que compõem os sistemas digitais B2 é o exemplo mais simples de Álgebra dei Boole não degenerada 29 Exemplo B4 0 a b 1 é uma Álgebra de Boole com quatro elementos descrita pelas tabelas I i Í W O CTCDCI OCJCD nCDn CI Q zzz z z zz z Teorema 1 Principio da Dualidade Todo resultado dedutível dos axiomas de 106 uma Álgebra de Boole permanece válido se nele trocarmos por e 0 por 1 e vice versa H 01 0 1 0 0 0 o o 1 1 0 1 1 1 1 o z sf 0 z ló 1 H 3 za 1 b b b 1 1 1 11 11 L O a b 1 3U Inllfiínlnlfixfi 7f 13 ii Í M HV riu 1 1 uuiifi It 1 F Prova Pela simetria da definição de uma Álgebra de Boole entre os operadores e e os elementos 0 e 1 tanto os operadores como O e 1 podem ser intercam biados conduzindo a outros resultados também verdadeiros cqd 19 Exemplo Dualizar a expressão x y x y z y z Solução Como a expressão não apresenta os valores O e 1 basta trocar os sinais por e por temos 1 lWPWvzPvfl que é o dual da expressão dada Obs 1 Não houve qualquer modificação nas letras complementadas ou seja onde aparecem y z continuam sendo x y z 2 A dualidade tem grande semelhança com as leis de DeMorgan que veremos adiante diferindo apenas pela observação 1 29 Exemplo Dar o dual da expressão x y O Solução Trocando na expressão dada por e O por 1 vem s y1 que é o resultado procurado Teorema2 aaaaaaVaEB Prova aaaa1 A8 aaaa A9 aaa A5 a0 A9 a A7 aaa Teorema 3 a a bl Analogamente 1 00 a11a0OVaEB Pelo Principio da Dualidade temos s Teorema 4 Lei da Absorção a la bl a a a bl a Teorema5 aëblab flJDJflJQJDI DJ IOCO OJ al la aal A6 a cqd a1 h1laãl a1al A5 aa A8 a11 1b lb1l A3 1 Teor3 a a bl a e pela dualidade temos aaba Teorema 6 Os operadores e são associativos Prova abc abcaa A89 abcaablca A6 aabcaabcl A4 laabacaablacll A6 a a cl llle al la bl la cl Teor 4A6 aOabac Teor4A49 aabac A37 aabC A6 albc Teor5 ablcalbc Pelo Princípio da Dualidade temos ablcabcl Expressões como a bl c e a bl c podem ser escritas sem parênteses e expressões tais como la b c d el podem ser desenvolvidas como na Álgebra usual a b pode ser escrita ab e o operador tem precedência sobre de modo que a lb c pode ser escrita a b c ou a bc cqd Teorema 7 O complemento de cada elemento de uma Álgebra de Boole é único Prova I N 3 Suponhamos que a e x sejam complementos de a Entao ax1 zo l Logozx xaa aa aa 3lb A5 alabab L 1 O ax aa ax aa xl a 1 a Corolário Qualquer Álgebra de Boole nao degenerada tem um numero par de elementos Teorema 9 ab ab D Teorema 10 01 O1 Logo 0 e 1 Então la bl é o complemento de la bl isto é la bl Teorema 8 al ab ab a 1 nu 01e1O la bll8bl bab 3 Pelo teorema 7 existe um único complemento portanto HT abb a1 ababa Teorema 11 De Morgan la bl a be 8 bl 6 b afIbf I abl 1 A9 abalabbl l1bl l1a aabbab0 a é o complemento de a então a a 1 e a a 0 Mas estas eQU3ÇÕ5 apenas mostram que a é o complemento de a isto é a la A37 A48 Teor 1 11 Faé l abacbc abacbc la bl la cl lb la bl la cl la bl la cl 19 Exemplo Simplificar la bl la b c QI 11 nn 1 gn í 1 1 1 F í um uq gx 1 í iq 1 1 íí Teorema 12 abacbcabac I I abacbcaal abacabcabc ab1cacl1bl abac abac Teorema 13 ab ac lb1caab lablla0llbcl laaacabbc bc 0abcabbbbcaccabcbcc abcabbcacabcbc abcabbcacabc ac1blabl1clbc acabbc acab cl acab TO0I8m8 14 ab acacab aaacabbc acabbc acabbclaa acababcabc ab1clac1b ab ac ac ab Esses teoremas têm sua grande aplicação na simplrflcaçao de expressoes bo oleanas e circuitos de interruptores conforme veremos nos exemplos a seguir III Soluçaol abllabcl aaabacabbbb0 aabacab0bC abc 2 Exemplo Simplificar o circuito Soludo lp qr lpq rl pqr 3 Exemplo rm f 1 p Í qkz f e o circuito simplificado sera Simplificar o circuito Solução nc mr Pf 1 pr pqrr lp 111lf p qrr q p H Dl l ííwill pqf p 1 f p qr qr plzÍf Dq Dr Df Dq lp 1lf D11f D1f off 1fI Fã Desenhando o circuito da expressão simplificada vem lIüÍJ 49 Exemplo Determinar o complemento de pq pfq Solução lpq D1 l1ql lrql ln lil llpl q lrqllDql rnDc1qqq r1rq Teorema 15 Se uma Álgebra de Boole contém pelo menos dois elementos dis tintos então 0 1 S Prova Á Suponhamos que existe uma Álmbra de Boole com pelo menos dois ele mentos distintos para a qual O 1 Seja a um elemento tal que a 5 0 Portanto O aê 1 cqd Sejam a e b elementos de uma Álgebra de Boole Dizemos que a é menor ou igualablašblse esomenteseabb f Teorema 16 é uma ordem parcial Prova Pelo teorema 2 a a a Logo ai a S 1 Seab então a b bsebáa então a b baaPortantose a b e b a então a b Finalmente suponhamos queašbebšc Então a bbe bcc Logoacabcabcbcc Portan toac cqd A Teorema 17 Sejam a b e c elementos de uma Álgebra de Boole Então a ordem parcial š tem as seguintes propriedades Como por hipótese tal elemento existeentão todos os outros elemen tos são iguais a 0 Logo a a 1 a 0 0 o que é uma contradição Iííf 1 Seabeacentão ašbc 2 Seaíbentão abcvc 3 Seab então acbrlc 4 ašbseesomente se ba Usando o teorema de De Morgan provar que lãbCl b c abcl Verificar esses resultados com os círculos de Euler Simplificar 1 abbeaccLogoabclabll8ClbC 2 eabbentãoalbclab0bC 3 Pelas leis da absorção aca a ou acáa O resultado seobtem Pela transitividade l alam ba bHpcrq cl a abc dl llStlsulv 4 Suponhamos a b Então a b b B DOFÍHHÍO b la bl L090 bi af 3 by ai 3 bla a pelas leis da absorção A recf proca decorre do teorema 8 onde temos la l 8 C Cl d EXERCÍCIOS Simplificar as expressões a seguir justificando cada passagem aabllabl blliqlilcfll l cllblacllalbcll d pplpillirll el xlyZllllVZl Simplificar l al abacabcabc bl fghfgh gl pqr pqS d yxyzxyz l el lab bcl lcdl ld al fl labllbcllcal Desenvolver as expressões a seguir tanto quanto DOSSÍWil al DClf b pqrs 3 pqlIS u dll 0l abcd 1 4 Provar que ab ab ac ac ab b0 l C3 Determinar o complemento das expressoes a a b cdef balblcdell cl abcdef dllabllCdllBfl el alb cbaacbc Nos circuitos a seguir determinar a ligaçao simplificar e desenhar o circuito resultante Ll mag um cnmípalííií íluxíIíí í mirim r b dl l Y cz iab bc 8 lb0 1 z zbzc C 3 zzlnoi c gd r zb S df im l d 2 ó 9 Determinar o circuito complemfifltaf lei al 1 b bc cI b Y Z y2 Í Ál bra de Boole 0 10 Provar que para quaisquer elementos a e b de uma 9 se e somente se ab 0 P À Ál bra de Boo 11 Provar que para quaisquer elementos a e b de uma 9 se e somente se bla 1 l mentos 12 Mostrar que nenhuma Álgebra de Boole tem tres e B I V mais de um 13 Mostrar que nenhuma Álgebra de Boole finita com p tem um número ímpar de elementos 10 Funções Booleonos Seja B uma Álgebra de Boole e sejam xl xn variáveis tais que seus valo res pertencem a B Chamase função booleana de n variáveis a uma aplicação f de B em B satisfazendo as seguintes regras 1 Se para quaisquer valores de xl xn f n 3 3 E 13 en tão f é uma função booleana É a função constante 2 Se para quaisquer valores de xa flxl xnl x para algum i i nl então fé uma função booleana É a função projeção 3 Se f é uma função booleana então g definida por glxl xnl flxl xnll para todos 1 xn é uma função booleana 4 Se f e g são funções booleanas então h e k definidas por hlxlz Xfll fX1 1 QX Xnl G l1 Xnl fl1nl g xn para todos os x xn são funções booleanas 5 Qualquer função construída por um número finito de aplicações das regras anteriores e somente tal função é booleana Então uma função booleana ê qualquer função que pode ser construida a partir das funções constantes e projeção mediante um número finito das opera ções e Para uma função de uma variável a função projeção é a função iden tidade flxl x Antes de nos adiantarmos neste assunto definamos o que se en S tende por constante e variável booleanas Chamase constante booleana em B a qualquer elemento de uma Álgebra de Boole B Chamase variável booleana em B ao simbolo que pode representar qualquer dos elementos de uma Álgebra de Boole B P 5 117 Á wwfifwwdwfwfufwiwiøz 5 l I 1 l f if xi 19 Exemplo fll x x a 29 Exemplo fl Vl Y XY V 39 Eempo flx Y zl av2 V2 a Y As expressões desses exemplos são funções booleanas onde as variáveis y e z percorrem uma Álgebra de Boole e a é um elemento dessa álgebra Por causa das relações existentes entre as operações uma função booleana pode assumir muitas formas 49 Exemplo Dadas fx yl xve glx Vl lx Vl sabemos pelas leis de De Morgan que f e g são a mesma função isto é elas assumem o mesmo valor para valores idênticos das variáveis Para melhor determinar se duas expressões representam a mesma função booleana tornase desejável a existência de uma forma padrão ou canônica na qual as expressões podem ser transformadas Desenvolveremos tal forma no teorema a seguir 1 Teorema Se f é uma função booleana de uma variável então para todos os valo V resrde x flxl fl1 f0 1 Prova Examinemos as possiveis formas de f 19 Caso f é uma função constante flxl a f1xf0xaxaxaxxa1afx 29 Caso f é a função identidade flxl x f1x f0lx 1x Ox x O x fx 39 Caso Suponhamos que o teorema vale para f e seja Qlxl lflll 9ll lflxll lfl1l fl0ll lfl1llfl0ll llf1llxllfl0lll lfl1lllfl0lfl1llfl0ll lf1lllfl0ll1 lf1 f0i lfl1lllfl0ll lf1ll fl1lllfl0llx lfl1lllfl0ll lf1 f1f0f lfl0ll lfllwx lfl0l absorção 9l1l 9l0l 49 Caso Suponhamos que o teorema vale para f e g e seja hlxl flxl gx hlxl flxl g flllx fl0 g1 g0 lfl1l gl1i ifioi gioi hlllx hl0 50 Caso Suponhamos que o teorema vale para f e g e seja k fg lll flxlglxl lfl1 f0x g1 g0 fl1l9l1lxx fl 1 l9l0l fOg1l fl fl0g0 Á fl1l9l1lx fl0l9l0 l1l kO Estabelecem 4 uma variável P0d1Ífl0 uma f0fma canônica para uma funçao booleana de mstrarf de md Semelhêflíei Cl16 se f é uma função booleana de duas variáveis então para todos os valores de x e y temos P Em Qefãlz S8 f é uma função booleana de n variáveis então para todos os valores de X1 xn S 0 C 0 ano an11 nn onde oi assume os valo gi a 1 05 Ú B 1 B x e interpretado como x ou xi conforme tem valor 1 ou 0 s E l Xemp 03 5618 B uma Álgebra de Boole com quatro elementos 0 a a e 1 Construamos as formas canônicas para as funções 3 fll a bl fl Y v xv v Solução al fu 1 flo 0 00 01000 que a forma canônica Para fé fl1lfl0lz1xax 119 Valores de flxl x xa f1Tí Í x l flxl ç 0 Í a t a 0 a i aÍ 1 i 1 il 1 b g11 0 e g10 g01 g00 1 de modo que a forma canôni ca para g é glVl Oxy 1xy 1xy 1xy Valores de gxyl xy xy y fi f rf r 1 1 t i Yi l rl M A1 eaO il zz zzz z i z z 741 il l l 1 1 93 r l il L Q OI Qi O na ÍJL Notese que em ambas as funções a forma canônica reduzse facilmente forma original s s A forma canônica que discutimos é conhecida como uma soma de prod ou forma normal disjuntíva FND Existe também um produto de somas ou for ma normal conjuntiva FNC Cada termo de uma FND é às vezes chamado mm term lm e os fatores de uma FNC são chamados mexterm Ml EXERCÍCIOS 0 1 Suponhamos que f é uma função booleana de uma variável sobre uma gebra de Boole de 4 elementos fl0 a e flll a Determinar uma exp são para f 2 Escrever a forma canônica geral para uma função booleana de três variáveis Determinar a forma canônica para cada uma das seguintes funções al flxl xx z l b f l lVl XV BX by onde a e b sao elementos fixos distintos de uma Algebra de Boole cl flVZl lV 82 l 2 ax V zl Suponhamos que B é uma Álgebra de Boole sobre o conjunto il 0 a bz b C C 1 e seja f uma função booleana tal que f000 fl001l fl100l 8 fl010l 0 f011l 1 fl101l f110 c e fl111l b Determinar facb Á Q abc abc abc abC 11 1 DIAGRAMAS DE VENN OU CIRCULOS DE EULER Seja representar as funções 3 y fab ab ab ab Verificação Algébríca ab ab ab alb l b ab 31a aa ab í 1 Representoçoo dos FunÇO2S Booleonos Í i gi u 13 Í3 b 7 Íá C C fzfzJ ab c abc abC ab C f W 3 ab mfi ab ab ab V ab ab a b Ê li ii ihr ëlfew iii ii laill if eiillíll szafff nz 1 v U I 3 fz Lil Í vf err rcaçao Algébrica abc abc abc abc ablc cl ablc cl ab ab ab bl a Y Para mais de três variáveis tornase muito difícil representar as interse ções formadas pelos respectivos círculos de Euler Neste caso utiliza se a dispo sição mostrada a seguir para quatro variáveis a b c d abcd abcd I I l abcd l l íinicieizig abcd abcd 1 lJl J zbá7 abcd abcd ínLlÇun abcd 1nn fa abcd n il me u oíoín abcd r abcd T 7 íí Yw f 1 nn 1 f t 112 TABELASVERDADE Construamos a tabelaverdade da função fabl a ab fm j z fa íenieeíeqinneoínníqi g í gi í o abcd abcd abcd abcd ío001 neínaíuníuníunínní 15 í í í a b a b fi ab f O O í í ú ü O d O O I i 3 CD O OO d 4j7 uB nl O 1 O li Nosso problema consiste em determinar a função booleana f dada sua tabe laverdade Ti Q ab 1ab 1ab 14 Solução á l com lementada r Fazendo a variável nao complementada igual a 1 e a vari ve P igual a 0 pelos valores de ab e c correspondentes a f 1 em cada linha da tabcela vemos que os termos da função procurada são abc abc e abc Logo temos a un ção ab C Í f 1 if m f ir O O O 1 T 1 O C3 1 l c 1 CD Ô CD za O O WL O À í l 17 W T fz CD l C OA À O 1 zzl z I Wf O i i í O mg 1l d nal I í í b l verdade Exemplo Determinar a funçao booleana f representada pela ta e a abc abc f T abc fabc abc abc abc 113 REPRESENTAÇÃO GEOMETRICAÁ al Função de uma variável 0 ix 1 bj Função de duas variáveis 01 11 yx 00 io III X tl li nf LA z uq tgz z cl Função de três variáveis 01 1 1 1 1 í zi1 li z1 f 1 1 gä A T1 1 z z ii 1 W1 Vl 101 l dl Função de quatro variáveis mia 114 is De modo geral representamos as possiveis combinações das n variáveis como pontos do nespaço e o conjunto de todos os 2 pontos formam os vérti ces de um ncubo ou um hipercubo booleana Para representar geometricamente as funções booleanas ou seja no ncubo atribulmos a cada vértice do ncubo o minterm de n variáveis correspondente Então no caso do 3cubo temos 011 111 1 m mi vértice y JV zz I 1 jl à mi mo ii 000 u m3 j 011 1 i 3 Ui ma x m4 l m 111 4 1 Yara u Hf m5 101 l 1 wu i 1 126 Ir cn z i i fFÍíÍ1LI 1 A representação geométrica de uma função de n variáveis é o conjunto dos vértices do ncubo correspondentes aos minterms da funçao r Exemplo Representar geometricamente a função f8bCl ÊmÍÚz237l Solução m1 910 Á mz I aoÁ Observação 1 Cada um dos vértices correspondentes aos minterms da função é dito 0cuboz s dessa função E 2 Dois 0cubos de uma função formam um 1cubo quando diferem entre si por somente um valor da variável como por exemplo 000 e 010 010 e 011 011 3 Quatro 0cubos formam um 2cubo da função Dizemos que um pcubo lp Q n é um subcubo de um ncubo quando os seus vértices pertencem ao coniunto dos vértices desse ncubo ou seia pcubo está contido ou coberto pelo ncubo E Exemplo Na representação a seguir Ar lv O 0cubo 100 está coberto pelos 1cubos 100 e 101 100 e 110 100 e 000 e pelo 2cubo 100101110 111 I I I e Defínimos a distância entre dois pontos de um n cubo como o número de valores das variáveis em que diferem as representa çoes bmarias dos dois pontos Assim dados os pontos 101 e 011 de um 3cubo a distancia entre eles é d 2 pois diferem entre si em duas posições Indicamos o fato escrevendo d35 2 onde 3 e 5 são os valores decimais desses pontos en contrados nos minterms m3 e m 5 R Vejamos agora alguns exemplos de representação geométrica das funções booleanas R 19 Exemplo Dar a representação geométrica do circuito yz e z Solução E fvzl v2 x y z 101 J 1 0 1 29 Exemplo Representar geometricamenteocircuito z a z z SoIuçâo fZ z xyz xyz né O4 C 39 Exemplo E Representar geometricamente a função fxyz y yz 127 zzz Solução fyz xy yz xyzyz yz JW a fyzyz l b f yz y i c f yz x y xyz dl fvzlv2v2 el f v2l V I I Í xyz xyz yZ lr Hi Hi ll 111 110 001 EXERCICIOS Representar geometricamente as funções Dar a representaçao geométrica dos circuitos Í y2 L X zz Y Z z zzzzz LV Y Z y z 5 í Z í y v 2 ea X e ff Yf iiY 1 1 yíín V ei Z v 2 W I I 1pri V Determinar as seguintes distâncias em ncubo al d713 b d27 cl d715 dl d311 e d914i Determinar a função booleana representada geometricamente por al bl FzI nn mz I I J me m4 m3 m7 I Í Í I z 1 f Í Tio ÍTI4 IDIIIIuy L RIIII I I z I 1 mo ma mz 1z Í 31 Lf Çvš 1 flz Qi 1 i cl ma m7 E ms Í zf I 3 Formos Normois Ô l V 1 Lflé 1 ffrfÍfla E 1 Í z šlí Í 1Í 121 FORMA NORMAL a n VARIÁVEIS E z 5f4 5 ru I t51i E Dizemos que uma função booleana está na forma norma a n variaves quan do envolve todas essas variáveis ou seus complementos 7 53 1in FTI4 19 Exemplo a b é normal em a e b I3s z 29 Exemplo a b e normal em a e b m 3 m 7 E 39 Exemplo a ab é normal em a e b u V 49 Exemplo a b cde é normal em abcd e e Ff s 59 Exemplo abcde é normal em abcd e e J z A 122 FORMA NORMAL DISJUNTIVA 1 z 111 Uma funçao booleana está na forma norma disjuntiva quando em todos os z 15 l m4 r seus termos aparecem todas as variáveis envolvidas ou seus complementos are 1 lÍ 19 Exemplo I A função booleana ab aab ab está ha forma normal dsjuntiva x v 29 Exemplo i A função booleana y abc abc abcestã na forma normal disjuntiva 7Ê I 39 Exemplo 1 A função booleana z abcd abcd abcd esta na forma normal dis aää juntiva 1 31 fi W l li I il Ê Í ri lyiii làif F hi Ê il ill JH Í TÍí j z71 url Í U as lj 1 ll li fz 4o Exemplo l E Í i i Íl 6bCz1z A função abc ab C ab nao esta na forma normal disiuntiva pois no ter ceiro termo falta a variável c ou seu complemento 50 Exemplo As funçoes abaixo nao estao na forma normal disiuntiva abbcac abcabd acd abcac abc b ã A ql arbrcr CDQCDCD oooo zze QoDo Q 1 abc qi abc abc i di abc fL J i a 3 cr fI z abc abc ab ab abc pois todas as variaveis não se encontram em todos os termos A fun ão inv d TRANSFORMAÇÃO DE uiviA iuNçÃo DisJuN1ivA QUALQUER EM ioiiiviA ivoiiiviAi oisiuNTivA Ç ersa e z pode também ser obtida diretamente da coluna de z da seguinte maneira Seiaafunçao 3 b 1 C Z 1 yabdabc abcd o ocoo zzz zzzzz a qual nao esta na forma normal disiufltlvfl POTQUB 00 Dfm Íem falta 3 má vel c e no segundo termo falta a variável d Como LLDo C d podemos escrever yabdabcl ddlflbCd irzzsr f ze l E l À afblcf Íi 1 l ll l i Ç abc A abc z abc 1 H abc l yabdabdabcdabcd abcd esta na forma normal disjuntiva P0fÍ00Í0 z a b c a be ab ab ab iiivEiisA DE UMA iuNçÃo NA ionMA NoiiiviAi DisiuNTivA 12 3 FORMA NORMAL CONJUNTIVA Seja a funçao abcabcabc Queremos determinar sua inversa z e Pflfa ISto lan na forma normal disiuntiva mao de um meio conhecido ou seia a tabela verdade Construamos çaremos I t ao as tabelas verdade de z e z Feito isto procedemos conforme vimos no cap 10 Exemplo tulo anterior Dizemos que uma função booleana está na forma norma conunt1va quando em todos os fatores aparecem todas as variáveis envolvidas ou seus complementos Y lã b 0 l la b Cl la b cl está na forma normal coniuntiva 133 20 Exemplo z la b a b cl não esta na forma normal conjuntiva porque no pri meiro fator falta a variável c ííxr TRANSFORMAÇÃO DA FORMA NORMAL DISJUNTIVA EM FORMA NORMAL CONJUNTIVA MEDIANTE A TABELAVERDADE Seia transformar a função da forma normal disiuntiva para a forma normal conjuntiva Procedese da seguin te maneira a Constrói se a tabelaverdade de y e dizse que a função está na forma binária v ab ab s0zUzâa Ii ív OCB CDO O c fu mm t Í fz 7 JI Qs Ar I i E a baab abíy O n nul Í 1 1 WlfT 7 oo Aoca za ooo aaa Oa IIÍIflxflc CCD6 oo l E li V Í Í f 1 ffl fÍ zwivz Portanto Seia a função bl Determinase y ab ab c Inverte se y para obterse y pelo Teorema de De Morgan ab abl O arbvr abr ab abl 12 4 FUNÇÕES NA FORMA BINARIA z O 7 i 3 bi la b está na forma normal coniuntiva que desejamos escrever na forma binária Como toda variável nao complementada corresponde ao valor 1 e as complementadas correspondem a 0 tal funçao pode ser escrita da seguinte maneira Í Vl0dl 20011 Exemplo Dada a tabelaverdade da função y esçrevëia na forma bmana abc abc ii i ablcf abc y abc abc abC 1 3bC 001501 V 001 010 100 110 o que nos dá Ylazbzcl l001010100110 Chamase indice de um termo dado na forma binaria o numero de valores 1 contidos nesse termo Assim por exemplo os termos 1010 1101 1000 e 1111 tem respectivamente indices 231 e 4 125 iuNçÓEs NA ioRiviA oEciiviAL Seja representar na forma decimal a função dada na tzbeia verdade ll 1 i n9abf il f ff T O OCJ ycdcd l l E i Í f 1 Nessa tabela Í9m05 ndec1mal n bIfläf0 comC9 528 p 1 1 mm fzzz GSCFBVB I fab Êl23 1au1amuO LT Í zz l nluII rf 4 I 4 b f shQOOG ccOQ QO 0 co 1 Í l I ll I 1 Í l I F J Í0 mJmmhwwO oc1oOO 444 ccocCO0 OnOnOoOO3 oÇooo1OI l 1 l 1 1 l 1 1 1 i gllfl 1 1 1 1 1 1 r JuElt r LO 1 flabcd 2l14671Ú12 Entao os valores decimais que correspondem a f 1 são 2 6 3 Pd9m P dendo de manerra análoga nas funções dadas pelas tabelas a seguir roce flabc El135 l ginl í l 4 zIf l ll âúJšIí 11 3fI 1 i 1 LI l lnrIr1ais 2 3 4 5 6 7 8 9 10 EXERCÍCIOS 1 1 Representar mediante cfrculos de Euler a função n E lõ E E y abc abc abc abc Indicar mediante uma tabelaverdade a função yad Representar sobre uma tabelaverdade a função s y abcd ad Usando a tabelaverdade dar a função y a d sob a forma normal dis iu ntiva Passar para a forma normal disjuntiva as funções a y a bc b y d c ad b c bcd abc d V ad cd Dar as funções do exercicio 5 na forma binária Dar as funções do eerc1cio 5 na forma decimal Determinar mediante a tabelaverdade a inversa da funçao booleana y abc abc abc abc Transformar para a forma normal conjuntiva as seguintes funções booleanas ayac babab c zabc ac ab dabHCbd Representar mediante círculos de Euler as funções ai yz1zz1 2235ô71 bi zb1 z1ooooo1o11111 Exprimir sob forma binária as funções a xabbc b yabbcac c zabcbcab 4Yumi Àfinízz lr 1 dwabCbCab 9 tabcdabc abd Exprimir sob a forma decimal as funçoes do exercicio 11 qxøxuVV Construir as tabelas verdade relativas as funçoes a xab 22 3 bl via ial Elooo 010110 ai via ba1 21001011 11il ai via bai 210 3 5 ai zlaba dl 2i0010 0101 01101011 f zlabc d Êl0 3 5 711 13 Minimizoçõo de Funções Minimizar ou simplificar uma função booleana é a operação mediante a qual se reduz ao minimo o número de seus termos resultando em economia do circuito a ela correspondente Os métodos de aplicação mais freqüentes na minimização de uma função ou expressão booleana são O 1 Método Algébrico 2 Método do Mapa de Karnaugh 3 Método de QuinaMclluskey Vejamos como se procede em cada um deles 131 MÉTODO ALGÊBRICO Este método já foi estudado como aplicação dos teoremas da Álgebra de Boole daremos apenas um exemplo como lembrete para possibilitar compara ções futuras com os demais Seja minimizar a função y ab c lb cl ab la bf b c Soiuçãb V allb cl lb c ab la b lb c abb bc be cc ab ab ac bb bc abc ab ab ab aa be ab be ab ac la a b be ac bbcac bcac bc1a bc 132 MÉTODO DO MAPA DE KARNAUGH O mapa de Karnaugh é uma forma modificada de tabelaverdade e nos per mite representar graficamente uma função booleana e se for o caso simpli ficáIa MAPA A UMA VARIÁVEL No caso de uma variável o mapa é formado por duas celas que correspon dem a cada um dos valores 0 e 1 que podem se atribuídos à variável Esta tabela pode ser lida de uma das seguintes maneiras 01 01 conforme usemos os valores atribuídos à variável ou à própria variável na forma complementada ou não Atribuiremos sempre o valor 1 à variável não comple mentada e o valor 0 à variável complementada MAPA A DUAS VARIÁVEIS E formado por quatro celas que correspondem às combinações binárias que podem ocorrer com estas variáveis Os termos da função a ser representada devem ser escritos em ordem alfabética e em todos os mapas de Karnaugh a ordem em que entrarão as variáveis deve vir claramente anotada na parte superior esquerda Representação binária Representação literal Representação decimal b0 1 be 1 b0 1 IIIJIIIIEI IiãIIIiIII IIJIIIIãII EIIII EI IIEI f Íz fzëfl Vz 1 ff fe Qz wi af i vy z Tr 5 1z z ff zêaêzi z 1 l MAPA A TRÊS vAiiiAvEis ab 0 IWIIEÍI 01 EEIIEII 11 EIIIIII 1 EEE 0 1 M 01 11 1 äfl MAPA A QUATRO VARIÁVEIS ab cd 00 01 11 10 00 0000 01001100 1000 01 0001 01011101 1001 11 001101111111 10 9010 0110 7 7 1110 1010 1 oo afblczrdi arbcrds abcfdf abocsda 10 afbaa azigad abaú aizraai O À niI NJ U1 AJ I NJ O3 MAPA A ciNco vARiÃvEis 0 1 as28 i ab l9 11 abfcdi abolñ abcd abcd cdab 00 01 11 10 00 Í 3 1 01 g ia 9 11 1 10 g 14 iq J I 11 10 I I ab ab ll aa 139 07 10 ad 99l 00 W 1 00 01 1 101 0 11 11 10 A 10 l ill 1 MAPA A seis vAiiiÃvEis Of 0 1 1 ab ab cd 00 O1 11 10 cd 00 01 11 10 00 00 01 11 10 10 ab ab 00 01 11 10 cd 00 01 11 10 001111 1 01 011111 11 111111 10 101111 01 0 11 00 Como se pode notar a partir de seis variáveis o processo de representação tornase complicado e difícil e não atende ao caráter prático da Álgebra de Boole Posteriormente estudaremos outro método que supera esta dificuldade REPRESENTAÇÃO DE UMA FUNÇÃO NA FORMA CANÕNICA MEDIANTE A 0 MAPA DE KARNAUGH E ç Representemos mediante o mapa de Karnaugh a seguinte função na forma normal disiuntiva y abc abc abc abc Tratase de uma função a três variáveis e o mapa a ser utilizado é É be O 1 00 01 11 10 Para representar a função através do mapa colocamos o valor 1 nas celas 142 correspondentes a cada termo da função deixando as demais vazias Assim 1 E agrzzz fiíilèvIV ILLJ t z Í 7711 51 i VL V z v 6 ÍvÂè 5 JÍ5 eziz AW ëá Y lvvfi nt ÇAIl FME ia 1 II 01 11 HI 10 II y abc abc abc abc nEPiiEsENTAçÃo os UMA uNçÃo ouAiouEii Representar a função a quatro variáveis que não está na forma normal disjuntiva e em três de seus ter mos falta uma variável Usando o teorema expresso por ab ab a temos abcd abcd abcd abcd abcd abc d abcd abcd abcd abcd abcd abcd ab cd YZ y abcd abd abc acd e construindo o mapa correspondente vem Notese que no caso de funções como y abcd ab deve se considerar todas as possibilidades de aplicação do teorema ab ab a ficando o mapa cor ab cd W1 01 00 11 A 01 d 11 10 í g y abcd abcd abcd abcd abcd ab c d respondente como se vê a seguir I OQ llU e III2 nl III 0 I 01 I 11 I 10 IIIII LO niO Pseí 1 za irei no na SIMPLIFICAÇAO DE FUNÇOES MEDIANTE O MAPA DE KARNAUGH Na representação de uma função mediante o mapa de Karnaugh devese buscar a forma mais simples de representação considerandose que uma função Dada uma funçao representada em um mapa de Karnaugh se encontrarmos a duas variáveis pode ser representada em mapas para maior número de variáveis Assim a função y ab tem as seguintes representações 8 H ab a 0 1 ba O 1 ad 0 00 1 01 11 10 a8 Ô qn lí míÔ 01 11 Duas celas que diferem em apenas uma variável são ditas adjacentes e podem ser combinadas pelo teorema ab ab a Num mapa de Karnaugh podemos ter celas adjacentes sem que tenham lados comuns Exemplos a1ba01 blaaaoi 0 00 Ê 1 01 s cla Ê 10 ia ba 0 1 111613 00 011110 00 oo I oi 11 101 01 11 10 1 às ab ab bc 00 01 11 10 IJ 01 11 10 G 01 11 10 oi InI 11 IIIII iaIl P termos em celas adiacentes podemos fazer uma simplificação No mapa que repre senta a função 8 OOU Ú 0 fli sentado Quando os termos a simplificar encontramse em celas nos extremos do mapa indicamos conforme segue ab C 00 y abcd abcd abcd abcd abcd podemos efetuar uma simplificação substituindo abcd abcd por acd A ope 1 ração é indicada agrupandose os dois termos conforme mostra o mapa retroapre 0 E I O I 01 Il H I 10 ÍíflIIIIIE gp 1 No mapa da função A y abcd abcd abcd abcd I O o28aãIII8III2 ni IIII o III L Í E r L 1 1 1 iIIflmee1 O A temos b a a 1 I 1121f I aum 11 10 aa 00 01 11 10 ai O0 ll 01 ilDI a I íàf y abc abcd abcd uainfz íIí1 i ab cd 00 01 11 10 0 I 1Ífl1I 11 lfllíI 10 y abd abcd abcd Transportando estas representações para um único mapa obtemos ab c 00 01 11 10 11 101 10 IÍI y abc abd bcd que é a função simplificada Para simplificar ao máximo uma função tornase ne cessário incluir o mesmo termo em diversos agrupamentos Vejamos agora o caso em que as celas sao adjacentes duas a duas Seja simplificar a função Vy abc abc abc abc 1 O mapa correspondente é 11 II 10 y bcd abcd abcd 639 1 01 EDÍIIÊÉ 1 Jg ë 121151 ç V 11z í 1 ii 1 11f 1 rísr S ÍÍt 7T T 1 1 q I ãi 0 bca 0 1 00 01 III 11 IIII 10 e temos duas maneiras diferentes para simplificar a mesma função ou seja aaa 0 1 1 0 1 z1ierreeaa 11 10 ia Considerando que as celas adjacentes no caso de ac e ac diferem na variável a e no caso de bc e be diferem na variável b podemos agrupálas da maneira mos trada a seguir ou seja 80 naQI 6 bc 0 1 01 1 ri Q 01 aiii raiiii 11 im 11 lšiiil io Éã ia EZ Outros casos de simplificação ab 00 01 11 10 01 00 lililili 01 KIÍÃIÉÍÚE I BÉS 3ill 2 I E 11 XXVIIE 10 1 1 vabad ybdbdzd GED z Vejamos agora em que as celas são adjacentes quatro a quatro ë Seja o mapa de Karnaugh que representa a função qn zë CÍI1 i H Ii1 WP á vi Íêl 1 Wi v abcd abcd abcd abcd abcd abcd abcd abcd tl V 1 a3e ElleElle Ille r 1z Í 01 1ri vÍÍ i azt iil É 1 F2 Í vÊÍ V Y i L f z là ft z fif f ri Temos J A Í il lafz fz Tí z rf Ize cd 00 00 5zí 11 1 10 z zÍV I m çnxnfj I 11 01 11 1o I 7 l 1 ff Jg Ç E I 1 iÍ z E t j V Cd d d r 1 il Íâfz fiz z 3 f 1 ea oo 01 11 10 I fr 12 i 1 oo âf Q f LUiileeHU nJ i z V 1rT O I E zr 5j 4 1zzif 1f75 1 1 1Ê 5 1 1 ñ 4Ú Í ê J I z Í 1 T y À ft iai íeiw y ad ad d zig 1 íÇ Hai 1 g Jc sã a 133 METooo DE ouNEMzcLusEY 1 Írm 1 4 1 n r i ír Este método aplicase exclusivamente a funções booleanas na forma normal repeo e a função 5mpfcada é dada po disiuntiva e notação binária Supera as limitações do mapa de Karnaugh que pode ii ser aplimdo a funçõesoom mais de seis variáveis e apresenta um procedimento que f 148 permite a utilização fle computadores Consiste na aplicação sucessiva do teorema xy X V Z 1 1 T nz 1 i expresso por ab ab a a termos que diferem entre si apenas por um digito binário Para utilização deste método procedese da seguinte maneira ai Classificamse e agrupamse os termos da função de acordo com seus Índices bl Comparamse todos os termos de um dado grupo com cada termo do cl grupo seguinte ou seja de Índice imediatamente superior mediante a utilização do teorema ab ab a Aplicase sucessivamente esse teo rema comparando cada termo do grupo de indice i com todos os ter mos do grupo de Índice i 1 até esgotaremse as possibilidades O termo resultante consiste na representação fixa original com o digito diferente substituido por um traço Marcase com todos os termos comparados com ao menos outro termo Após tabular os termos comparados procedese novamente conforme o exposto no item b até esgotaremse as possibilidades Os termos que ficarem sem a marca formam o conjunto dos termos irredutíveis 19 Exemplo Determinar os termos irredutiveis da função fVZ yZ yZ xz yz yz xyz Solução fxyz 200l100010011101111 RIR W T 13 o 1 A 15 1oo23o1 y HH9O a Q ÍÇÍ BláN AJi N 1357 z o1 1537 go g 37 57 Como 1357 e 1537 representam um mesmo termo não será necessário 45 ç xyz l 1 ú 1 1 1 1 0 1 r l 1 1 1 Jf J 1 150 v abcd izbca abcd abcd zbzó zbcdt zB4 x I 14E211 JlÍÍÊÂÍÁ Í r I fz z E z jfi s tv z J z z 29 Exemplo Solução Minimizar a funçao 15 Y abcde abcde abcde abcde 8bCCl 8b0dB l abcde abcde a abcde ab0dB Solução Por conveniência de notação podemos escrever a função dada na forma bi nária ou decimal Temos yabcde Ê00111101100001010000100100110111100 011110110000100 e vzbzóe v2221õ1813281f124z 2 q N af 21a šo N 4 P 1 412 0 bcide 1 à 9 oo oiÍÊoc0 EAQÔ B6LAPgaooooo iš O 5 16 Y 1618 1o 1 12 1228 9 zéoo 1 I I 1 13 1e221o Y f nun 13 i E 22 28 15 e a função simplificada é Y bcde acde bcde abde acde abCe 39 Exemplo Minimizar a função V vabcdl 2o10011000001010101101110 e vabdl 3l41215614l a1bcd Ímëabcwcl Labcd 15 0 1 412614 0 412 O Éí Hao az cn01 É unleÃuIEz i v bd acd abc aba Embora a função esteja simplificada não está minimizada pois apesar de serem seus termos irredutiveis não são termos irredutíveis indispensáveis Para identificar tais termos usamos o crivo dos termos irredut1eis 1 M4 5e 125 14 bd a acd abd Neste crivo aparece na horizontal a notação decimal correspondente aos termos e na vertical os termos da função simplificada O fato de cada termo da fun ção simplificada ser parte dos termos representados na forma decimal é indicado por um ponto na interseção das linhas e colunas correspondentes do crivo As co lunas em que a cada número decimal corresponde apenas um único termo identi fica um termo irredutfvel e indispensável Assim bd e acd são termos irreduti veis indispensáveis os demais são termos supérfluos Então a função minimizada resulta y bd acd Exencrcios 1 Determinar a função representada no mapa O 1 if 1 7 f z f I 7 I í L já Tlab zaiz 00 01 11 10 C Q0 0111 1 00 1 ç 1 L 00 1 01 1 W 01 1 H 1 11 T1 A 11 1 10 iii I 1 í 10 Í jm Z l L Í fr 2 Representar as seguintes fuflÇÕ95 U0 mapa de K3ma9h 1 Yabc ab bc ab Gb bd i vizbza and abr bcd bfid J mQICJ9L vabai 2i00010101111110101001 yabcd E245671114 y3b1bClC1i fi V aba c d 2 3 Simplificar mediante o mapa de Karnaugh as fuflÇ0e5 do e f 4 Simplificar pelo metodo de Quine McClusley as seguintBS UflÇ05 3 y ab bc ac fl bd flbC abc bi V z abc abc ab ac ab C y3bcabC3CbC3dbd dl Ylabc El01247l 3 e Ylabcd 2101 35791 115 f yabcd 20246789101113 9 yzaqbdababdabcd exercicio 4 e às funções 5 Desenhar os circuitos relativos as funçoes dadas no ç minimizadas 152 l Tv pv r1 z z z L H fé z éa äfifiä N9 Decimal 0 IOIOIhbãhãi 9 10 11 12 13 14 15 16 17 ia 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 N9 Binário 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1T04 1110 1111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 100000 100001 100010 100011 100100 100101 100110 100111 101000 101001 101010 101011 101100 101101 101110 101111 I Q I g 1 Q 1 o Correspondencia entre numeros decimais e binários N9 Decimal 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 f NP Binário 110000 110001 110010 110011 110100 110101 110110 110111 111000 111001 111010 111011 111100 111101 111110 111111 1154 14 I Í 0 Portos Logicos Até agora estudamos as funções booleanas descritas algebricamente Nos circuitos lógicos costumase indicar tais funções graficamente de modo a torná las mais simples i A representação gráfica das funções booleanas é feita mediante simbolos padronizados por normas internacionais chamados blocos ou portas lógicas As portas lógicas são as bases dos circuitos lógicos e têm por finalidade corn binar as diferentes grandezas booleanas de modo a realizar determinada função Cada porta lógica pode ter diferentes linhas de entrada porém somente uma linha de sa ida conforme veremos No decorrer do nosso estudo trabalharemos com as normas americanas MILSTD806B IMILITARY STANDARD de uso muito freqüente na prática citaremos as normas da CEI COMISSION ÉLECTROTECHNIOUE INTERNA CIONALE reconhecidos internacionalmente e as normas alemãs DIN 40700 IDEUTSCHE INDUSTRIE NORM I Daremos a seguir uma tabela com os circuitos tabelasverdade que os de finem portas lógicas segundo as normas citadas e funções booleanas correspon dentes que interessarão ao nosso estudo ie 1Ú J Li 1 fiífš F U N ÇAO BOOLEANA TABELA I L D N CIRCUITO VERDADE iii Í M i 51 l D Ep zz 13ID Êh izizi mnEni I NvEnsoa NEGAÇÃOI fr 1 Tí TTTÊ inAQ QI O00 uu 1I O O iJiz Âoc OO U NAN D ifl ÔC3U QDOX I il Ê2 1i Ú D i 1iz HICDO nopoa ÍÍ4Q É invertida ííuíil1uv lOO QaC U i1Ii 1 invertida LL OO Q Exclusivo Liíi 1 Exemplo Representar mediante portas logicas a função x ab i Soluçao 29 Exemplo Dar o circuito logico correspondente à funçao z ab H b Soluçao z ab b 39 Exemplo Determinar a funçao correspondente ao circuito logico OUm Soluçao bcd h 11 fviifi Vejamos a resoluçao de alguns exemplos 1137 i É faiz tz z11 7 1 z I 92 1 V ama z z1 12 z 31 âÊM 3 Solução 49 Exemplo Representar a função definida pela tabela verdade como circuito logico A tabela verdade define a funçao x ab0abcabc abc Simplifiquemos a funçao Entãox bcabac E o circuito lógico correspondente será if L CD oco ooc ao ca 5 O d C3 o Nil 41 í nl 4l ul ui abcabcbcbc abcab bcbc abcacbc abcacb abcacab acabac cabac bcabac 59 Exemplo Ilffinuf Soluçao u Dar o circuito logico correspondente a area hachurada nos circulos de A função correspondente a area hachurada e abcabcabc Simplificando obtemos Portanto x ac bc E o circuito Iogco procurado e C b 6 Exemplo Simplificar o circuito logico mediante utihzaçao do mapa de Kamaugh Iäll Ê äiflíãf ÉJDJ Solução O circuito Iogco dado corresponde a funçao abd acd bcd ab a cd a quatro variáveis e que nao esta na for ma normal disiuntiva faltando uma variavel em quatro de seus termos e duas va a b C bo a be riáveis em um de seus termos Usando o teorema expresso por ab ab a temos acabc ham c ab c acbc abcd abcd abcd ab cdabcda bcd abcd abcd a bcd que representada no mapa de Karnaugh nos dá null na Hum 1 Representar mediante portas lógicas as funções i donde tiramos a função simplificada x ab cd 4 fi T 1 fi i ii 3 š a 1 z b iLÊÍ1í 1 s 1Ê x i lr ii zv r i Ê iYšff 5f é iiI lÀxKÉ Éãfihñà 1 I d ii 1 57 Jvi f C d i Hšrb ç Íá gif í z tl f ft f À É M1 z Exercícios i i eÊ L 4 v31 t 4 34 z Êr5f IfÍ Ítr ii z z1z U r zzwrt e desenhamos o circuito lógico pedido ou cl 3bšj C a b dl 8 C el a b a b C lj b z a b z c x a b c d dl Y abc abc i Dar as tabelasverdade correspondentes a cada circuito logico 3 Í E a x a b c os b fi v 1 Ú i r T HW 1 Ê1i b 2 Determinar as funções correspondentes aos circuitos lógicos É rz if z z 15161 rf 1 2 a r l T a z zL z if z i F ii q9 ug f Í b c b i dl z Ç il c Í a r 2 f i Qu 1 i f ha z Í iii K à A E M ih a i 160 c a b a b dilviviwfifiwdw D l l fufíflí l l Í J 1 l l l il r ƒííufr i l I Mz l J 1 1 J J çi i É 4 Desenhar os circuitos correspondentes lSmDlf3d5l às t3bla5Vefdad al bl cl r1 ia b z ab lazbcy ii 0 1ÍiiicEci ÁÓEÓÀEÍoiói ciÍÃb35 ci o oo oio c calltDeco iÍii l i l 1 oo Í S foo 1 li1 O Ãá óÓ 4 do DEc Àt 5 1 a O I l f Q f 6 Desenhar os circulos de Euler correspondentes aos circuitos logicos a X fff bl riLiiiign i l li a l i b V O 5 i 1 I O util 1 z ItÍ E uler 5 Desenhar os circuitos logicos correspondentes aos circulos de E b z N zh u zz 1 14 is Éhof zh 3 a b t ru 51 ln eu eu V z el išlltii Jf à 11 1 L4 2515Z t 2 E É vI L õ 1t zzz w 8 7 Simplificar usando os teoremas da Álgebra de Boole os circuitos Iogicos 1em 3 div Ê Í f z 163 z fJçfÍ2ti fm bl 8bm z C ÊÊD 3 b cl b a b a b 8 Simplificar os circuitos lógicos mediante utilização do mapa de Karnaugh al 8 b 3 W C b c 8 za š iii f b L1 ZÉ 1 P L 5 b c cl b dl al b C i 3br C ai C dr 3 C 3 cl al af al al b c oocr n Z ff zfvur rrz zcznvufufvdlVwdnIIdvfIII i J 1z zfrINf i lê lf f 1 li i 1 l 1 zwifl Í mf 1 1 i i l 1 J JI l l J i J ias Bibliogroƒio ALENCAR FILHO Edgard de Iniciação à lógica matemática São Paulo Nobel 1976 AIDEP Algèbre de Boole Utilisation pour la simplification des circuits logi I 7 ques Cours Programé DUNOD 1971 BITTINGER Marvin L Logic and proofi AddisonWesley 1982 Boscoro A1ziâzsN0zzzs ae zzzzzzz F1cLs1 santo André 1971 BOUWENS A J Digital instrument course Part 1 NV Philips Gloeilampen fabrieken Test and measuring department Eindhoven The Netherlands BUDDEN F J An introduction to algebraic structures Longman 1975 BUKSTEIN Edward Practice problems in number systems Logic and Boolean Algebra Howard W Sams Co 1982 CALABRESE c1uszppeL 41gezrzz af Boole lvfiizno Dzifizw 1973 CASTRUCCI Benedito Introdução à lógica matemática São Paulo Nobel 1975 CIANFLONE Franco Lífllgebra di Boole e i circuiti logici Milano Etas Libri SPA 1978 ENNES Harold E Boolean algebra for computer logic Howard W Sams Co 1978 iss to FAURE R DENISPAPPIN M KA UBMANN A Cours de calcul booléien appliqué Paris Albin Michel 1970 FINE Nathan J An introduction to modern mathematics George Allen and 333 l Yfrgl uz f 11 elur I É50 I 1r Í5Le f I v5 azz z f 1 T Gin ie n za EÍ z if fié 1 äÍí V í  ia 4à Q 1øf zfârTšlfT FRT iT z l IaÉ zr wêí Ç Fëfien bÍÍl 2 I H f Lsí êtw 11 sf 1se 3f 21145 z rf z Ii z z 7 M Jz z f 3f Zzt 7 12ff I 1 em if i 1 1r sz 7 àÊs rn sz zz 41 r Y z Re111 S V fJ fša zw z s z f f l ë y Ts Ê r H L ä Y gr LT nn rf ln 12 1 U Unwin 1967 FLEGG H Graham Boolean algebra and its applications Blackie London and Glasgow 1964 HILL Frederik J PETERSON Gerald R Introduction to switching theory and logica design John Wiley Sons 1974 HOERNES Gerhard E HEILWEIL Melvin F Introducción al algebra de Boole y a los dispositivos lógicos Autoenseñanza Programada Madrid Parariinfo 1976 J igrsgë Llzfz i F 47 5 Ez É Íi 5 3 85z T sf sE tz z r iz l 4nfIÍ1jf 5 1 fe f 42 Ffrã 1 tficz ifzzai Qi âlšë 1 iffi kb Ê iu Ê HOHN FIHHZ E Applied boolean algebra Macmillan 1966 KOHäVl8Zv1 Switching and finite automata theory New Delhy McGrawHill 9 KORFHAGE Robert Logic and algórithms John Wiley Sons 1966 LARNEY Violet Hachemeister Abstract algebra a first course Prindle Weber Schmidt 1975 LEE Samuel C Modern switching theory and digital design Englewood Cliffs PrenticeHall 1978 J MANGE Daniel Analyse et synthèse des systèmes logiques St Saphorin Edi tions Georgi 1978 McCLUSKEY E J Introduction to the theory of switching cirçuits New York McGrawHill 1965 MUROGA S Logic design and switching theory New York John Wiley 81 Sons 1979 PINZÓN Álvaro Conjuntos y estructuras Harper 81 Row 1973 RUSSI Gonzalo Zubieta Manual de lógica para estudiantes de matemiáticas México Trillas 1977 ROETHEL Louis F Logic sets and numbers Wadsworth Publishing 1978 SOUTH G F Booledn algebra and its uses Van Nostrand Reinhold 1974 WHITESITT J Eldon Boolean algebra and its applications Addison Wesley 1961