APOSTILA DE MATEMÁTICA DISCRETA - PROF. DANIEL VIAIS NETO

Prévia do material em texto

1 
APOSTILA DE MATEMÁTICA DISCRETA 
PROFESSOR DANIEL VIAIS NETO 
 
1. LÓGICA FORMAL 
 
Proposição (ou declaração) é uma sentença que é verdadeira ou falsa. 
 
Exemplos: 
 
a) Paris fica na França. 
b) 5≤pi . 
c) Dante escreveu os Lusíadas. 
d) 2=x é solução de 42 =x . 
 
Proposição composta é aquela formada pela combinação de duas ou mais proposições. 
 
Conectivos são palavras que se usam para formar novas proposições a partir de outras. 
 
Exemplos: 
 
a) O número 6 é par e o número 8 é um cubo perfeito. 
b) O triângulo ABC é retângulo ou é isósceles. 
c) Se Jorge é engenheiro, então sabe matemática. 
d) Não está chovendo. 
e) O triângulo ABC é equilátero se, e somente se, é retângulo. 
 
Operações Lógicas Básicas: 
 
Expressão Conjunção Disjunção 
 
Condicional 
(implicação) 
Bicondicional 
(equivalência) 
Negação 
Expressão Lógica BA ∧ BA ∨ BA → BA ↔ 'A ou A¬ ou A~ 
Representação A e B A ou B A implica B A se, e só se B não A 
 
Observações: 
 
1. K,, BA são usadas para representar proposições e, por isso, são chamadas letras de proposição. 
2. ↔→∨∧ ,,, são conectivos binários e ' (ou ¬ ) é um conectivo unário. 
 
Tabela-verdade: 
 
A B BA ∧ BA ∨ BA → BA ↔ 'A 
V V V V V V F 
V F F V F F 
F V F V V F V 
F F F F V V 
 
A tabela-verdade de uma proposição composta com n proposições simples contém n2 linhas. 
 
 2 
Expressões comuns em português associadas a diversos conectivos lógicos: 
 
Expressão em Português Conectivo Lógico Expressão Lógica 
e; mas; também; além disso Conjunção 
 BA ∧ 
Ou Disjunção 
 BA ∨ 
Se A, então B. 
A implica B. 
A, logo B. 
A só se B; A somente se B. 
B segue de A. 
A é uma condição suficiente para B; basta A para B. 
B é uma condição necessária para A. 
Condicional 
 BA → 
A se e somente se B. 
A é uma condição necessária e suficiente para B. 
Bicondicional 
(equivalência) 
 BA ↔ 
Não A 
É falso que A.... 
Não é verdade que A... 
Negação 
 'A 
 
Exemplos de negação de uma proposição composta: 
 
Proposição Negação Correta Negação Incorreta 
Vai chover amanhã É falso que vá chover amanhã. 
Não vai chover amanhã. 
 
Pedro é alto e magro É falso que Pedro seja alto e magro. 
Pedro não é alto ou não é magro. 
Pedro é baixo ou gordo. 
Pedro é baixo e gordo. 
Esta proposição é muito forte. 
Pedro não tem ambas as propriedades 
(ser alto e ser magro) mas ainda pode ter uma delas. 
O rio é raso ou está poluído É falso que o rio seja raso ou esteja poluído. 
O rio não é raso nem está poluído. 
O rio é fundo e não está poluído. 
O rio não é raso ou não está poluído. 
Esta é uma proposição muita fraca. 
O rio não ter nenhuma das duas propriedades, não 
deixa de ter apenas uma delas. 
 
Uma cadeia que forma uma expressão válida é denominada uma fórmula bem formulada ou fbf. 
 
Ordem de precedência dos conectivos lógicos: 1. Para conectivos dentro de parênteses, efetua-se as expressões dentro 
dos parênteses mais internos. 2. ´ 3. ∨∧, 4. → 5. ↔ . 
 
Em uma fbf com diversos conectivos, o último a ser aplicado é o conectivo principal. 
 
Exemplo: Fazer a tabela-verdade para a fbf )'(' BABA ∨→∨ . 
 
 
 
 
A B 'B 'BA ∨ BA ∨ )'( BA ∨ )'(' BABA ∨→∨ 
V V F V V F F 
V F V V V F F 
F V F F V F V 
F F V V F V V 
conectivo principal 
 3 
Início da tabela-verdade para 3 letras de proposição: 
 
Exercícios: 
 
1. Quais das frases a seguir são proposições? 
 
a) A lua é feita de queijo verde. b) Ele é, certamente, um homem alto. 
c) Dois é um número primo. d) O jogo vai acabar logo? 
e) Os juros vão subir ano que vem. f) Os juros vão descer ano que vem. 
g) 042 =−x . 
 
2. Determine o valor lógico (V ou F) em cada uma das seguintes proposições: 
 
a) O número 17 é primo. 
b) Fortaleza é capital do Maranhão. 
c) 222 53)53( +=+ 
d) O produto de dois números ímpares é um número ímpar. 
e) Se 10 < então 2 é irracional. 
f) Roma é capital da França ou 145 =otg . 
g) 2021 2 <↔−>− pi . 
h) É falso que 532 =+ e 311 =+ . 
 
3. Sejam as proposições A : Marcos é alto e B : Marcos é elegante. Traduzir para linguagem simbólica. 
 
a) Marcos é alto e elegante. 
b) Marcos é alto, mas não é elegante. 
c) Não é verdade que Marcos é baixo ou elegante. 
d) Marcos não é nem alto e nem elegante. 
e) Marcos é alto ou é baixo e elegante. 
f) É falso que Marcos é baixo ou que não é elegante. 
 
4. Construa a tabela-verdade para as fbfs a seguir: 
 
a) )()( ABBA →↔→ b) )'()'( BBAA ∧→∨ c) )''()( ABBA →↔→ d) ]'')'[( CBA →∧ 
 
5. Sabendo que os valores lógicos das proposições CBA ,, e D são respectivamente V, V, F e F, determinar o valor 
lógico (V ou F) de cada uma das seguintes proposições: 
 
a) )''()( CACA →→→ b) '')'( BABA ∨→∧ c) '')'( DADA ∧→∧ d) ))'()(( CDDA ∨∧∨ 
 4 
Respostas: 
 
1. a), c), e) e f) 
2. a) V b) F c) F d) V e) V f) V g) V h) V 
3. a) BA ∧ b) 'BA ∧ c) )''( BA ∨ d) '' BA ∧ e) )'( BAA ∧∨ f) )'''( BA ∨ 
4. a) V,F,F,V b) F,F,F,F c) V,V,V,V d) F,F,V,F,F,F,F,F 
5. a) V b) V c) F d) V 
 
Uma fbf que assume apenas o valor V é denominada uma tautologia. Uma tautologia é “intrinsecamente verdadeira” 
pela sua própria estrutura; ela é verdadeira independentemente dos valores lógicos atribuídos às suas letras de 
proposição. 
 
Exemplo: “Hoje vai ter sol ou hoje não vai ter sol”. 
 
Uma fbf cujo valor lógico é sempre F é denominada uma contradição. Uma contradição é “intrinsecamente falsa” pela 
sua própria estrutura. 
 
Exemplo: “Hoje é terça-feira e hoje não é terça-feira”. 
 
Sejam P e Q duas fbfs e suponha que a fbf QP ↔ seja uma tautologia. Se fizermos uma tabela-verdade usando as 
letras de proposição P e Q, então os valores lógicos de P e de Q seriam sempre iguais em todas as linhas da tabela. 
Neste caso, dizemos que P e Q são fbfs equivalentes; denotamos essa propriedade por QP ⇔ . Assim, QP ⇔ 
enuncia um fato, a saber, que a fbf particular QP ↔ é uma tautologia. 
 
Exercícios: 
 
1. Determinar quais das seguintes expressões são tautologias e quais são contradições. 
 
a) ')'( AAAA ↔∧↔ b) )'()''( BBAA →∨→ c) )'(' BAA ∧∧ d) )('' BABA →→∨ 
 
2. Demonstrar por tabelas-verdade as seguintes equivalências: 
 
a) ABAA ⇔∧∨ )( b) CBACABA ∧→⇔→∧→ )()( c) '')( BCACBA →∧⇔→→ 
 
Respostas: 
 
1. a) tautologia b) contingência c) contradição d) contingência 
 
Algumas Equivalências Tautológicas 
 
1a. ABBA ∨⇔∨ 1b. ABBA ∧⇔∧ (comutatividade) 
2a. )()( CBACBA ∨∨⇔∨∨ 2b. )()( CBACBA ∧∧⇔∧∧ (associatividade) 
3a. )()()( CABACBA ∨∧∨⇔∧∨ 3b. )()()( CABACBA ∧∨∧⇔∨∧ (distributividade) 
4a. AA ⇔∨ )0( 4b. AA ⇔∧ )1( (elementos neutros) 
5a. 1'⇔∨ AA 5b. 0'⇔∧ AA (complementares) 
 
Obs: representamos qualquer contradição por 0 e qualquer tautologia por 1. 
 
As equivalências na lista estão agrupadas em cinco pares, Em cada par, uma equivalência pode ser obtida da outra 
substituindo ∧ por ∨ , ∨ por ∧ , 0 por 1 e 1 por 0 . Cada equivalência em um dos pares é a dual da outra. 
 
 5 
Leis de De Morgan '')'( BABA ∧⇔∨ e '')'( BABA ∨⇔∧ .Exemplo: Considere uma proposição em um programa de computador da forma 
 
If ((Fluxo_Saída > Fluxo_Entrada) and not (( Fluxo_Saída > Fluxo_Entrada) and (Pressão < 1000))) 
 do Alguma_Coisa; 
else 
 do Outra_Coisa; 
Aqui a expressão condicional tem a forma )'( BAA ∧∧ onde A é “Fluxo_Saída > Fluxo_Entrada” e B é “Pressão < 
1000”. Essa proposição pode ser simplificada substituindo-se uma fbf por outra equivalente. 
 
 )'( BAA ∧∧ = )''( BAA ∨∧ (Leis de De Morgan) 
 = )'()'( BAAA ∧∨∧ (tautologia 3b) 
 = )'(0 BA ∧∨ (tautologia 5b) 
 = 0)'( ∨∧ BA (tautologia 1a) 
 = 'BA ∧ (tautologia 4a) 
 
A proposição pode, então, ser escrita na forma: 
 
If ((Fluxo_Saída > Fluxo_Entrada) and not (Pressão < 1000)) 
 do Alguma_Coisa; 
else 
 do Outra_Coisa; 
 
Um algoritmo é um conjunto de instruções que podem ser executadas mecanicamente em um tempo finito de modo a 
resolver algum problema. 
 
Exercícios: 
 
1. Dados os valores lógicos A é verdadeira, B é falsa e C é verdadeira, qual o valor lógico de cada uma das fbfs a 
seguir? 
 
a) )( CBA ∨∧ b) CBA ∨∧ )( c) CBA ∨∧ )'( d) )''(' CBA ∧∨ 
 
2. Qual o valor lógico de cada uma das proposições a seguir? 
 
a) 8 é par ou 6 é ímpar. b) 8 é par e 6 é ímpar. 
c) 8 é ímpar ou 6 é ímpar. d) 8 é ímpar e 6 é ímpar. 
e) Se 8 for ímpar, então 6 é ímpar. f) Se 8 for par, então 6 é ímpar 
g) Se 8 for ímpar, então 6 é par. h) Se 8 for ímpar e 6 for par, então 8 < 6. 
 
3. São dadas diversas formas de negação para cada uma das proposições a seguir. Quais estão corretas? 
 
a) A resposta é 2 ou 3. b) Pepinos são verdes e têm sementes. 
1. A resposta é nem 2 nem 3. 1. Pepinos não são verdes e não têm sementes. 
2. A resposta não é 2 ou não é 3. 2. Pepinos não são verdes ou não têm sementes. 
3. A resposta não é 2 e não é 3. 3. Pepinos são verdes e não têm sementes. 
 
c) 2 < 7 e 3 é impar. 
1. 2 > 7 e 3 é par. 
2. 2 ≥ 7 e 3 é par. 
3. 2 ≥ 7 ou 3 é ímpar. 
4. 2 ≥ 7 ou 3 é par. 
 6 
4. Escreva a negação de cada fbf a seguir: 
 
a) Se a comida é boa, então o serviço é excelente. 
b) Ou a comida é boa, ou o serviço é excelente. 
c) Ou a comida é boa e o serviço excelente, ou então está caro. 
d) Nem a comida é boa, nem o serviço é excelente. 
e) Se é caro, então a comida é boa e o serviço é excelente. 
 
5. Escreva a negação de cada uma das afirmações a seguir: 
 
a) O processador é rápido, mas a impressora é lenta. 
b) O processador é rápido ou a impressora é lenta. 
c) Se o processador é rápido, então a impressora é lenta. 
d) Ou o processador é rápido e a impressora é lenta, ou então o arquivo está danificado. 
e) Se o arquivo não está danificado e o processador é rápido, então a impressora é lenta. 
f) A impressora só é lenta se o arquivo estiver danificado. 
 
6. Sejam A, B e C as seguintes proposições: 
 
A : Rosas são vermelhas B : Violetas são azuis C : Açúcar é doce 
 
Escreva as proposições compostas a seguir em notação simbólica. 
 
a) Rosas são vermelhas e violetas são azuis. 
b) Rosas são vermelhas e, ou violetas são azuis, ou açúcar é doce. 
c) Sempre que violetas são azuis, rosas são vermelhas e açúcar é doce. 
d) Rosas são vermelhas apenas se violetas não forem azuis ou se açúcar for amargo. 
e) Rosas são vermelhas e, se açúcar for amargo, então violetas não são azuis ou açúcar é doce. 
 
7. Sejam A, B, C e D as seguintes proposições: 
 
A : O bandido é francês B : O herói é americano C : A heroína é inglesa D : O filme é bom 
 
Escreva as proposições compostas a seguir em notação simbólica. 
 
a) O herói é americano e o filme é bom. 
b) Embora o bandido seja francês, o filme é bom. 
c) Se o filme é bom, então o herói é americano ou a heroína é inglesa. 
d) O herói não é americano, mas o bandido é francês. 
e) Uma heroína inglesa é uma condição necessária para o filme ser bom. 
 
8. Escreva cada uma das proposições compostas as seguir em notação simbólica usando letras de proposição para 
denotar as componentes. 
 
a) Se os preços subirem, então haverá muitas casas para vender e elas serão caras; mas se as casas não forem caras, 
então, ainda assim, haverá muitas casas para vender. 
 
b) Tanto ir dormir quanto ir nadar é uma condição suficiente para a troca de roupa; no entanto, mudar a roupa não 
significa que se vai nadar. 
 
c) Vai chover ou vai nevar, mas não ambos. 
 
d) Se Jane vencer ou perder, vai ficar cansada. 
 
e) Ou Jane irá vencer ou, se perder, ela ficará cansada. 
 
 7 
9. Escreva cada uma das proposições compostas as seguir em notação simbólica usando letras de proposição para 
denotar as componentes. 
 
a) Se o cavalo estiver descansado, o cavaleiro vencerá. 
b) O cavaleiro vencerá apenas se o cavalo estiver descansado e a armadura for forte. 
c) Um cavalo descansado é uma condição necessária para o cavaleiro vencer. 
d) O cavaleiro vencerá se, e somente se, a armadura for forte. 
e) Uma condição suficiente para o cavaleiro vencer é que a armadura seja forte ou o cavalo esteja descansado. 
 
10. Escreva cada uma das proposições compostas as seguir em notação simbólica usando letras de proposição para 
denotar as componentes. 
 
a) Se Anita ganhar a eleição, então os impostos serão reduzidos. 
b) Os impostos serão reduzidos somente se Anita ganhar as eleições e a economia permanecer forte. 
c) Os impostos serão reduzidos se a economia permanecer forte. 
d) Uma economia forte virá se Anita ganhar a eleição. 
e) A economia permanecerá forte se, e somente se, Anita ganhar a eleição ou os impostos forem reduzidos. 
 
11. Construa tabelas-verdade para as fbfs a seguir. Note quaisquer tautologias ou contradições. 
 
a) BABA ∨↔→ ')( b) )()( CBACBA ∨∧→∨∧ 
c) )'''( BAA ∨∧ d) 'ABA →∧ 
e) )]()[()( CBCABA ∨→∨→→ f) )( ABA →→ 
g) '' ABBA ∨↔∧ h) )'()'( BABA ∧∧∨ 
i) CACBA ∨→∧∨ '])[( 
 
