Matemática Discreta e Suas Aplicações - Sexta Edição

Matemática Discreta e Suas Aplicações SEXTA EDIÇÃO Matemática Discreta e Suas Aplicações Sexta Edição Kenneth H Rosen ATT Laboratories Tradução Técnica Helena Castro Professora Doutora do Instituto de Matemática e Estatística da Universidade de São Paulo IMEUSP Professor João Guilherme Giudice Matemático pela Universidade Estadual de Campinas UNICAMP Doutorado em Filosofia na área de lógica matemática pela Universidade Estadual de Campinas UNICAMP Atua como professor em instituições particulares de ensino Matemática Discreta e Suas Aplicações Sexta edição ISBN 9788577260362 2009 McGrawHill Interamericana do Brasil Ltda Todos os direitos reservados São Paulo SP CEP 01426100 2009 McGrawHill Interamericana Editores SA de CV Mat Pesq da Reforma 1015 Torre A Piso 17 Ol Desenvolvimento Sede A Delegação Álvaro Obregón CP 01376 México DF Trado na edição em inglês de Discrete Mathematics and Its Applications Publicado pela McGrawHill na unidade de negócios da McGrawHill Companies Inc 1221 Avenue of the Americas New York NY 10020 ISBN em inglês 9780072880083 Coordenadora Editorial Gaucir Simonelli Editora de Desenvolvimento Mariliede Gomes Supervisora de Préimpressão Natália Toshiyuki Preparação de Texto Artisleta TravancaMariste Goulart Desenho de Capa Rabinas Design Associates Imagem da Capa Cover art Jasper Johns b 1930Autorizado por WGA New York NY Dancers on a Plane Diagramática Contect Ltda R813m Rosen Kenneth H Matemática discreta e suas aplicações recurso eletrônico Kenneth H Rosen tradução técnica Helena Castro João Guilherme Giudice 6 ed Dados eletrônicos Porto Alegre AMGH 2010 Editado também como livro impresso em 2009 ISBN 9788563308399 1 Matemática I Título CDU501 Sumário Sumário Sumário Kenneth H Rosen tem uma longa carreira como Membro Remoto do Equipe Técnica dos Laboratórios ATT em Monmouth County Nova Jersey Ele manteve também a posição de professor pesquisador convidado na Universidade de Monmouth onde trabalhou em aspectos de segurança e privacidade do Projeto de Resposta Rápida em Database e também lecionou um curso sobre aplicações criptográficas Prefácio A escrever este livro fui guiado pela minha longa experiência e pelo interesse em ensinar matemática discreta Para o estudante minha proposta foi oferecer um material que fosse preciso e de fácil leitura com conceitos e técnicas da matemática discreta claramente apresentadas e demonstradas Meu objetivo foi mostrar sua relevância e praticidade aos estudantes geralmente aos séculos Estruturas Discretas Um curso de matemática discreta deve ensinar os alunos a trabalhar com estruturas discretas que são estruturas matemáticas abstratas usadas para representar objetos discretos e as relações entre eles Essas estruturas discretas incluem conjuntos permutações relações grafos árvores e mecanismos de estado finito Lógica O conteúdo sobre lógica foi ampliado com as idéiaschave explicadas com grande profundidade e com maior cuidado Proposições condicionais e a lei de De Morgan tiveram seu conteúdo expandido A construção de tabelasverdade foi introduzida antes e mais detalhadamente Escritura e Entendimento de Demonstrações Métodos e estratégias de demonstração são tratados em seções separadas do Capítulo 1 Um apêndice foi adicionado com uma listagem dos ambiciosos para os números reais e para os números inteiros de como esses axiomas são usados para demonstrar novos resultados O uso desses axiomas é em resultados básicos que os acompanham utilizados em diversas demonstrações no livro O processo de criação de conjecturas que usa diferentes métodos e estratégias de demonstrar para desen Algoritmos Aplicações Uma maior abordagem foi reservada ao uso da indução completa a fim de demonstrar que algoritmos recursivos estão corretos Está presente nesta edição a descrição de como o Teorema de Bayes poderia ser usado para construir filtros de spam Teoria dos Números Análise Combinatória Teoria da Probabilidade O conteúdo sobre teoria dos números está agora mais flexível com quatro seções que abordam aspectos diferentes do assunto sendo o conteúdo das três últimas seções opcional A introdução das técnicas básicas de contagem permutações e combinações foram melhoradas Grafos e Teoria da Computação A introdução à teoria dos grafos foi melhorada e racionalizada Foi inserida uma rápida introdução à terminologia e às aplicações com ênfase na escolha das melhores opções ao construir um modelo com grafos em vez da terminologia O material sobre grafos bipartidos e suas aplicações foi ampliado Exercícios Exemplos Foram inseridos muitos exercícios de rotina novos e exemplos especialmente em lugares nos quais foram introduzidos conceitoschave Esforços extras foram feitos para assegurar que exercícios numéricos e os extras sejam providos de conceitos básicos e habilidades Biografias Adicionais Notas Históricas e Novas Descobertas Biografias de Arquimedes Hopper Stirling e Bayes foram inseridas Muitas biografias existentes na edição anterior foram melhoradas incluindo a biografia de Augusta Ada Melhor correspondência foi feita entre os exemplos que introduzem conceitoschave e os exercícios de rotina Muitos novos exercícios de design foram acrescentados Mais de 400 exercícios foram inseridos com mais conceitoschave assim como introduzidos novos tópicos APLICAÇÕES As aplicações apresentadas neste texto demonstram a utilidade da matemática discreta na solução de problemas reais Este texto inclui aplicações em muitas áreas como ciência da computação transmissão de dados psicologia química engenharia linguística biologia negócios e internet ALGORITMOS Os resultados em matemática discreta geralmente são expressos em termos de algoritmos consequentemente algoritmos importantes são introduzidos em cada capítulo do livro Esses algoritmos são expressos em palavras e em estruturas de pseudocódigo facilmente compreendidos outros estão descritos e especificados no Apêndice A3 A complexidade computacional dos algoritmos é analisada também em um nível elementar INFORMAÇÕES HISTÓRICAS O que está por trás de muitos tópicos é suficientemente descrito neste livro Foram incluídas pequenas biografias de mais de 65 matemáticos e cientistas da computação acompanhadas de fotos ou imagens Essas biografias incluem informações sobre as vidas as carreiras e as realizações desses importantes pensadores que contribuíram com a matemática discreta Além disso há várias notas históricas não da página que foram incluídas para atualizar por meio de reflexão sobre as descobertas recentes TERMOSCHAVE E RESULTADOS Uma lista de termoschave e resultados acompanha todos os capítulos Os termoschave incluem apenas aqueles mais importantes que devem ser entendidos e não todo tema definido no capítulo Este livro foi cuidadosamente escrito e elaborado a fim de auxiliar nos cursos de matemática discreta em diferentes níveis e com focos diferentes A tabela a seguir identifica seu conteúdo e as seções opcionais Um curso introdutório de um semestre em matemática discreta no nível de segundo ano pode se basear nas seções principais do livro com outros incluirás à priori interesse do docente Um curso introdutório de segundo semestre pode incluir todas as seções matemáticas opcionais além das principais Um curso com grande ênfase em ciência da computação pode ser ministrado a partir de algumas ou todas as seções opcionais de ciência da computação Os professores que forem usar este livro podem ajustálo conforme o nível de dificuldade de seu curso decidindo integrar ou omitir os exemplos mais desafiadores e não esta seção bem como os exercícios mais desafiadores A dependência dos capítulos é mostrada na figura abaixo Gostaria de agradecer aos muitos professores estudantes e escolas que têm utilizado este livro e têm me auxiliado com suas avaliações e sugestões Suas interferências fizeram deste um livro muito melhor do que eu esperava Gostaria de agradecer em especial a Jerrold Grossman John Michaels e George Bergman pela revisão técnica desta sexta edição e pelo seus olhos de água que ajudaram a assegurar a precisão deste livro Gostaria também de agradecer a todos aqueles que enviaram seus comentários pela internet Jonathan Knapppenberger LaSalle University Ed Korntved Northwest Nazarene University Przemо Kranz University of Mississippi Loredana Lanzanni University of Arkansas Yoonji Lee Smith College Miguel Lerma Northwestern University Jason Levy University of Hawaii Lauren Tilly Taylor College Ekaterina Loutiukova Saint Joseph College Vladimir Logvinenko De Anza College Joan Lukas University of Massachusetts Boston Lester McCann University of Arizona Jennifer McNulty University of Montana John G Michaels SUNY Brockport Michael Oppedisano Morrisville State College Michael OSullivan San Diego State University Charles Parry Virginia Polytechnic Institute Linda Powers Virginia Polytechnic Institute Dan Pritikin Miami University Anthony Quas University of Memphis Eric Rawdon Duquesne University Henry Ricardo Alfred State College Medgar Evers Oskars Riekstins Katsurow University Stefan Robila Montclair State University Chris Rodger Auburn University Robert Rodman North Carolina State University Shai Simonson Stonehill College Barbara Smith Cochise College Wasin So San Jose State University Diana Statas Dutchess Community College Lorna Stewart University of Alberta Bogdan Suscea California State University Fullerton Kathleen Sullivan Seattle University Laszlo Szekely University of South Carolina Daniel Tauritz University of Missouri Rolla Don VanderJagt Grand Valley State University Fran Vasko Katsurow University Susan Wallace University of North Florida Zhenyuan Wang University of Nebraska Omaha Tom Wineinger University of Wisconsin Eau Claire Charlotte Young South Plains College Eric Allender Rutgers University Stephen Andrilli La Salle University Kendall Atkinson University of Iowa Iowa City Zhaojun Bai University of California Davis Jack R Barrone Baruch College Klaus Bichler University of Texas Austin Ron Davis Millersville University Nachum Dershowitz University of Illinois UrbanaChampaign Thomas Dowling The Ohio State University Patrick C Fischer Vanderbilt University Jane Fritz University of New Brunswick Ladnor Geisinger University of North Carolina Jonathan Goldstine Pennsylvania State University Paul Gormley Villanova University Brian Gray Howard Community College Jonathan Gross Columbia University Laxmi N Gupta Rochester Institute of Technology Daniel Gusfield University of California Davis David F Hayes San Jose State University Xin He SUNY at Buffalo Donald Hutchison Clackamas Community College Kenneth Johnson North Dakota State University David Jonah Wayne State University Akihiro Kanamori Boston University W Thomas Kiley George Mason University Takashi Kimura Boston University Nancy Kinnersley University of Kansas Gary Klatt University of Wisconsin Nicholas Krier Colorado State University Lawrence S Kroll San Francisco State University Shui F Lam California State University Long Beach Robert Lavelle Iona College Hartlib Lamba George Mason University Sheau Dong Lang University of Central Florida Cary Lee Grossmont Community College YiHsin Liu University of Nebraska Omaha Stephen C Locke Florida Atlantic University George Lugger University of New Mexico David S McAllister North Carolina State University Robert McGuigan Westfield State College Michael Maller Queequeg College Ernie Manes University of Massachusetts Francis Massat Glassboro State College J M Metzger University of North Dakota Thomas D Morley Georgia Institute of Technology D R Morrison University of New Mexico Ho Kueg Nge San Jose State University Timothy S Norfolk Sr University of Akron Carl H Smith University of Maryland Hunter S Savelly University of Idaho Daniel Somerville University of Massachusetts Boston Patrick Tantal University of California Santa Cruz Bharti Temkin Texas Tech University Wallace Terwilliger Bowling Green State University Philip D Tiu Oglethorpe University Lisa TownsleyKulich Illinois Benedictine College George Trapp West Virginia University David S Tucker Midwestern State University Thomas Upson Rochester Institute of Technology Roman Voronka New Jersey Institute of Technology James Walker University of Wisconsin Anthony S Wojcik Michigan State University Gostaria de agradecer a equipe da McGrawHill pelo grande apoio a este projeto Em particular agradeço a Liz Haefele publicitária por seu auxílio Liz Covello editor chefe por sua dedicação e entusiasmo e Dan Supert editor de desenvolvimento por sua dedicação e atenção Gostaria também de agradecer ao primeiro editor Wayne Yahasu que com suas habilidades e visão ajudou no sucesso do livro assim como os editores anteriores deste livro Quanto à equipe envolvida na produção desta sexta edição ofereço meus agradecimentos a Peggy Selle gerente de projeto Michelle Whitacker designerchefe Jeff Huetteman produtor de mídia Sandy Schent gerente de projeto de mídia Melissa Kleck coordenadora dos questionários e Kelly Brown gerente de marketing executivo Sou também grato a Jerry Grosrman que revisou o manuscrito e Georgia Medeer que checou as respostas do Guia de Solução do Estudante e do Guia de Recursos para o Professor Kenneth H Rosen estão ligados diretamente ao conteúdo do texto assim como aos exemplos e aos exercícios Recursos adicionais são proporcionados para ajudar em seu uso e sua aplicação O que é matemática discreta Matemática discreta é a parte da matemática voltada para o estudo dos objetos discretos Aqui discreto significa elemento distinto ou desconhecido Os tipos de problemas resolvidos com a matemática discreta incluem Quantas formas existem para escolher uma senha válida em um sistema computacional Qual é a probabilidade de se ganhar na loteria Existe um elo entre dois computadores em uma rede de transmissão Como identificar emails com spam Como posso criptografar uma mensagem para que nenhum destinatário não incluído possa lêla Qual o menor caminho entre duas cidades usando o sistema de transporte Como se pode sortear uma lista de números inteiros na qual os números estão em ordem crescente Quantos passos são necessários para se fazer uma escolha Como é possível provar que um algoritmo solucionou corretamente determinado problema Como é determinado um circuito que soma dois inteiros Como obter endereços válidos na internet exitem Você vai aprender as estruturas e as técnicas necessárias para resolver problemas como esses Generalizando a matemática discreta é usada quando os objetos são contados quando são estudadas as relações entre os conjuntos finitos ou contáveis e quando são analisados os processos que envolvem um número finito de passos A principal razão para o crescimento do interesse na matemática discreta é que a informação é administrada e manipulada por computadores de uma maneira discreta porcentagem deles requer pensamento original Isso é intencional o conteúdo discutido no texto proporciona as ferramentas necessárias para a resolução desses exercícios nas quais você trabalhará aplicando com sucesso essas ferramentas com sua própria criatividade Um dos principais objetivos deste curso é aprender a lidar com problemas que podem ter diferentes soluções que você viu e resolve anteriormente Infelizmente esperamse que você desenvolva as habilidades necessárias para a resolução de problemas nos cursos subsequentes e no trabalho profissional Este texto é direcionado a muitos tópicos diferentes uma vez que a matemática discreta é uma área do conhecimento extremamente ampla e diversificada Um dos objetivos como autor é ajudarlo a desenvolver as habilidades necessárias para maximizar as informações adicionais que você necessitar em sua caminhada futura OS EXERCÍCIOS Gostaria de dar alguns conselhos sobre como você pode aprender melhor a matemática discreta e outros assuntos nas ciências matemáticas e computacionais Minha experiência é dar o máximo a partir da resolução dos exercícios Sugiro que você resolva o máximo de exercícios positivos Depois de trabalhar os exercícios dados por seu professor eu encorajo a resolver os exercícios adicionais assim como aqueles que acompanham cada seção do texto e os exercícios complementares no final de cada capítulo veja a nota que explica as marcações que acompanham os exercícios Nota aos Exercícios Não marcados Um exercício de rotina Um exercício difícil Um exercício extremamente desafiador Um exercício que contém um resultado utilizado no livro A Tabela abaixo mostra onde cada um desses exercícios é usado Requer cálculo Um exercício que em sua solução exige o uso de limites ou conceitos de cálculos diferenciais ou integral Exercícios com o ícone mão e onde eles são usados Seção Exercício Seção onde são usados Páginas onde são usados 12 42 112 758 16 16 16 81 23 75a 24 31 43 31 472 31 43 31 174 37 30 106 700 41 79 41 700 42 28 42 287 43 57 43 237 54 17 54 411 57 6 57 247 62 15 62 414 81 24 81 545 94 49 101 685 101 101 693 101 48 102 700 101 113 763 A2 4 73 477 A melhor forma de estudo é tentar resolver os exercícios sozinho antes de consultar as respostas no final do livro Note que os exercícios ímpares possuem apenas as respostas e não as soluções completas normalmente a argumentação necessária para obter as respostas é conteúdo do Guia de Solução do Estudante Students Solutions Guide proporciona as soluções completas para todos os exercícios ímpares O Students Solutions Guide está disponível em inglês consulte o seguinte Material Adicional de Apoio Preço para obter mais informações Ao se deparar com um impasse para resolver um problema é recomendável a consulta ao seu material ou a busca de ajuda para resolver a questão Quão mais exercícios você resolver sozinho sem a cópia precisa das respostas mais você aprenderá As respostas às soluções dos exercícios ímpares foram omitidas intencionalmente na publicação aproveite e se profissionalize em si mesmo resolver problemas com elas CAPÍTULO 1 Os Fundamentos Lógica e Demonstrações A as regras da lógica especificam o significado de sentenças matemáticas Proposição essas regras nos ajudam a entender propostas tais como Existe um inteiro que não é a soma de dois quadrados e Para cada inteiro positivo n a soma dos inteiros positivos menores que o igual a n é nn 12 bem como raciocinar sobre elas Lógica é a base de todo raciocínio matemático e de todo raciocínio automatizado Ela tem aplicações práticas no desenvolvimento de máquinas de computação em especificação de sistemas em inteligência artificial em programação de computadores em linguagens de programação e em outras áreas da ciência da computação bem como em outros campos de estudo EXEMPLO 1 Todas as seguintes sentenças declarativas são propostas 1 Brasília é a capital do Brasil 2 Toronto é a capital do Canadá 3 1 1 2 4 2 2 3 As propostas 1 e 3 são verdadeiras assim como 2 e 4 são falsas Algumas sentenças que não são propostas são dadas no Exemplo 2 EXEMPLO 2 Considere as seguintes sentenças 1 Que horas são 2 Leia isto cuidadosamente 3 x 1 2 4 x y z Agora voltaremos nossas atenção para métodos de produção de novas proposições a partir daquelas que já temos Esses métodos foram discutidos pelo matemático inglês George Boole em 1854 em seu livro The Laws of Thought Muitas sentenças matemáticas são construídas combinandose uma ou mais proposições Novas proposições chamadas de proposições compostas são criadas a partir de proposições existentes usandose operadores lógicos A negação de uma proposição pode também ser considerada o resultado da operação do operador de negação em uma proposição O operador de negação constrói novas proposições a partir de proposições presentes Agora introduziremos os operadores lógicos que são usados para criar novas proposições e para outras duas ou mais já existentes Os operadores lógicos são também chamados de conectivos Aqui queremos dizer que estudantes que têm aulas de cálculo e ciência da computação podem assistir a estas aulas bem como estudantes que têm aulas em apenas um dos cursos Por outro lado se queremos usar o ou exclusivo dizemos Estudantes que têm aulas de cálculo e ciência da computação mas não ambas podem assistir a estas aulas TABELA 4 A TabelaVerdade para o Ou Exclusivo de Duas Proposições Se tirar nota 10 no exame final então você espera receber o conceito A Se não tirar 10 você pode ou não receber o conceito A dependendo de outros fatores QUAL é a contrapositiva a oposta e a inversa da proposição condicional O time das casa ganha sempre que está chovendo A oposta é Se o time da casa ganha então está chovendo USO IMPLÍCITO DE BICONDICIONAIS Devemos estar cientes de que nem sempre bicondicionais estão explícitas em nossa linguagem natural TABELA 8 Prioridade do Operador Lógico Solução Sejam q r e s as representações de Você pode pular de paraquedas Você tem autorização de seus pais e Você tem mais de 18 anos respectivamente Então a sentença pode ser traduzida por r s q É claro que existem muitas outras maneiras de traduzir a sentença mas essa já é suficiente Conectivos lógicos são largamente usados em buscadores de grandes conjuntos de informações tais como índices de páginas da Internet Com esses buscadores utilizam técnicas de lógica proposicional eles são chamados de buscadores booleanos Em buscadores booleanos o conectivo E AND é usado para encontrar informações que contenham ambos os termos procurados o conectivo OU OR é usado para encontrar informações que contenham um ou ambos os termos procurados e o conectivo NÃO NOT é usado para excluir alguma informação que contenha este termo na procura Solução Sejam p e q as proposições A é um cavaleiro e B é um cavaleiro respectivamente então p q e q são as afirmações que dizem ser A e B bandidos respectivamente Primeiro vamos considerar a possibilidade de A ser cavaleiro ou seja a proposição p é verdadeira Se isso ocorrer então q está falhando a verdade o que implica que B é um cavaleiro Sendo assim o que fala é verdade também no entanto ele diz que os dois são tipos diferentes e estamos concluindo que ambos são cavaleiros o que é absurdo Então devemos pensar que A é um bandido logo está falando mentira e portanto B também é bandido TABELA 9 Tabela para os Operadores Binários OR AND e XOR x y x y x y x y 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 0 Solução As sequências são 01 0011 0110 11 0001 1101 11 1011 1111 OU 01 0001 0100 E OUexclusivo Considere que p e q são proposições a Você tira um A nesta matéria mas não faz todos os exercícios deste livro b Você tira um A no exame final faz todos os exercícios deste livro e tira um A nesta matéria Para cada uma destas sentenças determine se o ou inclu sivo ou exclusivo Explique sua resposta Escreva cada uma destas proposições na forma se p então q em português Para cada sentença identifique o que significa a sentença se o ou inclusivo ou seja uma disjunção ou exclusivo Quais dois significados você pensa ser intencional Steve quer determinar os salários relativos de três colagas de trabalho usando dois fatores Primeiro ele sabe que se Fred não foi maior salário dos três então Janice tem Segundo ele sabe que Janice não tem o salário mais baixo então Maggie é a mais bem paga É possível determinar os salários relativos de Fred Maggie e Janice a partir do que Steve sabe Se sim quem tem o salário maior e quem tem o menor Explica seus argumentos Podemos construir exemplos de tautologias e contradições usando apenas uma variável proposicional Considere a tabelaverdade de p p e p p mostrada na Tabela 1 Como p p é sempre verdadeira é uma tautologia Como p p é sempre falsa é uma contradição Mostre que p q e p q são logicamente equivalentes Solução Construímos a tabelaverdade dessas proposições compostas na Tabela 4 Como os valoresverdade de p q e p q são idênticos elas são logicamente equivalentes TABELA 6 Equivalências Lógicas TABELA 7 Equivalências Lógicas que Envolvem Sentenças Condicionais TABELA 8 Equivalências Lógicas que Envolvem Bicondicionais EXEMPLO 8 Mostre que p q p q é uma tautologia Solução Para mostrar que essa proposição é uma tautologia vamos usar equivalências para demonstrar que é logicamente equivalente a V Nota Isso poderia ser feito usando tabelasverdade p q p q p q p q pelo Exemplo 3 p q p q pela primeira lei de De Morgan p p q q pelas propriedades associativas e comutativas para a disjunção p p q pelo Exemplo 1 e pela propriedade comutativa para a disjunção V q pela propriedade de dominação V Uma tabelaverdade pode ser usada para determinar se uma proposição composta é uma tautologia Isso pode ser feito rapidamente se for uma proposição composta com poucas variáveis mas quando o número de variáveis cresce isso pode ficar impraticável Por exemplo existe uma tabelaverdade para 20 variáveis proposicionais Claramente você precisaria de um computador para ajudar a determinar quando uma proposição composta é uma tautologia Quando no entanto existe um número variávels proposicionais um computador pode determinar em um tempo razoável se uma proposição é uma tautologia Testando todas as 21000 um número com mais de 300 arredondamentos decimais possíveis combinações de valoresverdade um computador não consegue terminar em menos de alguns trilhões de anos Além disso não existe um outro método conhecido que um computador possa seguir para determinar em um tempo razoável quando uma proposição com muitas variáveis proposicionais é uma tautologia Vamos estudar questões como essas no Capítulo 3 quando estudarmos a complexidade de algoritmos Exercícios 1 Use a tabelaverdade para verificar estas equivalências a p V p b p F p c p F F d p p p 2 Mostre que p e p são logicamente equivalentes 3 Use a tabelaverdade para verificar as propriedades comutativas a p q q p b p q q p 4 Use a tabelaverdade para verificar as propriedades associativas a p q r p q r b p q r p q r 5 Use a tabelaverdade para verificar a propriedade distributiva p q r p q p r 6 Use a tabelaverdade para verificar a primeira lei de De Morgan p q p q 7 Use as leis de De Morgan para encontrar a negação de cada uma das proposições abaixo a Jan é rico e feliz b Carlos andará de bicicleta ou correrá amanhã c Mel amiga ou pega o ônibus para ir à escola d Ibraim é esperto e trabalha muito 8 Use as leis de De Morgan para encontrar a negação de cada uma das proposições abaixo a Kwam trabalhou na indústria ou iria para a faculdade b Yoshiho conhece Java e cálculo c James é jovem e forte d Rita mudará para Oregon ou Washington 41 Encontre uma proposição composta que envolva as variáveis proposicionais p q e r que é verdadeira quando as duas condicionais p q e q r forem verdadeiras mas no contrário é falso Dica Forme uma disjunção das variáveis suas negações com uma conjunção formada por cada combinação de valores para os quais a proposição composta é verdadeira A proposição composta resultante é chamada de forma normal disjuntiva 42 Suponha que a tabelaverdade em variáveis proposicionais é dada Mostre que pode ser formada uma proposição composta com essa tabelaverdade a partir de uma disjunção das condições dadas às variáveis suas negações com uma conjunção formada por cada combinação de valores para as quais a proposição composta é verdadeira A proposição composta resultante é chamada de forma normal disjuntiva Um conjunto de operadores lógicos é chamado de funcionalmente completo quando todos os operadores lógicos são logicamente equivalentes entre si Mostre que e formam um grupo de operadores lógicos funcionalmente completo Mostre que e formam um grupo de operadores lógicos funcionalmente completo 45 Mostre que p e p p é um conjunto de operadores lógicos funcionalmente completo Os exercícios subsequentes envolvem os operadores lógicos NAND e NOR A proposição p NAND q é verdadeira quando ou p ou q ambos fazem verdadeiros e é falsa quando p e q ambos forem verdadeiros é falsa e é falsa em qualquer outro caso p q respectivamente Os operadores lógicos são chamados de operadores lógicos 55 Quantas formas diferentes de tabelasverdade de proposições compostas existem que envolvam as variantes proposicionais p e q Predicados EXEMPLO 1 Seja Px a declaração x 3 Qual o valorverdade de P4 e P2 EXEMPLO 6 Considere a afirmação if x 0 then x x 1 Quando essa declaração é encontrada em um programa o valor da variável x naquele ponto de execução é inserido em Px que x 0 Se Px é verdadeira para esse valor de x o comando x x 1 é executado logo o valor de x é incrementado em uma unidade Se Px é falsa para esse valor de x o comando não é executado e portanto o valor de x não é alterado Predicados são também usados em programas de computador para verificar se eles sempre produzem uma saída desejada quando é dada uma entrada válida As declarações que descrevem entradas válidas são conhecidas por condições iniciais ou précondições e as que verificam se as saídas são satisfatórias quando o programa roda são chamadas de condições finais ou póscondições Como ilustra o Exemplo 7 usamos predicados para descrever ambas as condições précondições e póscondições Vamos estudar esse processo com mais detalhes na Seção 44 EXEMPLO 7 Considere o seguinte programa feito para trocar os valores das variáveis x e y temp x x y y temp Encontre predicados que podem ser usados como précondições e póscondições para verificar se esse programa é correto Explique como podemos usálos para verificar se para toda entrada válida o programa faz o que se pretende Solução Como precondição precisamos saber se x e y têm certos valores antes de rodar o programa Então para essa precondição podemos usar o predicado Px y no qual Px y é a afirmação x a e y b em que a e b são os valores de x e y antes do programa Como queremos verificar se o programa está trocando os valores das variáveis como póscondição podemos usar Px y em que Px y x b e y a é verdadeira Quantificadores Quando impomos às variáveis de uma função proposicional algum valor a declaração resultante tornase um verdadeiro ou falso O QUANTIFICADOR UNIVERSAL Muitas afirmações matemáticas referemse a alguma propriedade que é verdadeira para todos os valores de uma variável em determinado domínio chamado de domínio de discurso ou universo de discurso frequentemente apenas chamado de domínio Essas afirmações são expressas usando quantificação universal A quantificação universal de Px para determinado domínio é a proposição que afirma que Px é verdadeira para todos os valores de x pertencentes a esse domínio Note que o domínio especifica os possíveis valores da variável x O significado da quantificação universal de Px muda quando mudamos o domínio O domínio deve ser sempre especificado quando usamos um quantificador universal sem ele a quantificação universal não está definida DEFINIÇÃO 1 A quantificação universal de Px é a afirmação Px é válida para todos os valores x do domínio A notação x Px indica a quantificação universal de Px Aqui é chamado de quantificador universal Lemos x Px como para todo x Px Um elemento para o qual Px é falsa é chamado de contraexemplo para x Px O significado do quantificador universal é resumido na primeira linha da Tabela 1 Vamos ilustrar o uso do quantificador universal nos exemplos 813 EXEMPLO 8 Seja Px a declaração x 1 x Qual é o valorverdade da quantificação x Px no domínio de todos os números reais Solução Como Px é verdadeira para todo número real x a quantificação x Px é verdadeira Lembrese Em geral é assumido implicitamente que todos os domínios dos quantificadores são não vazios Note que se o domínio é vazio então x Px é verdadeira para toda proposição Px uma vez que não há elemento no domínio para o qual Px é falsa Uma declaração x Px é falsa em que Px é uma função proposicional se e somente se Px não é sempre verdadeira para os valores de x no domínio Uma maneira de mostrar que Px não é sempre verdadeira no domínio é achar um contraexemplo para a declaração x Px Note que um único contraexemplo é tudo que precisamos para estabelecer que x Px é falsa O Exemplo 9 ilustra como contraexemplos são usados EXEMPLO 9 Seja Qx a declaração x 2 Qual o valorverdade da quantificação x Qx em que o domínio consiste em todos os números reais Solução Qx não é verdadeira para todo número real x porque por exemplo Q3 é falsa Isto é x 3 é um contraexemplo para a declaração x Qx Logo x Qx é falsa EXEMPLO 10 Suponha que Px seja x 2 0 Para mostrar que x Px é falsa onde o universo do discurso consiste em todos os números inteiros damos um contraexemplo Vemos que x 0 é um contraexemplo pois x² 0 quando x 0 então x² não é maior que 0 Procurar por contraexemplos em proposições universalmente quantificadas é uma importante atividade no estudo da matemática como veremos nas seções seguintes deste livro Quando todos os elementos do domínio podem ser listados seja x₁ x₂ xₙ seguese que a quantificação universal x Px é o mesmo que a conjunção Px₁ Px₂ Pxₙ pois esta conjunção é verdadeira se e somente se Px₁ Px₂ Pxₙ forem todas verdadeiras EXEMPLO 11 Qual o valorverdade de x Px em que Px é a proposição x 10 e o domínio é o conjunto dos inteiros positivos que não excedem 4 Solução A declaração x Px é o mesmo que a conjunção P1 P2 P3 P4 pois o domínio é formado por esses quatro elementos Como P4 que é a expressão 4 10 é falsa seguese que x Px é falsa EXEMPLO 12 O que significa dizer x Nx se Nx é O computador x está conectado à rede e o domínio são todos os computadores do campus Solução A declaração x Nx significa que para todo computador x no campus x está conectado à rede Em português a declaração pode ser expressa por Todo computador do campus está conectado à rede Apontamos anteriormente o fato de que a especificação do domínio é primordial e obrigatória quando quantificadores são usados O valorverdade da proposição quantificada frequentemente depende do domínio como mostra o Exemplo 13 EXEMPLO 13 Qual o valorverde de xx² x se o domínio consiste em todos os números reais E qual o valorverde dessa proposição se o domínio são todos os números inteiros EXEMPLO 16 Qual o valorverde de x Px em que Px é a proposição x 10 e o domínio é o conjunto dos inteiros positivos que não excedem 4 EXEMPLO 18 Na afirmação x x y 1 a variável x é ligada pelo quantificador existencial mas a variável y é livre pois não é ligada a nenhum quantificador nem assume nenhum valor específico e como xPx Qx yRy pois o escopo dos dois quantificadores não se sobrepõe O leitor deve estar ciente de que no uso comum a mesma letra é frequentemente usada para representar variáveis ligadas por diferentes quantificadores com escopo que não se sobrepõe Essa expressão é uma quantificação universal nominalmente xPx em que Px é a declaração x teve aulas de cálculo e o domínio consiste em todos os estudantes da sua classe A negação dessa proposição é Não é o caso de todos os alunos de sua classe terem feito aulas de cálculo Isso é equivalente a Existe um estudante em sua classe que não teve aula de cálculo E isso é simplesmente a quantificação existencial da negação da função proposicional original nominalmente xPx Negação Sentença Equivalente Quando a Negação é Verdadeira Quando é Falsa xPx xPx Para todo x Px é falsa Existe um x para o qual Px é verdadeira xPx xPx Existe um x para o qual Px é falsa Para todo x Px é verdadeira Traduzindo do Português para Expressões Lógicas Solução A sentença Algum estudante da classe visitou o México significa que Considera estas sentenças As duas primeiras são chamadas de premissas e a terceira é chamada de conclusão O conjunto inteiro é chamado de argumento EXEMPLO 27 Considere estas sentenças das quais as três primeiras são premissas e a quarta é uma conclusão válida Todos os beijaflores são ricamente coloridos Nenhum pássaro grande vive de néctar Pássaros que não vivem de néctar são montonhos nas cores Beijaflores são pequenos Sejam Px Qx e Rx as sentenças x é um beijaflor x é grande x vive de néctar e x é ricamente colorido respectivamente Assumindo que o domínio consiste em todos os pássaros expresse as sentenças do argumento usando quantificadores e Px Qx e Sx Solução Podemos expressar as sentenças do argumento por xPx Sx xQx Rx xRx Sx xPx Qx Note que assumimos que pequenos é o mesmo que não grandes e que montonhos nas cores é o mesmo que não ricamente colorido Para mostrar que a quarta sentença é uma conclusão válida a partir das três primeiras precisamos do uso de regras de inferência que serão discutidas na Seção 15 Programação Lógica Um importante tipo de linguagem de programação é designado a raciocinar usando regras de predicados lógicos Prolog de Programming in Logic desenvolvido na década de 1970 por cientistas computacionais que trabalhavam na área de inteligência artificial é um exemplo dessas linguagens Programas em Prolog incluem um conjunto de declarações que consistem em dois tipos de sentenças Prolog facts e Prolog rules fatos Prolog e regras Prolog definidos como predicados que especificam os elementos que satisfazem esses predicados Prolog rules são usados para definir novos predicados que usam aqueles que já estão definidos em Prolog facts O Exemplo 28 ilustra essas noções EXEMPLO 28 Considere um programa Prolog que oferece como fatos facts os instructores de cada classe instructor e em qual classe cada aluno está matriculado enrolled O programa usa fatos para responder quem é o instructor de um estudante em particular Esse programa deve usar os predicados instructorp c e enrolleds c para representar que o professor p é o instrutor da classe c e o estudante s está matriculado no curso c respectivamente Por exemplo os Prolog facts nesse programa podem incluir instructorchanmath273 instructorpatelee222 instructorgrossmancs301 enrolledkevinmath273 enrolledjuanaee222 enrolledjuanacs301 enrolledkikomath273 enrolledkikocs301 As letras minúsculas são usadas para as entradas pois o Prolog considera nomes que começam por letras maiúsculas como variáveis Um novo predicado teachesps que representa que o professor p ensina o estudante s pode ser definido usando uma Prolog rule teachesPS instructorPC enrolledSC o que significa que teachesps é verdadeiro existir uma classe c tal que o professor p é instrutor dessa classe e o estudante s está matriculado na classe c Note que uma vírgula é usada para representar uma conjunção de predicados em Prolog Similarmente um pontoevírgula é usado para representar uma disjunção de predicados Prolog responde às perguntas usando os fatos e as regras dadas Por exemplo usando os fatos enrolledkevinmath273 produz a resposta yes porque o fato enrolledkevinmath273 foi dado como entrada A pergunta enrolledXmath273 produz a resposta kevin kiko Para produzir essa resposta Prolog determina todos os valores possíveis da variável X para os quais enrolledXmath273 foi dado como Prolog fact Similarmente para encontrar os professores que são instrutores das classes de Juana usamos a pergunta teachesXjuana Essa pergunta retorna patel grossman Cada duas pessoas têm o mesmo nome