MatemáticaDiscreta UmaIntrodução 2aEd EdwardRScheinerman

MatemáticaDiscreta UmaIntrodução 2aEd EdwardRScheinerman

Disciplina:Matemática Discreta3.230 materiais69.269 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.

• V C E N G A G E
* % Learning’

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’

Austrália • Brasil • Ja pão » Coreia * México • Cingapura • Espanha • Reino Unido • Estados Unidos

C E N G A G E
Learning’« *

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