Matemática Discreta

Matematica Discreta

Josimar da Silva Rocha

2

Sumario

1 Fundamentos de Logica Matematica 7

1.1 Logica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.1.1 Sentencas ou Proposicoes Logicas . . . . . . . . . . . . . . . . . . 7

1.2 Conectivos Logicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.1 Conectivo de conjuncao (E): ∧ . . . . . . . . . . . . . . . . . . . . 7

1.2.2 Conectivo de disjuncao (OU): ∨ . . . . . . . . . . . . . . . . . . . 8

1.2.3 Conectivo de Negacao (NAO): ¬ . . . . . . . . . . . . . . . . . . 8

1.2.4 Conectivo de Implicacao ou conectivo condicional (SE ... ENTAO):

→ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2.5 Conectivo de bi-implicacao ou conectivo bicondicional (SE, E SO-

MENTE SE,): ↔ . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3 Tautologia e Contradicao . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4 Relacoes entre sentencas logicas . . . . . . . . . . . . . . . . . . . . . . . 11

1.4.1 Relacao de implicacao . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4.2 Relacao de equivalencia . . . . . . . . . . . . . . . . . . . . . . . 11

1.5 Sentenca abertas e Sentencas Fechadas . . . . . . . . . . . . . . . . . . . . 13

1.6 Quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.6.1 Quantificador universal . . . . . . . . . . . . . . . . . . . . . . . . 14

1.6.2 Quantificador existencial . . . . . . . . . . . . . . . . . . . . . . . 14

1.6.3 Negacao de sentencas quantificadas . . . . . . . . . . . . . . . . . 15

2 Conjuntos 19

2.1 Relacao de pertinencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2 Relacoes entre conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2.1 Relacao de igualdade . . . . . . . . . . . . . . . . . . . . . . . . . 19

3

4 SUMARIO

2.2.2 Relacao de continencia entre conjuntos . . . . . . . . . . . . . . . 19

2.3 Operacoes sobre conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3.1 Operacoes binarias . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3.2 Operacao unaria . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3.3 Operacao unaria restrita . . . . . . . . . . . . . . . . . . . . . . . 21

2.4 Princıpio da Inclusao-Exclusao . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Tecnicas de Demonstracao 31

3.1 Tecnica de demonstracao por exaustao . . . . . . . . . . . . . . . . . . . . 31

3.2 Tecnica de demonstracao direta . . . . . . . . . . . . . . . . . . . . . . . . 32

3.3 Tecnica de demonstracao por contraposicao . . . . . . . . . . . . . . . . . 33

3.4 Tecnica de demonstracao por contradicao (ou por absurdo) . . . . . . . . . 33

3.5 Princıpios de inducao matematica . . . . . . . . . . . . . . . . . . . . . . 35

4 Relacoes e Funcoes 45

4.1 Funcoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5 Analise Combinatoria 55

5.1 Princıpio das Casas de Pombo . . . . . . . . . . . . . . . . . . . . . . . . 55

5.2 Princıpio Fundamental da Contagem . . . . . . . . . . . . . . . . . . . . . 57

5.2.1 Princıpio da Multiplicacao . . . . . . . . . . . . . . . . . . . . . . 57

5.2.2 Princıpio da Soma . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.3 Outros Metodos de Contagem . . . . . . . . . . . . . . . . . . . . . . . . 59

5.4 Caso sem tecnica conhecida . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.5 Fatorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.6 Agrupamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.6.1 Arranjos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.6.2 Permutacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.6.3 Combinacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.6.4 Permutacoes com repeticao . . . . . . . . . . . . . . . . . . . . . . 64

6 Introducao a Teoria dos Numeros 65

6.1 Congruencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6.1.1 Propriedades das Congruencias . . . . . . . . . . . . . . . . . . . 79

SUMARIO 5

7 Conjuntos Enumeraveis 83

8 Grafos 93

8.1 Definicoes iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

8.2 Terminologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

8.3 Isomorfismo entre grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

8.4 Matrizes de Adjacencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

8.4.1 Matriz de adjacencia para grafo nao-direcionado (nao-orientado) . . 99

8.4.2 Matriz de adjacencia para grafo ponderado (valorado) . . . . . . . 105

8.5 Matriz de distancias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

8.5.1 Matriz de distancias para Grafos nao ponderados . . . . . . . . . . 105

8.5.2 Matriz de distancias 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 Algebra de Boole 115

9.1 Minimizacao de Funcoes Booleanas . . . . . . . . . . . . . . . . . . . . . 120

9.1.1 Metodo de Quine-McCluskey . . . . . . . . . . . . . . . . . . . . 120

9.1.2 Metodo de Karnaugh . . . . . . . . . . . . . . . . . . . . . . . . . 120

9.1.3 Desvantagens na utilizacao do metodo de reducao de Karnaugh . . 124

10 Duvidas Correlatas em aula 127

6 SUMARIO

Capıtulo 1

Fundamentos de Logica Matematica

1.1 Logica

1.1.1 Sentencas ou Proposicoes Logicas

Definicao 1. Uma afirmacao e uma sentenca (ou proposicao) logica se esta afirmacao

puder receber uma valoracao V (verdadeira) ou F (falsa).

1.2 Conectivos Logicos

1.2.1 Conectivo de conjuncao (E): ∧

Definicao 2. Conectivo de conjuncao (∧) e um conectivo que conecta duas sentencas

logicas para formar uma nova sentenca que recebe valoracao V (verdadeira) se as sentencas

conectadas por este conectivo possuem valoracao V (verdadeira).

Se p e q sao sentencas logicas entao a sentenca 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 CAPITULO 1. FUNDAMENTOS DE LOGICA MATEMATICA

Exemplo 1. • Se p : O aluno tirou nota maior ou igual a 6 e q : O aluno tem frequencia

maior ou igual a 75%; entao p ∧ q : O aluno foi aprovado.

1.2.2 Conectivo de disjuncao (OU): ∨

Definicao 3. Conectivo de disjuncao (∨) e um conectivo que conecta duas sentencas

logicas para formar uma nova sentenca que recebe valoracao V (verdadeira) se uma das

sentencas conectadas por este conectivo possui valoracao V (verdadeira).

Se p e q sao sentencas logicas entao a sentenca 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 frequencia

menor do que 75%; entao p ∨ q : O aluno foi reprovado.

Exemplo 3. • (V) p : Windows e um sistema operacional ou q pascal e uma linguagem

de programacao;

• (V) p : Windows nao e um sistema operacional ou q pascal e uma linguagem de

programacao;

• (V) p : Windows e um sistema operacional ou q pascal nao e uma linguagem de

programacao;

• (F) p : Windows nao e um sistema operacional ou q pascal nao e uma linguagem de

programacao;

1.2.3 Conectivo de Negacao (NAO): ¬

Definicao 4. Este conectivo serve para alterar a valoracao de uma sentenca logica. Desta

forma, se uma sentenca logica p tiver valoracao V entao ¬p possui valoracao F e se uma

sentenca logica p tiver valoracao F, entao ¬p possui valoracao V.

1.2. CONECTIVOS LOGICOS 9

Este conectivo pode ser representado pela seguinte tabela-verdade:

p ¬p

V F

F V

Exemplo 4. • Se p : o numero e primo, entao ¬p : o numero nao e primo.

• Se p : Choveu, entao ¬p : Nao choveu.

• Se p : Pedro foi aprovado, entao ¬p : Pedro nao foi aprovado.

1.2.4 Conectivo de Implicacao ou conectivo condicional (SE ... ENTAO):

→

Definicao 5. Conectivo de implicacao ou conectivo condicional (→) e um conectivo que

conecta duas sentencas logicas p e q para formar uma nova sentenca p → q que recebe

valoracao F (falsa) se, e somente se, p tem valoracao verdadeira e q tem valoracao falsa.

Neste caso, p e chamada de hipotese e q e chamada de tese.

Se p e q sao sentencas logicas entao a sentenca 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

Observacao 1. Para o sımbolo p→ q le-se se p entao q ou p implica em q.

Exemplo 5. Seja p : o numero m e maior do que 10 e q : o numero m e maior do que 3.

Assim, p→ q quer dizer que se o numero m e maior do que 10, entao o numero m e maior

do que 3.

Exemplo 6. Se n e um numero primo maior do que 2, entao n e impar.


1.2.5 Conectivo de bi-implicacao ou conectivo bicondicional (SE, E

SOMENTE SE,): ↔

Definicao 6. Conectivo de bi-implicacao ou conectivo bicondicional (↔) e um conectivo

que conecta duas sentencas logicas p e q para formar uma nova sentenca p↔ q que recebe

valoracao V (verdadeira) se, e somente se, p e q possuem a mesma valoracao.

Se p e q sao sentencas logicas entao a sentenca 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

Observacao 2. Para o sımbolo p↔ q le-se p se, e somente se, q.

Exemplo 7. Sejam p : n e um numero natural primo; q : n e um numero natural e seus

unicos divisores de n sao 1 e n. Entao p ↔ q significa que um numero n natural e primo

se, e somente se, seus unicos divisores sao 1 e n.

Exemplo 8. Sejam p : As retas r e s tem o mesmo coeficiente angular; q : As retas r e s

sao paralelas. Entao p ↔ q significa que duas retas sao paralelas se, e somente se, tem o

mesmo coeficiente angular.

1.3 Tautologia e Contradicao

Definicao 7. Se uma sentenca recebe valoracao V para quaisquer que sejam as valoracoes

das sentencas componentes, entao dizemos que esta sentenca e uma tautologia.

Exemplo 9. Mostre que (p→ q) ∧ (q → r)→ (p→ r) e uma tautologia.

Definicao 8. Se uma sentenca recebe valoracao F para quaisquer que sejam as valoracoes

das sentencas componentes, entao dizemos que esta sentenca e uma contradicao.

Exemplo 10. Prove que (p→ q) ∧ (p ∨ ¬q) e uma contradicao.

1.4. RELACOES ENTRE SENTENCAS LOGICAS 11

1.4 Relacoes entre sentencas logicas

1.4.1 Relacao de implicacao

Definicao 9. Relacao de implicacao: (⇒) Diz-se que uma sentenca logica (proposicao)

p implica em uma sentenca logica (ou proposicao) q, (p⇒ q), se a sentenca logica q tem

valoracao verdadeira V sempre que a sentenca logica q possuir valoracao 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 Relacao de equivalencia

Definicao 10. Relacao de equivalencia: (⇔) Diz-se que duas sentencas logicas (ou proposicoes)

p e q sao equivalentes, p⇔ q, quando suas tabelas-verdade forem iguais, ou seja, se p↔ q

e uma tautologia.

Equivalencias Notaveis

1. Dupla negacao

¬(¬p)⇔ p (1.1)

2. Idempotencia

p ∨ p⇔ p (1.2)

p ∧ p⇔ p (1.3)

3. Comutatividade

p ∨ q ⇔ q ∨ p (1.4)

p ∧ q ⇔ q ∧ p (1.5)


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. Contraposicao

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 programacao e comum utilizarmos conectivos logicos. Estes conectivos

logicos muitas vezes sao apresentados de uma forma (ou com um sımbolo) diferente do

que vimos aqui. A tabela abaixo apresenta alguns conectivos logicos utilizados com sua

representacao nas linguagens de programacao C e pascal.

Sımbolo padrao Linguagem C Linguagem Pascal

∧ && and

∨ || or

¬ ! notPara demonstrar que uma sentenca logica q formada a partir das sentencas constituintes

a, · · · , c e uma tautologia basta utilizarmos o seguinte algoritmo em C para demonstrar

esta condicao:

#include<stdlib.h>

#include<stdio.h>

1.5. SENTENCA ABERTAS E SENTENCAS 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 Sentenca abertas e Sentencas Fechadas

Definicao 11. Uma sentenca fechada e uma sentenca logica cuja valoracao nao depende

de atribuicao de valores para variaveis.

Exemplo 12. A sentenca p : 5 > 7 e uma sentenca fechada cujo valor logico e falso.

Definicao 12. Uma sentenca aberta e uma sentenca logica cuja valoracao depende de

atribuicao de valores para variaveis.

Exemplo 13. A sentenca q : x2 < 5 e uma sentenca aberta.

Definicao 13. O conjunto universo de uma sentenca aberta e o conjunto de todos os va-

lores atribuıdos as variaveis de modo a torna-la uma sentenca logica. O conjunto universo

e representado pela letra U (maiuscula).

Definicao 14. O conjunto verdade de uma sentenca aberta p(x) e o subconjunto de U

de todos os valores atribuıdos a variavel x de modo que p(x) seja verdadeira. O conjunto

verdade de uma sentenca aberta p(x) e representado por

V = {x ∈ U | v(p(x)) = V }.


1.6 Quantificadores

Definicao 15. Expressoes como “existe”, “para algum”, “para todos”, “para qualquer”que

expressao quantidades sao chamadas de quantificadores.

1.6.1 Quantificador universal

Definicao 16. Expressoes como “para todo”, “para qualquer”que expressam que para

qualquer elemento x do conjunto universo a sentenca aberta p(x) e verdadeira sao repre-

sentadas pelo que chamamos de quantificador universal ∀, de modo que a expressao

“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)

Observacao 3. Observe que se o conjunto-verdade de uma sentenca aberta p(x) for igual

ao conjunto universo U, entao a sentenca logica (∀x) (p(x)) e verdadeira, ou seja,

v ((∀x) (p(x))) = V ⇔ V = U.

1.6.2 Quantificador existencial

Definicao 17. Expressoes como “existe”ou “para algum”que expressam a existencia de

que para algum elemento x do conjunto universo a sentenca aberta p(x) e verdadeira

sao representadas pelo que chamamos de quantificador existencial ∃, de modo que a

expressao “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)

Observacao 4. Observe que se o conjunto-verdade de uma sentenca aberta p(x) for nao

vazio, entao a sentenca (∃x) (p(x)) e sempre verdadeira, ou seja,

v(p(x)) = V ⇔ V 6= ∅.

Definicao 18. Uma sentenca quantificada e uma sentenca formada a partir de quantifi-

cadores.

1.6. QUANTIFICADORES 15

1.6.3 Negacao de sentencas quantificadas

¬[(∀x)(p(x))]⇔ (∃x)(¬p(x))

e

¬[(∃x)(p(x))]⇔ (∀x)(¬p(x))

Exemplo 16. Negue as seguintes sentencas 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 Logica Matematica

1. Mostre que as seguintes sentencas logicas sao tautologias:

(a) (p↔ q)↔ (p→ q) ∧ (q → p)

(b) ¬(¬p ∨ ¬q)↔ (p ∧ q)

2. Mostre que as seguinte sentenca logica (p→ q) ∧ (p ∧ ¬q) e uma contradicao.

3. Sejam as proposicoes p : Joao joga futebol e q : Joao joga tenis. Escreva na lingua-

gem usual as seguintes proposicoes:

(a) p ∨ q

(b) p ∧ q


(c) p ∧ ¬q

(d) ¬p ∧ ¬q

(e) ¬(¬p)

(f) ¬(¬p ∧ ¬q)

4. Dadas as proposicoes p : Maria e bonita e q : Maria e elegante, escreva na linguagem

simbolica as seguintes proposicoes:

(a) Maria e bonita e elegante.

(b) Maria e bonita, mas nao e elegante.

(c) Nao e verdade que Maria nao e bonita ou elegante.

(d) Maria nao e bonita nem elegante.

(e) Maria e bonita ou nao e bonita e elegante.

(f) E falso que Maria nao e bonita ou que nao e elegante.

5. Se V (p) = V (q) = V e V (r) = V (s) = F, determinar os valores logicos das

seguintes proposicoes:

(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 sentencas logicas:

(a) (p→ q)→ r

(b) (p→ q) ∧ (q → r)

(c) (¬r → q) ∧ p

(d) ¬(p ∧ r) ∨ p

(e) p↔ r

8. Negue as seguintes sentencas logicas 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 sentencas logicas e escreva estas sentencas na forma simbolica.

(a) Todo retangulo e um quadrilatero.

(b) Nem todo polıgono e regular.

(c) Toda arvore que possui n vertices possui n− 1 arestas.

(d) Nenhuma arvore contem ciclos.

(e) Um grafo conexo e acıclico e uma arvore.

(f) Todo homem e bom.

(g) Existem homens valentes e homens covardes.


Capıtulo 2

Conjuntos

Os termos elemento e conjunto sao primitivos, ou seja, nao precisam ser definidos. Con-

junto da ideia de colecao de objetos, que sao os elementos do conjunto.

Daı, conjunto poder ser visto como sinonimo de colecao.

2.1 Relacao de pertinencia

Quando um elemento a pertence a um conjunto A utilizamos o sımbolo ∈ para representar

esta relacao, de modo que a ∈ A. Caso contrario, quando um elemento a nao pertence a

um conjunto A utilizamos o sımbolo 6∈ para representar esta relacao, de modo que a 6∈ A.

2.2 Relacoes entre conjuntos

2.2.1 Relacao de igualdade

Definicao 19. Dois conjuntos sao 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}, entao A = B, pois A e

B possuem os mesmos elementos.

2.2.2 Relacao de continencia entre conjuntos

Definicao 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 contem A) se todo elemento do

conjunto A e elemento do conjunto B. Utilizamos os sımbolos A ⊂ B (A esta contido

19

20 CAPITULO 2. CONJUNTOS

em B) e B ⊃ A (B contem A) para representar que o conjunto A e um subconjunto do

conjunto B.

No caso em que um conjuntoA nao e um subconjunto de um conjuntoB (ouA nao esta

contido em B ou que B nao contem A, entao existem elementos do conjunto A que nao

estao no conjunto B. Neste caso utilizamos os sımbolos A 6⊂ B (A nao esta contido em B)

e B ⊃ A (B nao contem A) para representar que o conjunto A nao 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 sao

(1) A ⊂ A.

(2) Se A ⊂ B e B ⊂ C, entao A ⊂ C.

(3) Se A ⊂ B e B ⊂ A, entao A = B.

(4) A ⊂ U.

Definicao 21. O Conjunto Universo U e o conjunto de todos os elementos do sistema.

Definicao 22. O Conjunto Vazio ∅ (ou {}) e o conjunto que nao possui elementos.

Definicao 23. Conjunto Unitario e um conjunto que possui apenas um elemento.

Exemplo 18. Os conjuntos {∅}, {{}} e {1} sao conjuntos unitarios.

2.3 Operacoes sobre conjuntos

As operacoes sobre conjuntos dividem-se em operacoes binarias, operac oes unarias e

operacoes restritas.

2.3. OPERACOES SOBRE CONJUNTOS 21

2.3.1 Operacoes binarias

Definicao 24. O conjunto intersecao 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.

Definicao 25. O conjunto uniao 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.

Definicao 26. O conjunto diferenca A − B e o conjunto formado pelos elementos que

estao em A e nao estao em B.

Em sımbolos, (∀x) ((x ∈ A−B)↔ (x ∈ A) ∧ (x 6∈ B)) e uma tautologia.

2.3.2 Operacao unaria

Definicao 27. O complementar de um conjunto A, AC (ou C(A) ou A) e o conjunto dos

elementos que estao no conjunto universo U mas que nao estao em A.

Em sımbolos, (∀x)(x ∈ AC ↔ x 6∈ A

)e uma tautologia.

2.3.3 Operacao unaria restrita

Definicao 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 estao em B e que nao estao 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}, entao

(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}.

Definicao 29. O conjunto das partes de um conjunto A, P (A) ou P(A), e o conjunto

dos subconjuntos de A.


Exemplo 20. Se A = {0; 1}, entao o conjunto das partes de A e o conjunto

P (A) = {∅; {0}; {1}; {0; 1}}

Exemplo 21. Se A = {1; 2; 3}, entao o conjunto das partes de A e o conjunto

P (A) = {∅; {1}; {2}; {3}; {1; 2}; {1; 3}; {2; 3}; {1; 2; 3}}

Observacao 5.

n(P (A)) =

(n(A)

0

)+

(n(A)

1

)+ · · ·+

(n(A)

n(A)

)= 2n(A)

Definicao 30. O conjunto diferenca simetrica 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. OPERACOES SOBRE CONJUNTOS 23

Demonstracao.

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 sentencas logicas e teoria dos conjuntos que pode ser

traduzida pela seguinte tabela, onde

p : x ∈ A e q : x ∈ B.

Sentenca equivalente Em conjuntos

p→ q A ⊂ B

p ∧ q A ∩B

p ∨ q A ∪B

