Instituto Federal de Educação, Ciência e
Tecnologia de São Paulo - IFSP
Campus de Caraguatatuba
Tecnólogo em Análise e Desenvolvimento de Sistemas
20 Semestre de 2013
Matemática Discreta 2 – MD 2
Prof. Lineu Mialaret
Aula 3: Combinatória (1)
Matemática Discreta 2
Aula 3 - 1/51
©Prof. Lineu Mialaret
Introdução (1)
 A Combinatória (ou Análise Combinatória) é o ramo da
Matemática que trata de contagem. Problemas desse
tipo são importantes sempre que se utiliza recursos
finitos.
 Quanto espaço de armazenamento uma tecnologia de
banco de dados usa?
 Quantos usuários uma determinada configuração de
computador pode suportar?
 Quantas computações um determinado algoritmo executa?
 Esses problemas se resumem, muitas vezes, em
determinar o número de elementos em algum conjunto
finito. Exemplos de problemas de contagem já vistos:
 Quantas linhas tem uma tabela verdade com n letras de
proposição?
 Quantos subconjuntos tem um conjunto com n elementos?
Matemática Discreta 2
Aula 3 - 2/51
©Prof. Lineu Mialaret
Introdução (2)
 Outros exemplos de problemas de contagem:
 Qual o número de elementos dos seguintes conjuntos?
 A é o conjunto de números de dois algarismos com repetição
formados pelos dígitos 1, 2 e 3.
 B é o conjunto de diagonais de um heptágono.
 C é o conjunto das seqüências das letras que se obtém a
partir das letras da palavra ARI (anagramas);
– Obs.: Um anagrama é uma (outra) palavra construída com
as mesmas letras da palavra original trocadas de posição.
 D é o conjunto dos números de três algarismos, todos
distintos, formados pelos dígitos 1, 2, 3, 4, 5, 6, 7, 8.
Matemática Discreta 2
Aula 3 - 3/51
©Prof. Lineu Mialaret
Princípio da Multiplicação (1)
 Seja o seguinte cenário:
 Uma criança pode escolher uma entre duas balas, uma
rosa e outra preta, e um entre três chicletes, um amarelo,
outro verde e um outro branco. Quantos conjuntos
diferentes de doces a criança pode ter?
 Pode-se resolver esse problema separando-se a tarefa de
escolha dos doces em duas etapas (eventos ou escolhas)
seqüenciais:
 Primeiro, escolher a bala (R ou P);
 Depois, escolher o chiclete (A, V ou B).
 Para se facilitar a compreensão desse problema, pode-
se usar uma Árvore de Possibilidades (apresentada na
próxima transparência), que ajuda visualmente a
entender a solução do problema.
Matemática Discreta 2
Aula 3 - 4/51
©Prof. Lineu Mialaret
Princípio da Multiplicação (2)
 Árvore de Possibilidades:
 A árvore mostra que existem 2 x 3 = 6 possibilidades de
escolhas de balas e chicletes, a saber
 ({R,A}, {R,V},{R,B}, {P,A}, {P,V}, {P,B}).
Matemática Discreta 2
Aula 3 - 5/51
©Prof. Lineu Mialaret
Princípio da Multiplicação (3)
 A seqüência de eventos também pode ser trocada, sem
afetar o resultado (3 x 2 = 6 possibilidades).
Matemática Discreta 2
Aula 3 - 6/51
©Prof. Lineu Mialaret
Princípio da Multiplicação (4)
 O exemplo anterior ilustra o fato de que o número total
de resultados possíveis para uma seqüência de eventos
(no caso a escolha de balas e de chicletes) pode ser
obtido multiplicando-se o número de possibilidades do
primeiro evento (escolha das balas) pelo número de
possibilidades do segundo evento (escolha dos
chicletes). Isso é sintetizado no seguinte princípio abaixo.
 Princípio da Multiplicação:
 Se existem n1 resultados (escolhas) possíveis para um
primeiro evento e1 e n2 resultados (escolhas) possíveis
para um evento e2, então existem n1 x n2 resultados
possíveis para a seqüência e1e2 dos dois eventos.
 Obs.:
 O princípio vale para uma seqüência com qualquer número de
eventos.
Matemática Discreta 2
Aula 3 - 7/51
©Prof. Lineu Mialaret
Princípio da Multiplicação (5)
 Exemplo 1: A última parte de um número de telefone
possui 4 dígitos. Quanto desses números de 4 dígitos
existem?
 A seqüência de eventos (escolhas) é: escolher o primeiro
