Document Text Contents
Page 1
F U N D A M E N T O S
da
M A T E M Á T I C A
D I S C R E T A
J . H U N T E R
GEN I Informação Online
Page 2
Diferenciando-se dos livros-texto
tradicionais, Fundamentos da
Matemática Discreta foi concebido para
abordar o tema em amplitude, mantendo
o encadeamento e a uniformidade
das ideias.
O autor apresenta cinco tipos de
pensamento matemático ao longo da
obra: lógico, relacional, recursivo,
quantitativo e analítico. Ordenados
sequencialmente, cada capítulo trata
de um dos tópicos mencionados, o
que possibilita a compreensão efetiva
do texto.
O Capítulo 5, sobre o pensamento
analítico, aplica o conteúdo abordado
nos quatro capítulos anteriores aos
estudos da complexidade algorítmica e
da precisão de programas. Dessa forma,
a leitura proporciona a compreensão
da ocorrência e da eficiência dos
algoritmos. Além disso, a obra permite
que os estudantes desenvolvam o
pensamento ao ponto de poderem
encontrar, cotidianamente, estruturas
matemáticas aplicadas.
Voltado a cursos de graduação de
matemática e ciência da computação,
o livro também pode ser trabalhado
por diversas outras áreas, devido a
demonstrações de inúmeras e variadas
aplicações, como padrões em DNA,
redes sociais, estrutura de linguagem,
modelos de população e música
dodecafônica. Complementam
a obra exercícios propostos, exemplos
e demonstrações.
www. g r u p o g e n . c o m. b r
http://gen-io.grupogen.com.br
http://www.grupogen.com.br
http://gen-io.grupogen.com.br
Page 125
Pensamento Quantitativo ■ 111
“macaco chuta jacaré” não, porque contém duas
palavras de comprimento seis.) Use uma árvore de
decisão para chegar à sua resposta.
16. Existem quantas cadeias binárias de quatro dígitos
que não contêm 000 ou 111? (Use uma árvore de
decisão.)
17. Encontre uma solução alternativa para o Exercício
16. (Conte os números de cadeias que contêm 000
ou 111 e subtraia do número total de cadeias biná
rias de quatro dígitos.)
18. Seja X um conjunto contendo 20 elementos. Use o
princípio da multiplicação para calcular |P(A)|, o
tamanho do conjunto das partes de X. (Dica: Para
encontrar um subconjunto de X , você deve escolher
se vai ou não incluir cada elemento de X)
19. O Museo de la Matemática em Querétaro, México,
contém uma exposição com a seguinte figura.
Quantas maneiras existem para a escolha de uma
sequência de triângulos que comece pelo triângulo
do topo e continue para baixo até a última linha,
tal que a sequência sempre siga abaixo para um
triângulo adjacente? (Os triângulos vermelhos
indicam um caminho com essas características.)
20. Considere o mapa na Figura 4.5. Odorico quer ir
do ponto A para algum ponto no metrô (represen
tado pela linha grossa pontilhada). Em cada inter
seção, ele pode decidir entre ir para sul ou para
leste. Quantos caminhos diferentes ele pode tomar?
Desenhe uma árvore de decisão representando os
diferentes caminhos possíveis.
21. Dois times (A e B) jogam um torneio melhor-de-
cinco. O torneio termina quando um time ganha
três jogos. Quantos cenários diferentes de ganho ou
perda são possíveis? (Use uma árvore de decisão.)
22. Demonstre o Teorema 4.1.
23. Demonstre o Teorema 4.2.
4.2 Seleções e Arranjos
Até agora, vimos como enumerar conjuntos usando
adição e multiplicação. Esses princípios básicos podem
ser aplicados a quase todos os problemas de contagem em
matemática discreta, mas existem muito mais técnicas
de contagem que poderíamos estudar. Embora possamos
passar facilmente um semestre aprendendo essas técnicas,
as duas próximas seções irão focar algumas das ideias
mais importantes para a solução de problemas quanti
tativos.
Nesta seção iremos nos concentrar em duas tarefas:
selecionar e arranjar. Um problema de seleção envolve
escolher um subconjunto de elementos de um conjunto
dado. Um problema de arranjo envolve escolher um
subconjunto e então colocar seus elementos em alguma
ordem particular. Quando somos capazes de pensar
em um problema de contagem em termos de seleções e
arranjos, a solução costuma ser mais fácil de ser enxer
gada.
4.2.1 Permutações: O Princípio do
Arranjo
Aqui está um exemplo de um problema de arranjo:
Exemplo 4.12 lago tem 26 ímãs de geladeira na forma
de letras de A a Z. Quantas cadeias diferentes de três
letras ele pode formar com os ímãs?
Solução: Este é um problema de “placa de carro” (veja
o Exemplo 4.10), porém com uma restrição. Uma vez
que lago tem apenas um ímã para cada letra, ele não
tem permissão para repetir letras. Existem três espaços
a serem preenchidos. Ele tem 26 escolhas para o primeiro
espaço. Uma vez que ele não pode reutilizar essa letra,
ele tem 25 escolhas para o segundo espaço e, da mesma
forma, 24 para o terceiro. Portanto, o número total de
cadeias possíveis é 26 • 25 • 24. 0
A solução utiliza o princípio da multiplicação, mas
a cada decisão sucessiva o número de letras é reduzido
em um. O princípio do arranjo dá a regra geral.F ig u ra 4.5 Mapa da rua para o Exercício 20.
Page 126
112 ■ Capítulo 4
Princípio do Arranjo. O número de maneiras de
formar uma lista ordenada de r elementos distintos
escolhidos em um conjunto de n elementos é
P(n,r) = n • (n — 1) • (n — 2) • • • (n — r + 1).
Uma lista como essa é chamada um arranjo. Note que
os arranjos têm duas propriedades-chave: a ordem dos
elementos importa, e todos os elementos são distintos.
A notação P(n, r) vem do termo matemático para
arranjos: permutações. Note que
é um jeito conveniente de expressar o número de permu
tações em termos da função fatorial. Lembre que a função
fatorial é definida por
n! = n • (n — 1) • • • 3 • 2 • 1,
e, por convenção, 0! = 1. Note que P(n, n) = n\.
Exemplo 4.13 Um time de beisebol é formado por 24
jogadores. De quantas maneiras diferentes o técnico pode
escolher uma lista ordenada de 9 batedores?
Solução: Existem P(24, 9) = 241/15! = 474.467.051.520
~ 4,74 X 1011 maneiras de fazer tal lista. 0
Exem plo 4.14 Quantas maneiras diferentes existem
para rearranjarmos as letras na palavra CONVERSA?
Solução: E importante notarmos que todas as letras
da palavra CONVERSA são diferentes. Assim, elas
formam um conjunto de oito letras, e rearranjar as
letras consiste em escolher uma lista ordenada de oito
elementos distintos a partir desse conjunto. O número de
maneiras para se fazer isso é P(8, 8) = 8! = 40.320. 0
Rearranjar as letras na palavras CONVERSA é o
mesmo que achar uma correspondência bijetiva:
/:{C, O, N, V, E, R, S, A}— >{C, O. N, V, E, R, S. A}.
Para qualquer letra l em CONVERSA, f(J) é a letra que
a substitui no rearranjo. Em geral, se X é um conjunto
finito com n elementos, então o número de correspon
dências bijetivas / : X —> X ê n\. Uma função como esta
é chamada de permutação do conjunto X.
Exemplo 4.15 Uma gaveta de cozinha contém dez dife
rentes recipientes de plástico para comida e dez tampas
diferentes, mas qualquer tampa se encaixa em qual
quer um dos recipientes. De quantas maneiras diferentes
podemos casar as tampas com os recipientes?
Solução: A chave para resolver este problema é pensar
sobre ele da forma correta. A fim de ordenar em pares
cada recipiente com uma tampa, comece por alinhar
todos os recipientes em uma linha. (Não importa como
você irá alinhá-los.) Agora, escolha um arranjo das dez
tampas e posicione as tampas nessa ordem ao lado dos
recipientes. Isso determina uma correspondência entre
recipientes e tampas, e todas as correspondências são
determinadas dessa forma. A única escolha foi feita
durante o arranjo das tampas, portanto existem P(10,
10) = 10! = 3.628.800 maneiras de casar tampas e reci
pientes. 0
O próximo exemplo sublinha a diferença entre o prin
cípio da multiplicação e o princípio da combinação.
Exem plo 4.16 Uma urna contém 10 bolas de pingue-
pongue, numeradas de 1 a 10. Quatro bolas são reti
radas da urna em sequência, e os números nas bolas
são gravados. Quantas maneiras existem de isso ser
feito se
(a) cada bola é recolocada na urna antes que a
próxima seja retirada.
(b) as bolas são retiradas e não são repostas.
Solução: No caso (a), sempre existem 1.0 bolas na urna,
portanto sempre existem 10 escolhas. Pelo princípio da
multiplicação, o número de maneiras para retirar quatro
bolas é 104 = 10.000. No caso (b), as bolas não são
repostas, portanto o número de escolhas diminui em
um cada vez que uma bola é retirada. Por isso, existem
P(10, 4) = 10 • 9 • 8 • 7 = 5.040 maneiras de retirar
quatro bolas. 0
O Exemplo 4.16 pertence ao gênero misterioso de
“problemas de urna”. Embora não encontremos urnas
com muita frequência na vida real, esse tipo de problema
é um tanto prototípico. Como os problemas de placa
de automóveis, os problemas de urna fornecem uma
forma simples de classificar certos tipos de tarefas de
enumeração. E escutamos com frequência os termos “com
reposição” e “sem reposição” associados a arranjos ou
seleções; essa terminologia faz sentido no contexto de
urnas.
4.2.2 Combinações: O Princípio da
Seleção
Aqui está uma leve variação do Exemplo 4.13.
Exemplo 4.17 Um time de beisebol é formado por 24
jogadores. De quantas maneiras diferentes podemos esco
lher um grupo de nove jogadores para começar o jogo?
Page 249
David J. Hunter graduou-se, com
grandes honras, pela University of
Illinois e concluiu mestrado e doutorado
em Matemática na University of
Virginia. Atualmente trabalha como
professor na Westmont College. Possui
diversos artigos e publicações na área,
sendo inclusive consultor do periódico
de matemática da instituição onde atua.
É membro da Association of Christians
in the Mathematical Sciences, além de
participar da Mathematical Association
of America (Southern California Section)
como membro do conselho e editor de
conteúdo do site da associação.
w w w .g ru p o g en .co m .b r
http://gen-io.grupogen.com.br
http://www.grupogen.com.br
http://gen-io.grupogen.com.br
Page 250
F U N D A M E N T O S da
M A T E M Á T I C A
D I S C R E T A
DAVI D J. H U N T E R
Com conteúdo abrangente, apresentado de modo simples e repleto de demonstrações,
Fundamentos da Matemática Discreta é voltado principalmente a estudantes de matemática
e ciência da computação, embora diversas outras áreas possam se beneficiar da obra.
Estudos de caso de economia, biologia, sociologia, linguística e música são abordados no
livro, organizado em seis capítulos. Além disso, inúmeros gráficos, exemplos e exercícios
complementam a leitura.
A obra tem como ponto forte a diversidade e a variedade de aplicações da matemática
discreta, verificáveis no cotidiano dos leitores.
w w w .g ru p o g en .co m .b r
http://gen-io.grupogen.com.br
ISBN 978-85-216-1810-2
http://www.grupogen.com.br
http://gen-io.grupogen.com.br
F U N D A M E N T O S
da
M A T E M Á T I C A
D I S C R E T A
J . H U N T E R
GEN I Informação Online
Page 2
Diferenciando-se dos livros-texto
tradicionais, Fundamentos da
Matemática Discreta foi concebido para
abordar o tema em amplitude, mantendo
o encadeamento e a uniformidade
das ideias.
O autor apresenta cinco tipos de
pensamento matemático ao longo da
obra: lógico, relacional, recursivo,
quantitativo e analítico. Ordenados
sequencialmente, cada capítulo trata
de um dos tópicos mencionados, o
que possibilita a compreensão efetiva
do texto.
O Capítulo 5, sobre o pensamento
analítico, aplica o conteúdo abordado
nos quatro capítulos anteriores aos
estudos da complexidade algorítmica e
da precisão de programas. Dessa forma,
a leitura proporciona a compreensão
da ocorrência e da eficiência dos
algoritmos. Além disso, a obra permite
que os estudantes desenvolvam o
pensamento ao ponto de poderem
encontrar, cotidianamente, estruturas
matemáticas aplicadas.
Voltado a cursos de graduação de
matemática e ciência da computação,
o livro também pode ser trabalhado
por diversas outras áreas, devido a
demonstrações de inúmeras e variadas
aplicações, como padrões em DNA,
redes sociais, estrutura de linguagem,
modelos de população e música
dodecafônica. Complementam
a obra exercícios propostos, exemplos
e demonstrações.
www. g r u p o g e n . c o m. b r
http://gen-io.grupogen.com.br
http://www.grupogen.com.br
http://gen-io.grupogen.com.br
Page 125
Pensamento Quantitativo ■ 111
“macaco chuta jacaré” não, porque contém duas
palavras de comprimento seis.) Use uma árvore de
decisão para chegar à sua resposta.
16. Existem quantas cadeias binárias de quatro dígitos
que não contêm 000 ou 111? (Use uma árvore de
decisão.)
17. Encontre uma solução alternativa para o Exercício
16. (Conte os números de cadeias que contêm 000
ou 111 e subtraia do número total de cadeias biná
rias de quatro dígitos.)
18. Seja X um conjunto contendo 20 elementos. Use o
princípio da multiplicação para calcular |P(A)|, o
tamanho do conjunto das partes de X. (Dica: Para
encontrar um subconjunto de X , você deve escolher
se vai ou não incluir cada elemento de X)
19. O Museo de la Matemática em Querétaro, México,
contém uma exposição com a seguinte figura.
Quantas maneiras existem para a escolha de uma
sequência de triângulos que comece pelo triângulo
do topo e continue para baixo até a última linha,
tal que a sequência sempre siga abaixo para um
triângulo adjacente? (Os triângulos vermelhos
indicam um caminho com essas características.)
20. Considere o mapa na Figura 4.5. Odorico quer ir
do ponto A para algum ponto no metrô (represen
tado pela linha grossa pontilhada). Em cada inter
seção, ele pode decidir entre ir para sul ou para
leste. Quantos caminhos diferentes ele pode tomar?
Desenhe uma árvore de decisão representando os
diferentes caminhos possíveis.
21. Dois times (A e B) jogam um torneio melhor-de-
cinco. O torneio termina quando um time ganha
três jogos. Quantos cenários diferentes de ganho ou
perda são possíveis? (Use uma árvore de decisão.)
22. Demonstre o Teorema 4.1.
23. Demonstre o Teorema 4.2.
4.2 Seleções e Arranjos
Até agora, vimos como enumerar conjuntos usando
adição e multiplicação. Esses princípios básicos podem
ser aplicados a quase todos os problemas de contagem em
matemática discreta, mas existem muito mais técnicas
de contagem que poderíamos estudar. Embora possamos
passar facilmente um semestre aprendendo essas técnicas,
as duas próximas seções irão focar algumas das ideias
mais importantes para a solução de problemas quanti
tativos.
Nesta seção iremos nos concentrar em duas tarefas:
selecionar e arranjar. Um problema de seleção envolve
escolher um subconjunto de elementos de um conjunto
dado. Um problema de arranjo envolve escolher um
subconjunto e então colocar seus elementos em alguma
ordem particular. Quando somos capazes de pensar
em um problema de contagem em termos de seleções e
arranjos, a solução costuma ser mais fácil de ser enxer
gada.
4.2.1 Permutações: O Princípio do
Arranjo
Aqui está um exemplo de um problema de arranjo:
Exemplo 4.12 lago tem 26 ímãs de geladeira na forma
de letras de A a Z. Quantas cadeias diferentes de três
letras ele pode formar com os ímãs?
Solução: Este é um problema de “placa de carro” (veja
o Exemplo 4.10), porém com uma restrição. Uma vez
que lago tem apenas um ímã para cada letra, ele não
tem permissão para repetir letras. Existem três espaços
a serem preenchidos. Ele tem 26 escolhas para o primeiro
espaço. Uma vez que ele não pode reutilizar essa letra,
ele tem 25 escolhas para o segundo espaço e, da mesma
forma, 24 para o terceiro. Portanto, o número total de
cadeias possíveis é 26 • 25 • 24. 0
A solução utiliza o princípio da multiplicação, mas
a cada decisão sucessiva o número de letras é reduzido
em um. O princípio do arranjo dá a regra geral.F ig u ra 4.5 Mapa da rua para o Exercício 20.
Page 126
112 ■ Capítulo 4
Princípio do Arranjo. O número de maneiras de
formar uma lista ordenada de r elementos distintos
escolhidos em um conjunto de n elementos é
P(n,r) = n • (n — 1) • (n — 2) • • • (n — r + 1).
Uma lista como essa é chamada um arranjo. Note que
os arranjos têm duas propriedades-chave: a ordem dos
elementos importa, e todos os elementos são distintos.
A notação P(n, r) vem do termo matemático para
arranjos: permutações. Note que
é um jeito conveniente de expressar o número de permu
tações em termos da função fatorial. Lembre que a função
fatorial é definida por
n! = n • (n — 1) • • • 3 • 2 • 1,
e, por convenção, 0! = 1. Note que P(n, n) = n\.
Exemplo 4.13 Um time de beisebol é formado por 24
jogadores. De quantas maneiras diferentes o técnico pode
escolher uma lista ordenada de 9 batedores?
Solução: Existem P(24, 9) = 241/15! = 474.467.051.520
~ 4,74 X 1011 maneiras de fazer tal lista. 0
Exem plo 4.14 Quantas maneiras diferentes existem
para rearranjarmos as letras na palavra CONVERSA?
Solução: E importante notarmos que todas as letras
da palavra CONVERSA são diferentes. Assim, elas
formam um conjunto de oito letras, e rearranjar as
letras consiste em escolher uma lista ordenada de oito
elementos distintos a partir desse conjunto. O número de
maneiras para se fazer isso é P(8, 8) = 8! = 40.320. 0
Rearranjar as letras na palavras CONVERSA é o
mesmo que achar uma correspondência bijetiva:
/:{C, O, N, V, E, R, S, A}— >{C, O. N, V, E, R, S. A}.
Para qualquer letra l em CONVERSA, f(J) é a letra que
a substitui no rearranjo. Em geral, se X é um conjunto
finito com n elementos, então o número de correspon
dências bijetivas / : X —> X ê n\. Uma função como esta
é chamada de permutação do conjunto X.
Exemplo 4.15 Uma gaveta de cozinha contém dez dife
rentes recipientes de plástico para comida e dez tampas
diferentes, mas qualquer tampa se encaixa em qual
quer um dos recipientes. De quantas maneiras diferentes
podemos casar as tampas com os recipientes?
Solução: A chave para resolver este problema é pensar
sobre ele da forma correta. A fim de ordenar em pares
cada recipiente com uma tampa, comece por alinhar
todos os recipientes em uma linha. (Não importa como
você irá alinhá-los.) Agora, escolha um arranjo das dez
tampas e posicione as tampas nessa ordem ao lado dos
recipientes. Isso determina uma correspondência entre
recipientes e tampas, e todas as correspondências são
determinadas dessa forma. A única escolha foi feita
durante o arranjo das tampas, portanto existem P(10,
10) = 10! = 3.628.800 maneiras de casar tampas e reci
pientes. 0
O próximo exemplo sublinha a diferença entre o prin
cípio da multiplicação e o princípio da combinação.
Exem plo 4.16 Uma urna contém 10 bolas de pingue-
pongue, numeradas de 1 a 10. Quatro bolas são reti
radas da urna em sequência, e os números nas bolas
são gravados. Quantas maneiras existem de isso ser
feito se
(a) cada bola é recolocada na urna antes que a
próxima seja retirada.
(b) as bolas são retiradas e não são repostas.
Solução: No caso (a), sempre existem 1.0 bolas na urna,
portanto sempre existem 10 escolhas. Pelo princípio da
multiplicação, o número de maneiras para retirar quatro
bolas é 104 = 10.000. No caso (b), as bolas não são
repostas, portanto o número de escolhas diminui em
um cada vez que uma bola é retirada. Por isso, existem
P(10, 4) = 10 • 9 • 8 • 7 = 5.040 maneiras de retirar
quatro bolas. 0
O Exemplo 4.16 pertence ao gênero misterioso de
“problemas de urna”. Embora não encontremos urnas
com muita frequência na vida real, esse tipo de problema
é um tanto prototípico. Como os problemas de placa
de automóveis, os problemas de urna fornecem uma
forma simples de classificar certos tipos de tarefas de
enumeração. E escutamos com frequência os termos “com
reposição” e “sem reposição” associados a arranjos ou
seleções; essa terminologia faz sentido no contexto de
urnas.
4.2.2 Combinações: O Princípio da
Seleção
Aqui está uma leve variação do Exemplo 4.13.
Exemplo 4.17 Um time de beisebol é formado por 24
jogadores. De quantas maneiras diferentes podemos esco
lher um grupo de nove jogadores para começar o jogo?
Page 249
David J. Hunter graduou-se, com
grandes honras, pela University of
Illinois e concluiu mestrado e doutorado
em Matemática na University of
Virginia. Atualmente trabalha como
professor na Westmont College. Possui
diversos artigos e publicações na área,
sendo inclusive consultor do periódico
de matemática da instituição onde atua.
É membro da Association of Christians
in the Mathematical Sciences, além de
participar da Mathematical Association
of America (Southern California Section)
como membro do conselho e editor de
conteúdo do site da associação.
w w w .g ru p o g en .co m .b r
http://gen-io.grupogen.com.br
http://www.grupogen.com.br
http://gen-io.grupogen.com.br
Page 250
F U N D A M E N T O S da
M A T E M Á T I C A
D I S C R E T A
DAVI D J. H U N T E R
Com conteúdo abrangente, apresentado de modo simples e repleto de demonstrações,
Fundamentos da Matemática Discreta é voltado principalmente a estudantes de matemática
e ciência da computação, embora diversas outras áreas possam se beneficiar da obra.
Estudos de caso de economia, biologia, sociologia, linguística e música são abordados no
livro, organizado em seis capítulos. Além disso, inúmeros gráficos, exemplos e exercícios
complementam a leitura.
A obra tem como ponto forte a diversidade e a variedade de aplicações da matemática
discreta, verificáveis no cotidiano dos leitores.
w w w .g ru p o g en .co m .b r
http://gen-io.grupogen.com.br
ISBN 978-85-216-1810-2
http://www.grupogen.com.br
http://gen-io.grupogen.com.br