Tautologia U

Contradicao ∅

¬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 relacao (A−B)∪ (A∩B) = A utilizando sentencas

logicas.

E suficiente mostrarmos que a sentenca

(p ∧ ¬q) ∨ (p ∧ q)↔ p

e sempre verdadeira

Construindo a tabela verdade para a sentenca 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


Como a coluna que corresponde a sentenca

(p ∧ ¬q) ∨ (p ∧ q)↔ p

assume apenas valoracao V, entao a relacao (A−B) ∪ (A ∩B) = A esta correta.

2.4 Princıpio da Inclusao-Exclusao

O numero de elementos da uniao de dois conjuntos e igual a soma do numero de elementos

de cada um dos conjuntos subtraıdo do numero de elementos da intersecao 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

concentracao nazista e de la resgataram 1500 prisioneiros. Desses, 650 estavam com

sarampo, 350 com tuberculose e 700 nao tinham nenhuma dessas duas doencas. Qual o

numero de prisioneiros com as duas doencas?

Resolucao grafica

S T

x650-x 350-x

700

2.4. PRINCIPIO DA INCLUSAO-EXCLUSAO 25

650 + 350− x+ 700 = 1500

⇒ 1700− x = 1500

⇒ x = 1700− 1500 = 200

Resposta: 200 prisioneiros.

Resolucao algebrica

n(U) = 1500

n(S) = 650

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 preferencia musical dos seus ouvintes, certa emis-

sora de radio realizou uma pesquisa, dando como opcao tres compositores: M, B e S. Os

resultados sao:

Votos Opcoes

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 Nao gostam de B, M e S


Qual e o numero de pessoas consultadas?

Resolucao algebrica:

n(B) = 27

n(M) = 34

n(S) = 40

n(B ∩M) = 16

n(B ∩ S) = 12

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.

Resolucao grafica


B M

S 4

6105 10

86

20

Resposta: 27 + 10 + 8 + 20 + 4 = 69 pessoas consultadas.

Observacao 6. O numero de informacoes necessarias e suficientes para resolver qual-

quer problema utilizando o Princıpio da Inclusao-Exclusao e 2m, onde m e o numero de

conjuntos envolvidos diferentes do conjunto universo.

Listas de Exercıcios sobre Conjuntos

1) Encontre P (A), se

(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 sao conjuntos arbitrarios.

4) Mostre que se (A−B) ∪ (B − A) = A ∪B, entao A ∩B = ∅.

Dica: Demonstre por contradicao.

5) Prove que se P (A) = P (B), entao A = B.


6) Verifique se as seguintes propriedades de conjuntos sao satisfeitas atraves de sentencas

logicas 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

(g) AC ∩DC

8) Numa escola de 630 alunos, 350 deles estudam Portugues, 210 estudam Espanhol e

90 estudam as duas materias (Portugues e Espanhol). Pergunta-se:

(a) Quantos alunos estudam apenas Portugues?

(b) Quantos alunos estudam apenas Espanhol?


(c) Quantos alunos estudam Portugues ou Espanhol?

(d) Quantos alunos nao estudam nenhuma das duas materias?

9) De 200 pessoas que foram pesquisadas sobre suas preferencias em assistir aos cam-

peonatos de corrida pela televisao, foram colhidos os seguintes dados: 55 dos entre-

vistados nao assitem; 101 assistem as corridas de Formula 1 e 27 assitem as corridas

de Formula 1 e de Motovelocidade. Quantas das pessoas entrevistadas assistem, ex-

clusivamente, as 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 Ciencia e o Museu

de Historia da cidade. Quarenta e oito alunos foram visitar pelo menos um desses

museus. 20% dos que foram ao de Ciencia visitaram o de Historia e 25% dos que

foram ao de Historia visitaram tambem o de Ciencia. Calcule o numero de alunos

que visitaram os dois museus.

12) Num grupo de 99 esportistas, 40 jogam volei, 20 jogam volei e xadrez, 22 jogam

xadrez e tenis, 18 jogam volei e tenis, 11 jogam as tres modalidades. O numero de

pessoas que jogam xadrez e igual ao numero de pessoas que jogam tenis. Quantas

jogam:

(a) tenis e nao jogam volei?

(b) xadrez ou tenis e nao jogam volei?

(c) volei e nao jogam xadrez?

13) Analisando-se as carteiras de vacinacao das 84 criancas de uma creche, verificou-se

que 68 receberam vacina Sabin, 50 receberam vacina contra sarampo e 12 nao foram

vacinadas. Quantas dessas criancas 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 nao apresentavam nenhum dos tipos de problemas citados. Qual e o

numero de aparelhos que apresentaram somente problemas de imagem?


15) Dos 80 alunos de uma turma, 15 foram reprovados em Matematica, 11 em Fısica e

10 em Quımica. Oito alunos foram reprovados simultaneamente em Matematica e

Fısica, seis em Matematica e Quımica e quatro em Fısica e Quımica. Sabendo que

3 alunos foram reprovados nas tres disciplinas, determine quantos alunos nao 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 nao 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).

Capıtulo 3

Tecnicas de Demonstracao

Uma proposicao (ou teorema) do tipo P → Q e formado por um conjunto P de hipoteses

que sao condicoes necessarias e que, conjuntamente, sao suficientes para se chegar a uma

conclusao (tese) Q.

Dentre as diversas tecnicas de demonstracao utilizadas, abordaremos as seguintes tecnicas:

• Tecnica de demonstracao por exaustao;

• Tecnica de demonstracao direta;

• Tecnica de demonstracao por contraposicao;

• Tecnica de demonstracao por contradicao.

Como ferramenta em algumas demonstracoes, abordaremos o Princıpio de inducao

matematica.

3.1 Tecnica de demonstracao por exaustao

Esta tecnica consiste na verificacao da validade da proposicao P → Q a partir da verificacao

de uma quantidade finita de casos particulares.

Exemplo 25. Demonstre que se um numero natural n satisfaz n ≤ 2, entao n! ≤ n+ 1.

Demonstracao. Neste caso

P : n ≤ 2

31

32 CAPITULO 3. TECNICAS DE DEMONSTRACAO

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 exaustao, se n ∈ N e n ≤ 2, entao n! ≤ n+ 1.

3.2 Tecnica de demonstracao direta

Esta tecnica consiste na verificacao da validade da proposicao P → Q a partir do cami-

nho natural que se inicia a partir da suposicao da validade da hipotese P para chegar na

verificacao da validade da tese Q.

Utilizaremos as seguintes definicoes nos proximos exemplos:

Definicao 31. Um numero inteiro n e um numero par se existir um numero inteiro k tal

que n = 2k.

Definicao 32. Um numero inteiro n e um numero ımpar se existir um numero inteiro k tal

que n = 2k + 1.

Exemplo 26. Demonstre que soma de dois numeros pares e um numero par.

Demonstracao. Sejam a e b numeros pares. Pela definicao de numero 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 numero par.

Exemplo 27. Demonstre que o quadrado de um numero par e tambem e um numero par.

Demonstracao. Seja n um numero par, entao, pela definicao, existe k ∈ Z tal que n = 2k.

Assim, n2 = (2k)2 = 4k2 = 2 · (2k2), com 2k2 ∈ Z.

Logo n2 e um numero par.

Exemplo 28. Demonstre que o quadrado de um numero ımpar tambem e um numero ımpar.

3.3. TECNICA DE DEMONSTRACAO POR CONTRAPOSICAO 33

3.3 Tecnica de demonstracao por contraposicao

Esta tecnica consiste em demonstrarmos a validade da proposicao P → Q a partir da

demonstracao da validade da proposicao ¬Q → ¬P, uma vez que a proposicao P → Q e

logicamente equivalente a sua contrapositiva ¬Q→ ¬P.

Exemplo 29. Se n ∈ N satisfaz n! > n+ 1, mostre que n > 2.

Demonstracao. Pelo exemplo 25 mostramos que a seguinte proposicao e valida:

Se n ∈ N satisfaz n ≤ 2, entao n! ≤ n+ 1.

Logo, sua contrapositiva

Se n ∈ N satisfaz n! > n+ 1, entao n > 2.

tambem e valida.

Exemplo 30. Prove que se n2 e ımpar, entao n e ımpar.

Demonstracao. Esta proposicao e logicamente equivalente a sua contrapositiva:

Se n e um numero par, entao n2 e um numero par.

Portanto, como a proposicao acima e verdadeira, pelo Exemplo 27, entao a demonstracao

segue por contraposicao.

Exemplo 31. Demonstre que se n2 e um numero par, entao n e um numero par.

3.4 Tecnica de demonstracao por contradicao (ou por ab-

surdo)

Esta tecnica consiste em demonstrarmos a validade da proposicao P → Q a partir da

suposicao de que P e ¬Q sao verdadeiras para chegar em uma afirmacao 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


Exemplo 32. Prove que se x ∈ Z, entao x2 + x 6= 1.

Demonstracao. Suponhamos que x ∈ Z e que x2 + x = 1.

Se x for par, entao existira k ∈ Z tal que x = 2k. Assim,

x2 + x = 1

⇒ (2k)2 + (2k) = 1

⇒ 2(2k2 + k) = 2 · 0 + 1k′=2k2+k⇒ 2k′ = 2 · 0 + 1,

o que e um absurdo.

Se x for impar, entao existira k ∈ Z tal que x = 2k + 1. Assim,

x2 + x = 1

⇒ (2k + 1)2 + (2k + 1) = 1

⇒ 4k2 + 4k + 1 + 2k + 1 = 1k′=2k2+2k+1∈Z⇒ 2(2k2 + 2k + 1) = 2 · 0 + 1,

o que e um absurdo.

Portanto, por contradicao, se x ∈ Z, entao x2 + x 6= 1.

Exemplo 33. Prove que se x2 = 2, entao x nao e um numero racional.

Demonstracao. Suponhamos que x ∈ Q e x2 = 2. Como x ∈ Q, entao x = ab

onde a e b

nao possuem divisores primos comuns. Assim,

(ab

)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 numero primo divisor comum de a e b e a e b nao

possuem divisores primos comuns.

3.5. PRINCIPIOS DE INDUCAO MATEMATICA 35

3.5 Princıpios de inducao matematica

Primeiro Princıpio de Inducao Matematica

Seja a ∈ Z e suponhamos que para cada inteiro n ≥ a esteja associada uma proposicao

P (n). Entao 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, entao P (k + 1) tambem e verdadeira.

Neste caso, utilizamos a seguinte denominacao:

• base de inducao: demonstrar que P (a) e verdadeira;

• hipotese de inducao: supor que P (k) e verdadeira para algum k ≥ a;

• passo de inducao: provar que se P (k) e verdadeira entao P (k + 1) tambem e

verdadeira para k ≥ a.

Exemplo 34. Prove por inducao que para qualquer n ∈ N, vale n < 2n.

Exemplo 35. Prove por inducao que para qualquer n ∈ N, se n > 3, entao 2n < n!.

Exemplo 36. Prove por inducao que para qualquer n ∈ N, tem-se que

1 + 2 + · · ·+ n =n(n+ 1)

2

Demonstracao. Seja P (n) : 1 + 2 + 3 + · · ·+ n = n(n+1)2

.

Base de Inducao:

Como 1 = 1·(1+1)2

, entao P (1) e verdadeira.

Hipotese de Inducao:

Suponhamos que P (k) seja verdadeira.

Passo de Inducao:

Como P (k) e verdadeira, entao

1 + 2 + 3 + · · ·+ k =k(k + 1)

2.

Assim,1 + 2 + 3 + · · ·+ k + (k + 1) = k(k+1)

2+ (k + 1)

= (k + 1)[k2+ 1]

= (k + 1)[k+22

]= (k+1)((k+1)+1)

2.


Portanto, P (k + 1) e verdadeira.

Logo, por inducao P (n) : 1 + 2+ 3+ · · ·+ n = n(n+1)2

e verdadeira para todo n ∈ N∗.

Outra demonstracao 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 inducao, 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.

Demonstracao. Seja p(n) : n2 > 2n+ 1.

Como 32 = 9 > 7 = 2 · 3 + 1, entao 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 inducao, n2 > 2n+ 1 para todo n ∈ N, n ≥ 3.

Exemplo 38. Mostre que 1 + 3 + 32 + · · ·+ 3n = 3n+1−12

para todo n ∈ N.

Demonstracao. Seja p(n) : 1 + 3 + 32 + · · ·+ 3n = 3n+1−12

.

Como 1 = 3−12

= 30+1−12

, entao p(0) e verdadeira.

Suponhamos que p(m) seja verdadeira para algum m ∈ 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)− 1

2

⇒ 1 + 3 + 32 + · · ·+ 3n+1 = 3n+2−12

.

Portanto, p(m+ 1) e verdadeira.

Logo, por inducao, 1 + 3 + · · ·+ 3n = 3n+1−12

para todo n ∈ N.


Segundo Princıpio de Inducao Matematica

Seja a ∈ Z e suponhamos que para cada inteiro n ≥ a esteja associada uma proposicao

P (n). Entao 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, entao 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.

Demonstracao. 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.




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, entao k = (k−4)+4 tambem pode ser escrito como somas com

parcelas iguais a 4 e/ou 5. Logo P (k) tambem e verdadeira.

Logo, por inducao, P (n) e verdadeira para todo numero 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 numero natural maior ou igual a 2 ou e primo ou pode ser

escrito como produto de numeros primos.

Demonstracao. Seja p(n) : n e um numero primo ou n pode ser escrito como produto de

numeros primos.

Seja m um numero natural maior ou igual a 2.


Se m = 2, entao p(2) e verdadeira, pois 2 e um numero primo.

Se m > 2 e m e primo, entao, p(m) e verdadeira.

Se m > 2 e m e composto, entao existem numeros naturais a, b maiores ou iguais a 2

tais que m = a · b. Como a e b sao numeros 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 numeros primos e b ou e primo ou pode ser escrito como produto de numeros primos.

De qualquer forma, concluimos que m e o produto de numeros primos. Portanto, p(m) e

verdadeira.

Logo, pelo segundo princıpio de inducao, todo numero natural maior ou igual a 2 ou e

primo ou pode ser escrito como produto de numeros primos.


Lista de Exercıcios sobre Tecnicas de Demonstracao

Alem das definicoes de numero par e de numero ımpar, citadas no texto, para a seguinte

lista de exercıcios, utilizamos as seguintes definicoes:

(1) Dizemos que a divide b ou que a e um divisor de b ou que b e um multiplo 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 modulo n ou que a e equivalente a b modulo 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), entao d e o menor inteiro positivo satisfazendo

d = x · a+ y · b,

para x, y ∈ Z.

(6) Dizemos que um numero inteiro p > 1 e um numero primo se os unicos divisores

inteiros positivos de p sao 1 e p.

Tecnica de Demonstracao Direta

1) Sejam a, b e c inteiros. Se a | b e b | c, entao a | c.

2) Se x e um inteiro par, entao x2 − 6x+ 5 e ımpar.

3) Se a, b, c ∈ N, entao mmc(ca, cb) = c ·mmc(a, b).

4) Sejam x e y numeros positivos. Se x ≤ y, entao√x ≤ √y.

5) Se x e y sao numeros reais positivos, entao 2√xy ≤ x+ y.


6) Se n ∈ N, entao 1 + (−1)n(2n− 1) e um multiplo de 4.

7) Todo multiplo de 4 tem a forma 1 + (−1)n(2n− 1) para algum n ∈ N.

8) Suponha que x, y ∈ Z. Se x e y sao pares, entao xy e par.

9) Suponha que x, y ∈ Z. Se x e y sao ımpares, entao xy e ımpar.

10) Suponha que a, b, c ∈ Z. Se a | b e a | c, entao a | (b+ c).

11) Suponha que a, b ∈ Z. Se a | b, entao a2 | b2.

12) Seja a um inteiro. Se 5 | 2a, entao 5 | a.

13) Seja a um inteiro. Se 7 | 4a, entao 7 | a.

14) Sejam a, b ∈ Z. Se a | b, entao a | (3b3 − b2 + 5b).

15) Sejam a, b, c, d ∈ Z. Se a | b e c | d, entao ac | bc.

16) Se x ∈ R e 0 < x < 4, entao4

x(4− x)≥ 1.

17) Se n ∈ Z, entao 5n2 + 3n+ 7 e ımpar.

18) Se n ∈ Z, entao n2 + 3n+ 4 e par.

19) Sejam a, b e c inteiros. Se a2 | b e b3 | c, entao a6 | c.

20) Se n ∈ N e n ≥ 2, entao os numeros n! + 2, n! + 3, n! + 4, · · · , n! + n sao todos

compostos. Consequentemente, para qualquer n ≥ 2, podemos encontrar n consecu-

tivos numeros compostos. Isto significa que existe um arbitrariamente largo deserto

de numeros primos.

21) Todo numero inteiro ımpar e diferenca de dois quadrados.

Tecnica de demonstracao por contraposicao

22) Seja x ∈ Z. Se 7x+ 9 e par, entao x e ımpar.

23) Se x2 − 6x+ 5 e par, entao x e ımpar.

24) Sejam x, y ∈ R. Se y3 + yx2 ≤ x3 + xy2, entao y ≤ x.

25) Sejam x, y ∈ Z Se 5 - xy, entao 5 - x e 5 - y.


26) Sejam a, b ∈ Z e n ∈ N. Se a ≡ b( mod n), entao a2 ≡ b2(modn).

27) Sejam a, b ∈ Z e n ∈ N. Se 12a 6≡ 12b(modn), entao n - 12.

28) Seja x ∈ R. Se x2 + 5x < 0, entao x < 0.

29) Seja x ∈ R. Se x3 − x > 0, entao x > −1.

30) Sejam x, y, z ∈ Z e x 6= 0. Se x - yz, entao x - y e x - z.

31) Se n ∈ N e 2n − 1 e primo, entao n e primo.

32) Se n ∈ Z, entao 4 - (n2 − 3).

Tecnica de demonstracao por contradicao

33) Se a, b ∈ Z, entao a2 − 4b 6= 2.

34) Existem infinitos numeros primos.

35) Para todo numero real x ∈ [0, π/2], temos sen x+ cosx ≥ 1.

36) Prove que 3√2 e irracional.

37) Se a, b ∈ Z, entao a2 − 4b− 2 6= 0.

38) Para todo n ∈ Z, 4 - (n2 + 2).

39) Nao existem numeros inteiros a e b tal que 18a+ 6b = 1.

Princıpio de Inducao Matematica

40) Se n ∈ N, entao 1 + 3 + 5 + 7 + · · ·+ (2n− 1) = n2.

41) Se n e um inteiro nao-negativo, entao 5 | (n5 − n).

42) Se n ∈ Z e n ≥ 0, entao∑n

i=0 i · i! = (n+ 1)!− 1.

43) Se n ∈ N, entao (1 + x)n ≥ 1 + nx para todo x ∈ R com x > −1.

44) Se n ∈ N e n ≥ 1, entao

1 + 2 + 3 + 4 + · · ·+ n =n2 + n

2.


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, entao

1 · 3 + 2 · 4 + 3 · 5 + · · ·+ 4 · 6 + · · ·+ n(n+ 2) =n(n+ 1)(2n+ 7)

6.

48) Se n ∈ N, entao

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 numero natural n,

2n + 1 ≤ 3n.

Observacao: Nas demonstracoes destes exercıcios e valido citar qualquer resultado

conhecido, desde que a demonstracao deste resultado nao seja equivalente a demonstracao

do exercıcio.

Resposta dos Exercıcios sobre Tecnicas de Demonstracao

1) Como a | b e b | c, entao 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, entao 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) Sejam d1 = mmc(a, b) e d2 = mmc(ac, bc).

Se d1 = mmc(a, b), entao

a | d1 e b | d1⇒ ac | cd1 e bc | cd1⇒ d2 | cd1

Se d2 = mmc(ac, bc), entao

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, entao d2 = cd1, ou seja, mmc(ac, bc) = cmmc(a, b).

4) Como√x+√y > 0, entao 1√

y+√x> 0. Alem disso, como x ≤ y, entao 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, entao 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).


Capıtulo 4

Relacoes e Funcoes

Definicao 33. Sejam A e B conjuntos. Uma relacao 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}, entao

A×B = {(1; 1); (1; 3); (1; 5); (2; 1); (2; 3); (2; 5)}

e teremos 2n(A×B) = 26 = 64 relacoes deA emB.Uma destas relacoes eR = {(1; 3); (2; 5); (2; 3)}.