dígito, depois o segundo, o terceiro e finalmente o quarto.
 O primeiro dígito pode ser escolhido entre 0 a 9, ou seja de
10 dígitos, significando que há 10 possibilidades para a
primeira opção de escolha.
 As escolhas seguintes também terão cada uma 10 opções.
 Usando o princípio da multiplicação, deve-se multiplicar essas
possibilidades para cada tarefa.
 Existem 10 x 10 x 10 x 10 = 10000 números diferentes.
 Obs.: Se um elemento (dígito) não puder ser usado de
novo (não são permitidas repetições), o número de
possibilidades é afetado.
Matemática Discreta 2
Aula 3 - 8/51
©Prof. Lineu Mialaret
Princípio da Multiplicação (6)
 Exemplo 2: A última parte de um número de telefone
possui 4 dígitos. Quanto desses números de 4 dígitos
existem se não houver repetição de dígitos?
 A seqüência de eventos (escolhas) continua a ser a
mesma: escolher o primeiro dígito, depois o segundo, o
terceiro e finalmente o quarto.
 O primeiro dígito pode ser escolhido entre 0 a 9, ou seja 10
dígitos, indicando que há 10 possibilidades para a primeira
opção.
 As escolhas seguintes dos dígitos são afetadas. Há 9 opções
para o segundo dígito (retira-se o dígito escolhido
anteriormente) e assim por diante.
 Usando o princípio da multiplicação, deve-se multiplicar essas
possibilidades para cada escolha.
 Existem 10 x 9 x 8 x 7 = 5040 números diferentes.
Matemática Discreta 2
Aula 3 - 9/51
©Prof. Lineu Mialaret
Princípio da Multiplicação (7)
 Exemplo 3: Para qualquer conjunto finito S, seja |S|
(cardinalidade) o número de elementos em S. Sejam A e
B conjuntos finitos quaisquer, então |A  B| = |A| x |B|.
 A  B, o produto cartesiano de A com B, denota todos os
pares ordenados com a primeiro elemento em A e o
segundo em B.
 Pode-se formar tais pares ordenados como uma seqüência
de dois eventos (escolhas):
 Escolher o primeiro elemento, com |A| possibilidades.
 Escolher o segundo, com |B| possibilidades.
 Esse resultado segue o princípio da multiplicação.
 Obs.:
  representa o operador de produto cartesiano;
 x representa o operador de multiplicação.
Matemática Discreta 2
Aula 3 - 10/51
©Prof. Lineu Mialaret
Princípio da Multiplicação (8)
 Exercício 1 –
a) De quantas maneiras pode-se escolher
representantes em um grupo de 25 pessoas?
Matemática Discreta 2
Aula 3 - 11/51
três
©Prof. Lineu Mialaret
Princípio da Multiplicação (9)
 Exercício 1 –
a) De quantas maneiras pode-se escolher um grupo de três
representantes em um conjunto de 25 pessoas?
 Resposta:
 Existem três escolhas sucessivas sem repetição. A
primeira escolha tem 25 possibilidades. A segunda tem 24
e a terceira 23. O número total de possibilidades é de
25 x 24 x 23 = 13800 possibilidades.
Matemática Discreta 2
25 Escolhas
24 Escolhas
23 Escolhas
Ev. 1
Ev. 2
Ev. 3
Aula 3 - 12/51
©Prof. Lineu Mialaret
Princípio da Multiplicação (10)
 Exercício 1 –
b) De quantas maneiras pode-se escolher um representante
para três comissões, num conjunto de 25 pessoas, se um
representante pode participar de mais de uma comissão?
Matemática Discreta 2
Aula 3 - 13/51
©Prof. Lineu Mialaret
Princípio da Multiplicação (11)
 Exercício 1 –
b) De quantas maneiras pode-se escolher um representante
para três comissões, num conjunto de 25 pessoas, se um
representante pode participar de mais de uma comissão?
 Resposta:
 As três escolhas são realizadas sucessivamente, mas a
repetição é permitida. O número total de possibilidades é
de 25 x 25 x 25 = 15625 possibilidades.
25 Escolhas
Com 1
Matemática Discreta 2
25 Escolhas
Com 2
Aula 3 - 14/51
25 Escolhas
Com 3
©Prof. Lineu Mialaret
Princípio da Multiplicação (12)
 Exercício 1 –
c) Se um homem tem quatro ternos, oito camisas e cinco
gravatas, que quantos modos diferentes ele pode se
vestir?
Matemática Discreta 2
Aula 3 - 15/51
©Prof. Lineu Mialaret
Princípio da Multiplicação (13)
 Exercício 1 –