12. Um chip de memória de um microcomputador tem 24 elementos com dois estados (ligado/desligado). Qual o 
número total de configurações ligado/desligado possíveis? 
 
13. Construa tabelas-verdade para verificar que as fbfs a seguir são tautologias. 
 
a) 'AA ∨ b) AA ↔)''( c) BBA →∧ d) BAA ∨→ 
e) '')'( BABA ∧↔∨ f) '')'( BABA ∨↔∧ g) AAA ↔∨ 
 
Respostas: 
 
1. a) V b) V c) V d) F 2. a) V b) F c) F d) F e) V f) F g) V h) V 3. a) 1, 3 b) 2 c) 4 
4. a) A comida é boa, mas o serviço é ruim. b) A comida é ruim e o serviço também. 
c) A comida é ruim ou o serviço é ruim, e está barato. d) Ou a comida é boa ou o serviço é excelente. 
e) É caro, masa comida é ruim ou o serviço é ruim. 
6. a) BA ∧ b) )( CBA ∨∧ c) )( CAB ∧→ d) )''( CBA ∨→ e) ))'('( CBCA ∨→∧ 
8. a) A : os preços subirem; B : haverá muitas casas; C : casas serão caras. )'(][ BCCBA →∧∧→ 
b) A : ir dormir; B : ir nadar; C : trocar de roupa. )'(])[( BCCBA →∧→∨ 
c) A : vai chover; B : vai nevar. )'()( BABA ∧∧∨ 
d) A : Jane vence; B : Jane perde; C : Jane vai ficar cansada. CBA →∨ )( 
e) A : Jane vence; B : Jane perde; C : Jane vai ficar cansada. )( CBA →∨ 
11. a) V,V,V,V (tautologia) b) V,V,V,V,F,V,F,V c) V, F,F,F 
d) F,V,V,V e) V,V,V,V,V,V,V,V (tautologia) f) V,V,V,V (tautologia) 
g) F,F,F,F (contradição) h) F,V,F,V i) V,V,V,V,V,V,V,V (tautologia) 
12. 162 22
4
= 
 8 
Quantificadores Lógicos: Existem sentenças onde o valor lógico não está bem definido e varia para cada sujeito. 
Assim, estas afirmações não são proposições e sim funções proposicionais (ou sentenças abertas). Os quantificadores 
servem para especificar informações sobre variáveis em funções proposições, transformando-as assim em proposições. 
Exemplos: 0<x ; 96 =+x ; 02 ≥x . 
 
Quantificador Universal – “para todo”; “para qualquer”. O quantificador universal traduz a idéia de abrangência de 
uma proposição a todo um conjunto. O quantificador universal é denotado pelo símbolo ∀ e lido como “para todo”, 
“todo”, “para qualquer”, “qualquer”, “qualquer que seja”. Considerando uma função proposicional qualquer )(xp e 
um conjunto qualquer A , temos a proposição ))()(( xpAx ∈∀ . 
Exemplos: 0, <∈∀ xZx ; 96, =+∈∀ xNx ; 0, 2 ≥∈∀ xRx . 
 
Quantificador Existencial – “existe”; “existe pelo menos um”. O quantificador existencial traduz a idéia de existência 
de condições para a validade de uma proposição em um conjunto. O quantificador existencial é denotado pelo símbolo 
∃ e lido como “existe”, “existe pelo menos um”. Considerando uma função proposicional qualquer )(xp e um 
conjunto qualquer A , temos a proposição ))()(( xpAx ∈∃ . 
Exemplos: 0, <∈∃ xZx ; 96, =+∈∃ xNx ; 0, 2 <∈∃ xRx . 
 
Quantificador Existencial Estrito – “existe um só”; “existe somente um”. O quantificador existencial estrito é uma 
variação do quantificador existencial. Indica a existência de apenas um elemento capaz de tornar a proposição 
verdadeira. O quantificador existencial estrito é denotado pelo símbolo !∃ e tem o significado de “existe apenas um”, 
“existe somente um”, “existe um só”, “existe um único”. Considerando uma função proposicional qualquer )(xp e um 
conjunto qualquer A , temos a proposição ))()(!( xpAx ∈∃ . 
Exemplos: 0,! <∈∃ xZx ; 96,! =+∈∃ xNx ; 0,! 2 ≥∈∃ xRx . 
 
Observação: O conjunto A é dito o domínio de )(xp , e o conjunto pT de todos os elementos de A para os quais 
)(ap é verdadeira é chamado conjunto verdade de )(xp . 
 
Exemplos: *}0,:{
−
=<∈ ZxZxx ; RxRxx =≥∈ }0,:{ 2 ; }3{}96,:{ ==+∈ xNxx 
φ=<∈ }0,:{ 2xRxx . 
 
Negação de Declarações com Quantificadores: 
 
Teorema (De Morgan) 
a) )()()()( xpAxxpAx ¬∈∃⇔∈∀¬ 
b) )()()()( xpAxxpAx ¬∈∀⇔∈∃¬ 
 
 
 
 
 
 
Resumo de Negações das Proposições: 
 
 
 
 
 
 
 9 
Exercícios: 
 
1. Seja { }.5,4,3,2,1=A Determine o valor lógico de cada uma das declarações seguintes: 
a) ( )( )103 =+∈∃ xAx b) ( )( )103 <+∈∀ xAx c) ( )( )53 <+∈∃ xAx d) ( )( )73 ≤+∈∀ xAx 
 
2. Determine o valor lógico de cada uma das declarações seguintes, onde { }3,2,1=U é o conjunto universo: 
a) ;1, 2 +<∀∃ yxyx b) ;12, 22 <+∃∀ yxyx c) .12, 22 <+∀∀ yxyx 
 
3. Negue cada uma das declarações seguintes: 
a) ( );,, yxpyx∀∃ b) ( );,, yxpyx∀∀ c) ( ).,,, zyxpzxy ∀∃∃ 
 
4. Negue cada uma das declarações seguintes: 
 
a) Todos os estudantes moram em dormitórios. 
b) Todos os grandes matemáticos são do sexo masculino. 
c) Alguns estudantes têm 25 anos de idade ou mais. 
 
5. Seja { }.10,9,...,2,1=A Considere cada uma das sentenças seguintes. Se for uma declaração, determine seu valor 
lógico. Se for uma função proposicional, determine seu conjunto verdade. 
 