Relacoes sobre um conjunto

Definicao 34. Uma relacao R sobre A e uma relacao de um conjunto A em A.

Definicao 35. Seja R uma relacao sobre A.

(1) Se (∀a ∈ A) ((a, a) ∈ R) , entao R e chamada de relacao reflexiva.

(2) Se (a, b) ∈ R implicar em (b, a) ∈ R para todos a, b ∈ A, entao R e chamada de

relacao simetrica.

(3) Se (a, b) ∈ R e (b, c) ∈ R implicarem em (a, c) ∈ R para todo a, b, c ∈ A, entao R

e chamada de relacao transitiva.

(4) Se (a, b) ∈ R e (b, a) ∈ R implicarem em a = b, entao R e chamada de relacao

anti-simetrica.

(5) Uma relacao R e uma relacao de equivalencia, se R satisfaz as propriedades (1),

(2) e (3), ou seja, se R e reflexiva, simetrica e transitiva.

45

46 CAPITULO 4. RELACOES E FUNCOES

5

7 3

1

77

2

SS

??

Figura 4.1: R(A)

(6) Uma relacao R e uma relacao de ordem parcial, se R satisfaz as propriedades (1),

(3) e (4), ou seja, se R e reflexiva, anti-simetrica e transitiva.

Se A e B sao conjuntos finitos, entao toda relacao R de A em B pode ser representada

por um grafo direcionado cujos vertices sao os pontos de A e de B e cujas arestas sao

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}, entao a relacao R de A em B definida por

R = {(1; 3); (2; 5); (2; 3)}

pode ser representada graficamente pelo grafo da figura 3.1.

Definicao 36. Um ciclo e uma aresta que conecta um vertice nele mesmo.

Observacao 7. Graficamente:

• Uma relacao R sobre A e reflexiva se existem ciclos em cada elemento de A;

• Uma relacao R sobre A e simetrica se nao existem setas simples ligando elementos

de A;

• Uma relacao 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 relacaoR sobreA e anti-simetrica se nao existem setas duplas ligando elemen-

tos de A.

Exemplo 43. Se R = {(a, b) ∈ N × N | a | b}, entao R e uma relacao de ordem parcial

sobre N.

De fato,

47

(i) Se a ∈ A, entao a = 1 · a, i.e., a e multiplo 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 multiplo de a e c e multiplo

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 multiplo 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 multiplo de a e c e multiplo 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 multiplo de a)

⇒ ((a, c) ∈ R)

Logo R e transitiva.

(iii) Sejam a, b ∈ N tais que (a, b) ∈ R e (b, a) ∈ R, entao 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-simetrica.

Logo, por (i), (ii) e (iii), R e uma relacao de ordem parcial sobre A.

Exemplo 44. Seja A um conjunto. Se R = {(B,C) ∈ P (A) × P (A) | B ⊂ C}, entao R

e uma relacao de ordem parcial sobre P (A).

De fato,

(i) Como B ⊂ B para todo B ⊂ A, entao (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-simetrica.

(iii) Sejam B,C,D ∈ P (A) tais que (B,C) ∈ R e (C,D) ∈ R, entao B ⊂ C e C ⊂ D,

o que implica em B ⊂ D. Assim, (B,D) ∈ R. Logo R e transitiva.


ComoR e reflexiva, anti-simetrica e transitiva, entaoR e uma relacao de ordem parcial

sobre P (A).

Exemplo 45. Sejam A e B conjuntos disjuntos e R uma relacao de ordem sobre A ∪ B

definida por

R = {(a, b) ∈ (A ∪B)× (A ∪B) | {a, b} ⊂ A ou {a, b} ⊂ B},

entao R e uma relacao de equivalencia sobre A ∪B.

De fato, como

(1) Se a ∈ A ∪ B, entao {a, a} ⊂ A ou {a, a} ⊂ B. Logo (a, a) ∈ R. Portanto R e

reflexiva.

(2) Se (a, b) ∈ R, entao {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 simetrica.

(3) Se (a, b) ∈ R e (b, c) ∈ R, entao {a, b} ⊂ A ou {a, b} ⊂ B e {b, c} ⊂ A ou

{b, c} ⊂ B. Como A ∩ B = ∅, entao {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 relacao de equivalencia.

Definicao 37. Dizemos que R∗ e o fecho de uma relacao R por uma propriedade P se R∗

e a menor relacao que contem 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, entao R∗ ⊂ S.

Exemplo 46. Encontre os fechos reflexivo, simetrico 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 simetrico 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)}

Definicao 38. Se R e uma relacao de equivalencia sobre um conjunto A, entao, para cada

x ∈ A podemos definir uma classe de equivalencia para esta relacao R como sendo o

conjunto

[x] = {a ∈ A | (a, x) ∈ R}

Notacao 1. O conjunto das classes de equivalencia de uma relacao R sobre um conjunto

A e representado pelo sımbolo A/R.

Lista de Exercıcios sobre Relacoes

(1) Mostre que a relacao R definida por

R = {(a, b) ∈ Z× Z | a ≡ b mod 5}

e uma relacao de equivalencia 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 relacao R definida por

R = {(a, b) ∈M ×M | a e prefixo de b}

e uma relacao 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 relacao R sobre P (X) definida por

R = {(A,B) ∈ P (X)× P (X) | n(A) = n(B)}

e uma relacao de equivalencia e encontre P (X)/R.

(4) Encontre todas as relacoes de equivalencia sobre A = {1; 2; 3}.

(5) Encontre todas as relacoes de ordem sobre A = {1; 2; 3}.


(6) Construir sobre o conjunto E = {a, b, c, d} relacoes R1, R2, R3 e R4 tais que R1

so tem a propriedade reflexiva, R2 so a simetrica, R3 so a transitiva e R4 so a anti-

simetrica.

(7) Seja A = {x ∈ Z | |x| ≤ 5} a relacao definida por (x, y) ∈ R⇔ x2+2x = y2+2y.

Mostre que R e uma relacao de equivalencia.

(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 relacao de equivalencia e encontre E/R.

(9) SejaR a relacao sobre Q definida da forma seguinte (x, y) ∈ R⇔ x−y ∈ Z. Provar

que R e uma relacao de equivalencia.

(10) Seja R = {(x, y) ∈ R2 | x− y ∈ Q}. Provar que R e uma relacao de equivalencia.

4.1 Funcoes

Definicao 39. Uma funcao f de A em B e uma relacao que associa a cada elemento x do

conjunto A um unico elemento y do conjunto B. Como este elemento y ∈ B e unico para

cada x ∈ A, entao e comum representarmos este elemento por f(x), ou seja, y = f(x).

Notacao 2. Usamos o sımbolo f : A→ B para representarmos que f e uma funcao de A

em B.

Definicao 40. Seja f : A→ B, entao

• 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}

Definicao 41. Funcoes reais sao funcoes f : A→ B, onde A ⊂ R e B = R.

4.1. FUNCOES 51

Quando precisamos encontrar o domınio de uma funcao real f dada por uma formula

matematica significa que precisamos encontrar o maior subconjunto A de R de tal forma

que faca sentido definirmos f como sendo uma funcao de A em R.

Exemplo 47. Encontre o domınio e a imagem da funcao 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 nao existem raızes reais de numeros negativos, entao 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+x1−x .

A condicao de existencia para que f seja uma funcao real e que

1+x1−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+.

Definicao 42. Uma funcao f : A→ B e sobrejetora ou sobrejetiva se Im(f) = B.

Exemplo 50. Uma funcao f : R → R∗+ definida por f(x) = x2 e sobrejetora, pois

Im(f) = R+ = CDom(f).

Definicao 43. Uma funcao 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))


Exemplo 51. Uma funcao f : R→ R definida por f(x) = 2x e injetora, pois

(∀a, b ∈ R)(2a = 2b ⇒ a = b

).

Definicao 44. Uma funcao f : A → B e bijetora ou bijetiva se f for injetora e sobreje-

tora.

Exemplo 52. A funcao 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−32

)= 2 c−3

2+ 3 = c− 3 + 3 = c

).

Logo f e bijetora.

Definicao 45. Sejam f : A → B e g : C → D funcoes tais que B ⊂ C. A funcao

composta de g e f e uma funcao g ◦ f : A→ D tal que (g ◦ f)(x) = g(f(x)).

Exemplo 53. Se f(x) = 1x

e g(x) =√x, entao (f ◦ g)(x) = 1√

x.

Definicao 46. Seja f : A → B uma funcao injetiva. A funcao inversa de f e uma funcao

f−1 : Im(f)→ A tal que f−1(y) = x⇒ f(x) = y.

Exemplo 54. Calcule f−1, onde f(x) = 2x− 5.

Definicao 47. Sejam f : A → B e g : C → B com C ⊆ A. Dizemos que g e a restricao

de f ao conjunto C se

g(x) = f(x),∀x ∈ C.

Notacao 3. Utilizamos g = f |C quando g e a restricao 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 numeros

pares, entao g : S → N definida por g(n) = 1 e uma restricao de f ao subconjunto S de

N.

Definicao 48. Sejam f : A→ B e g : C → D com A ⊆ C e B ⊆ D. Dizemos que g e um

prolongamento (ou extensao ) de f se

f(x) = g(x),∀x ∈ A.

Exemplo 56. Se f : R − {1} → R e g : R → R sao definidas por f(x) = x2−1x−1 e

g(x) = x+ 1, entao g e um prolongamento (ou extensao) de f.

4.1. FUNCOES 53

Lista de Exercıcios sobre Funcoes

1) Prove que se f : A→ B e sobrejetora, entao existe C ⊆ A com f |C bijetora.

2) Prove que se f : A→ B e bijetora, entao a aplicacao inversa f−1 : B → A tambem

e bijetora.

3) Prove que se f : A→ B e injetora e B for finito, entao A tambem e finito.

4) Prove que se f : A→ B e sobrejetora e A for finito, entao B tambem e finito.

5) Prove que se f : A→ B e g : B → C sao aplicacoes injetoras, entao g ◦ f : A→ C

tambem e uma aplicacao injetora.

6) Prove que se f : A→ B e g : B → C sao aplicacoes sobrejetoras, entao g ◦f : A→

C tambem e uma aplicacao injetora.

7) Prove que se f : A→ B e g : B → C sao aplicacoes bijetoras, entao g ◦ f : A→ C

tambem e uma aplicacao bijetora.


Capıtulo 5

Analise Combinatoria

5.1 Princıpio das Casas de Pombo

Definicao 49 (Princıpio das Casas de Pombo). Se mais de k itens sao colocados em k

caixas, entao pelo menos uma caixa contem mais de um item.

Exemplo 57. Quantas pessoas precisam estar presentes em uma sala para garantir que

duas delas tenham o ultimo nome comecando com a mesma letra?

Exemplo 58. Prove que, se quatro numeros forem escolhidos do conjunto {1, 2, 3, 4, 5, 6},

pelo menos um par tem que somar 7.

Exemplo 59. Quantas pessoas deverao estudar numa escola para garantir que pelo menos

2 destas pessoas tenham nascido:

• no mesmo mes?

• no mesmo dia da semana?

• no mesmo mes e no mesmo dia da semana?

• no mesmo mes e no mesmo dia?

• no mesmo dia e no mesmo dia da semana?

• no mesmo mes, no mesmo dia da semana e no mesmo dia?

55

56 CAPITULO 5. ANALISE COMBINATORIA

Lista de Exercıcios sobre Princıpios das Casas de Pombos

1) Mostre que num grupo de 5 inteiros (nao 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 (nao

necessariamente consecutivos) existem dois com exatamente o mesmo resto quando

divididos por d.

3) Entre 100 pessoas, quantas pelo menos nasceram no mesmo mes?

4) Entre 2012 pessoas, quantas pelo menos nasceram no mesmo dia da semana?

5) Qual e o menor numero de estudantes que se deve ter em um curso para garantir que

pelo menos 6 irao receber a mesma nota, sabendo que as possıveis notas sao 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 sao os mesmos?

8) Quantas pessoas no mınimo sao necessarias para garantir que numa sala existam 2

pessoas que tenham nascido no mesmo mes?

9) Quantas pessoas no mınimo sao necessarias para garantir que numa sala existam n

pessoas que tenham nascido no mesmo mes?

10) Se tenho n caixas. Quantos objetos, no mınimo, sao necessarios para garantir que

existam m objetos numa mesma caixa?

11) Se tenho m objetos e k < m. Quantas caixas devo ter no maximo para garantir que

existam k objetos numa mesma caixa?

5.2. PRINCIPIO FUNDAMENTAL DA CONTAGEM 57

5.2 Princıpio Fundamental da Contagem

5.2.1 Princıpio da Multiplicacao

Se uma decisao d1 pode ser tomada de x maneiras e se, uma vez tomada a decisao d1, a

decisao d2 puder ser tomada em y maneiras entao o numero de maneiras de se tomarem as

decisoes d1 e d2 e xy.

5.2.2 Princıpio da Soma

Se uma decisao d1 pode ser tomada de x maneiras e uma decisao d2 pode ser tomada de y

maneiras e estas decisoes sao tomadas de forma independente (disjuntas), entao o numero

de maneiras distintas de se tomarem as decisoes d1 ou d2 e 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-Sao Paulo-Rio, posso usar como transporte o

trem, o onibus ou o aviao. De quantos modos posso escolher os transportes se nao desejo

usar na volta o mesmo meio de transporte usado na ida?

Resposta: 3︸︷︷︸ida

· 2︸︷︷︸volta

= 6.

Exemplo 62. As placas dos automoveis sao 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




= 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 numeros diferentes podem ser formados multiplicando alguns (ou

todos) dos numeros 1, 5, 6, 7, 7, 9, 9, 9?


Resposta: Os numeros formados multiplicando alguns (ou todos) dos numeros 1, 5, 6, 7, 7, 9, 9, 9

tem 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 selecao brasileira de futebol ira disputar um torneio internacional com

outras cinco selecoes, no sistema “todos jogam contra todos uma unica vez”. Quais as

possıveis sequencias de resultados – vitoria (V), empate (E) e derrota (D) – da equipe

brasileira nesse torneio?

Exemplo 66. No primeiro semestre de 2012 serao oferecidas quatro turmas de Calculo I,

tres turmas de Geometria Analıtica, duas turmas de Fundamentos de Matematica Elemen-

tar e apenas uma turma de Introducao a Logica Matematica. Sabendo-se que um calouro

aprovado para o curso de Matematica devera cursar todas as disciplinas acima mencio-

nadas, de quantas maneiras distintas ele podera se matricular nas mesmas, levando-se em

consideracao que as turmas de uma mesma disciplina sao oferecidas num mesmo horario

e nao existe coincidencia de horarios entre as disciplinas?

Exemplo 67. (a) Quantos numeros de cinco algarismos existem?

(b) Quantos numeros ımpares de cinco algarismos existem?

(c) Quantos numeros pares de cinco algarismos distintos existem?

Exemplo 68. Um dado foi lancado n vezes sucessivamente. Sabendo-se que o numero de

sequencias de faces possıveis de se obter e 368, qual e o valor de n?

Exemplo 69. Para os hospedes que desejam tomar cafe da manha no quarto, um hotel

oferece as seguintes opcoes:

• bebidas quentes: chocolate, cafe puro, cha e cafe com leite.

• sucos: laranja e abacaxi.

• paes: croissant, pao frances, pao de forma e pao integral.

5.3. OUTROS METODOS DE CONTAGEM 59

• queijo: branco, mussarela e queijo prato.

O hospede X fez a seguinte solicitacao: um suco, um pao e um tipo de queijo. O

hospede Y pediu: uma bebida quente ou um suco, um pao e um tipo de queijo. De quantas

formas distintas cada hospede podera ser servido?

Exemplo 70. Num hospital existem 3 portas de entrada que dao para um amplo saguao 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 eleicao de uma escola ha tres candidatos a presidente, cinco a vice-

presidente, seis a secretario e sete a tesoureiro. Quantos podem ser os resultados da

eleicao?

5.3 Outros Metodos de Contagem

Exemplo 72. Dois premios sao sorteados entre 10 pessoas. Quantos serao os possıveis

resultados, sabendo que uma pessoa nao pode ser sorteada mais de uma vez?

5.4 Caso sem tecnica conhecida

Caso sem tecnica conhecida

Quero retirar 100 reais de um caixa eletronico que dispoe de notas de 5 e 10 reais. Quantas

serao as possibilidades para este saque?

5.5 Fatorial

Fatorial de um numero natural

O Fatorial de um numero natural n e definido matematicamente por

n! =

1 se n = 0

n(n− 1)! se n ∈ N∗

Exercıcio 2. Calcule o valor de:


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 equacoes:

(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 tres 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) Permutacoes (arranjos, onde k=n);

(c) Combinacoes (a ordem nao importa).

5.6.1 Arranjos

Arranjos

Definicao 50. Dado um conjunto com n elementos distintos, chama-se arranjo dos n ele-

mentos, tomados k a k, a qualquer sequencia ordenada de k elementos distintos escolhidos

entre os n existentes.

Obtencao da Formula:

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 gremio de um

colegio, 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 sequencia

de quatro letras distintas (alfabeto com 26 letras) seguida por dois algarismos distintos.

(a) Quantas sao 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, mae e tres filhos) nasceram

em meses diferentes do ano. Quantas sao as sequencias 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

cobranca de penaltis. Cada um escolhe, de todas as formas possıveis, um colega para

bater o penalti e um outro para tentar defende-lo.

(a) Quantas cobrancas de penalti sao feitas nessa brincadeira?

(b) Quantas cobrancas haveria se o grupo resolvesse convidar um setimo amigo para

que ele escolhesse, de todas as formas possıveis, o cobrador e o defensor do penalti?

5.6.2 Permutacoes

Permutacoes

Definicao 51. Quando uma sequencia ordenada (arranjo) e formada por todos os elemen-

tos disponıveis, dizemos que se trata de uma permutacao. Assim, o numero de permutacoes

Pn de n elementos distintos e

Pn = n!


Exemplo 77. Quais sao 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

Sao p4 = 4! = 4 · 3 · 2 · 1 = 24 anagramas.

Exemplo 78. Jose e Maria tem tres filhos: Thiago, Pedro e Andre. A famılia quer tirar

uma foto de recordacao de uma viagem na qual todos aparecam 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 sao?

(b) Quantos comecam por vogal?

(c) Quantos comecam e terminam por consoante?

(d) Quantos tem as letras CON juntas e nessa ordem?

(e) Quantos apresentam a letra C antes da letra A?

Exemplo 80. Dona Lola tem tres filhos: Pedro, Paulo e Andre. Os tres casaram-se e

tem, respectivamente, 1, 3 e 2 filhos. Em um domingo, dona Lola recebeu, para o almoco,

seus tres filhos, acompanhados das respectivas esposas, alem de todos os netos. Como

recordacao, 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 numeros de 5 algarismos distin-

tos, obtidos com 1, 3, 4, 6 e 7, qual sera a posicao do numero 61473 ?

5.6. AGRUPAMENTOS 63

5.6.3 Combinacoes

Definicao 52. Dado um conjunto A com n elementos distintos, chama-se combinacao dos

n elementos de A, tomados k a k, qualquer subconjunto de A formado por k elementos.

Formula para o Calculo do numero de Combinacoes

Cn,k =An,kk!

=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 triangulos existem com vertices 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 circunferencia marcam-se dez pontos.

(a) Qual e o numero de segmentos de reta que podemos tracar com extremidades em

dois desses pontos?

(b) Quantos triangulos podemos construir com vertices em tres desses pontos?

(c) Quantos polıgonos com 4, 5, 6 ou 7 lados podem ser tracados com vertices nesses

pontos?

Exemplo 89. Em um curso de espanhol estudam vinte alunos, sendo dozes rapazes e oito

mocas. O professor quer formar uma equipe de quatro alunos para intercambio em outro

paıs. Quantas equipes de dois rapazes e duas mocas podem ser formadas?

Exemplo 90. Para montar uma cesta de cafe da manha estao disponıveis os seguintes

itens: quatro tipos de paes, tres tipos de queijo, tres tipos de frutas, cinco sabores de geleia

e quatro sabores de tortas doces. De quantos modos distintos a ceta podera ser montada se

um cliente pedir dois tipos de paes, um tipo de queijo, duas frutas, dois sabores de geleia

e um torta doce?


5.6.4 Permutacoes com repeticao

Permutacoes com repeticao

Definicao 53. Nos casos em que cada resultado possıvel e uma sequencia ordenada, nos