c) Se um homem tem quatro ternos, oito camisas e cinco
gravatas, que quantos modos diferentes ele pode se
vestir?
 Resposta:
 Existem três escolhas sucessivas. A primeira escolha tem
4 possibilidades. A segunda tem 8 e a terceira 5. O número
total de possibilidades é de 4 x 8 x 5 = 160 possibilidades.
Matemática Discreta 2
Aula 3 - 16/51
©Prof. Lineu Mialaret
Princípio da Adição (1)
 Seja o seguinte cenário: Deseja-se selecionar uma
sobremesa entre três tortas e/ou quatro bolos. De
quantos modos (maneiras) isso pode ser feito?
 Há dois eventos (escolhas), um com três resultados
possíveis (a escolha da torta) e outro com quatro (a
escolha do bolo).
 Não há uma seqüência de eventos (escolhas), pois só uma
sobremesa será escolhida (dentre dois conjuntos
disjuntos).
 O número total de escolhas possíveis é o número de
escolhas de sobremesas (3 + 4 = 7).
 Princípio da Adição:
 Se A e B são eventos (escolhas) disjuntos com n1 e n2
resultados, então o número total de possibilidades de
escolhas para o evento “A ou B” é n1 + n2.
Matemática Discreta 2
Aula 3 - 17/51
©Prof. Lineu Mialaret
Princípio da Adição (2)
 Exemplo 4: Um consumidor deseja comprar um veículo
numa concessionária. A loja tem 23 automóveis e 14
caminhões em estoque. Quantas escolhas possíveis de
veículos o consumidor pode fazer?
 O consumidor pode escolher um carro ou um caminhão.
Esses eventos (escolhas) são disjuntos:
 A escolha de um carro tem 23 possibilidades.
 A escolha de um caminhão tem 14 possibilidades.
 Pelo princípio da adição, o consumidor tem 23 + 14 = 37
possibilidades de escolha de um veículo.
 Obs.:
 Notar que os conjuntos de escolhas (eventos) são
disjuntos (o cliente só pode escolher ou um automóvel
ou um caminhão).
Matemática Discreta 2
Aula 3 - 18/51
©Prof. Lineu Mialaret
Princípio da Adição (3)
 Exemplo 5: Sejam A e B conjuntos quaisquer disjuntos.
Então |A  B| = |A| + |B|.
 Ou seja, a cardinalidade da união dos conjuntos A e B é
igual a soma das cardinalidades dos conjuntos A e B.
 Pode-se encontrar |A  B| separando-se em dois casos
disjuntos:
 Primeiro, conta-se o número de elementos de A, |A|.
 Depois, conta-se o numero de elementos de B, |B|.
 Pelo princípio da adição, soma-se esses dois números.
Matemática Discreta 2
Aula 3 - 19/51
©Prof. Lineu Mialaret
Princípio da Adição (4)
 Exemplo 6: Sejam A e B conjuntos quaisquer finitos.
Então
 |A  B| = |A| - |A  B|; e
 |A  B| = |A| - |B|, se B  A.
 Relembrando (MD 1):
 Se A é um subconjunto de B, simboliza-se
 por A  B, que se lê “A está contido em B” ou “B contém A”,
simbolizado por B  A.
 Caso contrário, indica-se que “A não está contido em B”, simbolizado
por A ⊈ B ou “B não contém A”, denotado por B ⊉ A.
 Se A  B, mas A ≠ B (há pelo menos um elemento de B que não
pertence a A), então diz-se que A é um subconjunto próprio de B,
simbolizado por A  B.
Matemática Discreta 2
Aula 3 - 20/51
©Prof. Lineu Mialaret
Princípio da Multiplicação + Adição (1)
 Freqüentemente o princípio da Adição é usado junto com
o da Multiplicação.
 Seja o seguinte cenário referente ao exemplo da
transparência 4: suponha que se quer encontrar de
quantas maneiras a criança pode escolher o doce, ao
invés do número de conjuntos de doces que ela pode ter.
 Logo, escolher uma bala rosa e um chiclete amarelo não é
o mesmo que escolher primeiro um chiclete amarelo e
depois uma bala rosa.
 Pode-se resolver esse problema considerando-se dois
casos disjuntos:
 A escolha de balas ou chicletes primeiro.
 Cada um desses casos (pelo princípio da multiplicação) tem 6
