Matemática 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
1.6.3 Negac¸a˜o de sentenc¸as quantificadas . . . . . . . . . . . . . . . . . 15
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
3
4 SUMA´RIO
2.2.2 Relac¸a˜o de contineˆncia entre conjuntos . . . . . . . . . . . . . . . 19
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 . . . . . . . . . . . . . . . . . . . . . . 35
4 Relac¸o˜es e Func¸o˜es 45
4.1 Func¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5 Ana´lise Combinato´ria 55
5.1 Princı´pio das Casas de Pombo . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2 Princı´pio Fundamental da Contagem . . . . . . . . . . . . . . . . . . . . . 57
5.2.1 Princı´pio da Multiplicac¸a˜o . . . . . . . . . . . . . . . . . . . . . . 57
5.2.2 Princı´pio da Soma . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.3 Outros Me´todos de Contagem . . . . . . . . . . . . . . . . . . . . . . . . 59
5.4 Caso sem te´cnica conhecida . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.5 Fatorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.6 Agrupamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.6.1 Arranjos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.6.2 Permutac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.6.3 Combinac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.6.4 Permutac¸o˜es com repetic¸a˜o . . . . . . . . . . . . . . . . . . . . . . 64
6 Introduc¸a˜o a` Teoria dos Nu´meros 65
6.1 Congrueˆncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.1.1 Propriedades das Congrueˆncias . . . . . . . . . . . . . . . . . . . 79
SUMA´RIO 5
7 Conjuntos Enumera´veis 83
8 Grafos 93
8.1 Definic¸o˜es iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
8.2 Terminologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
8.3 Isomorfismo entre grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
8.4 Matrizes de Adjaceˆncia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8.4.1 Matriz de adjaceˆncia para grafo na˜o-direcionado (na˜o-orientado) . . 99
8.4.2 Matriz de adjaceˆncia para grafo ponderado (valorado) . . . . . . . 105
8.5 Matriz de distaˆncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
8.5.1 Matriz de distaˆncias para Grafos na˜o ponderados . . . . . . . . . . 105
8.5.2 Matriz de distaˆncias para Grafos ponderados . . . . . . . . . . . . 105
8.6 Algoritmos em Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
8.7 Problema do Caminho Mı´nimo . . . . . . . . . . . . . . . . . . . . . . . . 108
8.8 Outros Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8.8.1 Lista de Exercı´cios sobre Grafos . . . . . . . . . . . . . . . . . . . 110
9 A´lgebra de Boole 115
9.1 Minimizac¸a˜o de Func¸o˜es Booleanas . . . . . . . . . . . . . . . . . . . . . 120
9.1.1 Me´todo de Quine-McCluskey . . . . . . . . . . . . . . . . . . . . 120
9.1.2 Me´todo de Karnaugh . . . . . . . . . . . . . . . . . . . . . . . . . 120
9.1.3 Desvantagens na utilizac¸a˜o do me´todo de reduc¸a˜o de Karnaugh . . 124
10 Du´vidas Correlatas em aula 127
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.3Conectivo 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 conectivo pode 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´mero m e´ maior do que 10, enta˜o o nu´mero m e´ maior
do que 3.
Exemplo 6. Se n e´ um nu´mero primo maior do que 2, enta˜o n e´ impar.
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 7. 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 8. 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 9. 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 10. 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 11. 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 12. 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 13. 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 ∈ 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 ∀, de modo que a expressa˜o
“para todo x, p(x)”pode ser substituı´da simbolicamente por (∀x) (p(x)) .
Exemplo 14.
(a) (∀x) (x2 + 1 > 0)
(b) (∀x) (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 (∀x) (p(x)) e´ verdadeira, ou seja,
v ((∀x) (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 ∃, de modo que a
expressa˜o “para algum x, p(x)”pode ser substituı´da simbolicamente por (∃x) (p(x)) .
Exemplo 15.
(a) (∃x) (x2 = 1)
(b) (∃x) (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 (∃x) (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 apartir de quantifi-
cadores.
1.6. QUANTIFICADORES 15
1.6.3 Negac¸a˜o de sentenc¸as quantificadas
¬[(∀x)(p(x))]⇔ (∃x)(¬p(x))
e
¬[(∃x)(p(x))]⇔ (∀x)(¬p(x))
Exemplo 16. Negue as seguintes sentenc¸as quantificadas:
(a) (∀x)(x2 + 1 < 1)
¬[(∀x)(x2 + 1 < 1)]⇔ (∃x)(x2 + 1 ≥ 1)
(b) U = Z, (∀x)(∃y)(x = 2y)
¬[(∀x)(∃y)(x = 2y)]⇔ (∃x)(∀y)(x 6= 2y)
(c) U = R∗+
(∀ε)(∃δ)(0 < |x− c| < δ → |f(x)− L| < ε)
¬[(∀ε)(∃δ)(0 < |x−c| < δ → |f(x)−L| < ε)]⇔ (∃ε)(∀δ)((0 < |x−c| < δ)∧(|f(x)−L| ≥ ε))
(d) U = Q
(∀x)(x2 = 2)
¬[(∀x)(x2 = 2)]⇔ (∃x)(x2 6= 2)
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 as seguintes proposic¸o˜es:
(a) p ∨ q
(b) p ∧ q
16 CAPI´TULO 1. FUNDAMENTOS DE LO´GICA MATEMA´TICA
(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)]
(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:
1.6. QUANTIFICADORES 17
(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) (∀ε) (∃δ) (0 < |x− c| < δ → |f(x)− L| < ε)
(b) (∃x) (x2 + 2x > 10)
(c) (∀x) (x2 + 1 6= 0)
(d) (∀x) (∀y) ((√x > √y)→ (x > y))
(e) (∀x) (∀y) (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 ∈ para representar
esta relac¸a˜o, de modo que a ∈ A. Caso contra´rio, quando um elemento a na˜o pertence a
um conjunto A utilizamos o sı´mbolo 6∈ para representar esta relac¸a˜o, de modo que a 6∈ 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 17. 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 ⇔ (∀x) ((x ∈ A) ∧ (x ∈ B)) ,
ou seja,
(A ⊂ B)↔ (∀x) ((x ∈ A) ∧ (x ∈ 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 18. 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, (∀x) (x ∈ A ∩B ↔ (x ∈ A) ∧ (x ∈ 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, (∀x) (x ∈ A ∪B ↔ (x ∈ A) ∨ (x ∈ 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, (∀x) ((x ∈ A−B)↔ (x ∈ A) ∧ (x 6∈ 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, (∀x) (x ∈ AC ↔ x 6∈ 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, (∀x) (x ∈ CB(A)↔ ((A ⊂ B) ∧ (x ∈ B − A)))
Exemplo 19. 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 20. Se A = {0; 1}, enta˜o o conjunto das partes de A e´ o conjunto
P (A) = {∅; {0}; {1}; {0; 1}}
Exemplo 21. 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 ∈ A
⇔ (x ∈ A e x 6∈ B) ou (x ∈ A e x ∈ B)
⇔ (x ∈ A−B) ou (x ∈ A ∩B)
⇔ x ∈ (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 ∈ A e q : x ∈ 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 22. 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)↔ p
assume 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 23. 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 24. 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˜o
de uma quantidade finita de casos particulares.
Exemplo 25. 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 ∈ 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 26. 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 ∈ Z
tais que a = 2k e b = 2s.
Assim, a+ b = 2k + 2s = 2(k + s), com k + s ∈ Z.
Logo a+ b e´ um nu´mero par.
Exemplo 27. 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 ∈ Z tal que n = 2k.
Assim, n2 = (2k)2 = 4k2 = 2 · (2k2), com 2k2 ∈ Z.
Logo n2 e´ um nu´mero par.
Exemplo 28. 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 29. Se n ∈ N satisfaz n! > n+ 1, mostre que n > 2.
Demonstrac¸a˜o. Pelo exemplo 25 mostramos que a seguinte proposic¸a˜o e´ va´lida:
Se n ∈ N satisfaz n ≤ 2, enta˜o n! ≤ n+ 1.
Logo, sua contrapositiva
Se n ∈ N satisfaz n! > n+ 1, enta˜o n > 2.
tambe´m e´ va´lida.
Exemplo 30. 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 27, enta˜o a demonstrac¸a˜o
segue por contraposic¸a˜o.
Exemplo 31. 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 32. Prove que se x ∈ Z, enta˜o x2 + x 6= 1.
Demonstrac¸a˜o. Suponhamos que x ∈ Z e que x2 + x = 1.
Se x for par, enta˜o existira´ k ∈ Z tal que x = 2k. Assim,
x2 + x = 1
⇒ (2k)2 + (2k) = 1
⇒ 2(2k2 + k) = 2 · 0 + 1
k′=2k2+k⇒ 2k′ = 2 · 0 + 1,
o que e´ um absurdo.
Se x for impar, enta˜o existira´ k ∈ Z tal que x = 2k + 1. Assim,
x2 + x = 1
⇒ (2k + 1)2 + (2k + 1) = 1
⇒ 4k2 + 4k + 1 + 2k + 1 = 1
k′=2k2+2k+1∈Z⇒ 2(2k2 + 2k + 1) = 2 · 0 + 1,
o que e´ um absurdo.
Portanto, por contradic¸a˜o, se x ∈ Z, enta˜o x2 + x 6= 1.
Exemplo 33. Prove que se x2 = 2, enta˜o x na˜o e´ um nu´mero racional.
Demonstrac¸a˜o. Suponhamos que x ∈ Q e x2 = 2. Como x ∈ Q, enta˜o x = a
b
onde a e b
na˜o possuem divisores primos comuns. Assim,
(
a
b
)2
= 2
⇒ a2 = 2b2
⇒ (a e´ par e a2 = 2b2)
⇒ (∃k ∈ Z) (a = 2k e a2 = 2b2)
⇒ (∃k ∈ Z) (a = 2k e (2k)2 = 2b2)
⇒ (∃k ∈ Z) (a = 2k e 2k2 = b2)
⇒ (∃k ∈ Z) (a = 2k e b e´ par e 2k2 = b2)
⇒ (∃s ∈ Z) (∃k ∈ 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. PRINCI´PIOS DE INDUC¸A˜O MATEMA´TICA 35
3.5 Princı´pios de induc¸a˜o matema´tica
Primeiro Princı´pio de Induc¸a˜o Matema´tica
Seja a ∈ 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 34. Prove por induc¸a˜o que para qualquer n ∈ N, vale n < 2n.
Exemplo 35. Prove por induc¸a˜o que para qualquer n ∈ N, se n > 3, enta˜o 2n < n!.
Exemplo 36. Prove por induc¸a˜o que para qualquer n ∈ 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
.
36 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O
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 ∈ 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) [k
2
+ 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 ∈ N.
Exemplo 37. Mostre que n2 > 2n+ 1 para todo n ∈ 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.
Suponhamos que p(m) seja verdadeira para algum m ≥ 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 ∈ N, n ≥ 3.
Exemplo 38. Mostre que 1 + 3 + 32 + · · ·+ 3n = 3n+1−1
2
para todo n ∈ N.
Demonstrac¸a˜o. Seja p(n) : 1 + 3 + 32 + · · ·+ 3n = 3n+1−1
2
.
Como 1 = 3−1
2
= 3
0+1−1
2
, enta˜o p(0) e´ verdadeira.
Suponhamos que p(m) seja verdadeira para algum m ∈ N.
Assim,1 + 3 + 32 + · · ·+ 3n = 3n+1−1
2
⇒ 1 + 3 + 32 + · · ·+ 3n + 3n+1 = 3n+1−1
2
+ 3n+1
⇒ 1 + 3 + 32 + · · ·+ 3n+1 = 3n+1 (1
2
+ 1
)− 1
2
⇒ 1 + 3 + 32 + · · ·+ 3n+1 = 3n+2−1
2
.
Portanto, p(m+ 1) e´ verdadeira.
Logo, por induc¸a˜o, 1 + 3 + · · ·+ 3n = 3n+1−1
2
para todo n ∈ N.
3.5. PRINCI´PIOS DE INDUC¸A˜O MATEMA´TICA 37
Segundo Princı´pio de Induc¸a˜o Matema´tica
Seja a ∈ 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 39. 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 ∈ 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.
• 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 igual ou maior que 12 pode ser formado usando exclusivamente
selos de 4 e 5 reais.
Exemplo 40. 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.
Seja m um nu´mero natural maior ou igual a 2.
38 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O
Se m = 2, enta˜o p(2) e´ verdadeira, pois 2 e´ um nu´mero primo.
Se m > 2 e m 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 que m = 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.
3.5. PRINCI´PIOS DE INDUC¸A˜O MATEMA´TICA 39
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 ∈ Z tal que b = ka. Neste caso utilizamos o sı´mbolo a | b.
(2) Dizemos que a e´ congruente a b mo´dulo n ou que a e´ equivalente a b mo´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 d′ ∈ Z, a | d′ e b | d′ ⇒ d | d′.
(4) Dizemos que d = mdc(a, b) se
(a) d | a e d | b.
(b) Para qualquer d′ ∈ Z, d′ | a e d′ | b⇒ d′ | d.
(5) Se d = mdc(a, b), enta˜o d e´ o menor inteiro positivo satisfazendo
d = x · a+ y · b,
para x, y ∈ 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 ∈ N, enta˜o mmc(ca, cb) = c ·mmc(a, b).
4) Sejam x e y nu´meros positivos. Se x ≤ y, enta˜o √x ≤ √y.
5) Se x e y sa˜o nu´meros reais positivos, enta˜o 2
√
xy ≤ x+ y.
40 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O
6) Se n ∈ 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 ∈ N.
8) Suponha que x, y ∈ Z. Se x e y sa˜o pares, enta˜o xy e´ par.
9) Suponha que x, y ∈ Z. Se x e y sa˜o ı´mpares, enta˜o xy e´ ı´mpar.
10) Suponha que a, b, c ∈ Z. Se a | b e a | c, enta˜o a | (b+ c).
11) Suponha que a, b ∈ 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 ∈ Z. Se a | b, enta˜o a | (3b3 − b2 + 5b).
15) Sejam a, b, c, d ∈ Z. Se a | b e c | d, enta˜o ac | bc.
16) Se x ∈ R e 0 < x < 4, enta˜o 4
x(4− x) ≥ 1.
17) Se n ∈ Z, enta˜o 5n2 + 3n+ 7 e´ ı´mpar.
18) Se n ∈ 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 ∈ 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 ∈ 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 ∈ R. Se y3 + yx2 ≤ x3 + xy2, enta˜o y ≤ x.
25) Sejam x, y ∈ Z Se 5 - xy, enta˜o 5 - x e 5 - y.
3.5. PRINCI´PIOS DE INDUC¸A˜O MATEMA´TICA 41
26) Sejam a, b ∈ Z e n ∈ N. Se a ≡ b( mod n), enta˜o a2 ≡ b2(modn).
27) Sejam a, b ∈ Z e n ∈ N. Se 12a 6≡ 12b(modn), enta˜o n - 12.
28) Seja x ∈ R. Se x2 + 5x < 0, enta˜o x < 0.
29) Seja x ∈ R. Se x3 − x > 0, enta˜o x > −1.
30) Sejam x, y, z ∈ Z e x 6= 0. Se x - yz, enta˜o x - y e x - z.
31) Se n ∈ N e 2n − 1 e´ primo, enta˜o n e´ primo.
32) Se n ∈ Z, enta˜o 4 - (n2 − 3).
Te´cnica de demonstrac¸a˜o por contradic¸a˜o
33) Se a, b ∈ Z, enta˜o a2 − 4b 6= 2.
34) Existem infinitos nu´meros primos.
35) Para todo nu´mero real x ∈ [0, pi/2], temos sen x+ cosx ≥ 1.
36) Prove que 3
√
2 e´ irracional.
37) Se a, b ∈ Z, enta˜o a2 − 4b− 2 6= 0.
38) Para todo n ∈ 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 ∈ 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 ∈ Z e n ≥ 0, enta˜o∑ni=0 i · i! = (n+ 1)!− 1.
43) Se n ∈ N, enta˜o (1 + x)n ≥ 1 + nx para todo x ∈ R com x > −1.
44) Se n ∈ N e n ≥ 1, enta˜o
1 + 2 + 3 + 4 + · · ·+ n = n
2 + n
2
.
42 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O
45) Para todo inteiro n ≥ 1,
12 + 22 + 32 + · · ·+ n2 = n(n+ 1)(2n+ 1)
6
.
46) Para todo inteiro n ∈ N,
n∑
i=1
(8i− 5) = 4n2 − n.
47) Se n ∈ N, enta˜o
1 · 3 + 2 · 4 + 3 · 5 + · · ·+ 4 · 6 + · · ·+ n(n+ 2) = n(n+ 1)(2n+ 7)
6
.
48) Se n ∈ 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 ∈ Z tais que b = ra e c = sb. Assim,
c = sb = s(ra) = (sr)a
com sr ∈ Z. Logo a | c.
2) Como x e´ par, enta˜o existe k ∈ 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 ∈ Z.
Logo x2 − 6x+ 5 e´ ı´mpar.
3.5. PRINCI´PIOSDE INDUC¸A˜O MATEMA´TICA 43
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
√
x+
√
y > 0, enta˜o 1√
y+
√
x
> 0. Ale´m disso, como x ≤ y, enta˜o y − x ≥ 0.
Logo,
√
y − √x = (
√
y−√x)(√y+√x)
(
√
y+
√
x)
= 1√
y+
√
x
· (y − x) ≥ 0, o que implica em
√
x <
√
y.
10) Como a | b e a | c, enta˜o existem k1, k2 ∈ Z tais que b = k1a e c = k2a, o que
implica em b+ c = (k1 + k2)a com k1 + k2 ∈ Z.
Logo a | (b+ c).
44 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O
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 ∈ A, b ∈ B}.
Exemplo 41. 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 (∀a ∈ A) ((a, a) ∈ R) , enta˜o R e´ chamada de relac¸a˜o reflexiva.
(2) Se (a, b) ∈ R implicar em (b, a) ∈ R para todos a, b ∈ A, enta˜o R e´ chamada de
relac¸a˜o sime´trica.
(3) Se (a, b) ∈ R e (b, c) ∈ R implicarem em (a, c) ∈ R para todo a, b, c ∈ A, enta˜o R
e´ chamada de relac¸a˜o transitiva.
(4) Se (a, b) ∈ R e (b, a) ∈ R 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.
45
46 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) ∈ R que representa uma aresta orientada de a para b.
Exemplo 42. 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 43. Se R = {(a, b) ∈ N × N | a | b}, enta˜o R e´ uma relac¸a˜o de ordem parcial
sobre N.
De fato,
47
(i) Se a ∈ A, enta˜o a = 1 · a, i.e., a e´ mu´ltiplo de a. Logo (a, a) ∈ R. Portanto R e´
reflexiva.
(ii) Sejam a, b, c ∈ A tais que (a, b), (b, c) ∈ R. Assim b e´ mu´ltiplo de a e c e´ mu´ltiplo
de b. Logo existem r, s ∈ Z tais que b = ra e c = sb. Portanto c = rb = s(ra) =
(sr)a, onde sr ∈ Z, ou seja, c e´ mu´ltiplo de a. Consequentemente, (a, c) ∈ R. Logo
(∀a, b, c ∈ A) (((a, b), (b, c) ∈ R)⇒ ((a, c) ∈ R)) .
Portanto, R e´ transitiva. Simbolicamente, se a, b, c ∈ N,
((a, b) ∈ R e (b, c) ∈ R)
⇒ (b e´ mu´ltiplo de a e c e´ mu´ltiplo de b)
⇒ (∃r, s ∈ Z) (b = ra e c = sb)
⇒ (∃r, s ∈ Z) (c = sb = s(ra) = (sr)a)
t=sr⇒ (∃t ∈ Z) (c = ta)
⇒ (c e´ mu´ltiplo de a)
⇒ ((a, c) ∈ R)
Logo R e´ transitiva.
(iii) Sejam a, b ∈ N tais que (a, b) ∈ R e (b, a) ∈ R, enta˜o existem r, s ∈ 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 44. Seja A um conjunto. Se R = {(B,C) ∈ 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) ∈ R para todo B ∈ P (A). Logo R e´
reflexiva.
(ii) Sejam B,C ∈ P (A), tais que (B,C) ∈ R e (C,B) ∈ R. Assim, B ⊂ C e C ⊂ B, o
que implica em B = C. Logo R e´ anti-sime´trica.
(iii) Sejam B,C,D ∈ P (A) tais que (B,C) ∈ R e (C,D) ∈ R, enta˜o B ⊂ C e C ⊂ D,
o que implica em B ⊂ D. Assim, (B,D) ∈ R. Logo R e´ transitiva.
48 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 45. Sejam A e B conjuntos disjuntos e R uma relac¸a˜o de ordem sobre A ∪ B
definida por
R = {(a, b) ∈ (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 ∈ A ∪ B, enta˜o {a, a} ⊂ A ou {a, a} ⊂ B. Logo (a, a) ∈ R. Portanto R e´
reflexiva.
(2) Se (a, b) ∈ R, enta˜o {a, b} ⊂ A ou {a, b} ⊂ B. Logo {b, a} ⊂ A ou {b, a} ⊂ B, o
que implica em (b, a) ∈ R. Portanto R e´ sime´trica.
(3) Se (a, b) ∈ R e (b, c) ∈ 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) ∈ 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 46. 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)}
49
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 ∈ A podemos definir uma classe de equivaleˆncia para esta relac¸a˜o R como sendo o
conjunto
[x] = {a ∈ A | (a, x) ∈ 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) ∈ Z× Z | a ≡ b mod 5}
e´ uma relac¸a˜o de equivaleˆncia e encontre Z/R.
(2) Seja Y = {0, 1} e M 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) ∈M ×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 ∈M 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) ∈ 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}.
50 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 ∈ Z | |x| ≤ 5} a relac¸a˜o definida por (x, y) ∈ 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) ∈ 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) ∈ R⇔ x−y ∈ Z. Provar
que R e´ uma relac¸a˜o de equivaleˆncia.
(10) Seja R = {(x, y) ∈ R2 | x− y ∈ 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 ∈ B e´ u´nico para
cada x ∈ 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 ∈ B | y = f(x) para algum x ∈ 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 51
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 47. 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 48. Encontre o domı´nio e a imagem de f(x) =
√
x− 1.
Como na˜o existem raı´zes reais de nu´meros negativos, enta˜o x− 1 ≥ 0⇒ x ≥ 1.
Assim, Dom(f) = [1;+∞[= {x ∈ R | x ≥ 1} e
Im(f) =]0;+∞[= {y ∈ R | y ≥ 0}.
Exemplo 49. Encontre o domı´nio e a imagem de f(x) =
√
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 ∈ 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 50. 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
(∀x, y ∈ A) (f(x) = f(y)⇒ x = y)
ou, equivalentemente, se
(∀x, y ∈ A) (x 6= y ⇒ f(x) 6= f(y))
52 CAPI´TULO 4. RELAC¸O˜ES E FUNC¸O˜ES
Exemplo 51. Uma func¸a˜o f : R→ R definida por f(x) = 2x e´ injetora, pois
(∀a, b ∈ 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 52. A func¸a˜o real f(x) = 2x+ 3 e´ bijetora, pois
• f e´ injetora: (∀a, b ∈ R) (f(a) = f(b)⇒ 2a+ 3 = 2b+ 3⇒ 2a = 2b⇒ a = b) e
• f e´ sobrejetora: (∀c ∈ R) (f ( c−3
2
)
= 2 c−3
2
+ 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 53. Se f(x) = 1
x
e g(x) =
√
x, enta˜o (f ◦ g)(x) = 1√
x
.
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 54. 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),∀x ∈ 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 55. 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),∀x ∈ A.
Exemplo 56. Se f : R − {1} → R e g : R → R sa˜o definidas por f(x) = x2−1
x−1 e
g(x) = x+ 1, enta˜o g e´ um prolongamento (ou extensa˜o) de f.
4.1. FUNC¸O˜ES 53
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.
54 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 57. 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 58. 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 59. 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?
55
56 CAPI´TULO 5. ANA´LISE COMBINATO´RIA
Lista de Exercı´cios sobre Princı´pios das Casas de Pombos
1) Mostre que num grupo de 5 inteiros (na˜o necessariamente consecutivos) existem pelo
menos dois com o mesmo resto quando divididos por 4.
2) Seja d um inteiro positivo. Mostre que entre qualquer grupo de d + 1 inteiros (na˜o
necessariamente consecutivos) existem dois com exatamente o mesmo resto quando
divididos por d.
3) Entre 100 pessoas, quantas pelo menos nasceram no mesmo meˆs?
4) Entre 2012 pessoas, quantas pelo menos nasceram no mesmo dia da semana?
5) Qual e´ o menor nu´mero de estudantes que se deve ter em um curso para garantir que
pelo menos 6 ira˜o receber a mesma nota, sabendo que as possı´veis notas sa˜o A, B, C,
D e E?
6) Quantos estudantes devem ter numa turma para garantir que pelo menos dois estu-
dantes possuam a mesma nota no exame final, se a nota do exame varia entre 0 e 100
pontos?
7) Entre um conjunto de 21 dı´gitos decimais quantos sa˜o os mesmos?
8) Quantas pessoas no mı´nimo sa˜o necessa´rias para garantir que numa sala existam 2
pessoas que tenham nascido no mesmo meˆs?
9) Quantas pessoas no mı´nimo sa˜o necessa´rias para garantir que numa sala existam n
pessoas que tenham nascido no mesmo meˆs?
10) Se tenho n caixas. Quantos objetos, no mı´nimo, sa˜o necessa´rios para garantir que
existam m objetos numa mesma caixa?
11) Se tenho m objetos e k < m. Quantas caixas devo ter no ma´ximo para garantir que
existam k objetos numa mesma caixa?
5.2. PRINCI´PIO FUNDAMENTAL DA CONTAGEM 57
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 d2e´ x+ y.
Exemplo 60. Numa sala ha´ 3 homens e 4 mulheres. De quantos modos e´ possı´vel selecio-
nar um casal homem-mulher?
Resposta: 3︸︷︷︸
homens
· 4︸︷︷︸
mulheres
= 12.
Exemplo 61. 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︸︷︷︸
ida
· 2︸︷︷︸
volta
= 6.
Exemplo 62. 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︸ ︷︷ ︸
1a letra
· 26︸ ︷︷ ︸
2a letra
· 10︸ ︷︷ ︸
1oalgarismo
· 10︸ ︷︷ ︸
2oalgarismo
· 10︸ ︷︷ ︸
3oalgarismo
· 10︸ ︷︷ ︸
4oalgarismo
= 6 760 000.
Exemplo 63. De quantos modos 3 pessoas podem sentar-se em 5 cadeiras em fila?
Resposta: 5︸ ︷︷ ︸
1a pessoa
· 4︸ ︷︷ ︸
2a pessoa
· 3︸ ︷︷ ︸
3apessoa
= 60.
Exemplo 64. Quantos nu´meros diferentes podem ser formados multiplicando alguns (ou
todos) dos nu´meros 1, 5, 6, 7, 7, 9, 9, 9?
58 CAPI´TULO 5. ANA´LISE COMBINATO´RIA
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 ,
onde m1 ∈ {0, 1},m2 ∈ {0, 1},m3 ∈ {0, 1, 2} e m4 ∈ {0, 1, 2, 3}.
Logo,
2︸ ︷︷ ︸
m1
· 2︸ ︷︷ ︸
m2
· 3︸ ︷︷ ︸
m4
· 4︸ ︷︷ ︸
m5
= 48.
Exemplo 65. 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 66. 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 67. (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 68. 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 69. 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.
5.3. OUTROS ME´TODOS DE CONTAGEM 59
• 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´spede podera´ ser servido?
Exemplo 70. 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 71. 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 72. 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! =
 1 se n = 0n(n− 1)! se n ∈ N∗
Exercı´cio 2. Calcule o valor de:
60 CAPI´TULO 5. ANA´LISE COMBINATO´RIA
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:
︸ ︷︷ ︸
n modos
︸ ︷︷ ︸
(n−1) modos
︸ ︷︷ ︸
(n−2) modos
· · · ︸ ︷︷ ︸
(n−k+1) modos
5.6. AGRUPAMENTOS 61
Logo,
An,k =
n!
(n− k)!
Exemplos
Exemplo 73. 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 74. 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 75. Sabe-se que as cinco pessoas de uma famı´lia (pai, ma˜e e treˆs filhos) nasceram
em meses diferentes do ano. Quantas sa˜o as sequeˆncias que representam os possı´veis meses
de nascimento dos membros dessa famı´lia?
Exemplo 76. 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!
62 CAPI´TULO 5. ANA´LISE COMBINATO´RIA
Exemplo 77. 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 78. 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 79. 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 80. 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 81. 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 ?
5.6. AGRUPAMENTOS 63
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 82. Quantas saladas contendo exatamente 4 frutas podemos formar se dispomos
de 10 frutas diferentes?
Exemplo 83. Marcam-se 5 pontos sobre uma reta r e 8 pontos sobre uma reta r′ paralela
a r. Quantos triaˆngulos existem com ve´rtices em 3 desses 13 pontos.
Exemplo 84. De quantos modos podemos escolher 6 pessoas, incluindo pelo menos duas
mulheres, em um grupo de 7 homens e 4 mulheres?
Exemplo 85. De um grupo de 5 pessoas, de quantas maneiras distintas posso convidar
uma ou mais para jantar?
Exemplo 86. Quantos subconjuntos de 2 elementos tem um conjunto de 6 elementos?
Exemplo 87. Quantas diagonais possui um polı´gono de n lados?
Exemplo 88. 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 89. 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 90. 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?
64 CAPI´TULO 5. ANA´LISE COMBINATO´RIA
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 91. Qual e´ o nu´mero de anagramas formados a partir da palavra VENEZUELA?
Exemplo 92. Qual e´ o nu´mero de anagramas da palavra MARROCOS?
Exemplo 93. Permutando os algarismos 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, quantos nu´meros de 10
algarismos podemos formar?
Exemplo 94. 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 95. 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 ?
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 ∈ Z, b 6= 0, enta˜o existe um u´nico par
(q, r) ∈ Z× Z tal que
a = bq + r, 0 ≤ r < |b|.
Demonstrac¸a˜o. (Existeˆncia) Seja A = {a − bq ∈ Z | a − bq ≤ 0, q ∈ Z}, enta˜o A 6= ∅,
pois a− b · 0 = a > 0, ou seja, a ∈ 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 ∈ 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| =
 a− b(q + 1), se b > 0a− b(q − 1), se b < 0
ou seja, 0 ≤ m < r0 e m ∈ 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) ∈ Z× Z tais que
a = bq1 + r, 0 ≤ r1 < b
e
a = bq2 + r2, 0 ≤ r2 < b.
65
66 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
⇒
 q1 = q2r2 − r1 = b(q1 − q2) = 0
⇒
 q1 = q2r1 = r2
⇒ (q1, r1) = (q2, r2)
Exemplo 96. Para encontrarmos (q, r) ∈ 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 ∈ 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) ∈ A× A | a | b}
e´ uma relac¸a˜o de ordem parcial sobre Z∗+, ou seja,
(i) (∀a ∈ A) (a | a) (Reflexiva)
(ii) (∀a, b, c ∈ Z) (a | b e b | c⇒ a | c) (Transitiva)
(iii) (∀a, b ∈ A) (a | b e b | a⇒ a = b) (Anti-sime´trica)
Demonstrac¸a˜o.
(i) Como a = 1 · a,∀a ∈ A, enta˜o a | a,∀a ∈ A.
(ii) Se a | b e b | c, enta˜o existem z1, z2 ∈ Z tais que b = z1a e c = z2b, o que implica
em c = z2(z1a) = (z2z1)a. Logo a | c.
67
(iii) Para a, b ∈ R∗+, temos que
(a | b e b | a)
⇒ (∃z1, z2 ∈ Z) (b = z1a e a = z2b)
⇒ (∃z1, z2 ∈ Z) (b = z1a e a = z2(z1a))
⇒ (∃z1, z2 ∈ Z) (b = z1a e a = (z2z1)a)
⇒ (∃z1, z2 ∈ Z) (b = z1a e 1 = z2z1)
a,b∈Z∗+⇒ (∃z1, z2 ∈ 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 ∈ 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 d′ ∈ Z satisfaz d′ | a e d′ | b, enta˜o d′ | 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 97. 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 ∈ Z d um divisor de a e de b. Enta˜o d | (αa+ βb),∀α, β ∈ Z.
Demonstrac¸a˜o. Se d | a e d | b, enta˜o existem z1, z2 ∈ Z tais que a = z1d e b = z2d.
Assim,
αa+ βb = α(z1d) + β(z2d) = (αz1 + βz2)d,
com αz1 + βz2 ∈ Z. Logo d | (αa+ βb).
68 CAPI´TULO 6. INTRODUC¸A˜O A` TEORIA DOS NU´MEROS
Proposic¸a˜o 4. Sejam a, b ∈ Z e A = {αa + βb | αa + βb > 0, α, β ∈ Z}, enta˜o
mdc(a, b) = minA.
Demonstrac¸a˜o. Pelo Princı´pio da Boa Ordem, existe m0 = minA.
Como d = mdc(a, b) e´ tal que d′ | a e d′ | b, enta˜o, pela proposic¸a˜o anterior, d |
(αa+ βb),∀α, β ∈ Z.