quais ocorre repeticao de elementos, dizemos que se trata de permutacao com repeticao.

Formula Geral

Se temos n elementos, dos quais

• n1 sao iguais a a1,



...

• nk sao iguais a ak,

entao o numero de permutacoes possıveis e dado por

p(n1,n2,··· ,nk)n =

n!

n1!n2! · · ·nk!

Exemplo 91. Qual e o numero de anagramas formados a partir da palavra VENEZUELA?

Exemplo 92. Qual e o numero de anagramas da palavra MARROCOS?

Exemplo 93. Permutando os algarismos 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, quantos numeros de 10

algarismos podemos formar?

Exemplo 94. Uma prova e constituıda de dez testes do tipo V ou F.

(a) Quantas sequencias de respostas sao possıveis?

(b) Quantas sequencias apresentam tres respostas V e sete respostas F?

Exemplo 95. Quantos numeros 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

Introducao a Teoria dos Numeros

Princıpio da Boa Ordem: Todo subconjunto nao vazio do conjunto dos numeros inteiros

constituıdo de elementos nao negativos possui um mınimo.

Proposicao 1 (Algorıtmo de Euclides). Sejam a, b ∈ Z, b 6= 0, entao existe um unico par

(q, r) ∈ Z× Z tal que

a = bq + r, 0 ≤ r < |b|.

Demonstracao. (Existencia) Seja A = {a − bq ∈ Z | a − bq ≤ 0, q ∈ Z}, entao 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 numeros

inteiros nao negativos, entao existe r0 = minA. Assim, existe q0 ∈ Z tal que r0 = a− bq0.

Afirmacao: 0 ≤ r0 < |b|.

De fato, se r0 ≥ |b|, entao 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 > 0

a− 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 CAPITULO 6. INTRODUCAO A TEORIA DOS NUMEROS

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 = q2

r2 − r1 = b(q1 − q2) = 0

⇒

q1 = q2

r1 = 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.

Definicao 54. Dizemos que um numero inteiro a e um divisor de um numero inteiro b

se existe z ∈ Z tal que b = za. Neste caso, dizemos que b e divisıvel por a ou que b e

multiplo de a.

Notacao 4. a | b significara que a e um divisor de b ou b e multiplo de a.

Proposicao 2 (Propriedades). Seja A = Z∗+, entao a relacao

R = {(a, b) ∈ A× A | a | b}

e uma relacao 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-simetrica)

Demonstracao.

(i) Como a = 1 · a,∀a ∈ A, entao a | a,∀a ∈ A.

(ii) Se a | b e b | c, entao 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)

Observacao 8. As propriedades (i) e (ii) valem tambem para A = Z.

Definicao 55. Sejam a, b ∈ Z. Dizemos que um numero inteiro positivo d e o maximo

divisor comum de a e b se

(i) d | a e d | b;

(ii) Se d′ ∈ Z satisfaz d′ | a e d′ | b, entao d′ | d.

Notacao 5. Utilizaremos o sımbolo mdc(a, b) ou (a, b) para representarmos o maximo

divisor comum de a e b (ou entre a e b).

Exemplo 97. Vamos calcular agora o maximo 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 sao d(45) ∩ d(12) = {1, 3}.

Portanto, o maximo divisor comum entre 45 e 12 sera o maximo do conjunto d(45)∩d(12),

que e 3, ou seja, mdc(45, 12) = max d(45) ∩ d(12) = 3.

Proposicao 3. Se a, b ∈ Z d um divisor de a e de b. Entao d | (αa+ βb),∀α, β ∈ Z.

Demonstracao. Se d | a e d | b, entao 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).


Proposicao 4. Sejam a, b ∈ Z e A = {αa + βb | αa + βb > 0, α, β ∈ Z}, entao

mdc(a, b) = minA.

Demonstracao. Pelo Princıpio da Boa Ordem, existe m0 = minA.

Como d = mdc(a, b) e tal que d′ | a e d′ | b, entao, pela proposicao anterior, d |

(αa+ βb),∀α, β ∈ Z. Como m0 ∈ A, existem α0, β0 ∈ Z tais que m0 = α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 ∈ 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 numero inteiro positivo escrito na forma

αa+ βb, com α, β ∈ Z.

Assim, a = m0q + r = m0q ⇒ m0 | a.

Da mesma forma podemos concluir que m0 | b.

Como m0 | a e m0 | b, entao m0 | d. Portanto, como m0 > 0 e d′ | m0 e m0 | d′, entao

d = m0.

Logo minA = mdc(a, b).

Corolario 1. mdc(n, n+ 1) = 1,∀n ∈ Z.

Demonstracao. Como 1 = n+1−n = 1 · (n+1)+(−1) ·n e 1 e o menor numero inteiro

positivo, entao, pela Proposicao anterior, mdc(n, n+ 1) = 1.

Corolario 2. Para todo inteiro n,

mdc

(2n+ 1,

n(n+ 1)

2

)= 1.

Demonstracao. Basta observar que se α = 2n+ 1 e β = −8, entao

α(2n+ 1) + βn(n+ 1)

2= (2n+ 1)(2n+ 1) + (−8)n(n+ 1)

2= 1.

Definicao 56. Um numero inteiro p 6= ±1 e primo se os unicos divisores de p sao ±1 e

±p.

69

Proposicao 5. Seja p um numero primo e sejam a, b ∈ Z, tais que p | (ab), entao p | a ou

p | b.

Demonstracao. Se p | a, entao ja temos o que querıamos.

Se p - a, entao mdc(a, p) = 1, pois os unicos divisores de p sao ±p e ±1.

Como mdc(p, a) = 1, entao existem α, β ∈ Z tais que

αp+ βa = 1⇒ b · 1 = b(αp+ βa)⇒ b = (αb)p+ β(ab)

Como p | (ab) e mdc(p, a) = 1, entao existem z, α, β ∈ 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, entao c | b.

Definicao 57. Um numero inteirom 6∈ {±1, 0} e um numero composto sem nao e primo,

ou seja, se m 6= 0 e m possui mais de 4 divisores.

Proposicao 6. Seja m um numero inteiro positivo maior ou igual a 2, entao o menor

elemento do conjunto (o mınimo) S = {x ∈ Z | x > 1 e x | m} e um numero primo.

Demonstracao. Como m ∈ S e S e constituıdo por numeros inteiros positivos, entao, pelo

Princıpio da Boa Ordem, existe p = minS. Para provar que p e primo, suponhamos que

p seja composto. Se p for composto, entao existem inteiros z1, z2 > 1 tais que p = z1z2.

Assim, como p | a e z2 | p, entao z2 | a. Portanto, z2 ∈ S e z2 < p, o que contradiz a

minimalidade de p.

Logo p e primo.


Proposicao 7 (Primeiro Princıpio de Inducao). Seja P (n) uma afirmacao que depende de

n ∈ N = {0, 1, 2, · · · } que pode ser julgada como verdadeira ou falsa para cada n.

Se

(i) P (n0) e verdadeira para algum n0 ∈ N e

(ii) (∀n ∈ N) (P (n) verdadeira ⇒ P (n+ 1) verdadeira) ,

entao P (n) e verdadeira para todo n ∈ N tal que n ≥ n0.

Demonstracao. Seja S = {n ∈ 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 6∈ 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, nao existe P (m) falsa para nenhum m ∈ N tal que m ≥ n0. Logo P (n) e

verdadeira para todo n ∈ N tal que n ≥ n0.

Proposicao 8 (Segundo Princıpio de Inducao). Seja P (n) uma afirmacao que pode ser

julgada verdadeira ou falsa para cada n ∈ N satisfazendo as seguintes condicoes:

(i) P (n0) e verdadeira para algum n0 ∈ N e

(ii) Se P (k) e verdadeira para todo k ∈ N tal que n0 ≤ k < n, entao P (n) verdadeira.

Logo P (n) e verdadeira para todo n ∈ N tal que n ≥ n0.

Demonstracao. Exercıcio.

Exemplo 98. Mostraremos que

1 + 2 + 3 + · · ·+ n =n(n+ 1)

2,∀n ∈ N∗.

Seja P (n) a seguinte afirmacao:

P (n) : 1 + 2 + · · ·+ n =n(n+ 1)

2.

Como 1 =1(1 + 1)

2, entao P (1) e verdadeira.

Se P (n) e verdadeira, entao

1 + 2 + · · ·+ n(n+ 1)

2. (6.3)

71

Assim, somando n+ 1 em ambos os lados da equacao (6.3), obtemos

1 + 2 + · · ·+ n+ (n+ 1)

= n(n+1)2

+ (n+ 1)

= (n+ 1)[n2+ 1]

= (n+ 1)n+22

= (n+1)((n+1)+1)2

.

Portanto P (n+ 1) e verdadeira.

Logo, por inducao,

1 + 2 + · · ·+ n =n(n+ 1)

2, ∀n ∈ N∗.

Proposicao 9. Seja p primo tal que p | (a1a2 · · · an), entao p | a1 ou p | a2 ou · · · ou

p | an.

Demonstracao. Por inducao sobre n.

Se n = 1, entao p | a1 ⇒ p | a1.

Se n = 2, entao p | (a1a2) e, pelo resultado da aula passada, p | a1 ou p | a2.

Se p | (a1 · · · an), entao p | ((a1a2 · · · an−1)an), o que implica em p | (a1 · · · an−1) ou

p | an. Por inducao, p | a1 ou p | a2 ou · · · ou p | an−1 ou p | an.

Demonstracao. Seja p primo e

P (n) : (∀a1, · · · , an ∈ N) (p | (a1a2 · · · an)⇒ ( p | a1 ou p | a2 ou · · · ou p | an ))

Assim,

• P (1) e verdadeira, pois p | a1 ⇒ p | a1.

• P (2) e verdadeira, pois p | (a1a2)⇒ (p | a1 ou p | a2) .

• Supondo que P (m) seja verdadeira para todo m ∈ N tal que 1 ≤ m < n, temos que

p | (a1 · · · an)

⇒ p | ((a1 · · · an−1)an)P (2) e verdadeira

⇒ (p | (a1 · · · an−1) ou p | an)P (n− 1) e verdadeira

⇒ ( p | a1 ou p | a2 ou · · · ou p | an−1 ou p | an )

Logo, por inducao, se p | (a1 · · · an), entao p | a1 ou p | a2 ou · · · ou p | an.


Definicao 58. Sejam a1, · · · , an ∈ Z. Dizemos que d e o maximo divisor comum de

a1, · · · , an, d = mdc(a1, a2, · · · , an), se

(i) d | a1, · · · , d | an;

(ii) Se d′ ∈ Z satisfaz d′ | a1, · · · , d′ | an, entao d′ | d.

Exercıcio 5. Mostre que mdc(a1, · · · , an) = mdc(a1,mdc(a2, · · · , an)).

Exercıcio 6. Se c = ab com mdc(a, b) = 1, a | n e b | n, entao c | n.

Teorema 1 (Teorema Fundamental da Aritmetica). Seja n ∈ Z, n > 1, entao existem k ∈

N e p1, · · · , pk numeros primos positivos tais que n = p1 · · · pk. Alem disso, se q1, · · · , qmsao numeros primos positivos tais que n = q1q2 · · · qm, entao k = m e cada pi e algum qj,

ou seja, todo numero inteiro maior do que 1 pode ser escrito de forma unica como produto

de numeros primos positivos a menos da ordem em que estes numeros primos aparecem no

produto.

Demonstracao. Por inducao sobre n. Para n = 2 temos que 2 e primo e a afirmacao e

verdadeira.

Caso contrario, existem p1 primo tal que p1 | n, pois n > 1, pelo resultado anterior.

Portanto existe a1 ∈ Z tal que n = p1a1. Se a1 = 1, entao n = p1 e a afirmacao e

verdadeira.

Se 1 < a1 < n, entao, por inducao, existem p2, · · · , pk primos positivos tais que

a1 = p2 · · · pk.

Logo n = p1a = p1p2 · · · pk.

Sejam p1, · · · , pk, q1, · · · , qm primos positivos tais que n = p1 · · · pk = q1 · · · qm.

Assim, p1 e um primo com p1 | n, ou seja,

p1 | (q1 · · · qm)⇒ ( p1 | q1 ou p1 | q2 ou · · · ou p1 | qm. )

A menos de ordenacao, podemos supor que p1 | q1 e, como p1 e q1 sao numeros primos

positivos, segue que p1 = q1.

Logo n = p1p2 · · · pk = p1q2 · · · qm ⇒ p2 · · · pk = q2 · · · qm. Fazendo n′ = p2 · · · pk =

q2 · · · qm. Por inducao, como n > n′, entao k − 1 = m − 1 e todo pi e igual a algum

qj para i, j ∈ {2, · · · , k}, ou seja, k = m e todo pi e igual a algum qj para todo i, j ∈

{1, 2, · · · , k}.

73

Corolario 3. Seja n ∈ N, n > 1, entao existem p1, · · · , pk primos positivos e α1, · · · , αk ∈

N∗ com p1 < p2 < · · · < pk tais que n pode ser escrito de forma unica:

n = pα11 p

α22 · · · p

αkk .

Corolario 4. Se n ∈ Z∗, n 6= 1, entao existem p1, · · · , pk primos positivos e α1, · · · , αkinteiros positivos tais que n pode ser escrito de forma unica:

n = upα11 p

α22 · · · p

αkk para u = ±1.

Proposicao 10. Sejam n > 1 e d > 1 um divisor de n. Se p1 < · · · < pk sao numeros

primos positivos e α1, · · · , αk ∈ N∗ sao tais que n = pα11 · · · p

αkk entao d = pβ11 · · · p

βkk ,

para alguns β1, · · · , βk ∈ N com 0 ≤ β1 ≤ α1, · · · , 0 ≤ βk ≤ αk.

Demonstracao. Seja pβ a maior potencia de um primo p que divide d. Assim, como d

e divisor de n = pα11 · · · p

αkk , entao existira pi tal que pi = p e pβ e um divisor de

n. Logo n = pα11 · · · p

αkk = pα1

1 · · · pαii · · · p

αkk = pβm. Pelo Teorema Fundamental da

Aritmetica, existem γ1, · · · , γk tais que m = pγ11 · · · pγkk . Assim, como p = pi, temos que

n = pα11 · · · p

αii · · · p

αkk = pγ11 · · · p

γi−1

i−1 pγi+βi p

γi+1

i+1 · · · pγkk ⇒ α1 = γ1, · · · , αi−1 = γi−1, αi =

γi + β, · · · , βi+1 = γi+1, · · · , αk = γk ⇒ β ≤ αi.

Logo d = pβ11 · · · pβkk , onde 0 ≤ β1 ≤ α1, · · · , 0 ≤ βk ≤ αk.

Corolario 5. Seja n = pα11 · · · p

αkk , onde p1, · · · , pk sao primos positivos com p1 < p2 <

· · · < pk e α1, · · · , αk ∈ N∗, entao o numero de divisores de n e

d(n) = (α1 + 1)(α2 + 1) · · · (αk + 1).

Demonstracao. Pela proposicao anterior, se d e um divisor de n, entao d e escrito na forma

d = pβ11 · · · pβkk , onde 0 ≤ β1 ≤ α1, · · · , 0 ≤ βk ≤ αk.

Assim, temos

• α1 + 1 possibilidades de escolha para β1;

• α2 + 1 possibilidades de escolha para β2;

· · ·

• αk + 1 possibilidades de escolha para βk.


Portanto, temos (α1 + 1) · · · (αk + 1) possibilidades de escolha para os divisores de

n.

Proposicao 11. Sejam a = pα11 · · · p

αkk e b = pβ11 · · · p

βkk , onde p1, · · · , pk sao primos posi-

tivos e α1, · · · , αk, β1, · · · , βk ∈ N. Entao,

mdc(a, b) = pmin{α1,β1}1 · · · pmin{αk,βk}

k .

Demonstracao. Como min{αi, βi} ≤ αi e min{αi, βi} ≤ βi, para todo i ∈ {1, · · · , k},

entao

d = pmin{α1,β1}1 · · · pmin{αk,βk}

k

e um divisor de a e de b, ou seja, d | a e d | b.

Pela proposicao anterior, se d′ | a e d′ | b, entao existem γ1, · · · , γk ∈ N tais que

d′ = pγ11 · · · pγkk

com

• γ1 ≤ α1, · · · , γk ≤ αk, pois d′ | a e

• γ1 ≤ β1, · · · , γk ≤ βk, pois d′ | b.

Logo γ1 ≤ min{α1, β1}, · · · , γk ≤ min{αk, βk}, ou seja, d′ | d.

Portanto, d = pmin{α1,β1}1 · · · pmin{αk,βk}

k = mdc(a, b).

Proposicao 12. Sejam a, b ∈ Z com b 6= 0 tais que a = bq + r para (q, r) ∈ Z × Z com

0 ≤ r < |b|, entao mdc(a, b) = mdc(b, r).

Demonstracao. Sejam d1 = mdc(a, b) e d2 = mdc(b, r). Como d1 | a e d1 | b, entao

d1 | (a − bq). Logo d1 | b e d1 | r ⇒ d1 | d2, pela definicao de d2 = mdc(b, r). Como

d2 | b e d2 | r, entao d2 | (bq + r) e d2 | b, ou seja, d2 | a e d2 | b. Portanto, pela definicao

de d1 = mdc(a, b), temos que d2 | d1. Logo, como d1 | d2 e d2 | d1 e d1, d2 > 0, entao

d1 = d2, ou seja mdc(a, b) = mdc(b, r).

Proposicao 13 (Algoritmo para calculo do mdc). Sejam a, b ∈ Z e considere a sequencia

(rn)n∈N definida recursivamente, atraves do Algoritmo de Euclides, por

75

r0 = b

a = bq + r1, 0 ≤ r1 < b

b = r1q2 + r2, 0 ≤ r2 < r1

r1 = r2q3 + r3, 0 ≤ r3 < r2...

rn = rn+1qn+2 + rn+2, 0 ≤ rn+2 < rn+1

Entao, existe um menor inteiro positivo n0 tal que rn0 = 0 e rn0−1 = mdc(a, b).

Demonstracao. Pela Proposicao anterior,

(a, b) = (b, r1) = (r1, r2) = · · · = (rn, rn+1).

Afirmacao: Existe n ∈ N tal que rn+1 = 0.

De fato, se rn+1 6= 0,∀n ∈ N, entao temos uma quantidade infinita de elementos na

sequencia

b > r1 > r2 > · · · rn > rn+1 · · · > 0,

o que contradiz o Princıpio da Boa Ordem.

Logo, existe um menor n ∈ N tal que rn+1 = 0.

Assim,

(a, b) = (b, r1) = (r1, r2) = · · · = (rn, rn+1) = (rn, 0) = rn.

Portanto, rn = (a, b).

Exemplo 99. Para calcular o mdc(36, 45), observe que

45 = 36 · 1 + 9

36 = 9 · 4 + 0.

Logo mdc(36, 45) = 9.


354 = 12 · 29 + 6

12 = 6 · 2 + 0.

Logo mdc(354, 12) = 6.


Observacao 9. Uma maneira de formar a sequencia a partir do Algoritmo de Euclides e

formar uma tabela do tipo

q1 q2 q3 · · · qn+1

a b r1 r2 · · · rn

r1 r2 r3 · · · rn+1

Desta forma, se n e o menor inteiro nao negativo tal que rn+1 = 0, entao rn =

mdc(a, b).


29 2

354 12 6

6 0

Logo 6 = mdc(354, 12).

Exemplo 102. Encontrar α, β ∈ Z tais que d = mdc(354, 12) = α ·354+β ·12. Voltando

os passos no algoritmo para a determinacao do maximo divisor comum, obtemos 6 =

1 · 354 + (−29) · 12.

Logo α = 1 e β = −29 satisfazem 6 = mdc(354, 12) = α · 354 + β · 12.

Exemplo 103. Encontrar α, β ∈ Z tais que d = mdc(345, 354) = α · 345 + β · 354.

Como

354 = 345 · 1 + 9,

345 = 9 · 38 + 3,

9 = 3 · 3 + 0,

entao

3 = 345 · 1− 38(354− 1 · 345) = 39 · 345− 38 · 354.

Assim, α = 39 e β = −38 satisfazem 3 = mdc(345, 354) = α · 345 + β · 354.

Proposicao 14. Sejam a, b ∈ Z, entao a equacao

ax+ by = c (6.4)

tem solucao inteira (nos inteiros) se, e so se, mdc(a, b) | c. Alem disso, se (x0, y0) e uma

solucao de (6.4), entao, para qualquer t ∈ Z, (x1, y1) =(x0 +

tb(a,b)

, y0 − ta(a,b)

)tambem e

solucao de (6.4).

77

Demonstracao. Se d = (a, b), entao existem α, β ∈ Z tais que d = α · a+ β · b. Assim, se

d | c, existira k ∈ Z tal que c = kd. Logo c = kd = (kα)a + (kβ)b, ou seja, (x0, y0) =

(kα, kβ) e solucao de (6.4).

Reciprocamente, se existe (x0, y0) tal que ax0 + by0 = c, entao, como d = mdc(a, b)

satisfaz d | a e d | b, obtemos que d | (ax0 + by0), ou seja, d | c.

Para provar a segunda parte da proposicao, se (x0, y0) e solucao de ax+ by = c, entao

a

(x0 +

tb

(a, b)

)+ b

(y0 −

ta

(a, b)

)

= ax0 +tab

(a, b)+ by0 −

tab

(a, b)

= ax0 + by0 = c,

para todo t ∈ Z, ou seja, (x1, y1) =(x0 +

tb(a.b)

, y0 − ta(a,b)

),∀t ∈ Z tambem e solucao de

ax+ by = c.

Proposicao 15. Seja (x0, y0) uma solucao em Z × Z da equacao ax + by = c, onde

a, b, c ∈ Z. Assim, se (x1, y1) tambem for solucao em Z× Z, existira t ∈ Z tal que

x1 = x0 +tb

(a, b)e y1 = y0 −

ta

(a, b)

Demonstracao. Se (x0, y0) e (x1, y1) sao solucoes de ax+ by = c, entao ax0 + by0 = c

ax1 + by1 = c

Assim, subtraindo as equacoes acima, obtemos

a(x0 − x1) + b(y0 − y1) = 0

⇒ a(x0 − x1) = −b(y0 − y1) = z,

para algum z ∈ Z.

Assim, temos que a(a,b)| z e b | z e como

(a

(a,b), b)= 1, temos que ab

(a,b)| z. Portanto,

existe t ∈ Z tal que z = −t ab(a,b)

.

Logo z = −t ab(a,b)

= a(x0 − x1) = −b(y0 − y1), o que implica em x1 = x0 + t b(a,b)

e

y1 = y0 − t a(a,b)

.

Observacao 10. Dois numeros inteiros a, b tais que mdc(a, b) = 1 sao chamados de co-

primos ou primos entre si.


6.1 Congruencias

Definicao 59. Sejam a, b e n inteiros. Dizemos que a e congruente a b modulo n se

n | (a− b), ou seja, se a− b e um multiplo de n.

Notacao 6. Se a, b e n sao inteiros entao utilizaremos a ≡ b mod n significando que a e

congruente a b modulo n.

Exemplo 104. 1) (∀a ∈ Z) (a ≡ a mod 0)