a) ( )( )( )14<+∈∃∈∀ yxAyAx b) ( )( )14<+∈∀ yxAy 
c) ( )( )( )14<+∈∀∈∀ yxAyAx d) ( )( )14<+∈∃ yxAy 
 
6. Negue cada uma das declarações no exercício 1. 
 
7. Ache um contra-exemplo para cada declaração onde { }9,7,5,3=U é o conjunto universo. 
a) ;73, ≥+∀ xx b) xx,∀ é impar; c) xx,∀ é primo; d) ., xxx =∀ 
 
8. Qual o valor-verdade de cada uma das proposições a seguir na interpretação onde o domínio consiste em inteiros, 
)(xO é “ x é ímpar”, )(xL é “ 10<x ” e )(xG é “ 9>x ”? 
a) ( ) )(xOx∃ b) ( )( ))()( xOxLx →∀ c) ( )( ))()( xGxLx ∧∃ d) ( )( ))()( xGxLx ∨∀ 
 
9. Qual o valor-verdade de cada uma das proposições a seguir na interpretação onde o domínio consiste nos números 
inteiros? 
 
a) ( )( )( )xyxyx =+∃∀ b) ( )( )( )xyxxy =+∀∃ c) ( )( )( )0=+∃∀ yxyx 
d) ( )( )( )0=+∀∃ yxxy e) ( )( )( )xyyxyx <∨<∀∀ f) ( )( )( )yxyx =∃∃ 2 
 
10. Indique o valor-verdade de cada uma das proposições a seguir na interpretação onde o domínio consiste nos estados 
do Brasil, ),( yxQ é “ x é ao norte de y ”, )(xP é “ x é começa com a letra P” e a é “Paraná”. 
 
a) ( ) )(xPx∀ b) ( )( )( )( )),(),(),( zxQzyQyxQzyx →∧∀∀∀ 
c) ( )( ) ),( xyQyx ∃∃ d) ( )( )( )),()( xyQyPyx ∧∃∀ e) ( ) ),( yaQy∃ 
 
Os itens a seguir são questões de múltipla escolha. 
 
 10 
11. (CVM/2000) Dizer que a afirmação “todos os economistas são médicos” é falsa, do ponto de vista lógico, equivale a 
dizer que a seguinte afirmação é verdadeira: 
 
a) pelo menos um economista não é médico. 
b) nenhum economista é médico. 
c) nenhum médico é economista. 
d) pelo menos um médico não é economista. 
e) todos os não médicos são não economistas. 
 
12. (TTN-98 ESAF) Se é verdade que "Alguns A são R" e que "Nenhum G é R", então é necessariamente verdadeiro 
que: 
 
a) algum G é A. 
b) algum A é G. 
c) nenhum A é G. 
d) algum A não é G. 
e) nenhum G é A. 
 
13. (Fiscal Trabalho 98 ESAF) Sabe-se que existe pelo menos um A que é B. Sabe-se, também, que todo B é C. Segue-
se, portanto, necessariamente que 
 
a) todo C é B. 
b) todo C é A. 
c) algum A é C. 
d) nada que não seja C é A. 
e) algum A não é C. 
 
14. (ANPAD_RL_SET_2004) - Se "Alguns profissionais são administradores" e "Todos os administradores são 
pessoas competentes", então, necessariamente, com as proposições apresentadas, pode-se inferir: 
 
a) Nenhum profissional não é competente. 
b) Toda pessoa competente é administradora. 
c) Todo administrador é profissional. 
d) Nenhuma pessoa competente é profissional. 
e) Algum profissional é uma pessoa competente. 
 
15. (SERPRO 2001 ESAF) Todos os alunos de matemática são, também, alunos de inglês, mas nenhum aluno de inglês 
é aluno de história. Todos os alunos de português são também alunos de informática, e alguns alunos de informática são 
também alunos de história. Como nenhum aluno de informática é aluno de inglês, e como nenhum aluno de português é 
aluno de história, então: 
 
a) pelo menos um aluno de português é aluno de inglês. 
b) pelo menos um aluno de matemática é aluno de história. 
c) nenhum aluno de português é aluno de matemática. 
d) todos os alunos de informática são alunos de matemática. 
e) todosos alunos de informática são alunos de português. 
 
16. (AFCE TCU 99 ESAF) Em uma comunidade, todo trabalhador é responsável. Todo artista, se não for filósofo, ou é 
trabalhador ou é poeta. Ora, não há filósofo e não há poeta que não seja responsável. Portanto, tem-se que, 
necessariamente, 
 
a) todo responsável é artista. 
b) todo artista é responsável. 
c) todo responsável é filósofo ou poeta. 
d) algum filósofo é poeta. 
e) algum trabalhador é filósofo. 
 11 
2. INDUÇÃO MATEMÁTICA 
 
Primeiro Princípio da Indução Matemática. 
 
 
Exemplos: 
 
1. Prove que 2)12(531 nn =−++++ L . 
 
1. )1(P é verdadeira, pois 211 = . 
2. Suponha que )(kP seja verdadeira, ou seja, 2)12(531 kk =−++++ L . Mostraremos que )1( +kP é 
verdadeira. 
 )]1)1(2[531 −+++++ kL = ]1)1(2[)12(531 −++−++++ kkL 
 = ]1)1[(22 −++ kk 
 = 122 ++ kk 
 = 
2)1( +k 
 
Portanto, )]1)1(2[531 −+++++ kL = 2)1( +k , o que mostra a validade de )1( +kP , provando assim que 
2)12(531 nn =−++++ L é verdadeira 1≥∀n . 
 
2. Prove que 1,2 ≥∀> nnn 
 
1. )1(P é verdadeira, pois 121 > . 
2. Suponha que )(kP seja verdadeira, ou seja, kk >2 . Mostraremos que )1( +kP é verdadeira. 
 
 1 pois,122.22 1 ≥+≥>=+ kkkkk 
 
Portanto, 12 1 +>+ kk , o que mostra a validade de )1( +kP , provando assim que nn >2 é verdadeira 1≥∀n . 
 
3. Prove que 1,
2
)1(321 ≥∀+=++++ nnnnL . (verifique!) 
 
 
1 1. )1(P é verdade. (passo básico) 
 2. ] verdade)1( verdade)([)( +→∀ kPkPk (passo indutivo) 
)(nP é verdadeiro para todo inteiro positivo n 
 12 
Exercícios: 
 
Nos exercícios de 1 a 12, use indução matemática para provar que as proposições dadas abaixo são verdadeiras para 
todo inteiro positivo n. 
 
1. 22)24(1062 nn =−++++ L 
2. )1(2642 +=++++ nnnL 
3. )12()34(951 −=−++++ nnnL 
4. 
6
)2)(1(
2
)1(631 ++=+++++ nnnnnL 
5. )13()26(16104 +=−++++ nnnL 
6. 
2
)1(5515105 +=++++ nnnL 
7. 
6
)12)(1(21 222 ++=+++ nnnnL 
8. 
4
)1(21
22
333 +
=+++
nn
nL 
9. 
3
)12)(12()12(31 222 +−=−+++ nnnnL 
10. 133.21862 1 −=++++ − nnL 
11. 
13)13)(23(
1
107
1
74
1
41
1
+
=
+−
++
⋅
+
⋅
+
⋅ n
n
nn
L 
12. 1)!1(!!33!22!11 −+=⋅++⋅+⋅+⋅ nnnL 
13. Prove que 3,322 ≥+≥ nnn . 
14. Prove que 2,12 ≥+> nnn . 
15. Prove que 6,1052 >+> nnn . 
16. Prove que 5,2 2 ≥> nnn . 
17. Prove que 4,! 2 ≥> nnn . 
18. Prove que 7,3! ≥> nn n . 
19. Prove que 4,!2 ≥< nnn . 
20. Prove que 1,0,1,
1
11
1
2 ≠≠≥
−
−
=++++
+
aan
a
a
aaa
n
n
L . 
21. Prove que 732 +n é divisível por 1,8 ≥∀n . 
22. Prove que 123 −n é divisível por 1,7 ≥∀n . 
23. Prove que 54.310 2 ++ +nn é divisível por 1,9 ≥∀n . 
24. Prove que nn −3 é divisível por 3 , 1≥∀n . 
25. Prove que nn 23 + é divisível por 3 , 1≥∀n . 
 13 
3. TEORIA DOS CONJUNTOS 
 
Conjunto é uma lista, coleção ou classe de objetos bem definidos. 
 
Exemplos: 
a) Os números 1, 3, 7 e 10. b) As soluções reais da equação 0532 =+− xx . 
c) As vogais do alfabeto. d) Os números ímpares 1, 3, 5, 7, ... 
 
Notações: 
 
• Conjuntos são em geral designados por letras maiúsculas: K,,, CBA 
• O conjunto vazio é representado das seguintes formas }{ ou φ . 
• Se x é um elemento de A , dizemos que x pertence a A e escrevemos Ax ∈ , caso contrário escrevemos 
Ax ∉ . 
 
Exemplos anteriores reescritos: 
a) { }10,7,3,1=A b) { } φ==+−∈= 053/ 2 xxRxB 
c) { }uoieaC ,,,,= d) { }ímpar é / xRxD ∈= 
 
Princípio da extensão. Dois conjuntos, A e B , são iguais se e somente se possuem os mesmos elementos. 
 
Subconjunto. Se todo elemento de um conjunto A é também um elemento de um conjunto B , diz-se que A é 
subconjunto de B . Também dizemos que A está contido em B ou que B contém A . 
 
Notação: BA ⊆ ou BA ⊂ (subconjunto próprio, ou seja, BA ⊆ e BA ≠ ) 
 
Teorema. (i) Para todo conjunto A , temos UA ⊆⊆φ (conjunto universo). 
 (ii) Para todo conjunto A , AA ⊆ . 
 (iii) Se BA ⊆ e CB ⊆ , então CA ⊆ . 
 (iv) BA = se, e somente se, BA ⊆ e AB ⊆ . 
 
Exemplos: 
 
a) { } NBA == e 10,7,3,1 , então BA ⊂ . 
b) { }023/ e }2,1{ 2 =+−∈== xxRxBA , então BA ⊆ . 
c) { }uoieacbaA ,,,,B e },,{ == , então BA ⊄ . 
 
Conjuntos de Conjuntos. Para um conjunto S , podemos formar um novo conjunto cujos elementos são os 
subconjuntos de S . Esse novo conjunto é chamado o conjunto das partes de S e denotado por )(S℘ . 
 
Exemplos: 
 
a) }1,0{=S e { }}1,0{},1{},0{,)( φ=℘ S 
b) },,{ cbaS = e { }ScbcabacbaS },,{},,{},,{},{},{},{,)( φ=℘ 
 
Observação: Se S tem n elementos, então )(S℘ tem n2 elementos. Vale para 0=n ? 
 14 
Operação Binária: o é uma operação binária em um conjunto S se, para todo par ordenado ),( yx de elementos de 
S , yx o existe, é único e pertence a S . 
Operação Unária: ∗ é uma operação unária em um conjunto S se, para todo Sx ∈ , ∗x existe, é único e pertence a 
S . 
 
Exercícios: 
 
1. Quantos conjuntos diferentes estão descritos a seguir? Quais são eles? 
 
}4,3,2{ φ } araraou bola cachorro, de letra primeira a é /{ xx }42,/{ ≤≤∈ xNxx 
 
},4,,3,,2{ cba } arara e bola cachorro, de letra primeira a é /{ xx }2,4,3{ },,{ eba 
 
2. Descreva cada um dos conjuntos a seguir listando seus elementos. 
a) }25,/{ 2 <∈ xNxx b) }112 par, é ,/{ <<∈ xxNxx 
c) }1,/{ 2 −=∈ xRxx d) }Sul Região da estados dos um é /{ xx 
e) }4,/{ <∈ xZxx f) }065,/{ 2 =+−∈ xxNxx 
g) }7,/{ 2 =∈ xRxx h) }082,/{ 2 =−−∈ xxNxx 
i) )}2},3,2{)((,/{ qxqqNxx =∈∃∈ j) )}par )((,/{ yxyyNxx ≠→∀∈ 
k) )}},4,3{},1,0{)()((,/{ zxyzyzyNxx <<∈∈∃∃∈ 
 
3. Dada uma descrição do conjunto A como { } ,8,4,2 K=A , você acha que A∈16 ? 
 
4. Sejam { }501 e / <<∈= xNxxA , { }501 e / <<∈= xRxxB e { }25 e / ≤∈= xZxxC . Quais 
das proposições a seguir são verdadeiras? 
 
a) BA ⊆ b) A∈17 c) CA ⊆ d) C∈− 40 
e) B∈3 f) { } A⊆2,1,0 g) B∈φ h) { } CxZxx ⊆>∈ 625 e / 2 
 
