Logica e Algebra de Boole - Jacob Daghlian - Guia Completo

LÓGICA E ÁLGEBRA DE BOOLE Diferentemente de textos convencionais este livro adota a estratégia de ensinar através de exemplos com a utilização de um instrumental lógico que facilita o entendimentoe a modelagem de sistemas ris O uso de ilustrações como meio de exposição proporciona neste taxto bases seguras para generalizações 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 modelo matemático de inúmeras 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ático em 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 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 econo mia de tempo NOTA SOBRE O AUTOR Jacob Daghlian é licenciado em Matemática pela Faculdade de Filosofía Ciências e Letras da Fundação Santo André onde leciona Álgebra como professoradjunto É titular de Álgebra Booleana na Faculdade de Filosofia Ciências Letras Prof Carlos Pasquale Leciona também nas Faculdades Integradas Ibirapuera e possui larga vivência industrial que lhe permitiu avaliar a importância da matéria ora apresentada APLICAÇÃC Livrotexto A E I LÓG Cia de Proc plinia CIRC DOREs do curso de Ciência da Computação publicação atlas JACOB DAGHLIAN LÓGICA e ÁlGEBRA de BOOLE atlas LÓGICA E ÁLGEBRA DE BOOLE JACOB DAGHLIAN LÓGICA E ÁLGEBRA DE BOOLE 3ª Edição SÃO PAULO EDITORA ATLAS SA 1990 EDITORA ATLAS SA Rua Conselheiro Nébias 1384 Campos Elísios Caixa Postal 7186 Tel 011 2219144 PABX 01203 São Paulo SP 1986 by EDITORA ATLAS SA Rua Conselheiro Nébias 1384 Campos Elíseos Caixa Postal 7186 Tel 011 2219144 PABX 01203 São Paulo SP 1 ed 1986 2 ed 1988 3 ed 1990 ISBN 852240643X Impresso no Brasil Printed in Brazil Deposito legal na Biblioteca Nacional conforme Decreto N 1825 de 20 de dezembro de 1907 TODOS OS DIREITOS RESERVADOS É proibida a reprodução total ou parcial de qualquer forma ou por qualquer meio salvo com autorização por escrito do Editor Capa Paulo Ferreira Leite Biblioteca Central ZILA MAMEDÊ Reg N 127326 1990 Natal 28 11 94 Entrada 60828 84 KB 1430 94017407 Dados de Catalogação na Publicação CIP Internacional Câmara Brasileira do Livro SP Brasil Daghlian Jacob 1936 Lógica e álgebra de Boole Jacob Daghlian 3 ed São Paulo Atlas 1990 Bibliografia ISBN 852249643X 1 Álgebra booleana 2 Lógica simbólica e matemática I Titulo CDD5113 511324 901898 Índices para catálogo sistemático 1 Álgebra booleana 511324 2 Lógica matemática 5113 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 Pela ajuda de dois sábios meus pais Leon e Hripsimé Pelo incentivo de minha esposa Fulúba Pela carinhosa presença de meus filhos Leon e Ricardo Pelos meus irmãos Carlos Luiz e Celi Pela oportunidade de realizar este trabalho Elevo o pensamento em gratidão a DEUS 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 142 Tabelaverdade 28 Exercícios 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 34 26 Bicondicional 35 Exercícios 36 9 3 CONSTRUÇÃO DA TABELAVERDADE 39 Exercícios 42 4 RELAÇÕES DE IMPLICAÇÃO E DE EQUIVALÊNCIA 46 41 Definições 46 42 Relação de implicação 47 43 Relação de equivalência 47 44 Equivalências notáveis 48 45 Propriedades 51 Exercícios 51 5 ARGUMENTO VÁLIDO 54 51 Definição 54 52 Regras de inferência 56 Exercícios 58 6 TÉCNICAS DEDUTIVAS 62 61 Prova direta 62 62 Prova condicional 65 63 Prova biocondicional 67 64 Prova indireta ou por redução ao absurdo 68 65 Prova indireta da forma condicional 70 Exercícios 71 7 FLUXOGRAMAS 77 Exercícios 85 8 QUANTIFICADORES 89 81 Sentença aberta 89 82 Quantificador universal 90 83 Quantificador existencial 91 84 Valores lógicos de sentenças quantificadas 93 85 Negação de sentenças quantificadas 93 Exercícios 96 9 INTRODUÇÃO À ÁLGEBRA DE BOOLE 97 91 Operador binário 97 92 Propriedades das operações 97 93 Sistemas algébricos 105 Exercícios 114 10 FUNÇÕES BOOLEANAS 117 Exercícios 120 11 REPRESENTAÇÃO DAS FUNÇÕES BOOLEANAS 122 111 Diagramas de Venn ou círculos de Euler 122 112 Tabelasverdade 123 113 Representação geométrica 124 Exercícios 128 12 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 Exercícios 137 13 MINIMIZAÇÃO DE FUNÇÕES 139 131 Método algébrico 139 132 Método do Mapa de Karnaugh 140 133 Método de QuineMcCluskey 148 Exercícios 152 14 PORTAS LÓGICAS 154 Bibliografia 166 Prefácio Os últimos 10 anos vêm presenciando um aumento sem precedentes da aplicaçã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 vêm sendo paulatinamente introduzida nos currículos das escolas de 2º e 3º graus sob formas diversas É pois com grande satisfação que apresentamos ao leitor este dedicado trabalho do colega Jacob Daghlian Tratase de um livro que surgiu como fruto do intenso trabalho de pesquisas bibliográficas e das experiências do magistério vivenciadas 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 perceber 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 utilizando 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 exclusivamente 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 certamente 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 Apresentaçã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ências e Letras da Fundação Santo André Ao redigilo como primeira razão moveunos o interesse de entregar aos nossos alunos um texto que contivesse os pontos principais de nosso curso e que superasse a necessidades nesta primeira parte dos estudos de livros estrangeiros de difícil e cara obtenção Outro aspecto importante 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 caracteristica 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 comercialização deste trabalho Finalizando prestamos nossa homenagem aos professores que desde o Jardim da Infância participaram de nossa formação dedicandolhes este livro e para evitar omissões citando as diferentes escolas que cursamos Jardim de Infância e Primário Academia de Comércio Horácio Berlinck Jaú SP Ginásio Ginásio Estadual de Jaú Jaú SP Colégio São Norberto Jaú SP Colégio Dante Alighieri São Paulo SP Científico 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 Águias 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 São Paulo 1986 JACOB DAGHLIAN 1 Sistemas 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 0 Sim Não Dia Noite Preto Branco Ligado Desligado 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 excludentes bem definidos A Lógica começou a desenvolverse com Aristóteles 384322 aC e os antigos filósofos gregos passaram a usar em suas discussões conceitos anunciados na forma 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 cálculos ratiocinator ou lógica mathematica ou logística Estas idéias nunca foram teorizadas por Leibniz porém seus escritos trazem a idéia da Lógica Matemática No século XVIII Leonhard Euler 17071783 introduziu a representação gráfica das relações entre sentenças ou proposições mais tarde ampliada por John Venn 18341923 E W Veitch em 1952 e M Karnaugh em 1953 Em 1847 Augustus DeMorgan 18061871 publicou um tratado Formal logic envol 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 aversão à Matemática o qual entre outras coisas escreveu A Matemática congela e embor ta 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 DeMorgan interessouse pelo debate entre o filósofo e o matemático escrevendo The mathematical analysis of logic 1848 em defesa de seu amigo mais tarde publicou um livro sobre Álgebra de Boole chamado An Investigation of the laws of thought 1854 e em 1859 escreveu Treatise on differential equations no qual discutiu o método simbólico geral O trabalho de George Boole foi ampliado por Lewis Carrol 1896 Whitehead 1896 Huntington 1904 e 1933 Sheffer 1913 e outros Este período de desenvolvimewto da Lógica culminou com a publicação do Principia mathematica por Alfred NorthWhitehead 18611947 e Bertrand Russell 18721970 que representou grande ajuda para completar o programa sugerido por Leibniz que visava dar uma base lógica para toda a Matemática A Álgebra de Boole embora existindo há mais de cem anos não teve qualquer 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 fói bemsucedido pois ao invés de desenvolver a teória já existente tentou desenvolver a Álgebra Booleanapor conceitos próprios Em 1938 Claude E Shannon mostrou em sua tese de mestrado no Departamento de Engenharia Elétrica do MIT Massachusetts Institute of Technology a aplicação da Álgebra de Boole na análise de circuitos de relés usandoa com rara elegância o que servia de base para o desenvolvimento da teoria dos interruptores O assunto deste curso ainda que elementar visa mostrar as aplicações da Álgebra de Boole ou Álgebra 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 Chamamos interruptor ao dispositivo ligado a um ponto de um circuito elétrico que pode assumir um dos dois estados revogado 1 ou aberto 0 Quando fechado o interruptor permite que a corrente passe através do ponto enquanto aberto nenhuma corrente pode passar pelo ponto Representação a aberto a fechado Por conveniência representaremos os interruptores da seguinte maneira a Neste caso somente conheceremos o estado do interruptor se tivermos a indicação de que a 1 ou a 0 Conhecendose o estado de um interruptor poderemos 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á aberto chamase complemento inverso ou negação de a e denotase por a Sejam a e b dois interruptores ligados em paralelo Numa ligação em paralelo 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 paralelo por a b Então 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 simplesmente ab Então Assim considerando os estados possíveis de serem assumidos pelos interruptores nas ligações em série e em paralelo podemos notar que 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 a b b a a b b a a a 1 a a 0 a 0 a a 0 0 a 1 1 a 1 a Todas estas equações podem ser verificadas desenhandose o circuito apropriado As ligações de 13 CONJUNTOS Sejam a b c conjuntos de pontos tomados num espaço E dado Na figura abaixo o retângulo é o nosso espaço E e as figuras internas são os conjuntos 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 interseção de a e b que pode ser denotada também por ab Seja a o conjunto de todos os pontos do espaço considerado que não pertencem 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 conjunto universo Para dois conjuntos quaisquer a e b do universo 1 valem as igualdades 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 a a 1 a a 0 a b b a a b b a a 0 a a 0 0 a 1 1 a 1 a Podemos verificar sua validade construindo os diagramas apropriados por exemplo pelos círculos de Euler ou diagramas de Venn Outros resultados podem ser obtidos para três conjuntos quaisquer a b e c 1º Exemplo Mostrar mediante diagramas apropriados que a b c a b a c Solução 2º Exemplo Ilustrar pelos círculos de Euler a expressão pr pq r Solução 3º Exemplo Dar a expressão da região hachurada no diagrama Solução x y z x y z EXERCÍCIOS 1 Desenhar os diagramas de EulerVenn para mostrar a p q b p q c p q p q d p q r e p q r f p q r 2 Dar as expressões correspondentes aos conjuntos hachurados 3 Usando círculos de Euler mostrar que a p q p q b p p q p q c p p 14 PROPOSIÇÕES Chamamos conceito primitivo aquele conceito que aceitamos sem definição Enquadraremos neste caso o conceito de proposição e portanto não o definiremos Entretanto nada impede que conheçamos suas qualidades lembrando que proposição é uma sentença declarativa afirmativa e que deve exprimir um pensamento de sentido completo podendo ser escrita na forma simbólica ou na linguagem usual Então são proposições a 104 1 b 3 π 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 proposição é verdadeira é a falsidade 0 se a proposição é falsa Por exemplo a O Japão fica na África b O Brasil ganhou a Copa do Mundo de 1970 no México O valor lógico da proposição a é a falsidade 0 e da proposição b é a 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 Indicaremos tais proposições por letras minúsculas de nosso alfabeto da seguinte forma p Carlos é careca q É dos carecas que elas gostam mais r O número 16 é quadrado perfeito s log2 1 0 A proposição composta é formada por duas ou mais proposições relacionadas pelos conectivos e ou e se então ou implica Serão indicadas por letras maiúsculas P Q R Exemplo Sejam p 1 2 3 q 2 1 duas proposições no caso ambas de valor 1 Podemos formar as proposições compostas P p q 1 2 3 e 2 1 Q p q 1 2 3 ou 2 1 R p q 1 2 3 implica 2 1 Observações a Quando for conveniente indicar que uma proposição composta P é formada pelas proposições simples p q r escrevese P p q r b As proposições componentes de uma proposição composta podem ser elas mesmas proposições compostas c As proposições compostas são também chamadas fórmulas proposicionais Indicaremos o valor lógico de uma proposição simples p por Vpl Assim se p é verdadeira Vpl 1 e se p é falsa Vpl 0 No caso de uma proposição composta P indicase por Vpl Nas proposições abaixo p O sol é verde Vpl 0 q Um hexágono tem 9 diagonais Vql 1 r 2 é raiz da equação x2 3x 4 0 Vrl 0 141 Princípios fundamentais da lógica matemática a Princípio do Nãocontradição Uma proposição não pode ser simultaneamente verdadeira e falsa b Princípio do Terceiro Excluído Toda proposição ou é só verdadeira ou só falsa nunca ocorrendo um terceiro caso De acordo com esses princípios podemos afirmar que toda proposição admite um e um só dos valores 10 Chamamse conectivos lógicos palavras ou expressões que se usam para formar novas proposições a partir de proposições dadas Damos abaixo algumas proposições compostas por diferentes conectivos grifados P O número 4 é quadrado perfeito e o número 3 é ímpar Q O triângulo ABC é retângulo ou isósceles R Se João estuda então sabe a matéria 142 Tabelaverdade Pelo Princípio do Terceiro Excluído toda proposição tem Vp 1 ou Vp 0 Nas composições o valor lógico de qualquer proposição composta depende unicamente dos valores lógicos das proposições simples componentes ficando por eles univocamente determinado Usaremos como meio auxiliar na construção das tabelasverdade o diagrama da árvore que se vê ao lado das tabelas Na situação atual os números que aparecem na primeira coluna têm apenas a finalidade de indicar o número de linhas para cada exemplo apresentado Para as proposições compostas veremos que o número das componentes simples determina o número de linhas das tabelasverdade Exemplos a Ppq f log3 1 0 g sen² 30 cos² 30 2 h sen² π7 cos² π7 1 i log 2 3 log 2 log 3 j Todo número divisível por 5 termina em 0 l O par x x é igual a x m O par ordenado x x x n 0 0 o cosx cos x p 2 0 2 Escrever cinco proposições de valor lógico igual a 1 3 Escrever cinco proposições falsas Outras maneiras de exprimir uma negação Não é verdade que João é estudante É falso que João é estudante 22 CONJUNÇÃO A conjunção de duas proposições p e q é uma proposição verdadeira quando Vp Vq 1 e falsa nos demais casos isto é só é verdadeira quando ambas as componentes forem verdadeiras Chamamos p q a conjunção de p e q e lêse p e q 23 DISJUNÇÃO INCLUSIVA OU SOMA LÓGICA 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 disjunção inclusiva ou soma lógica denotaremos a disjunção de p e q por p q e lêse p ou q O valor lógico da disjunção inclusiva de duas proposições é definido pela tabelaverdade 24 DISJUNÇÃO EXCLUSIVA e xor A palavra ou tem dois sentidos no caso anterior temos a disjunção inclusiva que exemplificamos a seguir P João é estudante ou mecânico indicando que pelo menos uma das proposições p João é estudante q João é mecânico é verdadeira podendo ambas ser verdadeiras João é estudante e mecânico Por outro lado temos o caso em que isto não ocorre é disjunção exclusiva definida a seguir A disjunção exclusiva de duas proposições p e q é uma proposição verdadeira somente quando Vp Vq e falsa quando Vp 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 e q e lêse p ou q mas não ambas O valor lógico da disjunção exclusiva é definido pela tabelaverdade Então dadas as proposições abaixo vem 25 CONDICIONAL O condicional de duas proposições p e q é uma proposição falsa quando Vp 1 e Vq 0 sendo verdadeira nos demais casos Representase o condicional de p e q por p q e lêse se p então q A proposição p é chamada antecedente e a proposição q é o consequente do condicional O valor lógico do condicional de duas proposições é definido pela tabelaverdade Então dadas as proposições abaixo vem Assim p q r é da forma bicondicional a proposição p q q r é da forma condicional ao passo que p q q r é composta por disjunção Portanto a correta colocação de parênteses quando for o caso é de extrema importância 3 Construção da Tabelaverdade Para se construir a tabelaverdade de uma proposição composta dada procedese da seguinte maneira e para todas as linhas da tabelaverdade vem P00011011 1101 O conjunto V 00011011 é o conjunto de todos os valores possíveis de serem assumidos pelas proposições componentes de Ppq e considerando que a cada elemento de V corresponde um e somente um dos valores de 01 diremos que PpqV 01 ou seja a tabelaverdade de Ppq é uma aplicação de V em 01 O mesmo se dá com proposições compostas por um número maior de proposições componentes 2º Exemplo Construir a tabelaverdade da proposição Ppq p q q p Solução Procedendo de maneira análoga ao exemplo anterior temos Então determinar P00011011 consiste em construir a tabelaverdade para a proposição dada e responder na forma indicada nos exemplos dados Há outros métodos para construção de tabelasverdade porém nos restringiremos ao método utilizado nos exemplos dados 29 Exemplo Construir a tabelaverdade da proposição Ppqr p r q r Solução No caso de três proposições componentes temos Fazendo V 000001010011100101110111 ou seja V é o conjunto de todos os valores possíveis de serem assumidos pelas proposições componentes de Ppqr mediante raciocínio análogo ao caso de Ppq temos Então a tabelaverdade de Ppqr é uma aplicação de V em 01 49 Exemplo Construir a tabelaverdade da proposição Ppqr p q q r p r Solução Neste caso temos P000 P001 P010 P011 P100 P101 P110 P111 1 ou P000001010011100101110111 11111111 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 contingência ou indeterminação EXERCICIOS 1 Construir as tabelasverdade das proposições seguintes a p q b p q c p q p q d p q p e p q p q f q q p g p q q p h p q p q i p r q r j p r q r k p p r q r m p q r p q r 2 Determinar P00011011 em cada um dos seguintes casos a Ppq p q b Ppq p q p c Ppq p q p q d Ppq p q p q e Ppq p q p q 3 Determinar P000001010011100101110111 em cada um dos seguintes casos a Ppqr p r q b Ppqr p q p r c Ppqr p q p r 4 Determinar P101 em cada um dos seguintes casos a Ppqr p q r b Ppqr p r q r c Ppqr r p q r p q d Ppqr p q r p r q 5 Sabendo que Vp Vr 1 e Vq Vs 0 determinar o valor lógico de cada uma das proposicões a p q r s b p q s r c p q p r s d p q r s p s 6 Sabendo que os valores lógicos das proposições p q r e s são respectivamente 1 1 0 e 0 determinar o valor lógico de cada uma das proposicões a p q q p b p s s r c r p p r d p r p r 7 Dizer quais as proposições que satisfazem às tabelasverdade abaixo A p q B p q C p q D q p E nenhuma delas A p q B p q C p q D p q E nenhuma delas A p q B q p C p q D p q E nenhuma delas 8 Determinar as proposições compostas por conjunção que satisfazem a cada uma das tabelasverdade indicadas 9 Determinar as proposições compostas por disjunção que satisfazem a cada uma das tabelasverdade indicadas 10 Determinar as proposições compostas por condicional que satisfazem a cada uma das tabelasverdade indicadas 4 Relações de Implicação e de Equivalência O estudo das relações de implicação e de equivalência de grande importância na Lógica será feito de maneira sucinta como convém ao nosso estudo Antes porém definiremos alguns conceitos introdutórios 41 DEFINIÇÕES a Duas proposições são ditas independentes quando em suas tabelasverdade ocorrem as quatro alternativas Exemplo p q 0 0 0 1 1 0 1 1 b Dizemos que duas proposições são dependentes quando em suas tabelasverdade uma ou mais alternativas não ocorrem Notação p q Observação importante Vale para os símbolos e a mesma observação feita para e Exemplo Verificar se p q p q Solução p q pq p q p q p q 0 0 0 1 1 1 0 0 1 0 1 1 1 1 0 0 0 1 Comparando as tabelasverdade de p q e p q verificamos que não ocorre 10 nem 01 numa mesma linha Portanto p q p q De maneira prática verificase que duas proposições dadas são equivalentes quando suas tabelasverdade forem iguais 44 EQUIVALÊNCIAS NOTÁVEIS Dupla negação p p Leis idempotentes a p p p b p p p Leis comutativas a p q q p b p q q p a p q p q q p 0 0 0 0 0 1 1 1 1 1 1 1 b Verificar como exercício Leis associativas a p q r p q r b p q r p q r a p q r q r p q r p q p q r 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 b Verificar como exercício Leis de De Morgan a p q p q b p q p q a p q p q p q p q p q 0 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 b Verificar como exercício Leis distributivas a p q r p q p r b p q r p q p r a p q r q r p q r p q p r p q p r 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 b Verificar como exercício Bicondicional p q p q q p p q p q q p p q q p 0 0 1 1 1 1 0 1 0 0 1 0 Condicionais a p q b q p contrapositivo c q p recíproca do condicional d p q recíproca do contrapositivo p q p q p q q p q p p q 0 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 Destas tabelas tiramos as seguintes equivalências notáveis p q q p q p p q 45 PROPRIEDADES a A condição necessária e suficiente para que p q é que o condicional p q seja uma tautologia Demonstração A A condição é necessária p q p T q Se p q não ocorre 10 logo o condicional p q é uma tautologia B A condição é suficiente p T q p q Se p T q não ocorre em sua tabelaverdade a alternativa 10 logo p q cqd b A condição necessária e suficiente para que p q e que p q seja uma tautologia Demonstração análoga à anterior EXERCÍCIOS 1 Dizer se entre as seguintes proposições há implicação ou equivalência quando tomadas aos pares a p b q p c p q d q p e p q 2 Mostrar que a q p q b p q p q c p q não implica p q d p não implica p q e p q p 3 Verificar mediante tabelasverdade as seguintes equivalências a p r p r b p q p q c r r r d p q p q p q e p q q p f p q q r p g p q p p h p p q p i p p q p q l q p q p q ll p q p r r q r ml p q p r p q r nl p q r p r q 4 Dadas as proposições abaixo escrever as proposições equivalentes usando as equivalências e notações indicadas a Dupla negação p q p q p q b Leis idempotentes p q p q p q p q p q c Leis comutativas p q r s r p s p s p r d Leis de De Morgan p q p q r s p q r e Leis associativas r p q p r s s s r p q p r p s f Leis distributivas s p q p q r r s g Contrapositivo p q r p q r p q r s h Condicional p q r p lq r p q i Bicondicional p q q p p q r r p q p q 53 5 Argumento Válido 51 DEFINIÇÃO Chamase argumento válido toda sequência de proposições p1 p2 pn1 n ℕ tal que a conjunção das n primeiras implica à última isto é p1 p2 p3 pn pn1 onde p1 p2 p3 pn são as premissas e pn1 é a conclusão O argumento é falso se nessas condições não houver implicação isto é p1 p2 p3 pn pn1 Então para testar a validade de um argumento procedese da seguinte maneira a constróise a tabelaverdade de p1 p2 p3 pn b constróise a tabelaverdade de pn1 c comparase as tabelas se na mesma linha ocorre 10 nesta ordem não há implicação e o argumento é falso se na mesma linha não ocorrer 10 haverá implicação e o argumento é válido Observação A sequência das proposições pode apresentarse nas seguintes formas p1 p2 p3 ou p1 p2 p3 pn pn1 pn1 54 1º Exemplo Testar a validade do argumento p q p p q q Solução Temos p1 p q p2 p p3 p q p4 q Devemos verificar se p1 p2 p3 p4 isto é p q p p q q Procedendo conforme o critério já estabelecido temos p q p q p q p q p q p p q q 0 0 1 1 1 0 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 Não há implicação pois na segunda linha da tabela ocorre 10 portanto o argumento é falso p q p p q q O leitor deve ter notado na tabela a repetição da coluna correspondente à última proposição da sequência q 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 q p q q p q ao invés de verificar p q p p q q que seria a forma correta 55 2º Exemplo Testar a validade do argumento p q p q q q Solução Devemos verificar se p q p q q q Construindo as tabelasverdade correspondentes temos p q q p q p q p q p q q q 0 0 1 1 0 0 0 1 0 1 1 0 1 1 1 1 0 1 Há implicação pois não ocorre 10 numa mesma linha portanto o argumento é válido 52 REGRAS DE INFERÊNCIA As regras de inferência são argumentos válidos simples 1 União U p q p q É a implicação p q p q 2 Modus Ponens MP p q p q É a implicação p q p q V Modus Tollens MT p q q p É a implicação p q q p Adição AI p p q É a implicação p p q Simplificação S p q p É a implicação p q p Silogismo Hipotético SH p q q r p r É a implicação p q q r p r Silogismo Disjuntivo SD p q p q É a implicação p q p q Regras do Bicondicional BIC a p q q p p q É a implicação p q q p p q b p q p q É a implicação p q p q Dilema Construtivo DC p q r s p r q s É a implicação p q r s p r q s Dilema Destrutivo DD p q r s q s p r É a implicação p q r s q s p r 57 56 Dupla Negação DN p p ou p p É a implicação p p ou p p Regra da Absorção RA p q p p q É a implicação p q Simplificação Disjuntiva S p r p r p p r É a implicação p r p r p EXERCICIOS 1 Testar a validade dos seguintes argumentos a p q p q a p b 1 r r t s s 2 Dados os conjuntos de valores lógicos A 1 0 0 0 B 0 1 1 1 C 1 1 1 0 D 1 1 1 0 qual deles torna o seguinte argumento válido p q premissa premissa conclusão 0 0 1 1 0 1 0 1 1 0 0 0 1 1 0 0 3 Dado o argumento p q premissa premissa conclusão 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 0 qual dos conjuntos de valores lógicos abaixo torna esse argumento válido A 1 1 0 0 B 1 0 1 1 C 1 1 1 1 D 1 0 0 1 4 Mudamse o uso de tabelasverdade testar a validade dos argumentos a q p p q b p q p q p q c r p p q q d a b d b d f e p q q r p q q r f r s t r t r s 5 Dar os nomes de cada um dos seguintes argumentos a c d e c d a b f b c a c a b b c a b d a b c c e a b c a d 59 58 b f b d b d f c p q q r p q q r d d a b a b e r s s r f a b c a a b c a g b c b c d d h a b b c a c i a b c a b c a b a b c a b c a c d e d e a c m r p q p q r n a c c o a b c a b c p s t r t r s 6 Completar cada um dos seguintes argumentos válidos a r p q q b a b c a c a b b c a b d a b c c e a b c a d 61 60 6 Técnicas Dedutivas 61 PROVA DIRETA Dizse que uma proposição q é formalmente dedutível conseqüência de certas proposições dadas premissas quando e somente quando for possível formar uma seqüência de proposições p1 p2 p3 pn de tal modo que a pn é exatamente q b para qualquer valor de i i 1 2 3 n pi ou é uma das premissas ou constitui a conclusão de um argumento válido formado a partir das proposições que a precedem na seqüência Escrevese p1 p2 p3 ou p1 p2 p3 pn1 pnq p n1 pnq 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 Vejamos alguns exemplos 1 Exemplo Provar s dadas as premissas 1 t 2 t q 3 q s Demonstração 1 t premissa 2 t q premi ssa 3 q s premissa 4 q Modus Ponens 1 e 2 5 s Modus Ponens 3 e 4 cqd Justificação do pass agem 4 1 q t q ou seja t q t q conforme se pode verificar q pela lista das regras de inferência 2 Exemplo Provar r s dadas as premissas 1 s q 2 t q 3 t r Demonstração 1 s q premissa 2 t q premissa 3 t r premissa 4 q s1 5 q t DN4 6 t MT 2 e b 7 r MP 3 e 6 8 r s A 7 cqd Justificação das passag ems 4 s q ou seja s q q q 5 q q q Exemplo Provar a v dadas as premissas 1 t a 2 v t 3 a m 4 v m Demonstração 1 t a p 2 v t p 3 a m p 4 v m p 5a a pp 6a m MP 3 e 5a 7a v SD 4 e 7a 8a a v PC 5a 7a 5b v pp 6b t MP 2 e 5b 7b a MP 1 e 6b 8b v a PC 5b 7b 9 a v v a U 8a 9b 10 a v Equivalência 9 cqd 64 PROVA INDIRETA OU POR REDUÇÃO AO ABSURDO Observemos inicialmente que de uma contradição podese deduzir qualquer proposição De fato seja a contradição p p e α uma proposição qualquer Temos p p p p 0 1 0 1 0 0 1 p p p 2 S 1 p p α 3 p S 1 4 p α A 2 5 α SD 3 e 4 Seja agora provar α e α partir das premissas P 1 P 2 P 3 P n sequência essa que chamaremos P Consideremos as premissas P e α e procuramos deduzir α a partir delas isto é vejamos se P α α A proposição α é formalmente dedutível de P α se P α α isto é P α τ α Mas P α τ α p τ α α Princípio da Exportação Ora essa última proposição constitui uma tautologia se ocorrer a seguinte implicação P α α isto é P α α α α α α α α α P α e P α α Então para mostrar a validade de um argumento por prova ou demonstração indireta introduzse a negação da conclusão como premissa provisória e deduzse uma contradição por exemplo q q 1o Exemplo Provar r dadas as premissas 1 p r 2 r q 3 p q Demonstração 1 p r p 2 r q p 3 p q p 4 r pp 5 q MP 2 e 4 6 p q De Morgan 3 7 q DN 5 8 p SD 6 e 7 9 r MP 1 e 8 10 r r U 4 e 9 11 r Prova indireta de 4 a 10 cqd 33 6 t q q ou seja t q q t 7 t r t ou seja t r t r 8 r r s ou seja r r s Na indicação das regras de inferência utilizadas na demonstração de um teorema MP 3 e 6 significam que a regra Modus Ponens foi aplicada entre as proposições de nºs 3 e 6 da sequência o mesmo ocorrendo com as demais abreviações Observações a Qualquer tautologia pode ser incluída na sequência após qualquer proposição já colocada De fato seja α uma proposição qualquer já escrita na sequência e β uma tautologia É claro que o argumento αβ é válido pois α β α β é válido pois não ocorre 10 b Se α for uma proposição já colocada na sequência e β for outra sentença tal que β α então seguindose a α podese colocar β De fato sendo β α temos β Log β α pode entrar na sequência por ser uma tautologia Mas β α α β Log α β pode ser incluída na sequência E finalmente podese escrever β pela regra do Modus Ponens 3o Exemplo Provar x 0 dadas as seguintes premissas 1 x 0 então x y 2 x y então x z 3 x z Inicialmente por razões de conveniência passemos as proposições dadas para a forma simbólica Nosso problema reduzirseá ao seguinte Provar a dadas as premissas 1 a b 2 b c 3 c Demonstração 1 a b p 2 b c p 3 c p 4 b MT 2 e 3 5 a MT 1 e 4 6 a DN 5 cqd 4o Exemplo Provar a dadas as premissas 1 a c 2 c m 3 m r 4 r Demonstração 1 a c p 2 c m p 3 m r p 4 r p 5 m SD 3 e 4 6 m DN 5 7 c MT 2 e 6 8 a MT 1 e 7 9 a DN 8 cqd 62 PROVA CONDICIONAL Seja provar α β dadas as premissas P 1 P 2 P 3 P n Fazendo o conjunto das premissas igual a P tratase de mostrar que é válido o argumento P α β isto é P α β Tratase de validar esse argumento Ocorrendo a 64 65 34 validade temos P α β ou P τ α β A letra grega τ sobre o símbolo do condicional indica tratarse de uma tautologia Princípio da Exportação Para mostrar este princípio utilizaremos a equivalência notável p q p q Então temos p τ α β P α β P α β P α β P α β P α β P α β Portanto se P α τ for tautologia isto é se P α τ β ou seja se for possível deduzir β de P α também será uma tautologia a proposição equivalente e portanto P α β é dedutível de P Dessas considerações seguese a técnica da prova condicional para demonstrar a validade do argumento cuja conclusão tem forma condicional α β introduzse α como premissa provisória indicada por pp e deduzse β 1o Exemplo Provar r p dadas as premissas 1 p q 2 r q Demonstração 1 p q p 2 r q p 3 r pp 4 q MP 2 e 3 5 p MT 1 e 4 6 r p cqd 2o Exemplo Provar c d dadas as premissas 1 b c 2 ld b Demonstração 1 b c p 2 ld b p 3 c pp 4 c DN 3 5 b MT 1 e 4 6 d b De Morgan 2 7 d SD 5 e 6 8 c d PC 3 a 7 cqd 3o Exemplo Provar a b dadas as premissas 1 a i g 2 j g h 3 j b Demonstração 1 a i g p 2 j g h p 3 j b p 4 a pp 5 a i A 4 6 g MP 1 e 5 7 j g h Equivalência 2 8 g h A 6 9 g h DN 8 10 j MT 7 e 9 11 b SD 3 e 10 12 a b PC 4 a 11 cqd 63 PROVA BICONDICIONAL A prova de um argumento cuja conclusão é uma proposição da forma bicondicional α β é semelhante à prova condicional com a diferença de que é feita em duas partes distintas Então dada uma proposição α β primeiro provase α β e a seguir provase β α concluindose pela validade do argumento Observação Da mesma forma como encontramos a contradição r r para provar r poderemos encontrar a contradição q q para provar p como veremos no exemplo a seguir Isto é a contradição procurada pode envolver ou não a mesma letra da proposição a ser provada 2º Exemplo Provar p dadas as premissas 1 q r 2 p r 3 q Demonstração 1 q r p 2 p r p 3 q p 4 p pp 5 p DN 4 6 r MP 2 e 5 7 q SD 1 e 6 8 q q U 3 e 7 9 p Pl 4 a 8 cqd 65 PROVA INDIRETA DA FORMA CONDICIONAL Para provar a validade de um argumento cuja conclusão é da forma condicional p q mediante a demonstração indireta usamos p q como premissa provisória pp a seguir p q por equivalência e p q seguindose daí p q Na prática começamos pela hipótese H e pela negação da tese T como premissas provisórias H T Provar p q n 1 p q pp n 2 p q Equivalência n 1 n 3 p q De Morgan n 2 n 4 p S n 3 n 5 q S n 3 Exemplo Provar r q dadas as premissas 1 r s 2 q s Demonstração 1 r s p 2 q s p 3 r pp 4 q pp 5 r DN 3 6 s SD 1 e 5 7 q MT 6 e 2 8 q DN 4 9 q q U 8 e 7 10 r q Pl 3 a 9 cqd EXERCÍCIOS 1 Provar t dadas as premissas 1 p s 2 p q 3 s r r 4 q r 2 Provar s dadas as premissas 1 t r 2 r 3 t s 3 Provar t s dadas as premissas 1 e s 2 t j 3 e i 70 71 4 Provar s dadas as premissas 1 p q r 2 p 3 t q 4 t s 5 Provar r s dadas as premissas 1 s q 2 t q 3 t r 6 Provar x y 5 dadas as premissas 1 3x y 11 3x 9 2 3x 9 3x y 11 y 2 3 y 2 ou x y 5 Utilizando a demonstração condicional 7 Provar a h dadas as premissas 1 a f g 2 j g h 3 j 8 Provar t s r dadas as premissas 1 r q 2 t 3 s q 9 Provar q t dadas as premissas 1 s r 2 s p 3 p q 4 r t Utilizando a demonstração indireta 10 Provar y 2 x y dadas as premissas 1 x y x y ou y x 2 y 2 ou x 2 3 x y ou y x x 2 11 Provar t dadas as premissas 1 t s 2 t t 3 s f 12 Provar e m dadas as premissas 1 s r 2 s e 3 r m 13 Provar t s dadas as premissas 1 r b 2 t s r 3 b s 4 t Utilizando a demonstração indireta do condicional 14 Provar p q dadas as premissas 1 p q r 2 s t r 3 s t u 15 Provar p q dadas as premissas 1 p q r 2 r 16 Provar p s dadas as premissas 1 p q r s 2 q Utilizando um método dedutivo de sua escolha 17 Provar p q dadas as premissas 1 p q r s 2 r s 18 Provar p r dadas as premissas 1 p q 2 r q 72 73 19 Provar s dadas as premissas 1 p q 2 s p 3 q r 20 Provar s dadas as premissas 1 p q r s t 2 p q r 3 r 21 Provar 2x 12 y 4 dadas as premissas 1 2x 3y 24 2 3x 6 y 4 ou 2x 12 3 2x 12 x 6 ou 2x 3y 24 4 x 6 22 Verificar mediante as regras de inferência a validade dos seguintes argumentos a s e e g s g b s p p w j s w j c a u u b l b a j a b i a 23 Nas demonstrações abaixo justificar as passagens indicadas a 1 p q p 2 r q p 3 p s p 4 p s 5 p 6 q 7 r 8 s 9 r s cqd b 1 l e p 2 e s p 3 l p 4 e s p 5 e 6 s cqd c 1 a b c p 2 c d e p 3 f b d p 4 f a p 5 f a 6 f 7 b d 8 a 9 b c 10 b 11 c 12 d 13 c d 14 e cqd d 1 p q q r p 2 p p 3 s t p 4 t p 5 s 6 p 7 p q 8 p q 9 q r 10 q cqd e 1 b c a p 2 a b d p 3 a pp 4 b d 5 b 6 b c 7 b 8 a cqd f 1 a b c p 2 d a d b p 3 c d b p 4 d a b 5 a b 6 a b 7 c 8 d b cqd 74 75 7 Fluxogramas O fluxograma constitui um método alternativo para as tabelasverdade na verificação da validade de um argumento no qual se ilustra o raciocínio 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ógico da conclusão ou em que 0 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 particularidades de cada uma das técnicas dedutivas já estudadas Vejamos alguns exemplos 1º Exemplo Provar p dadas as premissas 1 p q 2 q Solução Justificação 1 Consideramos as premissas verdadeiras fazendo p q 1 e q 1 2 Como q 1 pela negação temos q 0 3 Levando q 0 em p q 1 temos p 0 1 4 Pela definição de condicional p 0 1 se e somente se p 0 5 Como p 0 temos p 1 o que mostra ser válido o argumento pois premissas verdadeiras conduzem a uma conclusão verdadeira 2º Exemplo Testar a validade do argumento a b a b Solução Justificação 1 Consideremos as premisas verdadeiras fazendo a b 1 e a 1 2 Como a 1 pela negação a 0 3 Levando a 0 em a b 1 temos 0 b 1 4 Não podemos concluir se b é verdadeira ou falsa pois pela definição de condicional 0 1 0 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 3º Exemplo Provar q dadas as premissas 1 p q 2 p r 3 r Solução Justificação 1 Consideremos as premissas verdadeiras fazendo p q 1 p r 1 e r 1 2 Como r 1 por negação temos r 0 3 Levando r 0 em p r 1 temos p 0 1 4 Pela definição de condicional p 0 1 se e somente se p 0 5 Fazendo p 0 na premissa p q 1 temos 0 q 1 6 Pela definição de disjunção 0 q 1 somente se q 1 Portanto o argumento é válido 4º Exemplo Testar a validade do argumento p q p q p Solução Justificação 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 Se q 1 substituindo na premissa p q 1 temos p 1 1 4 Pela negação temos p 0 1 5 Pela definição de disjunção p 0 1 somente se p 1 Portanto o argumento é válido pois premissas verdadeiras levam a uma conclusão verdadeira 5º Exemplo Testar a validade do argumento p q p q p Solução Justificação 1 Consideremos as premissas verdadeiras fazendo p q 1 e p q 1 2 Pela negação p q 0 3 Pela definição de disjunção se p q 0 então p 0 e q 0 4 Como p 0 pela negação temos p 1 5 Levando p 1 e q 0 na premissa p q 1 temos 1 0 1 6 Pela definição de condicional 1 0 0 Considerando as premissas verdadeiras chegamos a uma contradição Portanto o argumento é falho 6º Exemplo Provar p r dadas as premissas 1 p q 2 q r Solução Como a conclusão é da forma condicional consideramos o antecedente p verdadeiro e procuraremos mostrar que o conseqüente r é verdadeiro 1 p q 1 q r 1 2 3 4 0 q 1 5 q 1 6 1 r 1 7 r 1 Justificação 1 Consideremos as premissas verdadeiras fazendo p q 1 e q r 1 2 Consideremos verdadeiro o antecedente da conclusão premissa provisória fazendo p 1 3 Como p 1 pela negação temos p 0 4 Levando p 0 na premissa p q 1 temos 0 q 1 5 Pela definição de disjunção 0 q 1 somente se q 1 6 Substituindo q 1 em q r 1 temos 1 r 1 7 Pela definição de condicional 1 r 1 somente se r 1 Portanto 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 é 0 r 1 79 Exemplo Provar p dadas as premissas 1 p q 2 p q Solução Usemos o método indireto 1 p q 1 2 q r 1 3 4 5 6 7 Justificação 1 Consideremos as premissas verdadeiras fazendo p q 1 e p q 1 2 Consideremos a conclusão falsa negação da conclusão fazendo p 0 3 Levando p 0 em p q 1 temos 0 q 1 4 Pela negação temos 1 q 1 5 Pela definição de condicional 1 q 1 somente se q 1 6 Pela negação q 0 7 Fazendo p 0 e q 0 em p q 1 temos 0 0 1 Usando a premissa provisória p 0 chegamos à contradição 0 0 1 Portanto p 0 é eliminada ficando a outra possibilidade p 1 como solução 1 r 1 q r 1 p q 1 2 3 4 5 6 r 0 p 0 0 q 1 q 1 1 0 1 Justificação 1 Consideremos as premissas verdadeiras fazendo p q 1 q r 1 e r 1 2 Consideremos a conclusão falsa fazendo p 0 3 Fazendo p 0 em p q 1 temos 0 q 1 4 Pela definição de disjunção 0 q 1 somente se q 1 5 Pela negação r 0 6 Substituindo q 1 e r 0 em q r 1 temos 1 0 1 Usando a premissa provisória p 0 chegamos à contradição 1 0 Portanto p 0 é eliminada ficando a outra possibilidade p 1 como solução 1 p q 1 q r 1 2 3 4 5 6 7 0 0 1 Justificaçã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 0 somente se p 1 e r 0 4 Pela negação temos p 0 5 Fazendo r 0 em q r 1 temos q 0 1 6 Pela definição de condicional q 0 1 somente se q 0 7 Substituindo p 0 e q 0 em p q 1 temos 0 0 1 Usando a premissa provisória p r 0 chegamos a uma contradição 0 0 1 Portanto p r 0 é eliminada ficando a outra possibilidade p r 1 como solução EXERCÍCIOS 1 Testar a validade dos argumentos abaixo mediante o uso de fluxogramas a q p p q b p q p q q c p q q r p d q b c b c a e p r p q q r s r f p q r r s s q q gl 1 x 1 x 0 x 0 ou 2x 0 2x 0 1 x 1 2 Mostre através do fluxograma usando os métodos direto e indireto que o argumento abaixo tem premissas contraditórias p q p q p 3 Mostre através do fluxograma usando os métodos direto e indireto que o argumento abaixo não contém informações suficientes para deduzir a conclusão p q q r p s 4 Dados os argumentos abaixo a qual deles corresponde o fluxograma a p q p q q b p q p q q c p q p q q p d nenhum deles p q 1 p q 1 q 0 p 0 1 p 0 0 0 1 0 1 5 A qual dos argumentos abaixo corresponde o fluxograma a a b b c a c b a b b c c a c a c c a b b c c a d nenhum deles a b 1 b c 1 c 1 b l 1 b 0 1 b 1 a 1 1 a 0 1 a 0 a 1 6 Qual fluxograma corresponde ao argumento p q q r p a p q 1 q r 1 q 1 r 1 p 1 1 p 0 1 p 1 8 Quantificadores 81 SENTENÇA ABERTA Sejam as proposições p 3 5 11 Vp 1 q x 5 11 Vq A proposição p como podemos ver é verdadeira ao passo que nada podemos afirmar sobre o valor lógico na proposição q Vq que somente será conhecido quando x for identificado Neste caso dizemos que a proposição q é uma sentença aberta ou função proposicionalν Nas sentenças abertas os símbolos x y X e outros são chamadas variáveis Chamamos conjunto universo da variável ao conjunto das possibilidades lógicas que podem substituir a variável na sentença Denotaremos este conjunto por U Cada elemento de U chamase valor da variável U às vezes é tacitamente imposto pelo contexto mas pode também ser escolhido pelo agente de estudo em questão 1º Exemplo Seja a sentença aberta x 5 11 Podemos impor que o conjunto universo da variável seja N ou Z ou Q ou R ou o conjunto U 1 3 5 7 2º 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 88 89 c p q 1 q r 1 p 1 q 1 p 1 p q 1 q 1 q r 1 p1 p 1 1 p 0 1 p 1 d nenhum deles b p 1 q 1 r 1 p q 1 q r 1 p 1 UX Mercúrio Vênus Terra Marte Júpiter Saturno Urano Netuno Plutão CONJUNTOVERDADE da sentença é o conjunto dos valores da variável para os quais a sentença é verdadeira Denotaremos este conjunto por V V x U Vpx 1 onde px é uma sentença aberta na variável x 1º Exemplo Dada a sentença aberta x 5 11 x R determinar seu conjuntoverdade Solução V x R x 6 2º Exemplo O conjuntoverdade da sentença aberta O planeta X é o maior planeta do Sistema Solar é V Júpiter 3º Exemplo Determinar o conjuntoverdade das seguintes sentenças abertas a x 11 21 U N b 2x 5 13 U Z Soluções a V 10 b V 4 3 2 1 0 6 7 8 9 82 QUANTIFICADOR UNIVERSAL Usaremos o símbolo chamado quantificador universal para exprimir o fato de que para todo x em um dado conjunto a proposição Px é verdadeira Uma proposição do tipo Para todo x Px é simbolicamente representada por x Px A proposição Todo inteiro é racional podese escrever 1 x x Z x Q 2 Para todo x se x Z então x Q 3 Para todo x se x Z então x Q 4 Para cada x se x Z então x Q 5 x x Z x Q 6 Qualquer que seja x x Z x Q 1º Exemplo Escrever de maneira simbólica a proposição os números do conjunto A são todos os reais Solução Rx x real xx A x R Ax Rx 2º Exemplo Simbolizar a proposição Para todo x se x é real então x Q Solução Qx x Q Rx x é real x Rx Qx 3º Exemplo x x² 0 x R 83 QUANTIFICADOR EXISTENCIAL No caso de proposições que envolvem expressões do tipo Existe Há pelo menos um Para ao menos um e Algum usaremos o símbolo chamado quantificador existencial para exprimir o fato de que para um ou mais elementos de um dado conjunto a proposição Px é verdadeira Uma proposição do tipo Existe um x tal que Px pode ser escrita simbolicamente x Px As seguintes proposições têm o mesmo significado x x N Existe um x tal que x N Algum número é natural Existe pelo menos um número natural 90 91 19 Exemplo Escrever de maneira simbólica a proposição Existe x tal que x² 1 2x Solução Px x² 1 2x x Px 29 Exemplo Simbolizar a proposição Existe x Q tal que 0 x 1 Solução Px 0 x 1 x Q x x Q Px Os quantificadores podem aparecer juntos ou não conforme mostramos nos exemplos abaixo 19 Exemplo Para todo x e para todo y x y y x é representada simbolicamente por x y x y y x 29 Exemplo Para todo x existe um y tal que x y representase por x y x y 39 Exemplo Existe um x tal que para todo y x y 0 representase simbolicamente por x y x y 0 40 Exemplo Existe um x e existe um y tal que x I escrevese x y x E 50 Exemplo Para todo x se x é par então existe um y tal que x 2y é representada simbolicamente por x x é par y x 2y 84 VALORES LÓGICOS DE SENTENÇAS QUANTIFICADAS A sentença x Px é verdadeira se e somente se o conjuntoverdade de Px e o conjunto universo forem iguais isto é U V e falso quando U V A tabela a seguir nos dará alguns exemplos do que acabamos de definir x Px U V Vx Px x x 0 0 0 1 x x 0 0 1 0 0 x x² x 1 R R 1 x 2x² 3x 1 0 N 0 0 x 2x² 3x 1 0 Z 1 0 A sentença x Px é verdadeira se e somente se o conjuntoverdade de Px é nãovazio ou seja V 0 e falso quando V 0 Vejamos alguns exemplos através da tabela abaixo x Px U V Vx Px x x 0 0 0 1 x x 0 0 1 0 1 x x² x 1 R R 1 x 2x² 3x 1 0 N 0 0 x 2x² 3x 1 0 Z 1 1 85 NEGAÇÃO DE SENTENÇAS QUANTIFICADAS Seja a sentença aberta Px e U a b c d o conjunto universo da variável x Então x Px Pa Pb Pc Pd e sua negação é dada por x Px Pa Pb Pc Pd Pela lei de DeMorgan x Px Pa Pb Pc Pd x Px 92 93 Portanto x Px x Px Vejamos agora a que equivale a negação da sentença x Px Temos x Px Pa Pb Pc Pd e sua negação é dada por x Px Pa Pb Pc Pd Pela lei de DeMorgan x Px Pa Pb Pc Pd x Px Portanto x Px x Px Vejamos alguns exemplos 1º Exemplo Negar a sentença Alguns alunos são estudiosos Solução 3 alguns x alunos Px alunos são estudiosos Então Existem alunos estudiosos x Px E a negação dessa sentença equivale a x Px x Px ou seja Todos os alunos não são estudiosos 2º Exemplo Negar a sentença Todos os pescadores são mentirosos Solução x Px x Px Existe pescador que não é mentiroso 3º Exemplo Negar a sentença x x 1 5 Solução x x 1 5 x x 1 5 4º Exemplo Negar a sentença x x² 1 x 0 Solução x x² 1 x 0 x x² 1 x 0 x x² 1 x 0 x x² 1 x 0 Observação Neste exemplo usamos a equivalência notável p q p q 5º Exemplo Negar a sentença x sen² x cos² x 1 x 2x é ímpar Solução x sen² x cos² x 1 x 2x é ímpar x 2x é ímpar x sen² x cos² x 1 x 2x é ímpar x sen² x cos² x 1 x 2x é par 6º Exemplo Negar a sentença x y x y 11 Solução x y x y 11 x y x y 11 7º Exemplo Negar a sentença x y x 0 y 1 7 Solução x y x 0 y 1 7 x y x 0 y 1 7 x y x 1 y 1 7 x y x 1 y 1 7 EXERCÍCIOS 1 Determinar o conjuntoverdade das seguintes sentenças abertas a x 11 21 U N b 2x 5 13 U Z c x² 7x 12 0 U N d x³ 1 0 U N e x² 4x 3 0 U Z f 15x² 2x 8 0 U R g 5x² 19x 12 0 U R 2 Escrever simbolicamente as sentenças a 1 2 então existe x tal que x 2 b Todo triângulo é um polígono c Existe x tal que x é primo e x é par d Existe x e existe y tais que x² y e Para todo x se x N então x Z f Todo polígono regular convexo é inscritível 3 Dadas as sentenças abertas px 15x² 2x 8 0 e qx 5x² 19x 12 0 com U R determinar os valores lógicos de p q e p q 4 Determinar o valor lógico de cada uma das sentenças a x x x U R b x x 3 10 U 1 2 3 4 5 c x x² 3x 2 0 U R d x 4x 3 1 2x U R e x 2x² x 15 U 1 2 3 4 f x x² x 6 U 1 2 3 g x x² 3x 1 U 1 2 3 5 Negar as seguintes sentenças a Todos os homens são maus b Existe pescador que não é mentiroso c x R x² 5 2x d Existe y tal que para todo x x y 7 e Para todo x existe y tal que x y 3 a b a b a b a b a b a b Sa tomarmos o conjunto C3 de todas as proposições e se a b C3 então a b C3 e a b C3 isto é dadas as proposições a João estuda b João trabalha Temos as seguintes proposições compostas a b João estuda ou trabalha a b João estuda e trabalha Ou mediante as tabelasverdade a b a b a b 1 1 1 1 1 0 1 0 0 1 1 0 0 0 0 0 P2 O operador é comutativo se x y y x x y X 1º Exemplo Se a b C1 então a b b a e a b b a isto é 2º Exemplo Se a b C3 então a b b a e a b b a isto é 3º Exemplo Se a b C1 então a b c a b c e a b c a b c isto é Podemos verificar esta propriedade mediante as tabelasverdade a b a b b a a b b a 1 1 1 1 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 P3 Dizemos que o operador é associativo se x y z x y z x y z X 19 Exemplo Se a b c C1 então a b c a b c e a b c a b c 99 2º Exemplo Se a b c C2 então a b c a b c e a b c a b c isto é 3º Exemplo Se a b c C3 então a b c a b c e a b c a b c P4 Um operador é distributivo sobre se x y z x y x z x y z X 1º Exemplo Se a b c C1 então a b c a b a c e a b c a b a c 3º Exemplo Se a b c C3 então a b c a b c e a b c a b c 100 101 2º Exemplo Se a b c C1 então a b c a b a c e a b c a b a c isto é 3º Exemplo Se a b c C3 então a b c a b a c e a b c a b a c isto é construindose as tabelasverdade correspondentes a cada caso teremos portanto a b c a b a c pois suas tabelasverdade são iguais P5 Um elemento e é um elemento neutro para a operação se e somente se x e e x x x X 1º Exemplo Sej a C1 então a 0 0 a a e a 1 1 a a a C1 2º Exemplo Dado a C2 então a 0 0 a a e a 1 1 a a a C2 102 103 3º Exemplo Dado a C3 então a e e a a a C3 Para temos que a disjunção inclusiva ou soma lógica é falsa somente quando ambas as proposições consideradas forem falsas Então dada uma proposição a e Va 1 vem Para temos que a conjunção é verdadeira somente quando as proposições componentes forem verdadeiras logo dada uma proposição a e Va 1 vem EXERCÍCIOS 1 Seja o conjunto C T O Definamos dois operadores binários e pelas tabelas abaixo Para ler a primeira tabela por 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 símbolos Então O T e O 1 a O operador é comutativo é associativo b O operador é comutativo é associativo c Os operadores e são distributivos um em relação ao outro 2 Dados os operadores aritméticos e dizer quais dentre eles são operadores binários no conjunto Z de todos os inteiros 3 Considerando os operadores aritméticos e dizer quais dentre eles são operadores binários no conjunto N dos números naturais 4 Seja a b a² b² onde a b R O operador é fechado é comutativo é associativo é distributivo em relação a é distributivo em relação a admite elemento neutro 5 Dados os operadores e distributivos um sobre o outro reduzir ou desenvolver as expressões a seguir de modo a apresentálas sob forma diferente a a b c b b a b c a a b d a b c d e b a b b f a b a c 93 SISTEMAS ALGEBRICOS 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 ou A que são álgebras com um operador ou uma operação e A que é uma álgebra com dois operadores ou duas operações Uma álgebra pode satisfazer a alguma a todas ou a nenhuma das propriedades dos operadores assumindo nomes particulares para os diferentes casos como semigrupo monóide grupo anel corpo espaço vetorial conforme as propriedades satisfeitas pelo operador ou operadores definidos sobre um conjunto considerado Não trataremos destes casos em nosso curso para o qual têm especial interesse os sistemas algébricos chamados Algebras de Boole que definiremos a seguir Dizemos que o sistema algébrico B é uma Álgebra de Boole quando e somente quando x a b c B valem os axiomas A1 a b B A2 a b B A3 a b b a A4 a b b a A5 a b c a b a c 104 105 A6 a b c a b a c A7 0 B tal que para cada a B a 0 0 a a A8 1 B tal que para cada a B a 1 1 a a A9 Para cada a B a B tal que a a 1 e a a 0 No axioma 9 o elemento a chamase 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 degeneradas isto é Álgebras de Boole nas quais 0 1 Vejamos alguns exemplos 1º 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 do comutaçã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 de Boole não degenerada 2º Exemplo B4 0 a b 1 é uma Álgebra de Boole com quatro elementos descrita pelas tabelas Teorema 1 Princípio da Dualidade Todo resultado dedutível dos axiomas de uma Álgebra de Boole permanece válido se nele trocarmos por e 0 por 1 e viceversa 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 0 e 1 podem ser intercambiados conduzindo a outros resultados também verdadeiros cqd 1º Exemplo Dualizar a expressão x y x y z y z Solução Como a expressão não apresenta os valores 0 e 1 basta trocar os sinais por e por temos x y x y z y z que é o dual da expressão dada Obs 1 Não houve qualquer modificação nas letras complementadas ou seja onde aparecem x y z continuam sendo x y z 2 A dualidade tem grande semelhança com as leis de DeMorgan que veremos adiante diferenciando apenas pela observação 1 2º Exemplo Dar o dual da expressão x y 0 Solução Trocando na expressão dada por e 0 por 1 vem x y 1 que é o resultado procurado Teorema 2 a a a a a a a B Prova a a a a 1 a a a a a a a a 0 a a a a 107 Analogamente a a a a 0 a a a a a a a a 1 a a a a cqd Teorema 3 a 1 1 a 0 0 a B Prova a 1 a 1 1 a 1 a a a 1 a a a 1 a 1 1 Pelo Princípio da Dualidade temos a 0 0 cqd Teorema 4 Lei da Absorção a a b a a a b a Prova a a b a 1 a b a 1 b a b 1 a 1 a a a b a e pela dualidade temos a a b a cqd Teorema 5 a a b a b Prova a a b a a a b 1 a b a b a a b a b cqd Teorema 6 Os operadores e são associativos Prova a b c a b c a a a b c a a b c a a a b c a a b c a a b a a a b a a b c a 1 a b 1 a c a a b a c a b c a b c Pelo Princípio da Dualidade temos a b c a b c cqd Expressões como a b c e a b c podem ser escritas sem parênteses e expressões tais como a b c d e podem ser desenvolvidas como na Álgebra usual pode ser escrita ab e o operador tem precedência sobre de modo que a b c pode ser escrita a bc Teorema 7 O complemento de cada elemento de uma Álgebra de Boole é único Prova Suponhamos que a e x sejam complementos de a Então a x 1 a x 0 Logo x x a a ax ax 0 ax ax ax a a x a 1 a a cqd Conclusão Qualquer Álgebra de Boole não degenerada tem um número par de elementos 109 Teorema 8 a a Prova a é o complemento de a então a a 1 e a a 0 Mas estas equações apenas mostram que a é o complemento de a isto é a a Pelo teorema 7 existe um único complemento portanto a a cqd Teorema 9 ab ab a Prova ab ab ab b a 1 a ab ab a cqd Teorema 10 0 1 e 1 0 Prova 0 1 1 0 1 0 Logo 0 1 1 0 cqd Teorema 11 De Morgan a b a b e a b a b Prova a b a b a b a a b b 1 b 1 a 1 1 1 a b a b a a b b a b 0 Então a b é o complemento de a b isto é a b a b a b a b cqd Teorema 12 ab ac bc ab ac Prova ab ac bc ab ac bc a a ab ac abc abc ab 1 c ac 1 b ab ac ab ac bc ab ac cqd Teorema 13 a b a c b c ac ab Prova a b a c b c aa ac ab bc b c 0 abc abb bbc acc abc bcc abc ab bc ac bc ac 1 b ab 1 c bc ac ab bc ac ab a b a c b c ac ab cqd Teorema 14 a b a c ac ab Prova a b a c aa ac ab bc ac ab bc ac ab bc a a ac ab abc abc ab 1 c ac 1 b ab ac a b a c ac ab cqd Esses teoremas têm sua grande aplicação na simplificação de expressões booleanas e circuitos de interruptores conforme veremos nos exemplos a seguir 1º Exemplo Simplificar a b a b c 111 Solução a b a b ce aa ab ac ab bb bec a ab ac ab 0 bc a bc 2º Exemplo Simplificar o circuito Solução p qr pq r pqr pr pqr p pqr p qr e o circuito simplificado será 3º Exemplo Simplificar o circuito Solução pq pqr pr pq qr pr p q r pr pq pr pr pq p pr pq r pq r Desenhando o circuito da expressão simplificada vem 4P Exemplo Determinar o complemento de pq pq Solução pq pq pq pq p q p q p q p q pp pq pq qq pq pq Teorema 15 Se uma Álgebra de Boole contém pelo menos dois elementos distintos então 0 1 Prova Suponhamos que existe uma Álgebra de Boole com pelo menos dois elementos distintos para a qual 0 1 Seja a um elemento tal que a 0 Como por hipótese tal elemento existe então todos os outros elementos são iguais a 0 Logo a a 1 a 0 0 o que é uma contradição Portanto 0 1 cqd Sejam a e b elementos de uma Álgebra de Boole Dizemos que a é menor ou igual a b a b se e somente se a b b Teorema 16 é uma ordem parcial Prova Pelo teorema 2 a a a Logo a a Se a b então a b b se b a então a b b a a Portanto se a b e b a então a b Finalmente suponhamos que a b e b c Então a b b e b c c Logo a c a b c a b c b c c Portanto a c cqd Teorema 17 Sejam a b e c elementos de uma Álgebra de Boole Então a ordem parcial tem as seguintes propriedades 113 1 Se a b e b c então a c 2 Se a b então a b c c 3 Se a b então ac bc c 4 a b se e somente se b a Prova 1 a b b e a c c Logo a bc a b a c bc 2 Se a b b então a b c a b c b c 3 Peles leis da absorção ac ac a ou ac a O resultado se obtém pela transitividade 4 Suponhamos a b Então a b b e portanto b a b Logo b a a b a a ba a pelas leis da absorção A recíproca decorre do teorema 8 onde temos a a cqd EXERCÍCIOS 1 Simplificar as expressões a seguir justificando cada passagem a a b a b b p q p q r c b a c a b c d p p p q q r e x y z x y z 2 Simplificar a ab ac abc abc b f g h fgh c p q r p q s d x xy xyz xyz e a b b c c d d a f a b b c c a 3 Desenvolver as expressões a seguir tanto quanto possível a p qr b p qrs c pq rs d a bc d e 4 Provar que ab ab ac ac ab bc ca 5 Usando o teorema de De Morgan provar que a abc a b c b a b c a b c Verificar esses resultados com os círculos de Euler 6 Simplificar a a b b c b p q r q c a ab c d s t s u v 7 Determinar o complemento das expressões a ab c de f b a b cd e c ab cd ef d a b c d e f e abcb ac bc 8 Nos circuitos a seguir determinar a ligação simplificar e desenhar o circuito resultante 115 d a b c a b b c a b c a b c 9 Determinar o circuito complementar de a a b b c c a b x y z x y z x y z 10 Provar que para quaisquer elementos a e b de uma Álgebra de Boole a b se e somente se ab 0 11 Provar que para quaisquer elementos a e b de uma Álgebra de Boole a b se e somente se b a 1 12 Mostrar que nenhuma Álgebra de Boole tem três elementos 13 Mostrar que nenhuma Álgebra de Boole finita com mais de um elemento tem um número ímpar de elementos 116 10 Funções Booleanas Seja B uma Álgebra de Boole e sejam x1 xn variáveis tais que seus valores pertencem a B Chamase função booleana de n variáveis a uma aplicação f de Bn em B satisfazendo as seguintes regras 1 Se para quaisquer valores de x1 xn fx1 xn a a B então f é uma função booleana É a função constante 2 Se para quaisquer valores de x1 xn fx1 xn xi para algum i i 1 n então f é uma função booleana É a função projeção 3 Se f é uma função booleana então g definida por gx1 xn fx1 xn para todos x1 xn é uma função booleana 4 Se f e g são funções booleanas então h e k definidas por hx1 xn fx1 xn gx1 xn e kx1 xn fx1 xn gx1 xn para todos os x1 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 construída 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 identidade fx x Antes de nos adiantarmos neste assunto definamos o que se entende 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 símbolo que pode representar qualquer dos elementos de uma Álgebra de Boole B 117