MatemáticaDiscreta UmaIntrodução 2aEd EdwardRScheinerman

MatemáticaDiscreta UmaIntrodução 2aEd EdwardRScheinerman


DisciplinaMatemática Discreta4.132 materiais80.201 seguidores
Pré-visualização50 páginas
M ATEM ÁTICA
DISCRETA
Uma introdução
T R A D U Ç Ã O D A 2 a E D I Ç Ã O 
N O R T E - A M E R I C A N A
CENGAGE
Learning*
Edward R. Scheinerman
MATEMÁTICA DISCRETA
Uma introdução
TRADUÇÃO DA 2« ED IÇÃO NORTE-AMER I CANA
Esta nova edição do Matemática discreta traz uma ampla abordagem da 
matemática discreta com o bônus da renovação de seu conteúdo, elaborada 
pelo autor em colaboração com diversos alunos e leitores.
O material é diretamente aplicável à Ciência da Computação e à Engenharia, 
mas apresentado a partir de uma perspectiva matemática. Não se pressupõe, 
no entanto, o cálculo em qualquer nível - e nem é necessário.
Os cursos de matemática discreta são feitos pela maioria dos estudantes 
de Ciência e Engenharia da Computação. Consequentemente, alguns cursos de 
matemática discreta enfocam tópicos como circuitos lógicos, autômatos 
de estado finito, máquinas de Turing, algoritmos etc. Embora sejam tópicos 
interessantes e importantes, um cientista da computação ou um engenheiro 
precisa saber mais.
Aplicações
Livro-texto para a disciplina matemática discreta nos cursos de graduação 
em Matemática e Ciência da Computação.
\u2022 V C E N G A G E 
* % Learning\u2019
Para suas soluções de curso e aprendizado, 
visite www.cengage.com.br
ISBN 13 978-85*221-0796-4 
ISBN 10 85-221-0796-3
9 7148522 ! 107964
Matemática discreta
Matemática discreta
Uma introdução
Tradução da 22 edição norte-americana
Edward R. Scheinerman
Departamento de Matemática Aplicada e Estatística 
The Johns Hopkins University
Revisão técnica
Flávio Soares Corrêa da Silva
PH.D. em Inteligência Artificial pela Edinburgh University, 
livre-docente e professor associado do Departamento de 
Ciência da Computação no Instituto de Matemática e 
Estatística da Universidade de São Paulo (IME - USP)
- C E N G A G E 
** Learning\u2019
Austrália \u2022 Brasil \u2022 Ja pão » Coreia * México \u2022 Cingapura \u2022 Espanha \u2022 Reino Unido \u2022 Estados Unidos
C E N G A G E
Learning\u2019« *
Matemática Discreta: uma introdução - tradução 
da 2a edição norte-americana
© 2006 Brooks/Cole, parte da Cengage Learning Edições Ltda. 
© 2011 Cengage Learning Edições Ltda.
Edward Scheinerman
Gerente Editorial: Patricia La Rosa
Editora de Desenvolvimento e Produção Editorial: 
Gisele Gonçalves Bueno Qulrino de Souza
Supervisora de Produção Gráfica e Editorial: 
Fabiana Alencar Albuquerque
Título original: Mathematics: a Discrete Introduction
ISBN original: 0-495-01866-X
Tradução: All Tasks
Todos os direitos reservados. Nenhuma parte deste livro poderá 
ser reproduzida, sejam quais forem os meios empregados, sem a 
permissão, por escrito, da Editora.
Aos infratores aplicam-se as sanções previstas nos artigos 102, 
104,106 e 107 da Lei n5 9.610, de 19 de fevereiro de 1998.
Para informações sobre nossos produtos, entre em 
contato pelo telefone 08001119 39
Para permissão de uso de material desta obra, envie 
seu pedido para direitosautorais@cengage.com
Revisor técnico: Flávio Soares Corrêa da Silva © 2011 Cengage Learning. Todos os direitos reservados.
Copidesque: Maria Alice da Costa
Revisão: Luicy Caetano de Oliveira, Cristiane 
Mayumi Morinaga
Capa: Marcela Perroni (Ventura Design) 
Diagramação: SGuerra Design
ISBN-10:85-221-0796-3 
ISBN-13:978-85-221-0796-4
Cengage Learning
Condomínio E-Business Park
Rua Werner Siemens, 111 - Prédio 20 - Espaço 04
Lapa de Baixo - CEP 05069-900 - São Paulo - SP
Tel.: (11) 3665-9900 - Fax: (11) 3665-9901
SAC: 08001119 39
Para suas soluções de curso e aprendizado, visite 
www.cengage.com.br
Impresso no Brasil. 
Printed in Brazil.
S um ário
A o Estudante xi
Exercícios
A o professor xv
0 que há de novo nesta segunda edição xix
Agradecim entos xxi
1 Fundamentos 1
1 Alegria 1
2 Definição 2
3 Teorema 8
4 Prova 17
5 Contraexemplo 28
6 Á lgebra de Boole 31
Autoteste 38
2 Coleções 41
7 Listas 41
8 Fatorial 50
9 Conjuntos I: introdução, subconjuntos 55
10 Quantificadores 64
11 Conjuntos II: operações 71
12 Prova combinatória: dois exem plos 85
Autoteste 90
3 Contagem e Relação 93
13 Relações 93
14 Relações de equivalência 100
15 Partições 109
16 Coeficientes binomiais 116
17 Contagem de multiconjuntos 132
18 Inclusão-exclusão 140
Autoteste 151
viii Matemática Discreta
4 M a is Provas
19 Contradição
20 Contraexem plo m ín im o
21 Indução
22 Relações de recorrência 
Autoteste
155
155
163
177
196
217
5 Funções 221
23 Funções 221
24 0 Princípio da Casa do Pom bo 236
25 C om posição 243
26 Perm utações 250
27 Simetria 267
28 T ipos de notação 274
Autoteste 280
6 Probabilidade 285
29 Espaço amostrai 286
30 Eventos 291
31 Probabilidade condicional e independência 299
32 Variáveis aleatórias 310
33 Valor esperado 316
Autoteste 335
7 Teoria dos Núm eros 339
34 D ivisão 339
35 M áx im o d iv iso r com um 345
36 Aritmética m odular 357
37 0 teorema do resto ch inês 369
38 Fato ração 375
Autoteste 386
8 Álgebra 387
39 G rupos 387
40 Isom orfism o de g rupo s 398
41 Su b grup o s 405
42 O pequeno teorema de Fermat 415
43 Criptografia de chave pública I: introdução 424
44 Criptografia de chave pública II: o método de Rabin 428
45 Criptografia de chave pública III: R S A 435
Autoteste 441
Sumário ix
9 Grafos 443
46 Fundamentos da teoria dos grafos 443
47 Subgrafos 455
48 Conexão 464
49 Á rvores 473
50 Grafos eulerianos 484
51 Coloração 490
52 Grafos planares 500
Autoteste 513
10 Conjuntos Parcialmente Ordenados 517
53 Fundamentos dos conjuntos parcialmente ordenados 517
54 M ax e min 524
55 Ordens lineares 528
56 Extensões lineares 532
57 D im ensão 541
58 Reticulados 550
Autoteste 557
Glossário
Fundamentos
561
571
Ao estudante
Bem-vindo!
Este livro constitui uma introdução à matemática. Em particular, é uma introdução à mate­
mática discreta. Que significam esses termos - discreta e matemática?
Matemática contínua versus matemática discreta
O mundo da matemática pode ser aproximadamente dividido em dois domínios: o contínuo 
e o discreto. A diferença é ilustrada pelos relógios de pulso. A matemática contínua corres­
ponde aos relógios analógicos - o tipo que separa os ponteiros das horas, minutos e segundos. 
Os ponteiros se movem suavemente ao longo do tempo. Do ponto de vista de um relógio ana­
lógico, entre 12h02min e 12h03min há um número infinito de tempos diferentes possíveis, na 
medida em que o ponteiro dos segundos percorre o mostrador. A matemática contínua estuda 
conceitos infinitos em seu objetivo, em que um objeto pode combinar-se suavemente com o 
próximo. O sistema dos números reais está no cerne da matemática contínua e - da mesma for­
ma que no relógio - entre dois números reais quaisquer, há uma infinidade de números reais. 
A matemática contínua oferece excelentes modelos e instrumentos para analisar fenômenos 
do mundo real que se modificam suavemente ao longo do tempo, inclusive o movimento dos 
planetas ao redor do Sol e o fluxo do sangue através do corpo.
Por outro lado, a matemática discreta é comparável a um relógio digital, em que há ape­
nas um número fin ito possível de tempos diferentes entre 12h02min pela manhã e 12h03min 
à tarde. Um relógio digital não reconhece frações de segundos! Não há tempo algum entre 
12h02min03 pela manhã e 12h02min04 à tarde. O relógio salta de um instante para o próximo. 
Um relógio digital só pode mostrar um número finito de tempos diferentes, e a transição de um 
tempo para o próximo é bem definida e sem ambiguidade. Assim como o sistema de números 
reais representa um papel central na matemática contínua, os inteiros são o instrumento prin­
cipal