5. Seja { } }20,16,12,10{,5 e / =≥∈= BxNxxA , )}2 e )(/({ yxNyyxC =∈∃= e RD = . Quais 
proposições são verdadeiras? 
 
a) CB ⊆ b) DAB ⊂⊂ c) CA ⊆ d) C∈26 e) { } A⊆13,12,11 
f) { } C⊂13,12,11 g) B∈}12{ h) B⊂}12{ i) DA ⊂⊆5 j) B⊆}{φ 
k) A∉φ l) D∈}}2{{ m) { } De ∈log,,2 pi n) { } BxNxx ⊄<∈ 20 e / 
 
6. Encontre )(S℘ , sendo { }}{,,1 φφ=S . 
 
7. Encontre ))(( S℘℘ , sendo { }baS ,= . 
 
8. O que se pode dizer sobre A se }},{},{},{,{)( babaA φ=℘ 
 
9. Prove que, se BA ⊆ , então )()( BA ℘⊆℘ 
 15 
10. Quais das seguintes operações não são binárias nem unárias nos conjuntos dados? Por que não? 
 
a) *; NSyxyx =÷=o b) *; +=÷= QSyxyx o 
c) RSxyx y == ;od) RSyxmáxyx == );,(o 
e) +∗ == RSxx ; f) RSxxequaçãodasoluçãox === ∗∗ ;)( 2 
g) ZSxx =−=∗ ; h) ZSyxyx =÷= ;o 
i) NSyxyx =−= ;o j) NS
x
x
x =



≤
≥
= ;
5,0
5,1*
 
k) RSxx ==∗ ;ln l) NSxyx =+= ;1o 
m) NSyxyx =−+= ;1o n) ZS
xx
xx
yx =


 −
= ;
par é ,
ímpar é ,1
o 
 
Respostas: 
 
1. 5 4. a) V b) V c) F d) V e) V f) F g) F h) V 8. },{ baA = 
10. Não são operações binárias nem unárias os itens (a), (c), (f), (h), (i), (j), (k), (m). 
 
Diagrama de Venn é uma representação pictórica na qual os conjuntos são representados por áreas delimitadas por 
uma curva no plano. 
 
Operações entre conjuntos 
 
Dado um conjunto arbitrário S , podemos definir algumas operações binárias e unárias no conjunto )(S℘ . S , neste 
caso, é chamado de conjunto universo. O conjunto universo define o contexto dos objetos em discussão. Se ZS = por 
exemplo, então todos seus subconjuntos conterão apenas inteiros. 
 
• União de Conjuntos 
 
Sejam )(, SBA ∈℘ . A união de A e B , denotada por BA ∪ , 
é { }BxAxx ∈∈ ou / . 
 
 
 
 
 
 
 
 
 
• Interseção de Conjuntos 
 
Sejam )(, SBA ∈℘ . A interseção de A e B , denotada por BA ∩ , 
é { }BxAxx ∈∈ e / . 
 
 
 
 
 16 
• Complemento de um Conjunto 
 
Seja )(SA ∈℘ . O complemento de A , 'A é { }AxSxx ∉∈ e / . 
 
• Diferença de Conjuntos 
 
Sejam )(, SBA ∈℘ . A diferença dos conjuntos A e B , denotada por BA − , é { }BxAxx ∉∈ e / . 
 
• Produto Cartesiano 
 
Seja )(, SBA ∈℘ . O produto cartesiano de A e B , denotado por BA× , é { }BAxyx ∈∈ y e /),( . 
 
Exercícios: 
 
1. Trace o diagrama de Venn para três conjuntos não vazios CBA ,, de tal maneira que CBA ,, tenham as 
seguintes propriedades: 
 
a) φ=∩⊂⊂ CABCBA ,, b) φ≠∩⊄⊂ CABCBA ,, 
c) φ=∩≠⊂ CBCACA ,, d) CABCCBCBA ≠≠⊂∩⊂ ,,),( 
 
2. Sejam { } 10,5,3,2,1=A , { }9,8,7,4,2=B , { }10,8,5=C e { }2,1=D subconjuntos de 
{ } 10,9,8,7,6,5,4,3,2,1=S . Encontre: 
 
a) BA ∪ b) CA − c) )'( BA ∩ d) )(' CAB ∪∩ e) DC × 
f) CD × g) 2D g) 3D h) 'S i) SDCBA ∪∪∪∪ 
 
3. Sejam { } { } 9,5,4,1,8,6,5,4,2 == BA e }52 e /{ <≤∈= xZxxC subconjuntos de 
{ } 9,8,7,6,5,4,3,2,1,0=S . Encontre 
 
a) BA ∪ b) BA ∩ c) CA ∩ d) CB ∪ e) BA − f) 'A 
g) 'AA ∩ h) )'( BA ∩ i) BC − j) ')( ABC ∪∩ k) )''( BC ∪ l) CB × 
 
4. Considere os seguintes subconjuntos de Z : 
 
)}3,4 ,)(/({ yxyZyyxA =≥∈∃= 
)}2,)(/({ yxZyyxB =∈∃= 
}10,/{ ≤∈= xZxxC 
 
Usando as operações definidas nos conjuntos, descreva cada um dos conjuntos a seguir em termos de BA, e C . 
 
a) o conjunto de todos os inteiros ímpares b) { } 10,8,6,4,2,0,2,4,6,8,10 −−−−− 
 
c) )}6,2 ,)(/({ yxyZyyx =≥∈∃ d) { } 9,7,5,3,1,1,3,5,7,9 −−−−− 
 
e) )}12,5 ,)(/({)}12,5 ,)(/({ −=−≤∈∃∪+=≥∈∃ yxyZyyxyxyZyyx 
 
 17 
5. Considere os seguintes subconjuntos do conjunto de todos os estudantes: 
 
=A o conjunto de todos os estudantes de ciência da computação 
=B o conjunto de todos os estudantes de física 
=C o conjunto de todos os estudantes de ciência de matemática 
=D o conjunto de todas as estudantes mulheres 
 
Usando as operações definidas nos conjuntos, descreva cada um dos conjuntos a seguir em termos de CBA ,, e D . 
 
a) O conjunto de todos os estudantes que não são de matemática. 
b) O conjunto de todas as mulheres estudantes de física. 
c) O conjunto de todos os estudantes que pretendem se formar, ao mesmo tempo, em ciência da computação e em física. 
d) O conjunto de todos os homens estudantes de ciência da computação. 
e) O conjunto de todos os homens que não são estudantes de física. 
f) O conjunto de todos os estudantes de matemática que não são de ciência da computação. 
g) O conjunto de todos os estudantes que são mulheres ou que estudam ciência da computação. 
 
6. Escreva uma expressão com conjuntos para o resultado de uma busca na rede sobre páginas a respeito de cães que 
não são de caça. Suponha que =D conjunto de páginas sobre cães e =R conjunto de páginas sobre cães de caça. 
 
Respostas: 
 
2. a) { } 9,8,7,5,4,3,2,1 b) { } 3,2,1 c) { } 10,9,8,7,6,5,4,3,1 d) { } 10,5,3,1 
e) { } )2,10(),2,8(),2,5(),1,10(),1,8(),1,5( f) { } )10,2(),8,2(),5,2(),10,1(),8,1(),5,1( 
g) { } )2,2(),1,2(),2,1(),1,1( h) { } )2,2,2(),1,2,2(),2,1,2(),1,1,2(),2,2,1(),1,2,1(),2,1,1(),1,1,1( 
i) φ j) S 4. a) ´B b) CB ∩ c) BA ∩ d) CB ∩' e) ´' CB ∩ 
5. a) ´C b) DB ∩ c) BA ∩ d) ´DA ∩ e) ´´ DB ∩ f) AC − g) DA ∪ 
 
Identidades básicas envolvendo conjuntos 
 
1a. ABBA ∪=∪ 1b. ABBA ∩=∩ (comutatividade) 
2a. )()( CBACBA ∪∪=∪∪ 2b. )()( CBACBA ∩∩=∩∩ (associatividade) 
3a. )()()( CABACBA ∪∩∪=∩∪ 3b. )()()( CABACBA ∩∪∩=∪∩ (distributividade) 
4a. AA =∪φ 4b. ASA =∩ (elementos neutros) 
5a. SAA =∪ ' 5b. φ=∩ 'AA (complementares) 
 
Propriedade de De Morgan 
 
Sejam A e B dois conjuntos quaisquer. Então '')'( BABA ∩=∪ e '')'( BABA ∪=∩ . 
 
Partições. Seja S um conjunto não vazio. Uma partição de S é uma subdivisão de S em conjuntos não vazios 
disjuntos. 
 
Exemplo: Seja { } 9,8,7,6,5,4,3,2,1=S . 
 
a) [ ]}9,8,4{},6,2{},5,3,1{1 =P não é partição de S . 
b) [ ]}9,7,5{},8,6,4,2{},5,3,1{2 =P não é partição de S . 
c) [ ]}9,7{},8,6,4,2{},5,3,1{3 =P é uma partição de S . 
 18 
Conjuntos Contáveis e Não-Contáveis 
 
Exemplos de conjuntos contáveis (ou enumeráveis): 
a) { } 10,5,3,2,1 b) { } ,...5,4,3,2,1,0=N c) }0 e ,, com ,;{ ≠∈== nnm
n
m
xxQ Z 
Exemplos de conjuntos não-contáveis (ou não-enumeráveis): 
a) R b) ]1,0[ c) conjunto dos números irracionais 
 
Exercícios: 
 
1. Considere os seguintes dados sobre 120 estudantes universitários no que diz respeito aos idiomas francês, alemão e 
russo. 
 
• 65 estudam francês 
• 45 estudam alemão 
• 42 estudam russo 
• 20 estudam francês e alemão 
• 25 estudam francês e russo 
• 15 estudam alemão e russo 
• 8 estudam os três idiomas 
 
Faça um diagrama de Venn com o número correto de estudantes em cada região. 
 
2. Seja { } 9,8,7,6,5,4,3,2,1=X . Determine se cada um dos itens abaixo é ou não uma partição de X . 
 