2) (∀a, b ∈ Z) (a ≡ b mod 1)

3) (∀a, b ∈ Z) (∀n ∈ N) (a ≡ b mod n⇒ a ≡ b mod (−n))

Observacao 11. Nos casos 1) e 2) do exemplo anterior temos as chamadas congruencias

triviais. O caso 3) mostra que trabalhar com congruencias modulo n e o mesmo que tra-

balhar com congruencias modulo |n|. Portanto, a partir de agora trabalharemos somente

com congruencias modulo n onde n ∈ Z e n ≥ 2.

Exemplo 105.

1) 5 ≡ 7 mod 2, pois 5− 7 = −2 e 2 | (−2).

2) 13 ≡ 8 mod 5, pois 13− 8 = 5 e 5 | 5.

3) 256 ≡ 1 mod 3, pois 256− 1 = 255 e 3 | 255.

Proposicao 16. Sejam a, n ∈ Z com n ≥ 2, entao existe r ∈ Z com 0 ≤ r < n satisfazendo

a ≡ r mod n.

Demonstracao. Pelo Algorıtmo de Euclides, existem q, r ∈ Z tais que

a = qn+ r, 0 ≤ r < n.

Portanto a− r = qn⇒ n | (a− r).

Logo a ≡ r mod n com 0 ≤ r < n.

Observacao 12. • Sejam a, b ∈ Z com b 6= 0, entao, pelo Algoritmo de Euclides,

existem q, r ∈ Z tais que

a = qb+ r, 0 ≤ r < |b|.

Neste caso, dizemos que q e o quociente da divisao de a por b e que r e o resto (ou

o resıduo ) da divisao de a por b.

6.1. CONGRUENCIAS 79

• Pela Proposicao anterior, se a, n ∈ Z com n ≥ 2, entao r ∈ Z tal que 0 ≤ r < n e

a ≡ r mod n e o resto da divisao de a por n.

6.1.1 Propriedades das Congruencias

Seja n um numero inteiro maior ou igual a 2. Entao,

(i) (∀a ∈ Z) (a ≡ a mod n) .

(ii) (∀a, b ∈ Z) (a ≡ b mod n⇒ b ≡ a mod n) .

(iii) (∀a, b, c ∈ Z) ((a ≡ b mod n e b ≡ c mod n)⇒ a ≡ c mod n)

(iv) (∀a, b, c, d ∈∈ Z) ((a ≡ b mod n e c ≡ d mod n)⇒ a+ c ≡ b+ d mod n) .

(v) (∀a, b, c ∈ Z) ((a ≡ b mod n e c ≡ d mod n)⇒ ac ≡ bd mod n) .

(vi) (∀a, b ∈ Z) (∀m ∈ N) (a ≡ b mod n⇒ am ≡ bm mod n) .

(vii) (∀a, b, c ∈ Z) ((ca ≡ cb mod n e (c, n) = 1)⇒ a ≡ b mod n)

Proposicao 17. Se (c, n) = 1, entao a congruencia cx ≡ b mod n tem uma solucao inteira

x. Quaisquer duas solucoes x1 e x2 sao congruentes modulo n.

Demonstracao. Se (c, n) = 1, entao existem α, β ∈ Z tais que

αc+ βn = 1

⇒ b(αc+ βn) = b

⇒ (bα)c+ (bβ)n = b

⇒ (bα)c ≡ b mod n

Logo x = bα e uma solucao da congruencia cx ≡ b mod n.

Se x1 e x2 sao solucoes de cx ≡ b mod n, entao cx1 ≡ b mod n

cx2 ≡ b mod n

Logo, subtraindo as equacoes acima, obtemos cx1 ≡ cx2 mod n e, como (c, n) = 1,

segue que x1 ≡ x2 mod n.

Proposicao 18. Seja a ∈ Z e p primo, entao ap ≡ a mod p.


Demonstracao. Fixemos p primo.

Se a = 0, entao, obviamente, ap ≡ a mod p.

Se a > 0 satisfaz ap ≡ a mod p, entao (−a)p ≡ (−a) mod p. Portanto basta mostrar-

mos que np ≡ n mod p para todo n ∈ N∗. Seja P (n) a afirmacao: np ≡ n mod p. P (1) e

verdadeira, pois 1 = 1p ≡ 1 mod p.

Suponhamos que P (n) seja verdadeira. Assim, np ≡ n mod p.

Portanto (n+ 1)p ≡ np + 1 ≡ (n+ 1) mod p, ou seja, P (n+ 1) e verdadeira.

Logo, por inducao, P (n) e verdadeira para todo n ∈ N∗, ou seja, np ≡ n mod p para

todo n ∈ N.

Observacao 13. Seja n ≥ 2. Definindo a relacao R sobre Z por

R = {(a, b) ∈ Z× Z | a ≡ b mod n},

entao R e uma relacao de equivalencia.

A classe de equivalencia de a ∈ Z e o conjunto

a = {x ∈ Z | x ≡ a mod n}.

O conjunto das classes de equivalencia de R e o conjunto quociente

Z/R = {0, 1, · · · , n− 1},

que pode tambem ser simbolizada por Z/nZ ou por Zn.

E possıvel definirmos operacoes de adicao e multiplicacao em Zn da seguinte forma:

a · b := a · b

a+ b := a+ b

Segunda Lista de Exercıcios

1) Prove por inducao:

(a) 1 + 2 + 3 + · · ·+ n =n(n+ 1)

2,∀n ∈ N, n ≥ 1.

(b) 12 + 22 + 32 + · · ·+ n2 = n(n+1)(2n+1)6

,∀n ∈ N, n ≥ 1.

(c) 0 < a⇒ 0 < an,∀n ∈ N.

6.1. CONGRUENCIAS 81

(d) am · an = am+n,∀m,n ∈ N.

(e) (am)n = amn,∀m,n ∈ N.

(f) a < 0⇒ 0 < a2n e a2n+1 < 0, ∀n ∈ N.

(g) 22n−1 · 3n+2 + 1 e divisıvel por 11,∀n ∈ N, n ≥ 1.

(h) 32n+1 + 2n+1 e divisıvel por 7,∀n ∈ N.

(i) 22n + 15n− 1 e divisıvle por 9,∀n ∈ N, n ≥ 1.

(j) 34n+2 + 2 · 43n+1 e multiplo de 17, ∀n ∈ N.

2) Sejam a, b, c ∈ N∗ numeros sem divisores comuns tais que a2 + b2 = c2.

(a) Mostre que ou a ou b e par;

(b) Mostre que ou a ou b e multiplo de 3.

3) Mostre que o quadrado de um numero ımpar e da forma 8q + 1, q ∈ Z.

4) Seja a ∈ Z um numero nao divisıvel por 5. Mostre que a4 = 5q + 1, q ∈ Z.

5) Sejam a, b ∈ Z de modo que mdc(a, b) = 1. Se a | c e b | c, mostre que ab | c.

6) Use o resultado do exercıcio anterior para provar que 6 | n(2n+7)(7n+1),∀n ∈ Z.

7) Mostre que, para todo inteiro n, o maximo divisor comum entre 2n + 1 en(n+ 1)

2e 1.

8) Prove que mdc(a, b) = mdc(a+ bc, a+ b(c− 1)),∀a, b, c ∈ Z.

9) Mostre que a3 − a e multiplo de 3,∀a ∈ Z.

10) Mostre que a3 − b3 e multiplo de 3, se, e somente se, a− b e multiplo de 3.

11) Mostre que 6 | n(n+ 1)(2n+ 1), ∀n ∈ Z.

12) Mostre que 30 | n(n2 − 49)(n2 + 49),∀n ∈ Z.

13) Ache o resto da divisao de a = 531 · 312 · 2 por 7.

14) Ache o algorismo das unidades dos numeros 9(99) e 7(7

7).

15) Ache os dois ultimos algarismos de 7(71000).


16) Enuncie e justifique criterios de divisibilidade por 9, 5, 11 e 6.

17) Mostre que o conjunto dos numeros primos e infinito.

18) Sejam a, b, c ∈ Z numeros tais que a | bc e mdc(a, b) = 1. Prove que a | c.

19) Mostre que se p e primo, entao p |(p

i

)onde 0 < i < p.

20) Sejam a, b ∈ Z. Se existem x, y ∈ Z tais que ax+by = 1,mostre que mdc(a, b) = 1.

Capıtulo 7

Conjuntos Enumeraveis

Definicao 60. Dizemos que um conjunto A e enumeravel se A e um conjunto finito ou se

A e um conjunto infinito e existir uma funcao bijetora f : N→ A.

Proposicao 19. Z e enumeravel.

Demonstracao. Basta notar que f(x) =

n−12, n ımpar

−n2, n par

e uma funcao bijetora de N→

Z.

Princıpio da Boa Ordem: Todo subconjunto nao-vazio de N possui um elemento mınimo.

Proposicao 20. Se S ⊂ N, entao S e enumeravel.

Demonstracao. Se S e finito, entao S e enumeravel, por definicao.

Se S for infinito, entao, como S ⊂ N, existem

x1 = minS

x2 = min (S − {x1})

x3 = min (S − {x1, x2})...

xn = min (S − {x1, x2, · · · , xn})...

tais que S =⋃∞k=1{xk} e x1 < x2 < x3 < · · · < xn < · · · .

Portanto, a funcao definita por f(n) = xn e uma bijecao de N em S. Logo S e enu-

meravel.

Proposicao 21. A uniao disjunta de dois conjuntos infinitos enumeraveis e um conjunto

enumeravel.

83

84 CAPITULO 7. CONJUNTOS ENUMERAVEIS

Demonstracao. Sejam A e B conjuntos infinitos enumeraveis com A ∩ B = ∅. Assim,

existirao funcoes bijetoras h : N→ A e g : N→ B.

Portanto, f(n) =

h(n+12

), n ımpar

g(n2

), n par

e uma funcao bijetora de N to A ∪ B, pois

A ∩B = ∅.

Proposicao 22. Existe uma aplicacao f : N → A sobrejetora se, e somente se, A e

enumeravel.

Demonstracao. Podemos supor que A e infinito, ja que se A for finito, entao A e enu-

meravel, pela definicao.

Como f : N → A e sobrejetora, entao existe um subconjunto infinito B de N tal que

g = f |B, a restricao da funcao f ao conjunto B, e bijetora.

Pela Proposicao 20, como B e um subconjunto infinito de N, entao B e enumeravel e

existe uma bijecao h : N→ B.

Portanto, g ◦ h : N→ A e bijetora. Logo A e enumeravel.

Se A for enumeravel e infinito, entao existira uma aplicacao f : N → A bijetora. Em

particular, f : N→ A e sobrejetora.

Se A for enumeravel e finito, digamos S = {x1, x2, · · · , xm}, entao a aplicacao f :

N→ A definida por g(n) =

xn, ∀n ∈ {1, 2, · · · ,m}

x1, ∀n 6∈ {1, 2, · · · ,m}e uma funcao sobrejetora de N

em A.

Proposicao 23. Todo subconjunto nao-vazio de um conjunto enumeravel e enumeravel.

Demonstracao. Seja A um conjunto enumeravel e S um conjunto nao-vazio de A. Pode-

mos supor que S e A sao infinitos, ja que todo conjunto finito e enumeravel e todo sub-

conjunto de um conjunto finito e finito. Como A e enumeravel, entao existira uma bijecao

g : N → A. Seja B o subconjunto de N tal que h = g |B tem imagem Im(g) = S. Como

g e uma bijecao, entao h : B → S e uma bijecao e B e um subconjunto infinito de N.

Pela Proposicao 20, B e enumeravel e existira uma funcao bijetora f : N → B. Portanto

h ◦ f : N→ S e uma funcao bijetora. Logo S e enumeravel.

Proposicao 24. A uniao de conjuntos enumeraveis e um conjunto enumeravel.

85

Demonstracao. Como A e B sao enumeraveis, entao existirao g : N → A e h : N → B

sobrejetoras.

Assim,

f(n) =

g(n2

), se n par

h(n+12

), se n ımpar

e uma funcao sobrejetora de N em A ∪B.

Logo, pela Proposicao 22, A ∪B e enumeravel.

Proposicao 25. Uma aplicacao f : A→ N e injetora se, e somente se, A e enumeravel.

Demonstracao. Seja f : A→ N injetora.

Podemos supor que A e infinito, ja que todo conjunto finito e enumeravel. Seja B =

Im(f). Como B e um subconjunto infinito de N, entao B e enumeravel e existe uma

bijecao h : N → B. Alem disso, como f : A → N e injetora, entao f−1 : B → A e uma

bijecao de B em A. Portanto, f−1 ◦ h : N→ A e uma bijecao. Logo A e enumeravel.

Seja A for enumeravel e infinito, entao existira uma aplicacao f : N→ A bijetora. Em

particular, f−1 : A→ N e injetora.

Se A for enumeravel e finito, digamos S = {x1, x2, · · · , xm}, entao a aplicacao g :

A → N definida por g(xn) = n,∀n ∈ {1, 2, · · · ,m} e uma funcao injetora de A em

N.

Proposicao 26. SeA e um conjunto finito, entao existem funcoes f1 : A→ N e f2 : N→ A

tais que f1 e injetora e f2 e sobrejetora.

Demonstracao. Seja A um conjunto finito com n elementos e sejam x1, x2, · · · , xn tais

que A = {x1, x2, · · · , xn}. Definindo f1 : A → N por f1(xi) = i, ∀i ∈ {1, 2, · · · , n} e

definindo f2 : N → A por f(a) = x1+a,∀a ∈ N, onde a e o resto da divisao de a por n,

entao f1 e injetora e f2 e sobrejetora.

Proposicao 27. N× N e enumeravel.

Demonstracao. Como h : N × N → N definida por h(n,m) = 2n · 3m e injetora, entao

N× N e enumeravel, pela Proposicao 25.

Proposicao 28. O produto cartesiano de conjuntos enumeraveis e um conjunto enumeravel.


Demonstracao. Como N×N e um conjunto infinito enumeravel, entao existira uma funcao

bijetora h : N → N× N. Como A e B sao conjuntos enumeraveis, entao, pela Proposicao

22, existirao funcoes sobrejetoras g1 : N → A e g2 : N → B. Alem disso, definindo

f : N × N → A × B por f(n,m) = (g1(n), g2(m)), entao f e sobrejetora. Portanto

f ◦ h : N→ A×B e sobrejetora. Logo, pela Proposicao 22, A×B e enumeravel.

Proposicao 29. Q e enumeravel.

Demonstracao. Como N×N e infinito enumeravel, existe uma funcao bijetora de h : N→

N×N.Alem disso, como g : N×N→ Q definida por g(n,m) =

n2

m, se n for par

n−12

m, se n for ımpar

e sobrejetora, entao g ◦ h : N→ Q e sobrejetora.

Portanto Q e enumeravel, pela Proposicao 22.

Proposicao 30. O conjunto de todas as sequencias infinitas cujos termos sao elementos de

um conjunto com pelo menos dois elementos nao e enumeravel.

Demonstracao. Suponhamos que o conjunto S das sequencias infinitas cujos termos sao

elementos de um conjunto com pelo menos dois elementos seja enumeravel. Assim, exis-

tira uma funcao f : N→ S bijetora tal que f(n) = yn e

y1 = (x11, x12, x13, · · · , x1k, · · · )

y2 = (x21, x22, x23, · · · , x2k, · · · )

...

yk = (xk1, xk2, xk3, · · · , xkk, · · · )

...

sao sequencias distintas com S =⋃k∈N{yk}.

Considere agora a sequencia y = (x1, x2, · · · , xk, · · · ) ∈ S tal que xj 6= xjj para todo

j ∈ N. Assim, y 6= yk, para todo k ∈ N, o que implica em y 6∈⋃k∈N{yk} = S, o que e um

absurdo.

Proposicao 31. O intervalo fechado [0, 1] e nao-enumeravel.

87

Demonstracao. Consideremos 0 = 0, 00000 · · · e 1 = 0, 99999 · · · e os outros elementos

do intervalo [0, 1] escritos de forma que o dıgito 9 nao aparece repetido indefinidamente ao

final. Suponhamos que [0, 1] seja enumeravel. Assim, existira uma funcao f : N → [0, 1]

bijetora tal que f(n) = yn e

y1 = 0, a11a12a13 · · · a1k · · ·

y2 = 0, a21a22a23 · · · a2k · · ·

y3 = 0, a31a32a33 · · · a3k · · ·...

yk = 0, ak1ak2ak3 · · · akk · · ·...

onde aij ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} para i, j ∈ N e [0, 1] =⋃k∈N{yk}.

Considere agora y = 0, a1a2 · · · ak · · · ∈ [0, 1] tal que aj 6∈ {ajj, 9} para todo j ∈ N.

Assim, y 6= yk, para todo k ∈ N, o que implica em y 6∈⋃k∈N{yk} = [0, 1], o que e um

absurdo.

Corolario 6. R e nao-enumeravel.

Demonstracao. Se R fosse enumeravel, entao [0, 1] tambem seria enumeravel, ja que todo

subconjunto nao-vazio de um conjunto enumeravel e enumeravel, o que e um absurdo, pela

Proposicao 31.

Proposicao 32. A uniao enumeravel de conjuntos enumeraveis e um conjunto enumeravel.

Demonstracao. Sejam A1, A2, · · · , An, · · · conjuntos enumeraveis e S =⋃∞n=1An.

Para cada n ∈ N, comoAn e enumeravel, existira uma funcao sobrejetora fn : N→ An.

Seja Ank = fn(k),∀k ∈ N. Assim, como fn e sobrejetora, teremos que An =⋃∞k=1{An k}.