possibilidades, de modo que (pelo princípio da adição) há
6 + 6 = 12 modos diferentes de escolher os doces.
Matemática Discreta 2
Aula 3 - 21/51
©Prof. Lineu Mialaret
Princípio da Multiplicação + Adição (2)
 Exemplo 7: Quantos números de quatro dígitos começam
com o dígito 4 ou 5?
 Podem ser considerados dois casos disjuntos: números
que começam com 4 e aqueles que começam com 5.
 Para aqueles que começam com o dígito 4, o número de
escolhas possíveis é uma escolha para o primeiro dígito, e
10 escolhas possíveis para cada um dos três outros
dígitos.
 Pelo princípio da multiplicação, há 1x10x10x10 = 1000
escolhas possíveis.
 O mesmo raciocínio vale para a seqüência de 4 dígitos
começando com o dígito 5,ou seja, há 1000 escolhas.
 Pelo princípio da adição, há 1000 + 1000 = 2000 escolhas
de números de quatro dígitos que começam com 4 ou 5.
Matemática Discreta 2
Aula 3 - 22/51
©Prof. Lineu Mialaret
Princípio da Multiplicação + Adição (3)
 Exercício 2: Se uma mulher possui sete blusas, cinco
saias e nove vestidos, de quantos modos diferentes ela
pode se vestir?
Matemática Discreta 2
Aula 3 - 23/51
©Prof. Lineu Mialaret
Princípio da Multiplicação + Adição (4)
 Exercício 2: Se uma mulher possui sete blusas, cinco
saias e nove vestidos, de quantos modos diferentes ela
pode se vestir?
 Resposta:?
Matemática Discreta 2
Aula 3 - 24/51
©Prof. Lineu Mialaret
Princípio da Multiplicação + Adição (5)
 Exemplo 8: Quantos números de quatro dígitos começam
com o dígito 4 ou 5?
 Uma outra solução para esse problema, sem usar o
princípio da adição, é dividí-lo em quatro tarefas (escolhas)
sucessivas, onde a primeira tarefa é escolher o primeiro
dígito. Isso gera duas possibilidades: escolher o dígito 4 ou
5.
 Existem então 2 x 10 x 10 x 10 = 2000 possibilidades.
 Isso mostra que um problema de contagem pode ser
resolvido, muitas vezes, de mais de uma forma.
Matemática Discreta 2
Aula 3 - 25/51
©Prof. Lineu Mialaret
Princípio da Multiplicação + Adição (6)
 Exemplo 9: Suponha que os quatro últimos dígitos de um
número de telefone têm que incluir pelo menos um dígito
repetido. Quantos desses números existem?
 Pode-se resolver esse problema usando-se o princípio da
adição diretamente, mas essa solução não é muito
conveniente.
 Por exemplo, se os dois primeiros dígitos são iguais mas o
terceiro e o quarto são diferentes, há 10 x 1 x 9 x 8 modos
disso ocorrer.
 Se o primeiro e o terceiro são iguais e o segundo e quarto
dígitos são diferentes, há 10 x 9 x 1 x 8 possibilidades, e
assim por diante.
 Como resolver esse problema de contagem?
Matemática Discreta 2
Aula 3 - 26/51
©Prof. Lineu Mialaret
Princípio da Multiplicação + Adição (7)
 Pode-se resolver esse problema observando-se que os
números com repetição e sem repetição formam um
conjunto disjunto cuja união é o conjunto de todos os
números com quatro dígitos.
 Lembrar que |A  B| = |A| + |B|.
 Pode-se encontrar o número de inteiros com dígitos
repetidos subtraindo o número de casos sem repetição
(que é de 5040, de acordo com o exemplo 2, transp. 9 ) do
número total de possibilidades (que é de 10000, de acordo
com o exemplo 1, transp. 8).
 Logo, o número total de dígitos com algarismos repetidos é
10000 – 5040 = 4960.
Matemática Discreta 2
Aula 3 - 27/51
©Prof. Lineu Mialaret
Princípio da Multiplicação + Adição (8)
 Exercício 3: Quantos inteiros de 3 dígitos no intervalo
[100, 999] são pares?
Matemática Discreta 2
Aula 3 - 28/51
©Prof. Lineu Mialaret
Princípio da Multiplicação + Adição (9)
 Exercício 3: Quantos inteiros de 3 dígitos no intervalo
[100, 999] são pares?
 Resposta:?
Matemática Discreta 2
Aula 3 - 29/51
©Prof. Lineu Mialaret
Árvore de Decisão (1)
 Árvores como a mostrada no exemplo da escolha dos