a) [ ]}9,7,5{},8,2{},6,3,1{ b) [ ]}6,5,3{},9,8,4,2{},7,5,1{ 
c) [ ]}7,6,3{},9,1{},8,5,4,2{ d) [ ]}9,8,6,4{},5,3{},7,2,1{ 
 
3. Seja { } }}}{{{}},{{},{, φφφφ=X . Determine se cada um dos itens abaixo é ou não uma partição de X . 
 
a) [ ]}}}}{{{},{{}},{{},{ φφφφ b) [ ]}}}}{{{{},},{{}}},{{{ φφφφ 
c) [ ]}}}{{,{}}}},{{{},{{ φφφφ d) [ ]}}}{{,{}}}},{{{{},{ φφφφ4. O programa QUAD encontra e imprime soluções de equações quadráticas da forma 02 =++ cbxax . O programa 
PAR lista todos os inteiros pares de n2− a n2 . Denote por Q o conjunto dos valores de saída de QUAD e por P o 
conjunto dos valores de saída de PAR. 
 
a) Mostre que, para 24,2,1 −=−== cba e PQn ⊆= ,50 . 
b) Mostre que, para os mesmos valores de ba, e c , mas para PQn ⊄= ,2 . 
 
5. Quais das proposições a seguir são verdadeiras para todos os conjuntos BA, e C ? 
 
a) Se BA ⊆ e AB ⊆ , então BA = b) φφ =}{ c) }0{}{ =φ d) }{φφ ∈ 
e) A⊆φ f) A∈φ g) }}{{}{ φφ = h) Se BA ⊂ e CB ⊆ , então CA ⊂ 
i) Se BA ≠ e CB ≠ , então CA ≠ j) Se BA ∈ e CB ⊄ , então CA ∉ 
 
Respostas: 
 
2. É partição: (c) e (d) 3. É partição: (b) e (c) 5. a) V b) F c) F d) V e) V f) F g) F h) V i) F j) F 
 19 
4. ANÁLISE COMBINATÓRIA 
 
A combinatória é o ramo da matemática que trata de contagem. Problemas de contagem são importantes sempre que 
temos recursos finitos (Quanto espaço de armazenamento um determinado banco de dados usa? Quantos usuários uma 
determinada configuração de computador pode suportar?) ou quando estamos interessados em eficiência (Quantos 
cálculos são efetuados por um determinado algoritmo?). 
 
Exemplo: A uma criança é permitido escolher um dentre dois confeitos, um vermelho e outro preto, e um entre três 
chicletes, amarelo, lilás e branco. Quantos conjuntos diferentes de doces a criança pode ter? 
 
A árvore abaixo mostra que existem 2 x 3 = 6 escolhas possíveis. São elas: {V, A}, {V, L}, {V, B}, {P, A}, {P, L} e 
{P, B}. 
 
 
 
Neste problema, a seqüência de eventos pode ser invertida; a criança pode escolher o chiclete antes de escolher o 
confeito, resultando na árvore abaixo, mas o número de escolhas possíveis permanece o mesmo (3 x 2 = 6). 
 
 
 
O Exemplo acima mostra que o número de possibilidades para eventos seqüenciados pode ser obtido por meio da 
multiplicação dos números de possibilidades do primeiro evento pelo número de possibilidades do segundo. Esta idéia é 
sintetizada no Princípio da Multiplicação. 
 
 
Princípio da Multiplicação: Se existem 1n resultados possíveis para um primeiro evento e 2n para um segundo, então 
existem 21 nn ⋅ resultados possíveis para a seqüência dos dois eventos. 
 
Exercícios: 
 
1. A última parte do número de seu telefone contém quatro dígitos. Quantos números de quatro dígitos existem? 
2. Se não fosse permitido ter repetições de dígitos, quantos números de quatro dígitos existem? 
3. De quantas maneiras podemos escolher três funcionários de um grupo de 25 pessoas? 
4. De quantas maneiras podemos escolher três funcionários de um grupo de 25 pessoas, se uma pessoa puder acumular 
mais de um cargo? 
5. Se um homem tem quatro ternos, oito camisas e cinco gravatas, quantas combinações ele pode compor? 
 