A seguinte construcao nos proporciona a enumerabilidade de S :

A1 : A11 A12 A13 · · · A1k · · ·

A2 : A21 A22 A23 · · · A2k · · ·

A3 : A31 A32 A33 · · · A3k · · ·...

Ak : Ak1 Ak2 Ak3 · · · Akk · · ·...


Proposicao 33. O conjunto S dos subconjuntos de N nao e enumeravel.

Demonstracao. Seja B o conjunto das sequencias sobre o conjunto {0, 1} e considere a

funcao f : B → S definida por

f((xn)) =∞⋃n=1xn=1

{n}

Como f e uma bijecao de B em S e B nao e enumeravel, entao S nao e enumeravel.

17) Seja A = {1, 2, 3}. Considerem-se as seguintes relacoes em A :

R1 = {(1, 2); (1, 1); (2, 2); (2, 1); (3, 3)}

R2 = {(1, 1); (2; 2); (3, 3); (1, 2); (2, 3)}

R3 = {(1, 1); (2, 2); (1, 2); (2, 3); (3, 1)}

R4 = A× A

R5 = ∅

Quais sao reflexivas? simetricas? transitivas? anti-simetricas?

18) Construir sobre o conjunto E = {a, b, c, d} relacoes R1, R2, R3 e R4 tais que R1

so tem a propriedade reflexiva, R2 so a simetrica, R3 so a transitiva e R4 so a anti-

simetrica.

Dica: Faca o diagrama de flechas.

19) Encontre os fechos reflexivo, simetrico e transitivo da relacao

R = {(a, a), (b, b), (c, c), (a, c), (a, d), (b, d), (c, a), (d, a)}

no conjunto S = {a, b, c, d}.

20) Mostrar que a relacao R sobre N× N tal que ((a, b), (c, d)) ∈ R⇔ a+ b = c+ d e

uma relacao de equivalencia.

21) Seja E um conjunto nao vazio. Dados X, Y ∈ P (E) mostre que as relacoes R e S

sao de equivalencia em P (E).

89

(a) (X, Y ) ∈ R⇔ X ∩ A = Y ∩ A.

(b) (X, Y ) ∈ S ⇔ X ∪ A = Y ∪ A

onde A e um subconjunto fixo de E.

22) Seja A = {x ∈ Z | 0 ≤ x ≤ 10} e R a relacao sobre A definida por (x, y) ∈ R ⇔

∃k ∈ Z | x− y = 4k. Determine o conjunto-quociente A/R.

23) Seja A = {x ∈ Z | |x| ≤ 5} e R a relacao sobre A definida por (x, y) ∈ R ⇔

x2 + 2x = y2 + 2y. Determine o conjunto-quociente A/R.

24) Enumerar todas as relacoes de equivalencia sobre A = {a, b, c}.

25) O diagrama simplificado de uma relacao de ordem R e o diagrama da menor relacao

S cujo fecho com relacao a propriedade de ser relacao de ordem parcial e R. Faca

um diagrama simplificado da relacao de ordem por inclusao em:

E = {{a}, {b}, {a, b, c}, {a, b, d}, {a, b, c, d}, {a, b, c, d, e}}.

26) Escreva o diagrama simplificado da relacao x divide y em {1, 2, 3, 6, 12, 18}.

27) Quais sao as classes de equivalencia correspondentes a relacao de congruencia modulo

5 no conjunto

A = {x ∈ Z | 1 ≤ x ≤ 20}.

28) Mostrar que f : R −{−dc

}→ R −

{ac

}dada pela sentenca y =

ax+ b

cx+ d, onde

a, b, c, d sao constantes reais, ad− bc 6= 0, e uma bijecao. Descrever a funcao f−1.

29) Explique porque as seguintes relacoes de A = {1, 2, 3} em B = {2, 3, 4, 5} nao sao

funcoes de A em B.

R1 = {(1, 2), (1, 4), (2, 3), (3, 5)}

R2 = {(1, 3), (2, 5)}

R3 = {(1, 3), (2, 4), (3, 5), (4, 3)}

30) Encontre o domınio e a imagem das seguintes funcoes:

(a) f(x) =

√x2 + 5x− 9

x3 − 4x

(b) f(x) =√x2 + 2x.


(c) f(x) =

|x− 2|, x < 2

−√x, x > 5

(d) f(x) = 3x+54x+7

.

31) Encontre uma funcao real g satisfazendo (f ◦ g)(x) = 5x− 4 e f(x) = 2x.

32) Encontre uma funcao real g satisfazendo (f ◦ g)(x) = 1

xe f(x) = 5x− 2.

33) Encontre uma funcao real f satisfazendo (f ◦ g)(x) = 2x+ 7 e g(x) =1

x.

34) Encontre uma funcao real f satisfazendo (f ◦ g)(x) = 4x− 5 e g(x) = 3x+ 7.

35) Encontre uma formula para f−1(y) para as seguintes funcoes:

(a) f(x) = 7x− 6.

(b) f(x) = 3x3 − 5.

(c) f(x) = x+1x−1 .

(d) f(x) =

5/2− x, x < 2

1/x, x ≥ 2

36) Mostre que a funcao f(x) = 2x+ 3 e bijetora.

37) Mostre que a funcao f(x) = 2x + 1 e injetora.

38) Mostre que a funcao f(x) = log2 (x2) e sobrejetora.

39) De exemplo de uma funcao que e injetora e nao e sobrejetora e de uma funcao que e

sobrejetora e nao e injetora.

51) Prove que N× N e enumeravel.

52) Prove que se A e B sao conjuntos enumeraveis, entao

(a) A ∩B e enumeravel;

(b) A ∪B e enumeravel;

(c) A×B e enumeravel.

53) Prove que se A1, · · · , An sao enumeraveis, entao

A1 × A2 × · · · × An e enumeravel.

91

54) Prove que Z e enumeravel.


Capıtulo 8

Grafos

8.1 Definicoes iniciais

Definicao 61 (Informal). Um grafo e um conjunto nao vazio de vertices (nos) e um con-

junto de arestas (arcos) tais que cada aresta conecta dois vertices.

Definicao 62 (Formal). Um grafo (nao orientado, nao direcionado) e uma tripla ordenada

(V,A, g), onde

• V e um conjunto nao vazio de vertices (nos);

• A e um conjunto de arestas (arcos);

• g e uma funcao que associa a cada arco a um par nao ordenado x − y de vertices.

Neste caso, os vertices x e y sao as extremidades da aresta a.

Exemplo 106. Desenhe um grafo (V,A, g), onde V = {1, 2, 3, 4}, A = {a1, a2, a3, a4, a5}

e g(a1) = 1− 2, g(a2) = 2− 3, g(a3) = 1− 4, g(a4) = 2− 4 e g(a5) = 1− 3.

1

2

4

3

a1 a4

a3

a2

a5

•

••

••

•

Definicao 63. Um grafo direcionado (orientado ou dıgrafo) e uma tripla ordenada (V,A, g)

onde

93

94 CAPITULO 8. GRAFOS

• V e um conjunto nao vazio de vertices;

• A e um conjunto de arestas;

• g e uma funcao que associa a cada aresta a um par ordenado (x, y) de vertices, onde

x e a extremidade inicial (ou inferior) e y e a extremidade final (ou superior) de a.

Exemplo 107.

Definicao 64. Um grafo rotulado e um grafo que contem informacoes identificadoras ou

rotulos em seus vertices e/ou arestas.

Definicao 65. Um grafo ponderado (grafo com pesos) e um grafo em que cada aresta

possui um valor numerico ou peso associado.

Exemplo 108. Uma relacao sobre um conjunto nao vazio pode ser representada por um

grafo direcionado.

Observacao 14. Aplicacoes de grafos:

• Representacao de circuitos;

• Representacao da estrutura organizacional de uma empresa;

• Representacao de automatos;

• Representacao de mapas;

• Representacao de relacoes.

8.2 Terminologia

Definicao 66. Dois vertices sao adjacentes se sao extremidades de uma mesma aresta.

Definicao 67. Duas arestas sao adjacentes se possuem uma extremidade em comum.

Definicao 68. Um laco e uma aresta cujas extremidades sao um mesmo vertice.

Definicao 69. Arestas paralelas sao arestas com as mesmas extremidades.

Definicao 70. Um grafo simples e um grafo sem lacos e sem arestas paralelas.

8.2. TERMINOLOGIA 95

Observacao 15. Existem 2(n2) grafos simples com n vertices (a menos de isomorfismo),

onde(n2

)e o numero de subconjuntos com dois elementos distintos tomados num conjunto

com n elementos.

Definicao 71. Um vertice isolado e um vertice que nao e extremidade de nenhuma aresta.

Definicao 72. O grau ou valencia de um vertice e o numero de arestas que tem este

vertice como extremidade.

Definicao 73. Um grafo completo e um grafo em que todos os seus pares de vertices sao

adjacentes.

Observacao 16. Um grafo completo simples Kn possui n(n−1)2

arestas.

Definicao 74. Um grafo regular de grau n e um grafo em que todos os seus vertices

possuem grau n.

Definicao 75. Um subgrafo de um grafo e um grafo cujo conjunto de arestas e vertices

sao subconjuntos de arestas e vertices do grafo original e cujas extremidades das arestas

sao as mesmas do grafo original (mantendo orientacao).

Definicao 76. Um grafo e um grafo bipartido (ou bipartite) se o conjunto de seus vertices

pode ser dividido (particionado) em dois subconjuntos disjuntos V1 e V2 de tal modo que

dois vertices de um mesmo subconjunto nao sao adjacentes.

Definicao 77. Um grafo e um grafo bipartido completo se o conjunto de seus vertices

pode ser dividido (particionado) em dois subconjuntos disjuntos V1 e V2 de tal modo que

dois vertices sao adjacentes se, e somente se, um deles pertence a V1 e o outro pertence a

V2. Se |V1| = m e |V2| = n, um tal grafo e denotado por Km,n.

••1 2

Figura 8.1: Grafo Bipartido Completo K1,1

Definicao 78. Dizemos que um grafo (V1, A1, g1) e um subgrafo de um grafo (V,A, g) se

V1 ⊆ V,A1 ⊆ A e g1 = g |A1 , ou seja, um subgrafo de um grafo e um grafo cujo conjunto

de vertices e arestas sao subconjuntos do conjunto dos vertices e arestas de um grafo

original, nos quais os vertices e arestas do subgrafo tem que ser as mesmas extremidades

do grafo original.


•

•

•

•

•

•

•

•

•

•

•

•

1 2

3 4 5

Figura 8.2: Grafo Bipartido Completo K2,3

Definicao 79. Um (caminho ) ou (cadeia) de um vertice v0 para um vertice vn e uma

sequencia

v0, a0, v1, a1, v2, a2, · · · , vk−1, ak−1, vk,

onde ai e uma aresta com extremidades nos vertices vi e vi+1. O comprimento de um cami-

nho (ou cadeia) e o numero de arestas contida na sequencia. Um caminho e dito reduzido

se nao existem arestas repetidas no caminho. Dizemos que o vertice v alcanca (ou acessa)

o vertice w se existe um caminho do vertice v para o vertice w. Neste caso dizemos tambem

que o vertice w e alcancavel (ou acessavel) a partir do vertice v.

Definicao 80. Um grafo e conexo se este grafo nao puder ser dividido em dois subgrafos

disjuntos cuja uniao contem todos os vertices e arestas do grafo original. No caso de grafo

nao orientado, um grafo e conexo se sempre existe um caminho (cadeia) de um vertice

qualquer para outro vertice qualquer.

Definicao 81. Um ciclo (ou circuito) de um grafo e um caminho (cadeia) de um vertice v

para ele mesmo em que nenhuma aresta aparece mais de uma vez no caminho.

Definicao 82. Um grafo que nao possui ciclos e chamado de grafo acıclico. No caso de

grafo nao orientado, um grafo acıclico e chamado de floresta.

Definicao 83. Um grafo nao orientado simples T e uma arvore (livre) se para cada par

de vertices distintos de T existir um unico caminho reduzido conectando estes vertices.

Definicao 84. Dizemos que um grafo T e uma arvore se este grafico possui um vertice v

(raiz) de tal forma que para qualquer vertice w de T existe apenas um caminho reduzido

de v para w.

Observacao 17. Para um grafo nao orientadoG, as seguintes afirmacoes sao equivalentes:

(1) G e uma arvore;

8.2. TERMINOLOGIA 97

(2) G e conexo e sem ciclos;

(3) G e sem ciclos com n vertices e n− 1 arestas;

(4) G e conexo com n vertices e n− 1 arestas;

(5) G e acıclico e acrescentando-se uma aresta entre dois vertices quaisquer cria-se

exatamente um ciclo;

(6) G e conexo e eliminando qualquer uma das arestas faz com que o grafo resultante

nao seja conexo.

Proposicao 34. Se G e uma arvore, entao G e conexo e acıclico.

Demonstracao. Se G e uma arvore, entao para cada par de vertices distintos de G, existe

um unico caminho reduzido conectando estes vertices. Portanto G e conexo.

Suponhamos que exista um ciclo em G. Assim existe um caminho de v para v para

algum vertice v de G. Digamos,

v = v0, a0, v1, a1, v2, · · · , an−1, vn = v.

Agora

v1, a0, v0 = v

e

v1, a1, v2, · · · , an−1, vn = v

sao dois caminhos reduzidos de v1 para v, o que e impossıvel. Logo G nao possui ciclos.

Proposicao 35. Se G e conexo e acıclico com n vertices, entao G possui n− 1 arestas.

Demonstracao. Por inducao sobre n, o numero de vertices.

Se n = 1, entao G nao possui arestas, ja que G nao pode conter lacos.

Se G possui m + 1 vertices e C e um caminho em G de maior comprimento, entao

existe um vertice v de grau 1 que e uma extremidade de C. Apagando este vertice v e a

aresta a, com extremidade em v, obtemos um subgrafo G de G que e conexo e acıclico

com m vertices. Por inducao, G possui m− 1 arestas. Logo G possui m arestas. Logo, por

inducao, se G e conexo e acıclico com n vertices, entao G possui n− 1 arestas.


8.3 Isomorfismo entre grafos

Definicao 85. Dois grafos (V1, A1, g1) e (V2, A2, g2) sao isomorfos se existem bijecoes

f1 : V1 → V2 e f2 : A1 → A2 de tal forma que para quaisquer vertices v1 e v2 de V1, se

v1 e v2 sao extremidades da aresta a1, entao f1(v1) e f1(v2) sao extremidades da aresta

f2(a1).

Exemplo 109. Os seguintes grafos G1 e G2 nao sao isomorfos.

Observacao 18. Se dois grafos satisfazem qualquer uma das seguintes condicoes, entao

eles nao sao isomorfos:

(1) Um grafo tem mais vertices do que o outro;

(2) Um grafo tem mais arestas do que o outro;

(3) Um grafo tem arestas paralelas e o outro nao;

(4) Um grafo tem mais lacos do que o outro;

(5) Um grafo e conexo e o outro nao;

(6) Um grafo tem um vertice de grau k e o outro nao;

(7) Um grafo tem um ciclo (circuito) e o outro nao.

Exemplo 110. Os grafos T1 e T2 nao sao isomorfos.

•

•

•

•• •• ••

•

•

•

1

2

3

4 5

6

7

Figura 8.3: Grafo T1

•

•

•

•• ••

•

•

•

• •a

b

c

e

f

d g


8.4. MATRIZES DE ADJACENCIA 99

Definicao 86. Dois grafos simples (V1, A1, g1) e (V2, A2, g2) sao isomorfos se existe uma

bijecao f : V1 → V2 tal que quaisquer vertices vi e vj de V1, vi e vj sao adjacentes se

f(vi) e f(vj) sao adjacentes.

Exemplo 111. Os seguintes grafos G1 e G2 nao sao isomorfos:

•

•

•

•• •• ••

•

•

•

1

2

3

4 5

6

7


•

•

•

•• ••

•

•

•

• •a

b

c

e

f

d g


8.4 Matrizes de Adjacencia

8.4.1 Matriz de adjacencia para grafo nao-direcionado (nao-orientado)

Seja (V,A, g) um grafo nao-direcionado com n vertices e (v1, v2, · · · , vn) uma sequencia

com os n vertices distintos de (V,A, g). A matriz de adjacencia com respeito a sequencia

(ordenada) (v1, v2, · · · , vn) e a matriz M = (aij)n×n, onde aij e o numero de arestas com

extremidades nos vertices vi e vj.

Seja M = (aij)n×n a matriz de adjacencia de um grafo. Para obtermos a matriz coluna


C =

c1

c2...

cn

, onde ci = grau(vi), basta utilizarmos a formula

C =M

1

1...

1

.

Matriz de adjacencia para grafo direcionado (dıgrafo)

Seja (V,A, g) um grafo direcionado com n vertices e (v1, v2, · · · , vn) uma sequencia com

os n vertices distintos de (V,A, g). A matriz de adjacencia com respeito a sequencia (or-

denada) (v1, v2, · · · , vn) e a matriz M = (aij)n×n, onde aij e o numero de arestas com

origem no vertice vi e extremidade no vertice vj (com extremidade inferior no vertice vi e

extremidade superior no vertice vj).

Seja M = (aij)n×n a matriz de adjacencia de um grafo direcionado. Para obtermos a

matriz coluna C =

c1

c2...

cn

, onde ci = grau(vi), basta utilizarmos a formula

C =M ′

1

1...

1

,

onde M ′ = (bij)n×n com bij =

aij + aji, se i 6= j

aii, se i = j

Isomorfismo entre grafos utilizando matrizes de adjacencia

SeG1 eG2 sao grafos isomorfos com matrizes de adjacenciaM1 eM2 existe uma sequencia

de troca simultanea de linhas e colunas que transforma M1 em M2.

Exemplo 112. Sejam G1 e G2 os grafos abaixo:


•

•

•

•

••

•

1

2

3

4

5

a1

a2

a3a4

a6

a7

Figura 8.7: Grafo G1

•

•

•

•

••

•

2

3

4

5

1

e2

e3

e4e5

e7

e6

Figura 8.8: Grafo G2

As matrizes de adjacencia de G1 e G2 sao

M1 =

0 1 0 1 0

1 0 1 1 0

0 1 0 1 0

1 1 1 0 1

0 0 0 1 0

e M2 =

0 0 0 0 1

0 0 1 0 1

0 1 0 1 1

0 0 1 0 1

1 1 1 1 0

Como podemos notar, se V1 e V2 sao os conjuntos de vertices dos grafos G1 e G2,

respectivamente, entao a funcao f : V1 → V2 definida por f(1) = 2, f(2) = 3, f(3) =

4; f(4) = 5 e f(5) = 1 e uma bijecao que mantem a relacao de adjacencia entre vertices,

ou seja, para quaisquer vertices v e u adjacentes deG1, temos que f(u) e f(v) sao vertices

adjacentes de G2.

As seguintes sequencias de trocas de linhas e colunas nas matrizes de adjacencia nos

proporciona uma sequencia de grafos isomorfos em que o primeiro grafo da sequencia e

G1 e o ultimo grafo desta sequencia e G2 :

A matriz de adjacencia

0 1 0 1 0

1 0 1 1 0

0 1 0 1 0

1 1 1 0 1

0 0 0 1 0

do grafo

•

•

•

•

••

•

1

2

3

4

5

e trans-


formada na matriz de adjacencia

0 1 1 1 0

1 0 0 1 0

1 0 0 1 0

1 1 1 0 1

0 0 0 1 0

do grafo

•

•

•

•

••

•

2

1

3

4

5

isomorfo por meio das seguintes operacoes:

0 1 0 1 0

1 0 1 1 0

0 1 0 1 0

1 1 1 0 1

0 0 0 1 0

L1↔L2↔

1 0 1 1 0

0 1 0 1 0

0 1 0 1 0

1 1 1 0 1

0 0 0 1 0

C1↔C2↔

0 1 1 1 0

1 0 0 1 0

1 0 0 1 0

1 1 1 0 1

0 0 0 1 0


0 1 1 1 0

1 0 0 1 0

1 0 0 1 0

1 1 1 0 1

0 0 0 1 0

do grafo

•

•

•

•

••

•

2

1

3

4

5

e trans-


0 0 1 1 0

0 0 1 1 0

1 1 0 1 0

1 1 1 0 1

0 0 0 1 0

do grafo

•

•

•

•

••

•

2

3

1

4

5


0 1 1 1 0

1 0 0 1 0