doces, que ilustram o número de possibilidades de um
evento baseado em uma série de escolhas possíveis são
chamadas de Árvores de Decisão (ou Árvore de
Possibilidades).
 O estudo de árvores (uma importante estrutura de dados
da Ciência da Computação) será introduzido
posteriormente, mas elas já podem ser usadas para
resolver problemas de contagens adicionais.
 Árvores regulares são as que os números de resultados
possíveis em qualquer nível da árvore é o mesmo em todo
o nível, como as do exemplo mostrado.
Matemática Discreta 2
Aula 3 - 30/51
©Prof. Lineu Mialaret
Árvore de Decisão (2)
 Exemplo
10: Uma árvore de decisão para uma
proposição com duas letras proposicionais.
Árvore de Decisão.
Matemática Discreta 2
Aula 3 - 31/51
©Prof. Lineu Mialaret
Árvore de Decisão (3)
 Exemplo 11: Considere um sistema computacional que
possui quatro unidades de Entrada/Saída A, B, C e D e
três processadores X, Y e Z. Qualquer unidade de E/S
pode ser conectada a um processador. Quantas
possibilidades existem de conectar uma unidade de E/S
a um processador?
 Pode-se fazer 4 escolhas
referentes às unidades de
E/S e 3 escolhas referentes
ao processador.
 Logo existem 4 x 3 = 12
possibilidades.
Matemática Discreta 2
Aula 3 - 32/51
©Prof. Lineu Mialaret
Árvore de Decisão (4)
 Exemplo 12: Quantas vezes o trecho de programa entre
os dois laços for é executado?
Matemática Discreta 2
Aula 3 - 33/51
©Prof. Lineu Mialaret
Árvore de Decisão (5)
 Exemplo 12: Quantas vezes o trecho de programa entre
os dois laços for é executado?
 Resposta:?
Matemática Discreta 2
Aula 3 - 34/51
©Prof. Lineu Mialaret
Árvore de Decisão (6)
 Exemplo 13: Antônio está jogando moedas. Cada jogada
resulta em cara (C) ou coroa (K). Quantos resultados
possíveis ele pode obter se jogar cinco vezes sem cair
duas caras consecutivas?
 Cada jogada da moeda tem dois resultados possíveis; o
ramo da esquerda está marcado com um C, denotando
cara, e o da direita, com um K, denotando coroa.
 Será visto na árvore a seguir, o número de possibilidades
obtido.
Matemática Discreta 2
Aula 3 - 35/51
©Prof. Lineu Mialaret
Árvore de Decisão (7)
Árvore de Decisão do Exemplo 11.
Matemática Discreta 2
Aula 3 - 36/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (1)
 Este é mais um princípio usado para se resolver
problemas de combinatória.
 Para se desenvolver esse princípio, sejam A e B
subconjuntos de um conjunto universo S. Então A  B,
B  A e A  B são disjuntos dois a dois, conforme
apresentado abaixo.
Matemática Discreta 2
Aula 3 - 37/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (2)
 Exercício 4: No que resulta (A  B)  (B  A)  (A  B)?
Matemática Discreta 2
Aula 3 - 38/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (3)
 Exercício 4: No que resulta (A  B)  (B  A)  (A  B)?
 Resposta:
 A  B.
Matemática Discreta 2
Aula 3 - 39/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (4)
 Lembrando-se que |A  B| = |A| + |B| (para conjuntos





disjuntos) e estendendo para os três conjuntos, tem-se
|(A  B)  (B  A)  (A  B)| = |A  B| + |B  A| + |A  B| (i).
Sabe-se que
 |A  B| = |A| - |A  B| e
 |A  B| = |A| - |B|, se B  A (transp. 20).
Usando essas equações em (i), e juntamente com o
resultado do exercício anterior, tem-se
 |A  B| = |A| - |A  B| + |B| - |A  B| + |A  B|
 |A  B| = |A| + |B| - |A  B|
(ii).
A equação (ii) ilustra o princípio. Ele surge do fato de que ao
contar o número de elementos na união de A e B, deve-se
incluir o números de elementos de A e B e excluir os
elementos comuns de A e B (para evitar contá-los
novamente).
Se A e B são disjuntos, |A  B| vale ?
Matemática Discreta 2
Aula 3 - 40/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (5)
 Exemplo