Proposição: Para todo conjunto finito S , denote por )(Sn o número de elementos de S . Se A e B são finitos, 
então )(.)()( BnAnBAn =× 
 
 20 
Exemplo: Suponha que desejamos escolher uma sobremesa dentre três tortas e quatro bolos. De quantas formas isto 
pode ser feito? 
 
Existem dois eventos, um com três resultados possíveis (escolher uma torta) e outro com quatro resultados possíveis 
(escolher um bolo). No entanto, não estamos compondo uma seqüência de dois eventos, uma vez que desejamos apenas 
uma sobremesa, que precisa ser escolhida dentre as possibilidades de dois conjuntos disjuntos. O número de 
possibilidades é o número total de opções que temos, 3 + 4 = 7. Isto ilustra o Princípio da Adição. 
 
Princípio da Adição: Se A e B são eventos disjuntos com 1n e 2n resultados possíveis, respectivamente, então o 
número total de possibilidades para o evento “ A ou B ” é 21 nn + . 
 
Proposição: Sejam A e B conjuntos finitos disjuntos. Então )()()( BnAnBAn +=∪ . 
 
Exercícios: 
 
1. Um comprador deseja comprar um veículo de uma concessionária. A concessionária tem 23 carros e 14 caminhões 
em estoque. Quantas possíveis escolhas o comprador pode ter? 
2. Um comprador desejar comprar um veículo de uma concessionária que tenha 23 carros, 14 caminhões e 17 veículos 
vermelhos. Quantas possíveis escolhas o comprador pode ter? 
3. Quantos números de quatro dígitos começam com 4 ou 5? 
4. Se uma mulher tem sete blusas, cinco saias e nove vestidos, com quantas combinações diferentes ela pode se vestir? 
5. Quantos inteiros de três dígitos (números entre 100 e 999) são pares? 
6. Suponha que os quatro últimos dígitos de um número de telefone precisam incluir, pelo menos, um dígito repetido. 
Quantos números deste tipo existem? 
 
Árvores como as mostradas nas Figuras acima ilustram o número de possibilidades de um evento baseado em uma série 
de opções possíveis. Tais árvores são chamadas árvores de decisão. Vejamos um exemplo em que a árvore de decisão 
é usada para resolver um problema de contagem onde o Princípio da Multiplicação não se aplica. 
 
Exemplo: Tony está jogando "cara ou coroa". Cada lançamento resulta em cara (C) ou coroa (K). De quantas formas ele 
pode lançar a moeda cinco vezes sem obter duas caras consecutivas? 
 
 
A Figura acima mostra a árvore de decisão para este problema. Cada lançamento de moeda tem duas possibilidades: o 
ramo à esquerda está marcado com um C para cara, e o ramo da direita com um K para coroa. Sempre que um C 
aparecer em um ramo, o próximo nível pode conter apenas um ramo para a direita (K). Existem 13 possibilidades. 
 
 21 
Exercício: Desenhe a árvore de decisões para o número de cadeias de caracteres com X's, Y's e Z's com tamanho 3 que 
não contenham um Z imediatamente após um Y. 
 
Exercícios: 
 
1. Uma loja de iogurte congelado permite escolher um sabor (baunilha, morango, limão, cereja ou pêssego), um 
acompanhamento (raspas de chocolate, jujuba ou castanha de caju) e uma calda (creme batido ou coco ralado). Quantas 
sobremesas diferentes são possíveis? 
2. No Exercício 1, por quantas escolhas de sobremesa podemos optar, se formos alérgicos a chocolate e a morangos? 
3. Começa-se um jogo de computador fazendo uma seleção em cada um dos três menus. O primeiro menu (número de 
jogadores) tem quatro opções, o segundo menu (nível de dificuldade do jogo) tem oito, e o terceiro menu (velocidade) 
tem seis. Quantas configurações possíveis têm o jogo? 
4. Um exame de múltipla escolha tem 20 perguntas, cada uma com quatro respostas possíveis, e 10 perguntas 
adicionais, cada uma com cinco respostas possíveis. Quantas formas diferentes de respostas são possíveis? 
5. Uma senha de usuário para acessar um sistema computacional consiste em três letras seguidas de dois dígitos. 
Quantas senhas diferentes existem (considere o alfabeto com 26 letras)? 
6. No sistema computacional do Exercício 5, quantas senhas existem se for possível distinguir entre letras maiúsculas e 
minúsculas? 
7. Uma conferência telefônica está acontecendo de Metrópolis para a Vila dos Previlégios, via Vale do Trevo. Existem 
45 troncos telefônicos de Metróplolis para o Vale do Trevo e 13 do Vale do Trevo para a Vila dos Previlégios. De 
quantas maneiras diferentes é possível fazer esta ligação? 
8. A, B, C e D são nós em uma rede de computadores. Existem dois caminhos entre A e C, dois entre B e D, três entre A 
e B e quatro entre C e D. Por quantas rotas diferentes é possível mandar uma mensagem de A para D? 
9. Um prédio comprou um novo sistema de fechaduras para seus 175 apartamentos. Uma fechadura é aberta digitando-
se um código numérico de dois algarismos. O síndico do edifício fez uma compra inteligente? 
10. Um palíndromo é uma cadeia de caracteres que é lida da mesma forma normalmente ou de trás para frente. 
Quantos palíndromos de cinco letras são possíveisna língua portuguesa? 
11. Quantos números de três dígitos menores que 600 podem ser formados usando-se os algarismos 8, 6, 4 e 2? 
12. Um conectivo lógico binário pode ser definido através da sua tabela-verdade. Quantos conectivos lógicos binários 
existem? 
13. Na linguagem de programação BASIC original, um identificador tem que ser uma única letra simples ou uma letra 
seguida de um único dígito. Quantos identificadores podemos formar? 
14. Três cadeiras na Câmara Municipal devem ser preenchidas com pessoas de partidos diferentes. Para pleitear essas 
vagas, existem quatro candidatos do Partido dos Ambientalistas Preocupados, três do Partido da Implementação de 
Regras para a Construção e dois do Partido dos Amigos da Salamandra Aquática. De quantas maneiras diferentes essas 
vagas podem ser preenchidas? 
15. Um presidente e um vice-presidente precisam ser escolhidos para a diretoria de uma organização. Existem 17 
voluntários da Região Leste e 24 voluntários da Região Sul. Se ambos os devem pertencer à mesma região, de quantas 
maneiras diferentes esses funcionários podem ser selecionados? 
16. Uma promoção especial de jantar especial permite que você escolha entre cinco entradas, três saladas, quatro pratos 
principais e três bebidas. Quantos jantares diferentes são possíveis? 
17. No Exercício 16, quantos jantares diferentes são possíveis, se você pode escolher uma entrada ou uma salada, mas 
não ambos? 
18. Pode-se encomendar um carro novo com as seguintes opções de escolha: 10 cores externas; sete cores internas; 
transmissão automática ou transmissão mecânica de 5 marchas; com ou sem ar condicionado; com ou sem direção 
hidráulica; com ou sem o pacote adicional que incluem as travas elétricas das portas e o desembaçador traseiro. Quantos 
carros diferentes podem ser encomendados? 
19. No Exercício 18, quantos carros diferentes podem ser encomendados se o pacote opcional só pode ser colocado em 
um carro com transmissão automática? 
20. Em um determinado estado americano, as placas dos carros começam com dois dígitos (o primeiro não pode ser 
zero), seguidos de uma letra (incluindo K, W e Y), seguidos de uma cadeia de dois a quatro dígitos (qualquer um 
podendo ser zero). Quantas placas diferentes são possíveis? 
21. Um cliente de uma lanchonete pode pedir um hambúrguer com ou sem mostarda, ketchup, picles ou cebola; pode 
pedir um sanduíche de atum com ou sem alface, tomate ou molho tártaro; e pode escolher entre três tipos de 
refrigerantes ou dois tipos de milk-shakes. Quantos pedidos diferentes podem ser feitos supondo que um cliente possa 
pedir, no máximo, um hambúrguer, um sanduíche de atum e uma bebida, mas possa pedir menos coisas? 
 22 
22. Qual o valor da variável Contagem após a execução do pseudocódigo a seguir? 
 
Contagem = 0 
para i = 1 até 5 faça 
 para Letra = 'A' até 'C' faça 
 Contagem := Contagem + 1 
 fim do para 
fim do para 
 
23. Qual o valor da variável Resultado após a execução do pseudocódigo a seguir? 
 
Resultado = 0; 
para Índice = 20 diminuindo até 10 faça 
 para Interno = 5 até 10 faça 
 Resultado = Resultado + 2 
 fim do para 
fim do para 
 
Os Exercícios de 24 a 30 referem-se ao conjunto dos inteiros com três dígitos (números entre 100 e 999, inclusive). 
 
24. Quantos são divisíveis por 2? 
25. Quantos são divisíveis por 5? 
26. Quantos não são divisíveis por 5? 
27. Quantos são divisíveis por 4? 
28. Quantos são divisíveis por 4 ou 5? 
29. Quantos são divisíveis por 4 e 5? 
30. Quantos não são divisíveis por 4 nem por 5? 
 
Os Exercícios de 31 a 40 referem-se ao conjunto das cadeias binárias de comprimento 8 (cada caractere é 0 ou 1). 
 
31. Quantas cadeias deste tipo existem? 
32. Quantas começam e terminam por 0? 
33. Quantas começam ou terminam por 0? 
34. Quantas têm o segundo dígito igual a 1? 
35. Quantas começam por 111? 
36. Quantas contêm exatamente um 0? 
37. Quantas começam por 10 e têm 0 como terceiro dígito? 
38. Quantas são palíndromos? (Veja o Exercício 10.) 
39. Quantas contêm exatamente sete caracteres iguais a 1? 
40. Quantas contêm dois ou mais caracteres iguais a 0? 
 
Nos Exercícios 41 a 50, cada mão consiste em duas cartas retiradas de dois baralhos de 52 cartas, um com flores no 
verso e o outro com aves no verso. 
 
41. Quantas mãos diferentes são possíveis? 
42. Quantas mãos consistem em um par de ases? 
43. Quantas mãos contêm apenas figuras? 
44. Quantas mãos contêm duas cartas do mesmo tipo? 
45. Quantas mãos contêm exatamente um rei? 
46. Quantas mãos têm o valor total de 5 (considere o ás como 1)? 
47. Quantas mãos têm o valor total menor que 5? 
48. Quantas mãos não contêm nenhuma figura? 
49. Quantas mãos contêm pelo menos uma figura? 
50. Quantas mãos contêm pelo menos um rei? 
 
 23 
51. Uma determinada votação é feita com cada pessoa colocando um pedaço de papel verde, amarelo ou preto em um 
chapéu. Os papéis são retirados um a um, e a primeira cor que recebe dois votos ganha. Desenhe uma árvore de decisão 
para encontrar o número de maneiras em que se pode desenvolver essa votação. 
52. Desenhe uma árvore de decisão (use os times A e B) para encontrar o número de maneiras em que as partidas da 
NBA podem ocorrer, onde o vencedor é o primeiro time a vencer 4 entre 7 partidas. 
 
Respostas: 
1. 30 2. 16 3. 192 4. 102054 5. 1.757.600 6. 14.060.800 7. 585 8. 14 9. Não 10. 17.576 
11. 32 12. 16 13. 286 14. 24 15. 824 16. 180 17. 96 18. 1120 19. 840 20. 25.974.000 
21. 917 22. 15 23. 132 24. 450 25. 180 26. 720 27. 225 28. 360 29. 45 30. 540 
31. 256 32. 64 33. 192 34. 128 35. 32 36. 8 37. 32 38. 16 39. 8 40. 247 
41. 2704 42. 16 43. 144 44. 208 45. 384 46. 64 47. 96 48. 1600 49. 1104 50. 400 
51. 
 
 
 
Permutação 
 
Considerando o problema de contagem de todas as possibilidades para os quatro últimos dígitos de um número de 
telefone sem dígitos repetidos, o número 1259 não é igual ao número 2951 , já que a ordem dos quatro dígitos é 
importante. Um arranjo ordenado de objetos é chamado de permutação. Cada um desses números é uma permutação 
de 4 objetos distintos escolhidos de um conjunto de 10 objetos distintos (os dígitos). Quantas dessas permutações 
existem? A resposta encontrada pelo Princípio da Multiplicação, é 7.8.9.10 . O número de permutações de r objetos 
distintos escolhidos entre n objetos distintos é denotado por ),( rnP . Portanto, a solução do problema dos números de 
quatro dígitos sem repetição pode ser expressa como )4,10(P . 
 
Uma fórmula para ),( rnP pode ser escrita usando a função fatorial. Para um inteiro positivo n , n fatorial é definido 
como 1)...2)(1( −− nnn e denotado por !n ; além disso, !0 é definido como tendo valor 1 Da definição de !n , 
temos: 
 
 
 
Exercícios: 
 
1. Quantas palavras de três letras (não necessariamente com sentido) podem ser formadas a partir da palavra 
COMPILAR se nenhuma letra pode ser repetida? 
2. Dez atletas competem em um evento olímpico. São dadas medalhas de ouro, prata e bronze. De quantas maneiras 
podem ser dadas as medalhas? 
3. De quantas maneiras pode-se selecionar um presidente e um vice-presidente dentre um grupo de 20 pessoas? 
4. De quantas maneiras seis pessoas podem se sentar em uma fileira de seis cadeiras? 
5. Uma biblioteca tem quatro livros sobre sistemas operacionais, sete sobre programação e três sobre estrutura de dados. 
De quantas maneiras esses livros podem ser arrumados em uma prateleira, considerando que todos os livros de cada 
assunto precisam estar juntos? 
nr
rn
n
rnP ≤≤
−
= 0,)!(!),(
 24 
 
Combinação 
 
Algumas vezes queremos selecionar r objetos de um conjunto de n objetos, mas não nos importamos com a ordem. 
Neste caso estamos contando o número de combinações de r objetos distintos escolhidos entre n objetos distintos, 
que denotamos por ),( rnC . Para cada uma dessas combinações, existem !r maneiras de ordenar os r objetos 
escolhidos. Pelo Princípio da Multiplicação, o número de permutações de r objetos distintos escolhidos entre n 
objetos é o produto do número de escolhas possíveis dos objetos, ),( rnC , pelo número de maneiras de ordenar os 
objetos escolhidos, !r . Logo, 
!
),(),(),(!),(
r
rnP
rnCrnPrrnC =⇒=⋅ 
ou 
 
 
Outras notações usadas para ),( rnC são nrC e 





r
n
. 
Exercícios: 
 
1. Quantas mãos de pôquer com 5 cartas cada, podem ser distribuídas com um baralho de 52 cartas? 
2. De quantas maneiras é possível escolher uma comissão de 3 pessoas em um grupo de 12? 
3. Uma comissão de 8 alunos deve ser escolhida em um grupo contendo 19 alunos do primeiro ano e 34 alunos do 
segundo ano. 
a) De quantas maneiras é possível selecionar 3 alunos do primeiro ano e 5 do segundo? 
b) De quantas maneiras é possível selecionar uma comissão contendo exatamente 1 aluno do primeiro ano? 
c) De quantas maneiras é possível selecionar uma comissão contendo no máximo 1 aluno do primeiro ano? 
d) De quantas maneiras é possível selecionar uma comissão contendo pelo menos 1 aluno do primeiro ano? 
 
Eliminação de Duplicatas 
 
Exercícios: 
 
1. Uma comissão com dois elementos, contendo necessariamente um aluno de matemática, vai ser escolhida entre 
quatro alunos de matemática e três de física. Calcule: 
 
a) )2,3()2,7( CC − 
b) )1,6()1,4( CC ⋅ 
 
Qual valor representa o número de comissões que podemos formar? 
 
Se temos n objetos dos quais um conjunto de 1n são indistinguíveis entre si, um outro conjunto 2n são indistinguíveis 
entre si, e assim por diante, até um conjunto de kn objetos que são indistinguíveis entre si, então o número de 
permutações distintas desses n objetos é: )!)...(!)(!(
!
21 knnn
n
. 
 
2. Quantas permutações distintas podem ser feitas com os caracteres que formam a palavra FLÓRIDA? 
3. Quantas permutações distintas podem ser feitas com os caracteres que formam a palavra MISSISSIPI? 
4. Quantas permutações distintas existem dos caracteres na palavra MONOFÁSICOS? 
 
nr
rnr
n
rnC ≤≤
−
= 0,)!(!
!),(
 25 
Permutações e Combinações com Repetições 
 
Nossas fórmulas para ),( rnP e ),( rnC supõem que arrumamos ou selecionamos r objetos entre os n disponíveis 
usando cada objeto apenas uma vez. Portanto, nr ≤ . Suponha, entretanto, que os n objetos estão disponíveis para 
serem usados quantas vezes quisermos. Por exemplo, construímos palavras usando as 26 letras do nosso alfabeto; as 
palavras podem ser tão longas quanto quisermos, com as letras usadas repetidamente. 
 
Exercícios: 
 
1. Uma moeda será lançada 6 vezes e a cada vez será anotado o resultado obtido, cara ou coroa, formando assim uma 
sequência de 6 resultados. Quantas sequências diferentes podem ser formadas? 
2. Um joalheiro, ao projetar um broche, decidiu usar cinco pedras escolhidas entre diamantes, rubis e esmeraldas. De 
quantas maneiras diferentes podem ser escolhidas as pedras? 
3. Seis crianças escolhem um pirulito cada entre pirulitos vermelhos, amarelos e verdes. De quantas maneiras isso pode 
ser feito? (Não interessa qual criança pega qual pirulito.) 
 
Fórmula: )!1(!
)!1(),1(
−
−+
=−+
nr
nr
rnrC . 
Exercícios: 
 
1. Calcule o valor das expressões a seguir: 
 
a) )2,7(P b) )5,8(P c) )4,6(P d) )1,(nP e) )1,( −nnP 
 
2. De quantas maneiras diferentes podemos ordenar 9 objetos? 
3. Os 14 times locais de futebol júnior estão listados no jornal. Quantas listas são possíveis? 
4. Quantas permutações das letras na palavra COMPUTAR existem? Quantas delas terminam com uma vogal? 
5. Quantas permutações diferentes dos caracteres na palavra ERRO existem? 
6. De quantas maneiras seis pessoas podem se sentar em um círculo formado por seis cadeiras? (Podem-se distinguir 
apenas posições relativas no círculo) 
7. De quantas maneiras pode-se dar o primeiro, segundo e terceiro prêmios em uma competição culinária de tortas da 
qual participam 15 pessoas? 
8. a) Os nomes que representam as ações nos pregões de uma bolsa estão limitados a três letras. Quantos nomes 
possíveis existem? 
 b) Quantos nomes diferentes existem se as letras não podem ser repetidas? 