1 0 0 1 0

1 1 1 0 1

0 0 0 1 0

L1↔L3↔

1 0 0 1 0

1 0 0 1 0

0 1 1 1 0

1 1 1 0 1

0 0 0 1 0

C1↔C3↔

0 0 1 1 0

0 0 1 1 0

1 1 0 1 0

1 1 1 0 1

0 0 0 1 0


0 0 1 1 0

0 0 1 1 0

1 1 0 1 0

1 1 1 0 1

0 0 0 1 0

do grafo

•

•

•

•

••

•

2

3

1

4

5

e trans-



0 1 1 1 1

1 0 1 0 0

1 1 0 1 0

1 0 1 0 0

1 0 0 0 0

do grafo

•

•

•

•

••

•

2

3

4

1

5


0 0 1 1 0

0 0 1 1 0

1 1 0 1 0

1 1 1 0 1

0 0 0 1 0

L1↔L4↔

1 1 1 0 1

0 0 1 1 0

1 1 0 1 0

0 0 1 1 0

0 0 0 1 0

C1↔C4↔

0 1 1 1 1

1 0 1 0 0

1 1 0 1 0

1 0 1 0 0

1 0 0 0 0


0 1 1 1 1

1 0 1 0 0

1 1 0 1 0

1 0 1 0 0

1 0 0 0 0

do grafo

•

•

•

•

••

•

2

3

4

1

5

e trans-


0 0 0 0 1

0 0 1 0 1

0 1 0 1 1

0 0 1 0 1

1 1 1 1 0

do grafo

•

•

•

•

••

•

2

3

4

5

1


0 1 1 1 1

1 0 1 0 0

1 1 0 1 0

1 0 1 0 0

1 0 0 0 0

L1↔L5↔

1 0 0 0 0

1 0 1 0 0

1 1 0 1 0

1 0 1 0 0

0 1 1 1 1

C1↔C5↔

0 0 0 0 1

0 0 1 0 1

0 1 0 1 1

0 0 1 0 1

1 1 1 1 0

Exemplo 113. Sejam T1 e T2 os grafos abaixo:


•

•

•

•

1

2

3

4


•

•

•

•

4

3

1

2


As matrizes de adjacencia de T1 e T2 sao

M1 =

0 0 1 0

0 0 1 0

1 1 0 1

0 0 1 0

e M2 =

0 1 1 1

1 0 0 0

1 0 0 0

1 0 0 0

Se V1 e V2 sao os conjuntos de vertices dos grafos T1 e T2, respectivamente, entao

qualquer aplicacao bijetora f : V1 → V2 satisfazendo f(3) = 1 mantem a relacao de

adjacencia entre vertices, ou seja, para quaisquer vertices v e u adjacentes de T1, temos

que f(u) e f(v) sao vertices adjacentes de T2.

Neste caso, a matriz de adjacencia

M1 =

0 0 1 0

0 0 1 0

1 1 0 1

0 0 1 0

do grafo T1 e transformada na matriz

M2 =

0 1 1 1

1 0 0 0

1 0 0 0

1 0 0 0

8.5. MATRIZ DE DISTANCIAS 105

do grafo T2 por meio da seguinte operacao:

M1 =

0 0 1 0

0 0 1 0

1 1 0 1

0 0 1 0

L3↔L1↔

1 1 0 1

0 0 1 0

0 0 1 0

0 0 1 0

C3↔C1↔

0 1 1 1

1 0 0 0

1 0 0 0

1 0 0 0

=M2

8.4.2 Matriz de adjacencia para grafo ponderado (valorado)

Seja G um grafo ponderado sem arestas paralelas e (v1, v2, · · · , vn) uma sequencia dos n

vertices distintos de G. Dizemos que M e a matriz de adjacencia do grafo ponderado G

com respeito a sequencia (v1, v2, · · · , vn) se M = (aij)n×n, onde

aij =

k, se existir uma aresta com peso k com extremidade (inferior)

no vertice vi e extremidade superior no vertice vj

∞, caso contrario

8.5 Matriz de distancias

8.5.1 Matriz de distancias para Grafos nao ponderados

Seja G um grafo ponderado e (v1, v2, · · · , vn) uma sequencia dos n vertices distintos de G.

Dizemos que D e a matriz de distancias de G com respeito a sequencia (v1, v2, · · · , vn) se

D = (aij)n×n, onde

aij =

k, se k e o comprimento do menor caminho conectando vi a vj

∞, se nao existirem caminhos conectando vi a vj

8.5.2 Matriz de distancias para Grafos ponderados

Seja G um grafo ponderado e (v1, v2, · · · , vn) uma sequencia dos n vertices distintos de G.

Dizemos que D e a matriz de distancias de G com respeito a sequencia (v1, v2, · · · , vn) se

D = (aij)n×n, onde

aij =

k, se k e o mınimo da soma dos pesos das arestas escolhido

dentre todos os caminhos de vi para vj.

0, se i = j

∞, caso contrario


8.6 Algoritmos em Grafos

Definicao 87. Em um grafo G, dizemos que o vertice vj e alcancavel a partir do vertice vi

se existir um caminho de vi ate vj.

Definicao 88. Dizemos que R e a matriz de alcancabilidade de um grafo G se R[i, j] = 1 se vi alcanca vj

0 caso contrario

Teorema 2 (Matrizes Booleanas de Adjacencia e Alcancabilidade). Se A e uma matriz

(booleana) de adjacencias de um grafo G com n vertices e sem arestas paralelas, entao

A(m)[i, j] = 1 se, e somente se, houver um caminho de comprimento m do vertice vi para

o vertice vj, onde A(d)[i, j] e definido recursivamente por

A(1)[i, j] = aij

e

A(d)[i, j] =n∨k=1

A(d−1)[i, k] ∧ akj para d > 1

Observacao 19 (Alcancabilidade). Se R e a matriz de alcancabilidade de um grafo G,

entao R = A(1) ∨ A(2) ∨ A(3) ∨ · · · ∨ A(n).

Algoritmo 1 (Algoritmo de Warshall para Alcancabilidade). procedure Warshall (var M :

matriz booleana n x n);

{ inicialmente, M e a matriz de adjacencias de um grafo G sem arestas paralelas }

begin

for k: = 1 to n do

for i: = 1 to n do

for j: = 1 to n do

M [i, j] :=M [i, j] ∨ (M [i, k] ∧m[k, j]);

end; {ao termino, M = matriz de alcancabilidade de G }

Teorema 3. O numero de vertices de grau ımpar em um grafo simples e par.

Definicao 89 (Leonhard Euler (1707-1783)). Um caminho (circuito) Euleriano de um

grafo G (sem lacos) e um caminho (circuito) que passa por cada aresta de G exatamente

uma vez.

8.6. ALGORITMOS EM GRAFOS 107

Teorema 4. Existe um caminho Euleriano em um grafo conexo (sem lacos) se, e somente

se, nao houver nenhum ou existirem exatamente dois vertices ımpares. No caso de nao

haver vertices ımpares, o caminho pode comecar em qualquer vertice e terminar neste

mesmo vertice; para o caso de haver dois vertices ımpares, o caminho deve comecar em

um vertice ımpar e terminar no outro.

Definicao 90 (Willian Rowan Hamilton (1805-1865)). Um caminho Hamiltoniano de um

grafo G e um caminho

v0, a0, v1, a1, · · · , an−1, vn

tal que v0, v1, · · · , vn e uma lista sem repeticao de todos os vertices de G. Um circuito

Hamiltoniano e um circuito

v = v0, a0, v1, a1, · · · , an−1, vn, an, vn+1 = v

em que

v0, a0, v1, a1, · · · , an−1, vn

e um caminho Hamiltoniano.

Definicao 91. Uma arvore geradora de um grafo conexo e nao orientado G e um subgrafo

de G conexo e acıclico que contem todos os vertices de G.

Definicao 92. Uma arvore geradora mınima de um grafo ponderado, conexo e nao orien-

tado G e um subgrafo de G conexo e acıclico que contem todos os vertices de G de forma

que a soma dos valores (pesos) associados as arestas seja mınima.

Algoritmo 2 (Algoritmo de Kruskal). Para a determinacao de uma arvore geradora mınima

T do grafo G.

1. Iniciar com os n vertices e nenhuma aresta em T.

2. Introduzir a aresta de menor peso p1 em T.

3. Introduzir arestas uma por uma por ordem crescente de pesos que nao completam

circuitos em T.

4. Parar quando o numero de arestas introduzidas em T for n− 1.

Algoritmo 3 (Algoritmo de Prim). Para a determinacao da arvore geradora mınima T do

grafo G.


1. Comece com um conjunto vertices V (T ) que inicialmente contem um vertice ar-

bitrario do grafo e com um conjunto vazio A(T ) de arestas.

2. A cada passo inclua em A(T ) uma aresta de A(G) com peso mınimo com extremi-

dade nos vertices u e v de tal forma que u ∈ V (T ) e v ∈ V (G) − V (T ), incluindo

depois v a V (T ).

3. Repetir o passo anterior ate que V (T ) possua n vertices.

8.7 Problema do Caminho Mınimo

Definicao 93. Seja G um grafo simples, conexo e ponderado, onde os pesos sao numeros

reais positivos. O problema do caminho mınimo entre dois vertices x e y consiste em

encontrar um caminho de modo que a soma dos pesos neste caminho seja mınima.

Algoritmo 4 (Algoritmo de Bellman-Kalaba). Para determinacao da distancia entre os

vertices v1 e vn do grafo.

Utiliza o seguinte conceito de programacao dinamica: Todo caminho contendo no

maximom arestas e que seja mınimo e formado por caminhos parciais contendo no maximo

k arestas (k ≤ m) que sejam mınimos.

Algoritmo 5 (Algoritmo de Bellman-Kalaba). Para determinacao da distancia entre os

vertices v1 e vn do grafo.

Seja M = (aij)n×n a matriz de adjacencia do grafo com aii = 0 para i = 1, 2, · · · , n.

}

Defina para k = 1, 2, 3, · · · e i = 1, · · · , n,

d(k)i =

0, se i = n

ain, se i 6= n e k = 1

minj 6=i(d(k−1)j + aij), se i 6= n e k 6= 1

O algoritmo termina quando d(k)i = d(k+1)i para i = 1, 2, · · · , n. Neste caso d(k)1 e o

caminho otimo entre os vertices v1 e vn. Este algoritmo termina ate n− 1 quando o grafo

tem pelo menos 3 vertices.

Algoritmo 6 (Algoritmo de Warshall-Floyd). Para encontrar a distancia entre dois vertices

quaisquer do grafo.

8.8. OUTROS ALGORITMOS 109

procedure Warshall ( M : matriz n× n)

{M e a matriz de adjacencia do grafo com M [i, i] = 0 para i = 1, 2, · · · , n. }

var i, j, k: integer;

begin

for k: = 1 to n do

for i: = 1 to n do

for j: = 1 to n do

if M [i, j] > M [i, k] +M [k, j] then M[i, j] :=M[i, k] + M[k, j];

end; {ao termino, M = matriz de distancias dos menores caminhos }

8.8 Outros Algoritmos

(1) Algoritmo de Warshall para listagem de caminhos elementares;

(2) Algoritmo de Dijkstra para determinacao da distancia mınima entre dois vertices;

(3) Outros

Exemplo 114. Utilize o Algoritmo de Bellman-Kalaba para determinar o caminho mınimo

entre os vertices 1 e 4 do seguinte grafo:

•

•

•

••

1

2 4

32

3 11

1


Neste caso, M =

0 1 2 3

1 0 ∞ 1

2 ∞ 0 1

3 1 1 0

d(1)1 = a14 = 3

d(1)2 = a24 = 1

d(1)3 = a34 = 1

d(1)4 = 0


d(2)1 = max{d(1)2 + a12, d

(1)3 + a13, d

(1)4 + a14}

= max{1 + 1, 1 + 2, 0 + 3}

= 2

d(2)2 = max{d(1)1 + a21, d

(1)3 + a23, d

(1)4 + a24}

= max{3 + 1, 1 +∞, 0 + 1}

= 1

d(2)3 = max{d(1)1 + a31, d

(1)2 + a32, d

(1)4 + a34}

= max{3 + 2, 1 +∞, 0 + 1}

= 1

d(2)4 = 0

d(3)1 = max{d(2)2 + a12, d

(2)3 + a13, d

(2)4 + a14}

= max{1 + 1, 1 + 2, 0 + 3}

= 2

d(3)2 = max{d(2)1 + a21, d

(2)3 + a23, d

(2)4 + a24}

= max{2 + 1, 1 +∞, 0 + 1}

= 1

d(3)3 = max{d(2)1 + a31, d

(2)2 + a32, d

(2)4 + a34}

= max{2 + 2, 1 +∞, 0 + 1}

= 1

d(3)4 = 0

Portanto, como d(3)i = d(2)i ,∀i ∈ {1, 2, 3, 4}, entao o caminho mınimo do vertice 1 ao

vertice 4 possui comprimento 2.

i = 1 i = 2 i = 3 i = 4

k = 1 3 1 1 0

k = 2 2 1 1 0

k = 3 2 1 1 0

8.8.1 Lista de Exercıcios sobre Grafos

Obs.: A menos que esteja explıcito, os grafos mencionados nos exercıcios sao nao

direcionados (orientados).

1. Para cada numero natural n, Kn representa um grafo simples e completo (nao orien-

tado) com n vertices.


(a) Desenhe K4 e K5.

(b) Represente os grafos encontrados em (a) por matrizes de adjacencia.

2. Para cada par (n,m) de numeros naturais Kn,m representa um grafo bipartido com-

pleto particionado em dois subconjuntos disjuntos nao vazios com n e m conforme a

definicao de grafo bipartido completo.

(a) Desenhe K2,3, K3,4 e K2,5.

(b) Quando e que Km,n e isomorfo a Kp,q ?

3. De um exemplo de um grafo bipartido nao conexo com 7 vertice.

4. Desenhe todos os grafos nao-isomorfos, simples com dois vertices.

5. Desenhe todos os grafos nao-isomorfos, simples com tres vertices.

6. Desenhe todos os grafos nao-isomorfos, simples com quatro vertices.

7. Mostre que existem quatro arvores nao-isomorfas com quatro vertices.

8. Desenhe os grafos representados pelas matrizes de adjacencia apresentadas e repre-

sente estes grafos por meio de listas de adjacencias.

(a)

0 2 0

2 0 2

0 2 0

(b)

0 1 0 0 0 0

1 0 1 0 0 0

0 1 1 1 0 0

0 0 1 0 0 0

0 0 0 0 0 2

0 0 0 0 2 0

(c)

0 1 1 1 0

1 0 0 0 1

1 0 0 0 1

1 0 0 0 1

0 1 1 1 0


(d)

0 1 0 0 1

1 0 1 0 0

0 1 0 1 0

0 0 1 0 1

1 0 0 1 0

(e)

2 0 0 0

1 0 0 0

0 1 1 0

0 1 2 0

9. Prove que se dois caminhos reduzidos possuem dois vertices em comum e nenhuma

aresta em comum, entao este grafo possui um circuito.

10. Qual e a condicao necessaria e suficiente para que duas matrizes de adjacencia re-

presentem o mesmo grafo? Esta condicao tambem garante o isomorfismo entre dois

grafos representados por matrizes de adjacencia.

11. Desenhe uma arvore livre que so tenha vertices de grau ımpar.

12. E possıvel que uma arvore livre tenha apenas vertices de grau par?

13. Desenhe um grafo representado por 5 vertices de grau par.

14. Existe um grafo completo (nao-orientado) representado por 3 vertices de grau par?

15. Desenhe uma arvore livre com vertices de grau 4 e 1 e com pelo menos dois vertices

de grau 4.

16. Encontre duas arvores livres nao isomorfas que contenham 6 vertices e com quatro

vertices de grau 1.

• 17.] Encontre dois grafos nao isomorfos que satisfazem as seguintes condicoes:

(a) Sejam conexos e acıclicos;

(b) Tenham 4 vertices de grau 1 e 2 vertices de grau 2.

18. Encontre dois grafos nao isomorfos que satisfazem as seguintes condicoes:

(a) Tenham ciclos;


(b) Tenham 6 vertices e 7 arestas;

(c) Tenham 4 vertices de grau 2 e 2 vertices de grau 3.

19. Justifique o seguinte argumento: Existem grafos nao orientados nao isomorfos, (V1, A1, g1)

e (V2, A2, g2) tais que para uma funcao f : V1 → V2 tenhamos

(∀v1, v2 ∈ V1) (v1 e adjacente a v2 ⇒ f(v1) e adjacente a f(v2))

20. Demonstre que dois caminhos reduzidos de comprimento maximo num grafo conexo

tem um vertice em comum.

21. Seja G um grafo simples. Mostre que

2n(A) =∑v∈V

grau(v).

Conclua entao que o numero de vertices de grau ımpar e par.

22. Por que nao existe um grafo simples e regular de grau 3 com 5 vertices?

23. Encontre um grafo simples e regular com grau 3 e 6 vertices.

24. Mostre que se ao acrescentarmos a um grafo nao orientado e acıclico G uma aresta e

obtermos um circuito, entao G e conexo.

25. Utilize o metodo de Prim e o metodo de Kruskal para obter a arvore geradora mınima

para cada um dos grafos representados pelas matrizes de adjacencia abaixo conside-

rando matrizes pela sequencia padrao de vertices (1, 2, 3, 4, · · · , n).

(a) M =

∞ 3 8 4 ∞ 10

3 ∞ ∞ 6 ∞ ∞

8 ∞ ∞ ∞ 7 ∞

4 6 ∞ ∞ 1 3

∞ ∞ 7 1 ∞ 1

10 ∞ ∞ 3 1 ∞

(b) M =

∞ 1 ∞ 4 ∞

1 ∞ 3 1 5

∞ 3 ∞ 2 2

4 1 2 ∞ 3

∞ 5 2 3 ∞


(c) M =

∞ 2 ∞ ∞ 3 2 ∞

2 ∞ 1 ∞ ∞ ∞ ∞

∞ 1 ∞ 1 1 ∞ ∞

∞ ∞ 1 ∞ 1 ∞ 1

3 ∞ 1 1 ∞ 1 2

2 ∞ ∞ ∞ 1 ∞ 3

∞ ∞ ∞ 1 2 3 ∞

(d) M =

∞ 1 ∞ ∞ ∞ ∞ ∞ ∞

1 ∞ ∞ 1 3 ∞ ∞ ∞

∞ ∞ ∞ 2 ∞ ∞ ∞ ∞

∞ 1 2 ∞ 1 ∞ 2 ∞

∞ 3 ∞ 1 ∞ 1 1 ∞

∞ ∞ ∞ ∞ 1 ∞ ∞ ∞

∞ ∞ ∞ 2 1 ∞ ∞ 5

∞ ∞ ∞ ∞ ∞ ∞ 5 ∞

26. Represente grafos regulares de graus 3 e 4 com 6 vertices.

Capıtulo 9

Algebra de Boole

Definicao 94. Um sistema algebrico (B,+, ·) e uma Algebra de Boole quando e somente

quando ∀a, b, c ∈ B, valem os axiomas:

A1. a+ b ∈ B.

A2. a · b ∈ B.

A3. a+ b = b+ a.

A4. a · b = b · a.

A5. a+ (b · c) = (a+ b) · (a+ c).

A6. a · (b+ c) = (a · b) + (a · c).

A7. ∃0 ∈ B tal que para cada a ∈ B, a+ 0 = 0 + a = a.

A8. ∃1 ∈ B tal que para cada a ∈ B, a · 1 = 1 · a = a.

A9. Para cada a ∈ B, ∃a′ ∈ B tal que a+ a′ = 1 e a · a′ = 0.

Observacao 20. Em A9, o elemento a′ chama-se complemento de a.

Teorema 5 (Princıpio da Dualidade). Todo resultado dedutıvel dos axiomas de uma Algebra

de Boole permanece valido se nele trocarmos + por · e 0 por 1, e vice-versa.

Exemplo 115. A Algebra de Boole B2 = {0, 1} cujos operadores sao definidos pelas

tabelas

115

116 CAPITULO 9. ALGEBRA DE BOOLE

· 0 1

0 0 0

1 0 1

+ 0 1

0 0 1

1 1 1

e conhecida como algebra dos interruptores.

Exemplo 116. Se A e um conjunto qualquer entao (P (A),∪,∩) e uma algebra de Boole

com 0 = ∅ e 1 = A.