14: Um pesquisador de opinião pública
entrevistou 35 eleitores, todos apoiando o referendo 1, o
referendo 2 ou ambos, e descobriu que 14 eleitores
apóiam o referendo 1 e 26 apóiam o referendo 2. Quanto
eleitores apóiam ambos?
 Seja A como o conjunto de eleitores que apóiam o





referendo 1 e B o conjunto dos eleitores que apóiam o
referendo 2.
Sabe-se que |A  B| = 35, |A| =14 e |B| =26.
Lembrando da equação abaixo,
 |A  B| = |A| + |B| - |A  B|
Tem-se então que
|A  B| = |A| + |B| - |A  B|
|A  B| = 14 + 26 - 35 = 5 eleitores.
Matemática Discreta 2
Aula 3 - 41/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (6)
 Exercício 5 –
 Calcule o resultado da equação |A  B  C|. Lembrar que
|A  B| = |A| + |B| - |A  B|.
Matemática Discreta 2
Aula 3 - 42/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (7)
 Exercício 5 –
 Calcule o resultado da equação |A  B  C|. Lembrar que
|A  B| = |A| + |B| - |A  B|.
 Resposta:
Matemática Discreta 2
Aula 3 - 43/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (8)
 Exercício 5 –
 Calcule o resultado da equação |A  B  C|. Lembrar que
|A  B| = |A| + |B| - |A  B|.
 Resposta:
 Pode-se usar um argumento geométrico para o resultado
da equação acima, conforme mostrado na figura abaixo.
Quando se soma |A| + |B| + |C|,
conta-se cada elemento em |AB|,
|AC| e |BC| duas vezes, de modo
que se deve retirar cada um deles
uma vez.
Nessa mesma soma, se conta cada
elemento em |ABC| três vezes,
mas ao se subtrair as interseções
anteriores, elimina-se três vezes
esses elementos, logo deve-se
colocá-los de volta uma vez,
somando |ABC| ao final.
Matemática Discreta 2
Aula 3 - 44/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (9)
 Exercício 5 –
 Calcule o resultado da equação |A  B  C|. Lembrar que
|A  B| = |A| + |B| - |A  B|.
 Resposta:
 A = {1,3,4}; B = {1,3,5}; C = {1,4,5}.
 A  B = {1,3}; A  C = {1,4}; B  C = {1,5}.
 A  B  C = {1}.
3
4
Matemática Discreta 2
1
5
Aula 3 - 45/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (10)
 Exercício 6: Um grupo de estudantes do curso de ADS
do IFSP de Caraguatatuba está planejando fazer uma
festa e encomendar pizzas. Se 13 alunos comem pizza
que contém calabresa como um dos ingredientes, 10
comem pizza que contém salame como um dos
ingredientes, 12 comem pizza que contém catupiry como
um dos ingredientes, 4 comem pizza de calabresa e
salame, 5 comem pizza de salame e catupiry, 7 comem
pizza de calabresa e catupiry e 3 comem pizza que
contenham os três ingrediente, quantos estudantes tem o
grupo?
Matemática Discreta 2
Aula 3 - 46/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (11)
 Resposta:
 Sejam:
 A = {estudantes que comem pizza que tem calabresa como
um dos ingredientes}
 B = {estudantes que comem pizza que tem salame como um
dos ingredientes}
 C = {estudantes que comem pizza que tem catupiry como um
dos ingredientes}
 Logo,
 |A| = 13; |B| = 10; |C| = 12; |A  B| = 4; |B  C| = 5;
|A  C| = 7 e |A  B  C| = 3.
 |A  B  C| = 13 + 10 + 12 – 4 – 5 – 7 + 3 = 22.
Matemática Discreta 2
Aula 3 - 47/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (12)
 O Exercício 6 também pode ser resolvido usando-se
diagramas de Venn, conforme apresentado abaixo.
Matemática Discreta 2
Aula 3 - 48/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (13)
 Sabe-se que existem 3 pessoas que estão em A  B  C,
conforme mostrado na figura a.
Matemática Discreta 2
Aula 3 - 49/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (14)
 Sabe-se também o número de pessoas nas interseções
A  B, A  C e B  C, conforme a figura b.
Matemática Discreta 2
Aula 3 - 50/51
©Prof. Lineu Mialaret
Princípio de Inclusão e Exclusão (15)
 Sabe-se também a quantidade de elementos de A, B e C
que não foram identificados (estão fora das interseções),
conforme a figura c.
 O número total de estudantes é obtido somando-se todos
os elementos obtidos.
Matemática Discreta 2
Aula 3 - 51/51
©Prof. Lineu Mialaret