Matematica Discreta - Rodrigo Veloso
Matematica Discreta - Rodrigo Veloso
I Parte Um
1 Lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Proposições 1
1.2 Conectivos ou Operadores Lógicos 2
1.3 Fórmulas Lógicas e Tabelas Verdade 6
1.4 Tautologia e Contradição 8
1.5 Equivalências Proposicionais 8
2 Predicados e Quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1 Predicados 11
2.2 Quantificadores 12
II Parte Dois
4 Conjuntos e Funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1 Conjuntos 31
4.2 Operações de Conjuntos 36
4.3 Funções 40
4.4 Funções Compostas e Inversas 43
4.5 Funções de Hash 46
6 Indução e Recursividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.1 Indução Matemática 61
6.2 Recursividade 65
8 Relações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.1 Relações e suas Propriedades 85
8.2 Relações de Equivalências 87
9 Grafos e Árvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
9.1 Grafos 91
9.2 Terminologia Básica de Grafos 93
9.3 Tipos Especiais de Grafos 94
9.4 Representação de Grafos 95
9.5 Isomorfismo de Grafos 97
9.6 Conectividade de Grafos 99
9.7 Árvores 101
IV Parte Três
10 Análise de Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
10.1 Complexidade de algoritmos 107
10.2 Crescimento de Funções 111
I
Parte Um
1 Lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Proposições
1.2 Conectivos ou Operadores Lógicos
1.3 Fórmulas Lógicas e Tabelas Verdade
1.4 Tautologia e Contradição
1.5 Equivalências Proposicionais
2 Predicados e Quantificadores . . . . . . . . 11
2.1 Predicados
2.2 Quantificadores
1.1 Proposições
Definição 1.1.1 Uma proposição é uma frase ou construção à qual podemos atribuir um
julgamento de verdadeiro ou falso.
Podemos dizer que proposições são frases que declaram um fato e podem ser classificadas
como verdadeiras ou falsas. O valor-verdade de uma proposição pode ser escrito através da notação
V (·):
2 Capítulo 1. Lógica
p q
V F
Tabela 1.1: Valores-verdade de “Seis é menor que sete” e “Toronto é a capital do Canadá”.
Conjunção.
A conjunção de duas proposições p,q é escrita como p ∧ q e é lida como “p e q”. A proposição
resultante é dita composta pois é fruto da combinação de outras duas e refleta uma noção de
simultaneidade: é necessário que ambas p e q sejam verdadeiras para que p ∧ q seja verdadeira.
Veja a Tabela 1.2, onde encontramos todas as possibilidade de valores-verdade para p e q.
p q p∧q
V V V
V F F
F V F
F F F
Disjunção.
A disjunção de duas proposições p ∨ q é lida como “p ou q”. Para que p ∨ q seja verdade, é preciso
que pelo menos uma das proposições seja verdadeira (Tabela 1.3).
p q p∨q p q p⊕q
V V V V V F
V F V V F V
F V V F V V
F F F F F F
Tabela 1.3: Tabela-verdade de uma disjun- Tabela 1.4: Tabela-verdade de uma disjunção
ção. exclusiva.
p. 23 = 8, r. 2 + 3 < 4,
q. 32 = 6, s. 3 · 5 = 15.
Negação.
A negação de uma proposição p é construída ao se introduzir “Não é verdade que” à frente da
frase, ou alguma expressão equivalente. A negação de uma proposição p é representada por ¬p ou
∼ p; esta notação é lida como “não p”.
■ Exemplo 1.2.3 Considere as seguintes proposições.
(i) Hoje é terça-feira.
(ii) 2 + 2 = 5.
(iii) No mínimo 10mm de chuva caíram ontem em Curitiba.
A negação destas proposições é dada por
(i) Não é verdade que hoje é terça-feira.
4 Capítulo 1. Lógica
Tabela 1.6: Tabela-verdade de uma ne- Tabela 1.7: Tabela-verdade da negação de “Hoje
gação. é terça-feira”.
■ Exemplo 1.2.4 Considere a proposição p definida por “Hoje é terça feira”. Sua negativa ¬p é
dada por “Hoje não é terça-feira”. Podemos resumir as possibilidades de valores-verdade para p e
¬p através da Tabela 1.7. ■
Implicação ou condição.
Sejam p e q proposições. A proposição “se p então q” é chamada de condição ou implicação
e é escrita como p → q. Neste caso dizemos que p é hipótese ou antecedente e q é chamada de
conclusão ou consequente. A tabela-verdade de uma implicação é dada na Tabela 1.8.
p q p→q
V V V
V F F
F V V
F F V
Discreta e não conseguir um bom emprego; caso contrário não há nada de errado com o “discurso”
acima, então dizemos que a proposição é verdadeira. ■
A implicação p → q também pode ser escrita como “p é condição suficiente para q”: no
caso acima temos “Para conseguir um bom emprego, é suficiente que Aline aprenda Matemática
Discreta.” Uma implicação também pode ser reescrita usando o termo condição necessária: p → q
pode ser escrita como “q é uma condição necessária para p”; veja o exemplo abaixo.
■ Exemplo 1.2.6 Considere a proposição “Se há fumaça, então há fogo.” Esta proposição pode
ser reescrita como “Há fumaça sempre que há fogo” ou “Fogo é uma condição necessária para
fumaça”. ■
Proposição bicondicional.
Sejam p e q proposições. A proposição bicondicional p ↔ q, lida como “p se e somente se q”, é
verdadeira sempre que p,q têm o mesmo valor-verdade, e é falsa caso contrário; veja a Tabela 1.9.
Bicondicionais também são chamadas de bi-implicações.
p q p↔q
V V V
V F F
F V F
F F V
■ Exemplo 1.2.8 Considere as proposições p e q definidas por “Você pode embarcar no avião” e
“Você comprou uma passagem”. A bicondicional p ↔ q é dada por “Você pode embarcar no avião
se e somente se você comprou uma passagem.” Veja a Tabela 1.10, que contém o valor-verdade da
proposição bicondicional em cada uma das possíveis configurações de valores-verdade de p,q.
Podemos pensar da seguinte maneira. Suponha que a proposição “Você pode embarcar no
avião se e somente se você comprou uma passagem” é verdadeira. Nesse caso p e q devem ter o
mesmo valor verdade: se p é verdadeira (você pode tomar o avião), então q é verdadeira (você
comprou uma passagem); se p é falsa (você não pode tomar o avião), então q é falsa (você não
comprou uma passagem). Por outro lado, se a bicondicional “Você pode embarcar no avião se
e somente se você comprou uma passagem” é falsa, isto significa há uma falha na argumentação
acima, isto é, é possível que as proposições tenham valores-verdade diferentes:
• p verdadeira (você pode tomar o avião) e q falsa (você não comprou uma passagem), ou
• p é falsa (você não pode tomar o avião) e q verdadeira (você comprou uma passagem).
■
6 Capítulo 1. Lógica
p : Você pode embarcar no avião q : Você comprou uma passagem p↔q
V V V
V F F
F V F
F F V
p q ¬q p q ¬q p ∨ ¬q
V V F V V F V
V F V V F V V
F V F F V F F
F F V F F V V
Tabela 1.11: V(¬q) a partir de V (p) e Tabela 1.12: Valores-verdade para p ∨ ¬q a partir
V (q). da Tabela 1.12.
A escrita de tais fórmulas pode ser simplificada com algumas convenções. Por exemplo:
convencionamos que a negação é aplicada antes de qualquer outro operador lógico. Logo ¬p ∧ q
representa a mesma expressão1 que (¬p) ∧ q. Mais geralmente, a seguinte ordem de precedência é
convencionada:
(i) Conectivos entre parênteses, dos mais internos para os mais externos.
(ii) Negação (¬).
(iii) Conjução (∧) e disjunção (∨).
(iv) Implicação (→).
(v) bicondicional (↔).
Por exemplo, se p,q,r são proposições, então:
• p ∨ (¬q) pode ser escrita como p ∨ ¬q;
1A expressão (¬p) ∧ q poderia ser interpretada como ¬(p ∧ q); porém, como a negação é aplicada antes da conjunção,
¬p → ∧¬ ∨ .
Restringimos nossa atenção a fórmulas lógicas que geram expressões bem definidas; alguns autores
denominam estas fórmulas de fórmulas bem-formuladas.
■ Exemplo 1.3.3 Sejam p,q proposições. O valor-verdade de p ↔ q coincide em todos os casos
com o da proposição (p → q) ∧ (q → p). Em outras palavras, a condicional p ↔ q é verdadeira
quando as implicações p → q e q → p são ambas verdadeiras.
Verificamos esta coincidência através de uma tabela-verdade, como no Exemplo 1.3.1; veja a
Tabela 1.13. Incluímos nas duas primeiras colunas as quatro configurações possíveis de valores
verdade para p,q. A seguir acrescentamos na tabela as proposições formadas a partir das colunas já
incluídas na tabela: a partir de p,q podemos incluir p → q e q → p; e a partir destas duas implicações
podemos analisar os valores-verdade de (p → q) ∧ (q → p). Note a fórmula (p → q) ∧ (q → p) é
verdadeira exatamente nos casos em que p,q possuem o mesmo valor-verdade, isto é, esta fórmula
lógica coincide com p ↔ q. ■
p q p→q q→ p (p → q) ∧ (q → p)
V V V V V
V F F V F
F V V F F
F F V V V
■ Exemplo 1.3.4 Considere a fórmula lógica (p → q) ↔ (¬q → ¬p). Veja na Tabela 1.14 o
valor-verdade desta proposição composta em cada um dos casos possíveis de valores-verdade para
p,q. ■
Contrapositiva.
Note que a proposição (p → q) ↔ (¬q → ¬p) é sempre verdadeira; tais proposições são tratadas
com mais detalhes na Seção 1.4. A proposição (¬q → ¬p) é dita a contrapositiva da implicação
(p → q). A Tabela 1.14 mostra que uma implicação e sua contrapositiva possuem sempre o mesmo
valor-verdade.
■ Exemplo 1.3.5 Considere as proposições p,q dadas por “Está chovendo” e “A calçada em frente
à minha casa está molhada”. A implicação p → q pode ser escrita como “Se está chovendo então a
calçada em frente à minha casa está molhada.” A contrapositiva ¬q → ¬p é escrita como “Se a
calçada em frente à minha casa não está molhada então não está chovendo.” A tabela-verdade para
estas proposições é dada na Tabela 1.14. ■
8 Capítulo 1. Lógica
■ Exemplo 1.4.2 Seja p uma proposição. Temos que p ∨ ¬p é uma tautologia e p ∧ q é uma
contradição, como ilustrado na Tabela 1.15.
Como uma ilustração, considere a proposição p dada por “Hoje é terça-feira”. Então a proposi-
ção p ∨ ¬p pode ser escrita como “Hoje é terça-feira ou hoje não é terça-feira.” Esta declaração é
claramente verdadeira em qualquer situação. Já a proposição p ∧ ¬p pode ser escrita como “Hoje é
terça-feira e hoje não é terça-feira,” o que é uma contradição; não é possível que um dado dia seja e
não seja, simultaneamente, terça-feira. ■
p ¬p p ∨ ¬q p ∧ ¬p
V F V F
F V V F
esta expressão deve considerar todas as possibilidades de valores-verdade para p,q,r. Como cada
variável tem duas possibilidades (V ou F), temos 2 · 2 · 2 = 8 possibilidades de valores-verdade para
p,q,r. Segue que as tabelas deste exemplo contêm 8 linhas.
Analisamos o valor-verdade de p ∨ (q ∧ r) e (p ∨ q) ∧ (p ∨ r) na Tabela 1.16. A seguir utilizamos
a Tabela 1.9 e as duas colunas correspondentes da Tabela 1.16 para analisar a bicondicional
p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p ∨ r); veja a Tabela 1.17. Como esta proposição é sempre verdadeira,
concluímos que ela é uma tautologia. ■
p ∨ (q ∧
p q r q∧r p∨q p∨r (p ∨ q) ∧ (p ∨ r)
r)
V V V V V V V V
V V F F V V V V
V F V F V V V V
V F F F V V V V
F V V V V V V V
F V F F F V F F
F F V F F F V F
F F F F F F F F
p ∨ (q ∧
p q r (p ∨ q) ∧ (p ∨ r) p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p ∨ r)
r)
V V V V V V
V V F V V V
V F V V V V
V F F V V V
F V V V V V
F V F F F V
F F V F F V
F F F F F V
Nos teoremas abaixo temos algumas equivalências importantes. A demonstração destas equiva-
lências utilizando tabelas-verdade é deixada como exercício.
Teorema 1.5.2 Sejam p,q,r proposições. As proposições abaixo são logicamente equivalentes.
• Propriedades dos elementos neutros: p ∧V ≡ p, p ∨ F ≡ p.
• Propriedades de dominação: p ∨V ≡ V, p ∧ F ≡ F.
• Propriedades idempotentes: p ∨ p ≡ p, p ∧ p ≡ p.
• Propriedade da dupla negação: ¬(¬p) ≡ p.
• Propriedades comutativas: p ∨ q ≡ q ∨ p, p ∧ q ≡ q ∧ p.
• Propriedade associativas: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r), (p ∧ q) ∧ r ≡ p ∧ (q ∧ r).
• Propriedade distributivas: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r).
• Leis de Morgan: ¬(p ∨ q) ≡ ¬p ∧ ¬q, ¬(p ∧ q) ≡ ¬p ∨ ¬q.
• Propriedades de absorção: p ∨ (p ∧ q) ≡ p, p ∧ (p ∨ q) ≡ p.
• Propriedades de negação: p ∨ ¬p ≡ V, p ∧ ¬p ≡ F.
Teorema 1.5.3 Sejam p,q,r proposições. As proposições abaixo são logicamente equivalentes.
• p → q ≡ ¬p ∨ q. • (p → q) ∧ (p → r) ≡ p → (q ∧ r).
• p → q ≡ ¬q → ¬p. • (p → r) ∧ (q → r) ≡ (p ∨ q) → r.
• p ∨ q ≡ ¬p → q. • (p → q) ∨ (p → r) ≡ p → (q ∨ r).
• p ∧ q ≡ ¬(p → ¬q). • (p → r) ∨ (q → r) ≡ (p ∧ q) → r.
• ¬(p → q) ≡ p ∧ ¬q.
Teorema 1.5.4 Sejam p,q,r proposições. As proposições abaixo são logicamente equivalentes.
10 Capítulo 1. Lógica
No exemplo abaixo provaremos que duas proposições são logicamente equivalentes através de
uma sequência de equivalências obtidas a partir do Teorema 1.5.2. Para tal faremos uso teorema
abaixo.
Teorema 1.5.7 Sejam p,q,r proposições compostas tais que p ≡ q e q ≡ r. Então p ≡ r.
O lado direito da equivalência acima coincide com uma das propriedades de dominação, a menos
da ordem da disjunção; no entanto, pela propriedade comutativa da disjunção, esta ordem não é
importante. Segue portanto de uma das propriedades de dominação que o lado direito acima é
equivalente a (¬p ∧ ¬q), como gostaríamos: ¬p ∧ (p ∨ ¬q) ≡ ¬p ∧ ¬q. ■
2. Predicados e Quantificadores
Considere a afirmação
“Todo aluno que está cursando Cálculo 2 foi aprovado em Cálculo 1.”
Mesmo sabendo que a afirmação acima é verdadeira, o conteúdo visto nas seções acima não nos dá
um caminho lógico preciso para concluir que a afirmação abaixo é verdadeira:
“Aline, uma das alunas que está cursando Cálculo 2, foi aprovada em Cálculo 1.”
Como fazer corresponder as afirmações acima com proposições p,q e concluir, usando os operadores
lógicos acima, que se a primeira proposição é verdadeira então necessariamente a outra também
deve ser?
A lógica que vimos na seção anteriores é chamada de lógica proposicional. Nesta seção
introduzimos a lógica de predicados, que nos permite investigar de maneira mais ampla afirmações
sobre elementos de conjuntos.
2.1 Predicados
Considere a declaração “x > 1”. Essa declaração não é uma proposição, pois não podemos atribuir
verdadeiro ou falso a ela a menos que seja escolhida um valor para x. Por exemplo: para x = 0
temos V (0 > 1) = F (proposição falsa), enquanto para x = 5 temos V (5 > 1) = V (proposição
verdadeira).
A declaração “x > 1” pode ser analisada como na análise sintática da língua portuguesa: “x é
maior que 1” possui um sujeito x sobre o qual a declaração declara alguma coisa; “é maior que 1”
é dito o predicado da declaração. A declaração x > 1 pode ser escrita em linguagem matemática
como P(x), onde P representa o predicado “é maior que 1” e x é a variável em que o predicado atua.
Obs 2.1.1 A declaração P(x) também é chamada de valor da função proposicional P em x. Note a
semelhança da notação P(x) no caso acima, de predicado aplicado a uma variável, com a notação
de funções reais como a função quadrática f (x) = x2 .
12 Capítulo 2. Predicados e Quantificadores
■ Exemplo 2.1.2 Considere a declaração P(x) dada por x ≤ 4. Determine o valor verdade das
proposições P(1) e P(5).
A proposição P(1) é obtida substituindo x por 1 em P(x), isto é, P(1) é a proposição “1 ≤ 4,
que é verdadeira. A proposição P(5) é obtida analogamente: obtemos 5 ≤ 4, que é uma proposição
falsa. ■
Podemos também considerar predicados que envolvem mais de uma variável, como no exemplo
abaixo.
■ Exemplo 2.1.3 Considere a declaração x2 = y2 + 3. Para obtermos uma proposição a que
podemos atribuir um valor-verdade, devemos atribuir valores para x e y. Por exemplo: para x = 2 e
y = 1 temos a proposição “22 = 12 + 3”, que é uma proposição verdadeira.
Podemos interpretar essa declaração através de sujeito e predicado, como discutido acima,
porém agora com o sujeito composto por duas variáveis: x e y. Podemos escrevê-la matematica-
mente como P(x,y), onde x,y são variáveis e P é o predicado. A proposição acima pode ser escrita
como P(2,1): para x = 2 e y = 1 temos “22 = 12 + 3”, uma proposição verdadeira. Já a proposição
P(4,5), dada por “42 = 52 + 3”, é falsa. ■
Podemos usar a lógica de predicados para entender declarações da forma “if-else” em linguagens
de programação. Suponha que um programa de computador possui a seguinte instrução:
if x > 2 then x := x + 1.
A instrução acima é lida como “se x > 2 então x := x + 1”, mas possui um significado diferente
do conectivo lógico que vimos na Seção 1.2. Escreva a condição x > 2 como um predicado P(x).
Se a execução do programa chega à linha acima com um valor para a variável x que torna P(x)
verdadeiro, então o valor de x é atualizado para x + 1; se o valor da variável x na execução torna
P(x) falso, então a instrução x =:= x + 1 não é executada.
2.2 Quantificadores
Considere as declarações
Ambas declarações envolvem o predicado “é menor de idade”, que denotamos aqui por P. A
primeira declaração não é uma proposição: podemos escrevê-la como P(x) e ela passa a ser uma
proposição quando atribuímos um certo aluno à variável x. A segunda declaração é uma proposição,
porém o seu sujeito não se refere a um aluno específico, mas sim a todos os alunos de um conjunto.
A proposição “Todo aluno de Matemática Discreta é menor de idade” foi obtida a partir do
predicado P usando um quantificador. A quantificação é uma maneira de criar proposições ao
declarar que um certo predicado é verdadeiro para os elementos de um certo conjunto. No caso
da declaração “Todo aluno de Matemática Discreta é menor de idade”, este conjunto é aquele
dos alunos da disciplina de Matemática Discreta. A área da lógica que estuda predicados e
quantificadores é chamada de cálculo de predicados.
2.2 Quantificadores 13
Quantificador universal.
Considere a declaração “2x é positivo para todo número real x positivo”. Podemos identificar duas
partes desta declaração:
• a afirmação “2x é positivo”, que possui sujeito 2x e predicado “é positivo”;
• “para todo número real x positivo”, a especificação de para quais valores da variável x a
declaração acima é verdadeira.
O conjunto de valores para a variável x (números reais positivos) considerado na declaração acima
é dito o universo de discurso, domínio de discurso, ou simplesmente o domínio. Declarações como
“2x é positivo para todo número real x positivo” são definidas como a quantificação universal de
uma declaração P(x). Uma quantificação universal deve ter um domínio especificado; sem um
domínio uma quantificação universal não está bem definida.
Definição 2.2.1 A quantificação universal de uma declaração P(x) é definida como
A quantificação ∀xP(x) pode ser lida, dentre outras maneiras, como “para todo x P(x)”, “todos
os x satisfazem P(x)”, “para qualquer x temos P(x)”, “dado qualquer x temos P(x)”.
■ Exemplo 2.2.2 Considere a declaração P(x) definida por x + 1 > x. Qual o valor verdade da
Segue que 2x > x não é verdadeiro para todo número real x e, portanto, a quantificação é falsa. ■
■ Exemplo 2.2.4 Considere a declaração P(x) definida por 2x > x. Qual o valor-verdade da
quantificação ∀xP(x) no domínio de todos os números reais positivos?
Para mostrar que ∀xP(x) é uma declaração falsa deveríamos encontrar um contra-exemplo no
domínio da declaração. Isto não é possível, pois realmente 2x > x para todo número real positivo.
Segue que a quantificação do enunciado é verdadeira. ■
14 Capítulo 2. Predicados e Quantificadores
Obs 2.2.6 Quando podemos listar todos os elementos de uma quantificação ∀xP(x) como x1 , . . . , xn ,
podemos escrever ∀xP(x) como a proposição P(x1 ) ∧ P(x2 ) ∧ · · · ∧ P(xn ). A quantificação do item
(iii) do Exercício 2.2.5 pode ser escrita como
Q(1) ∧ Q(2) ∧ Q(3) ∧ Q(4), isto é, (12 < 10) ∧ (22 < 10) ∧ (32 < 10) ∧ (42 < 10).
Para a conjunção acima ser verdadeira, devemos ter todas as proposições verdadeiras. Como
V (42 < 10) = F, a quantificação do item (iii) é falsa. A quantificação do item (iv) pode ser escrita
de maneira análoga.
Quantificador existencial.
Definição 2.2.7 A quantificação existencial de uma declaração P(x) é definida como
A quantificação ∃xP(x) em um dado domínio é falsa quando P(x) é falsa para todo elemento
do seu domínio. Veja o exemplo abaixo.
■ Exemplo 2.2.9 Seja P(x) a declaração x2 = −1. Qual o valor-verdade da quantificação ∃xP(x)
no domínio dos números reais?
O quadrado de todo número real é maior ou igual a zero, logo não existe um número real
que satisfaça x2 = −1. Em outras palavras, P(x) é falsa para todo número real x. Segue que a
quantificação do enunciado é falsa. ■
Obs 2.2.10 A quantificação ∃xP(x) só está bem definida quando acompanhada de um domínio
especificado. Se o domínio desta quantificação é vazio então ∃xP(x) é considerada verdadeira:
2.2 Quantificadores 15
podemos pensar que, por falta de provas do contrário, a quantificação é “inocentada” e é considerada
verdadeira.
Obs 2.2.12 Quando o domínio de uma quantificação ∃xP(x) consiste de um conjunto finito
como {x1 , . . . , xn }, podemos escrever ∃xP(x) como a proposição P(x1 ) ∨ P(x2 ) ∨ · · · ∨ P(xn ). A
quantificação do item (iii) do Exercício 2.2.11 pode ser escrita como
Q(1) ∨ Q(2) ∨ Q(3), isto é, (12 ≤ 1) ∧ (22 ≤ 1) ∧ (32 ≤ 1).
Para a disjunção acima ser verdadeira, devemos ter pelo menos das proposições verdadeiras; veja a
Tabela. Como V (42 < 10) = F, a quantificação do item (iii) é falsa. A quantificação do item (iv)
pode ser escrita de maneira análoga.
Obs 2.2.15 A quantificação do Exercício 2.2.14 também pode ser escrita como ∃x(x > 0 ∧ x2 = 5)
com domínio dos números reais.
Obs 2.2.18 Declarações envolvendo quantificadores têm a sua escrita simplificada com a seguinte
regra: os quantificadores ∀ e ∃ têm prioridade maior que todos os operadores lógicos. Por exemplo,
a declaração ∀xP(x) ∨ Q(x) representa (∀xP(x)) ∨ Q(x) e não ∀x(P(x) ∨ Q(x)).
Equivalências entre declarações envolvendo quantificações são importantes para caracterizar
negações. Considere e declaração
“Todo aluno de Matemática Discreta é maior de idade.”
O que caracteriza a negação desta declaração? Para responder esta pergunta precisamente, escreve-
mos a declaração acima como ∀xP(x), onde o domínio de discurso é o conjunto de todos os alunos
de Matemática Discreta e P(x) é dada por “x é maior de idade”. A negação desta declaração é dada
por
2.2 Quantificadores 17
Exercício 2.2.20 Escreva as declarações abaixo como quantificações e obtenha as suas negati-
vas.
(i) Todas as mulheres querem ter filhos.
(ii) Existe um iPhone que é barato.
■
Exercício 2.2.21 Escreva a negativa das quantificações abaixo usando o Teorema 2.2.19.
A negativa do Exemplo 2.2.22 abaixo é bastante utilizada em Matemática, por isso damos
destaque a ela aqui.
■ Exemplo 2.2.22 Mostre que as declarações ¬∀x(P(x) → Q(x)) e ∃x(P(x) ∧ ¬Q(x)) são logica-
mente equivalentes.
Temos do Teorema 2.2.19 que ¬∀x(P(x) → Q(x)) é equivalente a ∃x(¬(P(x) → Q(x))). Sabe-
mos do Teorema 1.5.3 que ¬(P(x) → Q(x)) é equivalente a P(x) ∧ ¬Q(x), ou seja: ¬(P(x) → Q(x))
e P(x) ∧ ¬Q(x) possuem sempre o mesmo valor-verdade. Podemos portanto substituir uma des-
tas expressões pela outra em uma equivalência lógica, donde segue que ¬∀x(P(x) → Q(x)) é
equivalente a ∃x(P(x) ∧ ¬Q(x)). ■
Quantificadores agrupados.
Muitos resultados importantes de matemática envolvem mais de um quantificador, onde um está
dentro do escopo do outro. Considere a seguinte declaração:
“Para todo número real x existe um número real y tal que x + y = 0.” (2.3)
18 Capítulo 2. Predicados e Quantificadores
A proposição acima é verdadeira: para cada número real x temos o número real y = −x tal que
x + y = 0. Como esta proposição se aplicada a todo elemento x de um domínio especificado
(conjunto dos números reais), podemos escrevê-la como
∀xQ(x),
onde Q(x) representa a declaração “existe um número real y tal que x + y = 0”. Ou seja, podemos
escrever Q(x) através de um quantificador existencial:
∃yP(x,y),
onde P(x,y) representa a declaração x + y = 0. Segue que a declaração (2.3) pode ser escrita como
Este é um exemplo de uma sentença com quantificadores agrupados. Veja os Exemplos 2.2.23 e
2.2.24 a seguir.
■Exemplo 2.2.23 Considere a declaração ∀x∀y(x · y = y · x) com o conjunto dos números reais
como domínio. Podemos traduzi-la para o português como “para todo número real x e para todo
número real y temos (x · y = y · x).” Em outras palavras, esta declaração afirma que para todo par de
números reais x,y temos xy = yx. Esta proposição é claramente verdadeira. ■
■ Exemplo 2.2.24 Considere a declaração ∀x∃y(y < x) com o conjunto dos números reais como
domínio. Esta sentença pode ser escrita como “para todo número real x existe número real y tal que
(y < x).” Esta proposição é verdadeira: para todo número real x fixado observamos que y = x − 1 é
um número real que satisfaz y < x. ■
Obs 2.2.25 A ordem dos quantificadores é essencial para o significado de sua sentença. A
declaração ∀x∃y(x + y = 0) pode ser escrita como
“para todo número real x existe número real y tal que (x + y = 0),”
“existe um número real x tal que para todo número real y temos (x + y = 0).”
O objetivo deste capítulo é a compreensão do que representa uma demonstração matemática válida.
Uma demonstração matemática deve ser baseada em um argumento válido: é apresentada uma
sequência de sentenças, ditas premissas, e uma sentença final dita a conclusão; no caso em que
todas as sentenças são verdadeiras, a conclusão também deve ser. Em outras palavras, em um
argumento válido não podemos ter a conclusão falsa no caso em que todas as outras sentenças do
argumento são verdadeiras.
É importante destacar que nem sempre é imediato concluir que a conclusão é verdadeira a
partir das premissas. Muitas vezes é necessário obter sentenças “intermediárias”, que não foram
fornecidas como premissas, mas nos ajudam a concluir que a conclusão deve ser verdadeira. Na
primeira seção deste capítulo veremos como obter novas sentenças a partir daquelas que foram
dadas com regras de inferência.
p→q
p (3.1)
∴q
onde o símbolo “∴” é lido como “portanto”. Temos neste caso que p → q e p são as premissas do
20 Capítulo 3. Regras de Inferência e Demonstrações
Temos acima uma forma válida de argumento: sempre que as premissas p → q e p são
verdadeiras, temos a conclusão q é verdadeira. Esta forma de argumentação pode ser aplicada a
diversas proposições, com as proposições p,q vistas no início desta seção. Se p,q são as proposições
“Você tem pelo menos 18 anos” e “Você pode entrar no parque”, a mesma forma de argumentação
constrói um argumento válido:
“Se você tem pelo menos 18 anos, então você pode entrar no parque.”
“Você tem pelo menos 18 anos. (3.2)
∴ “Você pode entrar no parque.”
É importante destacar que o argumento acima é sempre válido, porém se uma de suas premissas
é falsa, não podemos concluir que a conclusão é verdadeira. Por exemplo: o argumento acima
relativo à entrada no parque é sempre válido mas, se você não possui pelo menos 18 anos de idade,
não podemos utilizá-lo para concluir que você pode entrar no parque1 .
A validade de um argumento é definida pela sua forma de argumento, obtida ao substituir suas
proposições por variáveis proposicionais; veja o caso do argumento (3.2) e a forma de argumento
em (3.1).
Definição 3.1.1 Um argumento em lógica proposicional é uma sequência de proposições.
A última proposição é chamada de conclusão e todas as outras são chamadas de premissas.
Um argumento é dito válido se a conclusão é necessariamente verdadeira no caso em que as
premissas são verdadeiras.
Uma forma de argumento em lógica proposicional é uma sequência (p1 , p2 , . . . , pn , q) de
proposições compostas que envolvem variáveis proposicionais. Uma forma de argumento é
dita válida se (p1 ∧ p2 ∧ · · · ∧ pn ) → q é uma tautologia. Em outras palavras, a forma de argu-
mento é dita válida se, para quaisquer que sejam as proposições substituídas em suas variáveis
proposicionais, a a conclusão é necessariamente verdadeira no caso em que as premissas são
verdadeiras.
Regras de Inferência
Podemos verificar a validade de uma forma de argumento por tabelas-verdade, pois assim podemos
determinar se ela é uma tautologia. No entanto, uma forma de argumento envolvendo n proposições
deve levar em conta todas as configurações possíveis de valores-verdade para elas; isto significa que
a tabela-verdade deve conter 2n linhas, o que se torna impraticável já para pequenos valores de n.
1 Talvez você possa ainda assim, conversando com o gerente e sendo acompanhado por um responsável, porém o
argumento acima não nos permite concluir que sua entrada é permitida.
3.1 Regras de Inferência 21
Uma alternativa é utilizar regras de inferência, que nos permitem deduzir novas sentenças a partir
das premissas, construindo passo-a-passo um caminho que nos levará à veracidade da conclusão.
Vimos acima uma regra de inferência, baseada na tautologia ((p → q) ∧ p) → q. Ela é chamada
de modus ponens ou propriedade do destacamento. Uma importante regra de inferência na
tautologia [(p → q) ∧ ¬q] → ¬p:
p→q
¬q (3.3)
∴ ¬p
Esta regra é baseada na contra-positiva de uma implicação (Exemplo 1.3.5). Para entender esta
forma de argumento podemos verificar a tautologia [(p → q) ∧ ¬q] → ¬p ou analisar a Tabela 3.1:
se V (¬q) = V então V (q) = F; a única linha da Tabela 3.1 que possui V (p → q) = V e V (q) = F é
a última linha, de modo que devemos necessariamente ter neste caso V (p) = F, isto é, V (¬p) = V .
■ Exemplo 3.1.2 Suponha que as sentenças “Se fizer sol, então irei jogar futebol hoje” e “Está
fazendo sol hoje” são verdadeiras. Podemos denotar as proposições por p,q as “Está fazendo sol
hoje” e “Irei jogar futebol hoje”. As sentenças dadas podem então ser escritas na forma p → q e p.
Segue pela forma de argumentação (3.1) que V (q) = V , isto é, “Irei jogar futebol hoje” é verdadeira.
■
■ Exemplo 3.1.3 Suponha que as sentenças “Se fizer sol, então irei jogar futebol hoje” e “Não irei
jogar futebol hoje ” são verdadeiras. Podemos denotar as proposições por p,q as “Está fazendo sol
hoje” e “Irei jogar futebol hoje”. As sentenças dadas podem então ser escritas na forma p → q e ¬q.
Segue pela forma de argumentação (3.3) que V (¬p) = V , isto é, V (p) = F. Em outras palavras,
concluímos que “Está fazendo sol hoje” é uma proposição falsa. ■
Podemos concluir que “Se meu salário cair hoje, você vai comprar um tênis.” De fato, considere
as proposições p,q,r definidas por “Meu salário cai hoje”, “Eu te empresto R$500” e “Você vai
comprar um tênis.” Então as sentenças dadas podem ser escritas como p → q e q → r. Segue por
silogismo hipotético que p → r, isto é, “Se meu salário cair hoje, você vai comprar um tênis.” ■
■ Exemplo 3.1.5 Se as sentenças “y < 2 ou x > 1”, “y ≥ 2 ou z < 0” são verdadeiras, podemos
concluir que “x > 1 ou z < 0”.
De fato, considere as proposições p,q,r dadas por “x > 1 ou y < 2”, “y ≥ 2 ou z < 0” e “x > 1
ou z < 0”. As duas primeiras sentenças dadas podem ser escritas como p ∨ q e ¬p ∨ r. Segue pela
regra de inferência de resolução que q ∨ r, isto é, “x > 1 ou z < 0”. ■
Veremos agora como construir argumentos mais complexos usando as regras de inferência da
Tabela 3.3. Nos exemplos a seguir utilizaremos premissas e regras de inferência para obter novas
sentenças verdadeiras, que por sua vez serão combinadas com as premissas e regras de inferência
para gerar novas sentenças verdadeiras; este processo é conduzido até a veracidade da conclusão.
■ Exemplo 3.1.6 Mostre que as hipóteses
“Se você me mandar um e-mail, então eu terminarei o programa”
“Se você não me mandar um e-mail, então vou dormir cedo”
“Se eu dormir cedo, então acordarei me sentindo bem”
nos levam à conclusão “Se eu não terminar o programa, então acordarei me sentido bem.”
Sejam p,q,r,s as proposições “Você me manda um e-mail”, “Eu terminarei o programa”, “Vou
dormir cedo” e “Acordarei me sentindo bem”. Podemos escrever as hipóteses como p → q, ¬p → r
e r → s. Devemos provar que se essas sentenças são verdadeiras então ¬q → s é verdadeira; esta é
a conclusão.
Temos por hipótese que p → q é verdadeira, logo sua contra-positiva é verdadeira: ¬q → ¬p.
Veja agora que ¬q → ¬p e ¬p → r são verdadeiras: a primeira pelo argumento da contra-positiva,
a segunda por hipótese. Segue por silogismo hipotético que ¬q → r é verdadeira. Como r → s é
verdadeira por hipótese, a combinação dela e ¬q → r fornece, por silogismo hipotético, a conclusão:
¬q → s. Resumimos a nossa forma de argumento abaixo:
1. p→q Hipótese.
2. ¬q → ¬p Contra-positiva de 1.
3. ¬p → r Hipótese.
4. ¬q → r Silogismo hipotético usando 2 e 3.
5. r→s Hipótese.
6. ¬q → s Silogismo hipotético usando 4 e 5.
■
■ Exemplo 3.1.7 Mostre que as premissas “Todos os alunos da UTFPR são bons em matemática”
e “Ricardo é aluno da UTFPR” implicam a conclusão “Ricardo é bom em matemática”.
A premissa “Todos os alunos da UTFPR são bons em matemática” pode ser escrita como
∀x(P(x) → Q(x)), onde P(x) é a sentença “x é aluno da UTFPR” e Q(x) é a sentença “x é bom
em matemática”. As premissa “Ricardo é aluno da UTFPR” pode ser escrita como P(Ricardo) e
a conclusão “Ricardo é bom em matemática” pode, por sua vez, ser escrita como Q(Ricardo). O
argumento abaixo leva à veracidade da conclusão.
■ Exemplo 3.1.8 Suponha que a sentença “Para todo n inteiro, se n > 4 então n2 < 2n ” é verdadeira
e prove que 1002 < 2100 .
Sejam P(n), Q(n) as sentenças “n > 4” e n2 < 2n . Então a sentença “Para todo n inteiro, se
n > 4 então n2 < 2n ” pode ser escrita como “∀x(P(x) → Q(x)) com domínio dado pelo conjunto
dos números inteiros. Note que x = 100 é um elemento do domínio tal que P(100) é verdadeira
logo Q(100) também deve ser verdadeira, isto é, 1002 < 2100 .
■ Exemplo 3.1.9 Mostre que as premissas “Existe um aluno desta turma que não leu o livro” e
“Todos os alunos desta turma foram aprovados” implicam a conclusão “Alguém passou no exame
sem ter lido o livro”.
Sejam P(x), Q(x), R(x) as sentenças “x é desta turma”, “x não leu o livro” e “x foi aprovado”.
As premissas podem ser escritas como ∃x(P(x) ∧ Q(x)) e ∀x(P(x) → R(x)). A conclusão ∃x(Q(x) ∧
R(x)) é obtida a partir do argumento abaixo.
Textos matemáticos frequentemente fazem uso de certos termos cujo significado explicitamos
aqui:
• teorema: sentença matemática que se pode demonstrar que é verdadeira;
• demonstração: argumento que prova que um teorema é verdadeiro;
• proposição: um teorema com grau de importância menor;
• lema: um teorema que é utilizado na demonstração de outro teorema mas que não tem grande
relevância por si só;
• corolário: teorema que é demonstrado de maneira imediata a partir de um outro teorema;
• conjectura: sentença que suspeita-se que é verdadeira mas para a qual nenhuma demonstração
é conhecida;
• axiomas: sentenças que supomos que são verdadeiras e a partir das quais construímos
demonstrações e teoremas2
Demonstração direta.
Note que uma implicação p → q (Tabelas 1.8 e 3.1) é falsa apenas no caso em que V (p) = V e
V (q) = F; em todos os outros casos a implicação é verdadeira. Podemos demonstrar que p → q
é sempre verdadeira da seguinte maneira: supomos que p é verdadeira e, utilizando regras de
inferência, premissas e outros teoremas, provamos que q é verdadeira. Dessa maneira provamos
que não é possível ter a única combinação que torna p → q falsa, logo a implicação é sempre
verdadeira. Esta técnica é chamada de demonstração direta.
Exibiremos alguns exemplos de demonstrações diretas utilizando a definição a seguir.
Definição 3.2.1 Seja n um número inteiro.
(i) Dizemos que n é um número par se n = 2k para algum número inteiro k.
(ii) Dizemos que n é um número ímpar se n = 2k + 1 para algum número inteiro k.
■ Exemplo 3.2.2 Forneça uma demonstração do teorema “Se n é um número inteiro par então n2 é
par”.
Podemos escrever o teorema acima na forma ∀n(P(n) → Q(n)) com domínio dos números
inteiros, onde P(n) e Q(n) representam respectivamente as sentenças “n é par” e “n2 é par”. Como
mencionado acima, fazemos uso da instanciação universal: seja n0 um número inteiro genérico.
Devemos provar que P(n0 ) → Q(n0 ): isto será feito pela técnica de demonstração direta, isto é,
vamos supor que P(n0 ) é verdadeira e vamos provar que Q(n0 ) é verdadeira.
2 Na Geometria Euclideana Plana a sentença “dados dois pontos A,B no plano existe uma única reta que contém A e
Suponha que P(n0 ) é verdadeira, isto é, suponha que n0 é um número par. Segue da definição
de número par (Definição 3.2.1) que n0 = 2k0 para algum inteiro k0 . Segue que
onde 2k02 é um inteiro. Escrevendo k1 = 2k02 , temos que n0 = 2k1 onde k1 é um número inteiro;
segue novamente da definição de número par que n0 é par.
Provamos assim que P(n0 ) → Q(n0 ) é verdadeira para um elemento genérico n0 do domínio.
Segue da generalização universal que ∀n(P(n) → Q(n)) é verdadeira, como gostaríamos. ■
Exercício 3.2.3 Forneça uma demonstração do teorema “Se n é um número inteiro ímpar então
n2 é ímpar”. ■
Exercício 3.2.5 Forneça uma demonstração do teorema “Se m,n são inteiros pares então m + n
é par”. ■
onde 3k0 + 1 é um número inteiro. Escrevendo k1 = 3k0 + 1 temos que 3n0 + 2 = 2k1 , logo, pela
definição de número par, temos que 3n0 + 2 é um número par. Segue que 3n0 + 2 não é ímpar, isto
é, ¬P(n0 ) é verdadeira.
Provamos que ¬Q(n0 ) → ¬P(n0 ) é uma sentença verdadeira, logo P(n0 ) → Q(n0 ) é verdadeira.
Como n0 é um elemento genérico do domínio, segue por generalização universal que ∀n(P(n) →
Q(n)) é verdadeira. ■
26 Capítulo 3. Regras de Inferência e Demonstrações
Exercício 3.2.7 Forneça uma demonstração para o teorema a seguir: “Se n = ab, onde a,b,n
√ √
são números reais positivos, então a ≤ n ou b ≤ n”. ■
√ a 2 a2
( 2)2 = , isto é, 2= .
b b2
Multiplicando ambos os lados desta igualdade por b2 obtemos a equação a2 = 2b2 . Isto prova
que a2 é par. É possível provar que se a2 é par então a é par4 , isto é, a = 2k para algum inteiro k.
Substituindo a = 2k na equação a2 = 2b2 obtemos
Isto prova que b2 é par e novamente, pelo mesmo argumento, concluímos que b é par. Como a e b
são pares, segue que a e b tem um
√ fator comum (fator 2). √
Observe que ao supor que 2 é racional (¬p verdadeira) escrevemos 2 = a/b onde a,b
não possuem fator comum. Seja r a proposição “a,b não possuem fator comum”. Através de
implicações lógicas provamos que a,b possuem o fator comum 2, isto é, provamos que ¬r é
verdadeira. Ao provar que ¬p → (r ∧ ¬r) é verdadeira, observado que o lado direito
√ desta aplicação
é necessariamente falso, provamos que ¬p deve ser falso, isto é, p é verdadeiro: 2 é um número
irracional, como gostaríamos. ■
Demonstrações por contradição também podem ser utilizadas para provar uma condicional
p → q. Para tal, supomos que são verdadeiras a hipótese p e a negativa ¬q da conclusão e provamos
que p ∧ ¬q resulta em uma contradição, isto é, (p ∧ ¬q) → F. Ao provar que esta implicação é
verdadeira provamos que p → q é verdadeira, pois são implicações equivalentes; veja o Teorema
1.5.3.
3 Basta
dividir sucessivamente o numerador e o denominador por fatores comuns até que eles não possuam mais
nenhum divisor comum.
4A demonstração deste teorema é deixada como exercício; ver Exercício 3.2.9.
3.2 Introdução a Demonstrações 27
Demonstração de equivalências.
Para demonstrar um teorema da forma p ↔ q, lido como “p se e somente se q”, usamos a equiva-
lência
p ↔ q ≡ (p → q) ∧ (q → p) .
Veja o Teorema 1.5.4. Mais precisamente, provamos que as implicações p → q e q → p são
verdadeiras. Segue assim que (p → q) ∧ (q → p) é verdadeira. Isto prova, pela equivalência acima,
que p ↔ q é verdadeira.
■ Exemplo 3.2.10 Prove o teorema “se n é um inteiro, então n é ímpar se e somente se n2 é ímpar”.
O teorema acima pode ser escrito como p ↔ q, onde p,q são as proposições “n é ímpar” e “n2
é ímpar”. Provaremos que as implicações p → q e q → p são verdadeiras.
Suponha que p é verdadeira, isto é, suponha que n é ímpar: n = 2k + 1 para algum inteiro k.
Então
n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1,
isto é, n2 = 2k1 + 1 onde k1 = 2k2 + 2k. Segue que n2 é ímpar, isto é, V (q) = V . Isto prova que
V (p → q) = V . A demonstração de V (q → p) = V pode ser feita pela técnica de contra-positiva:
basta provar que ¬p ↛= q. Isto já foi feito no Exemplo 3.2.2.
Como p → q e q → p são verdadeiras, segue que a equivalência p ↔ q é verdadeira, como
gostaríamos. ■
Exercício 3.2.13 Prove o teorema “se n é um número inteiro positivo e n ≤ 4, então (n + 1)2 ≥
3n ”. ■
Exercício 3.2.14 Dizemos que um inteiro n é uma potência perfeita se n = ma para algum
inteiro a > 1. Prove que os únicos inteiros consecutivos não excedendo 100 que são potências
perfeitas são 8 e 9. ■
Erros em demonstrações.
Discutimos aqui brevemente alguns erros que se observam frequentemente na construção de
demonstrações. Alguns se dão em erros de aritmética, como na “demonstração” do Exemplo 3.2.15.
■ Exemplo 3.2.15 “Teorema”. 2 = 1.
“Demonstração”. Sejam a,b números iguais. Então:
1. a=b Hipótese.
2. a2 = ab Multiplicando ambos os lados de 1 por a.
3. a2 − b2 = ab − b2 Subtraindo b2 de ambos os lados de 2.
4. (a − b)(a + b) = b(a − b) Fatorando ambos os lados de 3.
5. a+b = b Dividindo ambos os lados de 4 por a − b.
6. 2b = b Substituindo a por b em 5, pois a = b.
7. 2=1 Dividindo ambos os lados de 6 por b.
O problema da “demonstração” acima é que no Passo 4: como a = b, efetuar uma divisão por a − b
representa uma divisão por zero, o que não é uma operação matemática válida. ■
Outros problemas que podem surgir são erros em regras de inferência, chamados de falácias.
Veja o Exemplo 3.2.16.
■ Exemplo 3.2.16 “Teorema”. Se n2 é positivo então n é positivo.
“Demonstração”. Suponha que n2 é positivo. Sabemos do Exemplo 3.2.2 que a proposição a
seguir é verdadeira: se n é positivo então n2 é positivo. Segue que n é positivo.
Na “demonstração” acima é utilizado um resultado que está correto (se n é positivo então n2 é
positivo), no entanto ele não foi utilizado de maneira correta. O teorema “se n é positivo então n2 é
positivo” é da forma P(n) → Q(n) para todo n; não podemos concluir que P(n) é verdadeiro no
caso de Q(n) é verdadeiro, apenas o contrário. ■
II
Parte Dois
4 Conjuntos e Funções . . . . . . . . . . . . . . . . 31
4.1 Conjuntos
4.2 Operações de Conjuntos
4.3 Funções
4.4 Funções Compostas e Inversas
4.5 Funções de Hash
6 Indução e Recursividade . . . . . . . . . . . . 61
6.1 Indução Matemática
6.2 Recursividade
4. Conjuntos e Funções
4.1 Conjuntos
A noção de conjuntos é familiar à maioria dos alunos de um curso de graduação: uma coleção
não-ordenada de objetos. É importante destacar o aspecto não-ordenado desta definição. Os alunos
de uma turma de Matemática Discreta formam um conjunto. No entanto, quando nos referimos a
um conjunto não estamos colocando os alunos em alguma ordem específica; a pauta de uma turma
de Matemática Discreta, com os alunos organizados em uma certa ordem, forma uma sequência:
uma coleção ordenada de objetos.
Definição 4.1.1 Um conjunto A é uma coleção não-ordenada de objetos. Os objetos do conjunto
são chamados de elementos ou membros do conjunto. Dizemos que um elemento a do conjunto
A pertence ao conjunto A e escrevemos a ∈ A. Se um objeto x não é um elemento de A, dizemos
que x não pertence a A e escrevemos x ∈
/ A. Se o conjunto A é composto por 4 elementos a,b,c,d,
escrevemos A = {a,b,c,d}.
Considere o conjunto B de todos os números ímpares positivos menores que 50. Descrever
seus elementos como nos itens (i) e (ii) acima pode ser muito inconveniente, de modo que fazemos
uso de reticências para descrever que o padrão observado continua se repetindo. Por exemplo, o
conjunto B pode ser escrito como
Também utilizamos reticências para descrever conjuntos infinitos que seguem um determinado
padrão. Por exemplo: o conjunto P dos números inteiros positivos ímpares pode ser escrito como
P = {1, 3, 5, . . . }. Neste caso, as reticências não levam o padrão de números ímpares até um certo
32 Capítulo 4. Conjuntos e Funções
“limite”, como o número 49 do conjunto em (4.1); as reticências indicam que este padrão se estende
indefinidamente, indicando infinitos elementos no conjunto.
Podemos descrever um conjunto diretamente através da propriedade que seus elementos satisfa-
zem, como no seguinte exemplo: o conjunto B de todos os números ímpares positivos menores que
50 pode ser descrito como
Definição 4.1.5 Sejam A,B conjuntos. Dizemos que A e B são iguais se eles têm os mesmos
elementos. Em outras palavras: A e B são iguais se a seguinte afirmação é verdadeira: para todo
x temos x ∈ A se e somente se x ∈ B ou seja, ∀x(x ∈ A ↔ x ∈ B). Escrevemos nesse caso A = B.
Com alguma frequência definimos um conjunto como a coleção de objetos que possuem uma
certa propriedade, porém não há objetos que satisfazem essa propriedade. Como um exemplo, seja
A o conjunto de números reais tais que x2 = −1:
A = {x ∈ R | x2 = −1}.
Não existe um número real com essa propriedade, de modo que o conjunto A acima não possui
nenhum elemento. Tal conjunto é dito vazio.
Definição 4.1.7 Um conjunto A que não possui elementos é chamado de conjunto vazio ou
conjunto nulo. Escrevemos A = 0/ ou A = {}.
4.1 Conjuntos 33
Definição 4.1.8 Um conjunto que possui um único elemento é dito um conjunto unitário.
Definição 4.1.10 Sejam A,B conjuntos. Dizemos que A é subconjunto de B se todo elemento
de A é elemento de B:
∀x(x ∈ A → x ∈ B).
Escrevemos nesse caso A ⊆ B e dizemos que A está contido em B. Escrevemos também B ⊇ A e
dizemos que B contém A.
■ Exemplo 4.1.12 O conjunto dos números inteiros Z = {. . . , −2, − 1,0,1,2, . . . } não é um sub-
conjunto de N, pois nem todo elementos de Z é elemento de N, como o inteiro −1. Já o conjunto
dos números naturais é um subconjunto dos números inteiros: N ⊆ Z. ■
Demonstração. Para provar o item (i) devemos provar que ∀x(x ∈ 0/ → x ∈ A) é verdadeiro.
Segue da tabela-verdade de uma implicação (Tabela 1.8 ou 3.1) que a implicação p → q é sempre
verdadeira se V (p) = F. Como o conjunto vazio não possui elementos, x ∈ 0/ é sempre falso. Segue
que a implicação x ∈ 0/ → x ∈ A é verdadeira para todo x e, portanto, 0/ ⊆ A.
Para provar o item (ii) devemos provar que ∀x(x ∈ A → x ∈ A) é verdadeiro, o que é auto-
evidente: se x ∈ A (hipótese da implicação), então x ∈ A (conclusão); segue que a implicação é
verdadeira para todo x. Concluímos que A ⊆ A. ■
Obs 4.1.14 Seja A um conjunto qualquer. Temos sempre que 0/ ⊆ A, como no Teorema 4.1.13, mas
não necessariamente temos 0/ ∈ A: é importante observar a diferença entre a relação de pertinência
(de elemento em um conjunto) e a relação de estar contido (de um conjunto em outro).
Segue do Teorema 4.1.13 que se B ⊆ A, então B é um subconjunto de A que pode ser igual
ao próprio conjunto A ou não. Para indicar que B é um subconjunto estrito ou próprio de A,
escrevemos B ⊂ A. O símbolo “⊆” admite a igualdade dos conjuntos, assim como o símbolo ≤
indica uma desigualdade que admite também a igualdade1 .
O teorema a seguir fornece um caminho para provar que dois conjuntos A,B são iguais. Temos
A = B se e somente A ⊆ B e B ⊆ A. Em outras palavras, se A está contido em B e B está contido
em A, devemos ter A = B. As relações A ⊆ B e B ⊆ A podem ser reescritas através da Definição
4.1.10, como nos itens (iii) e (iv) do Teorema 4.1.15.
Teorema 4.1.15 Sejam A,B conjuntos. São equivalentes:
(i) A = B;
(ii) A ⊆ B e B ⊆ A;
1Alguns autores utilizam a notação B ⊂ A admitindo também a possibilidade B = A. Neste texto manteremos a
•1∈Ae1∈
/ B; • 3 ∈ A e 3 ∈ B;
•2∈
/Ae2∈
/ B; •5∈ / A e 5 ∈ B.
Definição 4.1.18 Seja A um conjunto. O conjunto das partes de A é definido como o conjunto
P(A) cujos elementos são os subconjuntos de A.
Observamos que o conjunto vazio está contido em qualquer conjunto A dado, logo 0/ é um
elemento de P(A) para todo conjunto A. Além disso, A ⊆ A para todo A, então A também é um
elemento de P(A).
■ Exemplo 4.1.19 Considere o conjunto A = {1,2}. O conjunto P(A) das partes de A possui os
seguintes elementos:
/ {1}, {2}, {1,2}.
0,
Escrevemos P(A) = {0,
/ {1}, {2}, {1,2}}, ou ainda, P(A) = {0,
/ {1}, {2}, A}. ■
4.1 Conjuntos 35
■ Exemplo 4.1.20 O conjunto vazio tem um conjunto de partes que merece um comentário
/ = {0}.
destacado. O único subconjunto do conjunto vazio 0/ é ele mesmo, logo P(0) / ■
São pares ordenados (1,2) e (3,1). Como são coleções ordenadas, (1,2) e (2,1) são pares
ordenados diferentes.
Definição 4.1.22 Sejam A,B conjuntos. O produto cartesiano de A,B é definido como o
conjunto A × B cujos elementos são pares ordenados (a,b) onde a ∈ A e B ∈ B:
A × B = {(a,b) | a ∈ A ∧ b ∈ B}.
A1 × · · · × An = {(a1 , a2 , . . . , an ) | a1 ∈ A1 ∧ · · · ∧ an ∈ An }.
A × B ×C = {(1,5, − 2), (2,5, − 2), (1,5, − 1), (2,5, − 1), (1,5,0), (2,5,0)}.
Note que B × A = {(5,1), (5,2)}; isto ilustra o fato que, de um modo geral, A × B e B × A são
conjuntos diferentes. ■
Conjuntos e quantificadores.
Vimos que, se P é um predicado, a notação ∀xP(x) com domínio R representa a sentença “para
todo número real x temos P(x)”, o que pode ser escrito como “para todo x ∈ R temos P(x)”. Esta
notação de conjuntos pode ser introduzida na notação do quantificador, explicitando qual o domínio
de discurso: ∀x ∈ R(P(x)). É possível a introdução de parênteses para manter a notação mais clara,
como (∀x ∈ R)(P(x)) ou (∀x ∈ R)P(x).
Exercício 4.1.26 Determine o conjunto verdade de cada uma das sentenças abaixo.
(i) P(x) definida como “|x| = x” com domínio dos números inteiros.
(ii) Q(x) definida como “ 1x = x” com domínio dos números reais.
■
A ∩ B = {x | x ∈ A ∧ x ∈ B}.
Se A ∩ B = 0,
/ dizemos que A e B são conjuntos disjuntos.
O Teorema 4.2.4 nos fornece uma maneira de encontrar o número de elementos (cardinal)
da união de conjuntos finitos. Note que, no caso dos conjuntos A = {1,2,3,4} e B = {3,4,5} do
4.2 Operações de Conjuntos 37
Exemplo 4.2.2 temos |A| + |B| = 4 + 3 = 7, porém |A ∪ B| = 5. Esta diferença ocorre pelo seguinte
fato: na soma |A| + |B| temos computados uma vez cada elemento de A e uma vez cada elementos
de B, e os elementos que pertencem a ambos conjuntos são computados duas vezes. O conjunto de
elementos em ambos conjuntos é A ∩ B e, ao subtrair |A ∩ B| de |A| + |B|, estamos descontando a
contagem extra que foi feita na expressão |A| + |B|.
Definição 4.2.5 Sejam A,B conjuntos. A diferença A − B é definida como o conjunto de pontos
que pertencem a A mas não pertencem a B:
A − B = {x | x ∈ A ∧ x ∈
/ B}.
Considere novamente os conjuntos B13 , B15 , B17 , B e P do início da seção. A diferença B − B13
representa o conjunto de todos os jogadores de categoria de base do clube (pertencem a B) que não
são jogadores da categoria sub-13 (não pertencem a B13 ).
■ Exemplo 4.2.6 Sejam A = {1,2,3,4,5} e B = {−1,0,1,2}. Então A − B = {3,4,5}. ■
A = U − A = {x | x ∈ U ∧ x ∈
/ A}.
Identidades de conjuntos.
Encontram-se listadas abaixo as mais importantes identidades envolvendo as operações de conjuntos
vistas nesta seção. A demonstração de algumas delas são deixadas como exercícios a seguir. Estes
exercícios ilustram estratégias para a demonstração de teoremas envolvendo conjuntos.
• Elementos neutros: A ∪ 0/ = A,
A ∩U = A.
• Elementos neutros: A ∪ 0/ = A,
A ∩U = A
• Dominação: A ∩ 0/ = 0, /
A ∪U = U
• Idempotência: A ∩ A = A,
A∪A = A
• Complementação: (A) = A
• Comutatividade: A ∪ B = B ∪ A,
A∩B = B∩A
• Associatividade: (A ∪ B) ∪C = A ∪ (B ∪C),
(A ∩ B) ∩C = A ∩ (B ∩C)
• Distributividade: A ∩ (B ∪C) = (A ∩ B) ∪ (A ∩C),
A ∪ (B ∩C) = (A ∪ B) ∩ (A ∪C)
• Leis de Morgan: A ∪ B = A ∩ B,
A∩B = A∪B
• Absorção: A ∪ (A ∩ B) = A,
A ∩ (A ∪ B) = A
• Complementares: A ∪ A = U,
A ∩ A = 0/
A união de conjuntos é definida, a princípio, como uma operação envolvendo dois conjuntos.
Porém, com a propriedade associativa podemos trabalhar com a união de três conjuntos diretamente:
A ∪ B ∪C = (A ∪ B) ∪C = A ∪ (B ∪C):
A ∪ B ∪C = {x | x ∈ A ∨ x ∈ B ∨ x ∈ C}.
A ∩ B ∩C = {x | x ∈ A ∧ x ∈ B ∧ x ∈ C}.
Podemos demonstrar uma identidade como a do Exercício 4.2.14 através de uma tabela de
pertinência. No caso da identidade A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), iniciamos a tabela com
uma coluna para cada um dos conjuntos A,B,C; nessas três primeiras colunas incluímos todas as
possibilidade de pertinência de um elemento em relação a A,B,C: pertence a todos os conjuntos,
pertence a nenhum, pertence apenas a A, pertence a A e B e não a C, etc; isto é feito representar
pertinência por 1 e não-pertinência por 0. Procedemos de maneira muito semelhante às tabelas-
verdade da Seção 1.3: acrescentamos colunas uma a uma, progredindo até os conjuntos A ∩ (B ∪C)
e (A ∩ B) ∪ (A ∩ C), concluindo o que deve ser preenchido em cada linha a partir das colunas
anteriores. Se duas colunas da tabela são iguais, então os respectivos conjuntos também são iguais.
Exercício 4.2.14 Use as Leis de De Morgan para provar a identidade A ∪ (B ∩C) = A ∩ (B ∩C)
. ■
4.3 Funções
O conceito de função surge naturalmente quando existe uma associação entre grandezas ou quanti-
dades. Por exemplo:
(i) a área de um círculo e seu raio;
(ii) o perímetro de um triângulo equilátero e o comprimento de seu lado;
(iii) o lucro de uma loja e o número de unidades vendidades de seus produtos;
(iv) o número de pessoas convidadas a um churrasco e a quantidade de carne comprada.
De um modo mais geral, associamos a cada elemento de um conjunto um elemento de outro
conjunto. Por exemplo, considere o conjunto A de alunos matriculados no primeiro período do
curso de Engenharia da Computação. Podemos associar a cada elemento de A um número que
representa a sua nota na primeira prova de Matemática Discreta. Neste caso estamos associando
a cada elemento (aluno) de A um número real no intervalo [0,10]. Como um segundo exemplo,
podemos associar a cada aluno da turma do primeiro período de Engenharia da Computação o seu
melhor amigo desta turma; neste caso estamos associando a cada elemento de A um elemento do
próprio conjunto A.
Definição 4.3.1 Sejam A,B conjuntos não-vazios. Uma função, mapeamento ou transformação
f de A para B é uma regra que associa, a cada elemento a de A, um único elemento b de B.
Escrevemos nesse caso f (a) = b e dizemos que b é a imagem de a. Representamos uma função
de A para B por f : A → B.
Funções podem ser representadas graficamente através de um diagrama como na Figura 4.7,
onde temos ilustrada a função do Exemplo 4.3.2. Ao representar uma função f : A → B, repre-
sentamos os elementos de A e B por pontos, onde os elementos de A ficam mais à esquerda que
os elementos de B. A associação f (a) = b é representada por uma seta ou flecha que conecta
o elemento a ao elemento b. Frequentemente delimitamos os elementos de A e B por formas
circulares, assim como nos Diagramas de Venn da Seção 4.1.
■ Exemplo 4.3.3 Funções podem ser expressadas de diferentes maneiras. No caso de funções
envolvendo conjuntos numéricos, como uma função real f : R → R, podemos para cada elemento
x definir f (x) através de uma expressão algébrica. Por exemplo, a função f : R → R definida por
f (x) = x2 + 1 é tal que
f (1) = 12 + 1 = 2,
f (−3) = (−3)2 + 1 = 10.
■
Definição 4.3.4 Sejam A,B conjuntos não-vazios e f : A → B uma função de A para B. Dizemos
que A é o domínio de f e B é o contra-domínio de f . A imagem de f é o conjunto das imagens
de todos os elementos de A e é escrita como Im f :
Im f = {b ∈ B : ∃a ∈ A(b = f (a))}.
■ Exemplo 4.3.5 Considere o conjunto X = {Aline, Bruno, Carlos, Patrícia} de alunos da turma
de violão iniciante de um conservatório de música. Estes alunos foram avaliados ao fim do primeiro
ano de estudos em uma apresentação e receberam um dos conceito Y = {A,B,C,D,E}. Considere a
função f : X → Y representada na Tabela 4.1, que indica que conceito cada aluno recebeu pela sua
apresentação. Veja também a Figura 4.8.
Aluno Conceito
Aline A
Bruno B
Carlos D
Patrícia C
Figura 4.8: Conceito recebido por cada Tabela 4.1: Conceito recebido por cada aluno
aluno da turma de violão iniciante. da turma de violão iniciante.
O domínio da função f é o conjunto de alunos X = {Aline, Bruno, Carlos, Patrícia} e seu
contra-domínio é o conjunto de conceitos Y = {A,B,C,D,E}. No entanto, nem todo conceito de Y
foi de fato atribuído a algum aluno: nenhum aluno obteve conceito E. A imagem de f é o conjunto
de conceitos que foram atribuídos a pelo menos um aluno: Im f = {A,B,C,D}. ■
f (x) = y ⇐⇒ x2 = y
42 Capítulo 4. Conjuntos e Funções
√ √
temos solução para x = y. Por exemplo: se y = 4, temos f (x) = 4 para x = 4 = 2. Segue que
Im f = [0, + ∞). ■
■ Exemplo 4.3.7 Considere o conjunto X = {Aline, Bruno, Carlos, Patrícia} do Exemplo 4.3.5 de
alunos da turma de violão iniciante de um conservatório de música. Os pares ordenados (Aline,
16), (Bruno, 14), (Carlos, 14) e (Patrícia, 15) definem a função g : X → N que associa a cada aluno
de X a sua idade. Temos
g(Aline) = 16,
g(Bruno) = 14,
g(Carlos) = 14,
g(Patrícia) = 15.
■
Definição 4.3.8 Uma função é dita injetora ou um para um se, para todos a,b ∈ Dom f ,
f (a) = f (b) implica em a = b. Em outras palavras, f é dita injetora se não há dois elementos
diferentes do domínio com a mesma imagem.
■ Exemplo 4.3.10 Considere novamente a função f : X → Y do Exemplo 4.3.5, que associa a cada
estudante x ∈ X o conceito y ∈ Y que ele(a) obteve em sua apresentação. Como não existem dois
alunos com o mesmo conceito, concluímos que esta função é injetora. ■
Definição 4.3.12 Uma função f : A → B é dita sobrejetora se para todo b ∈ B existe a ∈ A tal
que f (a) = b.
cada estudante x ∈ X o conceito y ∈ Y que ele(a) obteve em sua apresentação. Note que existe um
elemento do conjunto Y = {A,B,C,D,E} que não foi associado a nenhum elemento do domínio:
não existe um aluno x ∈ X que obteve conceito E. Segue que esta função não é sobrejetora. Veja a
Figura 4.8. ■
4.4 Funções Compostas e Inversas 43
f (x0 ) = x0 + 1 = y0 − 1 + 1 = y0 .
x g(x)
x f (x) 10 1
a 50 20 1
b 20 30 0
c 30 40 1
50 0
Tabela 4.2: Função f do Exemplo 4.4.3.
Tabela 4.3: Função g do Exemplo 4.4.3.
x
■ Exemplo 4.4.4 Considere as funções f : R → R e g : R → R definidas por f (x) = 2x e g(x) = .
2
Para x = 5 que (g ◦ f )(5) calculada da seguinte maneira: (g ◦ f )(5) = g( f (5)), onde f (5) = 2 · 5 =
10, logo
10
(g ◦ f )(5) = g( f (5)) = g(2 · 5) = g(10) = = 5.
2
A função composta f ◦ g pode ser calculada da mesma maneira: ( f ◦ g)(5) = f (g(5)), onde
g(5) = 52 ; portanto,
5 5
( f ◦ g)(5) = f (g(5)) = f = 2 · = 5.
2 2
Mais geralmente, para todo x ∈ R temos
2x x x
g( f (x)) = g(2x) = = x e f (g(x)) = f = 2 · = x.
2 2 2
4.4 Funções Compostas e Inversas 45
2 √
■ Exemplo 4.4.5 Sejam y = f (x) = x e g(y) = y. Temos para x = 2 que
√
(g ◦ f )(2) = g( f (2)) = g(22 ) = g(4) = 4 = 2.
Para x = −2 temos
√
(g ◦ f )(−2) = g( f (−2)) = g((−2)2 ) = g(4) = 4 = 2.
■
g(b) = a, se f (a) = b,
Note que se uma função não é injetora, não é possível definir sua função inversa. Veja o caso
da função f (x) = x2 na Figura 4.12. Como x = 2 e x = −2 possuem a mesma imagem y = 4, não é
possível definir uma função inversa f −1 nesse caso, pois teríamos um elemento do domínio y = 4
com duas imagens x = ±2. Dizemos portanto que uma função f : A → B é inversível se ela é
injetora. Caso contrário dizemos que ela é não inversível.
Obs 4.4.7 Cuidado! A notação f −1 não indica a função 1/ f , mas sim a função inversa de f . Por
exemplo, no caso da função f (x) = 2x do Exemplo 4.4.4, temos
−1 x 1 1 1
f (x) = g(x) = e (x) = = .
2 f f (x) 2x
46 Capítulo 4. Conjuntos e Funções
Exercício 4.4.8 Determine se as funções abaixo são inversíveis ou não. Em caso positivo,
determine a função inversa.
(i) f : Z → Z definida por f (x) = x + 1.
(ii) g : R → R definida por g(x) = x + 1.
(iii) F : Z → Z definida por F(x) = sen x.
(iv) G : R → R definida por G(x) = x2 .
(v) H : R+ → R definida por H(x) = x2 , onde R+ = (0, + ∞).
■
2 SILVERMAN, Joseph H.; PIPHER, Jill; HOFFSTEIN, Jeffrey. An introduction to mathematical cryptography.
Exercício 4.5.1 Considere as funções de hash Hash1 e Hash2 que atribuem a cada CPF x
de aluno da turma atual de Matemática Discreta da Engenharia da Computação da UTFPR
Apucarana, respectivamente, o último dígito de seu CPF e o valor x mod 53.
(i) Determine o domínio de Hash1 e Hash2.
(ii) O que podemos afirmar sobre as imagens de Hash1 e Hash2?
(iii) Discuta a possibilidade de Hash1 e Hash2 serem sobrejetoras.
(iv) Discuta a possibilidade de Hash1 e Hash2 serem injetoras.
(v) Discuta a possibilidade de Hash1 e Hash2 serem bijetoras.
■
5. Teoria dos Números e Criptografia
Neste capítulo estudaremos mais a fundo propriedades de números inteiros. Os números inteiros
desempenham um papel central na Ciência da Computação em áreas como criptografia, geração de
números aleatórios, funções de hash, teoria de códigos, dentre outras.
Note que a divide b se a seguinte quantificação, com domínio dos números inteiros, é verdadeira:
∃k(b = ak).
■ Exemplo 5.1.2 Temos que 3 | 12, isto é, 3 divide 12, pois 12 = 3 · 4. ■
■ Exemplo 5.1.3 O inteiro 5 não é divisível por 2, pois não existe k ∈ Z tal que 5 = 2k. Esta
equação é verdadeira se e somente se k = 5/2, e este valor de k não é inteiro. Em outras palavras,
2 ∤ 5. ■
■ Exemplo 5.1.4 Todo número inteiro n é divisível por 1, isto é, 1 | n para todo inteiro n. De fato,
temos n = 1 · k para k = n ∈ Z. ■
Exercício 5.1.5 Sejam n,d números inteiros positivos. Quantos inteiros positivos x ≤ n são
divisíveis por d? ■
Demonstração. Fornecemos demonstrações diretas dos três itens. Para provar o item (i), considere
números inteiros a,b,c tais que a | b e a | c. Segue que b = ak1 e c = ak2 para k1 ,k2 ∈ Z. Segue que
logo b + c = aℓ, onde ℓ = k1 + k2 é um número inteiro. Isto prova, pela Definição 5.1.1, que
a | (b + c).
Suponha agora que a,b são números inteiros tais que a | b. Então b = ak para algum número
inteiro k. Se c é um número inteiro qualquer, temos que bc = akc = aℓ, onde ℓ = kc é um número
inteiro. Segue da Definição 5.1.1 que a | bc.
Provamos agora o item (iii). Sejam a,b,c números inteiros tais que a | b e b | c. Então b = ak1 e
c = bk2 para k1 , k2 ∈ Z. Temos assim que c = bk2 = ak1 k2 , logo c = aℓ, onde ℓ = k1 k2 é um número
inteiro. Segue da Definição 5.1.1 que a | c.
A demonstração do item (iv) segue rapidamente dos itens anteriores. Sejam a,b,c inteiros tais
que a | b e a | c. Então, pelo item (ii) acima, a | bm para todo m ∈ Z e a | cn para todo n ∈ Z. Segue
então pelo item (i) que a | (bm + cn), como gostaríamos. ■
A divisibilidade de números inteiros também pode ser abordada através da operação de divisão
com quociente e resto, assim como visto no Ensino Fundamental.
Teorema 5.1.7 Sejam a,d números inteiros, d > 0. Existem números inteiros únicos q,r ∈ Z
com 0 ≤ r < d tais que a = dq + r.
É importante destacar que os números q,r no Teorema 5.1.7 são únicos: se (q,r) e (q′ , r′ )
satisfazem a = dq + r e a = dq′ + r′ com 0 ≤ r, r′ < d, então (q,r) = (q′ , r′ ).
Definição 5.1.8 Sejam a,d números inteiros, d > 0 e sejam q,r ∈ Z tais que 0 ≤ r < d e
a = dq + r. Dizemos que q e r são respectivamente o quociente e o resto da divisão de a por d e
escrevemos
q = a div d e r = a mod d.
As equações de resto nos exemplos acima, como 2 = 14 mod 3, são particularmente importantes.
Em muitas situações temos como foco o resto da divisão de um número por outro. Por exemplo,
podemos determinar se d | a verificando se o resto r = a mod d é zero. Veja o exemplo a seguir.
■ Exemplo 5.1.13 Suponha que hoje é segunda-feira e queremos saber que dia da semana será
daqui a 15 dias. Podemos proceder da seguinte maneira: dividimos 15 por 7 (total de dias de
uma semana) e encontramos resto 1: ao “somar” um ao dia de segunda-feira, concluímos que será
terça-feira daqui a 15 dias.
Note que o mesmo resultado será obtido se perguntarmos que dia da semana será daqui a 8, 22
ou 50 dias, pois todos esses números possuem o mesmo resto na divisão por 7. ■
5.1 Divisibilidade e Aritmética Modular 51
Definição 5.1.14 Sejam a,b,m inteiros, m > 0. Dizemos que a é congruente a b módulo m se
m | (a − b). Escrevemos nesse caso a ≡ b (mod m).
A Definição 5.1.14 introduz uma notação para indicar inteiros que possuem o mesmo resto na
divisão por um inteiro dado. Veja o Teorema 5.1.15.
Teorema 5.1.15 Sejam a,b,m inteiros, m > 0. Então a ≡ b (mod m) se e somente se a mod m =
b mod m.
Demonstração. Sejam a,b,m inteiros, m > 0. Suponha que a ≡ b (mod m). Considere as divisões
inteiras a = mq1 + r1 e b = mq2 + r2 , onde q1 , q2 são inteiros, 0 ≤ r1 < m e 0 ≤ r2 < m. Então,
a − b = mq + r. (5.1)
Temos por hipótese que a ≡ b (mod m), isto é, m | (a − b). Temos então que a − b = mk para
algum inteiro k. Subtraindo esta Equação (5.1) obtemos 0 = mq + r − mk, ou seja,
Sabemos que 0 ≤ r1 < m, 0 ≤ r2 < m e r = r1 − r2 , logo −m < r < m. Segue da Equação (5.2) que
devemos ter k − q = 0 e r = 0. Como r = r1 − r2 , isto prova que r1 = r2 , isto é, a mod m = b mod m.
Suponha agora que a mod m = b mod m. Em outras palavras, temos a = mq1 + r1 e b =
mq2 + r2 , onde q1 , q2 são inteiros, 0 ≤ r1 < m e 0 ≤ r2 < m e r1 = r2 . Então,
Exercício 5.1.17 Calcule as reduções abaixo sabendo que a mod m deve ser um inteiro entre
0 e m − 1.
Demonstração. Sejam a,b ∈ Z e seja m um inteiro positivo. Suponha que a ≡ b (mod m). Segue
da Definição 5.1.14 que m | (a − b), isto é, a − b = km para algum k ∈ Z. Isto prova que a = b + km
para algum k ∈ Z.
Suponha agora que a = b + km para algum k ∈ Z. Então a − b = km onde k é um número
inteiro, logo k | (a − b). Segue da Definição 5.1.14 que a ≡ b (mod m). ■
Teorema 5.1.19 Sejam m um inteiro positivo e a,b inteiros tais que a ≡ b (mod m). Se c ≡ d
(mod m) então
(i) a + c ≡ b + d (mod m),
(ii) a − c ≡ b − d (mod m),
(iii) ac ≡ bd (mod m).
Corolário 5.1.21 Seja m um inteiro positivo. Sejam A,B números inteiros e sejam a = A
mod m e b = B mod m. Então
(i) A + B ≡ a + b (mod m),
(ii) A − B ≡ a − b (mod m),
(iii) AB ≡ ab (mod m).
Demonstração. Este é um caso particular do Teorema 5.1.19 no caso c = a mod m e d = b
mod m. ■
O Corolário 5.1.20 fornece uma alternativa para o cálculo de uma redução a mod m. Como
km ≡ 0 (mod m) para todo k ∈ Z, pois o resto da divisão de km por m é zero, temos que
a ± km ≡ a ± 0 (mod m), isto é, a ± km ≡ a (mod m).
Em outras palavras, os valores de a mod m e a ± km mod m são iguais. Este processo pode ser
repetido, somando ou subtraindo múltiplos de m repetidas vezes, até chegarmos a um valor entre 0
e m − 1.
■ Exemplo 5.1.22 Calcule as reduções abaixo.
5.2 Números Primos 53
Temos que 24 é múltiplo de 6, logo 24 ≡ 0 (mod 6). Então 25 mod 6 = 25 − 24 mod 6, isto
é, 25 mod 6 = 1 mod 6, onde 0 ≤ 1 < 6. Portanto 25 mod 6 = 1.
Analogamente, podemos calcular −6 mod 4 somando 4 (ou múltiplos de 4) repetidas vezes a
−6:
−6 mod 4 = −2 mod 4 = 2 mod 4,
logo −6 mod 4 = 2. ■
(i) n = 8 (iii) n = 11
(ii) n = 7 (iv) n = 12
Teorema 5.2.3 — Teorema Fundamental da Aritmética. Todo número inteiro positivo n > 1
pode ser escrito como um número primo ou como o produto de dois ou mais número primos.
Além disso, n é escrito como produto de números primos de maneira única a menos da ordem
em que os números primos no produto.
A expressão para n como produto de número primos no Teorema 5.2.3 é chamada de fatoração
de n em números primos ou simplesmente a fatoração de n.
■ Exemplo 5.2.4 Considere o número inteiro n = 12. Podemos fatorar 12 em números primos
como 12 = 2 · 2 · 3. Mais ainda, esta fatoração é única: podemos apenas trocar a ordem dos números
primos no lado direito da igualdade acima. ■
■ Exemplo 5.2.5 O número inteiro n = 13 é primo, então sua fatoração é escrita simplesmente
como 13 = 13. ■
12 = 22 · 31 ,
Teorema 5.2.6 Seja n um número inteiro. Se n é um número composto, então existe um fator
√
primo de n menor ou igual a n.
Demonstração. Seja n um número inteiro e suponha que n é composto. Então, pela Definição 5.2.1,
existe um divisor a de n diferente de 1 e n. Então n = ab para algum inteiro b e, como 1 < a < n,
√ √
temos 1 < b < n. Provamos agora que a ≤ n ou b ≤ n por contradição. Suponha que não é
√ √ √ √ √ √
verdade que a ≤ n ou b ≤ n, isto é, temos a > n e b > n. Então n = ab > n n = n, um
√ √
absurdo; isto prova que a ≤ n ou b ≤ n. Como a e b são divisores de n, isto prova que n possui
√
um divisor d ≤ n.
Se d é primo, então o teorema está provado. Caso contrário, d pode ser fatorado em números
√
primos: d = pe11 . . . pes s . Existe portanto um número primo pi tal que pi ≤ d ≤ n e pi | d. Temos
√
assim que pi ≤ n e, como pi | d e d | n, segue do item (iii) do Teorema 5.1.6 que pi | n. Isto prova
√
que n possui um fator primo pi ≤ n, como gostaríamos. ■
O Teorema 5.2.6 tem uma implicação prática importante: ao procurar por um fator primo de um
√
número n dado, podemos nos restringir aos números inteiros entre 2 e n; fora deste intervalo não
há divisor primo de n. Esta propriedade é enunciada no Corolário 5.2.7 abaixo, cuja demonstração
consiste simplesmente em observar que seu enunciado representa a contra-positiva do Teorema
5.2.6.
Corolário 5.2.7 Seja n um número inteiro. Se não existe um fator primo de n menor ou igual a
√
n, então n é um número primo.
■ Exemplo√
5.2.8 Prove
√que 97 é primo. √
√ Temos 81 = 9 e 100 = 10, logo 9 < 97 < 10. Os números primos menores ou iguais a
97 são 2,3,5 e 7, onde
• 97 mod 2 = 1, • 97 mod 5 = 2,
• 97 mod 3 = 1, • 97 mod 7 = 6.
Como 97 não tem resto zero na divisão por nenhum destes números primos, nenhum deles é
fator primo de 97. Segue do Corolário 5.2.7 que 97 é primo. ■
• 1 = 20 30 , • 2 = 21 30 ,
• 3 = 20 31 , • 6 = 21 31 ,
• 9 = 20 32 , • 18 = 21 32 .
5.3 Divisores e Múltiplos Comuns 55
Com alguma frequência encontramos pessoas se perguntando qual é o maior número primo de
todos. Esta pergunta é um absurdo, pois existem infinitos números primos: o menor dos números
primos é p = 2, entretanto eles formam uma lista infinita que não possui um maior elemento. O
que existe de fato é o maior número primo conhecido pelos homens: em Janeiro de 2018 o maior
primo conhecido tinha mais de 23 milhões de dígitos.
Demonstração. Fornecemos uma demonstração por contradição. Suponha que existe um número
finito de número primos e seja n o total de números primos. Escreva-os como p1 , p2 , . . . , pn e
considere o número
q = p1 . . . pn + 1.
Note que q ̸= pi para todo i = 1, . . . , n. Temos por hipótese que p1 , . . . , pn são todos os números
primos que existem, logo q é um número composto. Segue do Teorema Fundamental da Aritmética
que q é escrito como produto de números primos; em particular, existe um número primo pi , para
algum i = 1, . . . , n, tal que pi | q. Como pi | p1 . . . pn , segue do item (i) do Teorema 5.1.6 que
pi | (q − p1 . . . pn ), isto é, pi | 1. Isto é uma contradição, pois nenhum número primo divide 1.
Concluímos assim que a hipótese de que existe um número finito de números primos é falsa. ■
O máximo divisor comum de dois inteiros pode ser encontrado utilizando o método do Exemplo
5.2.9: fatoramos os inteiros em números primos e escolhemos, para cada númer primo, o menor
expoente que aparece na fatoração de um deles. Mais precisamente, se
então
min{e1 , f1 } min{es , fs }
mdc(a,b) = p1 · · · ps .
■ Exemplo 5.3.4 Sejam a = 50 e b = 30. Temos
50 = 21 52 e 30 = 21 31 51 .
Os números primos que constam nas fatorações acima são 2,3 e 5. O menor expoente que vemos
para 2 nas fatorações acima é 2, enquanto o primo 5 temos menor expoente 1. Como 3 não é um
56 Capítulo 5. Teoria dos Números e Criptografia
50 = 21 30 52 e 30 = 21 31 51 ,
pois 30 = 1. Segue que o menor expoente para 3 nas fatorações acima é 0. O máximo divisor
comum de 50 e 30 é portanto mdc(50,30) = 21 30 51 = 10. ■
É possível que o maior divisor comum de dois números inteiros seja d = 1: se a = 9 e b = 25,
então os divisores de a = 9 são 1,3,9 e os divisores de b = 50 são 1,2,5,10,25,50; como o único
divisor comum de a e b é 1, temos mdc(9,50) = 1. Dizemos nesse caso que a e b são relativamente
primos.
Definição 5.3.5 Sejam a,b números inteiros não-nulos. Se mdc(a,b) = 1 dizemos que a e b
são relativamente primos ou primos entre si.
Definição 5.3.6 Dizemos que números inteiros a1 , a2 , . . . , an são pares relativamente primos
ou primos entre si dois a dois se mdc(ai , a j ) = 1 para todo i, j tal que 1 ≤ i < j ≤ n.
O mínimo múltiplo comum de dois inteiros pode ser determinado como no Exemplo 5.3.4, mas
para o mmc escolhemos o maior expoente que aparece na fatoração de cada inteiro.
■ Exemplo 5.3.9 Sejam a = 50 e b = 30. Vimos no Exemplo 5.3.4
50 = 21 30 52 e 30 = 21 31 51 .
Os maiores expoentes para os números primos 2,3 e 5 nas fatorações acima são respectivamente
1,1 e 2. Segue que mmc(50,30) = 21 31 52 = 150. ■
Teorema 5.3.10 Sejam a,b números inteiros positivos. Então ab = mdc(a,b) · mmc(a,b).
5.4 Criptografia RSA 57
N = pq
A chave pública de Bob é o par (N,e). Para decriptar as mensagens que receberá, Bob deve calcular
o inverso d do número e módulo (p − 1)(q − 1), isto é, Bob deve encontrar o número d que satisfaz
Encriptação RSA.
Suponha que Alice deseja enviar a Bob uma mensagem m, que supomos já ser um inteiro m
satisfazendo 1 ≤ m < N. Alice tem acesso à chave pública (N,e) de Bob e utiliza-a para calcular a
mensagem cifracada c:
c = me (mod N).
1 SILVERMAN, Joseph H.; PIPHER, Jill; HOFFSTEIN, Jeffrey. An introduction to mathematical cryptography.
Decriptação RSA.
Ao receber a mensagem cifrada c de Alice, Bob utiliza sua chave privada (N,d) para calcular
cd = (mod N) = m.
A chave pública de Bob é neste caso (N,e) = (2430101, 948047). A chave privada de Bob é obtida
ao resolver a equação
É possível provar que d = 1051235 satisfaz a equação acima e a chave privada de Bob é portanto
(N,d) = (2430101, 1051235).
Se Alice possui uma mensagem m = 1070777 para enviar a Bob, a mensagem é encriptada por
meio da exponenciação
Ao receber a mensagem encriptada c = 1473513, Bob recupera a mensagem original por meio da
operação
como gostaríamos. ■
■ Exemplo 5.4.2 Suponha que Bob escolheu os primos p = 3 e q = 5 para a criação de suas chaves
RSA, além do expoente de encriptação e = 2. Alice deseja enviar a mensagem m = 12 para Bob.
(i) Determine se as escolhas de Bob atendem os critérios estabelecidos nesta seção.
(ii) Caso as escolhas de Bob tenham sido adequadas, determine a chave pública e a chave privada
de Bob.
(iii) Caso as escolhas de Bob tenham sido adequadas, determine a chave pública e a chave privada
de Bob.
(ii) Caso as escolhas de Bob tenham sido adequadas, determine a chave pública e a chave privada
de Bob.
Temos N = pq = 15 neste caso. Devemos ter mdc(e, (p − 1)(q − 1)) = 1, isto é, mdc(2, 2 · 4) = 1,
o que é falso. Segue que as escolhas de Bob não estão adequadas ao sistema criptográfico RSA. ■
■ Exemplo 5.4.3 Suponha que Bob escolheu os primos p = 3 e q = 11 para a criação de suas
chaves RSA, além do expoente de encriptação e = 3. Alice deseja enviar a mensagem m = 19 para
Bob.
(i) Determine se as escolhas de Bob atendem os critérios estabelecidos nesta seção.
(ii) Caso as escolhas de Bob tenham sido adequadas, determine a chave pública e a chave privada
de Bob.
(iii) Caso as escolhas de Bob tenham sido adequadas, determine a chave pública e a chave privada
de Bob.
5.4 Criptografia RSA 59
(ii) Caso as escolhas de Bob tenham sido adequadas, determine a chave pública e a chave privada
de Bob.
Temos N = pq = 33 neste caso. Devemos ter mdc(e, (p − 1)(q − 1)) = 1, e de fato temos mdc(3, 2 ·
10) = 1. A chave pública de Bob é (N,e) = (33,3) e a chave privada de Bob é (N,d), onde d é a
solução da equação
Temos que o número d = 7 satisfaz a equação acima, logo a chave privada de Bob é (N,d) = (33,7).
A mensagem m = 11 é encriptada como
como gostaríamos. ■
possível encontrar o valor d que resolve a equação de = 1 (mod (p − 1)(q − 1))? Caso exista, ele
é único? Tais perguntas impulsionam o desenvolvimento da Teoria dos Números e de seus aspectos
computacionais.
2 National Institute of Standards and Technology. FIPS 186-5 Digital Signature Standard (DSS), 2023. Disponível em
P(1)
P(1) → P(2)
P(2) → P(3)
.. (6.1)
.
P(n − 1) → P(n)
∴ P(n)
■ Exemplo 6.1.1 Forneça uma demonstração por indução matemática do teorema a seguir: se n é
62 Capítulo 6. Indução e Recursividade
(k + 1)(k + 1 + 1) (k + 1)(k + 2) k2 + 3k + 2
1 + 2 + 3 + · · · + k + (k + 1) = = = . (6.4)
2 2 2
Para demonstrar esta igualdade, vamos desenvolver a expressão 1 + 2 + 3 + · · · + k + k + 1, partindo
2
da hipótese (6.3), e concluir que ela é igual a k +3k+2
2 . Utilizando expressão para 1 + 2 + 3 + · · · + k
que a hipótese (6.3) nos dá obtemos
k(k + 1)
1 + 2 + 3 + · · · + k + (k + 1) = + k + 1.
2
Somando as frações no lado direito da igualdade acima obtemos
k(k + 1) + 2(k + 1)
1 + 2 + 3 + · · · + k + (k + 1) = .
2
Fazendo a distributiva obtemos
k2 + k + 2k + 2 k2 + 3k + 2
1 + 2 + 3 + · · · + k + (k + 1) = = .
2 2
Isto conclui o passo de indução: provamos que (6.4) é verdadeira a partir de (6.3); em outras
palavras, provamos que a implicação P(k) → P(k + 1) é verdadeira. Segue por indução matemática
que P(n) é verdadeira para todo inteiro positivo n. ■
1 + 3 + · · · + (2n − 1) = n2 . (6.5)
O teorema acima pode ser escrito como ∀nP(n), onde P(n) é a Equação (6.5) e o domínio de
discurso é o conjunto dos números inteiros positivos. Fornecemos uma demonstração por indução
matemática.
Passo base. Verificamos a Equação (6.5) para n = 1: temos nesse caso que 2n − 1 = 2 · 1 − 1 = 1,
logo
1 = 12 = 1, ok.
Passo de indução. Suponha que a Equação (6.5) é verdadeira para um inteiro positivo k
genérico:
1 + 3 + · · · + (2k − 1) = k2 .
6.1 Indução Matemática 63
Devemos agora provar, partindo desta hipótese, que a Equação (6.5) é verdadeira para n = k + 1:
Mais uma vez manipularemos o lado esquerdo da equação acima e chegaremos à expressão do lado
direito. A hipótese de indução afirma que 1 + 3 + · · · + (2k − 1) = k2 , logo
Segue que
1 + 2 + · · · + (2k − 1) + (2(k + 1) − 1) = k2 + 2k + 2 − 1 = k2 + 2k + 1.
Note que a expressão k2 + 2k + 1 coincide com o produto notável a2 + 2ab + b2 = (a + b)2 para
a = k e b = 1. Concluímos assim que
■ Exemplo 6.1.3 Sejam a,r números reais, r ̸= 1. Prove a fórmula para a soma de um número
finito dos termos de uma progressão geométrica: para n ≥ 0 temos
n
rn+1 − 1
∑ ar j = a + ar + ar2 + · · · + arn = a r−1
. (6.6)
j=0
Fornecemos novamente uma demonstração por indução matemática. Neste caso podemos
escrever o teorema como ∀nP(n) com domínio N = {0,1,2, . . . } e P(n) a equação do enunciado.
Passo base. O passo base consiste da verificação do teorema para o menor inteiro n do domínio
de ∀nP(n), isto é, n = 0: temos ∑0j=0 ark = ar0 = a e
r0+1 − 1 r−1
a =a = a, ok.
r−1 r−1
Passo de indução. Suponha que a Equação (6.6) é verdadeira para um inteiro k ≥ 0 qualquer, isto é,
k
rk+1 − 1
∑ ar j = 1 + ar + ar2 + · · · + ark = a r−1
.
j=0
Devemos provar que a Equação (6.6) é verdadeira para n = k +1. Para tal, consideramos a expressão
k+1
∑ ar j = 1 + ar + ar2 + · · · + ark + ark+1 .
j=0
k+1
Temos da hipótese que 1 + ar + ar2 + · · · + ark = a r r−1−1 , então
rk+1 − 1
1 + ar + ar2 + · · · + ark + ark+1 = a + ark+1 .
r−1
Colocando o número a em evidência obtemos
rk+1 − 1
2 k k+1 k+1
1 + ar + ar + · · · + ar + ar =a +r ,
r−1
64 Capítulo 6. Indução e Recursividade
Concluímos assim que k + 1 < 2k+1 , o que conclui o passo de indução. A demonstração do teorema
segue por indução matemática. ■
■ Exemplo 6.1.5 Prove que n3 − n é divisível por 3 para todo inteiro positivo n.
O teorema pode ser escrito como ∀nP(n), onde o domínio de discurso é {1,2,3, . . . } e P(n) é a
declaração 3 | (n3 − n).
Passo base. Para n = 1 temos n3 − n = 13 − 1 = 0. De fato 3 | 0.
Passo de indução. Suponha que 3 | (k3 − k) para um inteiro k positivo. Note que
No passo de indução devemos usar a hipótese de indução para provar que P(k + 1) é verdadeira.
Neste caso a hipótese de indução é 3 | (k3 − k). Destacamos a expressão k3 − k no lado direito da
equação acima para podermos utilizar a hipótese de indução:
Indução completa.
A indução completa representa um método para demonstrações de teoremas que é muito semelhante
à indução matemática vista acima. A indução completa é utilizada em teoremas do mesmo tipo,
como ∀nP(n) onde o domínio de discurso é um conjunto como {1,2,3, . . . }. Consideramos dois
passos, como na indução matemática.
6.2 Recursividade 65
(i) Passo base. Demonstrar que P(n) é verdadeira para o menor inteiro do conjunto em questão;
no exemplo aqui considerado devemos demonstrar que P(1) é verdadeira.
(ii) Passo de indução. Supomos que P(1), . . . , P(k) é verdadeira para algum inteiro k ≥ 1 e
provamos, partindo desta hipótese, que P(k + 1) é verdadeira.
A diferença entre a indução matemática e a indução completa se encontra no passo de indução:
enquanto na indução matemática supomos que P(n) é verdadeira para algum inteiro n = k, na
indução completa supomos que P(n) é verdadeira para todos os inteiros n ≤ k no domínio.
■ Exemplo 6.1.6 Mostre que se n é um inteiro maior que 1 então ou n é primo ou n se escreve
como o produto de números primos.
O teorema acima pode ser escrito como ∀nP(n), onde P(n) é a declaração “n se escreve como
o produto de números primos” e o domínio de discurso é o conjunto {2,3,4, . . . }. Fornecemos uma
demonstração utilizando o método de indução completa.
Passo base. O menor inteiro do conjunto em questão é n = 2. A declaração P(2) é dada por
“2 se escreve como produto de números primos”; esta declaração é verdadeira (para apenas um
número primo).
Passo de indução. Suponha que P(n) é verdadeira para n ≤ k, onde k é um inteiro qualquer
maior que 1. Devemos provar que k + 1 se escreve como o produto de números primos. Temos dois
casos: k + 1 é número primo e k + 1 é número composto.
(i) Se k + 1 é primo, então k + 1 é escrito como produto de números primos; no caso, de apenas
um número primo, o próprio k + 1.
(ii) Se k + 1 é um número composto, então k + 1 possui um divisor diferente de 1 e k + 1, isto
é, k + 1 = ab com 1 < a,b < k + 1. Como a,b ≤ k, segue da hipótese de indução que a e b
se escrevem cada um como o produto de números primos. Temos portanto que k + 1 = ab
também é produto de números primos: os primos na fatoração de k + 1 são aqueles das
fatorações de a e b. Isto conclui a demonstração do passo de indução.
A demonstração do teorema segue por indução completa. ■
6.2 Recursividade
A definição de um objeto é dita recursiva se ela utiliza o próprio objeto em sua definição. Por
exemplo, a sequência definida por an = 3n para n ≥ 0 é dada por
a0 = 1, a1 = 3, a2 = 9, a3 = 27, . . . .
a0 = 1
a1 = 3a0 = 3 · 1 = 3,
a2 = 3a1 = 3 · 3 = 9,
a3 = 3a2 = 3 · 9 = 27,
..
.
Note que a sequência an acima consiste simplesmente de uma nomenclatura e uma notação
diferente para uma função f definida no conjunto dos números naturais N = {0,1,2, . . . }. Mais
precisamente, uma função f definida recursivamente em um subconjunto do conjunto dos naturais
é definida através de dois passos, semelhantes àqueles de uma demonstração por indução.
(i) Passo base, onde se especifica o valor da função f no menor inteiro de seu domínio.
(i) Passo recursivo, onde se especifica o valor da função f no menor inteiro de seu domínio.
Dizemos que uma definição feita dessa maneira é uma definição indutiva ou uma recursividade.
66 Capítulo 6. Indução e Recursividade
Esta função pode ser definida de maneira recursiva: o valor de f (n) para um inteiro positivo n
é dado pelo valor anterior de f somado com 5, isto é, f (n) = f (n − 1) + 5. Este é chamado o
passo recursivo, que define o valor de f para n ≥ 1. O valor de f (0) não pode ser feito desta
maneira pois a função não está definida para n = −1; a definição f (0) = 2 deve ser feita de maneira
isolada, configurando o passo base. A definição de f por recursividade é dada por f (0) = 2 e
f (n) = f (n − 1) + 5, para n ≥ 1. ■
a0 = 0, a1 = 2, a2 = 4, a3 = 6, a4 = 6.
Uma definição recursiva escreve an em função de an−1 e, se necessário, de outros termos anteriores
a an−1 . A partir de n = 1 temos que an é igual a an−1 mais dois, e o primeiro termo da sequência é
a0 = 0. Temos assim que a0 = 2 e an = an−1 + 2, para n ≥ 1. ■
■ Exemplo 6.2.3 Seja αn , n ≥ 0, uma sequência qualquer de números reais. Dê uma definição
recursiva para An = ∑nk=0 αk , n ≥ 0.
Lembramos que, para n ≥ 0,
n
An = ∑ αk = α0 + α1 + α2 + · · · αn .
k=0
Uma definição recursiva para An escreve An em função dos termos anteriores da sequência: An−1 e,
se necessário, An−2 , An−3 , etc. Note que
An−1 = α0 + α1 + α2 + · · · + αn−1 ,
An = α0 + α1 + α2 + · · · + αn−1 + αn ,
Sequência de Fibonacci.
Possivelmente a definição recursiva mais famosa da matemática é a da sequência de Fibonacci,
definida da seguinte maneira:
f0 = 0, f1 = 1, f2 = 1, f3 = 2, f4 = 3, f5 = 5, f6 = 8, f7 = 13, f8 = 21, . . . .
6.2 Recursividade 67
Esta sequência é conhecida√pela razão áurea: a razão entre os elementos fn+1 e fn se aproxima
cada vez mais de ϕ = (1 + 5)/2 ≈ 1.61803. Confira abaixo:
f4
= 1.5,
f3
f5
= 1.666 . . . ,
f4
f6
= 1.625,
f5
f7
= 1.61538,
f6
..
.
fn = 3 fn−2 − fn−4 .
O teorema acima pode ser escrito como ∀nP(n), onde P(n) é a equação fn = 3 fn−2 − fn−4 e
o domínio de discurso para o teorema é o conjunto {5,6,7, . . . }. Provamos este teorema usando a
técnica de indução completa vista na Seção 6.1.
Passo base. Os primeiros valores da sequência de Fibonacci são
f0 = 0, f1 = 1, f2 = 1, f3 = 2, f4 = 3, f5 = 5, f6 = 8, f7 = 13, f8 = 21.
Assim podemos verificar o valor-verdade de P(n) para os primeiros valores de n em questão. Para
n = 5 e n = 6 temos que P(n) é dada por
P(5) : f5 = 3 f3 − f1 , isto é, 5 = 3 · 2 − 1,
P(6) : f6 = 3 f4 − f2 , isto é, 8 = 3 · 3 − 1,
ou seja, P(5) e P(6) são verdadeiras.
Passo de indução completa. Suponha que, para algum k ≥ 6, P(n) é verdadeira para n =
1,2, . . . ,k. Devemos provar que P(k + 1) é verdadeira, isto é, devemos provar que
fk+1 = fk + fk−1 .
Como, por hipótese de indução, P(k) e P(k − 1) são verdadeiras, temos que fk = 3 fk−2 − fk−4 e
fk−1 = 3 fk−3 − fk−5 . Substituindo essas expressões para fk e fk−1 na equação acima obtemos
fk+1 = 3 fk−2 − fk−4 + 3 fk−3 − fk−5 , isto é, fk+1 = 3( fk−2 + fk−3 ) − ( fk−4 + fk−5 ).
Utilizamos novamente a definição da sequência de Fibonacci: temos fk−1 = fk−2 + fk−3 e fk−3 =
fk−4 + fk−5 , logo
fk+1 = 3 fk−1 − fk−3 .
Isto conclui o passo de indução completa e a demonstração do teorema. ■
68 Capítulo 6. Indução e Recursividade
Muitos objetos e conjuntos importantes são definidos recursivamente. Estas definições são
semelhantes às definições recursivas de sequências: a sequência an , n ≥ 0, definida por a0 = 0 e
an = 2an−1 , n ≥ 1, é definida em duas etapas: o passo base a0 = 0, e o passo recursivo, que define
an = 2an−1 para n ≥ 1. Veja os Exemplos 6.2.6 e ?? a seguir.
■ Exemplo 6.2.6 Em uma universidade dois alunos, João e José, muito amigos um do outro,
resolvem dar uma festa. Eles decidem que eles próprios, João e José, estão convidados e, além disso,
está convidado qualquer aluno da universidade que faz alguma disciplina com algum convidado da
festa. Podemos descrever a ideia de João e José como uma definição recursiva: o conjunto A de
alunos convidados à festa é definido da seguinte maneira.
Passo base: João, José ∈ A.
Passo recursivo: se x ∈ A e y cursa uma disciplina com x, então y ∈ A. ■
Veremos agora brevemente o que são grafos. Eles serão estudados mais adiante neste texto,
mas os introduzimos aqui para ilustrarmos definições recursivas.
Definição 6.2.8 Um grafo G é um conjunto não-vazio V de vértices e um conjunto (possi-
velmente vazio) E de arestas que ligam vértices: uma aresta e ∈ E é da forma (a,b), onde
a,b ∈ V .
Os vértices de um grafo são ilustrado como pontos ou pequenos círculos; as arestas são
ilustradas como segmentos ou arcos ligando os vértices correspondentes. Como um exemplo,
considere o grafo G = (V,E) onde V = {1,2,3} e E = {(1,2), (1,3)}. O grafo G consiste de três
vértices 1,2,3 e de duas arestas: uma ligando 1 e 2 e outra ligando 1 e 3. Veja a Figura 6.1.
Definição 6.2.9 O conjunto de árvores com raiz ou árvores enraizadas é um conjunto de grafos
definido recursivamente da seguinte maneira.
Passo base. Um grafo com um único vértice r é uma árvore enraizada com raiz r.
Passo recursivo. Suponha que T1 , . . . , Tn são árvores enraizadas disjuntas com raízes
r1 , . . . , rn , respectivamente. Seja r um vértice que não pertence a nenhuma das árvores T1 , . . . , Tn .
Então o grafo obtido pelo vértice r e as árvores T1 , . . . , Tn com arestas ligando r a cada um dos
vértices r1 , . . . , rn é uma árvore enraizada com raiz r.
A Figura 6.2 mostra alguns elementos do conjunto de árvores enraizadas. Algumas restrições
podem ser impostas à construção de árvores, por exemplo a restrição n = 2 na Definição 6.2.9:
definimos assim uma classe de árvores em que um vértice ou não tem nenhum descendente ou
tem exatamente dois; essas são chamadas árvores binárias completas. Veja a Definição 6.2.10 e a
Figura 6.3.
6.2 Recursividade 69
Definição 6.2.11 A altura h(T ) de uma árvore binária completa T é definida recursivamente
da seguinte maneira.
Passo base. Uma árvore T com apenas um vértice tem altura h(T ) = 0.
Passo recursivo. Se T é uma árvore binária completa construída recursivamente a partir de
árvores T1 e T2 , então h(T ) = 1 + max{h(T1 ), h(T2 )}.
Podemos computar a altura das árvores binárias completas na Figura 6.3 através da Definição
70 Capítulo 6. Indução e Recursividade
6.2.11.
• A árvore T na primeira linha é aquela do passo base, portanto h(T ) = 0.
• A árvore T na segunda linha é construída a partir de árvores T1 , T2 , onde T1 , T2 são árvores
do passo base. Logo h(T1 ) = h(T2 ) = 0 e h(T ) = 1 + max{0,0} = 1 + 0 = 0.
• A árvore T na terceira linha é construída a partir de árvores T1 , T2 , onde h(T1 ) = 1 e h(T2 ) = 0.
Segue que h(T ) = 1 + max{1,0} = 1 + 1 = 2. Um argumento análogo mostra que as demais
árvores da Figura 6.3 têm altura 2.
Indução estrutural.
Considere um conjunto S definido recursivamente, como aquele do Exemplo 6.2.7: definimos que
3 ∈ S e, se x,y ∈ S, então x + y ∈ S. Podemos demonstrar um teorema da forma ∀xP(x) com domínio
S utilizando a construção recursiva do conjunto. Esta técnica é chamada de indução estrutural e
consiste de dois passos:
Passo base: provamos que P(x) é verdadeira para todo elemento x especificado no passo base
da definição de S.
Passo recursivo: provamos que, se y é um elemento de S construído a partir de elementos
x1 , x2 , . . . e P(x1 ), P(x2 ), . . . são verdadeiras, então P(y) é verdadeira.
A demonstração destes dois passos prova o teorema ∀xP(x) pelo seguinte argumento. Seja, para
n ≥ 0, Q(n) a afirmação de que P(x) é verdadeira para todo elemento x ∈ S construído com a
aplicação de n passos recursivos; o caso n = 0 corresponde ao passo base da definição de S. Os
dois passos acima correspondem à aplicação da indução matemática para o teorema ∀nQ(n).
■ Exemplo 6.2.12 Considere o conjunto S de números inteiros definido da seguinte maneira.
Passo base: 3 ∈ S.
Passo recursivo: se x,y ∈ S, então x + y ∈ S.
Prove que todos os elementos de S são múltiplos de 3.
O teorema acima é da forma ∀xP(x) com domínio dado pelo conjunto S e P(x) a declaração “x
6.2 Recursividade 71
z = x + y = 3k + 3ℓ = 3(k + ℓ),
■ Exemplo 6.2.13 Prove que, se T é uma árvore binária completa, então o número de vértices n(T )
Temos da hipótese de indução que n(T1 ) ≤ 2h(T1 )+1 − 1 e n(T2 ) ≤ 2h(T2 )+1 − 1, logo
n(T ) ≤ 2h(T1 )+1 − 1 + 2h(T2 )+1 − 1 + 1 = 2h(T1 )+1 + 2h(T2 )+1 − 1. (6.7)
Se a,b são números reais então a + b ≤ 2 max{a,b}. Aplicando este resultado com a = 2h(T1 )+1 e
b = 2h(T2 )+1 obtemos
7 Combinatória . . . . . . . . . . . . . . . . . . . . . . . 75
7.1 Combinatória Enumerativa
7.2 Princípio da cada dos pombos
8 Relações . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.1 Relações e suas Propriedades
8.2 Relações de Equivalências
9 Grafos e Árvores . . . . . . . . . . . . . . . . . . . . 91
9.1 Grafos
9.2 Terminologia Básica de Grafos
9.3 Tipos Especiais de Grafos
9.4 Representação de Grafos
9.5 Isomorfismo de Grafos
9.6 Conectividade de Grafos
9.7 Árvores
7. Combinatória
Suponha que uma decisão D possa ser dividida como a tomada de duas decisões D1 e D2
em sequência. Se há x maneiras de tomar a decisão D1 e y maneiras de tomar a decisão D2 ,
então existem xy maneiras de tomar a decisão D.
O princípio multiplicativo pode ser estendido para uma sequência de n decisões. Mais precisa-
mente, suponha que uma decisão D consiste da tomada de decisões D1 , D2 , . . . , Dn em sequência.
76 Capítulo 7. Combinatória
■ Exemplo 7.1.3 Uma universidade decidiu criar etiquetas de patrimônio para seus itens contendo
uma letra do alfabeto latino (26 letras) e dois números inteiros entre 0 e 9. Quantas etiquetas
diferentes podem ser fabricadas?
A criação da etiqueta pode ser descrita como uma sequência de três decisões: a escolha da letra,
com 26 possibilidades; a escolha do primeiro número, com 10 possibilidades; e a escolha do segundo
número, com 10 possibilidades. Segue que o número de etiquetas possíveis é 26 · 10 · 10 = 2600. ■
■ Exemplo 7.1.4 Quantas sequências de 8 bits de comprimento existem?
Cada sequência de 8 bits pode ser descrita pela decisão de cada um dos seus bits, o que
configura uma sequência de oito decisões com duas possibilidades cada uma. Logo temos 28 = 256
sequências de bits de comprimento 8. ■
Suponha que uma decisão D possa ser tomada de x formas diferentes em um conjunto D1
ou de y formas diferentes em um conjunto D2 , onde D1 e D2 são conjuntos com interseção
vazia. Então existem x + y maneiras de tomar a decisão D.
O princípio aditivo da contagem pode ser visto como a contagem dos elementos de uma união
de conjuntos. O número de formas possíveis de tomar a decisão D é dado por |D1 ∪ D2 | = x + y.
■ Exemplo 7.1.7 Suponha que o Diretório Central de Estudantes (DCE) de uma universidade deva
escolher um aluno de Engenharia para integrar uma comissão. Sabendo que a universidade possui
cursos de Engenharia Ambiental e de Alimentos, e que esses cursos possuem respectivamente 242
e 290 alunos, determine quantas escolhas diferentes o DCE desta universidade pode fazer para este
aluno.
O aluno que deverá integrar a comissão deve ser escolhido dentre dois conjuntos: o conjunto de
alunos de Engenharia Ambiental e o conjunto de alunos de Engenharia de Alimentos. Como esses
7.1 Combinatória Enumerativa 77
conjuntos têm 242 e 290 alunos, supondo que não há alunos em comum nos cursos temos um total
de 242 + 290 = 532 possibilidades para a escolha do aluno. ■
O princípio aditivo pode ser estendido para uma decisão D que têm como possibilidades os
elementos de n conjuntos disjuntos. Mais precisamente, suponha que uma decisão D possa ser
tomada como uma decisão em um dos conjuntos D1 , . . . , Dn , onde Di ∩ D j = 0/ para todo i ̸= j. Se
há xi maneiras diferentes de tomar a decisão em Di , então existem x1 + · · · + xn maneiras de tomar
a decisão D.
■ Exemplo 7.1.8 Um aluno de Matemática Discreta deve escolher um exercício para resolver em
sala no quadro negro valendo 1,0 ponto extra em sua primeira prova. Este aluno pode escolher
um dos exercícios das quatro listas foram passadas até aquele momento. Sabendo que as listas
possuem respectivamente 12, 9, 18 e 17 exercícios, determine de quantas maneiras o aluno pode
fazer a escolha do exercício.
O aluno deve escolher uma questão pertence à união de quatro conjuntos, isto é, os conjuntos
de exercícios de cada uma das listas. Supondo que não há questões em comum nas listas, temos
um total de 12 + 9 + 18 + 17 = 56 questões na união, que é o total de possibilidades de escolha do
aluno. ■
Alguns problemas de contagem não podem ser resolvidos como uma aplicação direta de apenas
um dos princípios básicos apresentados: eles requerem uma combinação mais elaborada de ambos.
É necessário ter em mente as técnicas a seguir.
• Quando as decisões possíveis podem ser caracterizadas como aquelas em um conjunto D mas
excluindo aquelas de um subconjunto A ⊆ D. Neste caso o número de decisões possíveis é
dado por |D| − |A|; veja o Exemplo 7.1.9.
• Quando as decisões possíveis podem ser caracterizadas como a união daquelas em conjuntos
D1 , D2 disjuntos, fornecendo um número |D1 | + |D2 | de decisões, mas a contagem de ele-
mentos de D1 e D2 é feita usando o princípio multiplicativo e/ou usando o item acima; veja o
Exercício 7.1.10.
■ Exemplo 7.1.9 Em um sistema computacional cada usuário deve ter uma senha de 6 caracteres
alfanuméricos, onde um caracter alfanumérico utiliza uma das 26 letras do alfabeto latino ou um
dos 10 dígitos numéricos. Mais ainda, cada senha deve conter pelo menos um dígito numérico.
Quantas senhas diferentes são possíveis neste sistema?
Seja P6 o conjunto de senhas de 6 caracteres conforme pedido no enunciado. Seja D o conjunto
de senhas de seis caracteres sem nenhuma restrição é descrito pela escolha dos 6 caracteres, onde
cada um deles tem 26 + 10 = 36 possibilidades. Segue que D possui 366 elementos.
Seja A o conjunto de senhas que não possui nenhum dígito numérico. O total destas senhas é
descrito pela escolha dos 6 caracteres, onde cada um deles pode ser apenas uma letra. O total de
elementos do conjunto A é, portanto, de 266 elementos. O número de elementos de P6 é portanto
366 − 266 = 1.867.866.560. ■
Exercício 7.1.10 Resolva o Exemplo 7.1.9 no caso em que a senha do sistema computacional
deve ter de 6 a 8 caracteres alfanuméricos. ■
Exercício 7.1.11 Quantos são os números pares com três dígitos distintos? ■
Princípio da Inclusão-Exclusão
Suponha que uma decisão D possa ser tomada de x formas diferentes em um conjunto D1
ou de y formas diferentes em um conjunto D2 , onde D1 e D2 são conjuntos com interseção
não-vazia. Suponha que |D1 ∩ D2 | = z. Então o número de maneiras de tomar a decisão D é
x + y − z.
Exercício 7.1.12 Quantos cadeias de bits de extensão oito começam com um bit 1 ou terminam
com dois bits 00? ■
Diagramas de árvore.
Problemas de contagem podem ser resolvidos usando diagramas de árvores; veja a Definição 6.2.9
para a definição de uma árvore. Mais precisamente, iniciamos o processo com um único nó, raiz da
árvore. Cada aresta (galho) saindo da raiz representa uma escolha possível para a primeira decisão
a ser tomada. A partir dos novos nós que foram criados partem novos galhos, que representam as
escolhas possíveis para a segunda decisão a ser tomada no problema, e assim por diante. Ao esgotar
este processo chegamos a nós terminais da árvore: nós a partir dos quais não partem novos galhos,
que podem ser vistos como membros de uma árvore genealógica que não possuem filhos. Estes nós
terminais são chamados de folhas e representam as possíveis escolhas globais do problema.
Exercício 7.1.13 Um homem possui um terno preto, camisas de cor azul e vermelha e gravatas
de cor azul, vermelha e verde. Quantas combinações de terno-camisa-gravata ele pode compor?
■
Exercício 7.1.14 De quantas maneiras diferentes uma pessoa pode realizar três lançamentos de
moeda sem obter dois resultados “cara” consecutivos? ■
Teorema 7.1.15 Seja n um inteiro positivo e seja P(n) o número de maneiras distintas que
podemos organizar n objetos em uma fila ordenada. Então,
P(n) = n · (n − 1) · (n − 2) · · · 2 · 1.
Demonstração. Para a primeira posição da fila podemos escolher qualquer um dos n objetos.
Uma vez escolhido o objeto da primeira posição, ele não pode constar também na segunda posição;
temos portanto n − 1 objetos possíveis para a segunda posição. Para a terceira posição teremos
n − 2 possibilidades e, usando o mesmo argumento, concluímos que temos n − (i − 1) possibilidades
para a i-ésima posição. Segue do princípio multiplicativo que P(n) = n · (n − 1) · (n − 2) · · · 2 · 1.
■
Exercício 7.1.17 Quantos são os anagramas da palavra “COBRA”? Quantos começam por
vogal? ■
Teorema 7.1.19 Sejam n,r inteiros positivos tais que 1 ≤ r ≤ n. Seja P(n,r) o número de
r-permutações de um conjunto com n elementos. Então,
P(n,r) = n · (n − 1) · (n − 2) · · · (n − r + 1).
Exercício 7.1.20 A final da prova de atletismo de 100m rasos das Olimpíadas de 2016 no
Rio de Janeiro foi disputada por oito atletas. Quantos pódios possíveis de 3 atletas podiam ser
compostos por estes atletas? ■
Fornecemos aqui uma segunda demonstração para o Teorema 7.1.19. Considere incialmente,
como um exemplo, o problema de determinar o número de 2-permutações construídas a partir
dos elementos do conjunto {1,2,3,4,5}. Podemos compor uma 2-permutação ao compor uma fila
com os 5 elementos do conjunto e selecionar os dois primeiros elementos, como ilustrado abaixo:
obtemos a 2-permutação (2,3) a partir da permutação (2,3,1,4,5).
2 3 1 4 5 =⇒ 2 3.
Sabemos que o número de permutações dos 5 objetos é P(5) = 5! = 120. No entanto, note que
cada 2-permutação determinada pelos dois primeiros elementos da fila maior aparece 3! = 6 vezes
na lista de todas as 120 permutações dos 5 objetos. No caso acima, independente da ordem em
que os elementos {1,4,5} aparece nas últimas três posições, a 2-permutação formados pela fila
ordenada (2,3) é a mesma:
2 3 1 4 5,
2 3 1 5 4,
2 3 4 1 5,
(7.1)
2 3 5 5 1,
2 3 5 1 4,
2 3 5 4 1.
Em outras palavras, o conjunto de 120 permutações dos 5 elementos é dividido em blocos de 3! per-
mutações que fornecem a mesma 2-permutação dada pelos dois primeiros elementos. Concluímos
80 Capítulo 7. Combinatória
que o número de 2-permutações de cinco elementos é dado pelo número destes blocos:
5! 120
P(5,2) = = = 20.
3! 6
Este é o mesmo valor obtido pela expressão P(5,2) = 5 · 4 = 20 dada pelo Teorema 7.1.19.
Mais geralmente, para compor uma r-permutação a partir de um conjunto de n objetos, podemos
compor uma fila com todos os n objetos e selecionar os primeiros r elementos para a r-permutação
desejada. Usando o mesmo argumento acima concluímos que o número de r-permutações é dado
por
n! n · (n − 1) · · · (n − r + 1) · (n − r) · (n − r − 1) · · · 2 · 1
P(n,r) = =
(n − r)! (n − r) · (n − r − 1) · · · 2 · 1
= n · (n − 1) · (n − r + 1),
2 3 1 4 5, 3 2 1 4 5,
2 3 1 5 4, 3 2 1 5 4,
2 3 4 1 5, 3 2 4 1 5,
(7.2)
2 3 5 5 1, 3 2 5 5 1,
2 3 5 1 4, 3 2 5 1 4,
2 3 5 4 1, 3 2 5 4 1.
Segue que os 5!
3! = 20 blocos obtidos se organizam em grupos de 2! = 2 que fornecem a mesma
comissão; no caso acima, com os blocos vermelho e azul, a comissão {2,3}. Portanto o total de
comissões que pode ser formada é de
5!/3! 5!
= = 10.
2! 3!2!
Este argumento pode ser estendido para o caso geral de r-combinações formadas a partir de um
total de n objetos. Veja o Teorema 7.1.21.
Teorema 7.1.21 Sejam n,r inteiros positivos tais que 1 ≤ r ≤ n. Seja P(n,r) o número de
7.2 Princípio da cada dos pombos 81
como gostaríamos. ■
Exercício 7.1.22 Em um jogo de buraco um jogador recebe 11 cartas inicialmente; este conjunto
de cartas é chamado de uma “mão”. Quantas “mãos” de 11 cartas podem ser retiradas de um
baralho de 52 cartas? ■
Seja k um inteiro positivo. Se k + 1 pombos devem entrar em k casas, então há uma casa
que terá dois ou mais pombos.
■ Exemplo 7.2.1 Prove que em um grupo de 366 pessoas existem pelo menos duas que fazem
aniversário na mesma data (excluindo o dia adicional de anos bissextos).
Consideramos neste problema os pombos como as 366 pessoas e as casas como as datas de
aniversário. Interpretamos a data de aniversário de uma pessoa como a inserção de um pombo na
casa correspondente. Como temos 366 pessoas e 365 datas de aniversário, então pelo princípio da
casa dos pombos existe uma data será a data de aniversário de pelo menos duas pessoas. ■
■ Exemplo 7.2.2 Considere um grupo de n casais, totalizando 2n pessoas casadas. Quantas das 2n
pessoas devem ser selecionadas para garantir que um dos casais esteja dentre as pessoas escolhidas?
Consideramos aqui as pessoas como os pombos e as casas como os casais do grupo. São n
casas no total, de modo que garantimos pelo princípio da casa dos pombos que em um grupo de
n + 1 pombos existirá uma casa com pelo menos dois pombos. Logo são necessárias n + 1 pessoas.
■
82 Capítulo 7. Combinatória
■ Exemplo 7.2.3 Seja A um conjunto de n + 1 números inteiros positivos. Prove que existem dois
números a,b tais que a − b é divisível por n.
Devemos provar que existem dois números a,b tais que n | (a − b), ou seja, devemos provar
que existem dois números a,b tais que a ≡ b (mod n). Escrevendo o conjunto A como A =
{a1 , . . . , an+1 }, consideramos as reduções a1 mod n, . . . , an+1 mod n e provamos que pelo menos
duas devem ser iguais; se ai mod n = a j mod n, concluímos pelo Teorema 5.1.15 que ai ≡ a j
(mod n), como gostaríamos.
Fazemos uso do princípio da casa dos pombos. Consideramos como os pombos os elementos
a1 , . . . , an+1 do conjunto A e consideramos os n possíveis restos na divisão por n como as casas
de pombo. Segue do princípio da casa dos pombos que existe uma casa com pelo menos dois
pombos, isto é, existe um resto 0 ≤ k < n tal que ai mod n = k e a j mod n = k para elementos
ai , a j distintos. Segue do Teorema 5.1.15 que n | (a − b). ■
O exemplo abaixo representa uma aplicação mais elaborada do princípio da casa dos pombos.
■ Exemplo 7.2.4 Dado um grupo de 101 inteiros distintos no conjunto {1, 2, . . . ,200}, prove que
existem pelo menos dois inteiros que tal que um é divisível pelo outro.
Escreva os 101 inteiros como a1 , . . . , a101 e escreva
ai = 2αi qi ,
onde αi ≥ 0 e qi é um número ímpar. Como ai ≤ 200, devemos ter qi ≤ 200. Note que o número de
inteiros ímpares positivos entre 1 e 200 é igual a 100. Interpretando o valor de qi como as casa de
pombo e os inteiros a1 , . . . , a101 como os pombos, concluímos pelo princípio da casa dos pombos
que qi = q j = q para inteiros distintos ai , a j . Logo
ai = 2αi q e a j = 2α j q.
Como os 101 inteiros da lista original são distintos, temos ai ̸= a j e portanto αi ̸= α j . Se αi > α j
então a j | ai , e se αi < α j então ai | a j . Como estes são os únicos dois casos possíveis, está provado
que existem dois números da lista tal que um divide o outro. ■
O princípio da casa dos pombos pode ser generalizado para o caso em que N pombos devem
ser alocados em k casas, onde N > k. Neste princípio utilizamos a função ⌈x⌉, definida para x ∈ R
como o menor inteiro maior ou igual a x. Exemplos:
⌈3,2⌉ = 4,
⌈4,7⌉ = 5,
⌈5⌉ = 5.
Sejam N,k inteiros positivos. Se N pombos devem entrar em k casas, então há uma casa que
com pelo menos ⌈N/k⌉ pombos.
■ Exemplo 7.2.6 Prove que em um grupo de 100 pessoas existem pelo menos 9 que fazem
aniversário no mesmo mês.
7.2 Princípio da cada dos pombos 83
Este problema corresponde à alocação de 100 pombos em 9 casas. Segue do princípio generali-
zado da casa dos pombos que existe um mês em que pelo menos ⌈100/12⌉ onde pessoas fazem
aniversário, ⌈100/12⌉ = ⌈8,5⌉ = 9. ■
■ Exemplo 7.2.7 Uma prova de História é aplicada e os alunos recebem uma das seguintes notas
após a correção: 0, 1, 2, . . . , 9 ou 10. Quantos alunos devem fazer a prova para se ter certeza que
pelo menos cinco tirarão a mesma nota?
Consideramos os alunos como os pombos e as possíveis notas como as casas de pombo. Se
N alunos realizam a prova, N > k, então existe uma nota que será atribuída a pelo menos ⌈N/11⌉
alunos. Para N = 44 temos ⌈44/11⌉ = 4, logo o menor inteiro N tal que ⌈N/11⌉ = 5 é N = 45.
Segue que são necessário 45 alunos para se ter garantia que pelo menos 5 tirarão a mesma nota na
prova. ■
Exercício 7.2.8 Considere um baralho de 52 cartas dividido nos quatro naipes usuais (paus,
espadas, ouro e copas) com 13 cartas cada um. Quantas cartas devem ser escolhidas do baralho
para garantir que pelo menos 3 sejam do mesmo naipe? ■
8. Relações
Um relação é definida matematicamente logo no início da Seção 8.1, mas podemos entendê-las
como um tipo de associação entre elementos de conjuntos. Esta é uma situação que ocorre com
bastante frequência, por exemplo em relações de amizade entre indivíduos de um grupo e cidades
do Brasil que estão conectadas por um voo comercial.
Definimos acima a relação como binária pois ela envolve apenas dois conjuntos. É possível
estender esse conceito para relação entre n conjuntos, mas não o faremos aqui neste texto. Por esse
motivo relações binárias serão chamadas simplesmente de relação daqui em diante.
■ Exemplo 8.1.2 Sejam A o conjunto de alunos do curso de Engenharia da Computação da
UTFPR Apucarana e B o conjunto de disciplinas ofertadas em um determinado semestre para este
curso. Considere a relação R definida como os pares (a,b) tais que o estudante a está matricu-
lado na disciplina b. Por exemplo, se Bruno e Marcela estão matriculados em Cálculo 2, então
(Bruno, Cálculo 2) ∈ R e (Marcela, Cálculo 2) ∈ R. ■
é uma relação de A em B. Segue que 0 R a mas 1 e b não estão relacionados de acordo com a
definição de R. Veja na Figura 8.1 uma representação gráfica desta relação. ■
• 2 divide 2, • 3 divide 3,
• 2 divide 4, • 4 divide 4.
Segue que R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}. ■
■ Exemplo 8.1.8 Quais das relações abaixo no conjunto A = {1, 2, 3} são reflexivas?
Para que R seja uma relação reflexiva em A é necessário que (a,a) ∈ R para todo elemento
a ∈ A, isto é, é necessário que {(1,1), (2,2), (3,3)} ⊆ R. Segue que R1 é reflexiva mas R2 não o é. ■
■ Exemplo 8.1.9 Quais das relações do Exemplo 8.1.8 são simétricas e quais são antisimétricas?
A relação R1 não é simétrica pois (2,1) ∈ R1 mas (1,2) ∈ / R1 . Além disso, temos (1,3) ∈ R1 e
(3,1) ∈ R1 e é falso que 1 = 3; logo R1 não é antisimétrica.
8.2 Relações de Equivalências 87
Exercício 8.1.11 Considere a relação R definida no conjunto Z dos inteiros por (a,b) ∈ R se e
somente se a divide b. Determine se R é reflexiva, simétrica, antisimétrica e/ou transitiva. ■
■ Exemplo 8.2.3 Sejam n ≥ 2 um inteiro e R a relação definida no conjunto dos inteiros tal que
a − b = nk1 e c − b = nk2 ,
Demonstração. Inicialmente provamos que (i) implica (ii). Supomos que a ∼ b e provamos que
[a] ⊆ [b]. Seja c um elemento qualquer de [a]. Então a ∼ c. Como a ∼ b e R é simétrica, então
b ∼ a e, sendo R transitiva, b ∼ a e a ∼ c implicam em b ∼ c. Isto prova que c ∈ [b] e que [a] ⊆ [b].
A demonstração de [b] ⊆ [a] é análoga e deixada como exercício.
Para prova que (ii) implica (iii), suponha agora que [a] = [b]. Então [a] ∩ [b] = [a] ∩ [a]. Como
a ∈ [a] uma vez que R é reflexiva, segue que a interseção [a] ∩ [a] é não vazia pois contém {a}.
Por último provamos que (iii) implica (i). Suponha que [a] ∩ [b] ̸= 0. / Segue que existe um
elemento c tal que c ∈ [a] e c ∈ [b], isto é, c ∼ a e c ∼ b. Como R é reflexiva, temos que a ∼ c e,
mais uma vez pelo argumento de transitividade, a ∼ c e c ∼ b implicam a ∼ b, como queríamos
demonstrar. ■
Demonstração. Para provar que a∈A [a] = A, observamos que a∈A [a] ⊆ A por definição: uma
S S
classe de equivalência de [a] é composta por elementos de A, logo todo elemento de [a] pertence a
A. Por outro lado, se b ∈ A então sua classe de equivalência [b] está inserida na notação a∈A [a],
S
Sejam [a], [b] classes de equivalência diferentes de R. Como [a] ̸= [b], segue do Teorema 8.2.6
que [a] ∩ [b] = 0,
/ como gostaríamos. ■
9.1 Grafos
Grafos são estruturas combinatórias de grande importância, uma vez que suas aplicações são vastas
e numerosas: podemos utilizar grafos para modelar diversas situações como mapas rodoviários, co-
laboração de pesquisadores, usuários de redes sociais, links entre websites e estruturas moleculares.
A definição de grafo é bastante simples: um grafo consiste de um conjunto de vértices (ou nós) que
são ligados por arestas.
Definição 9.1.1 Um grafo G é um conjunto não-vazio V de vértices e um conjunto E de arestas
que ligam vértices, onde uma aresta e ∈ E é da forma {a,b}, onde a,b ∈ V . Dizemos que a e b
são as extremidades da aresta e; dizemos também que e liga ou conecta as suas extremidades.
■ Exemplo 9.1.2 Considere o grafo G = (V,E) onde os conjuntos de vértices e arestas são dados por
V = {1,2,3} e E = {{1,2}, {1,3}}. Podemos ilustrar este grafo através de três pontos ou círculos,
cada um representando um vértice de V = {1,2,3}. O conjunto de arestas E = {{1,2}, {1,3}}
determina que existe uma ligação entre os vértices 1 e 2, assim como uma ligação entre os vértices
1 e 3; os vértices 2 e 3 não possui ligação neste grafo. Veja a Figura 9.1. ■
Figura 9.1: Grafo com três vértices e duas Figura 9.2: Grafo com quatro vértices e
arestas. cinco arestas.
■ Exemplo 9.1.3 Considere que no Facebook existem quatro usuários A,B,C e D tais que existem
92 Capítulo 9. Grafos e Árvores
■ Exemplo 9.1.4 Considere uma região do Brasil que possui quatro cidades A,B,C e D tais que
existem estradas que conectam as cidades A e B, A e C, A e D, B e D e uma última estrada que
liga C e D. Podemos representar este mapa rodoviário através de um grafo G = (V,E) onde
V = {A,B,C,D} e E = {{A,B}, {A,C}, {A,D}, {B,D}, {C,D}}. Note que este é o mesmo grafo do
Exemplo 9.1.3 e da Figura 9.2, o que ilustra que grafos servem de modelos para muitas aplicações
diferentes. ■
Os grafos dos Exemplos 9.1.2, 9.1.3 e 9.1.4 satisfazem a seguinte propriedade: não existem
duas arestas que conectam o mesmo par de vértices e não existe uma aresta que conecta um vértice
a ele mesmo. Tais grafos são chamados de grafos simples. No entanto, é possível que um grafo
possua arestas múltiplas ligando o mesmo par de vértices: no Exemplo 9.1.4 podemos considerar
um grafo que ilustra o fato de que existe uma segunda estrada ligando as cidades A e B; veja a
Figura 9.3. Dizemos nesse caso que a aresta {A,B} tem multiplicidade 2.
■ Exemplo 9.1.5 Considere uma rede formada por centros de dados A,B,C e D e links (canais) de
comunicação entre elas como na Figura 9.4. Note que há mais de um canal de comunicação entre
as redes A e C e há um canal de comunicação da centro D com ele mesmo, o que pode denotar um
laço de auto-alimentação para fins de diagnóstico. ■
No Exemplo 9.1.5 (Figura 9.4) temos um grafo com uma aresta múltipla de multiplicidade
2 e uma aresta que conecta um vértice a ele mesmo. Uma aresta que conecta um vértice a ele
mesmo é dita um laço; grafos que possuem arestas múltiplas e laços são algumas vezes chamados
de pseudografos.
Uma outra classe importante de grafos é a dos grafos direcionados, onde as arestas possuem
um direcionamento: uma aresta ligando vértices A e B ou começa em A e termina em B ou começa
em B e termina em A. Caracterizar as arestas de um grafo desta forma pode ser importante em
várias situações, como a modelagem de usuários de uma rede social como o Instagram: enquanto
no Facebook as relações de amizade não possuem direcionamento nenhum, pois se A é amigo de B
então B é amigo de A, no Instagram é possível que A seja seguidor de B sem que B seja seguidor de
A. Veja a Definição 9.1.6 e o Exemplo 9.1.7. No Exemplo 9.1.8 temos um mapa rodoviário com
vias de mão única ilustradas por arestas direcionadas.
Definição 9.1.6 Um grafo direcionado G é um conjunto não-vazio V de vértices e um conjunto
E de arestas orientadas ou arcos que ligam vértices, onde uma aresta orientada e ∈ E é da forma
(a,b), onde a,b ∈ V . Dizemos que a aresta (a,b) começa em a e termina em b.
■ Exemplo 9.1.8 Considere uma região do Brasil que possui quatro cidades A,B,C e D tais que as
estradas que conectam estas cidades são como na Figura 9.6. Note que há arcos ligando A a B e
ligando B a A: isto indica uma via de mão dupla conectando as cidades A e B ou, possivelmente,
duas vias diferentes de mão única ligando A a B e ligando B a A. Neste problema não podemos
nos deslocar diretamente da cidade D para a cidade C: é precisa passar pela cidade A para chegar à
cidade C. ■
Demonstração. Seja e ∈ E uma aresta do grafo G. Como e possui duas extremidades, digamos
a,b ∈ V , temos que e contribui em duas unidades para a soma ∑v∈V gr(v): uma unidade em gr(a)
e uma unidade em gr(b). Note que este argumento se aplica a arestas múltiplas e laços. Segue que
na soma ∑v∈V gr(v) há duas unidades para cada aresta do grafo, totalizando 2m. ■
94 Capítulo 9. Grafos e Árvores
Exercício 9.2.5 Quantas arestas possui um grafo com 8 vértices, onde cada um possui grau 4?
■
Exercício 9.2.6 Prove que todo grafo não-orientado possui um número par de vértices de grau
ímpar. ■
Os conceitos apresentados nas Definições 9.2.1 e 9.2.2 são interpretados de maneira diferente
no caso de grafos orientados, discutidos a seguir.
Definição 9.2.7 Sejam G = (V,E) um grafo orientado e u,v ∈ V vértices de G. Dizemos que u
é adjacente para v e que v é adjacente a partir de u se existe uma aresta (u,v) ∈ E. O vértice u
é dito o vértice inicial de (u,v) e v é dito o vértice final ou terminal de (u,v).
O Teorema do Aperto de Mãos (Teorema 9.2.4) tem sua versão para grafos direcionados. Veja
o Teorema 9.2.10 a seguir.
Em outras palavras, um grafo G é completo existe exatamente uma aresta conectando cada par
de vértices no grafo. Veja a Figura 9.7. A Figura 9.8 ilustra um grafo de ciclo (Definição 9.3.3).
Definição 9.3.2 O ciclo de n vértices, n ≥ 1, é o grafo não-direcionado com vértices v1 , . . . , vn
e arestas {v1 , v2 }, {v2 , v3 }, . . . , {vn−1 , vn }, {vn , v1 }.
9.4 Representação de Grafos 95
Definição 9.3.3 Um grafo simples G = (V,E) é dito bipartido se podemos escrever o conjunto
de vértices como a união V = V1 ∪V2 de conjuntos disjuntos V1 ,V2 tais que toda aresta conecta
um vértice de V1 e um vértice de V2 . Dizemos nesse caso que V1 ,V2 é uma bipartição do conjunto
de vértices de G.
Em outras palavras, podemos dizer que em um grafo bipartido G = (V,E) com bipartição
V = V1 ∪V2 não existe uma aresta que conecta dois vértices de V1 ou que conecta dois vértices de
V2 . Veja a Figura 9.9, onde mostramos que o grafo de ciclo C6 é bipartido.
■ Exemplo 9.4.1 Considere o grafo G = (V,E) da Figura 9.1 onde V = {1,2,3} e E = {{1,2}, {1,3}}.
Exibimos a lista de adjacência de G na tabela abaixo, onde cada linha fornece os vértices adjacentes
a um vértice do grafo.
vértice vértices adjacentes
1 2,3
2 1
3 1
■
■ Exemplo 9.4.2 Seja G = (V,E) o grafo de ciclo C5 (Figura 9.8) onde V = {1,2,3,4,5} e E =
{{1,2}, {2,3}, {3,4}, {4,5}, {5,1}, }. A lista de adjacência de G é apresentada abaixo.
vértice vértices adjacentes
1 1,5
2 1,3
3 2,4
4 3,5
5 1,4
■
■ Exemplo 9.4.4 Considere o grafo C5 do Exemplo 9.4.2, Figura 9.8: G = (V,E) onde V =
{1,2,3,4,5} e E = {{1,2}, {2,3}, {3,4}, {4,5}, {5,1}, }. A matriz deste grafo é apresentada abaixo.
0 1 0 0 1
1 0 1 0 0
A= 0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
■
Matrizes de adjacência também podem ser utilizadas para representar grafos com múltiplas
arestas e laços: definimos a entrada ai, j da matriz como o número de arestas que conectam os
vértices i e j; se existe um laço no vértice i, definimos ai,i = 1. Ou seja, definimos a matriz de
adjacência de grafos com múltiplas arestas e laços por
■ Exemplo 9.4.5 Considere o grafo da Figura 9.4 (Exemplo 9.1.5). Os vértices deste grafo têm
rótulos V = {A,B,C,D}, de modo que precisamos criar uma correspondência entre estes vértices
e as quatro linhas da matriz de adjacência. Existem 4! maneiras de fazê-lo, mas faremos o mais
natural: as Linhas 1,2,3 e 4 corresponderão aos vértices A,B,C e D, respectivamente. A matriz de
adjacência é portanto dada da seguinte maneira.
0 1 2 1
1 0 0 1
A= 2 0 0 1
1 1 1 1
■
Também podemos descrever grafos orientados com matrizes de adjacência. Definimos neste
caso
1, se (vi ,v j ) é aresta de G,
ai, j =
0, caso contrário.
Em outras palavras, definimos ai, j = 1 se existe uma aresta de vi para v j .
■ Exemplo 9.4.6 Considere o grafo direcionado do Exemplo 9.1.8 (Figura 9.6). Sua matriz de
adjacência é dada por
0 1 1 1
1 0 0 1
A=
0
0 0 1
1 0 0 0
■
Note que os grafos possuem o mesmo número de arestas e a correspondência da Definição 9.5.1 é
preservada:
É importante destacar que se uma bijeção escolhida entre os vértices de dois grafos não preserva
as arestas, isso não significa que os grafos não são isomorfos: possivelmente a escolha de uma
outra bijeção definiria um isomorfismo. Por exemplo, no caso do Exemplo 9.5.2, a bijeção
não define um isomorfismo, pois (A,C) é aresta de G1 mas (g(A), g(C)) = (2,3) não é aresta de G2 .
Em outras palavras, para que dois grafos sejam isomorfos não é necessário que toda bijeção entre
os conjuntos de vértices defina um isomorfismo; basta que apenas uma das n! bijeções possíveis
seja um isomorfismo.
No caso de grafos G1 , G2 que não são isomorfos, a princípio deveríamos testar todas as bijeções
possíveis entre os conjuntos de vértices e verificar que nenhuma delas define um isomorfismo. No
caso de grafos com n vértices, o total de n! pode tornar este caminho inviável. A alternativa é dada
pelo Teorema 9.5.4 abaixo, onde são enunciados alguns parâmetros que devem ter o mesmo valor
no caso de grafos isomorfos; tais parâmetros são chamados de invariantes do grafo.
9.6 Conectividade de Grafos 99
O item (i) do Teorema 9.5.4 pode ser enunciado da seguinte maneira: se G1 e G2 são isomorfos,
então G1 e G2 possuem o mesmo número de vértices. A contra-positiva deste teorema fornece uma
maneira de provar que dois grafos não são isomorfos: se G1 e G2 não possuem o mesmo número
de vértices, então G1 e G2 são isomorfos. O mesmo vale para os outros invariantes de grafos.
■ Exemplo 9.5.6 Mostre que os grafos da Figura 9.13 não são isomorfos.
Temos que um dos grafos possui 3 arestas e o outro possui 4 arestas. Segue do item (ii) do
Corolário 9.5.5 que estes grafos não são isomorfos. ■
■ Exemplo 9.5.7 Mostre que os grafos da Figura 9.14 não são isomorfos.
Note que o grafo G2 à direita possui um vértice de grau 4 e o grafo G1 à esquerda não possui
nenhum vértice de grau 4. Como o número de vértices de um dado grau é um invariante do grafo,
segue que estes grafos não são isomorfos. ■
primeiro grafo é desconexo e o segundo é conexo, definição que apresentamos a seguir. Mas para
esta definição precisamos do conceito de caminho entre vértices.
■ Exemplo 9.6.3 Considere o grafo G = (V,E) ilustrado na Figura 9.15. Temos 6 vértices neste
grafo: V = {A,B,C,D,E,F}. O grafo G é desconexo, pois não existe um caminho ligando os
vértices A e D. ■
■ Exemplo 9.6.4 Considere o grafo G = (V,E) ilustrado na Figura 9.16. O grafo G é conexo pois
existe um caminho entre qualquer par de vértices de G. Por exemplo, dados os vértices C e E temos
o caminho C,A,D,E que liga C a E. ■
9.7 Árvores
Vimos a definição de árvores enraizadas na Seção 6.2 e daremos continuidade a este tópico aqui.
A seguir apresentação a definição de árvores não-enraizadas, ou simplesmente árvores. Para tal é
necessário o conceito de grafos conexos e de ciclos; veja as Definições 9.6.1 e 9.6.2.
Definição 9.7.1 Uma árvore é um grafo simples não orientado conexo que não possui ciclos.
Os nós de grau 1 de uma árvore são chamados de folhas.
Teorema 9.7.2 Um grafo simples não orientado G é uma árvore se e somente se existir um
único caminho simples entre quaisquer dois vértices de G.
■ Exemplo 9.7.3 Considere os grafos das Figuras 9.1 e 9.2. Na Figura 9.2 temos um ciclo dado
por ({A,C}, {C,D}, {D,A}), portanto este grafo não é uma árvore. Já o grafo da Figura 9.1 é uma
árvore pois claramente não possui ciclos. ■
Na Definição 9.7.5 temos uma outra definição para as árvores enraizadas da Definição 6.2.9,
isto é, as Definições 6.2.9 e 9.7.5 estabelecem o mesmo conjunto de grafos como árvores enraizadas.
Não fornecemos aqui a demonstração do teorema que estabelece a equivalência destas definições.
Definição 9.7.5 Uma árvore com raiz ou árvore enraizada é uma árvore na qual um vértice foi
escolhido como raiz e toda aresta é orientada no sentido que se afasta da raiz.
Em muitos textos a orientação dos vértices é omitida em árvores enraizadas, uma vez que esta
orientação já está clara a partir da definição. No entanto, apresentamos aqui a definição de árvores
enraizadas através da orientação de arestas por facilitar a redação de alguns conceitos.
C = ({x1 , x2 }, . . . , {xn−1 , xn }), então x1 é um nó de grau 1, pois caso contrário existiria um caminho maior que C em T .
102 Capítulo 9. Grafos e Árvores
Definição 9.7.6 Seja T uma árvore enraizada.
(i) Se v é um vértice de T diferente da raiz, definimos o pai de v como o único vértice u tal
que existe uma aresta de u para v. Dizemos nesse caso que v é filho de u.
(ii) Vértices de mesmo pai são chamados de irmãos.
(iii) Os ancestrais de um vértice v de T são os vértices contidos no caminho da raiz até v,
excluindo o próprio vértice v. Em outras palavras, os ancestrais de v são o seu pai, o pai
do seu pai e assim por diante, incluindo a raiz da árvore.
(iv) Os descendentes de um vértice v de T são os vértices que têm v como ancestral.
(v) Os vértices de T que não têm filhos são chamados de folhas. Os vértices de T que não
são folhas são chamados de vértices internos.
Aplicações de árvores.
Árvores podem ser utilizadas para representar estruturas fortemente hierarquizadas, como na Figura
9.17, que representa o organograma da UTFPR2 . Nessa árvore, a subordinação de um Setor X a
um Setor Y é representada pela paternidade de Y em relação a X; a raiz da árvore representa nesse
caso o setor que está acima de todos os outros do campus: o Conselho Universitário. A mesma
estrutura pode representar a estrutura de pastas no armazenamento de um computador, onde a raiz
representar o diretório raiz, os nós internos representam diretórios e as folhas representam arquivos
e diretórios vazios.
Uma outra aplicação de árvores é a de árvores de decisão. Na Figura 9.18 temos representada
uma árvore que a partir de alguns parâmetros de uma amostra de concreta retorna o seu valor de
resistência à força compressiva. Na raiz da árvore temos a primeira verificação, considerada a
mais importante de acordo com o treinamento a que o modelo foi submetido com os dados: é
verificado se a idade da amostra de concreto é menor ou igual a 21 dias. A seguir, é verificado se a
quantidade de cimento em quilos por metro cúbico é menor ou igual a 354.5 se a idade é menor ou
igual a 21 dias, ou menor ou igual a 357.5, caso contrário. Na árvore da Figura 9.18 o caminho à
esquerda de um nó representa sempre o resultado da verificação ter o valor verdadeiro, e seguimos
à direita se a verificação for falsa. A variável Amostras mostra quantas amostras de concreto do
conjunto de treinamento satisfazem as verificações em questão; na raiz temos a indicação de 875
amostras no total. O variável Resistência mostra o valor médio de resistência a força compressiva
em megapascais das amostras dentro das condições do nó em questão da árvore. As soluções do
problemas são representadas nas folhas da árvore: uma nova amostra de concreto é submetida a
sucessivas verificações até chegar a um nó terminal da árvore, onde o valor médio armazenado
na variável Resistência é fornecido como previsão para a resistência desta nova amostra. Mais
informações sobre este problema podem ser encontradas na página concrete compressive strength
do repositório de aprendizado de máquina da University of California, Irvine3 .
Definição 9.7.7 Seja m um inteiro positivo.
(i) Uma árvore T é dita de grau m se todo vértice de T possui no máximo m filhos.
(ii) Uma árvore T é dita cheia de grau m se todo vértice interno de T possui exatamente m
filhos.
Dizemos que uma árvore de grau m = 2 é dita uma árvore binária.
2 Disponível em http://www.utfpr.edu.br/documentos/reitoria/documentos-institucionais/organograma.
3 https://archive.ics.uci.edu/dataset/165/concrete+compressive+strength.
9.7 Árvores 103
Teorema 9.7.9 Existem no máximo mh folhas em uma árvore enraizada T de grau m e altura h.
Demonstração. Fornecemos uma demonstração por indução na altura h de T . Seja T uma árvore
de grau m. Se T possui altura h = 0, então T possui um único nó, que é simultaneamente raiz e
folha, e o número de folhas é igual a m0 = 1. Isto prova o teorema no caso h = 0.
Suponha agora que T tem altura h e o teorema é valido para árvores de altura menor ou igual
a h − 1. Sejam T1 , . . . , Tk as árvores obtidas pela remoção da raiz de T . Como T tem grau m, temos
que k ≤ m. Além disso, as folhas de T são as folhas de T1 , . . . , Tk que, como têm altura no máximo
h − 1, possuem por hipótese de indução no máximo mh−1 folhas cada uma. Segue que o número de
folhas de T é no máximo
k · mh−1 ≤ m · mh−1 = mh ,
como gostaríamos. ■
IV
Parte Três
Considere como exemplo uma situação em que é necessário ordenar a lista de números de CPF dos
usuários de um sistema. Podemos identificar este problema como um caso particular dos problemas
de ordenação de uma sequência finita de números, algo bastante comum na Ciência da Computação.
Na busca por um método de resolução de tais problemas, os algoritmos se apresentam como um
conceito central.
Definição 10.0.1 Um algoritmo pode ser definido como uma sequência precisa de instruções
para a resolução de um problema.
da quantidade de tempo que o algoritmo demanda para produzir a saída correta do problema. É
possível estudar também a complexidade de espaço, que representa uma investigação da quantidade
de memória que o algoritmo utiliza, mas nosso foco aqui será na complexidade de tempo.
A complexidade de tempo de um algoritmo é em geral descrita por meio do número de operações
necessárias para a sua execução. Isso se dá porque o tempo de execução de um algoritmo depende
de outros fatores, como característica do hardware da máquina utilizada, e mudanças nestes fatores
resultam frequentemente em uma mudança por um fator constante; por exemplo, a Máquina A pode
executar um algoritmo usando metade do tempo da Máquina B, devido a diferenças de hardware.
Mas o que exatamente significa “número de operações necessárias”? A resposta depende do
tipo de problema que temos em mãos e nos exemplos abaixo isso fica mais claro.
■ Exemplo 10.1.1 — Complexidade de tempo do Algoritmo 1. Considere o Algoritmo 1. A
operação que consideramos como medida para sua complexidade de tempo é a comparação. A
comparação comparação mais clara no Algoritmo 1 é aquela da Linha 3, realizada uma vez para
cada iteração do laço, mas uma comparação também é realizada na Linha 2: em cada iteração a
variável i passa por uma comparação que verifica se o fim da lista já foi atingido. Segue que duas
comparações são feitas para cada iteração i = 2, . . . , n e uma comparação adicional, que interrompe
o laço de iteração, é feita para i = n + 1. Segue que o número de comparações do Algoritmo 1 é
2(n − 1) + 1 = 2n − 1. ■
Note que o número de comparações no Exemplo 10.1.1 é uma função do tamanho n da entrada,
algo que podemos considerar esperado: quando maior a entrada de um algoritmo, mas tempo será
necessário para processá-la e chegar na saída correta.
Estendemos agora nosso estudo a outros problemas e algoritmos. O Algoritmo 2 é um algoritmo
de busca sequencial: dada uma sequência (a1 , . . . , an ) e um elemento x, o algoritmo deve identificar
a coordenada ou índice da sequência em que o elemento x se encontra. O algoritmo se inicia
com i = 1 e repete a operação i = i + 1 enquanto o elemento x não for encontrado (x ̸= ai ) e não
chegou-se ao fim da lista (i ≤ n). O algoritmo alcança a Linha 5 em uma das duas situações: ou o
elemento x foi encontrado em x = ai para algum i ≤ n; ou o elemento x não foi encontrado, caso em
que i = n + 1. A verificação condicional if-else nas Linhas 5 e 8 identifica o caso e retorna loc > 0
quando o elemento foi encontrado e loc = 0 caso contrário.
■ Exemplo 10.1.2 — Complexidade de tempo do Algoritmo 2. Analisamos a complexidade de
tempo do Algoritmo 1 utilizando, mais uma vez, a contagem do número de comparações realizadas
em sua execução. Dividimos a análise em dois casos.
(i) Suponha que o elemento x não se encontra na lista. Então ela será percorrida por completo
pelo laço definido na Linha 2, onde para cada i = 1, . . . , n duas comparações são feitas na
Linha 2 e uma comparação adicional é feita para interromper o laço de repetição; por fim,
uma comparação é feita na Linha 5. O total de comparações é 2n + 2.
10.1 Complexidade de algoritmos 109
(ii) Suponha que o elemento x se encontra na lista na posição j. Se j = 1, então o algoritmo fará
as duas comparações da Linha 2, identificando que x = a1 e passando para a Linha 5 então.
Caso contrário, o algoritmo atualiza o valor de i para i = 2 e o procedimento é repetido.
Concluímos que o número de comparações feita nesse caso é 2 j + 1.
Percebemos que o número de comparações não é determinado totalmente a partir do tamanho da
lista n. O melhor caso é aquele em que x se encontra na primeira posição, caso em que o algoritmo
realiza 2 · 1 + 1 = 3 comparações; e quando x se encontra na última posição são necessárias 2n + 1
comparações. Quando x não se encontra na lista, uma comparação a mais é realizada na Linha 2
para que o algoritmo identifique que já percorreu toda a lista; nesse caso são necessárias 2n + 2
comparações. ■
No Exemplo 10.1.2 foi feita uma análise de pior caso, isto é, foi estimado o maior número de
operações necessário para resolver o problema com uma entrada de tamanho fixo n. No exemplo
abaixo estudamos a complexidade de caso médio no algoritmo, onde determinamos o número
médio de operações que o algoritmo realizará considerando todas as configurações possíveis de
entradas igualmente prováveis.
■ Exemplo 10.1.3 — Complexidade de tempo de caso médio do Algoritmo 2. Suponha que
o Algoritmo 1 é acionado para a busca de um elemento x que se encontra em uma lista (a1 , . . . , an )
com n elementos. Suponha que a probabilidade de x se encontrar na i-ésima posição é 1/n para
todo i = 1, . . . , n. O número médio de comparações que o algoritmo realiza no caso de listas com n
elementos, considerando as possíveis posições i = 1, . . . , n para x, é
!
1 n 1 n n
∑ (2i + 1) = n 2 ∑ i + ∑ 1 ,
n i=1 i=1 i=1
onde, conforme visto no Exemplo 6.1.1, ∑ni=1 i = n(n + 1)/2. Segue que o número médio de
comparações no caso de listas com n elementos é igual a
!
n
1 n(n + 1) n2 + n + n
2 +∑1 = = n + 2.
n 2 i=1 n
■
Nos exemplos acima contabilizamos as comparações realizadas para checar se o fim de um laço
“for” foi atingido. Essas comparações são frequentemente ignoradas em análises e deste ponto em
diante nós ignoramos esse tipo de comparação.
110 Capítulo 10. Análise de Algoritmos
Algoritmos de ordenação.
Vejamos agora o estudo da complexidade de tempo de dois algoritmos de ordenação: bubble sort e
insertion sort. O Algoritmo 3, chamado de bubble sort, consiste em sucessivas comparações entre
elementos consecutivos na sequência. Os maiores elementos da sequência são deslocados para o
fim de modo tal que a primeira iteração do primeiro laço (Linha 1) garante que a última posição
está correta, a segunda iteração garante que a penúltima posição está correta e assim por diante.
pelo resultado provado no Exemplo 6.1.1. Note que este é o número de comparações reali-
zado pelo bubble sort independente da configuração da lista de entrada, de modo que esta é a
complexidade de tempo de pior caso e de caso médio. ■
Apresentamos no Algoritmo 4 o insertion sort. Ele tem início com a comparação do segundo
elemento da sequência de entrada com o primeiro e a ordenação dessas duas entradas. A partir
disso, para j = 3, . . . , n, o algoritmo compara o j-ésimo elemento com os j − 1 anteriores e insere-o
na posição correta, obtendo assim uma lista ordenada nos j primeiros elementos da sequência neste
ponto da execução.
■ Exemplo 10.1.5 — Complexidade de tempo do Algoritmo 4. A operação considerada na
análise da complexidade de tempo do Algoritmo 4 é novamente o número de comparações. O
algoritmo possui um laço na Linha 1 que em cada iteração j = 2, . . . , n realiza comparações na
Linha 4. No pior caso o algoritmo efetua, para cada j, uma comparação para cada i = 1, . . . , j,
interrompendo o laço da Linha 3 na comparação a j > a j , que é falsa. Segue que o total de
comparações realizadas para a ordenação de uma lista de n elementos com o insertion sort é, no
pior caso,
n(n + 1)
2 + 3 + 4 + · · · + n = (1 + 2 + 3 + 4 + · · · + n) − 1 = − 1.
2
A análise de caso médio do insertion sort é mais consideravelmente mais complexa do que aquelas
já apresentadas e por isso será omitida. ■
10.2 Crescimento de Funções 111
um termo da forma Cx2 , convém estimar cada um dos termos por um monômio da forma cx2 :
x2 ≤ x2 , para todo x,
2x ≤ 2x · x = 2x2 , para x > 1,
1 ≤ x2 , para x > 1.
Segue que
|x2 + 2x + 1| = x2 + 2x + 1 ≤ x2 + 2x2 + x2 = 4x2 , para x > 1,
isto é, f (x) ≤ 4x2 para x > 1. Isto prova que f (x) é O(x2 ). ■
Agora que temos já um exemplo em mãos, podemos discutir: o que significa realmente a
afirmação f (x) = O(x2 )? Veja a Figura 10.1. Não podemos afirmar que x2 + 2x + 1 = x2 ou que
x2 + 2x + 1 ≤ x2 , mas a partir de x = 1 podemos visualizar que x2 + 2x + 1 ≤ Cx2 para C = 4. Isto
pode ser interpretado como uma comparação do ritmo de crescimento das funções f (x) e Cx2 para
“valores grandes” de x, que nesse caso são aqueles que satisfazem x > 1.
Note que se f (x) = O(g(x)) então a Definição 10.2.1 se aplica com diferentes contantes C,k.
Por exemplo, no caso do Exemplo 10.2.2 temos que x2 + 2x + 1 ≤ 4x2 para x > 1 e, como 4x2 ≤ 5x2 ,
temos x2 + 2x + 1 ≤ 5x2 para x > 1. Mais ainda, se essa desigualdade vale de x = 1 em diante, ela
também valera de x = 2 em diante, portanto
Teorema 10.2.3 Seja f (x) = an xn + an−1 xn−1 + · · · a1 x + a0 , onde a j é um número real para
todo j. Então f (x) é O(xn ).
n2 ≤ Cn
não é verdade para todo n maior que k, quaisquer que sejam as constantes C,k.
10.2 Crescimento de Funções 113
Para tal observamos que, para n positivo, a divisão da desigualdade acima por n nos mostra que
n2 ≤ Cn ⇐⇒ n ≤ C.
Segue que n2 é O(n) se n ≤ C para todo n > k, o que não é possível pois, uma vez fixado um valor
para k, o conjunto de valores n > k não pode ser limitado superiormente como na afirmação n ≤ C.
Segue que n2 não é O(n). ■
No Exemplo 10.2.4 provamos que n2 não é O(n), o que pode ser interpretado da seguinte forma.
As funções n2 e n ambas tem limite infinito quando n → +∞, mas o ritmo de crescimento da função
n2 é fundamentalmente mais rápido: não conseguimos afirmar que n2 ≤ n nem n2 ≤ Cn a partir de
certo valor de n, por maior que seja a constante C. Veja a Figura 10.2.
Os resultados abaixo são importantes para a análise de algoritmos porque fornecem uma
estimativa para a soma e produto de funções f1 (x) e f2 (x). Em uma situação em que, por exemplo,
um algoritmo é dividido em duas partes que têm complexidade de tempo respectivamente f1 (x)
e f2 (x), o teorema abaixo pode ser usado na determinação da complexidade de tempo total do
algoritmo.
Teorema 10.2.6 Suponha que f1 (x) é O(g(x)) e f2 (x) é O(h(x)). Suponha ainda que existe x0
tal que g(x) ≤ h(x) para x ≥ x0 . Então f1 (x) + f2 (x) é O(h(x)).
114 Capítulo 10. Análise de Algoritmos
Corolário 10.2.7 Suponha que f1 (x) e f2 (x) são O(g(x)). Então f1 (x) + f2 (x) é O(g(x)).
Teorema 10.2.8 Suponha que f1 (x) é O(g1 (x)) e f2 (x) é O(g2 (x)). Então f1 (x) · f2 (x) é
O(g1 (x) · g2 (x)).
■ Exemplo 10.2.9 Forneça uma estimativa big-O para f (x) = (x + 1) log(x2 + 1) + 3x2 .
Estimamos uma soma usando o Teorema 10.2.6: estimamos cada termo separadamente e a
seguir aplicamos o teorema. Na estimativa do termo (x + 1) log(x2 + 1) observamos que x2 + 1 ≤
x2 + x2 = 2x2 para x ≥ 1. Portanto,
para x ≥ 2. Segue que log(x2 + 1) é O(log x) e, como x + 1 = O(x), temos que (x + 1) log(x2 + 1) =
O(x log x) pelo Teorema 10.2.8.
Como 3x2 é O(x2 ) pelo Teorema 10.2.3, devemos determinar qual dos termos x2 e x log x
é maior. Note que, para x ≥ 1, podemos dividir a inequação x2 ≥ x log x e concluir que ela
é equivalente a x ≥ log x, o que é de fato verdade para x ≥ 1. Segue do Teorema 10.2.6 que
(x + 1) log(x2 + 1) = O(x2 ). ■
■ Exemplo 10.2.13 Vimos no Exemplo 10.2.11 que a função x3 + 2x2 + 1 é Ω(x3 ). Por outro lado,
temos do Teorema 10.2.3 que x3 + 2x2 + 1 é O(x3 ), portanto segue que x3 + 2x2 + 1 é Θ(x3 ), isto é,
x3 + 2x2 + 1 é da ordem de x3 . ■
O Exemplo 10.2.13 é um caso particular do teorema abaixo, que fornece a ordem de crescimento
de polinômios no caso mais geral.
Teorema 10.2.14 Seja f (x) = an xn + an−1 xn−1 + · · · a1 x + a0 , onde a j é um número real para
todo j. Então f (x) é da ordem de xn .
seção são válidas a partir de certo ponto: por exemplo, se um algoritmo de ordenação é mais eficaz
que um outro apenas para listas de n ≥ 10200 números, tal situação pode nunca se apresentar na
prática.
Cabe ressaltar também que a complexidade de pior caso de um algoritmo pode ser uma
estimativa demasiado pessimista do seu tempo de execução. É possível que um algoritmo tenha
complexidade de tempo de pior caso Θ(n2 ), mas isso ocorra apenas em raríssimos casos; se sua
complexidade de caso médio, que estima seu tempo de execução típico para uma entrada de tamanho
n, é Θ(n log n), esta última estimativa pode ser mais útil para uma análise de sua viabilidade em uma
aplicação em que o algoritmo é acionado repetidas vezes para resolver o problema em questão.