9. De quantas maneiras diferentes você pode sentar 11 homens e 8 mulheres em uma fila? 
10. De quantas maneiras diferentes você pode sentar 11 homens e 8 mulheres em uma fila se os homens sentam todos 
juntos e as mulheres também? 
11. Calcule o valor das expressões a seguir: 
 
a) )7,10(C b) )2,9(C c) )6,8(C d) )1,( −nnC 
 
12. Explique por que )1,()1,( nCnnC =− . 
13. O controle de qualidade quer verificar 25 processadores dos 300 produzidos por dia. De quantas maneiras isto pode 
ser feito? 
14. Um time de futebol tem 18 jogadores entre titulares (11) e reservas. De quantas maneiras pode-se escolher o time 
titular? 
15. De quantas maneiras pode-se selecionar um júri de 5 homens e 7 mulheres em um conjunto de 17 homens e 23 
mulheres? 
16. De quantas maneiras uma bibliotecária pode selecionar 4 romances e 3 peças teatrais em uma coleção de 21 
romances e 11 peças? 
 
 26 
Os Exercícios 17 a 20 tratam da seguinte situação: entre os funcionários de uma companhia, 7 trabalham em projeto, 14 
em produção, 4 em testes, 5 em vendas, 2 em contabilidade e 3 em marketing. Deve-se formar uma comissão de seis 
pessoas para se encontrar com a diretoria. 
 
17. De quantas maneiras pode-se formar uma comissão se deve haver um membro de cada departamento? 
18. De quantas maneiras pode-se formar uma comissão se deve haver exatamente duas pessoas da área de produção? 
19. De quantas maneiras pode-se formar uma comissão se o departamento de contabilidade não deve ser representado e 
o do marketing deve ter exatamente um representante? 
20. De quantas maneiras pode-se formar uma comissão se a produção deve ter pelo menos dois representantes? 
 
Os Exercícios 21 a 26 estão relacionados a mãos de 5 cartas retiradas de um baralho comum com 52 cartas. 
 
21. Quantas mãos contêm três cartas de espadas e duas de copas? 
22. Quantas mãos contêm apenas carta de ouros? 
23. Quantas mãos contêm cartas do mesmo naipe? 
24. Quantas mãos contêm apenas figuras? 
25. Quantas mãos contêm uma trinca (três cartas do mesmo tipo)? 
26. Quantas mãos contêm um full house (uma trinca e um par)? 
 
Nos Exercícios 27 a 30, um conjunto de quatro moedas é selecionado de uma caixa contendo cinco moedas de dez 
centavos e sete moedas de vinte e cinco centavos. 
 
27. Encontre o número de conjuntos de quatro moedas. 
28. Encontre o número de conjuntos nos quais duas moedas são de dez centavos e duas são de vinte e cinco centavos. 
29. Encontre o número de conjuntos composto apenas de moedas de dez centavos ou apenas de moedas de vinte e cinco 
centavos. 
30. Encontre o número de conjuntos com três ou mais moedas de vinte e cinco centavos. 
 
Os Exercícios 31 a 34 se referem a uma rede de computadores com 60 nós. 
 
31. A rede é projetada para continuar funcionando se dois dos nós falharem. De quantas maneiras pode ocorrer uma 
dessas falhas? 
32. De quantas maneiras um ou dois nós podem falhar? 
33. Se um dos nós falhar, de quantas maneiras pode-se selecionar sete nós sem que se encontre o nó que não funciona? 
34. Se dois nós falharam, de quantas maneiras pode-se selecionar sete nós de modo a encontrar exatamenteum dos nós 
que não funciona? 
 
Nos Exercícios 35 a 38, deve-se formar uma comissão com três pessoas escolhidas entre cinco pessoas pertencentes a 
partidos que apóiam o governo, três que pertencem a partidos de oposição e quatro que pertencem a partidos 
independentes. 
 
35. De quantas maneiras pode-se escolher essa comissão? 
36. De quantas maneiras pode-se escolher essa comissão se ela deve incluir pelo menos uma pessoa pertencente a um 
partido independente? 
37. De quantas maneiras pode-se escolher essa comissão se ela não pode incluir ao mesmo tempo pessoas pertencentes 
a partidos que apóiam governo e pessoas de partido de oposição? 
38. De quantas maneiras pode-se escolher essa comissão se ela deve incluir pelo menos uma pessoa pertencente a um 
partido que apóia o governo e pelo menos uma pessoa de partidos da oposição? 
 
Nos Exercícios 39 a 42, uma anfitriã deseja convidar 6 pessoas para jantar de uma lista de 14 amigos. 
 
39. De quantas maneiras ela pode escolher seus convidados? 
40. De quantas maneiras ela pode escolher seus convidados se seis de seus amigos são maçantes, seis são interessantes e 
ela quer convidar pelo menos um de cada tipo? 
41. De quantas maneiras ela pode escolher seus convidados se dois de seus amigos não gostam um do outro e, se um 
deles vier o outro não vem? 
 27 
42. De quantas maneiras ela pode escolher seus convidados, se dois de seus amigos gostam muito um do outro e um 
deles não vem sem o outro? 
 
43. Vinte e cinco pessoas, inclusive Simon e Jasmim, são candidatos a participar de uma comissão formada por cinco 
pessoas. Se essa comissão tem que incluir Simon e Jasmim, de quantas maneiras ela pode ser selecionada? 
44. Um estudante precisa selecionar 5 disciplinas, entre 12, para o próximo semestre e uma delas tem que ser História 
do Brasil ou Literatura. De quantas maneiras o estudante pode escolher as suas disciplinas? 
45. Quantas mãos de 5 cartas retiradas de um baralho comum com 52 cartas, contêm exatamente 4 ases e 1 carta de 
paus? 
46. Quantas mãos de 5 cartas retiradas de um baralho comum com 52 cartas, contêm exatamente 3 valetes e 2 cartas de 
copas? 
47. a) Quantas permutações distintas existem das letras na palavra HAVAIANO? 
 b) Quantas delas começam com H? 
48. a) Quantas permutações distintas existem das letras na palavra APALACHICOLA? 
 b) Quantas delas têm os dois L’s juntos? 
49. Uma livraria tem uma prateleira onde estão expostos cinco, três e quatro exemplares, respectivamente, dos três 
livros mais vendidos. Quantos arranjos diferentes desses livros podem ser feitos se livros com mesmo título não são 
distinguíveis? 
50. O Grupo Unido em Prol da Dissensão usa palavras de código secretas que são permutações de cinco caracteres. 
Você descobre que existem apenas 10 palavras de código. O que você pode dizer sobre caracteres repetidos nas 
palavras código? 
51. Em um jantar para cinco pessoas prepara-se uma bandeja com cinco pratos contendo as entradas. As entradas 
podem ser mariscos, bolinhos de bacalhau ou bolinhas de queijo. Quantas bandejas diferentes podem ser produzidas? 
52. Um florista tem rosas, cravos, lírios e margaridas em estoque. Quantos buquês diferentes de uma dúzia de flores 
podem ser feitos? 
53. Cada um de quatro amigos compra um par de sapatos de corrida dentre uma seleção de uma loja com 14 tipos. De 
quantas maneiras eles podem ter feito as escolhas? 
54. Um “pacote de jogo” consiste em 12 cartelas de bingo. Quantos pacotes diferentes são possíveis se existem 15 tipos 
de cartelas e são permitidas repetições? 
55. Um pedido para uma loja de ferragens contém 6 itens, onde cada item é um galão de tinta, um martelo ou uma 
furadeira. 
a) Quantos pedidos diferentes podem ser feitos? 
b) Quantos pedidos diferentes podem ser feitos se não há pedido de tinta? 
c) Quantos pedidos diferentes podem ser feitos se cada pedido tem que conter pelo menos um galão de tinta, um 
martelo e uma furadeira? 
56. Em uma festa de aniversário, a mãe prepara um prato de biscoito para 8 crianças. Há uma grande quantidade de 
biscoitos de chocolate, de aveia e recheados de morango, mas cada criança só ganha um biscoito. 
a) Quantos pratos diferentes podem ser preparados? 
b) Quantos pratos diferentes contendo pelo menos um biscoito de cada tipo podem ser preparados? 
c) Quantos pratos diferentes podem ser preparados se ninguém gosta de biscoitos de aveia? 
57. No dia de Cosme e Damião são distribuídas 10 maçãs idênticas para 7 crianças. 
a) De quantas maneiras isto pode ser feito? 
b) De quantas maneiras isto pode ser feito se cada criança recebe pelo menos uma maçã? 
58. Oito móveis antigos idênticos estão sendo vendidos em um leilão e há três compradores interessados. 
a) De quantas maneiras isto pode ser feito? 
b) De quantas maneiras isto pode ser feito se o comprador A compra apenas um móvel? 
59. Na loteria de números (loto) são sorteados 5 números entre os naturais 0, 1, 2, 3, ..., 99. 
a) Quantos são os resultados possíveis para cada sorteio? 
b) Quantos são os resultados possíveis formados por três números pares e dois ímpares? 
c) Quantos são os resultados possíveis com pelo menos quatro números pares? 
60. Sobre uma mesa estão 4 copos de suco de laranja, 3 de caju e 2 de manga. De quantos modos diferentes podemos 
distribuí-los entre 9 crianças, dando um copo de suco cada uma? 
61. De quantos modos podemos formar uma sucessão de três números naturais ),,( cba não necessariamente distintos, 
cuja soma é igual a 10. 
 
 
 28 
Respostas: 
 
1. a) 42 b) 1680 c) 360 d) n e) !n 2. !9 3. !14 4. !7.3,!8 5.12 6. !5 7. 2730 
8. a) 576.17 b) 600.15 9. !19 10. !2!8!11 11.a)120 b) 36 c) 28 d) n 13. )25,300(C 
14. )11,18(C 15. )7,23().5,17( CC 16. )3,11().4,21( CC 17. )1,3().1,2().1,5().1,4().1,14().1,7( CCCCCC 
18. )4,21().2,14( CC 19. )5,30(.3 C 20. [ ])5,21().1,14()6,21()6,35( CCCC +− 
21. )2,13().3,13( CC 22. )5,13(C 23. )5,13(.4 C 24. )5,12(C 25. )2,48().3,4(.13 CC 
26. )2,4(12).3.4(.13 CC 27. )4,12(C 28. )2,7().2,5( CC 29. )4,7()4,5( CC + 
30. )3,7(.5)4,7( CC + 31. )2,60(C 32. )2,60()1,60( CC + 33. )7,59(C 34. )6,58(.2 C 
35. 220 36.164 37.115 38.105 39. )6,14(C 40. )6,8(.2)6,14( CC − 
41. )6,12()5,12(.2 CC + 42. )6,12()4,12( CC + 43. )3,23(C 44. )4,10(.2 C 45.12 46. )2,12().3,4( CC 
47. a) 
!3
!8
 b) 
!3
!7
 48. a) 
!2!2!4
!12
 b) 
!2!4
!11
 49.
