Matematica Discreta

Prévia do material em texto

Matema´tica Discreta
Josimar da Silva Rocha
2
Suma´rio
1 Fundamentos de Lo´gica Matema´tica 7
1.1 Lo´gica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Sentenc¸as ou Proposic¸o˜es Lo´gicas . . . . . . . . . . . . . . . . . . 7
1.2 Conectivos Lo´gicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Conectivo de conjunc¸a˜o (E): ^ . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Conectivo de disjunc¸a˜o (OU): _ . . . . . . . . . . . . . . . . . . . 8
1.2.3 Conectivo de Negac¸a˜o (NA˜O): ¬ . . . . . . . . . . . . . . . . . . 8
1.2.4 Conectivo de Implicac¸a˜o ou conectivo condicional (SE ... ENTA˜O):
! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.5 Conectivo de bi-implicac¸a˜o ou conectivo bicondicional (SE, E SO-
MENTE SE,): $ . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Tautologia e Contradic¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Relac¸o˜es entre sentenc¸as lo´gicas . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.1 Relac¸a˜o de implicac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.2 Relac¸a˜o de equivaleˆncia . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Sentenc¸a abertas e Sentenc¸as Fechadas . . . . . . . . . . . . . . . . . . . . 13
1.6 Quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6.1 Quantificador universal . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6.2 Quantificador existencial . . . . . . . . . . . . . . . . . . . . . . . 14
2 Conjuntos 19
2.1 Relac¸a˜o de pertineˆncia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Relac¸o˜es entre conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Relac¸a˜o de igualdade . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Relac¸a˜o de contineˆncia entre conjuntos . . . . . . . . . . . . . . . 19
3
4 SUMA´RIO
2.3 Operac¸o˜es sobre conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.1 Operac¸o˜es bina´rias . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.2 Operac¸a˜o una´ria . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.3 Operac¸a˜o una´ria restrita . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Princı´pio da Inclusa˜o-Exclusa˜o . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Te´cnicas de Demonstrac¸a˜o 31
3.1 Te´cnica de demonstrac¸a˜o por exausta˜o . . . . . . . . . . . . . . . . . . . . 31
3.2 Te´cnica de demonstrac¸a˜o direta . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Te´cnica de demonstrac¸a˜o por contraposic¸a˜o . . . . . . . . . . . . . . . . . 33
3.4 Te´cnica de demonstrac¸a˜o por contradic¸a˜o (ou por absurdo) . . . . . . . . . 33
3.5 Princı´pios de induc¸a˜o matema´tica . . . . . . . . . . . . . . . . . . . . . . 34
4 Relac¸o˜es e Func¸o˜es 43
4.1 Func¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5 Ana´lise Combinato´ria 53
5.1 Princı´pio das Casas de Pombo . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2 Princı´pio Fundamental da Contagem . . . . . . . . . . . . . . . . . . . . . 54
5.2.1 Princı´pio da Multiplicac¸a˜o . . . . . . . . . . . . . . . . . . . . . . 54
5.2.2 Princı´pio da Soma . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3 Outros Me´todos de Contagem . . . . . . . . . . . . . . . . . . . . . . . . 56
5.4 Caso sem te´cnica conhecida . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.5 Fatorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.6 Agrupamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.6.1 Arranjos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.6.2 Permutac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.6.3 Combinac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.6.4 Permutac¸o˜es com repetic¸a˜o . . . . . . . . . . . . . . . . . . . . . . 61
6 Introduc¸a˜o a` Teoria dos Nu´meros 63
6.1 Congrueˆncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.1.1 Propriedades das Congrueˆncias . . . . . . . . . . . . . . . . . . . 77
7 Conjuntos Enumera´veis 81
SUMA´RIO 5
8 Grafos 91
8.1 Definic¸o˜es iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
8.2 Terminologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
8.3 Isomorfismo entre grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
8.4 Matrizes de Adjaceˆncia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
8.4.1 Matriz de adjaceˆncia para grafo na˜o-direcionado (na˜o-orientado) . . 97
8.4.2 Matriz de adjaceˆncia para grafo ponderado (valorado) . . . . . . . 103
8.5 Matriz de distaˆncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
8.5.1 Matriz de distaˆncias para Grafos na˜o ponderados . . . . . . . . . . 103
8.5.2 Matriz de distaˆncias para Grafos ponderados . . . . . . . . . . . . 103
8.5.3 Lista de Exercı´cios sobre Grafos . . . . . . . . . . . . . . . . . . . 105
9 A´lgebra de Boole 111
9.1 Minimizac¸a˜o de Func¸o˜es Booleanas . . . . . . . . . . . . . . . . . . . . . 116
9.1.1 Me´todo de Quine-McCluskey . . . . . . . . . . . . . . . . . . . . 116
9.1.2 Me´todo de Karnaugh . . . . . . . . . . . . . . . . . . . . . . . . . 116
9.1.3 Desvantagens na utilizac¸a˜o do me´todo de reduc¸a˜o de Karnaugh . . 120
10 Du´vidas Correlatas em aula 123
6 SUMA´RIO
Capı´tulo 1
Fundamentos de Lo´gica Matema´tica
1.1 Lo´gica
1.1.1 Sentenc¸as ou Proposic¸o˜es Lo´gicas
Definic¸a˜o 1. Uma afirmac¸a˜o e´ uma sentenc¸a (ou proposic¸a˜o) lo´gica se esta afirmac¸a˜o
puder receber uma valorac¸a˜o V (verdadeira) ou F (falsa).
1.2 Conectivos Lo´gicos
1.2.1 Conectivo de conjunc¸a˜o (E): ^
Definic¸a˜o 2. Conectivo de conjunc¸a˜o (^) e´ um conectivo que conecta duas sentenc¸as
lo´gicas para formar uma nova sentenc¸a que recebe valorac¸a˜o V (verdadeira) se as sentenc¸as
conectadas por este conectivo possuem valorac¸a˜o V (verdadeira).
Se p e q sa˜o sentenc¸as lo´gicas enta˜o a sentenc¸a p^q pode ser representada pela seguinte
tabela-verdade:
p q p ^ q
V V V
F V F
V F F
F F F
7
8 CAPI´TULO 1. FUNDAMENTOS DE LO´GICA MATEMA´TICA
Exemplo 1. • Se p :O aluno tirou nota maior ou igual a 6 e q :O aluno tem frequeˆncia
maior ou igual a 75%; enta˜o p ^ q : O aluno foi aprovado.
1.2.2 Conectivo de disjunc¸a˜o (OU): _
Definic¸a˜o 3. Conectivo de disjunc¸a˜o (_) e´ um conectivo que conecta duas sentenc¸as
lo´gicas para formar uma nova sentenc¸a que recebe valorac¸a˜o V (verdadeira) se uma das
sentenc¸as conectadas por este conectivo possui valorac¸a˜o V (verdadeira).
Se p e q sa˜o sentenc¸as lo´gicas enta˜o a sentenc¸a p_q pode ser representada pela seguinte
tabela-verdade:
p q p _ q
V V V
F V V
V F V
F F F
Exemplo 2. Se p : O aluno tirou nota menor ou igual a 6 ou q : O aluno tem frequeˆncia
menor do que 75%; enta˜o p _ q : O aluno foi reprovado.
Exemplo 3. • (V) p :Windows e´ um sistema operacional ou q pascal e´ uma linguagem
de programac¸a˜o;
• (V) p : Windows na˜o e´ um sistema operacional ou q pascal e´ uma linguagem de
programac¸a˜o;
• (V) p : Windows e´ um sistema operacional ou q pascal na˜o e´ uma linguagem de
programac¸a˜o;
• (F) p : Windows na˜o e´ um sistema operacional ou q pascal na˜o e´ uma linguagem de
programac¸a˜o;
1.2.3 Conectivo de Negac¸a˜o (NA˜O): ¬
Definic¸a˜o 4. Este conectivo serve para alterar a valorac¸a˜o de uma sentenc¸a lo´gica. Desta
forma, se uma sentenc¸a lo´gica p tiver valorac¸a˜o V enta˜o ¬p possui valorac¸a˜o F e se uma
sentenc¸a lo´gica p tiver valorac¸a˜o F, enta˜o ¬p possui valorac¸a˜o V.
1.2. CONECTIVOS LO´GICOS 9
Este conectivopode ser representado pela seguinte tabela-verdade:
p ¬p
V F
F V
Exemplo 4. • Se p : o nu´mero e´ primo, enta˜o ¬p : o nu´mero na˜o e´ primo.
• Se p : Choveu, enta˜o ¬p : Na˜o choveu.
• Se p : Pedro foi aprovado, enta˜o ¬p : Pedro na˜o foi aprovado.
1.2.4 Conectivo de Implicac¸a˜o ou conectivo condicional (SE ... ENTA˜O):
!
Definic¸a˜o 5. Conectivo de implicac¸a˜o ou conectivo condicional (!) e´ um conectivo que
conecta duas sentenc¸as lo´gicas p e q para formar uma nova sentenc¸a p ! q que recebe
valorac¸a˜o F (falsa) se, e somente se, p tem valorac¸a˜o verdadeira e q tem valorac¸a˜o falsa.
Neste caso, p e´ chamada de hipo´tese e q e´ chamada de tese.
Se p e q sa˜o sentenc¸as lo´gicas enta˜o a sentenc¸a p ! q pode ser representada pela
seguinte tabela-verdade:
p q p! q
V V V
F V V
V F F
F F V
Observac¸a˜o 1. Para o sı´mbolo p! q leˆ-se se p enta˜o q ou p implica em q.
Exemplo 5. Seja p : o nu´mero m e´ maior do que 10 e q : o nu´mero m e´ maior do que 3.
Assim, p! q quer dizer que se o nu´merom e´ maior do que 10, enta˜o o nu´merom e´ maior
do que 3.
10 CAPI´TULO 1. FUNDAMENTOS DE LO´GICA MATEMA´TICA
1.2.5 Conectivo de bi-implicac¸a˜o ou conectivo bicondicional (SE, E
SOMENTE SE,): $
Definic¸a˜o 6. Conectivo de bi-implicac¸a˜o ou conectivo bicondicional ($) e´ um conectivo
que conecta duas sentenc¸as lo´gicas p e q para formar uma nova sentenc¸a p$ q que recebe
valorac¸a˜o V (verdadeira) se, e somente se, p e q possuem a mesma valorac¸a˜o.
Se p e q sa˜o sentenc¸as lo´gicas enta˜o a sentenc¸a p $ q pode ser representada pela
seguinte tabela-verdade:
p q p$ q
V V V
F V F
V F F
F F V
Observac¸a˜o 2. Para o sı´mbolo p$ q leˆ-se p se, e somente se, q.
Exemplo 6. Sejam p : n e´ um nu´mero natural primo; q : n e´ um nu´mero natural e seus
u´nicos divisores de n sa˜o 1 e n. Enta˜o p $ q significa que um nu´mero n natural e´ primo
se, e somente se, seus u´nicos divisores sa˜o 1 e n.
Exemplo 7. Sejam p : As retas r e s teˆm o mesmo coeficiente angular; q : As retas r e s
sa˜o paralelas. Enta˜o p $ q significa que duas retas sa˜o paralelas se, e somente se, teˆm o
mesmo coeficiente angular.
1.3 Tautologia e Contradic¸a˜o
Definic¸a˜o 7. Se uma sentenc¸a recebe valorac¸a˜o V para quaisquer que sejam as valorac¸o˜es
das sentenc¸as componentes, enta˜o dizemos que esta sentenc¸a e´ uma tautologia.
Exemplo 8. Mostre que (p! q) ^ (q ! r)! (p! r) e´ uma tautologia.
Definic¸a˜o 8. Se uma sentenc¸a recebe valorac¸a˜o F para quaisquer que sejam as valorac¸o˜es
das sentenc¸as componentes, enta˜o dizemos que esta sentenc¸a e´ uma contradic¸a˜o.
Exemplo 9. Prove que (p! q) ^ (p _ ¬q) e´ uma contradic¸a˜o.
1.4. RELAC¸O˜ES ENTRE SENTENC¸AS LO´GICAS 11
1.4 Relac¸o˜es entre sentenc¸as lo´gicas
1.4.1 Relac¸a˜o de implicac¸a˜o
Definic¸a˜o 9. Relac¸a˜o de implicac¸a˜o: ()) Diz-se que uma sentenc¸a lo´gica (proposic¸a˜o)
p implica em uma sentenc¸a lo´gica (ou proposic¸a˜o) q, (p) q), se a sentenc¸a lo´gica q tem
valorac¸a˜o verdadeira V sempre que a sentenc¸a lo´gica q possuir valorac¸a˜o verdadeira V,
ou seja, se p! q e´ uma tautologia.
Exemplo 10. Mostre que:
(a) p ^ q ) p
(b) p) p _ q.
1.4.2 Relac¸a˜o de equivaleˆncia
Definic¸a˜o 10. Relac¸a˜o de equivaleˆncia: (,) Diz-se que duas sentenc¸as lo´gicas (ou proposic¸o˜es)
p e q sa˜o equivalentes, p, q, quando suas tabelas-verdade forem iguais, ou seja, se p$ q
e´ uma tautologia.
Equivaleˆncias Nota´veis
1. Dupla negac¸a˜o
¬(¬p), p (1.1)
2. Idempoteˆncia
p _ p, p (1.2)
p ^ p, p (1.3)
3. Comutatividade
p _ q , q _ p (1.4)
p ^ q , q ^ p (1.5)
12 CAPI´TULO 1. FUNDAMENTOS DE LO´GICA MATEMA´TICA
4. Associatividade
p _ (q _ r), (p _ q) _ r (1.6)
p ^ (q ^ r), (p ^ q) ^ r (1.7)
5. Bicondicionalidade
p$ q , (p! q) ^ (q ! p) (1.8)
6. Contraposic¸a˜o
p! q , ¬q ! ¬p (1.9)
7. Leis de De Morgan
¬(p _ q), ¬p ^ ¬q (1.10)
¬(p ^ q), ¬p _ ¬q (1.11)
Exercı´cio 1. Prove que p! q , (¬p _ q)
Usando o computador
Na linguagem de programac¸a˜o e´ comum utilizarmos conectivos lo´gicos. Estes conectivos
lo´gicos muitas vezes sa˜o apresentados de uma forma (ou com um sı´mbolo) diferente do
que vimos aqui. A tabela abaixo apresenta alguns conectivos lo´gicos utilizados com sua
representac¸a˜o nas linguagens de programac¸a˜o C e pascal.
Sı´mbolo padra˜o Linguagem C Linguagem Pascal
^ && and
_ || or
¬ ! not
Para demonstrar que uma sentenc¸a lo´gica q formada a partir das sentenc¸as constituintes
a, · · · , c e´ uma tautologia basta utilizarmos o seguinte algoritmo em C para demonstrar
esta condic¸a˜o:
#include<stdlib.h>
#include<stdio.h>
1.5. SENTENC¸A ABERTAS E SENTENC¸AS FECHADAS 13
int main()
{
int a, ... , c, x;
x=1;
for (a=0; a<2; a+ +)
{
...
{
for(c=0; c<2; c++)
if (!q) {x=0; break;}
if (!q) {break;} }
...
if (!q) {break;}}
return x;
}
1.5 Sentenc¸a abertas e Sentenc¸as Fechadas
Definic¸a˜o 11. Uma sentenc¸a fechada e´ uma sentenc¸a lo´gica cuja valorac¸a˜o na˜o depende
de atribuic¸a˜o de valores para varia´veis.
Exemplo 11. A sentenc¸a p : 5 > 7 e´ uma sentenc¸a fechada cujo valor lo´gico e´ falso.
Definic¸a˜o 12. Uma sentenc¸a aberta e´ uma sentenc¸a lo´gica cuja valorac¸a˜o depende de
atribuic¸a˜o de valores para varia´veis.
Exemplo 12. A sentenc¸a q : x2 < 5 e´ uma sentenc¸a aberta.
Definic¸a˜o 13. O conjunto universo de uma sentenc¸a aberta e´ o conjunto de todos os va-
lores atribuı´dos as varia´veis de modo a torna´-la uma sentenc¸a lo´gica. O conjunto universo
e´ representado pela letra U (maiu´scula).
Definic¸a˜o 14. O conjunto verdade de uma sentenc¸a aberta p(x) e´ o subconjunto de U
de todos os valores atribuı´dos a varia´vel x de modo que p(x) seja verdadeira. O conjunto
verdade de uma sentenc¸a aberta p(x) e´ representado por
V = {x 2 U | v(p(x)) = V }.
14 CAPI´TULO 1. FUNDAMENTOS DE LO´GICA MATEMA´TICA
1.6 Quantificadores
Definic¸a˜o 15. Expresso˜es como “existe”, “para algum”, “para todos”, “para qualquer”que
expressa˜o quantidades sa˜o chamadas de quantificadores.
1.6.1 Quantificador universal
Definic¸a˜o 16. Expresso˜es como “para todo”, “para qualquer”que expressam que para
qualquer elemento x do conjunto universo a sentenc¸a aberta p(x) e´ verdadeira sa˜o repre-
sentadas pelo que chamamos de quantificador universal 8, de modo que a expressa˜o
“para todo x, p(x)”pode ser substituı´da simbolicamente por (8x) (p(x)) .
Exemplo 13.
(a) (8x) (x2 + 1 > 0)
(b) (8x) (x > 5)
Observac¸a˜o 3. Observe que se o conjunto-verdade de uma sentenc¸a aberta p(x) for igual
ao conjunto universo U, enta˜o a sentenc¸a lo´gica (8x) (p(x)) e´ verdadeira, ou seja,
v ((8x) (p(x))) = V , V = U.
1.6.2 Quantificador existencial
Definic¸a˜o 17. Expresso˜es como “existe”ou “para algum”que expressam a existeˆncia de
que para algum elemento x do conjunto universo a sentenc¸a aberta p(x) e´ verdadeira
sa˜o representadas pelo que chamamos de quantificador existencial 9, de modo que a
expressa˜o “para algum x, p(x)”pode ser substituı´da simbolicamente por (9x) (p(x)) .
Exemplo 14.
(a) (9x) (x2 = 1)
(b) (9x) (x2 + 1 < 0)
Observac¸a˜o 4. Observe que se o conjunto-verdade de uma sentenc¸a aberta p(x) for na˜o
vazio, enta˜o a sentenc¸a (9x) (p(x)) e´ sempre verdadeira, ou seja,
v(p(x)) = V , V 6= ?.
Definic¸a˜o 18. Uma sentenc¸a quantificada e´ uma sentenc¸a formada a partir de quantifi-
cadores.
1.6. QUANTIFICADORES 15
Lista de Exercı´cios sobre Lo´gica Matema´tica
1. Mostre que as seguintes sentenc¸as lo´gicas sa˜o tautologias:
(a) (p$ q)$ (p! q) ^ (q ! p)
(b) ¬(¬p _ ¬q)$ (p ^ q)
2. Mostre que as seguinte sentenc¸a lo´gica (p! q) ^ (p ^ ¬q) e´ uma contradic¸a˜o.
3. Sejam as proposic¸o˜es p : Joa˜o joga futebol e q : Joa˜o joga teˆnis. Escreva na lingua-
gem usual asseguintes proposic¸o˜es:
(a) p _ q
(b) p ^ q
(c) p ^ ¬q
(d) ¬p ^ ¬q
(e) ¬(¬p)
(f) ¬(¬p ^ ¬q)
4. Dadas as proposic¸o˜es p :Maria e´ bonita e q :Maria e´ elegante, escreva na linguagem
simbo´lica as seguintes proposic¸o˜es:
(a) Maria e´ bonita e elegante.
(b) Maria e´ bonita, mas na˜o e´ elegante.
(c) Na˜o e´ verdade que Maria na˜o e´ bonita ou elegante.
(d) Maria na˜o e´ bonita nem elegante.
(e) Maria e´ bonita ou na˜o e´ bonita e elegante.
(f) E´ falso que Maria na˜o e´ bonita ou que na˜o e´ elegante.
5. Se V (p) = V (q) = V e V (r) = V (s) = F, determinar os valores lo´gicos das
seguintes proposic¸o˜es:
(a) ¬p _ r
(b) [r _ (p! s)]
(c) [¬p _ ¬(r ^ s)]
16 CAPI´TULO 1. FUNDAMENTOS DE LO´GICA MATEMA´TICA
(d) ¬[q $ (¬p)]
(e) (p$ q) _ (q ! ¬p)
(f) (p$ q) ^ (¬r ! s)
(g) ¬{¬[¬q ^ ¬(p ^ ¬s)]}
(h) ¬p _ [q ^ (r ! ¬s)]
(i) (¬p _ r)! (q ! s)
(j) ¬[¬p _ (q ^ s)] _ (r ! ¬s)
(k) ¬q ^ [(¬s _ s)$ (p! ¬q)]
(l) ¬[p! (q ! r)]! s
6. Verifique que:
(a) (p! q) ^ (q ! p), (p$ q)
(b) (p ^ q)) (p _ q)
(c) ¬(p _ q), ¬p ^ ¬q
(d) p _ (q ^ r), (p _ q) ^ (p _ r)
(e) ¬b ^ q ) q
7. Negue as seguintes sentenc¸as lo´gicas:
(a) (p! q)! r
(b) (p! q) ^ (q ! r)
(c) (¬r ! q) ^ p
(d) ¬(p ^ r) _ p
(e) p$ r
8. Negue as seguintes sentenc¸as lo´gicas com quantificadores:
(a) (8") (9�) (0 < |x� c| < � ! |f(x)� L| < ")
(b) (9x) (x2 + 2x > 10)
(c) (8x) (x2 + 1 6= 0)
1.6. QUANTIFICADORES 17
(d) (8x) (8y) �(px > py)! (x > y)�
(e) (8x) (8y) (x 6= y ! ((x > y) _ (y > x)))
9. Negue as seguintes sentenc¸as lo´gicas e escreva estas sentenc¸as na forma simbo´lica.
(a) Todo retaˆngulo e´ um quadrila´tero.
(b) Nem todo polı´gono e´ regular.
(c) Toda a´rvore que possui n ve´rtices possui n� 1 arestas.
(d) Nenhuma a´rvore conte´m ciclos.
(e) Um grafo conexo e acı´clico e´ uma a´rvore.
(f) Todo homem e´ bom.
(g) Existem homens valentes e homens covardes.
18 CAPI´TULO 1. FUNDAMENTOS DE LO´GICA MATEMA´TICA
Capı´tulo 2
Conjuntos
Os termos elemento e conjunto sa˜o primitivos, ou seja, na˜o precisam ser definidos. Con-
junto da´ ideia de colec¸a˜o de objetos, que sa˜o os elementos do conjunto.
Daı´, conjunto poder ser visto como sinoˆnimo de colec¸a˜o.
2.1 Relac¸a˜o de pertineˆncia
Quando um elemento a pertence a um conjunto A utilizamos o sı´mbolo 2 para representar
esta relac¸a˜o, de modo que a 2 A. Caso contra´rio, quando um elemento a na˜o pertence a
um conjunto A utilizamos o sı´mbolo 62 para representar esta relac¸a˜o, de modo que a 62 A.
2.2 Relac¸o˜es entre conjuntos
2.2.1 Relac¸a˜o de igualdade
Definic¸a˜o 19. Dois conjuntos sa˜o iguais se possuem os mesmos elementos.
Exemplo 15. Se A = {1; 1; 2; 4; 6; 7} e B = {1; 2; 4; 4; 6; 7; 7; 7}, enta˜o A = B, pois A e
B possuem os mesmos elementos.
2.2.2 Relac¸a˜o de contineˆncia entre conjuntos
Definic¸a˜o 20. Sejam A e B conjuntos. Dizemos que um conjunto A e´ um subconjunto
de um conjunto B (ou A esta´ contido em B ou que B conte´m A) se todo elemento do
conjunto A e´ elemento do conjunto B. Utilizamos os sı´mbolos A ⇢ B (A esta´ contido
19
20 CAPI´TULO 2. CONJUNTOS
em B) e B � A (B conte´m A) para representar que o conjunto A e´ um subconjunto do
conjunto B.
No caso em que um conjuntoA na˜o e´ um subconjunto de um conjuntoB (ouA na˜o esta´
contido em B ou que B na˜o conte´m A, enta˜o existem elementos do conjunto A que na˜o
esta˜o no conjunto B. Neste caso utilizamos os sı´mbolos A 6⇢ B (A na˜o esta´ contido em B)
e B � A (B na˜o conte´m A) para representar que o conjunto A na˜o e´ um subconjunto do
conjunto B.
Em sı´mbolos,
A ⇢ B , (8x) ((x 2 A) ^ (x 2 B)) ,
ou seja,
(A ⇢ B)$ (8x) ((x 2 A) ^ (x 2 B))
e´ uma tautologia.
Algumas propriedades dos subconjuntos sa˜o
(1) A ⇢ A.
(2) Se A ⇢ B e B ⇢ C, enta˜o A ⇢ C.
(3) Se A ⇢ B e B ⇢ A, enta˜o A = B.
(4) A ⇢ U.
Definic¸a˜o 21. O Conjunto Universo U e´ o conjunto de todos os elementos do sistema.
Definic¸a˜o 22. O Conjunto Vazio ? (ou {}) e´ o conjunto que na˜o possui elementos.
Definic¸a˜o 23. Conjunto Unita´rio e´ um conjunto que possui apenas um elemento.
Exemplo 16. Os conjuntos {?}, {{}} e {1} sa˜o conjuntos unita´rios.
2.3 Operac¸o˜es sobre conjuntos
As operac¸o˜es sobre conjuntos dividem-se em operac¸o˜es bina´rias, operac¸ oes una´rias e
operac¸o˜es restritas.
2.3. OPERAC¸O˜ES SOBRE CONJUNTOS 21
2.3.1 Operac¸o˜es bina´rias
Definic¸a˜o 24. O conjunto intersec¸a˜o A\B e´ o conjunto formado pelos elementos comuns
entre os conjuntos A e B.
Em sı´mbolos, (8x) (x 2 A \ B $ (x 2 A) ^ (x 2 B)) e´ uma tautologia.
Definic¸a˜o 25. O conjunto unia˜o A [ B e´ o conjunto formado por todos os elementos de
A e por todos os elementos de B.
Em sı´mbolos, (8x) (x 2 A [ B $ (x 2 A) _ (x 2 B)) e´ uma tautologia.
Definic¸a˜o 26. O conjunto diferenc¸a A � B e´ o conjunto formado pelos elementos que
esta˜o em A e na˜o esta˜o em B.
Em sı´mbolos, (8x) ((x 2 A� B)$ (x 2 A) ^ (x 62 B)) e´ uma tautologia.
2.3.2 Operac¸a˜o una´ria
Definic¸a˜o 27. O complementar de um conjunto A, AC (ou C(A) ou A) e´ o conjunto dos
elementos que esta˜o no conjunto universo U mas que na˜o esta˜o em A.
Em sı´mbolos, (8x) �x 2 AC $ x 62 A� e´ uma tautologia.
2.3.3 Operac¸a˜o una´ria restrita
Definic¸a˜o 28. Sejam A e B conjuntos tais que A ⇢ B. O complementar de A em B, CAB
ou CB(A), e´ o conjunto dos elementos que esta˜o em B e que na˜o esta˜o em A.
Em sı´mbolos, (8x) (x 2 CB(A)$ ((A ⇢ B) ^ (x 2 B � A)))
Exemplo 17. Se A = {1; 2; 3; 7; 8; 9}, B = {2; 4; 6; 8} e C = {1; 3; 7; 9}, enta˜o
(1) A \ B = {2; 8};
(2) A [ B = {1; 2; 3; 4; 6; 7; 8; 9};
(3) A� B = {1; 3; 7; 9};
(4) B � A = {4; 6};
(5) CA(C) = {2; 8}.
Definic¸a˜o 29. O conjunto das partes de um conjunto A, P (A) ou P(A), e´ o conjunto
dos subconjuntos de A.
22 CAPI´TULO 2. CONJUNTOS
Exemplo 18. Se A = {0; 1}, enta˜o o conjunto das partes de A e´ o conjunto
P (A) = {?; {0}; {1}; {0; 1}}
Exemplo 19. Se A = {1; 2; 3}, enta˜o o conjunto das partes de A e´ o conjunto
P (A) = {?; {1}; {2}; {3}; {1; 2}; {1; 3}; {2; 3}; {1; 2; 3}}
Observac¸a˜o 5.
n(P (A)) =
✓
n(A)
0
◆
+
✓
n(A)
1
◆
+ · · ·+
✓
n(A)
n(A)
◆
= 2n(A)
Definic¸a˜o 30. O conjunto diferenc¸a sime´trica entre os conjuntos A e B e´ o conjunto
A4B = (A� B) [ (B � A).
Outras propriedades dos conjuntos
(1) A \ A = A (Idempotente);
(2) A [ A = A (Idempotente);
(3) A \? = A (identidade);
(4) A [? = ? (identidade);
(5) A [B = B [ A (comutativa);
(6) A \B = B \ A (comutativa);
(7) (A \ B) \ C = A \ (B \ C) (associativa);
(8) (A [ B) [ C = A [ (B [ C) (associativa);
(9) A \ (B [ C) = (A \B) [ (A \ C) (distributiva);
(10) A [ (B \ C) = (A [B) \ (A [ C) (distributiva);
(11) A \ B = A [B (De Morgan);
(12) A [ B = A \B (De Morgan);
(13) (A� B) [ (A \ B) = A.
2.3. OPERAC¸O˜ES SOBRE CONJUNTOS 23
Demonstrac¸a˜o.
x 2 A
, (x 2 A e x 62 B) ou (x 2 A e x 2 B)
, (x 2 A� B) ou (x 2 A \ B)
, x 2 (A� B) [ (A \B)
Existe uma equivalencia entre sentenc¸as lo´gicas e teoria dos conjuntos que pode ser
traduzida pela seguinte tabela, onde
p : x 2 A e q : x 2 B.
Sentenc¸a equivalente Em conjuntos
p! q A ⇢ B
p ^ q A \ B
p _ q A [ B
Tautologia U
Contradic¸a˜o ?
¬p A
p ^ ¬q A� B
(p! q) ^ (p ^ ¬q) CB(A)
(p ^ ¬q) _ (q ^ ¬p) A4B
De Morgan De Morgan
Exemplo 20. Verifique a validade da relac¸a˜o (A�B)[ (A\B) = A utilizando sentenc¸as
lo´gicas.
E´ suficiente mostrarmos que a sentenc¸a
(p ^ ¬q) _ (p ^ q)$ p
e´ sempre verdadeira
Construindo a tabela verdade para a sentenc¸a acima, obtemos
p q ¬q p ^ ¬q p ^ q (p ^ ¬q) _ (p ^ q) (p ^ ¬q) _ (p ^ q)$ p
V V F F V V V
V F V V F V V
F V F F F F V
F F V F F F V
24 CAPI´TULO 2. CONJUNTOS
Como a coluna que corresponde a sentenc¸a
(p ^ ¬q) _ (p ^ q)$ passume apenas valorac¸a˜o V, enta˜o a relac¸a˜o (A� B) [ (A \ B) = A esta´ correta.
2.4 Princı´pio da Inclusa˜o-Exclusa˜o
O nu´mero de elementos da unia˜o de dois conjuntos e´ igual a soma do nu´mero de elementos
de cada um dos conjuntos subtraı´do do nu´mero de elementos da intersec¸a˜o entre estes
conjuntos.
Em sı´mbolos,
n(A [ B) = n(A) + n(B)� n(A [ B)
Exemplo 21. Durante a Segunda Guerra Mundial, os aliados tomaram um campo de
concentrac¸a˜o nazista e de la´ resgataram 1500 prisioneiros. Desses, 650 estavam com
sarampo, 350 com tuberculose e 700 na˜o tinham nenhuma dessas duas doenc¸as. Qual o
nu´mero de prisioneiros com as duas doenc¸as?
Resoluc¸a˜o gra´fica
S T
x650-x 350-x
700
xy~z}{|xy~z}{|
650 + 350� x+ 700 = 1500
) 1700� x = 1500
) x = 1700� 1500 = 200
Resposta: 200 prisioneiros.
Resoluc¸a˜o alge´brica
n(U) = 1500
n(S) = 650
2.4. PRINCI´PIO DA INCLUSA˜O-EXCLUSA˜O 25
n(T ) = 350
n(S [ T ) = 700
n(U) = n((S [ T ) [ (S [ T ))
) n(U) = n(S [ T ) + n(S [ T )� n((S [ T ) \ (S [ T ))
) n(U) = n(S) + n(T )� n(S \ T ) + n(S [ T )� n(?)
) 1500 = 650 + 350� n(S \ T ) + 700� 0
) 1500 = 1700� n(S \ T )
) n(S \ T ) = 1700� 1500
) n(S \ T ) = 200
Exemplo 22. Objetivando conhecer a prefereˆncia musical dos seus ouvintes, certa emis-
sora de ra´dio realizou uma pesquisa, dando como opc¸a˜o treˆs compositores: M, B e S. Os
resultados sa˜o:
Votos Opc¸o˜es
27 Gostam de B
34 Gostam de M
40 Gostam de S
16 Gostam de B e M
12 Gostam de B e S
14 Gostam de M e S
6 Gostam de B, M e S
4 Na˜o gostam de B, M e S
Qual e´ o nu´mero de pessoas consultadas?
Resoluc¸a˜o alge´brica:
n(B) = 27
n(M) = 34
n(S) = 40
n(B \M) = 16
n(B \ S) = 12
26 CAPI´TULO 2. CONJUNTOS
n(M \ S) = 14
n(B \M \ S) = 6
n(B [M [ S) = 4
n(U) = n((B [M [ S) [ (B [M [ S))
) n(U) = n(B [M [ S) + n(B [M [ S)
) n(U) = n(B [M) [ S) + n(B [M [ S)
) n(U) = n(B [M) + n(S)� n((B [M) \ S) + n(B [M [ S)
) n(U) = n(B) + n(M)� n(B \M) + n(S)
�n((B \ S) [ (M \ S)) + n(B [M [ S)
) n(U) = n(B) + n(M)� n(B \M) + n(S)
�n(B \ S)� n(M \ S) + n((B \ S) \ (M \ S)) + n(B [M [ S)
) n(U) = n(B) + n(M)� n(B \M) + n(S)
�n(B \ S)� n(M \ S) + n(B \M \ S) + n(B [M [ S)
) n(U) = 27 + 34� 16 + 40� 12� 14 + 6 + 4
) n(U) = 111� 42 = 69
Resposta: 69 pessoas consultadas.
Resoluc¸a˜o gra´fica
B M
S 4
6
105 10
86
20
xy~z}{|xy~z}{|xy~z}{|
Resposta: 27 + 10 + 8 + 20 + 4 = 69 pessoas consultadas.
Observac¸a˜o 6. O nu´mero de informac¸o˜es necessa´rias e suficientes para resolver qual-
quer problema utilizando o Princı´pio da Inclusa˜o-Exclusa˜o e´ 2m, onde m e´ o nu´mero de
conjuntos envolvidos diferentes do conjunto universo.
Listas de Exercı´cios sobre Conjuntos
1) Encontre P (A), se
2.4. PRINCI´PIO DA INCLUSA˜O-EXCLUSA˜O 27
(a) A = {1; 2}.
(b) A = {2; 3; 4}.
2) O que se pode dizer sobre o conjunto A se P (A) = {?, {x}, {y}, {x, y}}?
3) Prove que P (A) \ P (B) = P (A \B), onde A e B sa˜o conjuntos arbitra´rios.
4) Mostre que se (A� B) [ (B � A) = A [B, enta˜o A \ B = ?.
Dica: Demonstre por contradic¸a˜o.
5) Prove que se P (A) = P (B), enta˜o A = B.
6) Verifique se as seguintes propriedades de conjuntos sa˜o satisfeitas atrave´s de sentenc¸as
lo´gicas equivalentes:
(a) A� (B [ C) = (A� B) \ (A� C)
(b) A = (A [ B)� B
(c) (A \ B) ⇢ A.
7) SeU = {1, 3, 9, 27, 2, 4, 6, 8, 10, 12, 16, 24} e´ o conjunto universo,A = {1, 2, 3, 6, 12, 24}, B =
{1, 3, 6} e D = {1, 2, 4, 8, 16}, calcule
(a) A�D
(b) D � A
(c) CBA
(d) AC
(e) DC
(f) A [D
28 CAPI´TULO 2. CONJUNTOS
(g) AC \DC
8) Numa escola de 630 alunos, 350 deles estudam Portugueˆs, 210 estudam Espanhol e
90 estudam as duas mate´rias (Portugueˆs e Espanhol). Pergunta-se:
(a) Quantos alunos estudam apenas Portugueˆs?
(b) Quantos alunos estudam apenas Espanhol?
(c) Quantos alunos estudam Portugueˆs ou Espanhol?
(d) Quantos alunos na˜o estudam nenhuma das duas mate´rias?
9) De 200 pessoas que foram pesquisadas sobre suas prefereˆncias em assistir aos cam-
peonatos de corrida pela televisa˜o, foram colhidos os seguintes dados: 55 dos entre-
vistados na˜o assitem; 101 assistem a`s corridas de Fo´rmula 1 e 27 assitem a`s corridas
de Fo´rmula 1 e de Motovelocidade. Quantas das pessoas entrevistadas assistem, ex-
clusivamente, a`s corridas de Motovelocidade?
10) Numa prova constituı´da de dois problemas, 300 alunos acertaram somente um dos
problemas, 260 acertaram o segundo, 100 alunos acertaram os dois e 210 erraram o
primeiro. Quantos alunos fizeram a prova?
11) Um grupo de alunos de uma escola deveria visitar o Museu de Cieˆncia e o Museu
de Histo´ria da cidade. Quarenta e oito alunos foram visitar pelo menos um desses
museus. 20% dos que foram ao de Cieˆncia visitaram o de Histo´ria e 25% dos que
foram ao de Histo´ria visitaram tambe´m o de Cieˆncia. Calcule o nu´mero de alunos
que visitaram os dois museus.
12) Num grupo de 99 esportistas, 40 jogam voˆlei, 20 jogam voˆlei e xadrez, 22 jogam
xadrez e teˆnis, 18 jogam voˆlei e teˆnis, 11 jogam as treˆs modalidades. O nu´mero de
pessoas que jogam xadrez e´ igual ao nu´mero de pessoas que jogam teˆnis. Quantas
jogam:
(a) teˆnis e na˜o jogam voˆlei?
(b) xadrez ou teˆnis e na˜o jogam voˆlei?
2.4. PRINCI´PIO DA INCLUSA˜O-EXCLUSA˜O 29
(c) voˆlei e na˜o jogam xadrez?
13) Analisando-se as carteiras de vacinac¸a˜o das 84 crianc¸as de uma creche, verificou-se
que 68 receberam vacina Sabin, 50 receberam vacina contra sarampo e 12 na˜o foram
vacinadas. Quantas dessas crianc¸as receberam as duas vacinas?
14) 10 000 aparelhos de TV foram examinados depois de um ano de uso, e constatou-se
que 4 000 deles apresentavam problemas de imagem, 2 800 tinham problemas de
som e 3 500 na˜o apresentavam nenhum dos tipos de problemas citados. Qual e´ o
nu´mero de aparelhos que apresentaram somente problemas de imagem?
15) Dos 80 alunos de uma turma, 15 foram reprovados em Matema´tica, 11 em Fı´sica e
10 em Quı´mica. Oito alunos foram reprovados simultaneamente em Matema´tica e
Fı´sica, seis em Matema´tica e Quı´mica e quatro em Fı´sica e Quı´mica. Sabendo que
3 alunos foram reprovados nas treˆs disciplinas, determine quantos alunos na˜o foram
reprovados em nenhuma dessas disciplinas.
16) Numa pesquisa verificou-se que, das pessoas consultadas, 100 liam o jornal A, 150
liam o jornal B, 20 liam os dois jornais (A e B) e 110 na˜o liam nenhum dos jornais.
Quantas pessoas foram consultadas?
17) Seja U = {0, 1, 2, 3, 4, 5, 6, 7, 8} o conjunto universo.
(a) Encontre o conjunto A sabendo que AC = {1, 5, 7, 8}.
(b) Encontre o maior conjunto D satisfazendo D [ C = {1, 4, 5, 6}.
(c) Encontre o conjunto E sabendo que F = {4, 5, 6, 7, 8} e CEF = {4, 8}.
(d) Encontre o conjunto G sabendo que G [ B = {1, 5, 6, 7, 8}, G \ B = {1, 6} e
B = {1, 6, 8}.
18) Demonstre as seguintes propriedades de conjuntos:
(a) (A [ B)C = AC \ BC .
(b) A [B = A, B ⇢ A.
(c) A [ (B \ C) = (A [ B) \ (A [ C).
(d) A = (A� B) [ (A \ B).
30 CAPI´TULO 2. CONJUNTOS
Capı´tulo 3
Te´cnicas de Demonstrac¸a˜o
Uma proposic¸a˜o (ou teorema) do tipo P ! Q e´ formado por um conjunto P de hipo´teses
que sa˜o condic¸o˜es necessa´rias e que, conjuntamente, sa˜o suficientes para se chegar a uma
conclusa˜o (tese) Q.
Dentre as diversas te´cnicas de demonstrac¸a˜o utilizadas, abordaremos as seguintes te´cnicas:
• Te´cnica de demonstrac¸a˜o por exausta˜o;
• Te´cnica de demonstrac¸a˜o direta;
• Te´cnica de demonstrac¸a˜o por contraposic¸a˜o;
• Te´cnica de demonstrac¸a˜o por contradic¸a˜o.
Como ferramenta em algumas demonstrac¸o˜es, abordaremos o Princı´pio de induc¸a˜o
matema´tica.
3.1 Te´cnica de demonstrac¸a˜o por exausta˜o
Esta te´cnica consiste na verificac¸a˜o da validade da proposic¸a˜o P ! Q a partir da verificac¸a˜ode uma quantidade finita de casos particulares.
Exemplo 23. Demonstre que se um nu´mero natural n satisfaz n  2, enta˜o n!  n+ 1.
Demonstrac¸a˜o. Neste caso
P : n  2
31
32 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O
e
Q : n!  n+ 1.
Para n = 0, temos que n! = 0! = 1  1 = 0 + 1 = n+ 1.
Para n = 1, temos que n! = 1! = 1 = 1  2 = 1 + 1 = n+ 1.
Para n = 2, temos que n! = 2! = 2  3 = 2 + 1 = n+ 1.
Logo, por exausta˜o, se n 2 N e n  2, enta˜o n!  n+ 1.
3.2 Te´cnica de demonstrac¸a˜o direta
Esta te´cnica consiste na verificac¸a˜o da validade da proposic¸a˜o P ! Q a partir do cami-
nho natural que se inicia a partir da suposic¸a˜o da validade da hipo´tese P para chegar na
verificac¸a˜o da validade da tese Q.
Utilizaremos as seguintes definic¸o˜es nos pro´ximos exemplos:
Definic¸a˜o 31. Um nu´mero inteiro n e´ um nu´mero par se existir um nu´mero inteiro k tal
que n = 2k.
Definic¸a˜o 32. Um nu´mero inteiro n e´ um nu´mero ı´mpar se existir um nu´mero inteiro k tal
que n = 2k + 1.
Exemplo 24. Demonstre que soma de dois nu´meros pares e´ um nu´mero par.
Demonstrac¸a˜o. Sejam a e b nu´meros pares. Pela definic¸a˜o de nu´mero par, existem k, s 2 Z
tais que a = 2k e b = 2s.
Assim, a+ b = 2k + 2s = 2(k + s), com k + s 2 Z.
Logo a+ b e´ um nu´mero par.
Exemplo 25. Demonstre que o quadrado de um nu´mero par e´ tambe´m e´ um nu´mero par.
Demonstrac¸a˜o. Seja n um nu´mero par, enta˜o, pela definic¸a˜o, existe k 2 Z tal que n = 2k.
Assim, n2 = (2k)2 = 4k2 = 2 · (2k2), com 2k2 2 Z.
Logo n2 e´ um nu´mero par.
Exemplo 26. Demonstre que o quadrado de um nu´mero ı´mpar tambe´m e´ um nu´mero ı´mpar.
3.3. TE´CNICA DE DEMONSTRAC¸A˜O POR CONTRAPOSIC¸A˜O 33
3.3 Te´cnica de demonstrac¸a˜o por contraposic¸a˜o
Esta te´cnica consiste em demonstrarmos a validade da proposic¸a˜o P ! Q a partir da
demonstrac¸a˜o da validade da proposic¸a˜o ¬Q ! ¬P, uma vez que a proposic¸a˜o P ! Q e´
logicamente equivalente a sua contrapositiva ¬Q! ¬P.
Exemplo 27. Se n 2 N satisfaz n! > n+ 1, mostre que n > 2.
Demonstrac¸a˜o. Pelo exemplo 23 mostramos que a seguinte proposic¸a˜o e´ va´lida:
Se n 2 N satisfaz n  2, enta˜o n!  n+ 1.
Logo, sua contrapositiva
Se n 2 N satisfaz n! > n+ 1, enta˜o n > 2.
tambe´m e´ va´lida.
Exemplo 28. Prove que se n2 e´ ı´mpar, enta˜o n e´ ı´mpar.
Demonstrac¸a˜o. Esta proposic¸a˜o e´ logicamente equivalente a sua contrapositiva:
Se n e´ um nu´mero par, enta˜o n2 e´ um nu´mero par.
Portanto, como a proposic¸a˜o acima e´ verdadeira, pelo Exemplo 25, enta˜o a demonstrac¸a˜o
segue por contraposic¸a˜o.
Exemplo 29. Demonstre que se n2 e´ um nu´mero par, enta˜o n e´ um nu´mero par.
3.4 Te´cnica de demonstrac¸a˜o por contradic¸a˜o (ou por ab-
surdo)
Esta te´cnica consiste em demonstrarmos a validade da proposic¸a˜o P ! Q a partir da
suposic¸a˜o de que P e ¬Q sa˜o verdadeiras para chegar em uma afirmac¸a˜o falsa, uma vez
que P ! Q e´ logicamente equivalente a ¬(P ^ ¬Q).
P Q ¬Q P ^ ¬Q P ! Q ¬(P ^ ¬Q)
V V F F V V
V F V V F F
F V F F V V
F F V F V V
34 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O
Exemplo 30. Prove que se x2 = 2, enta˜o x na˜o e´ um nu´mero racional.
Demonstrac¸a˜o. Suponhamos que x 2 Q e x2 = 2. Como x 2 Q, enta˜o x = ab onde a e b
na˜o possuem divisores primos comuns. Assim,
�
a
b
�2
= 2
) a2 = 2b2
) (a e´ par e a2 = 2b2)
) (9k 2 Z) (a = 2k e a2 = 2b2)
) (9k 2 Z) (a = 2k e (2k)2 = 2b2)
) (9k 2 Z) (a = 2k e 2k2 = b2)
) (9k 2 Z) (a = 2k e b e´ par e 2k2 = b2)
) (9s 2 Z) (9k 2 Z) (a = 2k e b = 2s e 2k2 = b2) ,
o que e´ um absurdo, ja´ que 2 seria um nu´mero primo divisor comum de a e b e a e b na˜o
possuem divisores primos comuns.
3.5 Princı´pios de induc¸a˜o matema´tica
Primeiro Princı´pio de Induc¸a˜o Matema´tica
Seja a 2 Z e suponhamos que para cada inteiro n � a esteja associada uma proposic¸a˜o
P (n). Enta˜o P (n) sera´ verdadeira para todo n � a desde que seja possı´vel provar que:
(a) P (a) e´ verdadeira;
(b) Se P (k) e´ verdadeira para k � a, enta˜o P (k + 1) tambe´m e´ verdadeira.
Neste caso, utilizamos a seguinte denominac¸a˜o:
• base de induc¸a˜o: demonstrar que P (a) e´ verdadeira;
• hipo´tese de induc¸a˜o: supor que P (k) e´ verdadeira para algum k � a;
• passo de induc¸a˜o: provar que se P (k) e´ verdadeira enta˜o P (k + 1) tambe´m e´
verdadeira para k � a.
Exemplo 31. Prove por induc¸a˜o que para qualquer n 2 N, vale n < 2n.
3.5. PRINCI´PIOS DE INDUC¸A˜O MATEMA´TICA 35
Exemplo 32. Prove por induc¸a˜o que para qualquer n 2 N, se n > 3, enta˜o 2n < n!.
Exemplo 33. Prove por induc¸a˜o que para qualquer n 2 N, tem-se que
1 + 2 + · · ·+ n = n(n+ 1)
2
Demonstrac¸a˜o. Seja P (n) : 1 + 2 + 3 + · · ·+ n = n(n+1)2 .
Base de Induc¸a˜o:
Como 1 = 1·(1+1)2 , enta˜o P (1) e´ verdadeira.
Hipo´tese de Induc¸a˜o:
Suponhamos que P (k) seja verdadeira.
Passo de Induc¸a˜o:
Como P (k) e´ verdadeira, enta˜o
1 + 2 + 3 + · · ·+ k = k(k + 1)
2
.
Assim,
1 + 2 + 3 + · · ·+ k + (k + 1) = k(k+1)2 + (k + 1)
= (k + 1)
⇥
k
2 + 1
⇤
= (k + 1)
⇥
k+2
2
⇤
= (k+1)((k+1)+1)2 .
Portanto, P (k + 1) e´ verdadeira.
Logo, por induc¸a˜o P (n) : 1 + 2+ 3+ · · ·+ n = n(n+1)2 e´ verdadeira para todo n 2 N⇤.
Outra demonstrac¸a˜o sem utilizar os indicativos
Como 1 = 1·(1+1)2 e supondo 1 + 2 + 3 + · · ·+ k = k(k+1)2 temos que
1 + 2 + 3 + · · ·+ k + (k + 1) = k(k+1)2 + (k + 1)
) 1 + 2 + 3 + · · ·+ k + (k + 1) = (k + 1) ⇥k2 + 1⇤
) 1 + 2 + 3 + · · ·+ k + (k + 1) = (k+1)(k+2)2
) 1 + 2 + 3 + · · ·+ k + (k + 1) = (k+1)((k+1)+1)2
Logo, por induc¸a˜o, 1 + 2 + 3 + · · ·+ n = n(n+1)2 para todo n 2 N.
Exemplo 34. Mostre que n2 > 2n+ 1 para todo n 2 N, n � 3.
Demonstrac¸a˜o. Seja p(n) : n2 > 2n+ 1.
Como 32 = 9 > 7 = 2 · 3 + 1, enta˜o p(3) e´ verdadeira.
36 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O
Suponhamos que p(m) seja verdadeira para algumm � 3. Assim,
m2 > 2m+1) m2+2m+1 > 4m+2 = 2(m+1)+2m > 2(m+1)+1) (m+1)2 > 2(m+1)+1.
Portanto, p(m+ 1) e´ verdadeira.
Logo, por induc¸a˜o, n2 > 2n+ 1 para todo n 2 N, n � 3.
Exemplo 35. Mostre que 1 + 3 + 32 + · · ·+ 3n = 3n+1�12 para todo n 2 N.
Demonstrac¸a˜o. Seja p(n) : 1 + 3 + 32 + · · ·+ 3n = 3n+1�12 .
Como 1 = 3�12 =
30+1�1
2 , enta˜o p(0) e´ verdadeira.
Suponhamos que p(m) seja verdadeira para algumm 2 N.
Assim,
1 + 3 + 32 + · · ·+ 3n = 3n+1�12
) 1 + 3 + 32 + · · ·+ 3n + 3n+1 = 3n+1�12 + 3n+1
) 1 + 3 + 32 + · · ·+ 3n+1 = 3n+1 �12 + 1�� 12
) 1 + 3 + 32 + · · ·+ 3n+1 = 3n+2�12 .
Portanto, p(m+ 1) e´ verdadeira.
Logo, por induc¸a˜o, 1 + 3 + · · ·+ 3n = 3n+1�12 para todo n 2 N.
Segundo Princı´pio de Induc¸a˜o Matema´tica
Seja a 2 Z e suponhamos que para cada inteiro n � a esteja associada uma proposic¸a˜o
P (n). Enta˜o P (n) sera´ verdadeira para todo n � a desde que seja possı´vel provar que:
(a) P (a) e´ verdadeira;
(b) Dado k > a, se P (m) e´ verdadeira para todo m tal que a  m < k, enta˜o P (k) e´
verdadeira.
Exemplo 36. Mostre que qualquer postagem de valor igual ou maior que 12 reais pode
ser formado usando exclusivamente selos de 4 e 5 reais.
Demonstrac¸a˜o. Seja p(n) : n = a · 4 + b · 5, para a, b 2 N.
Assim,
• P (12) e´ verdadeira, pois 12 = 4 + 4 + 4 = 3 · 4 + 0 · 5.
• P (13) e´ verdadeira, pois 13 = 4 + 4 + 5 = 2 · 4 + 1 · 4.
3.5. PRINCI´PIOS DE INDUC¸A˜O MATEMA´TICA 37
• P (14) e´ verdadeira, pois 14 = 4 + 5 + 5 = 1 · 4 + 2 · 5.
• P (15) e´ verdadeira, pois 15 = 5 + 5 + 5 = 0 · 4 + 3 · 5.
Suponhamos que P (m) seja verdadeira para todo m satisfazendo 15  m < k.
Assim, P (k� 4) e´ verdadeira. Portanto, como k� 4 pode ser escrito como somas com
parcelas iguais a 4 e/ou 5, enta˜o k = (k�4)+4 tambe´m pode ser escrito como somas com
parcelas iguais a 4 e/ou 5. Logo P (k) tambe´m e´ verdadeira.
Logo, por induc¸a˜o, P (n) e´ verdadeira para todo nu´mero natural n � 12, ou seja, qual-
quer postagem de valor igualou maior que 12 pode ser formado usando exclusivamente
selos de 4 e 5 reais.
Exemplo 37. Mostre que todo nu´mero natural maior ou igual a 2 ou e´ primo ou pode ser
escrito como produto de nu´meros primos.
Demonstrac¸a˜o. Seja p(n) : n e´ um nu´mero primo ou n pode ser escrito como produto de
nu´meros primos.
Sejam um nu´mero natural maior ou igual a 2.
Sem = 2, enta˜o p(2) e´ verdadeira, pois 2 e´ um nu´mero primo.
Sem > 2 em e´ primo, enta˜o, p(m) e´ verdadeira.
Se m > 2 e m e´ composto, enta˜o existem nu´meros naturais a, b maiores ou iguais a 2
tais quem = a · b. Como a e b sa˜o nu´meros naturais maiores ou iguais a 2, podemos supor
que p(a) e p(b) sejam verdadeiras. Portanto a ou e´ primo ou pode ser escrito como produto
de nu´meros primos e b ou e´ primo ou pode ser escrito como produto de nu´meros primos.
De qualquer forma, concluimos que m e´ o produto de nu´meros primos. Portanto, p(m) e´
verdadeira.
Logo, pelo segundo princı´pio de induc¸a˜o, todo nu´mero natural maior ou igual a 2 ou e´
primo ou pode ser escrito como produto de nu´meros primos.
38 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O
Lista de Exercı´cios sobre Te´cnicas de Demonstrac¸a˜o
Ale´m das definic¸o˜es de nu´mero par e de nu´mero ı´mpar, citadas no texto, para a seguinte
lista de exercı´cios, utilizamos as seguintes definic¸o˜es:
(1) Dizemos que a divide b ou que a e´ um divisor de b ou que b e´ um mu´ltiplo de a se
existir k 2 Z tal que b = ka. Neste caso utilizamos o sı´mbolo a | b.
(2) Dizemos que a e´ congruente a bmo´dulo n ou que a e´ equivalente a bmo´dulo n se
n | (b� a). Neste caso utilizamos o sı´mbolo a ⌘ b mod n.
(3) Dizemos que d = mmc(a, b) se
(a) a | d e b | d.
(b) Para qualquer d0 2 Z, a | d0 e b | d0 ) d | d0.
(4) Dizemos que d = mdc(a, b) se
(a) d | a e d | b.
(b) Para qualquer d0 2 Z, d0 | a e d0 | b) d0 | d.
(5) Se d = mdc(a, b), enta˜o d e´ o menor inteiro positivo satisfazendo
d = x · a+ y · b,
para x, y 2 Z.
(6) Dizemos que um nu´mero inteiro p > 1 e´ um nu´mero primo se os u´nicos divisores
inteiros positivos de p sa˜o 1 e p.
Te´cnica de Demonstrac¸a˜o Direta
1) Sejam a, b e c inteiros. Se a | b e b | c, enta˜o a | c.
2) Se x e´ um inteiro par, enta˜o x2 � 6x+ 5 e´ ı´mpar.
3) Se a, b, c 2 N, enta˜o mmc(ca, cb) = c ·mmc(a, b).
4) Sejam x e y nu´meros positivos. Se x  y, enta˜o px  py.
5) Se x e y sa˜o nu´meros reais positivos, enta˜o 2pxy  x+ y.
3.5. PRINCI´PIOS DE INDUC¸A˜O MATEMA´TICA 39
6) Se n 2 N, enta˜o 1 + (�1)n(2n� 1) e´ um mu´ltiplo de 4.
7) Todo mu´ltiplo de 4 tem a forma 1 + (�1)n(2n� 1) para algum n 2 N.
8) Suponha que x, y 2 Z. Se x e y sa˜o pares, enta˜o xy e´ par.
9) Suponha que x, y 2 Z. Se x e y sa˜o ı´mpares, enta˜o xy e´ ı´mpar.
10) Suponha que a, b, c 2 Z. Se a | b e a | c, enta˜o a | (b+ c).
11) Suponha que a, b 2 Z. Se a | b, enta˜o a2 | b2.
12) Seja a um inteiro. Se 5 | 2a, enta˜o 5 | a.
13) Seja a um inteiro. Se 7 | 4a, enta˜o 7 | a.
14) Sejam a, b 2 Z. Se a | b, enta˜o a | (3b3 � b2 + 5b).
15) Sejam a, b, c, d 2 Z. Se a | b e c | d, enta˜o ac | bc.
16) Se x 2 R e 0 < x < 4, enta˜o 4
x(4� x) � 1.
17) Se n 2 Z, enta˜o 5n2 + 3n+ 7 e´ ı´mpar.
18) Se n 2 Z, enta˜o n2 + 3n+ 4 e´ par.
19) Sejam a, b e c inteiros. Se a2 | b e b3 | c, enta˜o a6 | c.
20) Se n 2 N e n � 2, enta˜o os nu´meros n! + 2, n! + 3, n! + 4, · · · , n! + n sa˜o todos
compostos. Consequentemente, para qualquer n � 2, podemos encontrar n consecu-
tivos nu´meros compostos. Isto significa que existe um arbitrariamente largo deserto
de nu´meros primos.
21) Todo nu´mero inteiro ı´mpar e´ diferenc¸a de dois quadrados.
Te´cnica de demonstrac¸a˜o por contraposic¸a˜o
22) Seja x 2 Z. Se 7x+ 9 e´ par, enta˜o x e´ ı´mpar.
23) Se x2 � 6x+ 5 e´ par, enta˜o x e´ ı´mpar.
24) Sejam x, y 2 R. Se y3 + yx2  x3 + xy2, enta˜o y  x.
25) Sejam x, y 2 Z Se 5 - xy, enta˜o 5 - x e 5 - y.
40 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O
26) Sejam a, b 2 Z e n 2 N. Se a ⌘ b( mod n), enta˜o a2 ⌘ b2(modn).
27) Sejam a, b 2 Z e n 2 N. Se 12a 6⌘ 12b(modn), enta˜o n - 12.
28) Seja x 2 R. Se x2 + 5x < 0, enta˜o x < 0.
29) Seja x 2 R. Se x3 � x > 0, enta˜o x > �1.
30) Sejam x, y, z 2 Z e x 6= 0. Se x - yz, enta˜o x - y e x - z.
31) Se n 2 N e 2n � 1 e´ primo, enta˜o n e´ primo.
32) Se n 2 Z, enta˜o 4 - (n2 � 3).
Te´cnica de demonstrac¸a˜o por contradic¸a˜o
33) Se a, b 2 Z, enta˜o a2 � 4b 6= 2.
34) Existem infinitos nu´meros primos.
35) Para todo nu´mero real x 2 [0, ⇡/2], temos sen x+ cosx � 1.
36) Prove que 3
p
2 e´ irracional.
37) Se a, b 2 Z, enta˜o a2 � 4b� 2 6= 0.
38) Para todo n 2 Z, 4 - (n2 + 2).
39) Na˜o existem nu´meros inteiros a e b tal que 18a+ 6b = 1.
Princı´pio de Induc¸a˜o Matema´tica
40) Se n 2 N, enta˜o 1 + 3 + 5 + 7 + · · ·+ (2n� 1) = n2.
41) Se n e´ um inteiro na˜o-negativo, enta˜o 5 | (n5 � n).
42) Se n 2 Z e n � 0, enta˜oPni=0 i · i! = (n+ 1)!� 1.
43) Se n 2 N, enta˜o (1 + x)n � 1 + nx para todo x 2 R com x > �1.
44) Se n 2 N e n � 1, enta˜o
1 + 2 + 3 + 4 + · · ·+ n = n
2 + n
2
.
3.5. PRINCI´PIOS DE INDUC¸A˜O MATEMA´TICA 41
45) Para todo inteiro n � 1,
12 + 22 + 32 + · · ·+ n2 = n(n+ 1)(2n+ 1)
6
.
46) Para todo inteiro n 2 N,
nX
i=1
(8i� 5) = 4n2 � n.
47) Se n 2 N, enta˜o
1 · 3 + 2 · 4 + 3 · 5 + · · ·+ 4 · 6 + · · ·+ n(n+ 2) = n(n+ 1)(2n+ 7)
6
.
48) Se n 2 N, enta˜o
1
2!
+
2
3!
+ · · ·+ n
(n+ 1)!
= 1� 1
(n+ 1)!
49) Para qualquer inteiro n � 0, prove que 9 | (43n + 8).
50) Prove que para todo nu´mero natural n,
2n + 1  3n.
Observac¸a˜o: Nas demonstrac¸o˜es destes exercı´cios e´ va´lido citar qualquer resultado
conhecido, desde que a demonstrac¸a˜o deste resultado na˜o seja equivalente a demonstrac¸a˜o
do exercı´cio.
Resposta dos Exercı´cios sobre Te´cnicas de Demonstrac¸a˜o
1) Como a | b e b | c, enta˜o existem r, s 2 Z tais que b = ra e c = sb. Assim,
c = sb = s(ra) = (sr)a
com sr 2 Z. Logo a | c.
2) Como x e´ par, enta˜o existe k 2 Z tal que x = 2k. Assim,
x2 � 6x+ 5 = (2k)2 � 6 · (2k) + 5 = 4k2 � 12k + 5 = 2(2k2 � 6k + 2) + 1,
com 2k2 � 6k + 2 2 Z.
Logo x2 � 6x+ 5 e´ ı´mpar.
42 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O
3) Sejam d1 = mmc(a, b) e d2 = mmc(ac, bc).
Se d1 = mmc(a, b), enta˜o
a | d1 e b | d1
) ac | cd1 e bc | cd1
) d2 | cd1
Se d2 = mmc(ac, bc), enta˜o
ac | d2 e bc | d2
) d2 = kc, ac | kc e bc | kc
) d2 = kc, a | k e b | k
) d2 = kc e d1 | k
) cd1 | kc
) cd1 | d2
Logo, como d2 | cd1 e cd1 | d2, enta˜o d2 = cd1, ou seja, mmc(ac, bc) = cmmc(a, b).
4) Como
p
x+
p
y > 0, enta˜o 1py+px > 0. Ale´m disso, como x  y, enta˜o y � x � 0.
Logo, py � px = (
p
y�px)(py+px)
(
p
y+
p
x) =
1p
y+
p
x · (y � x) � 0, o que implica emp
x <
p
y.
10) Como a | b e a | c, enta˜o existem k1, k2 2 Z tais que b = k1a e c = k2a, o que
implica em b+ c = (k1 + k2)a com k1 + k2 2 Z.
Logo a | (b+ c).
Capı´tulo 4
Relac¸o˜es e Func¸o˜es
Definic¸a˜o 33. Sejam A e B conjuntos. Uma relac¸a˜o R de A em B e´ um subconjunto do
produto cartesiano de A por B,
A⇥ B = {(a, b) | a 2 A, b 2 B}.
Exemplo 38. Se A = {1; 2} e B = {1; 3; 5}, enta˜o
A⇥ B = {(1; 1); (1; 3); (1; 5); (2; 1); (2; 3); (2; 5)}
e teremos 2n(A⇥B) = 26 = 64 relac¸o˜es deA emB.Uma destas relac¸o˜es e´R = {(1; 3); (2; 5); (2; 3)}.
Relac¸o˜es sobre um conjunto
Definic¸a˜o 34. Uma relac¸a˜o R sobre A e´ uma relac¸a˜o de um conjunto A em A.
Definic¸a˜o 35. Seja R uma relac¸a˜o sobre A.
(1) Se (8a 2 A) ((a, a) 2 R) , enta˜o R e´ chamada de relac¸a˜o reflexiva.
(2) Se (a, b) 2 R implicar em (b, a) 2 R para todos a, b 2 A, enta˜o R e´ chamada de
relac¸a˜o sime´trica.
(3) Se (a, b) 2 R e (b, c) 2 R implicarem em (a, c) 2 R para todo a, b, c 2 A, enta˜o R
e´ chamada de relac¸a˜o transitiva.
(4) Se (a, b) 2 R e (b, a) 2R implicarem em a = b, enta˜o R e´ chamada de relac¸a˜o
anti-sime´trica.
(5) Uma relac¸a˜o R e´ uma relac¸a˜o de equivaleˆncia, se R satisfaz as propriedades (1),
(2) e (3), ou seja, se R e´ reflexiva, sime´trica e transitiva.
43
44 CAPI´TULO 4. RELAC¸O˜ES E FUNC¸O˜ES
5
7 3
1
77ooooooooooooooooooooooooooooo
2
SS''''''''''''''''''''''''''
??����������������
Figura 4.1: R(A)
(6) Uma relac¸a˜o R e´ uma relac¸a˜o de ordem parcial, se R satisfaz as propriedades (1),
(3) e (4), ou seja, se R e´ reflexiva, anti-sime´trica e transitiva.
Se A e B sa˜o conjuntos finitos, enta˜o toda relac¸a˜o R de A em B pode ser representada
por um grafo direcionado cujos ve´rtices sa˜o os pontos de A e de B e cujas arestas sa˜o
representadas por pares (a, b) 2 R que representa uma aresta orientada de a para b.
Exemplo 39. Se A = {1; 2} e B = {3; 5; 7}, enta˜o a relac¸a˜o R de A em B definida por
R = {(1; 3); (2; 5); (2; 3)}
pode ser representada graficamente pelo grafo da figura 3.1.
Definic¸a˜o 36. Um ciclo e´ uma aresta que conecta um ve´rtice nele mesmo.
Observac¸a˜o 7. Graficamente:
• Uma relac¸a˜o R sobre A e´ reflexiva se existem ciclos em cada elemento de A;
• Uma relac¸a˜o R sobre A e´ sime´trica se na˜o existem setas simples ligando elementos
de A;
• Uma relac¸a˜o R sobre A e´ transitiva se para todo caminho ligando dois pontos a e b
de A, existe uma seta ligando a e b;
• Uma relac¸a˜oR sobreA e´ anti-sime´trica se na˜o existem setas duplas ligando elemen-
tos de A.
Exemplo 40. Se R = {(a, b) 2 N ⇥ N | a | b}, enta˜o R e´ uma relac¸a˜o de ordem parcial
sobre N.
De fato,
45
(i) Se a 2 A, enta˜o a = 1 · a, i.e., a e´ mu´ltiplo de a. Logo (a, a) 2 R. Portanto R e´
reflexiva.
(ii) Sejam a, b, c 2 A tais que (a, b), (b, c) 2 R. Assim b e´ mu´ltiplo de a e c e´ mu´ltiplo
de b. Logo existem r, s 2 Z tais que b = ra e c = sb. Portanto c = rb = s(ra) =
(sr)a, onde sr 2 Z, ou seja, c e´ mu´ltiplo de a. Consequentemente, (a, c) 2 R. Logo
(8a, b, c 2 A) (((a, b), (b, c) 2 R)) ((a, c) 2 R)) .
Portanto, R e´ transitiva. Simbolicamente, se a, b, c 2 N,
((a, b) 2 R e (b, c) 2 R)
) (b e´ mu´ltiplo de a e c e´ mu´ltiplo de b)
) (9r, s 2 Z) (b = ra e c = sb)
) (9r, s 2 Z) (c = sb = s(ra) = (sr)a)
t=sr) (9t 2 Z) (c = ta)
) (c e´ mu´ltiplo de a)
) ((a, c) 2 R)
Logo R e´ transitiva.
(iii) Sejam a, b 2 N tais que (a, b) 2 R e (b, a) 2 R, enta˜o existem r, s 2 Z tais que
b = ra e a = rb.
Assim, b = ra = r(sb) ) b(1 � rs) = 0 ) 1 � rs = 0 ) rs = 1 ) r = s =
±1 a,b>0) r = s = 1. Logo b = a. Portanto, R e´ anti-sime´trica.
Logo, por (i), (ii) e (iii), R e´ uma relac¸a˜o de ordem parcial sobre A.
Exemplo 41. Seja A um conjunto. Se R = {(B,C) 2 P (A) ⇥ P (A) | B ⇢ C}, enta˜o R
e´ uma relac¸a˜o de ordem parcial sobre P (A).
De fato,
(i) Como B ⇢ B para todo B ⇢ A, enta˜o (B,B) 2 R para todo B 2 P (A). Logo R e´
reflexiva.
(ii) Sejam B,C 2 P (A), tais que (B,C) 2 R e (C,B) 2 R. Assim, B ⇢ C e C ⇢ B, o
que implica em B = C. Logo R e´ anti-sime´trica.
(iii) Sejam B,C,D 2 P (A) tais que (B,C) 2 R e (C,D) 2 R, enta˜o B ⇢ C e C ⇢ D,
o que implica em B ⇢ D. Assim, (B,D) 2 R. Logo R e´ transitiva.
46 CAPI´TULO 4. RELAC¸O˜ES E FUNC¸O˜ES
ComoR e´ reflexiva, anti-sime´trica e transitiva, enta˜oR e´ uma relac¸a˜o de ordem parcial
sobre P (A).
Exemplo 42. Sejam A e B conjuntos disjuntos e R uma relac¸a˜o de ordem sobre A [ B
definida por
R = {(a, b) 2 (A [ B)⇥ (A [B) | {a, b} ⇢ A ou {a, b} ⇢ B},
enta˜o R e´ uma relac¸a˜o de equivaleˆncia sobre A [B.
De fato, como
(1) Se a 2 A [ B, enta˜o {a, a} ⇢ A ou {a, a} ⇢ B. Logo (a, a) 2 R. Portanto R e´
reflexiva.
(2) Se (a, b) 2 R, enta˜o {a, b} ⇢ A ou {a, b} ⇢ B. Logo {b, a} ⇢ A ou {b, a} ⇢ B, o
que implica em (b, a) 2 R. Portanto R e´ sime´trica.
(3) Se (a, b) 2 R e (b, c) 2 R, enta˜o {a, b} ⇢ A ou {a, b} ⇢ B e {b, c} ⇢ A ou
{b, c} ⇢ B. Como A \ B = ?, enta˜o {a, b} ⇢ A e {b, c} ⇢ A ou {a, b} ⇢ B e
{b, c} ⇢ B. Logo {a, c} ⇢ A ou {a, c} ⇢ B, o que implica em (a, c) 2 R. Portanto,
R e´ transitiva
Logo, por (1), (2) e (3), R e´ uma relac¸a˜o de equivaleˆncia.
Definic¸a˜o 37. Dizemos que R⇤ e´ o fecho de uma relac¸a˜o R por uma propriedade P se R⇤
e´ a menor relac¸a˜o que conte´m R e que satisfaz a propriedade P, ou seja, se
(i) R⇤ satisfaz a propriedade P ;
(ii) R ⇢ R⇤;
(iii) Se S satisfaz a propriedade P e R ⇢ S, enta˜o R⇤ ⇢ S.
Exemplo 43. Encontre os fechos reflexivo, sime´trico e transitivo deR = {(1; 2); (2; 1); (1; 3)}
sobre S = {1; 2; 3}.
O fecho reflexivo de R sobre S e´
R⇤ = {(1; 2); (2; 1); (1; 3); (1; 1); (2; 2); (3; 3)}
47
O fecho sime´trico de R sobre S e´
R⇤ = {(1; 2); (2; 1); (1; 3); (3; 1)}
O fecho transitivo de R sobre S e´
R⇤ = {(1; 2); (2; 1); (1; 3); (1; 1); (2; 3); (2; 2)}
Definic¸a˜o 38. Se R e´ uma relac¸a˜o de equivaleˆncia sobre um conjunto A, enta˜o, para cada
x 2 A podemos definir uma classe de equivaleˆncia para esta relac¸a˜o R como sendo o
conjunto
[x] = {a 2 A | (a, x) 2 R}
Notac¸a˜o 1. O conjunto das classes de equivaleˆncia de uma relac¸a˜o R sobre um conjunto
A e´ representado pelo sı´mbolo A/R.
Lista de Exercı´cios sobre Relac¸o˜es
(1) Mostre que a relac¸a˜o R definida por
R = {(a, b) 2 Z⇥ Z | a ⌘ b mod 5}
e´ uma relac¸a˜o de equivaleˆncia e encontre Z/R.
(2) Seja Y = {0, 1} eM o conjunto de todas as palavras de comprimento finito formada
a partir de 0 e 1.Mostre que a relac¸a˜o R definida por
R = {(a, b) 2M ⇥M | a e´ prefixo de b}
e´ uma relac¸a˜o de ordem parcial.
Obs: Dizemos que a e´ prefixo de b se existe c 2M tal que b = ac.
(3) Seja X = {0; 1; 2; 3; 4}. Mostre que a relac¸a˜o R sobre P (X) definida por
R = {(A,B) 2 P (X)⇥ P (X) | n(A) = n(B)}
e´ uma relac¸a˜o de equivaleˆncia e encontre P (X)/R.
(4) Encontre todas as relac¸o˜es de equivaleˆncia sobre A = {1; 2; 3}.
(5) Encontre todas as relac¸o˜es de ordem sobre A = {1; 2; 3}.
48 CAPI´TULO 4. RELAC¸O˜ES E FUNC¸O˜ES
(6) Construir sobre o conjunto E = {a, b, c, d} relac¸o˜es R1, R2, R3 e R4 tais que R1
so´ tem a propriedade reflexiva, R2 so´ a sime´trica, R3 so´ a transitiva e R4 so´ a anti-
sime´trica.
(7) Seja A = {x 2 Z | |x|  5} a relac¸a˜o definida por (x, y) 2 R, x2+2x = y2+2y.
Mostre que R e´ uma relac¸a˜o de equivaleˆncia.
(8) Sejam E = {�3,�2,�1, 0, 1, 2, 3} e R = {(x, y) 2 E ⇥ E | x + |x| = y + |y|}.
Mostre que R e´ uma relac¸a˜o de equivaleˆncia e encontre E/R.
(9) SejaR a relac¸a˜o sobreQ definida da forma seguinte (x, y) 2 R, x�y 2 Z. Provar
que R e´ uma relac¸a˜o de equivaleˆncia.
(10) Seja R = {(x, y) 2 R2 | x� y 2 Q}. Provar que R e´ uma relac¸a˜o de equivaleˆncia.
4.1 Func¸o˜es
Definic¸a˜o 39. Uma func¸a˜o f de A em B e´ uma relac¸a˜o que associa a cada elemento x do
conjunto A um u´nico elemento y do conjunto B. Como este elemento y 2 B e´ u´nico para
cada x 2 A, enta˜o e´ comum representarmos este elemento por f(x), ou seja, y = f(x).
Notac¸a˜o 2. Usamos o sı´mbolo f : A! B para representarmos que f e´ uma func¸a˜o de A
em B.
Definic¸a˜o 40. Seja f : A! B, enta˜o
• O domı´nio de f e´ o conjunto
Dom(f) = A
• O contradomı´nio de f e´ o conjunto
CDom(f) = B
• A imagem de f e´ o conjunto
Im(f) = {y 2 B | y = f(x) para algum x 2 A}
Definic¸a˜o 41. Func¸o˜es reais sa˜o func¸o˜es f : A! B, onde A ⇢ R e B = R.
4.1. FUNC¸O˜ES 49
Quando precisamos encontrar o domı´nio de uma func¸a˜o real f dada por uma fo´rmula
matema´tica significa que precisamos encontrar o maior subconjunto A de R de tal forma
que fac¸a sentido definirmos f como sendo uma func¸a˜o de A em R.
Exemplo 44. Encontre o domı´nio e a imagem da func¸a˜o real f(x) = x2.
Neste caso, Dom(f) = R e Im(f) = R+.
Exemplo 45. Encontre o domı´nio e a imagem de f(x) =
p
x� 1.
Como na˜o existem raı´zes reais de nu´meros negativos, enta˜o x� 1 � 0) x � 1.
Assim, Dom(f) = [1;+1[= {x 2R | x � 1} e
Im(f) =]0;+1[= {y 2 R | y � 0}.
Exemplo 46. Encontre o domı´nio e a imagem de f(x) =
q
1+x
1�x .
A condic¸a˜o de existeˆncia para que f seja uma func¸a˜o real e´ que
1+x
1�x � 0
1� x 6= 0
Como
1 + x � 0 e 1� x > 0) �1  x < 1
e
1 + x  0 e 1� x < 0
e´ possı´vel.
Logo, Dom(f) = {x 2 R | �1  x < 1} e Im(f) = R+.
Definic¸a˜o 42. Uma func¸a˜o f : A! B e´ sobrejetora ou sobrejetiva se Im(f) = B.
Exemplo 47. Uma func¸a˜o f : R ! R⇤+ definida por f(x) = x2 e´ sobrejetora, pois
Im(f) = R+ = CDom(f).
Definic¸a˜o 43. Uma func¸a˜o f : A! B e´ injetora ou injetiva se
(8x, y 2 A) (f(x) = f(y)) x = y)
ou, equivalentemente, se
(8x, y 2 A) (x 6= y ) f(x) 6= f(y))
50 CAPI´TULO 4. RELAC¸O˜ES E FUNC¸O˜ES
Exemplo 48. Uma func¸a˜o f : R! R definida por f(x) = 2x e´ injetora, pois
(8a, b 2 R) �2a = 2b ) a = b� .
Definic¸a˜o 44. Uma func¸a˜o f : A ! B e´ bijetora ou bijetiva se f for injetora e sobreje-
tora.
Exemplo 49. A func¸a˜o real f(x) = 2x+ 3 e´ bijetora, pois
• f e´ injetora: (8a, b 2 R) (f(a) = f(b)) 2a+ 3 = 2b+ 3) 2a = 2b) a = b) e
• f e´ sobrejetora: (8c 2 R) �f � c�32 � = 2 c�32 + 3 = c� 3 + 3 = c� .
Logo f e´ bijetora.
Definic¸a˜o 45. Sejam f : A ! B e g : C ! D func¸o˜es tais que B ⇢ C. A func¸a˜o
composta de g e f e´ uma func¸a˜o g � f : A! D tal que (g � f)(x) = g(f(x)).
Exemplo 50. Se f(x) = 1x e g(x) =
p
x, enta˜o (f � g)(x) = 1px .
Definic¸a˜o 46. Seja f : A ! B uma func¸a˜o injetiva. A func¸a˜o inversa de f e´ uma func¸a˜o
f�1 : Im(f)! A tal que f�1(y) = x) f(x) = y.
Exemplo 51. Calcule f�1, onde f(x) = 2x� 5.
Definic¸a˜o 47. Sejam f : A ! B e g : C ! B com C ✓ A. Dizemos que g e´ a restric¸a˜o
de f ao conjunto C se
g(x) = f(x), 8x 2 C.
Notac¸a˜o 3. Utilizamos g = f |C quando g e´ a restric¸a˜o de f ao subconjunto C do domı´nio
de f.
Exemplo 52. Seja f : N! N definida por f(n) = (�1)n. Se S e´ o conjunto dos nu´meros
pares, enta˜o g : S ! N definida por g(n) = 1 e´ uma restric¸a˜o de f ao subconjunto S de
N.
Definic¸a˜o 48. Sejam f : A! B e g : C ! D com A ✓ C e B ✓ D. Dizemos que g e´ um
prolongamento (ou extensa˜o ) de f se
f(x) = g(x), 8x 2 A.
Exemplo 53. Se f : R � {1} ! R e g : R ! R sa˜o definidas por f(x) = x2�1x�1 e
g(x) = x+ 1, enta˜o g e´ um prolongamento (ou extensa˜o) de f.
4.1. FUNC¸O˜ES 51
Lista de Exercı´cios sobre Func¸o˜es
1) Prove que se f : A! B e´ sobrejetora, enta˜o existe C ✓ A com f |C bijetora.
2) Prove que se f : A! B e´ bijetora, enta˜o a aplicac¸a˜o inversa f�1 : B ! A tambe´m
e´ bijetora.
3) Prove que se f : A! B e´ injetora e B for finito, enta˜o A tambe´m e´ finito.
4) Prove que se f : A! B e´ sobrejetora e A for finito, enta˜o B tambe´m e´ finito.
5) Prove que se f : A! B e g : B ! C sa˜o aplicac¸o˜es injetoras, enta˜o g � f : A! C
tambe´m e´ uma aplicac¸a˜o injetora.
6) Prove que se f : A! B e g : B ! C sa˜o aplicac¸o˜es sobrejetoras, enta˜o g �f : A!
C tambe´m e´ uma aplicac¸a˜o injetora.
7) Prove que se f : A! B e g : B ! C sa˜o aplicac¸o˜es bijetoras, enta˜o g � f : A! C
tambe´m e´ uma aplicac¸a˜o bijetora.
52 CAPI´TULO 4. RELAC¸O˜ES E FUNC¸O˜ES
Capı´tulo 5
Ana´lise Combinato´ria
5.1 Princı´pio das Casas de Pombo
Definic¸a˜o 49 (Princı´pio das Casas de Pombo). Se mais de k itens sa˜o colocados em k
caixas, enta˜o pelo menos uma caixa conte´m mais de um item.
Exemplo 54. Quantas pessoas precisam estar presentes em uma sala para garantir que
duas delas tenham o u´ltimo nome comec¸ando com a mesma letra?
Exemplo 55. Prove que, se quatro nu´meros forem escolhidos do conjunto {1, 2, 3, 4, 5, 6},
pelo menos um par tem que somar 7.
Exemplo 56. Quantas pessoas devera˜o estudar numa escola para garantir que pelo menos
2 destas pessoas tenham nascido:
• no mesmo meˆs?
• no mesmo dia da semana?
• no mesmo meˆs e no mesmo dia da semana?
• no mesmo meˆs e no mesmo dia?
• no mesmo dia e no mesmo dia da semana?
• no mesmo meˆs, no mesmo dia da semana e no mesmo dia?
53
54 CAPI´TULO 5. ANA´LISE COMBINATO´RIA
5.2 Princı´pio Fundamental da Contagem
5.2.1 Princı´pio da Multiplicac¸a˜o
Se uma decisa˜o d1 pode ser tomada de x maneiras e se, uma vez tomada a decisa˜o d1, a
decisa˜o d2 puder ser tomada em y maneiras enta˜o o nu´mero de maneiras de se tomarem as
deciso˜es d1 e d2 e´ xy.
5.2.2 Princı´pio da Soma
Se uma decisa˜o d1 pode ser tomada de x maneiras e uma decisa˜o d2 pode ser tomada de y
maneiras e estas deciso˜es sa˜o tomadas de forma independente (disjuntas), enta˜o o nu´mero
de maneiras distintas de se tomarem as deciso˜es d1 ou d2 e´ x+ y.
Exemplo 57. Numa sala ha´ 3 homens e 4 mulheres. De quantos modos e´ possı´vel selecio-
nar um casal homem-mulher?
Resposta: 3|{z}
homens
· 4|{z}
mulheres
= 12.
Exemplo 58. Para fazer uma viagem Rio-Sa˜o Paulo-Rio, posso usar como transporte o
trem, o oˆnibus ou o avia˜o. De quantos modos posso escolher os transportes se na˜o desejo
usar na volta o mesmo meio de transporte usado na ida?
Resposta: 3|{z}
ida
· 2|{z}
volta
= 6.
Exemplo 59. As placas dos automo´veis sa˜o formadas por duas letras (num alfabeto de 26
letras) seguidas por quatro algarismos. Quantas placas podem ser formadas?
Resposta: 26| {z }
1a letra
· 26| {z }
2a letra
· 10| {z }
1oalgarismo
· 10| {z }
2oalgarismo
· 10| {z }
3oalgarismo
· 10| {z }
4oalgarismo
= 6 760 000.
Exemplo 60. De quantos modos 3 pessoas podem sentar-se em 5 cadeiras em fila?
Resposta: 5| {z }
1a pessoa
· 4| {z }
2a pessoa
· 3| {z }
3apessoa
= 60.
Exemplo 61. Quantos nu´meros diferentes podem ser formados multiplicando alguns (ou
todos) dos nu´meros 1, 5, 6, 7, 7, 9, 9, 9?
5.2. PRINCI´PIO FUNDAMENTAL DA CONTAGEM 55
Resposta: Os nu´meros formados multiplicando alguns (ou todos) dos nu´meros 1, 5, 6, 7, 7, 9, 9, 9
teˆm a forma
n = 5m1 · 6m2 · 7m3 · 9m4 ,
ondem1 2 {0, 1},m2 2 {0, 1},m3 2 {0, 1, 2} em4 2 {0, 1, 2, 3}.
Logo,
2| {z }
m1
· 2| {z }
m2
· 3| {z }
m4
· 4| {z }
m5
= 48.
Exemplo 62. A selec¸a˜o brasileira de futebol ira´ disputar um torneio internacional com
outras cinco selec¸o˜es, no sistema “todos jogam contra todos uma u´nica vez”. Quais as
possı´veis sequeˆncias de resultados – vito´ria (V), empate (E) e derrota (D) – da equipe
brasileira nesse torneio?
Exemplo 63. No primeiro semestre de 2012 sera˜o oferecidas quatro turmas de Ca´lculo I,
treˆs turmas de Geometria Analı´tica, duas turmas de Fundamentos de Matema´tica Elemen-
tar e apenas uma turma de Introduc¸a˜o a` Lo´gica Matema´tica. Sabendo-se que um calouro
aprovado para o curso de Matema´tica devera´ cursar todas as disciplinas acima mencio-
nadas, de quantas maneiras distintas ele podera´ se matricular nas mesmas, levando-se em
considerac¸a˜o que as turmas de uma mesma disciplina sa˜o oferecidas num mesmo hora´rio
e na˜o existe coincideˆncia de hora´rios entre as disciplinas?
Exemplo 64. (a) Quantos nu´meros de cinco algarismos existem?
(b) Quantos nu´meros ı´mpares de cinco algarismos existem?
(c) Quantos nu´meros pares de cinco algarismos distintos existem?
Exemplo 65. Um dado foi lanc¸ado n vezes sucessivamente. Sabendo-se que o nu´mero de
sequeˆncias de faces possı´veis de se obter e´ 368, qual e´ o valor de n?
Exemplo 66. Para os ho´spedes que desejam tomar cafe´ da manha˜ no quarto, um hotel
oferece as seguintes opc¸o˜es:
• bebidas quentes: chocolate, cafe´ puro, cha´ e cafe´ com leite.
• sucos: laranja e abacaxi.
• pa˜es: croissant, pa˜o franceˆs, pa˜o de foˆrma e pa˜o integral.
56 CAPI´TULO 5. ANA´LISE COMBINATO´RIA
• queijo: branco, mussarela e queijo prato.
O ho´spede X fez a seguinte solicitac¸a˜o: um suco, um pa˜o e um tipo de queijo. O
ho´spede Y pediu: uma bebida quente ou um suco, um pa˜o e um tipo de queijo. De quantas
formas distintas cada ho´spedepodera´ ser servido?
Exemplo 67. Num hospital existem 3 portas de entrada que da˜o para um amplo sagua˜o no
qual existem 5 elevadores. Um visitante deve se dirigir ao 6o
¯
andar, utilizando-se de um
dos elevadores. De quantas maneiras diferentes podera´ fazeˆ-lo?
Exemplo 68. Numa eleic¸a˜o de uma escola ha´ treˆs candidatos a presidente, cinco a vice-
presidente, seis a secreta´rio e sete a tesoureiro. Quantos podem ser os resultados da
eleic¸a˜o?
5.3 Outros Me´todos de Contagem
Exemplo 69. Dois preˆmios sa˜o sorteados entre 10 pessoas. Quantos sera˜o os possı´veis
resultados, sabendo que uma pessoa na˜o pode ser sorteada mais de uma vez?
5.4 Caso sem te´cnica conhecida
Caso sem te´cnica conhecida
Quero retirar 100 reais de um caixa eletroˆnico que dispo˜e de notas de 5 e 10 reais. Quantas
sera˜o as possibilidades para este saque?
5.5 Fatorial
Fatorial de um nu´mero natural
O Fatorial de um nu´mero natural n e´ definido matema´ticamente por
n! =
8<: 1 se n = 0n(n� 1)! se n 2 N⇤
Exercı´cio 2. Calcule o valor de:
5.6. AGRUPAMENTOS 57
a)
7!
5! · 2! d)
15! · 4!
13! · 3!
b)
8! · 6!
7! · 7! e)
21!� 3 · 20!
19!
c) 17!� 17 · 16!
Exercı´cio 3. Resolva as seguintes equac¸o˜es:
(a)
n!
(n� 1)! = 4
(b)
(n� 1)!(n+ 1)!
(n!)2
=
5
4
(c) (n!)2 � 100n! = 2400
5.6 Agrupamentos
Tipos de Agrupamentos
Existem treˆs tipos de Agrupamentos de k elementos distintos escolhidos entre n disponı´veis
que podem ser obtidos a partir do Princı´pio Fundamental da Contagem:
(a) Arranjos (a ordem importa);
(b) Permutac¸o˜es (arranjos, onde k=n);
(c) Combinac¸o˜es (a ordem na˜o importa).
5.6.1 Arranjos
Arranjos
Definic¸a˜o 50. Dado um conjunto com n elementos distintos, chama-se arranjo dos n ele-
mentos, tomados k a k, a qualquer sequeˆncia ordenada de k elementos distintos escolhidos
entre os n existentes.
Obtenc¸a˜o da Fo´rmula:
Pelo PFC:
| {z }
n modos
| {z }
(n�1) modos
| {z }
(n�2) modos
· · · | {z }
(n�k+1) modos
58 CAPI´TULO 5. ANA´LISE COMBINATO´RIA
Logo,
An,k =
n!
(n� k)!
Exemplos
Exemplo 70. Para ocupar os cargos de presidente e vice-presidente do greˆmio de um
cole´gio, candidataram-se dez alunos. De quantos modos distintos pode ser feita essa es-
colha?
Exemplo 71. A senha de acesso a uma rede de computadores e´ formada por uma sequeˆncia
de quatro letras distintas (alfabeto com 26 letras) seguida por dois algarismos distintos.
(a) Quantas sa˜o as possı´veis senhas de acesso?
(b) Quantas senhas apresentam simultaneamente apenas consoantes e algarismos mai-
ores que 5?
Exemplo 72. Sabe-se que as cinco pessoas de uma famı´lia (pai, ma˜e e treˆs filhos) nasceram
emmeses diferentes do ano. Quantas sa˜o as sequeˆncias que representam os possı´veis meses
de nascimento dos membros dessa famı´lia?
Exemplo 73. Seis amigos participam de uma brincadeira de futebol, que consiste em
cobranc¸a de peˆnaltis. Cada um escolhe, de todas as formas possı´veis, um colega para
bater o peˆnalti e um outro para tentar defendeˆ-lo.
(a) Quantas cobranc¸as de peˆnalti sa˜o feitas nessa brincadeira?
(b) Quantas cobranc¸as haveria se o grupo resolvesse convidar um se´timo amigo para
que ele escolhesse, de todas as formas possı´veis, o cobrador e o defensor do peˆnalti?
5.6.2 Permutac¸o˜es
Permutac¸o˜es
Definic¸a˜o 51. Quando uma sequeˆncia ordenada (arranjo) e´ formada por todos os elemen-
tos disponı´veis, dizemos que se trata de uma permutac¸a˜o. Assim, o nu´mero de permutac¸o˜es
Pn de n elementos distintos e´
Pn = n!
5.6. AGRUPAMENTOS 59
Exemplo 74. Quais sa˜o os anagramas formados a partir da palavra SAPO?
AOPS AOSP APOS
APSO ASOP ASPO
OAPS OASP OPAS
OPSA OSAP OSPA
PAOS PASO POAS
POSA PSAO PSOA
SAOP SAPO SOAP
SOPA SPAO SPOA
Sa˜o p4 = 4! = 4 · 3 · 2 · 1 = 24 anagramas.
Exemplo 75. Jose´ e Maria teˆm treˆs filhos: Thiago, Pedro e Andre´. A famı´lia quer tirar
uma foto de recordac¸a˜o de uma viagem na qual todos aparec¸am lado a lado.
(a) De quantas formas distintas os membros da famı´lia podem se distribuir?
(b) Em quantas possibilidades o casal aparece junto?
Exemplo 76. Considere os anagramas formados a partir de CONQUISTA.
(a) Quantos sa˜o?
(b) Quantos comec¸am por vogal?
(c) Quantos comec¸am e terminam por consoante?
(d) Quantos teˆm as letras CON juntas e nessa ordem?
(e) Quantos apresentam a letra C antes da letra A?
Exemplo 77. Dona Lola tem treˆs filhos: Pedro, Paulo e Andre´. Os treˆs casaram-se e
teˆm, respectivamente, 1, 3 e 2 filhos. Em um domingo, dona Lola recebeu, para o almoc¸o,
seus treˆs filhos, acompanhados das respectivas esposas, ale´m de todos os netos. Como
recordac¸a˜o, ela fotografou todos os familiares, lado a lado, mas pediu que cada filho
aparecesse junto de sua famı´lia. De quantas formas distintas a foto poderia ter sido feita?
Exemplo 78. Se colocarmos em ordem crescente todos os nu´meros de 5 algarismos distin-
tos, obtidos com 1, 3, 4, 6 e 7, qual sera´ a posic¸a˜o do nu´mero 61473 ?
60 CAPI´TULO 5. ANA´LISE COMBINATO´RIA
5.6.3 Combinac¸o˜es
Definic¸a˜o 52. Dado um conjunto A com n elementos distintos, chama-se combinac¸a˜o dos
n elementos de A, tomados k a k, qualquer subconjunto de A formado por k elementos.
Fo´rmula para o Ca´lculo do nu´mero de Combinac¸o˜es
Cn,k =
An,k
k!
=
n!
(n� k)!k! =
✓
n
k
◆
Exemplo 79. Quantas saladas contendo exatamente 4 frutas podemos formar se dispomos
de 10 frutas diferentes?
Exemplo 80. Marcam-se 5 pontos sobre uma reta r e 8 pontos sobre uma reta r0 paralela
a r. Quantos triaˆngulos existem com ve´rtices em 3 desses 13 pontos.
Exemplo 81. De quantos modos podemos escolher 6 pessoas, incluindo pelo menos duas
mulheres, em um grupo de 7 homens e 4 mulheres?
Exemplo 82. De um grupo de 5 pessoas, de quantas maneiras distintas posso convidar
uma ou mais para jantar?
Exemplo 83. Quantos subconjuntos de 2 elementos tem um conjunto de 6 elementos?
Exemplo 84. Quantas diagonais possui um polı´gono de n lados?
Exemplo 85. Sobre uma circunfereˆncia marcam-se dez pontos.
(a) Qual e´ o nu´mero de segmentos de reta que podemos trac¸ar com extremidades em
dois desses pontos?
(b) Quantos triaˆngulos podemos construir com ve´rtices em treˆs desses pontos?
(c) Quantos polı´gonos com 4, 5, 6 ou 7 lados podem ser trac¸ados com ve´rtices nesses
pontos?
Exemplo 86. Em um curso de espanhol estudam vinte alunos, sendo dozes rapazes e oito
moc¸as. O professor quer formar uma equipe de quatro alunos para intercaˆmbio em outro
paı´s. Quantas equipes de dois rapazes e duas moc¸as podem ser formadas?
Exemplo 87. Para montar uma cesta de cafe´ da manha˜ esta˜o disponı´veis os seguintes
itens: quatro tipos de pa˜es, treˆs tipos de queijo, treˆs tipos de frutas, cinco sabores de gele´ia
e quatro sabores de tortas doces. De quantos modos distintos a ceta podera´ ser montada se
um cliente pedir dois tipos de pa˜es, um tipo de queijo, duas frutas, dois sabores de gele´ia
e um torta doce?
5.6. AGRUPAMENTOS 61
5.6.4 Permutac¸o˜es com repetic¸a˜o
Permutac¸o˜es com repetic¸a˜o
Definic¸a˜o 53. Nos casos em que cada resultado possı´vel e´ uma sequeˆncia ordenada, nos
quais ocorre repetic¸a˜o de elementos, dizemos que se trata de permutac¸a˜o com repetic¸a˜o.
Fo´rmula Geral
Se temos n elementos, dos quais
• n1 sa˜o iguais a a1,
• n2 sa˜o iguais a a2,
• n3 sa˜o iguais a a3,
...
• nk sa˜o iguais a ak,
enta˜o o nu´mero de permutac¸o˜es possı´veis e´ dado por
p(n1,n2,··· ,nk)n =
n!
n1!n2! · · ·nk!
Exemplo 88. Qual e´ o nu´mero de anagramas formados a partir da palavra VENEZUELA?
Exemplo 89. Qual e´ o nu´mero de anagramas da palavra MARROCOS?
Exemplo 90. Permutando os algarismos 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, quantos nu´merosde 10
algarismos podemos formar?
Exemplo 91. Uma prova e´ constituı´da de dez testes do tipo V ou F.
(a) Quantas sequeˆncias de respostas sa˜o possı´veis?
(b) Quantas sequeˆncias apresentam treˆs respostas V e sete respostas F?
Exemplo 92. Quantos nu´meros de 7 dı´gitos, maiores que 6 000 000, podem ser formados
usando apenas os algarismos 1, 3, 6, 6, 6, 8, 8 ?
62 CAPI´TULO 5. ANA´LISE COMBINATO´RIA
Capı´tulo 6
Introduc¸a˜o a` Teoria dos Nu´meros
Princı´pio da Boa Ordem: Todo subconjunto na˜o vazio do conjunto dos nu´meros inteiros
constituı´do de elementos na˜o negativos possui um mı´nimo.
Proposic¸a˜o 1 (Algorı´tmo de Euclides). Sejam a, b 2 Z, b 6= 0, enta˜o existe um u´nico par
(q, r) 2 Z⇥ Z tal que
a = bq + r, 0  r < |b|.
Demonstrac¸a˜o. (Existeˆncia) Seja A = {a � bq 2 Z | a � bq  0, q 2 Z}, enta˜o A 6= ?,
pois a� b · 0 = a > 0, ou seja, a 2 A.
Portanto, pelo Princı´pio da Boa Ordem, como A 6= ? e A e´ constituı´do de nu´meros
inteiros na˜o negativos, enta˜o existe r0 = minA. Assim, existe q0 2 Z tal que r0 = a� bq0.
Afirmac¸a˜o: 0  r0 < |b|.
De fato, se r0 � |b|, enta˜o existiria m � 0 tal que r0 = |b| +m e, como 0  m < r0 e
r0 = |b|+m = a� bq0, terı´amos que
m = a� bq � |b| =
8<: a� b(q + 1), se b > 0a� b(q � 1), se b < 0
ou seja, 0  m < r0 em 2 A, o que e´ um absurdo, pois r0 = minA.
Logo 0  r0 < b.
Portanto, tomando q = q0 e r = r0, temos que (q, r) satisfaz a = bq + r e 0  r < b.
(Unicidade) Sejam (q1, r1), (q2, r2) 2 Z⇥ Z tais que
a = bq1 + r, 0  r1 < b
e
a = bq2 + r2, 0  r2 < b.
63
64 CAPI´TULO 6. INTRODUC¸A˜O A` TEORIA DOS NU´MEROS
Assim,
bq1 + r1 = bq2 + r2
) b(q1 � q2) = r2 � r1
) |b||q1 � q2| = |r2 � r1| < |b|
) |q1 � q2| < 1
) |q1 � q2| = 0
) q1 = q2
)
8<: q1 = q2r2 � r1 = b(q1 � q2) = 0
)
8<: q1 = q2r1 = r2
) (q1, r1) = (q2, r2)
Exemplo 93. Para encontrarmos (q, r) 2 Z⇥ Z satisfazendo a = bq + r, com 0  r < b,
onde a = 45 e b = 56, basta escolhermos q = 0 e r = a = 45. Desta forma, obtemos que
a = 45 = 56 · 0 + 45 = bq + r, com 0  r = 45 < 56 = b.
Definic¸a˜o 54. Dizemos que um nu´mero inteiro a e´ um divisor de um nu´mero inteiro b
se existe z 2 Z tal que b = za. Neste caso, dizemos que b e´ divisı´vel por a ou que b e´
mu´ltiplo de a.
Notac¸a˜o 4. a | b significara´ que a e´ um divisor de b ou b e´ mu´ltiplo de a.
Proposic¸a˜o 2 (Propriedades). Seja A = Z⇤+, enta˜o a relac¸a˜o
R = {(a, b) 2 A⇥ A | a | b}
e´ uma relac¸a˜o de ordem parcial sobre Z⇤+, ou seja,
(i) (8a 2 A) (a | a) (Reflexiva)
(ii) (8a, b, c 2 Z) (a | b e b | c) a | c) (Transitiva)
(iii) (8a, b 2 A) (a | b e b | a) a = b) (Anti-sime´trica)
Demonstrac¸a˜o.
(i) Como a = 1 · a, 8a 2 A, enta˜o a | a, 8a 2 A.
(ii) Se a | b e b | c, enta˜o existem z1, z2 2 Z tais que b = z1a e c = z2b, o que implica
em c = z2(z1a) = (z2z1)a. Logo a | c.
65
(iii) Para a, b 2 R⇤+, temos que
(a | b e b | a)
) (9z1, z2 2 Z) (b = z1a e a = z2b)
) (9z1, z2 2 Z) (b = z1a e a = z2(z1a))
) (9z1, z2 2 Z) (b = z1a e a = (z2z1)a)
) (9z1, z2 2 Z) (b = z1a e 1 = z2z1)
a,b2Z⇤+) (9z1, z2 2 Z) (b = z1a e z1 = z2 = 1)
) (a = b)
Observac¸a˜o 8. As propriedades (i) e (ii) valem tambe´m para A = Z.
Definic¸a˜o 55. Sejam a, b 2 Z. Dizemos que um nu´mero inteiro positivo d e´ o ma´ximo
divisor comum de a e b se
(i) d | a e d | b;
(ii) Se d0 2 Z satisfaz d0 | a e d0 | b, enta˜o d0 | d.
Notac¸a˜o 5. Utilizaremos o sı´mbolo mdc(a, b) ou (a, b) para representarmos o ma´ximo
divisor comum de a e b (ou entre a e b).
Exemplo 94. Vamos calcular agora o ma´ximo divisor comum entre 45 e 12. Para fazermos
isto, observe primeiramente que
• o conjunto dos divisores positivos de 45 e´ d(45) = {1, 3, 5, 9, 15, 45};
• o conjunto dos divisores positivos de 12 e´ d(12) = {1, 2, 3, 4, 6, 12};
• o conjunto dos divisores positivos de 12 e de 45 sa˜o d(45) \ d(12) = {1, 3}.
Portanto, o ma´ximo divisor comum entre 45 e 12 sera´ o ma´ximo do conjunto d(45)\d(12),
que e´ 3, ou seja, mdc(45, 12) = max d(45) \ d(12) = 3.
Proposic¸a˜o 3. Se a, b 2 Z d um divisor de a e de b. Enta˜o d | (↵a+ �b), 8↵, � 2 Z.
Demonstrac¸a˜o. Se d | a e d | b, enta˜o existem z1, z2 2 Z tais que a = z1d e b = z2d.
Assim,
↵a+ �b = ↵(z1d) + �(z2d) = (↵z1 + �z2)d,
com ↵z1 + �z2 2 Z. Logo d | (↵a+ �b).
66 CAPI´TULO 6. INTRODUC¸A˜O A` TEORIA DOS NU´MEROS
Proposic¸a˜o 4. Sejam a, b 2 Z e A = {↵a + �b | ↵a + �b > 0,↵, � 2 Z}, enta˜o
mdc(a, b) = minA.
Demonstrac¸a˜o. Pelo Princı´pio da Boa Ordem, existem0 = minA.
Como d = mdc(a, b) e´ tal que d0 | a e d0 | b, enta˜o, pela proposic¸a˜o anterior, d |
(↵a+ �b), 8↵, � 2 Z. Comom0 2 A, existem ↵0, �0 2 Z tais quem0 = ↵0a+ �0b. Logo
d | (↵0a+ �0b), o que implica em d | m0.
Provaremos agora que m0 | a e m0 | b. De fato, pelo Algorı´tmo de Euclides, existem
q, r 2 Z tais que
(a = m0q + r, 0  r < m0)
) (a = (↵0a+ �0b)q + r, 0  r < m0)
) ((1� ↵0q)a+ (��0q)b = r, 0  r < m0)
Logo r = 0, pois 0  r < m0 e m0 e´ o menor nu´mero inteiro positivo escrito na forma
↵a+ �b, com ↵, � 2 Z.
Assim, a = m0q + r = m0q ) m0 | a.
Da mesma forma podemos concluir quem0 | b.
Comom0 | a em0 | b, enta˜om0 | d. Portanto, comom0 > 0 e d0 | m0 em0 | d0, enta˜o
d = m0.
Logo minA = mdc(a, b).
Corola´rio 1. mdc(n, n+ 1) = 1, 8n 2 Z.
Demonstrac¸a˜o. Como 1 = n+1�n = 1 · (n+1)+(�1) ·n e 1 e´ o menor nu´mero inteiro
positivo, enta˜o, pela Proposic¸a˜o anterior, mdc(n, n+ 1) = 1.
Corola´rio 2. Para todo inteiro n,
mdc
✓
2n+ 1,
n(n+ 1)
2
◆
= 1.
Demonstrac¸a˜o. Basta observar que se ↵ = 2n+ 1 e � = �8, enta˜o
↵(2n+ 1) + �
n(n+ 1)
2
= (2n+ 1)(2n+ 1) + (�8)n(n+ 1)
2
= 1.
Definic¸a˜o 56. Um nu´mero inteiro p 6= ±1 e´ primo se os u´nicos divisores de p sa˜o ±1 e
±p.
67
Proposic¸a˜o 5. Seja p um nu´mero primo e sejam a, b 2 Z, tais que p | (ab), enta˜o p | a ou
p | b.
Demonstrac¸a˜o. Se p | a, enta˜o ja´ temos o que querı´amos.
Se p - a, enta˜o mdc(a, p) = 1, pois os u´nicos divisores de p sa˜o ±p e ±1.
Como mdc(p, a) = 1, enta˜o existem ↵, � 2 Z tais que
↵p+ �a = 1) b · 1 = b(↵p+ �a)) b = (↵b)p+ �(ab)
Como p | (ab) e mdc(p, a) = 1, enta˜o existem z,↵, � 2 Z tais que
ab = zp (6.1)
e
↵p+ �a = 1 (6.2)
Portanto,
1 = ↵p+ �a
) b · 1 = b(↵p+ �a)
) b = (b↵)p+ �(ab)
(6.1)) b = (b↵)p+ �(zp)
) b = (b↵ + �z)p
) p | b
Logo p | a ou p | b.
Exercı´cio 4. Se c | (ab) e mdc(c, a) = 1, enta˜o c | b.
Definic¸a˜o 57. Um nu´mero inteirom 62 {±1, 0} e´ um nu´mero composto sem na˜o e´ primo,
ou seja, sem 6= 0 em possui mais de 4 divisores.
Proposic¸a˜o 6. Seja m um nu´mero inteiro positivo maior ou igual a 2, enta˜o o menor
elemento do conjunto (o mı´nimo) S = {x 2 Z | x > 1 e x | m} e´ um nu´mero primo.
Demonstrac¸a˜o. Comom 2 S e S e´ constituı´do por nu´meros inteiros positivos, enta˜o, pelo
Princı´pio da Boa Ordem, existe p = minS. Para provar que p e´ primo, suponhamos que
p seja composto. Se p for composto, enta˜o existem inteiros z1, z2 > 1 tais que p = z1z2.
Assim, como p | a e z2 | p, enta˜o z2 | a. Portanto, z2 2 S e z2 < p, o que contradiz a
minimalidade de p.
Logo p e´ primo.
68 CAPI´TULO 6. INTRODUC¸A˜O A` TEORIA DOS NU´MEROS
Proposic¸a˜o 7 (Primeiro Princı´pio de Induc¸a˜o). Seja P (n) uma afirmac¸a˜o que depende de
n 2 N = {0, 1, 2, · · · } que pode ser julgada como verdadeira ou falsa para cada n.
Se
(i) P (n0) e´ verdadeira para algum n0 2 N e
(ii) (8n 2 N) (P (n) verdadeira ) P (n+ 1) verdadeira) ,
enta˜o P (n) e´ verdadeira para todo n 2 N tal que n � n0.
Demonstrac¸a˜o. Seja S = {n 2 N | n > n0 e P (n) e´ falsa, }. Suponhamos que P (n)
seja falsa para algum m > n0. Assim, S 6= ? e pelo Princı´pio da Boa Ordem, existe
m0 = minS. Logo, m0 � 1 62 S e P (m0 � 1) e´ verdadeira. Se P (m0 � 1) e´ verdadeira,
por (ii), P (m0) e´ verdadeira, o que e´ um absurdo.
Portanto, na˜o existe P (m) falsa para