Observacao 21 (ASS). Os operadores + e . sao associativos.

Teorema 6. a+ a = a e a · a = a,∀a ∈ B.

Demonstracao.

a+ a

A8= (a+ a) · 1A9= (a+ a) · (a+ a′)

A5= a+ (a · a′)A9= a+ 0

A7= a

A demonstracao de a · a = a segue do Princıpio da Dualidade.

Teorema 7. a+ 1 = 1, a · 0 = 0,∀a ∈ B.

Demonstracao.

a+ 1

A8= (a+ 1) · 1A9= (a+ 1) · (a+ a′)

A5= a+ (1 · a′)A8= a+ a′

A9= 1

A demonstracao de a · 0 = 0 segue do Princıpio da Dualidade.

Teorema 8 (Lei da Absorcao). a+ (a · b) = a, a · (a+ b) = a.

117

Demonstracao.

a+ (a · b)A8= (a · 1) + (a · b)A5= a · (1 + b)

A3= a · (b+ 1)

Teo.7= a · 1

A8= a

A demonstracao de a · (a+ b) = a segue do Princıpio da Dualidade.

Teorema 9. a+ (a′ · b) = a+ b.

Demonstracao.

a+ (a′ · b)A5= (a+ a′) · (a+ b)

A9= 1 · (a+ b)

A8= a+ b

Teorema 10. O complemento de cada elemento de uma Algebra de Boole e unico.

Demonstracao. Se x e complemento de a, entao a+ x = 1 e a · x = 0.

Assim,

x

A8= x · 1A9= x · (a+ a′)

A6= (x · a) + (x · a′)A7= 0 + (x · a′)A9= (a · a′) + (x · a′)A4= (a′ · a) + (a′ · x)A6= a′ · (a+ x)

A9= a′ · 1A8= a′

A demonstracao de a · x = 0 segue do Princıpio da Dualidade.

Teorema 11. (a′)′ = a.


Demonstracao. Por A9, A3 e A4 temos que a+ a′ = a′+ a = 1 e a · a′ = a′ · a = 0. Logo

a e complemento de a′. Portanto, pelo Teorema 10, (a′)′ = a.

Teorema 12. ab+ ab′ = a.

Demonstracao.

a · b+ a · b′A6= a · (b+ b′)

A9= a · 1A8= a

Teorema 13. 0′ = 1 e 1′ = 0.

Demonstracao. Por A3, A4, A7 e A8, 0 + 1 = 1 + 0 = 1 e 0 · 1 = 1 · 0 = 0. Portanto, por

A9, temos que 0′ = 1 e 1′ = 0.

Teorema 14 (De Morgan). (a · b)′ = a′ + b′ e (a+ b)′ = a′ · b′.

Demonstracao. Como

(a · b) + (a′ + b′)A3,A5= (a+ (a′ + b′)) · (b+ (a′ + b′))

ASS,A3= ((a+ a′) + b′) · ((b+ b′) + a′)

A9= (1 + b′) · (1 + a′)

Teo.7= 1 · 1A8= 1

e(a · b) · (a′ + b′)

A6= ((a · b) · a′) + ((a · b) · b′)

ASS,A4= (b · (a · a′)) + (a · (b · b′))A9= (b · 0) + (a · 0)

Teo.7= 0 + 0

A7= 0,

entao (a · b)′ = (a′ + b′).

Como a identidade demonstrada acima vale tambem para os complementos, teremos

((a′ · b′)′)′ = ((a′)′ + (b′)′)′

Teo.11= a′ · b′ = (a+ b)′

119

Teorema 15. ab+ a′c+ bc = ab+ a′c.

Demonstracao.

ab+ a′c+ bc

A8= a · b+ a′ · c+ (b · c) · 1A9= a · b+ a′ · c+ (b · c) · (a+ a′)

A6= a · b+ a′ · c+ ((b · c) · a) + ((b · c) · a′)

ASS,A3,A4= a · b+ (a · b) · c+ a′ · c+ (a′ · c) · b

Teo.8= a · b+ a′ · c

Exercıcio 7. Prove que (a+ b)(a′ + c) = ac+ a′b.

Exercıcio 8. Simplificar as expressoes a seguir, justificando cada passagem:

(a) (a · b) + (a · b′)

(b) (p · q) + (p · (q′ · r))

(c) (b · (a · c)) + (a · (b · c′))

(d) (x+ (y · z)) · (x+ (y′ · z))

Exercıcio 9. Simplificar:

(a) ab+ ac+ abc+ ab′c′

(b) f + g + h+ f ′g′h′

(c) (p+ q + r) · (p+ q + s)

(d) x′ + xy′ + xyz + xy′z′

(e) (a+ b′)(b+ c′)(c+ d′)(d+ a′)


9.1 Minimizacao de Funcoes Booleanas

9.1.1 Metodo de Quine-McCluskey

Para este metodo, consideraremos os seguintes passos:

(1) Represente a funcao na forma de soma binaria;

(2) Divida os numeros binarios em classes, onde a classe k e formada pelos numeros

binarios com k dıgitos iguais a 1;

(3) Faca uma tabela indicando as classes, a representacao decimal e a representacao

binaria dos numeros;

(4) Utilizando a relacao xy′ + xy = x combine o elemento de uma classe com o

elemento da classe imediatamente subsequente que difere em apenas um dıgito na

representacao binaria do numero e elimine este dıgito dos numeros, marcando com

− para indicar a eliminacao;

(5) Crie uma nova tabela com os novos numeros obtidos a partir da combinacao de dois

numeros na forma binaria, dividindo por classes e indicando qual combinacao foi

feita para obter estes numeros transformados e com os numeros que nao combinaram

com nenhum numero.

(6) Se a nova tabela conter numeros que podem ser combinados, crie outra tabela repe-

tindo de passos de (4) a (5).

(7) Se nao houver numeros que possam ser combinados, escolheremos o conjunto dos

elementos da ultima tabela para encontrarmos representacoes reduzıdas para a funcao;

(8) Se alguns numeros da ultima tabela foram obtidos a partir de todos os numeros da pri-

meira tabela, entao estes numeros nos fornecem uma forma reduzida para a funcao.

9.1.2 Metodo de Karnaugh

Mapa de Karnaugh para duas variaveis

Se f(x1, x2) = f(0, 0)x′1x′2 + f(1, 0)x1x

′2 + f(1, 1)x1x2 + f(0, 1)x′1x2 e a forma canonica

de uma funcao de duas variaveis, entao o Mapa de Karnaugh e uma tabela que pode ser

escrita nas formas

9.1. MINIMIZACAO DE FUNCOES BOOLEANAS 121

x1 x′1

x2 f(1, 1) f(0, 1)

x′2 f(1, 0) f(0, 0)

Mapa de Karnaugh para tres variaveis

Se

f(x1, x2, x3) = f(0, 0, 0)x′1x′2x′3 + f(0, 0, 1)x′1x

′2x3 + f(0, 1, 0)x′1x2x

′3 + f(0, 1, 1)x′1x2x3

+f(1, 0, 0)x1x′2x3 + f(1, 0, 1)x1x

′2x3 + f(1, 1, 0)x1x2x

′3 + f(1, 1, 1)x1x2x3

e a forma canonica de uma funcao de tres variaveis, entao o Mapa (Diagrama) de Karnaugh,

neste caso pode ser representado por um dos seguintes diagramas

x1x2 x′1x2 x′1x′2 x1x

′2

x3 f(1, 1, 1) f(0, 1, 1) f(0, 0, 1) f(1, 0, 1)

x′3 f(1, 1, 0) f(0, 1, 0) f(0, 0, 0) f(1, 0, 0)

x1 x′1

x2x3 f(1, 1, 1) f(0, 1, 1)

x′2x3 f(1, 0, 1) f(0, 1, 0)

x′2x′3 f(1, 0, 0) f(0, 0, 0)

x2x′3 f(1, 1, 0) f(0, 1, 0)

Mapa de Karnaugh para quatro variaveis

Se

f(x1, x2, x3, x4) = f(0, 0, 0, 0)x′1x′2x′3x′4 + f(0, 0, 1, 0)x′1x

′2x3x

′4 + f(0, 1, 0, 0)x′1x2x

′3x′4

+f(0, 1, 1, 0)x′1x2x3x′4 + f(1, 0, 0, 0)x1x

′2x3x

′4 + f(1, 0, 1, 0)x1x

′2x3x

′4

+f(1, 1, 0, 0)x1x2x′3x′4 + f(1, 1, 1, 0)x1x2x3x

′4 + f(0, 0, 0, 1)x′1x

′2x′3x4

+f(0, 0, 1, 1)x′1x′2x3x4 + f(0, 1, 0, 1)x′1x2x

′3x4 + f(0, 1, 1, 1)x′1x2x3x4

+f(1, 0, 0, 1)x1x′2x3x4 + f(1, 0, 1, 1)x1x

′2x3x4 + f(1, 1, 0, 1)x1x2x

′3x4

+f(1, 1, 1, 1)x1x2x3x4

e a forma canonica de uma funcao de quatro variaveis, entao o Mapa (Diagrama) de Kar-

naugh, neste caso pode ser representado pelo seguinte diagrama:


x1x2 x′1x2 x′1x′2 x1x

′2

x3x4 f(1, 1, 1, 1) f(0, 1, 1, 1) f(0, 0, 1, 1) f(1, 0, 1, 1)

x′3x4 f(1, 1, 0, 1) f(0, 1, 0, 1) f(0, 0, 0, 1) f(1, 0, 0, 1)

x′3x′4 f(1, 1, 0, 0) f(0, 1, 0, 0) f(0, 0, 0, 0) f(1, 0, 0, 0)

x3x′4 f(1, 1, 1, 0) f(0, 1, 1, 0) f(0, 0, 1, 0) f(1, 0, 1, 0)

Observacao 22.

(1) A primeira linha e adjacente a ultima linha no Mapa de Karnaugh;

(2) A primeira coluna e adjacente a ultima coluna no Mapa de Karnaugh;

(3) As linhas e as colunas do Mapa de Karnaugh podem ser trocadas, desde que duas li-

nhas adjacentes ou duas colunas adjacentes sejam rotuladas por termos que diferem

de apenas uma variavel;

(4) Uma translacao cıclica das linhas e/ou colunas do Mapa de Karnaugh tambem e um

Mapa de Karnaugh;

(5) O Mapa de Karnaugh pode ser representado rotulando as linha e colunas por numeros

binarios correspondentes e/ou deixando vazias as entradas (quadrados) com 0.

Exemplo 117. A funcao booleana f(x1, x2, x3) = x1x′2x3 + x′1x

′2x3 + x1x2x

′3 + x′1x2x

′3

pode ser representada pelos seguintes Mapas de Karnaugh:

x1x2 x1x′2 x′1x

′2 x′1x2

x3 1 1

x′3 1 1

x1 x′1

x2x3

x2x′3 1 1

x′2x3 1 1

x′2x′3


Minimizacao utilizando Mapas de Karnaugh para ate quatro variaveis

Este metodo consiste em minimizar funcoes booleanas escritas na forma canonica, atraves

da regra xy′ + xy = x utilizando as seguintes regras:

1o¯

Faca um Mapa de Karnaugh que representa a funcao;

2o¯

Combine os quadrados contendo 1’s em blocos de dois quadrados para eliminar uma

variavel;

3o¯

Combine os quadrados contendo 1’s em blocos de quatro quadrados para eliminar

duas variaveis;

4o¯

Combine os quadrados contendo 1’s em blocos de oito quadrados para eliminar 3

variaveis;

5o¯

Os quadrados contendo 1’s que aparecem isolados serao considerados blocos de um

quadrado, mas nao elimina variaveis;

6o¯

A melhor maneira de escolhermos os blocos e sempre aquela que contem a menor

quantidade de blocos de 1’s e aquela que possuir blocos maiores.

Observacao 23. Para utilizarmos o Mapa de Karnaugh na minimizacao so utilizaremos

blocos (retangulos) contendo 1, 2, 4 ou 8 quadrados de 1’s.

Exemplo 118. Funcoes booleanas representadas por Mapas de Karnaugh contendo dois

quadrados adjacentes:

x1x2 x1x′2 x′1x

′2 x′1x2

x3 1 1

x′3 1 1

x1x2 x1x′2 x′1x

′2 x′1x2

x3x4 1

x3x′4

x′3x′4 1 1

x′3x4 1

Exemplo 119. Funcoes booleanas representadas por Mapas de Karnaugh contendo blocos

(retangulos) de quatro quadrados:

x1x2 x1x′2 x′1x

′2 x′1x2

x3 1 1

x′3 1 1

x1x2 x1x′2 x′1x

′2 x′1x2

x3 1 1

x′3 1 1


x1x2 x1x′2 x′1x

′2 x′1x2

x3x4 1 1

x3x′4

x′3x′4

x′3x4 1 1

x1x2 x1x′2 x′1x

′2 x′1x2

x3x4 1 1

x3x′4

x′3x′4

x′3x4 1 1

Exemplo 120. Funcoes booleanas representadas por Mapas de Karnaugh contendo blocos

(retangulos) de oito quadrados:

x1x2 x1x′2 x′1x

′2 x′1x2

x3x4 1 1 1 1

x3x′4

x′3x′4

x′3x4 1 1 1 1

x1x2 x1x′2 x′1x

′2 x′1x2

x3x4 1 1

x3x′4 1 1

x′3x′4 1 1

x′3x4 1 1

Exemplo 121. Utilize o metodo de Karnaugh para minimizar as seguintes expressoes bo-

oleanas:

(a) x′1x′2x3x4 + x1x2x

′3x4 + x′1x

′2x′3x4 + x1x

′2x3x

′4 + x1x2x3x4 + x′1x2x

′3x4 + x′1x

′2x3x

′4

(b) x′1x′2x3x4 + x1x2x

′3x4 + x′1x

′2x′3x4 + x′1x2x3x4 + x′1x

′2x′3x′4

9.1.3 Desvantagens na utilizacao do metodo de reducao de Karnaugh

(1) Este metodo se torna inviavel para a minimizacao de funcoes com mais de 4 variaveis;

(2) Para se encontrar a forma mais reduzida depende das escolhas de blocos contendo

1’s.

(3) Algoritmicamente o metodo de Quine-McCluskey para funcoes com mais de 4 variaveis.

1. Minimize as seguintes funcoes dadas pela tabela de Karnaugh pelo metodo de Quine

Mc Cluskey.


(a)

00 10 11 01

00 1 1 1 1

10 1 1

11 1 1

01

f(x1, x2, x3, x4) =∑

(0000, 0010, 0011, 1000, 1100, 0100, 0110, 0101)

Classes R. Decimal R. Binaria

0 0 0000

1 2 0010

8 1000

4 0100

2 3 0011

12 1100

6 0110

5 0101

3 7 0111


0 0, 2 00-0

0,8 -000

0,4 0-00

1 2, 3 001-

2, 6 0-10

8, 12 1-00

4, 12 -100

4, 6 01-0

4, 5 010-

2 3, 7 0-11

6, 7 011-

5, 7 01-1


0 0, 2,4,6 0–0

0,8, 4, 12 –00

0, 4, 2, 6 0–0

0,4,8,12 –00

1 2, 3, 6, 7 0-1-

2, 6,3, 7 0-1-

4, 6, 5, 7 01–

4, 5, 6, 7 01–

Podemos escrever a solucao na forma de “soma binaria”


f =∑

(−− 00, 01−−)

(b)

00 10 11 01

00 1 1

10 1 1 1 1

11 1 1

01

f =∑

(0000, 0010, 0011, 1010, 1110, 0100, 0110, 0111)


0 0 0000

1 2 0010

4 0100

2 3 0011

10 1010

6 0110

3 14 1110

7 0111


0 0, 2 00-0

0,4 0-00

1 2, 3 001-

2, 10 -010

2, 6 0-10

4, 6 01-0

2 3, 7 0-11

10, 14 1-10

6, 14 -110

6, 7 011-


0 0, 2,4,6 0–0

0, 4, 2, 6 0–0

1 2, 3, 6, 7 0-1-

2, 10, 6, 14 –10

2, 6, 10, 14 –10

Podemos escrever a solucao na forma de “soma binaria”

f =∑

(0−−0, 0− 1−,−− 10)

Capıtulo 10

Duvidas Correlatas em aula

(1) Seja n ∈ N. Mostre que se n ≥ 3, entao n+1√n+ 1 < n

√n.

Demonstracao. E suficiente provarmos que nn+1 > (n+ 1)n para n ≥ 3.

Primeira demonstracao: Basta notar que 2 < (1 + 1n)n < e para todo n ∈ N∗.

Assim, para n ≥ 3, temos que(1 +

1

n

)n< 3 ≤ n⇒

(n+ 1

n

)n< n⇒ (n+ 1)n < nnn ⇒ (n+ 1)n < nn+1.

Segunda demonstracao: (Assintotica) Como lim(1+ 1

n)n

n= 0, entao para ε = 1,

existira n0 ∈ N tal que para n ≥ n0,

∣∣∣∣(1 + 1n)n

n

∣∣∣∣ < ε = 1.

Assim, para n ≥ n0,

(1 + 1n)n

n< 1⇒

(n+ 1

n

)n< n⇒ (n+ 1)n < nnn ⇒ (n+ 1)n < nn+1.

Terceira demonstracao (Usando que f(x) = x1/x e derivavel) :

Seja f(x) = x1/x, Entao

f(x) = exp

[1

xlnx

]Assim, para x ≥ 3,

f ′(x) = exp

[1

xlnx

](− 1

x2lnx+

1

x2

)= x1/x

(− 1

x2lnx+

1

x2

)< 0

127

128 CAPITULO 10. DUVIDAS CORRELATAS EM AULA

Portanto, a funcao f(x) = x1/x e decrescente para todo x ≥ 3 e

n1/n > (n+ 1)1/(n+1)

ou sejan√n > n+1

√n+ 1

(2) Analise a convergencia da serie∑∞

n=11

n n√n .

Primeira demonstracao:

Como lim n√n = 1, entao para ε = 1, existira n0 ∈ N tal que

| n√n− 1| < ε = 1,∀n ≥ n0

Assim, para n ≥ n0,

| n√n− 1| < 1

⇒ −1 < n√n− 1 < 1

⇒ 0 < n√n < 2

⇒ 1n√n >

12

⇒ 1n n√n >

12n

Logo, pelo Criterio da Comparacao, como∑

1n

diverge, entao∑

1n n√n tambem di-

verge.

Segunda demonstracao:

Como n < 2n para todo n ∈ N, entao

n√n < 2

⇒ n n√n < 2n

⇒ 1n n√n >

12n

Logo, pelo Criterio da Comparacao, como∑

1n

diverge, entao∑

1n n√n tambem di-

verge.

Referencias Bibliograficas

[1] DAGHLIAN, Jacob. Logica e Algebra de Boole. - 4. ed. - Sao Paulo: Editora

Atlas, 1995.

[2] FIGUEIREDO, Djairo G., Analise I, LTC - Livros Tecnicos e Cientıficos, Rio

de Janeiro, 1996.

[3] FURTADO, Antonio Luz. Teoria dos Grafos: algoritmos. Sao Paulo: LTC, 1973.

[4] GERSTING, Judith L. Fundamentos Matematicos para a Ciencia da

Computacao. - 4. ed. - Rio de Janeiro: LTC, 2001.

[5] HOERNES, Gerhard E. & HEILWEIL, Melvin F. Introduccion al algebra de

Boole y a los dispositivos logicos (Autoensenanza Programada). Madrid: Para-

ninfo, 1976.

[6] HUNTER, David J. Fundamentos da Matematica Discreta. Rio de Janeiro: LTC,

2011.

[7] JOHNSONBAUGH, Richard. Matematicas Discretas. Mexico, D. F.: Grupo

Editorial Iberoamerica, 1988.

[8] LIMA, Elon L., Curso de Analise, Vol. 1, Projeto Euclides, IMPA - CNPq, 1995.

[9] LIPSCHUTZ, Seymor. Teoria dos Conjuntos. Sao Paulo: McGraw-Hill, 1978.

[10] SANTOS, Jose Plınio de O. Introducao a Teoria dos Numeros. Rio de Janeiro:

IMPA-CNPq, 1998. 199p. (Colecao Matematica Universitaria).

[11] ZIVIANI, Nivio. Projeto de Algoritmos com implementacoes em Pascal e C. - 2.

ed. - Sao Paulo: Cengage Learning, 2009.

129

Documents

Matemática Discreta