!3!4!5
!12
 51. )5,7(C 52. )12,15(C 53. )4,17(C 
54. )12,26(C 55. a) )6,8(C b) )6,7(C c) )3,5(C 56. a) )8,10(C b) )5,7(C c) )8,9(C 
57. a) )10,16(C b) )3,9(C 58. a) )3,12(C b) )2,8()2,9( CC + 59. a) )5,100(C b) )2,50().3,50( CC 
c) )5,50()4,50(.50 CC + 60.1260 61. 66 
 
 
5. RELAÇÕES E FUNÇÕES 
 
Definição: Dado o conjunto S , uma relação binária em S , é um subconjunto de SS × . 
 
Exemplo: Seja }2,1{=S . Então )}2,2(),1,2(),2,1(),1,1{(=× SS . Seja ρ a relação em S dada pela descrição 
yx ρ se, e somente se, yx + é ímpar. Então ρ∈)1,2(),2,1( . 
 
Definição: Dados os conjuntos S e T , uma relação binária de S para T é um subconjunto de TS × . 
 
Exemplos: 
 
1. Sejam }2,1{=S e }4,3,2{=T . Uma relação ρ em )}4,2(),3,2(),2,2(),4,1(),3,1(),2,1{(=×TS pode 
ser definida por yx ρ se, e somente se, yx
2
1
= . Portanto )2,1( e )4,2( satisfazem ρ . Opcionalmente, poderíamos 
ter definido a mesma ρ dizendo que )}4,2(),2,1{( é o conjunto de pares ordenados que satisfazem ρ . 
 
2. Sejam }2,1{=Se }4,3,2{=T . Seja ρ a relação em TS × dada pela descrição yxyx +↔ρ for par. Então 
ρ∈)4,2(),2,2(),3,1( . 
 
3. Se }5,3,2,1,0,1,2{ −−=S e }4,3,2,1,
2
1
,
3
1{=T , quais pares abaixo pertencem à relação ρ em TS × dada 
pela descrição xyyx ↔ρ é um número inteiro? 
 
)2/1,5(),1,1(),2,1(),2/1,2(),4,0(),3/1,1(),1,5(),4,2(),3,3(),3,2(),2,0(),2,1( −−−−− 
 
 
 
 29 
Exercícios: 
 
1. Para cada uma das relações binárias ρ definidas a seguir em N, decida quais entre os pares ordenados dados 
pertencem a ρ . 
 
a) )2,3(),3,3(),3,2(),2,2(;1+=↔ yxyx ρ b) )6,2(),5,2(),4,2(; divide yxyx ↔ρ 
c) )6,5(),5,4(),4,3(),3,2(;ímpar é xyx ↔ρ d) )3,4(),4,6(),2,5(),1,2(),2,1(;2yxyx >↔ρ 
e) )4,4(),3,3(),5,2(),3,1(;7<+↔ yxyx ρ f) )3,5(),3,6(),2,4(),2,0(;2+=↔ yxyx ρ 
g) )3,1(),1,3(),2,2(),0,5(;1032 =+↔ yxyx ρ 
h) )5,25(),9,3(),2,4(),1,1(;perfeito quadrado um é yyx ↔ρ 
 
Se ρ é uma relação binária em TS × , então ρ consiste em um conjunto de pares ordenados da forma ),( ts . Dada 
uma primeira componente s ou uma segunda componente t , podem ser formados diversos pares pertencentes à 
relação. A relação é um para um se cada primeira componente e cada segunda componente aparece apenas uma vez na 
relação. A relação é um para muitos se alguma primeira componente aparece mais de uma vez, isto é, se um s pode 
aparecer em mais de um par. Ela é dita muitos para um se alguma segunda componente t aparece em mais de um par. 
Finalmente, ela é dita muitos para muitos se pelo menos um s aparece em mais de um par e pelo menos um t 
aparece em mais de um par. A Figura a seguir ilustra essas quatro possibilidades. Note que nem todos os valores de S 
e T precisam ser componentes de algum par ordenado de ρ . 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2. Identifique cada uma das relações em S como sendo um para um, um para muitos, muitos para um ou muitos para 
muitos, onde }9,7,5,2{=S . 
 
a) )}2,9(),5,7(),2,5{( b) )}2,7(),7,5(),5,2{( 
c) )}7,2(),9,9(),5,2(),9,7{( d) )}9,2(),7,2(),5,2(),2,2{( 
 
3. Sejam ρ e σ duas relações binárias em }5,4,2,1{=S definidas por yxyx =↔ρ e yxyx <↔σ . 
Descreva quem são as relações: 
 
a) σρ ∪ b) 'ρ c) 'σ d) σρ ∩ 
 
 30 
Definição: Seja ρ uma relação binária em um conjunto S . Então: 
 
• ρ ser reflexiva significa )),()(( ρ∈→∈∀ xxSxx ; 
• ρ ser simétrica significa )),(),(,)()(( ρρ ∈→∈∧∈∀∀ xyyxSyxyx ; 
• ρ ser transitiva significa )),(),(),(,,)()()(( ρρρ ∈→∈∧∈∧∈∀∀∀ zxzyyxSzyxzyx ; 
• ρ ser anti-simétrica significa )),(),(,)()(( yxxyyxSyxyx =→∈∧∈∧∈∀∀ ρρ . 
 
4. Verifique se as relações binárias nos conjuntos abaixo são reflexivas, simétricas, anti-simétricas e transitivas: 
 
a) NSyxyx =≤↔ ,ρ b) )(, NSBABA ℘=⊆↔ρ 
 
5. Seja { }3,2,1=S 
 
a) Se uma relação ρ em S é reflexiva, quais pares ordenados devem pertencer a ρ ? 
b) Se uma relação ρ em S é simétrica, quais pares ordenados devem pertencer a ρ ? 
c) Se uma relação ρ em S é simétrica e se ρ∈),( ba , então que outro par ordenado tem que pertencer a ρ ? 
d) Se uma relação ρ em S é anti-simétrica e se ),( ba e ),( ab pertencem a ρ , o que tem que ser verdade? 
e) A relação )}2,1{(=ρ em S é transitiva? 
 
6. Verifique se as relações binárias nos conjuntos abaixo são reflexivas, simétricas, anti-simétricas e transitivas: 
 
a) par é , yxyxNS +↔= ρ ; 
b) yxyxNS divide , ↔= ρ ; 
c) yxyxyxS com coincide ou a paralela é ,plano do retas as todasde conjunto ↔= ρ ; 
d) 2, yxyxNS =↔= ρ ; 
e) 2},1,0{ yxyxS =↔= ρ ; 
f) yxyxxxS que velhomais é ,Bahia} na mora que pessoa uma é /{ ↔= ρ ; 
g) yxyxxxS que fileira mesma na senta ,sala} sua da aluno um é /{ ↔= ρ ; 
h) )}1,2(),2,1(),3,3(),2,2(),1,1{(,1,2,3}{ == ρS . 
 
Definição: Uma relação binária ∗ρ em um conjunto S é o fecho de uma relação ρ em S em relação à propriedade 
P se: 
 
• 
∗ρ tem a propriedade P ; 
• 
∗⊆ ρρ ; 
• 
∗ρ é um subconjunto de qualquer outra relação em S que inclui ρ e tem a propriedade P . 
 
7. Encontre os fechos reflexivo, simétrico e transitivo da relação em },,,{ dcbaS = dada por 
)},(),,(),,(),,(),,(),,(),,(),,{( adacdbdacaccbbaa=ρ . 
 
Definição: Uma relação binária em um conjunto S que seja reflexiva, anti-simétrica e transitiva é chamada de uma 
ordem parcial em S . 
 31 
Definição: Uma relação binária em um conjunto S que seja reflexiva, simétrica e transitiva é chamada de uma relação 
de equivalência em S . 
 
8. Verifique quais relações do exercício 6 são ordens parciais ou relações de equivalência. 
 
Definição: Sejam S e T conjuntos. Uma função (aplicação) f de S em T , TSf →: , é um subconjunto de 
TS × tal que cada elemento de S aparece exatamente uma vez como a primeira componente de um par ordenado. S 
é o domínio e T é o contradomínio da função. Se ),( ts pertence à função, então denotamos t por )(sf ; t é a 
imagem de s por f . Para )(, AfSA ⊆ denota });({ Aaaf ∈ . 
 
 
 
 
 
 
 
 
 
9. Quais das relações abaixo são funções do domínio no contradomínio indicado? Para as que não são, por que não? 
 
a) )}1,2(),1,3(),3,2(),1,1{(},3,2,1{,: ===→ fTSTSf . 
b) xxgZZg =→ )(,: . 
c) 4)(,: −=→ xxhNNh . 
d) TSf →: , onde S é o conjunto de pessoas residentes em sua cidade, T é o conjunto de números de CPF e f 
associa cada pessoa ao seu número de CPF. 
e) TSh →: , onde S é o conjunto de todos os polinômios de grau 2 em x com coeficientes inteiros, ZT = e h é 
definida por cbcbxaxh +=++ )( 2 . 
f) 14)(,: −=→ xxfRRf . 
g) 



≤
≥+
=→
5
53)(,:
xx
xx
xgNNg . 
 
Definição: Uma função TSf →: é dita sobrejetora se sua imagem é igual o seu contradomínio. 
 
Definição: Uma função TSf →: é injetora se nenhum elemento de T é imagem, por f , de dois elementos 
distintos de S . 
 
Definição: Uma função TSf →: é bijetora se é, ao mesmo tempo, injetora e sobrejetora. 
 
Definição: Sejam TSf →: e UTg →: . A função composta fg o é a função de S em U definida por 
))(())(( sfgsfg =o . 
 
Definição: Seja f uma função TSf →: . Se existir uma função STg →: tal que Sifg =o e Tigf =o , 
então g é chamada a função inversa de f , denotada por 1−f . 
 
Teorema sobre Bijeções e Funções Inversas: Seja TSf →: . Então f é uma bijeção, se, e somente se, 1−f 
existe. 
 32 
Exercícios: 
 
1. Diga se cada uma das relações em N a seguir é um para um, um para muitos, muitos para um ou muitos para muitos. 
 
a) )}3,4(),3,2(),6,1(),4,1(),2,1{(=ρ b) )}5,8(),6,3(),5,6(),7,9{(=ρ 
c) )}12,7(),3,6(),4,8(),5,12{(=ρ d) )}1,10(),6,7(),5,2(),4,8(),7,2{(=ρ 
 
2. Diga se cada uma das relações em S a seguir é um para um, um para muitos, muitos para um ou muitos para muitos. 
 
a) 1, +=↔= yxyxNS ρ ; 
b) yxyxS de filha é Xarópolis, em mulheres as todasde conjunto ↔= ρ ; 
c) )()(}),3,2,1({ BnAnBAS =↔℘= ρ ; 
d) 5, =↔= xyxRS ρ . 
 
3. Sejam ρ e σ duas relações binárias em N definidas por yxyx divide ↔ρ e yxyx ≤↔ 5σ . Decida 
quais dos pares ordenados satisfazem as relações correspondentes: 
 
a) σρ ∪ ; )0,0(),1,2(),17,3(),6,2( b) σρ ∩ ; )12,2(),2,1(),6,3( 
c) 'ρ ; )15,3(),8,2(),5,1( c) 'σ ; )8,4(),10,2(),1,1( 
 
4. Sejam }6,4,2,1,0{=S . Teste se as relações binárias em S dadas a seguir são reflexivas, simétricas, anti-
simétricas ou transitivas. 
 
a) )}6,4(),4,2(),2,1(),1,0(),6,6(),4,4(),2,2(),1,1(),0,0{(=ρ 
b) )}4,6(),6,4(),2,4(),4,2(),0,1(),1,0{(=ρ 
c) )}2,2(),1,1(),0,0(),0,1(),1,2(),0,2(),2,0(),2,1(),1,0{(=ρ