Livro 3 - Matemática Discreta

Prévia do material em texto

WELINGTON SANTOS
MATEMÁTICA DISCRETA
Código Logístico
59915
Fundação Biblioteca Nacional
ISBN 978-65-5821-012-2
9 7 8 6 5 5 8 2 1 0 1 2 2
Matemática Discreta 
Welington Santos
IESDE BRASIL
2021
© 2021 – IESDE BRASIL S/A. 
É proibida a reprodução, mesmo parcial, por qualquer processo, sem autorização por escrito do autor e 
do detentor dos direitos autorais.
Projeto de capa: IESDE BRASIL S/A. Imagem da capa: devotchkah/a_slowik/envatoelements
Todos os direitos reservados.
IESDE BRASIL S/A. 
Al. Dr. Carlos de Carvalho, 1.482. CEP: 80730-200 
Batel – Curitiba – PR 
0800 708 88 88 – www.iesde.com.br
CIP-BRASIL. CATALOGAÇÃO NA PUBLICAÇÃO 
SINDICATO NACIONAL DOS EDITORES DE LIVROS, RJ
S239m
Santos, Welington
Matemática discreta / Welington Santos. - 1. ed. - Curitiba [PR] : Iesde, 
2021.
136 p. : il.
Inclui bibliografia
ISBN 978-65-5821-012-2
1. Matemática. 2. Lógica simbólica e matemática. 3. Teoria dos conjun-
tos. 4. Análise combinatória. 5. Funções (Matemática). I. Título.
21-69713 CDD: 510
CDU: 51
Welington Santos Doutor e Mestre em Matemática pela Universidade 
Federal do Paraná (UFPR). Graduado em Licenciatura 
em Matemática pela Universidade Estadual de Ponta 
Grossa (UEPG). Participou de programa de doutoramento 
sanduíche na Universidade de Maryland, EUA. Tem 
experiência na área de Matemática com ênfase em 
Teoria algébrica dos códigos corretores de erros, Teoria 
de invariantes, Self-dual codes, Decodificação fracionária 
e Teoria de matróides. Tem experiência em ensino 
superior, ministrando aulas no formato presencial e a 
distância.
SUMÁRIO
1 Fundamentos de lógica matemática e métodos de demonstração 9
1.1 Fundamentos de lógica matemática 9
1.2 Demonstração direta e demonstração por contraposição 20
1.3 Demonstração por contradição 24
1.4 Demonstração por absurdo 25
1.5 Demonstração por indução finita 26
2 Teoria de conjuntos 30
2.1 Noção intuitiva de conjuntos 30
2.2 Descrição e igualdade de conjuntos 31
2.3 Subconjuntos 34
2.4 Operações com conjuntos 36
3 Conjuntos numéricos 47
3.1 Conjunto dos números naturais 47
3.2 Conjunto dos números inteiros 51
3.3 Conjunto dos números racionais 54
3.4 Números reais e cardinalidade 56
3.5 Aritmética modular 58
4 Relações 61
4.1 Produto cartesiano e par ordenado 61
4.2 Conceito de relação 64
4.3 Relação inversa 68
4.4 Propriedades das relações 69
4.5 Operações e fecho de relações 72
4.6 Relação de ordem e de equivalência 74
5 Funções discretas 80
5.1 Conceito e classificação 80
5.2 Função composta e função inversa 85
5.3 Funções recursivas 89
6 Análise combinatória 92
6.1 Princípios de contagem 92
6.2 Arranjos 97
6.3 Permutações 99
6.4 Combinações 102
6.5 Binômio de Newton 106
6 Matemática Discreta
7 Funções geradoras e partição de um inteiro 112
7.1 Funções geradoras 112
7.2 Operações com funções geradoras 114
7.3 Funções geradoras exponenciais 120
7.4 Sequência de Fibonacci 123
7.5 Partição de um inteiro 124
7.6 Gráfico de uma partição 126
 Gabarito 129
APRESENTAÇÃO
Esta obra oferece uma abordagem introdutória à matemática discreta, 
área da matemática dedicada ao estudo de objetos que são formados 
por elementos desconexos entre si, chamados de elementos discretos. 
Apresentamos, com detalhes, conceitos fundamentais de teoria de 
conjuntos, conjuntos numéricos e aritmética modular, diferentes problemas 
de combinatória e funções úteis para a resolução de problemas de contagem. 
Para tanto, no primeiro capítulo, discorremos sobre os fundamentos 
básicos da lógica matemática, apresentando operações entre proposições 
lógicas e suas implicações nas técnicas de demonstração para resultados 
matemáticos. 
A matemática é fundamentada por axiomas, lemas, corolários e 
teoremas, que são validados por meio das demonstrações. Nesse sentido, 
ao longo de toda a obra, apresentamos e aplicamos as principais técnicas de 
demonstração (direta, contraposição, contradição, absurdo e indução) para 
provar fatos bem conhecidos da matemática. 
No segundo capítulo, abordamos a teoria fundamental de conjuntos, que 
embasa toda a matemática discreta, apresentando as técnicas básicas de 
contagem do número de elementos dos conjuntos e as principais operações 
entre eles, como a intersecção, a união e a diferença. 
O terceiro capítulo propõe um estudo aprofundado dos principais 
conjuntos numéricos, explorando as diferentes propriedades e operações 
que cada um desses conjuntos possui. Além disso, classificamos os 
conjuntos numéricos em termos de sua cardinalidade, descrevendo o 
conceito de conjunto enumerável e não enumerável. Diante da importância 
da aritmética modular em problemas que envolvem contagem, discorremos 
detalhadamente sobre essa matéria, que é observada na leitura de um CD e 
na validação do número do Cadastro de Pessoa Física (CPF).
No quarto capítulo, com objetivo de introduzir o conceito de relações 
entre conjuntos, nos debruçamos sobre a operação de produto cartesiano 
entre conjuntos. Além disso, apresentamos as principais propriedades das 
relações entre conjuntos e dois tipos especiais de relação: relação de ordem 
e de equivalência, que são utilizadas na alocação de frota de empresas 
aéreas, por exemplo.
No quinto capítulo, utilizamos o conceito de relações entre conjuntos 
para definir funções discretas, apresentando os principais elementos que 
compõem uma função: domínio, contradomínio e imagem. Exploramos 
também as principais propriedades operatórias entre funções. Por fim, 
apresentamos os fundamentos básicos de funções recursivas, apontando 
sua aplicação para a criação de sequências numéricas, como a famosa 
sequência de Fibonacci.
Vídeo
8 Matemática Discreta
No sexto capítulo, nos debruçamos sobre os princípios fundamentais de contagem: 
princípio da adição, da subtração, da multiplicação e o princípio da casa dos pombos, 
exibindo exemplos de aplicações para cada um deles. Além disso, o capítulo define, 
classifica e ilustra diferentes problemas de contagem. Por fim, são exploradas as principais 
propriedades do binômio de Newton e do teorema multinomial.
No capítulo final, abordamos a função geradora ordinária de uma sequência numérica, 
identificando as relações entre operação com sequências numéricas e funções geradoras. 
Exibimos, por meio de exemplos, como podemos utilizar funções geradoras para 
solucionar problemas de contagem. Por fim, as ideias básicas de partição de um número 
inteiro são apresentadas.
O livro também apresenta, ao final de cada capítulo, exercícios cuidadosamente 
selecionados para que você exercite e explore, na prática, os temas apresentados. 
Bons estudos!
Fundamentos de lógica matemática e métodos de demonstração 9
1
Fundamentos de lógica 
matemática e métodos 
de demonstração
Você já se perguntou como surgiram as diversas fórmulas da ma-
temática, como as famosas fórmulas de Bhaskara e de Pitágoras? Já 
imaginou o porquê de elas sempre funcionarem? Isso se deve ao fato 
de que essas (e muitas outras) fórmulas foram demonstradas, isto é, 
alguém, utilizando um método lógico dedutivo, provou que elas são 
sempre válidas.
Neste capítulo, você irá aprender os principais fundamentos da lógica 
matemática, por exemplo, qual é o principal objetivo de se estudá-la, o 
que é um paradoxo, o que é uma proposição e como podemos operar 
com proposições. Além disso, aprenderá os principais métodos de de-
monstrações, isto é, as principais técnicas utilizadas para demonstrar que 
alguma fórmula ou propriedade é verdadeira. Por fim, você realizará suas 
primeiras demonstrações matemáticas.
1.1 Fundamentos de lógica matemática
Vídeo A lógica matemática teve origem no século IV antes de Cristo na Grécia Antiga, 
com os trabalhos de Parmênides (530-460 a.C) e Zenão (510-470 a.C), mas ganhou 
status de ciência apenas após os trabalhos do filósofo Aristóteles (384-322 a.C), 
em especial na obra Organum, na qual ele estabelece os princípios dela e, poresse 
motivo, é chamado de pai da lógica matemática.
O norte da lógica matemática é a busca pela verdade; sendo assim, possui como 
objeto de estudo as leis de formação do pensamento e as regras para se aplicar 
essas leis para investigar a verdade. Outro grande objetivo dessa ciência é entender 
como podemos utilizar noções previamente estabelecidas como verdadeiras para 
deduzir novos conhecimentos.
Com o objetivo de estudar a verdade, precisamos definir o principal objeto de 
estudo da lógica matemática: as proposições.
10 Matemática Discreta
Definição
Uma proposição é uma declaração que pode ser verdadeira ou falsa.
De modo mais preciso, poderíamos dizer que uma proposição é um conjunto de 
símbolos e palavras que exprimem um pensamento, o qual pode ser verdadeiro ou 
falso. Observe os seguintes exemplos de proposições.
Σxemρlo 1
São proposições:
 • p: Tóquio é a capital da China.
 • q: Wellington é a capital da Nova Zelândia.
 • r: 1 + 5 = 6.
 • s: π < 3.
Cada uma das proposições do exemplo anterior exprime um pensamento, al-
guns verdadeiros, como os pensamentos expressos nas proposições q e r, e alguns 
falsos, como nas proposições p e s. Assim, dizemos que as proposições q e r pos-
suem valor lógico verdadeiro (V) e a as proposições p e s possuem valor lógico 
falso (F).
É possível escrevermos sentenças que não possuem nem valor lógico verdadei-
ro nem valor lógico falso. Essas sentenças não são proposições e são conhecidas 
como paradoxos. Existem alguns exemplos bem conhecidos, os quais são muito 
utilizados na música e na literatura. Vejamos:
 • “O amor é ferida que dói e não se sente” – Luís Vaz de Camões.
 • “Estou cego e vejo” – Carlos Drummond de Andrade.
 • “Já estou cheio de me sentir vazio” – Renato Russo.
Note que não podemos atribuir um valor lógico verdadeiro ou falso para a frase 
de Carlos Drummond de Andrade, pois estar cego e ver é um paradoxo.
A seguir vamos analisar o paradoxo conhecido como paradoxo do mentiroso.
Σxemρlo 2
Considere a seguinte sentença: Esta frase não é verdadeira.
Agora, faça a análise desse paradoxo.
Fundamentos de lógica matemática e métodos de demonstração 11
Note que, se a sentença é verdadeira, então, pelo seu significado, a sentença é 
falsa e isso é uma contradição. Semelhantemente, se a sentença for falsa, então o 
que ela diz não é fato e, assim, a sentença é verdadeira, ou seja, temos novamente 
uma contradição e, portanto, um paradoxo.
A lógica matemática adota alguns axiomas, que são proposições presumida-
mente assumidas como verdadeiras, porque se acredita que são de alguma forma 
razoáveis, por exemplo, o seguinte axioma de Euclides: “pode-se traçar uma única 
reta ligando dois pontos quaisquer”.
Os dois princípios fundamentais da lógica matemática são:
Princípio da não contradição Princípio do terceiro excluído
Uma proposição não pode ter valor 
lógico verdadeiro e falso ao mesmo 
tempo. Por definição, exclui-se a 
possibilidade de um paradoxo ser 
uma proposição.
Toda proposição ou é verdadeira ou 
é falsa, não havendo possibilidade 
de assumir outro valor lógico. Esse 
princípio diz que toda proposição não 
abre espaço para interpretação, isto 
é, ou a proposição é verdadeira ou 
é falsa; não existe a possibilidade de 
“talvez” e “depende”.
Assim como fazemos com pensamentos, podemos combinar mais de uma 
proposição para formar uma nova, chamada de proposição composta. Mais preci-
samente, dadas proposições simples p, q, r, s, t, ... podemos construir uma nova 
proposição P(p, q, r, s, t, ...), ou simplesmente P, formada pelas proposições simples 
que foram dadas.
Considere os seguintes exemplos de proposições simples:
 • p: Welington é professor de matemática.
 • q: Você é estudante de matemática.
 • r: Você será professor de matemática.
 • s: Você será engenheiro.
Com essas proposições podemos formar novas proposições compostas, como:
 • P(p, q): Welington é professor de matemática e você é estudante de matemática.
 • Q(s, r): Você será engenheiro ou você será professor de matemática.
 • R(q, r): Se você é estudante de matemática, então você será professor de 
matemática.
 • S(p, r): Welington é professor de matemática e você será professor de 
matemática.
Utilizamos algumas palavras para conectar as proposições simples p, q, r, s e 
produzirmos as proposições compostas P, Q, R, S. Essas palavras são chamadas de 
conectivos. Na lógica matemática existem cinco conectivos: e, ou, não, se… então, 
e se, e somente se.
O ato de combinar proposições é chamado de operação lógica e os conectivos de 
operadores. Para cada conector daremos um nome e um símbolo especial.
12 Matemática Discreta
O quadro a seguir apresenta as cinco operações lógicas, seus conectivos e res-
pectivos símbolos.
Quadro 1
Conectivos lógicos e seus símbolos
Conectivo Símbolo do conectivo Operação do conectivo
e ∧ Conjunção
ou ∨ Disjunção
não ∼ ou ¬ Negação
se… então → Condicional
se, e somente se ↔ Bicondicional
Fonte: Elaborado pelo autor.
Dada uma proposição lógica composta, iremos utilizar o valor lógico das pro-
posições simples que a compõem para determinar o seu valor lógico. Isso só será 
possível se as operações estiverem bem definidas. Para cada conjunto de proposi-
ções simples, com seus respectivos valores lógicos, obtemos um único valor lógico 
possível para a proposição composta.
Os valores lógicos das cinco operações lógicas são definidos como segue.
1. Negação
A negação da proposição p é a proposição ∼p (não p), cujo valor lógico é definido 
da seguinte forma:
 • O valor lógico de ∼p é verdadeiro se o valor lógico de p for falso.
 • O valor lógico de ∼p é falso se o valor lógico de p for verdadeiro.
Podemos organizar essa informação em uma tabela, a qual é chamada de 
tabela-verdade da proposição ∼p.
p ~p
V F
F V
Vejamos no exemplo a seguir como aplicar a tabela-verdade da negação para 
encontrar o valor lógico de uma proposição composta formada pela negação de 
uma proposição dada.
Σxemρlo 3
Considere a proposição p: Tóquio é a capital da China. Encontre o valor lógico da 
negação da proposição dada.
Fundamentos de lógica matemática e métodos de demonstração 13
Sabemos que p tem valor lógico falso (F); sendo assim, o valor lógico da proposi-
ção ~p: Não é verdade que Tóquio é a capital da China tem valor lógico verdadeiro (V).
2. Conjunção
A conjunção das proposições p e q é a proposição p ∧ q (p e q), cujo valor lógico 
é definido da seguinte maneira:
 • O valor lógico de p ∧ q é verdadeiro se os valores lógicos de p e q são verdadeiros.
 • O valor lógico de p ∧ q é falso se o valor lógico de p ou de q é falso.
A tabela-verdade da proposição p ∧ q é apresentada a seguir:
p q p ∧ q
V V V
V F F
F V F
F F F
Vejamos no exemplo a seguir como aplicar a tabela-verdade da conjunção para 
encontrar o valor lógico de uma proposição composta formada pela conjunção de 
duas proposições simples dadas.
Σxemρlo 4
Considere as proposições p: Welington é professor de matemática, q: Wellington 
é capital da Nova Zelândia e s: π < 3. Encontre o valor lógico de p ∧ q, p ∧ s e q ∧ s.
Sabemos que p tem valor lógico (V), q tem valor lógico (V) e s tem valor lógico (F). 
Sendo assim, p ∧ q tem valor lógico (V), p ∧ s tem valor lógico (F), q ∧ s tem valor 
lógico (F).
3. Disjunção
A disjunção das proposições p e q é a proposição p ∨ q (p ou q), cujo valor lógico 
é definido do seguinte modo:
 • O valor lógico de p ∨ q é verdadeiro se o valor lógico de p é verdadeiro ou o 
valor lógico de q é verdadeiro.
 • O valor lógico de p ∨ q é falso se o valor lógico de p é falso e o valor lógico de 
q é falso.
A tabela-verdade da proposição p ∨ q é apresentada a seguir:
14 Matemática Discreta
p q p ∨ q
V V V
V F V
F V V
F F F
Vejamos no exemplo a seguir como aplicar a tabela-verdade da disjunção para 
encontrar o valor lógico de uma proposição composta formada pela disjunção de 
duas proposições simples dadas.
Σxemρlo 5
Considere as proposições p: Welington é professor de matemática,q: Wellington 
é capital da Nova Zelândia e s: π < 3. Encontre o valor lógico de p ∨ q, p ∨ s e q ∨ s.
Sabemos que p tem valor lógico (V), q tem valor lógico (V) e s tem valor lógico 
(F). Sendo assim, p ∨ q tem valor lógico (V), p ∨ s tem valor lógico (V), q ∨ s tem valor 
lógico (V).
4. Condicional
A condicional das proposições p e q é a proposição p → q (se p então q), cujo 
valor lógico é definido da seguinte forma:
 • O valor lógico de p → q é verdadeiro se p e q são verdadeiros.
 • O valor lógico de p → q é verdadeiro sempre que p é falso.
 • O valor lógico de p → q é falso se p é verdadeiro e q é falso.
A seguir representamos a tabela-verdade da proposição p → q.
p q p → q
V V V
V F F
F V V
F F V
Vejamos no exemplo a seguir como aplicar a tabela-verdade da condicional para 
encontrar o valor lógico de uma proposição composta formada pela condicional 
p → q de duas proposições simples.
Σxemρlo 6
Considere as proposições p: Welington é professor de matemática, q: Wellington 
é capital da Nova Zelândia e s: π < 3. Encontre o valor lógico de p → q, p → s e s → q.
Fundamentos de lógica matemática e métodos de demonstração 15
Sabemos que p tem valor lógico (V), q tem valor lógico (V) e s tem valor lógico (F). 
Sendo assim, p → q tem valor lógico (V), p → s tem valor lógico (F), s → q tem valor 
lógico (V).
5. Bicondicional
A bicondicional de duas proposições p e q é a proposição p ↔ q (p se, e somente 
se, q), cujo valor lógico é definido da seguinte maneira:
 • O valor lógico de p ↔ q é verdadeiro se p e q são verdadeiros.
 • O valor lógico de p ↔ q é verdadeiro se p e q são falsos.
 • O valor lógico de p ↔ q é falso se p é verdadeiro e q é falso.
 • O valor lógico de p ↔ q é falso se p é falso e q é verdadeiro.
A seguir, representamos a tabela-verdade da proposição p ↔ q.
p q p ↔ q
V V V
V F F
F V F
F F V
Vejamos no exemplo a seguir como aplicar a tabela-verdade da bicondicional 
para encontrar o valor lógico de uma proposição composta formada pela bicondi-
cional p ↔ q de duas proposições simples.
Σxemρlo 7
Considere as proposições p: Welington é professor de matemática, q: Welling-
ton é capital da Nova Zelândia e s: π < 3. Encontre o valor lógico de p ↔ q, p ↔ s e 
s ↔ q.
Sabemos que p tem valor lógico (V), q tem valor lógico (V) e s tem valor lógico (F). 
Sendo assim, p ↔ q tem valor lógico (V), p ↔ s tem valor lógico (F), s ↔ q tem valor 
lógico (F).
Podemos construir tabelas-verdade de proposições compostas forma-
das por mais de duas proposições simples. Nesse caso, o número de linhas da 
tabela-verdade vai depender do número de proposições simples; mais especifica-
mente, o número de linhas da tabela-verdade da proposição composta P será 2n, 
onde n é o número de proposições simples que a compõem.
Vejamos um exemplo:
16 Matemática Discreta
Σxemρlo 8
Sejam p, q e r três proposições simples, vamos construir a tabela-verdade da 
proposição composta P(p, q, r): p ∧ r → ~q ∨ r. Primeiro note que o número de 
linhas da tabela-verdade será 2³. Além disso, teremos as colunas p, q, r, ~q, p ∧ r, 
~q ∨ r e P: p ∧ r → ~q ∨ r.
Mais precisamente, a tabela-verdade de P(p, q, r) é:
p q r ~q p ∧ r ~q ∨ r P
V V V F V V V
V V F F F F V
V F V V V V V
V F F V F V V
F V V F F V V
F V F F F F V
F F V V F V V
F F F V F V V
Observamos que a última coluna da tabela-verdade de P(p, q, r): p ∧ r → ~q ∨ r 
possui apenas valor lógico verdadeiro. Nesse caso, dizemos que P é uma tautologia. 
Por outro lado, chamaremos de contradição toda proposição composta P que pos-
sui apenas valor lógico falso na última coluna de sua tabela-verdade.
Podemos então utilizar a tabela-verdade para verificarmos se uma proposição 
composta é verdadeira ou não. Para tanto, basta considerarmos o valor lógico 
da última coluna da linha referente aos valores lógicos das proposições simples 
que a compõem. Por exemplo, se considerarmos p: Welington é professor de 
matemática (V), q: Wellington é capital da Nova Zelândia (V) e s: π < 3 (F), teremos 
que o valor lógico de P(p, q, r): p ∧ r → ~q ∨ r será (V). Basta olharmos para a segun-
da linha de sua tabela-verdade.
Durante a construção da tabela-verdade do exemplo anterior você deve ter 
se perguntado: “como saberei qual operação lógica irei realizar primeiro?”. Assim 
como acontece nas operações com números reais, as operações lógicas possuem 
uma ordem de preferência para serem realizadas. A ordem de preferência para 
operações lógicas é a seguinte: negação, conjunção, disjunção, condicional, bicon-
dicional, sempre dando preferência para as operações entre parênteses.
Fundamentos de lógica matemática e métodos de demonstração 17
Definição
Duas proposições compostas P e Q são chamadas de logicamente equivalentes se a tabela-verdade de 
P ↔ Q é uma tautologia. Nesse caso, escrevemos que P ≡ Q são logicamente equivalentes.
A seguir apresentamos dois exemplos de proposições equivalentes. Esses dois 
exemplos são conhecidos como Leis de De Morgan e são superimportantes. Cons-
truiremos a tabela-verdade de uma delas para comprovar que realmente temos 
uma equivalência lógica.
Σxemρlo 9
As seguintes equivalências lógicas são conhecidas como Leis de De Morgan.
 • ~(p ∨ q) ≡ ~p ∧ ~q.
 • ~(p ∧ q) ≡ ~p ∨ ~q.
Vamos verificar que o segundo item é realmente uma equivalência lógica. Por 
definição, devemos construir a tabela-verdade de P: ~(p ∧ q) ↔ ~p ∨ ~q e verificar 
que temos uma tautologia.
p q ∼p ∼q p ∧ q ∼(p ∧ q) ∼p ∨ ∼q P
V V F F V F F V
V F F V F V V V
F V V F F V V V
F F V V F V V V
Observamos que P é uma tautologia; sendo assim, temos a seguinte equivalên-
cia: ~(p ∧ q) ≡ ~p ∨ ~q.
Como já foi comentado, podemos utilizar a tabela-verdade para analisar o valor 
lógico de uma proposição composta. A seguir, apresentamos um exemplo de como 
isso funciona para proposições matemáticas.
Σxemρlo 10
Sejam p: π < 3 e q: 1 + 2 = 4 duas proposições matemáticas, vamos analisar o 
valor lógico de P(p, q): ~p ∧ q ↔ ~q ∧ p.
Agora é com você: construa a 
tabela-verdade para provar que a 
primeira Lei de De Morgan, apre-
sentada no exemplo, realmente é 
uma equivalência lógica.
Desafio
18 Matemática Discreta
Inicialmente, vamos traduzir P(p, q) em uma sentença matemática (traduzindo 
os conectivos para a linguagem formal). Temos que:
 • ~p: π ≥ 3.
 • ~q: 1 + 2 ≠ 4.
 • ~p ∧ q: π ≥ 3 e 1 + 2 = 4.
 • ~q ∧ p: 1 + 2 ≠ 4 e π < 3.
Então, P(p, q): π ≥ 3 e 1 + 2 = 4 se, e somente se, 1 + 2 ≠ 4 e π < 3.
Vamos agora construir a tabela-verdade de P(p, q).
p q ∼p ∼p ∧ q ∼q ∼q ∧ p P(p, q)
V V F F F F V
V F F F V V F
F V V V F F F
F F V F V F V
Para analisarmos o valor lógico da proposição composta P(p, q) basta olharmos 
para os valores lógicos das proposições simples p e q. Sabemos que ambas, p e 
q, são falsas. Sendo assim, o valor lógico de P(p, q) está na quarta linha de sua 
tabela-verdade (a linha onde os valores lógicos de p e q são falsos), ou seja, P(p, q) 
tem valor lógico verdadeiro.
Você deve estar se perguntando: “sempre terei que construir a tabela-verdade 
para provar que uma proposição matemática é verdadeira?”. A resposta para 
essa questão é não. Nas próximas seções deste capítulo iremos aprender mé-
todos e linhas de raciocínio lógico que são utilizados para provar que uma pro-
posição matemática é verdadeira. Esses métodos são conhecidos como métodos 
de demonstração.
Antes de iniciarmos o estudo sobre os métodos de demonstração, precisamos 
estabelecer a estrutura de uma proposição matemática e algumas nomenclaturas.
Toda proposição matemática tem sua estrutura formada por uma hipótese, a qual é a premissa que assu-
mimos como verdadeira, e por uma tese, uma afirmação que queremos provar utilizando nossa hipótese.
Observe a seguinte proposição que estabelece a fórmula de Bhaskara:
Seja ax² + bx + c = 0, com a ≠ 0, uma equação do segundo grau, então:
x b� � b � ac
a
�
�
� � �2 4
2
Nessa proposição, nossa hipótese é “p: ax² + bx + c = 0, com a ≠ 0, é uma 
equação do segundo grau” e nossa tese é “q:x b b ac
a
�
� � �2 4
2
”.
Fundamentos de lógica matemática e métodos de demonstração 19
As proposições matemáticas recebem nomes especiais conforme seu grau de 
importância.
Como vimos, os axiomas são proposições presumidamente assumidas como verdadeiras, ou seja, 
que não requerem provas.
Observe os seguintes exemplos de axiomas da adição de números reais:
 • Associatividade: sejam a, b, c ∈ ℝ, tem-se (a + b) + c = a + (b + c).
 • Comutatividade: sejam a, b ∈ ℝ, tem-se a + b = b + a.
Um teorema é uma sentença matemática que pode ser provada como verdadeira.
Podemos citar como exemplo o famoso Teorema de Pitágoras: em qualquer 
triângulo retângulo, o quadrado do comprimento da hipotenusa é igual à soma dos 
quadrados dos comprimentos dos catetos.
Um lema é um teorema de menor importância que pode ser utilizado para demonstrar teoremas 
mais importantes.
Nesse sentido, ao nos depararmos com um teorema complicado, para realizar-
mos a sua demonstração de modo simples, o dividimos em vários lemas. Como 
exemplo, vamos considerar o importantíssimo lema que é utilizado para demons-
trar o algoritmo da divisão de números inteiros.
Lema – Método de divisão de Euclides
Sejam a e b inteiros, tais que a ≥ 0 e b > 0, então existem q e r, quociente e resto 
respectivamente, tais que a = bq + r e 0 ≤ r < b.
Um corolário é uma proposição que pode ser provada diretamente de um teorema mais importante 
já demonstrado.
Tomemos como exemplo o seguinte corolário do Teorema de Pitágoras: seja d 
a diagonal de um quadrado de lado l, então d = l√2.
Estabelecida a estrutura de uma proposição matemática e sua nomenclatura, 
iremos estudar a seguir os métodos de demonstração.
20 Matemática Discreta
1.2 Demonstração direta e demonstração 
por contraposiçãoVídeo
Podemos representar a fórmula de Bhaskara pela proposição composta 
p → q, onde p: ax² + bx + c = 0, com a ≠ 0, é uma equação do segundo grau e 
q: x �b� � b � � ac
a
�
� � �2 4
2
. Demonstrar a fórmula de Bhaskara é, portanto, assumir que 
p é verdade e provar que q também é verdade.
Utilizar uma sequência lógica de pensamentos para, com base na hipótese, pro-
var que a conclusão é verdadeira é conhecido como método de demonstração 
direta. Esse tipo de demonstração consiste em utilizar as particularidades da hi-
pótese para provar a tese. Vamos apresentar alguns exemplos de demonstrações 
diretas, inclusive uma demonstração para a famosa fórmula de Bhaskara.
Σxemρlo 11
Considere as definições de números inteiros pares e ímpares:
 • Um número inteiro n é par se existe um k ∈ ℤ tal que n = 2k.
 • Um número inteiro m é ímpar se existe um t ∈ ℤ tal que m = 2t + 1.
Demonstre os teoremas a seguir:
a. Se a e b são dois números inteiros ímpares, então o produto ab é um número ímpar.
b. Se a e b são dois números inteiros pares, então o produto ab é um número par.
a. Demonstração
Considere a e b dois números inteiros ímpares. Pela definição de número inteiro 
ímpar, sabemos que a = 2t1 + 1 e b = 2t2 + 1. Logo, o produto ab é
ab = (2t1 + 1)(2t2 + 1) = 2t12t2 + 2t1 + 2t2 + 1 = 2(2t1t2 + t1 + t2) + 1, ou seja,
ab = 2t3 + 1, onde t3 = 2t1t2 + t1 + t2.
Isso mostra que ab tem a forma de um número inteiro ímpar. Podemos assim 
concluir que ab é um número inteiro ímpar.
b. Demonstração
Sejam a e b dois números inteiros pares, pela definição de número inteiro par, 
sabemos que a = 2k1 e b = 2k2. Logo, o produto ab é
ab = (2k1)(2k2) = 2(2k1k2), ou seja, ab = 2k3, onde k3 = 2k1k2.
Isso mostra que ab tem a forma de um número inteiro par. Podemos concluir, 
portanto, que ab é um número inteiro par.
Vamos provar propriedades análogas aos teoremas anteriores, porém com 
relação à soma de números inteiros.
Fundamentos de lógica matemática e métodos de demonstração 21
Σxemρlo 12
Demonstre os seguintes teoremas sobre a soma de números inteiros:
a. Se a e b são dois números inteiros ímpares, então a soma a + b é um número 
inteiro par.
b. Se a e b são dois números inteiros pares, então a soma a + b é um número 
inteiro par.
a. Demonstração
Considere a e b dois números inteiros ímpares. Pela definição de número inteiro 
ímpar sabemos que a = 2t1 + 1 e b = 2t2 + 1. Logo, a soma a + b é
a + b = (2t1 + 1) + (2t2 + 1) = 2(t1 + t2) + 2 = 2(t1 + t2 + 1), ou seja,
a + b = 2k3, onde k3 = t1 + t2 + 1
Isso mostra que a + b tem a forma de um número inteiro par. Podemos assim 
concluir que a + b é um número inteiro par.
b. Demonstração
Sejam a e b dois números inteiros pares, pela definição de número inteiro par, 
sabemos que a = 2k1 e b = 2k2. Logo, a soma a + b é:
a + b = (2k1) + (2k2) = 2(k1 + k2), ou seja, a + b = 2k3, onde k3 = k1 + k2
Isso mostra que a + b tem a forma de um número inteiro par. Podemos, portanto, 
concluir que a + b é um número inteiro par.
Vamos agora demonstrar a famosa fórmula de Bhaskara.
Teorema (Fórmula de Bhaskara)
Seja ax² + bx + c = 0, com a ≠ 0, uma equação do segundo grau, então,
x b� � b � � ac
a
�
� � �2 4
2
Demonstração
Consideremos a equação ax² + bx + c = 0, com a ≠ 0. Vamos aplicar várias opera-
ções nessa equação para chegarmos a nossa tese.
ax bx c �2 0� � � � �÷a
� � � �
a
a
x b
a
x c
a a
��������������������2 0
 
� � � �
�
�
��
�
�
��x
b
a
x c
a
2 + b
4a
2
2
� � � � �x b
a
x b
4a
c
a
+ b
4a
�
2 2
2
2 2
22 Matemática Discreta
� �
�
�
�
�
�
� �
�x b
a
b ac
a2
4
4
2 2
2
� �
�
�
�
�
�
� �
�x b
a
b ac
a2
4
4
2 2
2
� �
�
�
�
�
�
� � �
�x b
a
�� b ac
a
��
2
4
4
2
2
 
� �
�
�
�
�
�
� � �
�� x b
a
�� b ac
a2
4
2
2
� � � �
�x b
a
b ac
a
�
2
4
2
2
� x � b b ac
a
�� � � � �
2 4
2
Sendo assim, utilizamos nossa hipótese para provar que nossa tese é verdadeira, 
ou seja, a fórmula de Bhaskara é verdadeira.
Durante a demonstração da fórmula de Bhaskara você deve ter percebido que 
há casos em que demonstrar um teorema pelo método direto pode não ser algo 
simples. Podemos contornar esse fato utilizando o método de demonstração por 
contraposição. Esse método consiste na seguinte tautologia: P: p → q ↔ ∼q → ∼p.
Vamos verificar, por meio de sua tabela-verdade, que P é realmente uma 
tautologia.
p q ~p ~q p → q ∼q → ∼p P
V V F F V V V
V F F V F F V
F V V F V V V
F F V V V V V
Como todos os valores lógicos da última coluna da tabela-verdade de P são ver-
dadeiros, concluímos que P é realmente uma tautologia.
Vejamos um exemplo simples de como aplicar o método de demonstração por 
contraposição.
Σxemρlo 13
Considere as proposições p: João é curitibano e q: João é brasileiro, e a proposi-
ção composta dada por P: p → q. Aplique o método de demonstração por contra-
posição sem usar a tabela-verdade.
Fundamentos de lógica matemática e métodos de demonstração 23
A proposição composta P pode ser traduzida como P: Se João é curitibano, en-
tão João é brasileiro. Essa proposição é equivalente à proposição Q: ~q → ~p, que 
traduzida é Q: Se João não é brasileiro, então João não é curitibano. Claramente, P 
é verdadeira sempre que Q é verdadeira e vice-versa.
Vamos agora aplicar o método de demonstração por contraposição para provar 
o seguinte teorema:
Teorema
Se a é um número natural e a² é par, então a é um número par.
Demonstração
Nossa proposição é “p: a² é par → q: a é par”. Vamos demonstrar que a propo-
sição equivalente “∼q: a é ímpar → ∼p: a² é ímpar” é verdadeira. Com efeito, se a é 
ímpar existe k natural tal que a = 2k + 1.
Logo, a² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1 = 2k2 + 1, onde k2 = 2k² + 2k, 
ou seja, a² é um número ímpar, provando que a contrapositiva do teorema é 
verdadeira. Podemos então concluir que o teorema é verdadeiro.
Definição 
Dizemos que um número a não é múltiplo de b se a divisão de a por b tem resto diferente de zero. Um núme-
ro a não é múltiplo de b se a = kb + r, onde 0 < r < b. Por exemplo, 7 não é múltiplo de 3, pois 7 = 2(3) + 1.
Vamos demonstrar o seguinte teorema pelo método da contrapositiva.
Teorema
Se a é um número natural e a³ é múltiplo de três, então a é um múltiplo detrês.
Demonstração
Nossa proposição é “p: a³ é múltiplo de 3 → q: a é múltiplo de 3”. Vamos de-
monstrar que a proposição equivalente “~q: a não é múltiplo de 3 → ∼p: a³ não é 
múltiplo de 3” é verdadeira. Com efeito, note que se a não é múltiplo de 3, então 
a = 3k1 + 1 ou a = 3k2 + 2. Analisando ambos os casos:
 • Se a = 3k1 + 1, temos:
a³ = (3k1 + 1)³
= (3k1 + 1)² (3k1 + 1)
= 27k1³ + 9k1² + 9k1 + 1
= 3(9k1³ + 3k1² + 3k1) + 1
= 3k3 + 1
Onde k3 = 9k1³ + 3k1² + 3k1.
Existe mais de uma 
maneira de se demons-
trar um teorema! Um dos 
teoremas mais impor-
tantes que estudamos e 
ensinamos para os alunos 
da educação básica é o 
Teorema de Pitágoras. 
Na página Decifrando a 
Matemática, da Unicamp, 
você vai encontrar vários 
caminhos diferentes para a 
demonstração do Teorema 
de Pitágoras, além de 
encontrar boas aborda-
gens para o ensino desse 
teorema.
Disponível em: www.ime.unicamp.
br/~apmat/teorema-de-pitagoras/. 
Acesso em: 5 mar. 2021.
Saiba mais
http://www.ime.unicamp.br/~apmat/teorema-de-pitagoras/
http://www.ime.unicamp.br/~apmat/teorema-de-pitagoras/
24 Matemática Discreta
 • Se a = 3k2 + 2, temos:
a³ = (3k2 + 2)³
= (3k2 + 2)²(3k2 + 2)
= 27k2³ + 18k2² + 36k2 + 6 + 2
= 3(9k2³ + 6k2² + 12k2 + 2) + 2
= 3k4 + 2
Onde k4 = 9k2³ + 6k2² + 12k2.
Sendo assim, a³ = 3k3 + 2 ou a³ = 3k4+2, provando que a³ não é múltiplo de três, 
ou seja, a contrapositiva do teorema é verdadeira. Podemos concluir, portanto, que 
o teorema é verdadeiro.
1.3 Demonstração por contradição
Vídeo Esse método consiste em utilizar uma contradição para mostrar que uma pro-
posição é verdadeira e tem como inspiração a seguinte tabela-verdade:
p q ~p ∼p → q
V V F V
V F F V
F V V V
F F V F
Observando as duas primeiras linhas da tabela-verdade, temos que p é verda-
deira sempre que ~p → q é verdadeira. Isso significa que para mostrarmos que 
uma proposição p é verdadeira, basta encontrarmos q, tal que ~p → q é verdadeira.
Resumidamente, o método de demonstração por contradição consiste em 
afirmar a hipótese, negar a tese e chegar a uma contradição. Vejamos alguns 
exemplos de aplicação do método de demonstração por contradição.
Σxemρlo 14
Utilize o método de demonstração por contradição para provar que o único 
número que, quando somado com ele mesmo, resulta no próprio número é o zero.
Queremos demonstrar o seguinte teorema: Se a + a = a, então a = 0. Para isso, 
vamos utilizar o método da demonstração por contradição. Nossa hipótese p é 
“a + a = a” e nossa tese q é “a = 0”. Vamos então negar q, ou seja, ~q: a ≠ 0.
Suponha então que a + a = a e a ≠ 0. Temos que 2a = a, e como a ≠ 0, podemos 
realizar a divisão por a (se a = 0, a divisão não pode ser realizada, afinal, não existe 
divisão por zero).
Fundamentos de lógica matemática e métodos de demonstração 25
Finalmente, 2a
a
a
a
= . Concluímos que 2 = 1. Isso é uma contradição; logo, não 
podemos ter a ≠ 0, então a = 0.
Agora, vamos utilizar o método de demonstração por contradição para demons-
trar o seguinte teorema, que já foi demonstrado pelo método de demonstração direta.
Σxemρlo 15
Utilize o método de demonstração por contradição para provar o seguinte teo-
rema: Se a e b são dois números inteiros pares, então a soma a + b é um número 
inteiro par.
Nossa hipótese é “p: a e b são números inteiros pares” e nossa tese é “q: a + b é 
um número inteiro par”. Vamos então negar q, isto é, ∼q: a + b é um número ímpar. 
Considere que:
 • a = 2k1
 • b = 2k2
 • a + b é um número ímpar
Logo, a + b = 2k3 + 1, onde, por um lado, a + b = 2k1 + 2k2 e, por outro lado, a + b = 2k3 + 1. 
Daí, 2k1 + 2k2 = 2k3 + 1 ⇒ 2(k1 + k2 - k3) = 1. Isso nos diz que 1 é um número par, obvia-
mente uma contradição, da qual obtemos que a + b é um número par.
1.4 Demonstração por absurdo
Vídeo Esse método consiste em assumir que a hipótese e a negação da tese são 
verdadeiras, para construir uma linha de raciocínio que nos leve a um absur-
do. A demonstração por absurdo tem como inspiração a seguinte tautologia 
P: (p → q) ↔ (p ∧ ∼q) → c, onde c é uma contradição. Essa tautologia pode ser veri-
ficada pela tabela-verdade a seguir.
p q c ∼q p ∧ ∼q p → q p ∧ ∼q → c P
V V F F F V V V
V F F V V F F V
F V F F F V V V
F F F V F V V V
Sendo assim, para demonstrar que um teorema é verdadeiro pelo método de 
demonstração por absurdo:
1. Assumimos que a hipótese e a negação da tese são verdadeiras.
2. Construímos uma linha de raciocínio de modo a encontrarmos um absurdo.
26 Matemática Discreta
Considere o seguinte exemplo de aplicação do método de demonstração por 
absurdo.
Σxemρlo 16
Demonstre o seguinte teorema pelo método de demonstração por absurdo: Se 
a é um número natural e a² é par, então a é um número par.
Para demonstrarmos por absurdo o teorema, temos que nossa hipótese é “p: a² 
é par” e nossa tese “q: a é par”. Suponha que p e ∼q, “a é ímpar”, sejam verdadeiras. 
Se a é ímpar, a = 2k1 + 1, de onde
a² = (2k1 + 1)²
= 4k1² + 4k1 + 1
= 2(2k1² + 2k1) + 1
= 2k2 + 1
Onde k2 = 2k1² + 2k
1. Isto é, a² é par e ímpar ao mesmo tempo. Um absurdo! 
Portanto, o teorema é válido.
1.5 Demonstração por indução finita
Vídeo Em matemática discreta os principais problemas de estudo são problemas de 
contagem em espaços discretos, por exemplo: o espaço formado por todas as ida-
des dos cidadãos brasileiros. Desse modo, o principal método de demonstração 
que utilizamos é o método da indução finita. Esse método é utilizado para de-
monstrar teoremas como os seguintes.
Teorema
A soma dos n primeiros números naturais é n n� ��� �1
2
.
Note que o teorema diz que se somarmos, por exemplo, 1 + 2 + 3 + 4 o resultado 
será 4 4 1
2
4 5
2
20
2
10
�� �
�
� �
� � .
Teorema
A soma dos quadrados dos n primeiros números naturais é n n n� � � ��� � �� �1 2 1
6
.
Utilizando o teorema podemos concluir, por exemplo, que a soma 1² + 2² + 3² é 
igual a 
3 3 1 2 3 1
6
3 4 7
6
14
�� � � � �� �
�
� �� �
� .
Mas como podemos demonstrar que esses teoremas são válidos para qualquer 
número? O método da indução finita consiste nos seguintes passos:
Fundamentos de lógica matemática e métodos de demonstração 27
Mostrar que o teorema é válido 
para o menor n possível que 
satisfaz a hipótese.
Assumir que o teorema é válido 
para n = k.
1
2
Utilizar o fato de o teorema ser 
válido para n = k para demonstrar 
que o teorema é verdadeiro para 
n = k + 1.
3
Podemos observar pelo passo 3 que a principal ideia da demonstração por 
indução finita é mostrar que o teorema é sempre válido para o próximo núme-
ro. Vamos utilizar o método de indução para demonstrar os teoremas utilizados 
como exemplos.
Teorema
A soma dos n primeiros números naturais é n n� ��� �1
2
.
Demonstração
Vamos inicialmente mostrar que o resultado é válido para n = 1. Se n = 1, temos 
que 1 = 
1 1� ��� �
�
1
2
2
2
 = 1, provando que o teorema é válido para n = 1.
Assumindo que o teorema é válido para n = k, ou seja, assumindo que
1 + 2 + 3 + ... + k = 
k k� ��� �1
2
Vamos mostrar que o teorema é válido para n = k + 1, ou seja, mostraremos que
1 + 2 + 3 + ... + k + (k + 1) = �
k� � k� ��� � �� �1 2
2
De fato,
� � � �k� �(k + 1) �
k k� �
� � k� �1 2 3
1
2
1� � � � � �
�� �
� �� �...
=�
k k� �
�
�� � � �1 2 1
2
( )k
=�
k� �
�
�� � �1 2
2
( )k
Provando assim que 1 + 2 + 3 + ... + k + (k + 1) = 
k� � k� ��� � �� �1 2
2
.
Desse modo, podemos concluir que o teorema é válido.
Finalizaremos esta seção com o seguinte teorema:
28 Matemática Discreta
Teorema
A soma dos quadrados dos n primeiros números naturais é 
n n� � n� ��� � �� �1 2 1
6
.
Demonstração
Inicialmente, vamos mostrar que o resultado é válido para n = 1. Se n = 1, temos que 
1² = 
1 1� � (1)� ��� � �� �
� �
1 2 1
6
12 3
6
6
6
( )( ) = 1, provando que o teorema é válido no caso n = 1.
Assumindo que o teorema é válido para n = k, ou seja, assumindo que
1² + 2² + 3² + ... + k² = k k� � k� ��� � �� �1 2 1
6
Mostraremos que o teorema é válido para n = k + 1, ou seja, que
1² + 2² + 3² + ... +k² + (k + 1)² = 
k� � k� � k� ��� � �� � �� �1 2 2 3
6
De fato,
1² + 2² + 3² + ... + k² + (k + 1)² = k k� � k� ��� � �� �1 2 1
6
 + (k + 1)²
�
�� � �� � � �k� � k� �1 2 1 6 1
6
[ ( )]k k
�
�� � � �� �k k k1 2 7 6
6
2
�
�� � �� � �� �k k k1 2 2 3
6
Provando, assim, que 1² + 2² + 3² + ... + k² + (k + 1)² = 
k� k� � k� ��� � �� � �� �1 2 2 3
6
.
Desse modo, podemos concluir que o teorema é válido.
CONSIDERAÇÕES FINAIS
Neste capítulo, aprendemos que, para afirmarmos que um teorema ou uma fórmu-
la é verdadeira ou não, precisamos realizar um procedimento matemático chamado 
de demonstração matemática, a qual consiste em provar que o teorema ou a fórmula é 
verdadeira para qualquer elemento que satisfaça suas hipóteses.
Estudamos que é importante conhecermos os diferentes métodos de demonstra-
ção, pois podemos utilizar qualquer um deles para mostrar que um teorema ou uma 
fórmula é verdadeira. Contudo, o ato de construir um raciocínio lógico para demons-
trar uma proposição torna-se mais fácil (ou mais difícil) conforme o método escolhido.
ATIVIDADES
1. Utilize a técnica de demonstração direta para provar os seguintes teoremas:
a) Se a é um número inteiro par e b é um número inteiro ímpar, então a soma 
a + b é um número inteiro ímpar.
b) Se a é um número inteiro par e b um número inteiro ímpar, então o produto 
ab é um número par.
O filme O homem que viu 
o infinito conta a história 
do matemático indiano 
Srinivasa Ramanujan (1887-
1920). No filme, podemos 
perceber a importância de 
uma boa escrita matemá-
tica, ou seja, saber fazer 
boas demonstrações. 
Apesar de ter boas ideias, 
Ramanujan sofreu muito 
em sua história como 
matemático pelo fato de 
não ter a capacidade de 
escrever boas demons-
trações.
Direção Matt Brown. Londres: Animus 
Films, 2016.
Filme
Fundamentos de lógica matemática e métodos de demonstração 29
2. Utilize a técnica de demonstração por contraposição para o seguinte teorema: Se a 
é um número natural e a² é ímpar, então a é um número ímpar.
3. Utilize a técnica de demonstração por contradição para provar o seguinte teorema: 
Se a é um número inteiro par e b é um número inteiro ímpar, então a soma a + b é 
um número inteiro ímpar.
4. Utilize a técnica de demonstração por indução para provar o seguinte teorema: Se 
n é um número natural, 1² + 3² + 5² + ... + (2n - 1)² = n 2n�-�1 2n�+�1
3
� �� � .
REFERÊNCIAS
FILHO, E. A. Iniciação à lógica matemática. São Paulo: Nobel, 2002.
GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5. ed. Boston: Addison-
Wesley, 2004.
ROSEN, K. H. Matemática discreta e suas aplicações. 6. ed. São Paulo: McGraw-Hill, 2009.
30 Matemática Discreta
2
Teoria de conjuntos
As ideias fundamentais da teoria dos conjuntos e da álgebra dos con-
juntos são provavelmente os conceitos mais importantes em todas as 
áreas da matemática, e isso não é diferente na matemática discreta.
Este capítulo apresenta a teoria dos conjuntos. O material é principal-
mente elementar. Lembre-se de que, em matemática, elementar não significa 
simples, mas sim que não requer vários conhecimentos prévios para ser com-
preendido. O material elementar pode ser bastante desafiador, e parte deste 
capítulo talvez exija que você ajuste seu ponto de vista para compreendê-lo. 
Um ponto em especial no qual este capítulo pode divergir da sua ex-
periência anterior com teoria de conjuntos é o fato de realizarmos a de-
monstração das propriedades elementares dos conjuntos. 
Neste capítulo você aprenderá a noção intuitiva de conjuntos, como 
descrever um conjunto e seus subconjuntos e, por fim, como realizar ope-
rações entre conjuntos e as principais propriedades dessas operações. 
2.1 Noção intuitiva de conjuntos
Vídeo Uma matilha, um cacho de uvas ou um bando de pombos são exemplos de con-
juntos. O conceito matemático de um conjunto pode ser expresso por meio desses 
exemplos. Porém, como definir um conjunto matemático?
Um conjunto matemático pode ser definido simplesmente como uma coleção 
de objetos diferentes, mais precisamente:
Definição
Um conjunto A é uma coleção de objetos distintos.
Vejamos o exemplo a seguir:
Σxemρlo 1
São exemplos de conjuntos:
 • A = {1, 2, 3, 4, 5}.
 • B = {quadrado, triângulo, circunferência}.
 • C = {Pedro, Maria, Welington}.
• Os conjuntos são denotados por 
letras maiúsculas A, B, C, … do 
nosso alfabeto.
• Os objetos de um conjunto A 
são chamados de elementos do 
conjunto.
• Se A é um conjunto formado 
pelos objetos a, b, c, d, escreve-
mos A = {a, b, c, d}.
Importante
Teoria de conjuntos 31
Precisamos prestar atenção a um fato bem importante na definição de conjun-
tos: em um conjunto não é permitida a repetição de elementos.
Σxemρlo 2
Não são conjuntos:
 • A = {1, 1, 2, 3, 4, 5}.
 • B = {quadrado, triângulo, triângulo, circunferência}.
 • C = {Pedro, Maria, Welington, Welington}.
Note que, no Exemplo 2, A, B e C não são conjuntos pelo fato de existirem repe-
tições entre seus elementos. Quando existem repetições de elementos, chamamos 
A, B e C de multiconjuntos. 
Um conjunto A = {a, b, c, d, …} com infinitos elementos é chamado de conjunto 
infinito.
• Se a é um elemento do conjunto 
A, escrevemos a ∈ A e dizemos 
que a pertence a A.
• Se A é um conjunto e b não é 
um elemento de A, escrevemos 
b ∉ A e dizemos que b não 
pertence a A.
Importante
2.2 Descrição e igualdade de conjuntos
Vídeo A maneira mais básica de se definir um conjunto é listar seus elementos entre 
chaves, por exemplo: A = {2, 4, 6, 8, 10}, como feito na seção anterior. Também 
podemos definir um conjunto fornecendo uma regra chamada lei de formação do 
conjunto, que determina com segurança se um objeto é um membro ou não, por 
exemplo: B = {x | 0 < x < 1} 1 , lido como “B é o conjunto dos números x, tal que x é 
maior que zero e menor que um”.
Se A é um conjunto descrito por uma regra, dizemos que um elemento b perten-
ce a A se b satisfaz a regra que define A.
Σxemρlo 3
Considere os seguintes conjuntos e suas leis de formação.
 • A = {x ∈ ℕ | x = 2t, onde t é um número natural}.
 • B = {x ∈ ℕ | x = 2t, onde t é um número natural e 1 < t < 10}.
Descrevendo os elementos de A, temos que A = {2, 4, 6, …}, ou seja, A é o conjun-
to dos números pares. Descrevendo os elementos de B, temos que B = {4, 6, 8, 10, 
12, 14, 16, 18}, ou seja, B é o conjunto dos números pares entre 3 e 19.
Observamos que A é um conjunto infinito e B é um conjunto finito com oito 
elementos.
Note que, algumas vezes, a regra que define um conjunto não é satisfeita por 
nenhum elemento. Por exemplo:
A = {a ∈ ℕ | a = 2t, onde t é um número natural e 1 < t < 2}
O símbolo "|" é lido como tal que 
(alguns autores usam ":").
1
32 Matemática Discreta
Nesse caso, não existe nenhum elemento que satisfaça a regra de formação do 
conjunto A. Quando isso acontece, dizemos que o conjunto A é um conjunto vazio. 
Mais precisamente, temos a seguinte definição de conjunto vazio:
Definição
Um conjunto que não possui nenhum elemento é chamado de conjunto vazio. Escrevemos ∅ ou { } para 
representar o conjunto vazio.
Σxemρlo 4
São exemplos de conjuntos vazios:
 • A = {x | x ≠ x}.
 • B = {x | x é ímpar e múltiplo de dois}.
 • C = {x | x é um triângulo e possui quatro lados}.
 • D = {x | x < 0 e x > 0}.
 • E = {x | x tem 20 anos de idade e x nasceu em 1820}.
Na definição de conjuntos não se está exigindo nada com relação à ordem em 
que seus elementos aparecem, ou seja, a ordem não importa. Isso significa, por 
exemplo, que os conjuntos A = {1, 3, 4, 7} e B = {3, 1, 4, 7} são iguais. Em geral, po-
demos definir a igualdade de dois conjuntos como:
Definição
Dois conjuntos A e B são iguais se possuem exatamente os mesmos elementos. 
Em símbolos, escrevemos:
A = B ↔ ∀ x, x ∈ A ↔ x ∈ B
E lemos:
A é igual a B se, e somente se, para todo x, x pertence a A se, e somente se, x pertence a B.
Definição
Dois conjuntos A e B são diferentes se existe um elemento a ∈ A tal que a ∉ B, ou existe um elemento 
b ∈ Btal que b ∉ A. Em símbolos, escrevemos:
A ≠ B ↔ ∃ a | a ∈ A e a ∉ B, ou ∃ b | b ∈ B e b ∉ A
E lemos:
A é diferente de B se, e somente se, existe a tal que a pertence a A e a não pertence a B, ou existe b tal que 
b pertence a B e b não pertence a A
A definição de igualdade de conjuntos estabelece que, para provarmos que dois 
conjuntos A e B são iguais, devemos provar que:
1. Todo elemento de A também é um elemento de B.
2. Todo elemento de B também é um elemento de A.
Teoria de conjuntos 33
Vejamos um exemplo.
Σxemρlo 5
Prove que os conjuntos A = {x | 2x + 4 = 10} e B = {3} são iguais.
Devemos mostrar que todo elemento de A é um elemento de B e que todo ele-
mento de B é um elemento de A. Seja a ∈ A, pela definição do conjunto A, a é tal que 
2a + 4 = 10. Resolvendo essa equação linear, temos que a = 3, ou seja, a ∈ B, uma 
vez que 3 ∈ B. Note que 2(3) + 4 = 10, ou seja, 3 satisfaz a definição do conjunto A e, 
assim, 3 ∈ A, provando que A = B.
Definição
Para um conjunto finito, a cardinalidade é o número de elementos que ele contém. Em notação simbóli-
ca, a cardinalidade de um conjunto A é descrita como |A| ou n(A). 
Se A é um conjunto com infinitos elementos, dizemos que a cardinalidade de A é infinita e escrevemos 
|A| = ∞ ou n(A) = ∞.
Vejamos o exemplo a seguir:
Σxemρlo 6
A cardinalidade do conjunto A = {1, 3, 10, 40, 400} é n(A) = 5, e a cardinalidade do 
conjunto B = {x | x é um número par} é n(B) = ∞.
Chamaremos de conjunto unitário todo conjunto que possui apenas um elemen-
to. O conjunto A = {27}, por exemplo, é um conjunto unitário.
Quando vamos descrever um conjunto, por exemplo, o conjunto A = {todos os 
homens que possuem 27 anos de idade}, admitimos a existência de um conjunto 
maior ao qual pertencem todos os elementos que compõem o conjunto que esta-
mos definindo. Esse conjunto maior é chamado de conjunto universo e é denota-
do pela letra U. No nosso exemplo, U = {todos os homens}.
Σxemρlo 7
Se A = {x ∈ N | x = 2k, onde k é um número natural} é o conjunto dos números 
naturais pares, o universo U é o conjunto de todos os números naturais.
Utilizando a definição de conjunto universo, podemos introduzir um novo con-
junto com base em um conjunto dado A.
34 Matemática Discreta
Definição
Dado um conjunto A e seja U seu conjunto universo, o conjunto dos elementos que pertencem a U 
e não pertencem a A é chamado de conjunto complementar de A. Denotamos o complementar de A 
por AC ou C(A).
Vejamos no exemplo a seguir:
Σxemρlo 8
Se A = {x ∈ ℕ | x = 2k, onde k é um número natural} é o conjunto dos números 
naturais pares, sabemos que seu universo U é o conjunto de todos os números 
naturais. Desse modo, pela definição de complementar, temos: 
AC = {x ∈ ℕ | x ≠ 2k, onde k é um número natural}
Ou seja, AC é o conjunto dos números naturais ímpares.
Nesta seção, você aprendeu a classificar vários objetos da vida real em termos 
de conjuntos. Além disso, vimos diferentes maneiras de descrever um conjunto e 
como podemos considerar um conjunto como parte menor de um conjunto maior 
(chamado de conjunto universo). Introduzindo a noção de subconjunto, vamos, na 
próxima seção, explorar o fato de podermos considerar um conjunto como uma 
parte menor de outro conjunto.
2.3 Subconjuntos
Vídeo Consideremos os seguintes conjuntos: A = {capitais brasileiras} e B = {São Paulo, 
Porto Alegre, Curitiba}. Observamos que todos os elementos do conjunto B também 
são elementos do conjunto A, pois São Paulo, Porto Alegre e Curitiba são capitais 
brasileiras. Nesse caso, dizemos que o conjunto B é um subconjunto do conjunto 
A. O mesmo acontece com os conjuntos C = {0, 10, 7, 8, 79, 5} e D = {0, 7, 5}, onde D 
é um subconjunto de C.
A definição matemática de subconjunto é apresentada a seguir:
Definição
Um conjunto B é subconjunto de um conjunto A se, e somente se, todo elemento de B for um elemento 
de A.
Vejamos no exemplo a seguir:
• Escrevemos B ⊂ A se B é um 
subconjunto de A. Nesse caso, 
também dizemos que B está 
contido em A.
• Em símbolos, temos:
 B ⊂ A ↔ ∀ b ∈ B → b ∈ A
• Escrevemos B ⊄ A se B não 
é subconjunto de A. Nesse 
caso, dizemos que B não está 
contido em A.
• Todo conjunto A é um subcon-
junto do seu universo U.
Importante
Teoria de conjuntos 35
Σxemρlo 9
a. {⊠, ⊝} ⊂ {⊠, ⨁, ⊟, ⊝}.
b. {a, b, c} ⊄ {b, c, d}.
c. {x | x é um número natural par} ⊂ {x | x é um número natural}.
Podemos representar a inclusão de conjuntos de modo gráfico por meio do Dia-
grama de Venn. Seja A um conjunto, U seu universo e B ⊂ A, graficamente temos:
A
B
U
Teorema 
A inclusão de conjuntos satisfaz as seguintes propriedades:
a. ∅ ⊂ A para todo conjunto A.
b. A ⊂ A (reflexiva).
c. Se A ⊂ B e B ⊂ A, então A = B (antissimétrica).
d. Se A ⊂ B e B ⊂ C, então A ⊂ C (transitiva).
Demonstração
O item a pode ser descrito na seguinte proposição:
∀ x ∈ ∅ → x ∈ A
Onde temos p: ∀ x ∈ ∅ e q: x ∈ A. Como p é falsa, pois não há elementos em ∅, a 
proposição é sempre verdadeira, pois p → q é sempre verdadeira. Provando, então, 
que ∅ ⊂ A.
O item b segue do fato de que, se x ∈ A, então x ∈ A. 
O item c segue da definição de igualdade de conjuntos.
Para o item d, temos: seja x ∈ A, então, como A ⊂ B, temos que x ∈ B, mas B ⊂ C, 
onde x ∈ C, ou seja, A ⊂ C. 
Pela definição de igualdade de 
conjuntos, dois conjuntos A e B 
são iguais se, e somente se, A ⊂ B 
e B ⊂ A.
Importante
36 Matemática Discreta
Σxemρlo 10
Considere os conjuntos A = {números naturais}, B = {números naturais pares} e 
C = {números naturais que dividem 4}. Temos que:
a. B ⊂ A e n(B) = n(A) = ∞.
b. C ⊂ A e n(C) = 3 < n(A) = ∞.
A inclusão de conjuntos e seus complementares está relacionada ao seguinte 
teorema.
Teorema 
Sejam A e B dois conjuntos e AC e BC seus complementares, se A ⊂ B, então 
BC ⊂ AC.
Demonstração
Seja x ∈ BC, então, pela definição de conjunto complementar, temos que x ∉ B. 
Como A ⊂ B, tem-se que x ∉ A, ou seja, x ∈ AC. Provando, assim, que BC ⊂ AC.
Definição
Para qualquer conjunto A, definimos o conjunto das partes de A, denotado por ℘(A), como sendo o 
conjunto formado por todos os subconjuntos de A. Em símbolos:
℘(A) = {B | B ⊂ A}
Observamos que, pela definição de conjunto das partes, ∅ ∈ ℘(A) e A ∈ ℘(A) para todo conjunto A.
Vejamos um exemplo de como encontrar o conjunto das partes de um conjunto A.
Σxemρlo 11
Seja A = {1, 11, 0}, então o conjunto das partes de A é:
℘(A) = {∅, {0}, {1}, {11}, {1,11}, {1,0}, {11,0}, {1,11,0}}
No exemplo é possível notar que se n(A) < ∞, então a cardinalidade de ℘(A) 
também será finita; além disso, teremos que n(℘(A)) > n(A). Na verdade, é possível 
provar que n(℘(A)) = 2n(A). Obviamente, n(℘(A)) = ∞ se n(A) = ∞.
2.4 Operações com conjuntos
Vídeo Em teoria de conjuntos, assim como em todos os tópicos estudados em mate-
mática, estamos interessados em definir e compreender operações matemáticas 
que podem ser realizadas entres seus objetos. Nesta seção vamos definir as princi-
pais operações entre conjuntos. 
Observamos a seguinte proprie-
dade elementar da inclusão de 
conjuntos: 
Se A ⊂ B, então n(A) ≤ n(B)
Importante
Teoria de conjuntos 37
Começaremos com a interseção.
Definição
A interseção entre os conjuntos A e B é o conjunto A∩B formado pelos elementos que estão simultanea-
mente em A e B. Em símbolos:
A∩B = {x | x ∈ A e x ∈ B}
O Diagrama de Venn da interseção de dois conjuntos é dado por:
A B
A∩B
Vejamos um exemplo a seguir:
Σxemρlo 12
Sejam A = {1, ∆, ∇} e B = {1, a, ∇, Θ}, então A∩B = {1, ∇}.
A definição de interseção de conjuntos pode ser generalizada para uma quanti-
dade finita de conjuntos, conforme segue:
Definição
A interseção entre os conjuntos A
1
, A
2
, …, A
n
 é o conjunto A
1
∩A
2
∩…∩A
n
, formado pelos elementos 
que estão simultaneamente em A
1
, A
2
, …, A
n
. Em símbolos:

i =1
n
iA = A1∩A2∩...∩An = {x | x ∈ A1 e x ∈ Ai, ∀ i = 2, 3, ..., n} 
Vejamos um exemplo:
Σxemρlo 13
Vamos representar as diversas interseções que podem ser estudadas com rela-
ção aosconjuntos:
A = {01,11, 001, 10, 00, 010}, B = {01, 11, 001, 101, 011, 111} e 
C = {01,11, 011, 101, 10, 000, 110}
38 Matemática Discreta
A B
C
00100,010 111
01,11
000,110
10 101,011
Temos que: 
 A∩B∩C = {01, 11}
 A∩B = {01, 11, 001}
 A∩C = {01, 11, 10}
 B∩C = {01, 11, 101, 011}
Definição
Dois conjuntos A e B são ditos conjuntos disjuntos se A∩B = ∅, ou seja, se A e B não possuem elementos 
em comum.
Σxemρlo 14
Sejam A = {101, 111} e B = {010, 100}, então A∩B = ∅.
Apresentaremos a seguir algumas das principais propriedades da interseção 
entre conjuntos. As propriedades são apresentadas considerando, em geral, a in-
terseção entre dois ou três conjuntos, mas podem ser facilmente generalizadas 
para a interseção de n conjuntos.
Teorema
Sejam A e B dois conjuntos tais que A ⊂ B, então A∩B = A.
Demonstração
Vamos mostrar que A∩B ⊂ A e A ⊂ A∩B. De fato, seja x ∈ A∩B, isso significa que 
x ∈ A e x ∈ B e, como x ∈ A, prova que A∩B ⊂ A. Seja agora y ∈ A, como A ⊂ B, temos 
que y ∈ B, isto é, y ∈ A∩B, provando que A ⊂ A∩B. Concluímos, então, que A∩B = A.
Σxemρlo 15
Sejam A = {1010, 0101} e B = {1010, 1001, 1111, 0101}, então, como A ⊂ B:
A∩B = A = {1010, 0101}
Teoria de conjuntos 39
Teorema 
Sejam A e B dois conjuntos quaisquer, então:
A∩B ⊂ B e A∩B ⊂ A
Demonstração
Vamos mostrar apenas a primeira inclusão, já que a segunda é análoga. Seja 
x ∈ A∩B, então x ∈ A e x ∈ B, onde x ∈ B, provando que A∩B ⊂ B.
Σxemρlo 16
Sejam A = {11010, 10110} e B = {11010, 11111, 00000}, então:
A∩B = {11010} ⊂ {11010, 11111, 00000}
Teorema 
Sejam A, B e C conjuntos quaisquer, se A ⊂ B, então:
C∩A ⊂ C∩B
Demonstração
Seja x ∈ C∩A → x ∈ C e x ∈ A ⊂ B → x ∈ C e x ∈ B → x ∈ C∩B, onde C∩A ⊂ C∩B.
Σxemρlo 17
Sejam A = {101, 111}, B = {101, 111, 110, 001} e C = {001, 111}, então: 
A ⊂ B e A∩C = {111} ⊂ {111, 001} = B∩C
Teorema (propriedades fundamentais da interseção de conjuntos)
Sejam A, B e C conjuntos quaisquer e U o conjunto universo, a interseção de 
conjuntos satisfaz as seguintes propriedades:
a. A∩∅ = ∅.
b. A∩AC = ∅.
c. A∩A = A (idempotente).
d. A∩U = A (elemento neutro).
e. A∩B = B∩A (comutativa).
f. A∩(B∩C) = (A∩B)∩C (associativa).
Demonstração
Provaremos apenas a propriedade associativa: seja x ∈ A∩(B∩C) ↔ x ∈ A e 
x ∈ (B∩C) ↔ x ∈ A e (x ∈ B e x ∈ C) ↔ (x ∈ A e x ∈ B) e x ∈ C ↔ x ∈ (A∩B) e x ∈ C ↔ 
x ∈ (A∩B)∩C, então temos que A∩(B∩C) = (A∩B)∩C.
Outra operação importante entre dois ou mais conjuntos é a operação de 
união, que consiste em reunir elementos para formar um novo conjunto. Mais pre-
cisamente, a união de conjuntos é definida como segue:
40 Matemática Discreta
Definição
A união entre os conjuntos A e B é o conjunto A∪B, formado pela reunião dos elementos de A e B. Em 
símbolos:
A∪B = {x | x ∈ A ou x ∈ B}
Vejamos o exemplo a seguir:
Σxemρlo 18
Sejam A = {∆, 11, ∇} e B = {1, ∆, 11, α, β}, então:
A∪B = {1, ∆, 11, ∇, α, β}
A definição de união de conjuntos pode ser generalizada para uma quantidade 
finita de conjuntos, conforme segue:
Definição
A união entre os conjuntos A
1
, A
2
, …, A
n
 é o conjunto A
1
∪A
2
∪…∪A
n
, formado por todos os elementos 
de A
1
, A
2
, …, A
n
. Em símbolos:

i =1
n
iA = A1∪A2∪...∪An = {x | x ∈ A1 ou x ∈ Ai, ∀ i = 2, 3, ..., n}
Vejamos o exemplo a seguir:
Σxemρlo 19
Vamos representar a união dos conjuntos. 
A = {01, 11, 001, 10, 00, 010}, B = {01, 11, 001, 101, 001, 111} e 
C = {01, 11, 011, 101, 10, 000, 110}
Um ponto importante que devemos notar ao escrever a união de conjuntos é 
que nunca repetiremos elementos, ou seja, cada elemento deverá aparecer uma 
única vez no conjunto união. Sendo assim, temos:
A∪B∪C = {01, 11, 001, 00, 010, 101, 001, 111, 011, 10, 000, 110}
A seguir, apresentaremos algumas das principais propriedades da união de con-
juntos. As propriedades são apresentadas considerando, em geral, a união entre 
dois ou três conjuntos, porém podem ser facilmente generalizadas para a união de 
n conjuntos.
Teoria de conjuntos 41
Teorema
Sejam A e B dois conjuntos, então A ⊂ A∪B e B ⊂ A∪B.
Demonstração
Vamos mostrar que A ⊂ A∪B. De fato, seja x ∈ A, isso significa que x ∈ A ou x ∈ B, 
isto é, x ∈ A∪B, provando que A ⊂ A∪B.
 Σxemρlo 20
Sejam A = {∆, ⊗, ⊠} e B = {111, 101}, então A∪B = {∆, ⊗, ⊠, 111, 101} e, claramente, 
A ⊂ A∪B, assim como B ⊂ A∪B.
Teorema
Sejam A e B dois conjuntos, então A∪B = B ↔ A ⊂ B.
Demonstração
De fato, já sabemos que A ⊂ A∪B. Como A∪B = B, temos que A ⊂ B. Agora, 
sabendo que A ⊂ B, vamos mostrar que A∪B = B. De fato, já sabemos que B 
⊂ A∪B, isso significa que basta provarmos que A∪B ⊂ B para termos a igual-
dade A∪B = B. Então, se x ∈ A∪B, isso significa que x ∈ A ou x ∈ B, mas A ⊂ B. 
Em qualquer caso, teremos que x ∈ B; se x ∈ A∪B, temos que x ∈ B, provando 
que A∪B = B.
Σxemρlo 21
Sejam A = {4, 7} e B = {4, 7, 8, 9}, então:
A∪B = {4, 7, 8, 9} = B
Teorema 
Sejam A, B e C conjuntos tais que A ⊂ C e B ⊂ C, então A∪B ⊂ C.
Demonstração
De fato, seja x ∈ A∪B, então, por definição, x ∈ A ou x ∈ B. Como A ⊂ C e B ⊂ C, 
segue que x ∈ A ⊂ C ou x ∈ B ⊂ C, ou seja, x ∈ C. Provando que A∪B ⊂ C.
Teorema (propriedades fundamentais da união de conjuntos)
Sejam A, B e C conjuntos quaisquer e U o conjunto universo, a união de conjun-
tos satisfaz as seguintes propriedades:
a. A∪∅ = A (elemento neutro).
b. A∪U = U.
c. A∪AC = U.
d. A∪A = A (idempotente).
e. A∪B = B∪A (comutativa).
f. A∪(B∪C) = (A∪B)∪C (associativa).
Agora é com você: faça a demons-
tração de que B ⊂ A∪B
Desafio
42 Matemática Discreta
Σxemρlo 22
Sejam A = {α, θ} e B = {101, 111, 110}, então:
A∪B = {α, θ, 101, 111, 110} = B∪A
Podemos também combinar as operações de união e interseção de conjun-
tos para obter um novo conjunto. A combinação das operações de interseção e 
união de conjuntos satisfaz as seguintes propriedades, que são chamadas de leis 
de absorção:
Teorema 
Sejam A e B conjuntos, então: 
A∩(A∪B) = A e A∪(A∩B) = A
Demonstração 
Sabemos que A ⊂ A∪B e, assim, segue do teorema ilustrado no Exemplo 15 que 
A∩(A∪B) = A. De maneira análoga, temos que A∪(A∩B) = A.
Duas propriedades importantes na combinação entre união e interseção de 
conjuntos são as propriedades de distributividade, que são equivalentes às pro-
priedades de distributividade com relação à soma e multiplicação de números 
reais. A seguir, vamos enunciar e provar as propriedades de distributividade da 
 interseção e união de conjuntos.
Teorema 
Sejam A, B e C conjuntos, então valem as seguintes distributivas:
a. A∩(B∪C) = (A∩B)∪(A∩C).
b. A∪(B∩C) = (A∪B)∩(A∪C).
Demonstração 
Para provar essas propriedades, utilizaremos as leis distributivas da lógica ma-
temática. Vamos provar o item a.
Seja x ∈ A∩(B∪C) ↔ x ∈ A e x ∈ B∪C ↔ x ∈ A e (x ∈ B ou x ∈ C)
 ↔ (x ∈ A e x ∈ B) ou (x ∈ A e x ∈ C) ↔ x ∈ A∩B ou x ∈ A∩C
 ↔ x ∈ (A∩B)∪(A∩C)
Provando que A∩(B∪C) = (A∩B)∪(A∩C).
Agora é com você: faça a demons-
tração do item b.
Desafio
Teoria de conjuntos 43
Σxemρlo 23
Considere A = {1, 2}, B = {0, 1, 3, 4} e C = {1, 4, 5}.
Note inicialmente que B∩C = {1, 4}, onde A∪(B∩C) = {1, 2, 4}. 
Por outro lado, temos que A∪B = {0, 1, 2, 3, 4} e A∪C = {1, 2, 4, 5}, onde 
(A∪B)∩(A∪C) = {1, 2, 4}. 
Sendo assim, A∪(B∩C) = (A∪B)∩(A∪C).
Vamos agora demonstrar um teorema muito importante, conhecido como Leis 
de De Morgan para conjuntos. Essas leis recebem esse nome porque sua demonstra-
ção é feita com base nas Leis de De Morgan da lógica matemática.
Teorema (Leis de De Morgan)
Sejam A e B conjuntos, então valem as seguintes leis de De Morgan:
a. (A∩B)C = AC∪BC.
b. (A∪B)C = AC∩BC.
Demonstração
Vamos provar o item a. 
Seja x ∈ (A∩B)C ↔ x ∉ A∩B ↔ ~(x ∈ A∩B) 
 ↔ ~(x ∈ A e x ∈ B) ↔ ~(x ∈ A) ou ~(x ∈ B) 
 ↔ x ∉ A ou x ∉ B ↔ x ∈ AC ou x ∈ BC ↔ x ∈ AC∪BC
Uma terceira operação importante entre conjuntos é a diferença entre conjun-
tos, a qual está definida a seguir.
Definição
A diferença entre os conjuntos A e B é o conjunto A\B 2 , formado pelos elementos de A que não estão 
em B. Em símbolos:
A\B= {x | x ∈ A e x ∉ B}
A diferença entre conjuntos pode 
ser denotada também por A – B.
2
Vejamos o exemplo a seguir:
Σxemρlo 24
Sejam A = {0, 3, 7} e B = {3, 5, 7} dois conjuntos, então:
A\B = {0} e B\A = {5}
Agora é com você: faça a demons-
tração do item b.
Desafio
A diferença entre dois conjuntos 
A e B não é comutativa, ou seja, 
A\B ≠ B\A.
Importante
44 Matemática Discreta
Teorema
Sejam A, B e C conjuntos em um universo U, então valem as seguintes proprie-
dades relacionadas com a diferença entre conjuntos:
a. A\∅ = A.
b. U\A = AC.
c. A\A = ∅.
d. A\AC = A.
e. (A\B)C = AC\B.
f. A\B = BC\AC.
g. (A\B)\C = A\(B∪C).
h. A\(B\C) = (A\B)∪(A∩C).
Demonstração
Vamos provar apenas o item g. Seja x ∈ (A\B)\C, temos por definição da opera-
ção de diferença de conjuntos que:
x ∈ (A\B)\C ↔ x ∈ A\B e x ∉ C ↔ (x ∈ A e x ∉ B) e x ∉ C
 ↔ x ∈ A e (x ∉ B e x ∉ C) ↔ x ∈ A e (~(x ∈ B) e ~(x ∈ C))
 ↔ x ∈ A e ~(x ∈ B ou x ∈ C) ↔ x ∈ A e ~(x ∈ B∪C)
 ↔ x ∈ A\(B∪C)
Ou seja, (A\B)\C = A\(B∪C).
Para finalizar este capítulo, iremos apresentar alguns exemplos de como pode-
mos utilizar operações entre conjuntos para analisar afirmações ou um conjunto 
de afirmações.
Σxemρlo 25
Dado que Pedro é um homem e que todos os homens são mortais, mostre que 
Welington é mortal.
Vamos utilizar a propriedade de que se A ⊂ B e B ⊂ C, então A ⊂ C. Sejam:
 U: Conjunto de todos os seres vivos.
 B: Conjunto de todos os seres humanos.
 C: Conjunto de todos os mortais.
 A: Conjunto unitário cujo único elemento é Pedro.
Temos que A ⊂ B, B ⊂ C. Logo, A ⊂ C, onde Pedro é mortal.
Teoria de conjuntos 45
Σxemρlo 26
Em uma escola de 1.000 alunos, 800 gostam de sorvete de chocolate, 700 gos-
tam de sorvete de morango e 600 gostam dos dois sabores. Quantos alunos não 
gostam de nenhum dos dois sabores?
Seja U = {Alunos da escola}, A = {Alunos que gostam de sorvete de chocolate} e 
B = {Alunos que gostam de sorvete de morango}. Vamos construir o Diagrama de 
Venn após analisar os dados.
Temos que n(A∩B) = 600, ou seja, 600 alunos gostam dos sabores chocolate e 
morango.
Para sabermos quantos alunos gostam apenas do sabor chocolate, fazemos a 
subtração da quantidade de alunos que gostam desse sabor pela quantidade de 
alunos que gostam de ambos os sabores. Assim: 
n(A)\n(A∩B) = 800 – 600 = 200
 Agora, para determinarmos a quantidade de alunos que gostam apenas do 
sabor morango, o processo é análogo ao anterior, fazemos:
n(B)\n(A∩B) = 700 – 600 = 100
Sabemos que n(U) = 1.000, que é composto pela quantidade de alunos que gos-
tam apenas do sabor chocolate, de ambos os sabores, apenas do sabor de moran-
go e alunos que não gostam de nenhum dos dois sabores, logo:
n(U) = n(A\(A∩B)) + n(A∩B) + n(B\(A∩B)) + n(U\(AUB))
= 200 + 600 + 100 + n(U\(AUB)) 
Sendo assim, n(U\(AUB)) = 1.000 – 900 = 100, ou seja, 100 alunos não gostam de 
nenhum dos sabores. O Diagrama de Venn ficará da seguinte forma:
Alunos da escola
Chocolate 
e 
morango 
600
Chocolate Morango
100
200 100
Podemos definir outras 
operações entre conjuntos. 
Uma operação bem conhe-
cida é a diferença simétrica 
entre conjuntos. Saiba 
mais sobre essa operação 
na página Matemática 
Essencial, da UEL.
Disponível em: http://www.uel.br/
projetos/matessencial/basico/medio/
conjuntos.html#sec11. Acesso em: 5 
mar. 2021.
Saiba mais
Sempre que você for resolver um 
exercício com interseções e uniões 
de conjuntos, inicie anotando a 
cardinalidade das interseções e 
lembre-se de que as subtrações 
da cardinalidade de cada conjunto 
com a interseção são realizadas 
para que não façamos a soma 
de cada interseção mais de uma 
vez, ou seja, para determinar a 
cardinalidade apenas de cada 
conjunto, sem a interseção.
Importante
http://www.uel.br/projetos/matessencial/basico/medio/conjuntos.html#sec11
http://www.uel.br/projetos/matessencial/basico/medio/conjuntos.html#sec11
http://www.uel.br/projetos/matessencial/basico/medio/conjuntos.html#sec11
46 Matemática Discreta
CONSIDERAÇÕES FINAIS 
Neste capítulo você aprendeu os conceitos fundamentais de teoria de conjuntos, 
as diferentes formas de descrevê-los e como relacioná-los com objetos da vida real. 
Pôde entender, ainda, como realizar várias operações básicas entre conjuntos, que 
estão diretamente relacionadas com fatos e temas de estudos da matemática discreta. 
Por fim, compreendeu como podemos utilizar a teoria de conjuntos para demons-
trar afirmações matemáticas.
ATIVIDADES
1. Demonstre a propriedade comutativa da interseção de conjuntos. Mais 
precisamente, demonstre que dados dois conjuntos A e B, então A∩B = B∩A.
2. Prove que, se A, B e C são conjuntos, então:
A∪(B∩C) = (A∪B)∩(B∪C)
3. Verifique a validade da seguinte lei de De Morgan: se A e B são conjuntos, então 
(A∪B)C = AC∩BC.
4. Prove que, se A e B são conjuntos, então A\B = BC\AC.
REFERÊNCIAS
IEZZI, G.; MURAKAMI, C. Fundamentos da matemática elementar. São Paulo: Atual, 2013.
FILHO, E. A. Teoria elementar dos conjuntos. São Paulo: Nobel, 1980.
ROSEN, K. H. Matemática discreta e suas aplicações. São Paulo: McGraw-Hill, 2009.
GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5. ed. Boston: Addison-
-Wesley, 2004.
Conjuntos numéricos 47
3
Conjuntos numéricos
Você deve concordar que o conceito fundamental em matemática é a ideia 
de número. Mais ainda, é provável que a primeira palavra que surge na sua 
cabeça ao pensar em matemática seja números. 
A ideia de número se desenvolveu com a capacidade de contar e vem evo-
luindo conforme a evolução da matemática como ciência. Da necessidade de 
contar objetos surgiram os números naturais, que já foram representados por 
diversas notações até chegar à notação que utilizamos hoje. Com o desenvolvi-
mento de novos problemas matemáticos, fez-se necessária a criação de novos 
conjuntos numéricos: inteiros, racionais, reais e imaginários. 
Neste capítulo, você vai aprender os principais conjuntos numéricos, suas 
principais operações e propriedades. Além disso, vai aprender a trabalhar com 
aritmética modular, uma ferramenta fundamental para que nossos computa-
dores realizem tarefas, como executar um vídeo da internet de modo pratica-
mente instantâneo.
3.1 Conjunto dos números naturais 
Vídeo “Deus criou os números naturais, todo o resto é obra do homem”. Essa frase 
foi dita pelo famoso matemático alemão Leopold Kronecker (1823-1891) para dar 
ênfase à importância dos números naturais. 
Na verdade, toda a sistemática dos conjuntos numéricos conhecidos na ma-
temática pode ser feita por meio dos números que utilizamos para contar. Esses 
números são conhecidos como números naturais.
Definição
Chamamos de conjunto dos números naturais, denotando por  , o conjunto formado pelos números 
1, 2, 3, ….
 = {1, 2, 3, …}
Assumiremos que já é sabido que podemos realizar duas operações fundamen-
tais com números naturais: adição e multiplicação. Essas operações satisfazem al-
gumas propriedades bem interessantes, que serão anunciadas em seguida.
Teorema 
A operação da adição de números naturais satisfaz as propriedades a seguir:
48 Matemática Discreta
a. Associativa da adição:
(a + b) + c = a + (b + c), para todo a, b, c ∈  .
b. Comutativa da adição:
a + b = b + a, para todo a, b ∈  .
Observamos que na definição apresentada o número zero não pertence ao 
conjunto dos números naturais, já que a criação dos números naturais se dá 
com o objetivo de contagem, por exemplo, para um pastor contar suas ovelhas. 
Sendo assim, não incluímos o zero como número natural; afinal, ninguém conta 
zero ovelhas.
Em algumas oportunidades é conveniente trabalhar com o número zero. Sendo 
assim, vamos denotar por 0 o conjunto dos números naturais unido ao elemento 
zero, ou seja, 0 = ∪{0}. Nesse caso, chamaremos o zero de elemento neutro da 
adição em 0, pois para todo a ∈  , temos que a + 0 = a.
A multiplicação de números naturais também possui propriedades bem defini-
das, a saber:
Teorema
A operação de multiplicação de númerosnaturais satisfaz as propriedades 
a seguir:
a. Associativa da multiplicação:
(ab)c = a(bc), para todo a, b, c ∈  .
b. Comutativa da multiplicação:
ab = ba, para todo a, b ∈  .
c. Elemento neutro da multiplicação:
a · 1 = a, para todo a ∈  .
d. Distributiva da multiplicação relativamente à adição:
a(b + c) = ab + ac, para todo a, b, c ∈  .
Outra propriedade importante que os números naturais satisfazem é a proprie-
dade conhecida como tricotomiaI, enunciada a seguir.
Dados a, b ∈  , pode ocorrer exatamente uma das três alternativas seguintes:
 • a = b. 
 • Existe p ∈  tal que a = b + p. 
 • Existe q ∈  com b = a + q.
Além das suas propriedades operatórias e da propriedade da tricotomia, o con-
junto dos números naturais possui outra propriedade muito importante: a orde-
nação dos números naturais, que diz que dados dois números naturais diferentes, 
existe sempre um maior que o outro. 
A ordenação dos números naturais é chamada de relação de ordem. A relação de 
ordem no conjunto dos números naturais é definida da seguinte forma: 
Conjuntos numéricos 49
Definição
Dados a, b ∈  , dizemos que a é menor que b, e escrevemos a < b, se existe p ∈  tal que 
b = a + p. Nessas condições, dizemos que b é maior que a. 
Também podemos utilizar a notação a ≤ b para dizer que um número a é menor 
ou igual a um número b, ou seja, quando a = b + p com p ∈ 0.
Teorema 
A relação de ordem dos números naturais satisfaz as propriedades a seguir:
a. Transitividade: se a < b e b < c, então a < c.
b. Tricotomia: dados a e b, pode ocorrer exatamente uma das alternativas: 
a = b ou a < b ou b < a.
c. Monotonicidade da adição: se a < b, então para todo p ∈  tem-se a + p < b + p.
Demonstração
Vamos demonstrar apenas os itens a e c. 
Para o item a, suponhamos que a < b e b < c. Isso significa que existem p, q ∈  
tais que b = a + p e c = b + q, em que c = (a + p) + q = a + (p + q), ou seja, a < c.
Para o item c, temos que a < b, em que existe q ∈  tal que a + q = b. Sendo 
assim, (a + p) + q < b + p, ou seja, a + p < b + p.
As propriedades do teorema apresentado continuam verdadeiras quando con-
sideramos ≤. Além disso, podemos descrever uma propriedade de monotonicidade 
para multiplicação, mais precisamente:
Teorema 
A relação de ordem dos números naturais satisfaz a seguinte propriedade de 
monotonicidade da multiplicação: 
Se a < b e p ∈  , então ap < bp.
A demonstração desse fato segue diretamente da propriedade distributiva da 
multiplicação com relação à soma de números naturais.
Outra propriedade importante é a propriedade do corte, ou propriedade do 
cancelamento, a qual é utilizada com frequência quando estamos fazendo cálculos 
e comparações de números naturais. A lei do corte para números naturais é dada 
pelo seguinte teorema:
Teorema (lei do corte) 
Sejam a, b e c números naturais tais que c ≠ 0 e ac = bc. Então, a = b.
Demonstração
Suponhamos por contraposição que a ≠ b. Por tricotomia, a < b ou b < a. Se 
a < b, existe m ∈  tal que b = a + m, em que bc = (a + m)c = ac + mc. Logo, ac < bc. 
Se a > b, existe n ∈  tal que a = b + n, em que ac = (b + n)c = bc + nc. Logo, ac > bc. 
Sendo assim, se ac = bc, então a = b.
Agora é com você: prove o item b.
Desafio
50 Matemática Discreta
Existem infinitos números naturais, ou seja, a cardinalidade do conjunto dos 
números naturais é infinita. Esse fato é enunciado e demonstrado no teorema 
a seguir:
Teorema 
O conjunto dos números naturais tem cardinalidade infinita, isto é, n() = ∞. 
Demonstração
Suponhamos que  é um conjunto finito. Então, utilizando a tricotomia para 
comparar todos os elementos de  , dois a dois, obtemos um natural b maior que 
todos os elementos de  . Mas b + 1 também é natural e é maior que b, uma con-
tradição, provando que  tem cardinalidade infinita.
Para encerrar esta seção, demonstraremos um teorema muito importante, pois 
possui várias aplicações, em especial na computação. Esse teorema é conhecido 
como teorema fundamental da aritmética e indica que todo número natural pode 
ser escrito como a multiplicação de números primos. Lembramos que a definição 
de número primo é dada por:
Definição
Um número natural p é chamado de número primo quando p ≠ 1 e não existem a, b ∈  tais que 
p = ab. 
Entre os cem primeiros números naturais, temos os seguintes números primos:
2 3 5 7 11
13 17 19 23 29
31 37 41 43 47
53 59 61 67 71
73 79 83 89 97
Teorema (teorema fundamental da aritmética)
Se b ∈  , então b pode ser escrito (de maneira única) como o produto de nú-
meros primos. 
Demonstração
Vamos utilizar um método de demonstração conhecido como segundo princípio 
da indução. Seja b ∈  e suponha que todo número natural menor que b pode ser 
escrito como o produto de fatores primos, então b é primo (nesse caso, b é trivial-
mente um produto de fatores primos) ou b = cd, com c < b e d < b. Pela hipótese de 
indução, c e d podem ser escritos como o produto de fatores primos. Sendo assim, 
o teorema é válido.
Conjuntos numéricos 51
3.2 Conjunto dos números inteiros 
Vídeo Ao longo do tempo, com o desenvolvimento de novos problemas matemáti-
cos, fez-se necessária a ampliação do conjunto dos números naturais de modo que 
fosse possível, por exemplo, obter a solução de uma equação do tipo x + 3 = 1. Ou 
seja, foi preciso estender o conjunto dos números naturais para um conjunto que 
apresentasse entre seus elementos números negativos. Esse conjunto é chamado 
de conjunto dos números inteiros e é definido da seguinte maneira:
Definição
Chamamos de conjunto dos números inteiros, denotado por  , o conjunto formado pelos números 
…, -3, -2, -1, 0, 1, 2, 3, ….
 = {…, -3, -2, -1, 0, 1, 2, 3, …}
O conjunto dos números inteiros possui alguns subconjuntos notáveis, a saber:
 •  + = {0, 1, 2, 3, …} = ∪{0}, chamado de conjunto dos números inteiros não 
negativos.
 •  – = {..., -3, -2, -1, 0}, chamado de conjunto dos números inteiros não positivos.

* = {…, -3, -2, -1, 1, 2, 3, …}, chamado de conjunto dos inteiros não nulos.
Assim como no caso do conjunto dos números naturais, o conjunto dos nú-
meros inteiros também apresenta um número infinito de elementos. Esse fato é 
sintetizado no seguinte teorema:
Teorema
O conjunto dos números inteiros possui cardinalidade infinita, isto é, n( ) = ∞. 
Demonstração
Segue desse fato que n() = ∞ e  ⊂  .
A grande importância dos números inteiros se dá pelo fato de que podemos 
realizar três das quatro operações fundamentais (adição, subtração e multiplica-
ção). Vamos assumir que essas operações já nos são conhecidas. Sendo assim, ire-
mos rever apenas algumas notações e propriedades.
Existem algumas diferenças básicas nas propriedades operatórias da multiplica-
ção e da soma quando consideramos o conjunto dos números inteiros em relação 
ao conjunto dos números naturais. Podemos citar, por exemplo, a existência de um 
elemento simétrico da adição, ou seja, dado a ∈  , existe um elemento b ∈  tal 
que a + b = 0. Nesse caso, denotamos b = -a.
A operação de subtração de números inteiros não é simétrica, pois é claro que, 
por exemplo, 1 - 3 ≠ 3 - 1. A seguir, elencamos algumas propriedades operatórias.
Teorema 
As operações de adição e subtração de números inteiros satisfazem as proprie-
dades a seguir:
a. Associativa da adição e subtração: (a ± b) ± c = a ± (b ± c), para todo a, b, c ∈  .
52 Matemática Discreta
b. Comutativa da adição: a + b = b + a, para todo a, b ∈  .
c. Elemento neutro da adição e subtração: a ± 0 = a, para todo a ∈  .
Além disso, existem propriedades análogas para a operação de multiplicação de 
números inteiros.
Teorema
A operação de multiplicação de números inteiros satisfaz as propriedades 
a seguir:
a. Associativa da multiplicação: (ab)c = a(bc), para todo a, b, c ∈  .
b. Comutativa da multiplicação: ab = ba, para todo a, b ∈  .
c. Elemento neutro da multiplicação: a · 1 = a, para todo a ∈  .
d. Distributiva da multiplicação relativamente à adição e à subtração:a(b ± c) = 
ab ± ac, para todo a, b, c ∈  .
O elemento 0 ∈  é chamado de elemento absorvente da multiplicação, pois 
0 · b = b · 0 = 0, para todo b ∈  . Além disso, a multiplicação de números inteiros 
satisfaz a chamada regra de sinais. Vejamos: dados a, b ∈  , então a multiplicação 
de a e b é tal que:
 • a(-b) = -(ab).
 • (-a)(-b) = (ab).
 • ab = 0 se, e somente se, a = 0 ou b = 0.
A lei do corte pode ser estendida para números inteiros da seguinte forma:
Teorema (lei do corte para números inteiros) 
Se 0 ≠ a ∈  , então ab = ac ↔ b = c, para todo b, c ∈  .
Outra operação fundamental entre números inteiros é a operação de divisão 
inteira. Essa operação é esquematizada pelo algoritmo da divisão de Euclides: 
sejam a, b ∈  com b ≠ 0, podemos escrever a da seguinte forma:
a = bq + r 
em que q, r ∈  são únicos para 0 ≤ r < b. Nesse caso, dizemos que q é o quociente 
da divisão e r é o resto da divisão.
Σxemρlo 1
Considerando os números inteiros -2, -15 e 10, temos:
a. -2 = (-15) · 0 + (-2)
b. 10 = (-2)(-5) + 0
c. -15 = (-2)(7) + (-1)
Note que no item b do exemplo temos que o resto é zero. Nesse caso, temos 
que a = 10 é um múltiplo de b = -2. Isso nos leva à definição de divisor de um nú-
mero inteiro.
Conjuntos numéricos 53
Definição
Sejam a, b ∈  , dizemos que b divide a, ou que b é divisor de a, ou ainda que a é divisível por 
b, se existe q ∈  tal que:
a = bq
Se não existe q ∈  , dizemos que b não divide a.
Observamos então que b divide a se, e somente se, o resto da divisão de a por 
b é zero. Vamos escrever b | a para representar que b divide a. Se b não divide a, 
vamos escrever b ∤ a.
Vejamos um exemplo:
Σxemρlo 2
Considerando os números inteiros -2, -10 e 13, temos que:
-2 | -10 e -2 ∤ 13.
A noção de divisibilidade possui propriedades importantes, as quais nos ajudam 
a operar e encontrar os divisores de um número. Essas propriedades estão elenca-
das no seguinte teorema:
Teorema
Sejam a, b, c ∈  , temos que:
a. Se a | b e b | c, então a | c.
b. Se a | b e b | a, então |a| = |b|.
c. Se a, b > 0 e a | b, então a ≤ b.
Demonstração
Vamos demonstrar apenas o item a. Se a | b e b | c, então existem m, n ∈  tais 
que b = na e c = mb, em que c = mna, e isso significa que a | c.
Lembramos que o módulo, ou valor absoluto, de um número a ∈  é defi-
nido por: 
|a| = 
a se�a
a �� se�a
,
,
�
� �
�
�
�
��
0
0
Agora é com você: prove os itens 
b e c.
Desafio
Note que, pela definição de valor 
absoluto, é sempre válido que 
|a| ≥ 0 e |a| = |-a| para qualquer 
a ∈  . 
Importante
54 Matemática Discreta
3.3 Conjunto dos números racionais 
Vídeo A fim de definir a divisão de dois números, iremos estender o conjunto dos 
números inteiros para um conjunto maior, chamado de conjunto dos números racio-
nais. Note que a divisão de dois números inteiros nem sempre tem como resultado 
um número inteiro, por exemplo, 3 e 2 ∈  , porém 3
2
 ∉  , ou seja, não é um 
número inteiro. O conjunto dos números racionais é definido da seguinte maneira:
Definição
Chamamos de conjunto dos números racionais, denotado por  , o conjunto formado pelas frações 
p
q , em que p, q ∈  e q ≠ 0.
Para b = p
q
 ∈  , chamamos p de numerador e q de denominador de b. Dizemos 
que dois números racionais pq e 
r
s são iguais se ps = rq. Note, por exemplo, que os 
números racionais 9
4
 e 18
8
 são iguais.
As operações de adição, subtração, multiplicação e divisão de números racio-
nais são definidas da seguinte forma:
Definição (operações fundamentais de números racionais)
Sejam pq e 
r
s ∈  , então as operações de adição, subtração, multiplicação e divisão são definidas 
como:
a. pq
r
s
ps ± rq
qs
± =
b. pq
r
s
pr
qs
. =
c. 
p
q p
qr
s
s
r
ps
qr
.= =
O conjunto dos números racionais possui alguns subconjuntos notáveis, 
a saber:
 •  +, chamado de conjunto dos números racionais não negativos.
 •  –, chamado de conjunto dos números racionais não positivos.
 •  *, chamado de conjunto dos números racionais não nulos.
Teorema 
As operações de adição e subtração de números racionais satisfazem as pro-
priedades a seguir:
Note que se a ∈  ou a ∈  , 
então a ∈  .
Importante
Conjuntos numéricos 55
a. Associativa da adição e da subtração: 
p
q
r
s
c
d
�
�
�
�
�
�
� � = 
p
q
r
s
± c
d
�
�
�
�
�
�
� , para todo 
�p
q
r
s
c
d
, , ∈  .
b. Comutativa da adição: 
p
q
r
s
ps rq
qs
� �
�
 
p
q
r
s
r
s
p
q
p
q
r
s
c
d
p
q
r
s
c
d
�para�todo�p
q
r
s
c
� � � �
�
�
�
�
�
� � � � �
�
�
�
�
�
� , , dd
�, para todo 
p
q
r
s
, � ∈  .
c. Elemento neutro da adição e da subtração: p
q
 ± 0 = p
q
 , para todo 
p
q
 ∈  .
d. Elemento oposto da adição: 
p
q
+ p
q
�
�
�
�
�
� �
�
�
�
�
�
� � 0 , para todo 
p
q
 ∈  .
Demonstração
Vamos demonstrar apenas o item b. Temos, por um lado, que:
p
q
 r
s
 ps rq
qs
 sp qr
sq
� �
�
�
�
 
Por outro lado, r
s
p
q
 rq sp
sq
 sp qr
sq
� �
�
�
� . 
Sendo assim, p
q
r
s
 r
s
p
q
� � � .
Teorema 
A operação de multiplicação de números racionais satisfaz as propriedades 
a seguir:
a. Associativa da multiplicação: 
p
q
r
s
c
d
 p
q
r
s
c
d
�
�
�
�
�
�
� � �
�
�
�
�
�
� , para todo 
p
q
r
s
c
d
, , ∈ .
b. Comutativa da multiplicação: p
q
r
s
r
s
p
q
�� � � , para todo p
q
r
s
, ∈ .
c. Elemento neutro da multiplicação: p
q
1= p
q
⋅ , para todo 
p
q
∈ .
d. Elemento inverso da multiplicação: p
q
q
p
� � 1, para todo 
p
q
∈ .
e. Distributiva da multiplicação relativamente à adição e à subtração: 
p
q
r
s
c
d
 p
q
r
s
p
q
c
d
�, para todo p
q
r
s
c
d
�
�
�
�
�
�
� � � � � �, ,  .
Demonstração
Vamos demonstrar apenas o item b. Pela definição de igualdade de números ra-
cionais, verificamos que o produto pr · sq = qs · rp; isso, é claro, pelas propriedades 
de números inteiros. 
Todo número racional pode ser escrito na forma decimal. Quando transforma-
mos um número racional que está na forma de fração para a notação na forma 
decimal, pode ocorrer um dos seguintes casos:
Agora é com você: prove os itens 
a, c e d.
Desafio
Agora é com você: prove os itens 
a, c, d e e.
Desafio
56 Matemática Discreta
I. O número decimal é exato, ou seja, o número de algoritmos é finito. Por 
exemplo:
a. 1
2
 = 0,5.
b. 6
2
 = 3,0.
II. O número decimal é uma dízima periódica, ou seja, tem infinitos algoritmos 
que se repetem periodicamente. Por exemplo:
a. 13 = 0,333...
b. 2
7
 = 0,285714285714...
O caminho inverso nem sempre é verdadeiro, ou seja, dado um número escrito 
em sua forma decimal, nem sempre é possível escrevê-lo na forma de fração. Esses 
números são chamados de números irracionais. 
3.4 Números reais e cardinalidade 
Vídeo Para finalizar nosso estudo sobre conjuntos numéricos, vamos definir um con-
junto numérico maior, que abrange todos os conjuntos já estudados. Esse conjunto 
recebe o nome de conjunto dos números reais.
Definição
Chamamos de conjunto dos números reais, denotado por  , o conjunto formado pelos números 
com representação decimal finita ou periódica (chamados de números racionais) e pelos decimais 
infinitos não periódicos (chamados de números irracionais).
 Observamos que, pela definição de números reais:
 •  ,  ,  ⊂  .
 • As operações de adição, subtração, multiplicação e divisão de números reais 
satisfazem todas as propriedades operatórias já enunciadas para os demais 
conjuntos numéricos.
O conjunto dos números reais possui alguns subconjuntos notáveis. A saber:
 •  +, chamado de conjunto dos números reais não negativos.
 •  –, chamado de conjunto dos números reais não positivos.
 •  *, chamado de conjunto dos números reais não nulos.
Ao estudarmos conjuntos, definimos a cardinalidade de um conjunto finito 
como seu número de elementos. Desse modo, dizemos que dois conjuntos pos-
suem a mesma cardinalidade se apresentam o mesmo número de elementos. 
Vamos estender a ideia de igualdade entre cardinalidade para conjuntoscom in-
finitos elementos.
O número irracional mais fa-
moso que existe é o número 
3,141592653589…, o qual 
possui infinitas casas deci-
mais e é conhecido como π. 
No vídeo Para que serve o Pi 
e por que esse número causa 
tanto fascínio?, produzido 
pela BBC News Brasil, você 
vai encontrar uma pequena 
descrição e várias curiosida-
des sobre o número π.
Disponível em: https://www.youtube.
com/watch?v=vY6965UdcLI. Acesso 
em: 5 mar. 2021.
Vídeo
https://www.youtube.com/watch?v=vY6965UdcLI
https://www.youtube.com/watch?v=vY6965UdcLI
Conjuntos numéricos 57
Definição
Dois conjuntos A e B possuem a mesma cardinalidade se, e somente se, existe uma bijeção f: A → B. 
Uma bijeção f: A → B é uma função que associa cada elemento de A a um único 
elemento de B e vice-versa, a cada elemento de B, um único elemento de A. Tam-
bém chamamos esse tipo de associação de associação biunívoca ou um para um.
Utilizaremos a definição anterior para classificar os conjuntos de cardinalidade 
infinita em dois grupos diferentes: o grupo dos conjuntos que possuem a mesma 
cardinalidade do conjunto dos números naturais e o grupo dos conjuntos que pos-
suem cardinalidade diferente.
Definição
Um conjunto que é finito ou tem a mesma cardinalidade do conjunto dos números naturais é chama-
do de conjunto enumerável ou conjunto contável. 
Quando um conjunto infinito A é enumerável, indicamos a cardinalidade de A 
por n(A) = ℵ0 (ℵ é alef, a primeira letra do alfabeto hebraico) e dizemos que A tem 
cardinalidade alef zero.
Definição
Um conjunto que não é contável é chamado de incontável ou não enumerável. 
Vejamos um exemplo:
Σxemρlo 3
Vamos mostrar que o conjunto dos números inteiros é enumerável.
Demonstração
Basta considerarmos f:  →  , dada por:
f n 
n se�n�é�par
n - �� se�n�é�ímpar
� � �
�
�
�
��
�
�
�
2
1
2
,
,
É fácil perceber que f é uma bijeção.
58 Matemática Discreta
3.5 Aritmética modular 
Vídeo Para finalizar este capítulo, iremos introduzir a ideia de congruência modular. 
A teoria de congruência modular é muito rica e extensa. Além disso, possui várias 
aplicações; por exemplo, na leitura de um CD. Durante esta seção iremos estudar 
os conceitos básicos de congruência modular.
Definição
Seja m ∈  um número natural, dizemos que a, b ∈  são congruentes módulo m, e escrevemos 
a ≡ b mod m
se m divide a - b, ou seja, se b = a + km para um certo k ∈  .
Vejamos um exemplo:
Σxemρlo 4
a. Se m = 10, temos 32 ≡ 2 mod 10, já que 32 - 2 = 3(10).
b. Se m = 2, temos 27 ≡ -5 mod 2, já que 27 - (-5) = 16(2).
Consideremos as seguintes congruências: 
 • 28 ≡ 7 mod 3 
 • 26 ≡ -4 mod 3 
Note que 28 + 26 ≡ 7 + (-4) mod 3, pois 28 + 26 - (7 + (-4)) = 51 = 17(3). Esse fato 
nos indica que podemos somar congruências. Podemos resumir essa propriedade 
no seguinte teorema:
Teorema 
Sejam m ∈ 

 e a, b, c, d ∈  tais que a ≡ b mod m, c ≡ d mod m. Então, 
a ± c ≡ b ± d mod m.
Além disso, podemos multiplicar congruências, conforme enunciado no próxi-
mo teorema.
Teorema 
Sejam m ∈ 

 e a, b, c, d ∈  tais que a ≡ b mod m, c ≡ d mod m. Então, 
ac ≡ bd mod m.
Vejamos um exemplo:
Σxemρlo 5
Sejam 2 ≡ -5 mod 7 e -5 ≡ 16 mod 7. Então, pelo teorema da multiplicação de 
congruências, temos que 2(-5) ≡ (-5)(16) mod 7.
A aritmética modular está presente 
em vários campos da nossa vida. 
No site Campus Code, , você irá en-
tender como funciona a validação 
de documentos como o CPF.
Disponível em: https://www.
campuscode.com.br/conteudos/o-
-calculo-do-digito-verificador-
-do-cpf-e-do-cnpj. Acesso em: 
5 mar. 2021.
Saiba mais
Conjuntos numéricos 59
Uma outra propriedade da congruência é que para qualquer a ∈  e 
m ∈ , a ≡ 0 mod m se, e somente se, a é múltiplo de m. Além disso, dado um 
número natural m fixo, qualquer número inteiro pode ser descrito por uma con-
gruência com m.
Teorema
Sejam m ∈  e a ∈  , então existe um único r ∈ {0, 1, …, m - 1} tal que 
a ≡ r mod m
Demonstração
Dividindo a por m, utilizando o algoritmo da divisão de Euclides, temos a = qm + r, 
com r ∈ {0, 1, …, m - 1}. Logo, a - r = qm, e isso significa que a ≡ r mod m. A unicidade 
de r é clara, pois o resto da divisão é único. 
Σxemρlo 6
Se m = 6, temos 40 ≡ 4 mod 6, já que 40 - 4 = 6(6). Nesse caso, temos a = 40 e 
r = 4 ∈ {0, 1, 2, 3, 4, 5}.
A operação de congruência módulo m é uma relação de equivalência, ou seja, 
satisfaz as propriedades a seguir:
Teorema 
Sejam m ∈  e a, b, c ∈  . 
a. Reflexiva: a ≡ a mod m.
b. Simétrica: se a ≡ b mod m, então b ≡ a mod m.
c. Transitiva: se a ≡ b mod m e b ≡ c mod m, então a ≡ c mod m.
Demonstração
Vamos provar apenas o item c. Como m | (a - b) e m | (b - c), existem inteiros 
s e t tais que b = a + sm, c = b + tm, em que c = a + (s + t)m, e isso significa que 
a ≡ c mod m.
Σxemρlo 7
Se m = 6, temos 40 ≡ 4 mod 6 e 4 ≡ 22 mod 6. Sendo assim, pelo item c do teo-
rema apresentado, temos que 40 ≡ 22 mod 6.
Agora é com você: prove os itens 
a e b.
Desafio
No livro Códigos correto-
res de erros, você pode 
aprofundar seus conheci-
mentos sobre aritmética 
modular por meio de 
reflexões valiosas sobre as 
propriedades operatórias 
das classes residuais e apli-
cações do tema na teoria 
de informação.
HEFEZ, A.; VILLELA, M. L. T. Rio de 
Janeiro: IMPA, 2017.
Livro
60 Matemática Discreta
CONSIDERAÇÕES FINAIS 
Neste capítulo, você aprendeu conceitos fundamentais dos principais conjun-
tos numéricos, as operações essenciais e suas propriedades operatórias. Com-
preendeu o conceito de divisibilidade e como podemos aplicá-lo para resolver 
problemas matemáticos.
Por fim, você aprendeu a trabalhar com aritmética modular, presente em várias 
aplicações de tecnologia e de segurança, como na criação de um código de barras ou 
de um número de CPF.
ATIVIDADES
1. Mostre que se a, b ∈  , com a, b > 0 e a | b, então a ≤ b.
2. Sejam p
q
 r
s
 c
d
 , , ∈  , mostre que p
q
r
s
 c
d
 p
q
 r
s
c
d
�
�
�
�
�
�
� � � � �
�
�
�
�
�
� .
3. Demonstre o seguinte teorema: sejam m ∈ 

 e a, b, c, d ∈  , tais que a ≡ b mod m, 
c ≡ d mod m, então a + c ≡ b + d mod m.
4. Mostre que a ∈  é par se, e somente se, a ≡ 0 mod 2 e que a é ímpar se, 
e somente se, a ≡ 1 mod 2.
REFERÊNCIAS
GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5. ed. Boston: 
Addison-Wesley, 2004.
IEZZI, G.; MURAKAMI, C. Fundamentos da matemática elementar 1: conjuntos, funções. São Paulo: Atual, 
2013.
LIPSCHUTZ, S.; LIPSON, M. Matemática discreta. 2. ed. Porto Alegre: Bookman, 2004.
ROSEN, K. H. Matemática discreta e suas aplicações. 6. ed. São Paulo: McGraw-Hill, 2009.
Relações 61
4
Relações
Ao estudarmos a teoria elementar de conjuntos, aprendemos a realizar 
diversas operações e comparações entre conjuntos. Porém, quando apro-
fundamos nossos estudos em matemática, geralmente também estamos 
interessados em comparar os elementos dos conjuntos e não apenas os 
conjuntos. Por exemplo, é mais comum comparar números em relação 
à ordem e divisibilidade do que conjuntos numéricos. Em matemática, a 
comparação entre elementos de um ou mais conjuntos é chamada de 
relação entre os conjuntos.
No nosso dia a dia, estamos frequentemente utilizando o conceito 
de relações, como quando comparamos objetos (maior, menor, igual). 
Relações podem ser usadas para resolver problemas tais como determi-
nar quais pares de cidades são ligadas por linhas aéreas em uma rede.
Neste capítulo serão apresentadas as principais propriedades opera-
tórias entre relações, com destaque para dois tipos muito especiais: rela-
ção de ordem e relação de equivalência.
4.1 Produto cartesiano e par ordenado
Vídeo O principal objetivo deste capítulo é estudar relações entre elementos que per-
tencem a um ou mais conjuntos. Para isso precisamos definir uma maneira espe-
cial de organizar elementos.
Definição
Dados dois objetos quaisquer, a e b, chamamos de par ordenado um terceiro objeto (a, b). Nesse caso, 
dizemos que a é a primeira coordenada e b éa segunda coordenada de (a, b).
Observe alguns fatos importantes que decorrem da definição:
a. A ordem dos elementos importa! Ou seja, o par ordenado (a, b) é diferente do 
par ordenado (b, a).
b. Não devemos confundir um par ordenado (a, b) com um conjunto {a, b}.
c. Dois pares ordenados (a, b) e (c, d) são iguais se, e somente se, 
a = c e b = d.
62 Matemática Discreta
São exemplos triviais de pares ordenados:
 • (1, 4), (4, 1), (100, 0).
 • (carro, motocicleta), (Maria, José), (futebol, voleibol).
Durante seus estudos no ensino médio, você provavelmente aprendeu geometria 
analítica e conheceu uma forma de representar pontos ordenados em um plano cha-
mado cartesiano. Para construirmos um plano cartesiano, basta que fixemos uma ori-
gem e dois eixos perpendiculares.
O plano cartesiano que conhecemos é, então, um conjunto de todos os pares or-
denados de números reais. Esse conjunto é chamado de produto cartesiano e pode 
ser generalizado para o produto de conjuntos quaisquer, conforme a definição:
Definição
Dados dois conjuntos A e B, o conjunto de todos os pares ordenados (a, b), com a ∈ A e b ∈ B, é chama-
do de produto cartesiano de A e B, e é denotado por A x B. Em linguagem de conjuntos:
A x B = {(a, b) | a ∈ A e b ∈ B}
Vejamos um exemplo:
Σxemρlo 1
Sejam A � � ��,�� e B � �� � �0 1 2, , , então:
A × B � � � � � � � � � � � � �� �� � �,�� ,� ,�� ,� ,�� , ,�� ,� ,�� ,�� ,��0 1 2 0 1 2  
B × A � � � � � � � � � � � � �� �0 0 1 1 2 2,�� ,� ,�� ,� ,�� ,� ,�� ,� ,�� ,� ,��� � �  
Observamos no exemplo que, em geral, A x B ≠ B x A. Além disso, podemos pro-
var que se n(A) e n(B) são finitos, então: 
n(A x B) = n(B x A) = n(A)n(B)
A ideia de produto cartesiano de dois conjuntos pode ser estendida para o pro-
duto cartesiano de um número finito de conjuntos.
Definição
Dados n conjuntos A
1
, A
2
, ..., A
n
. O conjunto de todas as n-uplas ordenados (a
1
, a
2
, ..., a
n
) com a
i 
∈ A
i
 
é chamado de produto cartesiano de A
1
, A
2
, ..., A
n,
 e é denotado por A
1
 x A
2
 x ... x A
n
. Em linguagem de 
conjuntos:
A
1
 x A
2
 x ... x A
n 
= {(a
1
, a
2
, ..., a
n
) | a
i 
∈ A
i
}
n-upla: é uma lista ordenada, 
denotada por (a
1
, a
2
, ..., a
n
), 
onde a
1
, a
2
, ..., a
n 
são elementos 
pertencentes a um conjunto A
i.
Glossário
Observamos novamente que a ordem dos elementos de uma n-upla importa, 
ou seja, (a1, ..., aj, ..., ak, ..., an) ≠ (a1, ..., ak, ..., aj, ..., an) se ak ≠ (aj). Além disso, se todos 
os n conjuntos Ai são finitos, vale que:
n(A1 x A2 x ... x An) = n(A1) n(A2) ...n(An)
Relações 63
Σxemρlo 2
Sejam A ��� { , }�  , B = {0, 1, 2} e C = {00, 11}, então:
A × B × C � � � � � � � � �{ ,� ,� ,� ,� ,� ,� ,� ,� , ,� ,� ,� ,�� � � � �0 00 0 11 1 00 111 2,,� , ,� ,� ,�00 2 11� � � ��
����������������� , , , , , , , , , , ,   � � � � � � � � � �0 00 0 11 1 00 1� � � � � � 111 2 00 2 11� � � � � �, , , , , , }� � � � � 
E observamos que:
(Δ, 0, 11) ∈ A x B x C, (0, Δ, 11) ∈ B x A x C, (Δ, 11, 0) ∈ A x C x B
A operação de produto cartesiano possui algumas propriedades operatórias. 
Observe algumas no teorema a seguir:
Teorema
Sejam A, B e C conjuntos, então são válidas as seguintes propriedades:
a. A x B = Ø ↔ A = Ø ou B = Ø.
b. Se A ≠ Ø e B ≠ Ø, então A x B = B x A ↔ A = B.
c. Se A ⊂ B, então A x C ⊂ B x C e C x A ⊂ C x B.
d. Se A ≠ Ø, então A x B ⊂ A x C ↔ B ⊂ C.
Demonstração
Vamos provar apenas o item d. Note que se B = Ø, então o resultado é trivial. 
Vamos supor que B ≠ Ø. Seja b ∈ B um elemento qualquer. Como A ≠ Ø, existe no 
mínimo um elemento em A. Vamos considerar que esse elemento seja a, então 
a ∈ A. Assim, se A x B ⊂ A x C, temos:
a ∈ A e b ∈ B → (a, b) ∈ A x B → (a, b) ∈ A x C → a ∈ A e b ∈ C
Onde B ⊂ C.
Suponha agora que B ⊂ C. Seja (a, b) ∈ A x B, então, pela definição de produto 
cartesiano, a ∈ A e b ∈ B. Como B ⊂ C, temos que b ∈ C, ou seja, (a, b) ∈ A x C. Pro-
vando que A x B ⊂ A x C.
A operação de produto cartesiano também pode ser combinada com as demais 
operações entre conjuntos (interseção, união e diferença), satisfazendo as seguin-
tes propriedades distributivas.
Teorema
Sejam A, B e C conjuntos, então são válidas as seguintes propriedades 
distributivas:
a. A x (B∩C) = (A x B)∩(A x C).
b. (A∩B) x C = (A x C)∩(B x C).
c. A x (B∪C) = (A x B)∪(A x C).
d. (A∪B) x C = (A x C)∪(B x C).
a. A x (B\C) = (A x B)\(A x C).
b. (A\B) x C = (A x C)\(B x C).
Agora é com você: prove os itens 
a, b e c.
Desafio
64 Matemática Discreta
Demonstração
Vamos provar apenas os itens c e e.
Para o item c, temos que:
(a, b) ∈ A x (B∪C) ↔ a ∈ A e b ∈ (B∪C) 
↔ a ∈ A e (b ∈ B ou b ∈ C) 
↔ (a ∈ A e b ∈ B) ou (a ∈ A e b ∈ C) 
↔ (a, b) ∈ A x B ou (a, b) ∈ A x C
↔ (a, b) ∈ (A x B) U (A x C)
Provando que A x (B∪C) = (A x B)∪(A x C).
Para o item e, temos que:
(a, b) ∈ A x (B\C) ↔ a ∈ A e b ∈ (B\C) 
↔ a ∈ A e (b ∈ B e b ∉ C)
↔ (a ∈ A e a ∈ A) e (b ∈ B e b ∉ C)
↔ a ∈ A e (b ∈ B e a ∈ A) e b ∉ C)
↔ (a ∈ A e b ∈ B) e (a ∈ A e b ∉ C)
↔ (a, b) ∈ A x B e (a, b) ∉ A x C
↔ (a, b) ∈ (A x B)\(A x C)
Provando que A x (B\C) = (A x B)\(A x C).
O produto cartesiano A x A é chamado de quadrado cartesiano de A, o qual é 
denotado por A2, ou seja, A2 = {(x, y) | x, y ∈ A}. Denotamos por Da o conjunto cha-
mado de diagonal de A2, o qual é formado pelos pares ordenados (x, x) ∈ A2, ou seja, 
Da = {(x, x) | x ∈ A}.
Por exemplo, considerando o conjunto A = {1, 2}, temos:
A2 = {(1, 1), (1, 2), (2, 1), (2, 2)} e Da = {(1, 1), (2, 2)}
Observamos também que se A é um conjunto com cardinalidade finita, digamos 
n(A) = m, então n(A2) = m2 e n(Da) = m.
4.2 Conceito de relação
Vídeo Uma relação é uma ferramenta matemática que considera o vínculo de certo 
elemento de um conjunto com elementos de um ou mais conjuntos. As relações 
são amplamente utilizadas na ciência da computação, especialmente em bancos de 
dados e códigos corretores de erros.
No artigo Modelagem do problema de alocação de frota de uma empresa aérea brasileira, dos auto-
res Daniel J. Caetano e Nicolau D. F. Gualda, publicado em 2008 no congresso anual da Associação 
Nacional de Pesquisa e Ensino em Transportes (ANPET), você pode conhecer mais a respeito de 
resolução de problemas com relações entre conjuntos.
Acesso em: 5 mar. 2021. 
https://www.caetano.eng.br/trabalhos/getfile.php?fn=2008_XXII_ANPET_Anais.pdf
Artigo
Agora é com você: prove os itens 
a, b, d e f.
Desafio
https://www.caetano.eng.br/trabalhos/getfile.php?fn=2008_XXII_ANPET_Anais.pdf
Relações 65
Notemos as seguintes relações matemáticas:
 • Menor que: 1 < π, o número real 1 está relacionado com o número π por essa 
relação.
 • Contido em: {1, 2} ⊂ , o conjunto {1, 2} está relacionado com o conjunto  
por essa relação.
Observamos, então, que uma relação é uma regra para fazer uma afirmação 
sobre dois elementos, que podem ou não pertencer ao mesmo conjunto. Em ou-
tros termos, para descrevermos uma relação de um conjunto A em B, precisamos 
escolher (ou definir uma regra de como escolher) pares (a, b) ∈ A x B. Em termos de 
teoria de conjuntos, podemos definir uma relação como segue.
Definição
Dados dois conjuntos A e B, uma relação binária R de A em B é um subconjunto do produto cartesiano 
A x B.
Se A = B, chamaremos a relação R de relação binária em A.
Vejamos um exemplo:
Σxemρlo 3
Dados A = {4, 5, 6} e B = {a, b, c}, podemos definir relações de A e B escolhendo 
pares ordenados aleatoriamente em A x B, por exemplo:
R �a �R �a � �c1 � � �� � � � � � �� �4 4 62, , , , , e R a b c b3 � � � � � � � � �� �4 5 6 6,� , ,� , ,� , ,�
Observe também que, no exemplo anterior, R R21 ⊂ e R R31 ⊂ , porém, R R2 3⊄ .
Dado dois conjuntos A e B e uma relação R de A em B, existem alguns subcon-
juntos especiais de R que são utilizados para descrever a relação.
Definição
Seja R A B� � uma relação de A em B, o domínio de R , denotado por Dom R� � é o conjunto de 
todos os elementos em A que estão relacionados com algum elemento em B.
Vejamosum exemplo:
Σxemρlo 4
Considere os conjuntos A = {4, 5, 6} e B = {a, b, c}. Qual é o domínio da relação 
R3 de A em B, dada por R 4, a , 5, b3 � � � � �� �?
66 Matemática Discreta
Temos por definição que o domínio de R3 é Dom R = 4, �53� � � �.
Definição
Seja R A B � � uma relação de A em B, a imagem de R, denotada por Ran R� � ou Im R� � , é o con-
junto de todos os termos de B que são os segundos termos dos pares de R.
Vamos considerar um exemplo:
Σxemρlo 5
Considere os conjuntos A = {8, 9, 10} e B = {x, y, z}. Qual é a imagem da relação 
R1 de A em B, onde R1 é dada por R = 8, x , 9, y ,� 10,� y 1 � � � � � �� �?
Temos por definição que a imagem de R1 é Im R x �y1� � � � �, , pois x e y são os se-
gundos termos dos pares (8, x), (9, y) e (10, y), ou seja, pares de R1.
Definição
Seja R A B� � uma relação de A em B, se x ∈ A, definimos o conjunto R x� � dos R-relativos de 
x como sendo o conjunto de todos os y ∈ B com a propriedade de que x está relacionado a y por R , 
ou seja:
R x = {y B | xRy}� � �
Esclarecemos a definição de R -relativos de x com o seguinte exemplo:
Σxemρlo 6
Sejam A e B dois conjuntos, onde A = {8, 9, 10}, B = {x, y, z} e R1 a relação de A 
em B dada por:
R = 8,�x , 9,�y ,� 10,�y ,� 8,�z ,� 9,�z 1 � � � � � � � � � �� �
Descreva o conjunto R1 8� �.
Pela definição de conjunto dos 1-relativos de 8, tem-se R y B � R y1 18 8� � � �{ | }. 
Como em R1 temos 8 nos pares (8, x) e (8, z), ou seja, o 8 está relacionado a x e z, 
temos que R x �z1 8� � � � �, .
Relações 67
Definição
Seja R A B� � uma relação de A em B, se A
1 
⊂ A, definimos o conjunto R A1� � dos R-relativos de 
A
1
 como sendo o conjunto de todos os b ∈ B com a propriedade de que x está relacionado a y por R e 
x ∈ A
1
. Em símbolos:
R A b B xRy e x A1 1� �� � �{ | }
Esclareceremos a definição de -relativos de A1 com o exemplo a seguir.
Σxemρlo 7
Considere A e B dois conjuntos, onde A = {8, 9, 10} e B = {x, y, z}, sendo R1 a re-
lação entre eles dada por:
R = 8, x ,� 8, y , 9, y ,� 10,�y ,� 8, z ,� 9,�z 1 � � � �� � � � � � � � � � � �� �
Considerando A1 ⊂ A dado por A1 = {9, 10}, descreva o conjunto R A1 1� �.
Pela definição de conjunto dos R1-relativos de um subconjunto A1 de A, tem-se 
R A b B� �xR y�e�x A1 1� � � � �{ | }1 1 . Ou seja, R A = y,�z1 1� � � � .
Para finalizar esta seção, destacamos as seguintes relações triviais para um con-
junto A:
 • Relação vazia: corresponde ao conjunto vazio Ø ⊂ A2.
 • Relação total: corresponde ao próprio produto cartesiano A2.
 • Relação diagonal: �
A
a b A b a2
2� � �� �� �, ; .
A relação diagonal também é chamada de relação identidade e é denotada por 
Ia ou Ida. Observamos também que o número de elementos da relação diagonal é 
igual ao número de elementos do conjunto A.
Σxemρlo 8
Considere os conjuntos A = {0, 1, 2, 3} e B = {x, y}. Determine a relação diagonal 
de cada conjunto.
Pela definição, temos que �
A
a b A b a2
2� � �� �� �, ; , ou seja, a relação diagonal 
do conjunto A é dada por �
A2
� � � � � � � � �� �0,�0 , 1,�1 , 2,�2 , 3,�3 , e a relação diagonal do 
conjunto B é dada por �
B2
� � � � �� �x,�x , y,�y .
68 Matemática Discreta
4.3 Relação inversa
Vídeo Nesta seção aprenderemos a definir uma relação do conjunto B no conjunto A, 
com base em uma relação de A em B.
Definição
Dada uma relação binária R de A em B, chamamos de relação inversa de R o conjunto
R y, x B A x, y R� � � �� � � ��1 { | }
Notamos que se R é uma relação binária de A em B, então R-1 é subconjunto de 
B x A, ou seja, R-1 é uma relação binária de B em A. Além disso, temos que:
y,�x R x, y R� �� � ����1
Segue da definição que R−1 é o conjunto dos pares ordenados obtidos a partir 
dos pares ordenados de R, invertendo-se a ordem dos termos em cada par. Veja-
mos um exemplo:
Σxemρlo 9
Dados A = {0, 1, 2, 3} e B = {1, 3, 5, 7} com relação R entre esses conjuntos dada 
por R x �y A B� �x y� � �� � � �{ , | }1 , determine os elementos de R e de R−1, usando a 
notação de conjunto.
Pela definição de R, temos que:
R= 0,�3 ,� 0,�5 ,� 0,�7 ,� 1,�3 ,� 1,�5 ,� 1,�7 ,� 2,�5 ,�� � � � � � � � � � � � � � 22,�7 ,� 3,�5 ,� 3,�7� � � � � �� �
E pela definição de relação inversa, teremos:
R = 3,�0 ,� 5,�0 ,� 7,�0 ,� 3,�1 ,� 5,�1 ,� 7,�1 ,� 5,�2-1 � � � � � � � � � � � � � � ,,� 7,�2 ,� 5,�3 ,� 7,�3� � � � � �� �
Teorema
Sejam A e B conjuntos, R uma relação de A em B e R−1 sua relação inversa, então 
são válidas as seguintes propriedades:
 • Dom R = Im R-1� � � �;
 • Im R = Dom R-1� � � �;
 • R = R-1
-1� � .
Não demonstraremos o teorema anterior, mas vamos ilustrá-lo com um exemplo.
Σxemρlo 10
Dados A = {a, b, c} e B = {1, 3}, e a relação R de A em B dada por 
R = a,�1 , b,�1 ,� b,�3 ,� c,�3� � � � � � � �� �, vamos comparar o domínio e a imagem de R e de R−1.
Relações 69
Como R = a,�1 , b,�1 ,� b,�3 ,� c,�3� � � � � � � �� �, tem-se por definição que Dom R = a,�b,�c� � � � 
e Im R = 1,�3� � � �. Determinando R−1, temos que R = 1,�a , 1,�b ,� 3,�b ,� 3,�c -1 � � � � � � � �� �, 
onde Dom R = 1,�3-1� � � � e Im R = a,�b,�c-1� � � � .
Sendo assim, são verdadeiras as afirmações do teorema anterior.
4.4 Propriedades das relações
Vídeo Ao definirmos relações de A em B como subconjuntos do produto cartesiano A 
x B, adquirimos a grande vantagem de colocar à nossa disposição todo o nosso co-
nhecimento sobre teoria de conjuntos para descrever propriedades a respeito de 
relações. Entretanto, é comum encontrarmos na literatura a descrição de relação 
entre dois elementos por meio de um símbolo entre eles. Por exemplo, x + y e x > y 
expressam duas relações matemáticas: a relação de soma e a relação de maior que.
As relações x + y e x > y podem ser escritas na linguagem de conjuntos como:
 • x y x,�y� � � ���
 • x y x,�y� � � ����
Em geral, para uma dada relação R de A em B, escrevemos:
aRb a �b R� � ��,
para representar que a está relacionado com b.
Ao considerarmos um conjunto A não vazio e uma relação interna R em A, isto 
é, uma relação R de A em A, podemos explorar algumas propriedades importantes. 
São elas o objeto de estudo desta seção.
Definição
Dado um conjunto A não vazio, uma relação binária R em A é reflexiva se para todo a ∈ A temos que 
a está relacionado com a. Em símbolos:
R é reflexiva se� �a A aRa, .
A relação de igualdade (=) é reflexiva em qualquer conjunto numérico, uma vez 
que escrever, por exemplo, 2 = 2 é equivalente a escrever 2 = 2 (invertendo a ordem 
dos números dois).
Nem toda relação em um conjunto é reflexiva, como podemos observar no se-
guinte exemplo.
Σxemρlo 11
Dado o conjunto A = {1, 2, 3}, considere a relação R1 em A dada por 
R = 1,1 , 2,2 , 1,2 , 2,1 1 � � � � � � � �� �. Verifique que R1 não é reflexiva.
Claramente R1 não é reflexiva, pois 3 ∈ A e 3 3 1, .� R� ��
70 Matemática Discreta
Definição
Dado um conjunto A não vazio, uma relação binária R em A é simétrica se, para todo a, b ∈ A, temos 
que a está relacionado com b se, e somente se, b está relacionado com a. Em símbolos:
R é simétrica se � , ,� � ��a �b A �aRb bRa
A relação de diferença (≠) é simétrica em qualquer conjunto numérico, uma vez 
que escrever, por exemplo, 3 ≠ 2 é equivalente a escrever 2 ≠ 3.
Nem toda relação em um conjunto é simétrica, como podemos observar no 
seguinte exemplo.
Σxemρlo 12
Dado o conjunto A = {a, b, c}, considere a relação R2 em A dada por 
R = a, a , b, b , c, c , a, b , b, c , a, c 2 � � � � � � � � � � � �� � . Verifique que R2 não é simétrica.
Claramente R2 não é simétrica, pois a �c A � a �c R �e� c �a R �, , , , .� � �� � ��2 2
Definição
Dado um conjunto A não vazio, uma relação binária R em A é assimétrica se, para todo a, b ∈ A, tal 
que a está relacionado com b, temos que b não está relacionado com a. Em símbolos.
R é assimétrica se� � � �� �� ��a b A se a, b R b, a R, .
Vejamos um exemplo:
Σxemρlo 13
Dado o conjunto A = {1, 2, 3}, claramente a relação R1 em A, dada por 
R = 1,�2 ,�� 3,1 1 � � � �� �, é assimétrica.
Novamente, nem todarelação em um conjunto é assimétrica, como podemos 
observar no seguinte exemplo:
Σxemρlo 14
Dado o conjunto A = {a, 3, d}, considere a relação R2 em A dada por 
R = a, a , d, d , d, a ,� a, d2 � � � � � � � �� �. Verifique que R2 não é assimétrica.
Relações 71
Claramente 2 não é assimétrica, pois a �d A � a �d R �e� d �a R �, , , , .� � �� � ��2 2
Definição
Dado um conjunto A não vazio, uma relação binária R em A é antissimétrica se, para todo a, b ∈ A, 
tal que a está relacionado com b e b está relacionado com a, então a = b. Em símbolos:
R é antissimétrica se� � � �� � �� �a b A se a, b R e b, a R a = b,
A relação “menor que” (<) é antissimétrica em qualquer conjunto numérico. Uma 
vez que escrever, por exemplo, 1 < 2 implica que não podemos escrever 2 < 1, pois 2 
não é menor que 1.
Nem toda relação em um conjunto é antissimétrica, como podemos observar 
no exemplo a seguir.
Σxemρlo 15
Dado o conjunto A = {a, 3, d}, considere a relação R2 em A dada por 
R = a, a , d, d , d, a , � a, d 2 � � � � � � � �� �. Verifique que R2 não é antissimétrica.
Claramente R2 não é antissimétrica, pois a �d A � a �d R �e� d �a R, , , ,� � �� � ��2 2 e a ≠ d.
Definição
Dado um conjunto A não vazio, uma relação binária R em A é transitiva se, para todo a, b, c ∈ A, tal 
que a está relacionado com b e b está relacionado com c, então a está relacionado com c. Em símbolos:
R é transitiva se� � �a b c Ase aRb e bRc aRc, , , .
A relação “menor que” (<) é transitiva em qualquer conjunto numérico, uma vez 
que escrever, por exemplo, 1 < 2 e 2 < 3 implica escrever que 1 < 3.
Nem toda relação em um conjunto é transitiva, como podemos observar no 
seguinte exemplo.
Σxemρlo 16
Considere a seguinte relação no conjunto dos números reais: � � � � ��x �y �xRy x� �y, , 1 
� � � � ��x �y �xRy x� �y, , 1. Verifique que essa relação R não é transitiva.
R não é transitiva. Para provar isso basta apresentar um contraexemplo. Note 
que 2 2,� ��R e 2 12,
�
�
�
�
�
��R , porém 2
1
2
,�
�
�
�
�
��R .
72 Matemática Discreta
4.5 Operações e fecho de relações
Vídeo Utilizando o fato de que uma relação entre dois conjuntos A e B pode ser consi-
derada como um subconjunto do produto cartesiano A x B, iremos utilizar as ope-
rações usuais entre conjuntos para definir algumas operações entre relações.
Definição
Sejam R e S A B� � duas relações de A em B, então a relação interseção entre R e S é a relação 
R S∩ de A em B dada por:
a R S b aRb e aSb�� � �
Vejamos um exemplo:
Σxemρlo 17
Considere A = {0, 1, 2, 3} e B = {x, y}, e as relações:
R = 0, x , 1, x , 2, y , 3, x� � � � � � � �� � e S = 0, x , 3, y� � � �� �
Descreva a relação R S∩ .
Note que 0, �x R�e� 0, x S� �� � �� , onde o único elemento da relação R S∩ é (0, x). Ou 
seja, R S �x� � � �� �0, .
Definição
Sejam R e S A B� � duas relações de A em B, então a relação união entre R e S 
é a relação R S∪ de A em B dada por:
a R S b aRb ou aSb�� � �
Vejamos um exemplo:
Σxemρlo 18
Considere A = {0, 1, 2, 3} e B = {x, y}, e as relações:
R = 0, x , 1, x , 2, y , 3, x� � � � � � � �� � e S = 0, x , 3, y� � � �� �
Descreva a relação R S∪ .
Note que, por definição, precisamos apenas reunir todos os elementos das rela-
ções R e S, ou seja, R S = 0,�x ,� 1,�x ,� 2,�y ,�� 3,�x ,� 3,�y .� � � � � � � � � � �� �
Relações 73
Definição
Sejam R e S A B� � duas relações de A em B, então a relação diferença entre R e S é a relação R\S 
de A em B dada por:
a R\S b a b R e a, b S� � �� �� � ��,
Vejamos um exemplo:
Σxemρlo 19
Considere A = {0, 1, 2, 3} e B = {x, y}, e as relações:
R = 0, x , 1, x , 2, y , 3, x� � � � � � � �� � e S = 0, x , 3, y� � � �� �
Descreva a relação R S\ .
Pela definição de R S\ , temos que R\S = 1,�x ,� 2,�y ,� 3,�x� � � � � �� �.
Definição
Seja R A B� � uma relação de A em B, então a relação complementar de R é a relação Rc de A 
em B dada por:
a R b a, b Rc� � � � � �
Essa definição nos diz que a relação complementar é formada por todos os ele-
mentos (a, b) ∈ A x B que não estão R-relacionados.
Por fim, definiremos a operação mais importante entre relações: a operação 
composição.
Definição
Seja R uma relação de A em B e S uma relação de B em C, definimos a relação composta S R de 
A e C da seguinte forma:
S R a, c A C b B a, b R e b, c S � � � � � � �� � � � � � � �� �; ,
Vejamos um exemplo:
Σxemρlo 20
Sejam A = {1, 2, 3}, B = {x, y, z} e C = {α, β, γ} três conjuntos dados, considere as 
seguintes relações:
R = 1, x , 2, x , 3, z A B� � � � � �� � � � ;
S = x, , y, , y, , z, B C� � � �� � � � � � � �� � � � .
Verifique que 1,���� ��S R .
O símbolo ∘ significa a compo-
sição das funções e lemos “ S 
bola R ”. É a notação utilizada 
para a função g composta com 
a função f.
Glossário
74 Matemática Discreta
De fato, notamos que 1,���� ��S R , pois 1, x R� �� e x S,���� �� .
A relação composta satisfaz as propriedades enunciadas no teorema a seguir.
Teorema
Considere as relações R A B �S B C� � � �, e T C D� � , então:
a. T S R = T S R   � � � � .
b. S R = R S-1 -1 -1 � � .
Demonstração
Provaremos apenas o item a. Claramente, T S R � � e T S R � � são relações de 
A e D. Seja (a, d) ∈ A x B um elemento qualquer, se a, d T S R� �� � �  , pela definição 
de composição, existe um elemento c ∈ C tal que a, c S R� ��  e c, d T� �� . Como 
a, c S R� ��  , podemos usar novamente a definição de composição e obter um ele-
mento b ∈ B tal que a, b R� �� e b, c S� �� .
Agora, sabemos que b, c S� �� e c, d T� �� , e podemos concluir que b, d �T S.� �� 
Da mesma forma, de a, b R� � � e b, d �T S� � �  , segue-se que a, d T S R� � � � �  . Isso 
prova que T S R T S R   � � � � � .
Para provar a inclusão contrária e concluir a prova, basta repetir o argumento apre-
sentado a partir de um elemento a, d T S R� � � � �  , para mostrar que a, d T S R� � � � �  .
4.6 Relação de ordem e de equivalência
Vídeo Nesta seção, iremos estudar duas classes muito especiais de relações entre con-
juntos: as relações de ordem e de equivalência. Essas duas classes de relações são 
as mais estudas em toda a matemática.
Definição
Dado um conjunto A não vazio, uma relação binária R em A é dita relação de ordem parcial em A se for 
reflexiva, antissimétrica e transitiva.
Vejamos um exemplo:
Σxemρlo 21
Verifique que a relação “divide” nos números naturais é uma relação de ordem 
parcial.
Agora é com você: prove o item b.
Desafio
Relações 75
Para verificar que a relação “divide” é de ordem parcial, analisamos suas 
propriedades:
 • É reflexiva porque x | x.
 • É antissimétrica porque x | y e y | x implica x = y.
 • É transitiva porque x | y e y | z implica x | z.
Portanto, é uma relação de ordem parcial.
Outra relação de ordem parcial clássica que podemos citar é a relação “menor 
ou igual” (≤) nos números naturais. Porém, note que a relação “menor que” (<) não 
é uma ordem parcial, porque não é reflexiva.
Frequentemente, uma relação de ordem parcial é denotada com o símbolo  
em vez de uma letra, como R. Isso faz sentido, uma vez que evoca o símbolo ≤, que 
é uma das ordens parciais mais comuns.
Definição
Dado um conjunto A e uma ordem parcial  no conjunto A, o par P A�� �, é chamado de conjunto 
parcialmente ordenado ou poset.
A representação gráfica dos posets, quando A é finito, é dada pelo Diagrama de 
Hasse. Dado um poset finito A �, ,� � os elementos de A são representados por vér-
tices e as relações dos elementos por arestas, convencionando que um elemento a 
∈ A está abaixo de b ∈ A se, e somente se, a b . Vejamos um exemplo:
Σxemρlo 22
Considere P A �� � �,  o poset definido sobre o conjunto A = {1, 2, 3, 4} e com 
ordem parcial:
       :� , , , , , ,� � �� � � � � � �1 1 2 2 3 3 4 4 1 3 2 3 2 4
Descreva o Diagrama de Hasse de P.
O Diagrama de Hasse de P A �� � �,  é
3 4
1 2
Vejamos como é descrito o Diagrama de Hasse de uma relação de ordem parcialformada apenas por relações reflexivas.
76 Matemática Discreta
Σxemρlo 23
Considere P A �� � �,  o poset definido sobre o conjunto A = {1, ..., n} e com ordem 
parcial  formado apenas pelas relações reflexivas dos elementos, ou seja,
    :� , , , ,� �� �� � � �n n1 1 2 2 3 3
Descreva o Diagrama de Hasse de P.
Como não existem elementos a, b ∈ A distintos, tais que a ≠ b e a b , isso signi-
fica que não existirá nenhuma aresta no Diagrama de Hasse de P A �� � �,  . Sendo 
assim, o Diagrama de Hasse de P A �� � �,  é:
1 2 n – 1 n…
O poset do exemplo anterior é muito importante e recebe o nome de poset de 
Hamming ou poset anticadeia. Sua importância se dá pelo fato de estar relacionado 
com a famosa métrica de Hamming, a qual é utilizada para identificar erros em 
teoria de informação.
Definição
Dado um conjunto A não vazio, uma relação binária R em A é dita relação de equivalência em A se for 
reflexiva, simétrica e transitiva.
O exemplo mais óbvio de relação de equivalência é a igualdade em um conjunto 
numérico.
Σxemρlo 24
Verifique que a igualdade no conjunto dos números reais  é uma relação de 
equivalência.
Para verificar que a igualdade é uma relação de equivalência, analisamos suas 
propriedades:
 • É reflexiva: ∀ a ∈ , a = a.
 • É simétrica: ∀ a, b ∈ , a = b → b = a.
 • É transitiva: ∀ a, b, c ∈ , a = b e b = c → a = c.
Portanto, é uma relação de equivalência.
Para saber mais sobre a 
identificação de erros na 
teoria de informação, re-
comendamos o Capítulo 1 
do livro Códigos corretores 
de erros. Nele, é abordado 
o conceito e equivalên-
cia de códigos, além da 
métrica de Hamming. Uma 
excelente complementa-
ção para seus estudos.
HEFEZ, A.; VILLELA, M. L. Rio de 
Janeiro: IMPA, 2017.
Saiba mais
Relações 77
Observe que existe uma pequena diferença entre relação de ordem e relação 
de equivalência: Toda relação de ordem é antissimétrica e toda relação de equi-
valência é simétrica.
Vejamos mais um exemplo de relação de equivalência:
Σxemρlo 25
Verifique que se a, b ∈ , a relação a ≡ b mod 2 é uma relação de equivalência 
em .
Para verificarmos que é relação de equivalência, vamos mostrar que é uma re-
lação reflexiva, simétrica e transitiva. De fato,
 • É reflexiva:
Para cada a ∈ , temos:
a – a = 0 = 2 · 0 → a ≡ a mod 2
 • É simétrica:
Se a, b ∈ , tais que a ≡ b mod 2, então existe k ∈ , tal que:
a – b = 2k → b – a = 2(–k) → b ≡ a mod 2
 • É transitiva:
Se a, b, c ∈ , tais que a ≡ b mod 2 e b ≡ c mod 2, então existe k1, k2 ∈ , tais que 
b – a = 2k1 e c – b = 2k2. Adicionando essas duas igualdades, temos:
(c – b) + (b – a) = 2k1 + 2k2 → c – a = 2(k1 + k2) →
c – a = 2k, com k = k1 + k2 ∈ 
Portanto, a ≡ c mod 2.
Logo, a relação a ≡ b mod 2 é de equivalência.
Há outra maneira de pensarmos sobre as relações de equivalência, mas vamos 
precisar de algumas definições para entender essa perspectiva alternativa.
Definição
Dado que R é uma relação de equivalência em um conjunto A, então, a classe de equivalência de um 
elemento x ∈ A é o conjunto de todos os elementos em A relacionados a x por R. A classe de equiva-
lência de x é denotada por [x]. Assim, em símbolos:
x x� �xRy�� �� � { | } .
78 Matemática Discreta
Vejamos um exemplo:
Σxemρlo 26
Seja A =  e R x �y�mod�� �� �5 � uma relação de A. Determine a classe de equiva-
lência [7] e a compare com as classes [12] e [17].
Nesse caso, temos que [7] é o conjunto de todos os elementos em  que estão 
relacionados a 7 por R x �y�mod�� �� �� �5 , assim:
[7] = {..., -3, 2, 7, 12, 17, 22, ...}.
Ao comparar [7] com as classes [12] e [17], observamos que [7] = [12] = [17].
Definição
Uma partição de um conjunto A é uma coleção de subconjuntos disjuntos e não vazios A
1
, A
2
, ..., A
n
 cuja 
união é A.
Vejamos um exemplo:
Σxemρlo 27
Considere o conjunto A = {a, b, c, d, e}. Vamos encontrar uma partição de A.
Existe mais de uma partição possível para A. Podemos considerar, por exem-
plo, a partição formada pelos conjuntos A1 = {a, c}, A2 = {b, e}, A3 = {d}. Existe uma 
correspondência entre relações de equivalência em A e partições de A. Podemos 
simplificar essa correspondência no seguinte teorema.
Teorema
As classes de equivalência de uma relação de equivalência em um conjunto A 
formam uma partição de A.
Vejamos um exemplo do teorema:
Σxemρlo 28
Considere o conjunto dos números inteiros ℤ e a relação de congruência mó-
dulo 5 (≡ mod 5). Determine a quantidade e quais são as classes de equivalência 
dessa relação.
Relações 79
Essa relação particiona o conjunto dos números inteiros em cinco classes de 
equivalência, a saber:
 • [0] = {..., -5, 0, 5, 10, 15, 20, ...}
 • [1] = {..., -4, 1, 6, 11, 16, 21, ...}
 • [2] = {..., -3, 2, 7, 12, 17, 22, ...}
 • [3] = {..., -2, 3, 8, 13, 18, 23, ...}
 • [4] = {..., -1, 4, 9, 14, 19, 24, ...}
CONSIDERAÇÕES FINAIS 
Neste capítulo, você aprendeu a realizar o produto cartesiano entre conjuntos 
e viu que essa operação pode ser utilizada para definir relações entres conjun-
tos que, por sua vez, podem ser empregadas para solucionar problemas práticos, 
como na malha aérea de uma empresa.
Além disso, estudamos que é possível realizar operações entre relações e como 
definir a relação inversa de uma dada relação. E, por fim, nos debruçamos sobre dois 
tipos especiais de relações, as de ordem – que podem ser encontradas em aplicações 
de teoria da informação – e as de equivalência – aprendendo a relacioná-las com par-
tição de um conjunto.
ATIVIDADES 
1. Sejam A, B e C conjuntos. Prove que:
Se A ⊂ B, então A x C ⊂ B x C.
2. Sejam A, B e C conjuntos. Prove que:
(A∩B) x C = (A x C)∩(B x C).
3. Sejam A = {x ∈ ℕ | x ≤ 7} e R a relação em A dada por:
R { x �y A A�|x y 9� � �� � � �, }
Determine os conjuntos R,�R ,�Dom R ,�Dom R ,�Im R ,�Im R-1 -1 -1� � � � � � � � .
4. Seja m ∈ N, m > 1. Mostre que R { x,�y |x y�mod�m� � � � } é uma relação de 
equivalência em Z.
REFERÊNCIAS
GERSTING, J. L. Fundamentos matemáticos para Ciência da Computação. 4. ed. São Paulo: LTC, 2001.
GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5. ed. Boston: Addison-
Wesley, 2004.
IEℤℤI, G.; MURAKAMI, C. Fundamentos da matemática elementar 1: conjuntos, funções. São Paulo: Atual, 
2013.
ROSEN, K. H. Matemática discreta e suas aplicações. 6. ed. São Paulo: McGraw-Hill, 2009.
80 Matemática Discreta
5
Funções discretas
O objetivo primordial de estudar matemática é aprender técnicas para 
conseguir descrever objetos da natureza por meio de ferramentas mate-
máticas, a fim de solucionar problemas e desenvolver novas tecnologias. A 
principal ferramenta é o conceito de função, o qual nos ajuda a agrupar e 
descrever elementos por meio de uma regra.
Neste capítulo, vamos apresentar as principais propriedades de fun-
ções. Você aprenderá a definir uma função entre dois conjuntos A e B 
por meio de uma relação entre esses conjuntos e a classificá-la em inje-
tora, sobrejetora e bijetora. Além disso, aprenderá a realizar uma opera-
ção muito importante entre funções: a composição. Iremos ainda utilizar 
funções para contar o número de elementos em um conjunto e, por fim, 
definiremos funções de maneira recursiva.
5.1 Conceito e classificação 
Vídeo Funções como f(x) = x2 + x – 1 e g(x) = x · tg–1(x) são certamente bastante fami-
liares nas disciplinas de cálculo. Em matemática discreta, usaremos funções para 
contagem, mas de uma forma que pode não ser familiar. Em vez de utilizarmos fun-
ções que mapeiam um número real para outro, usaremos funções que relacionam 
elementos de conjuntos finitos.
Para contar com precisão, precisamos definir cuidadosamente a noção de 
função.
Definição
Uma função f entre os conjuntos X e Y é uma regra que associa a cada elemento x ∈ X um único ele-
mento de Y, denotado por f(x) ∈ Y.
É comum representarmos uma função de um conjunto X em um conjunto Y por:
 f: X → Y
   x  y = f(x)
Uma função f: X → Y também pode ser considerada uma relação entre dois con-juntos, X e Y, que relaciona cada elemento de X a um elemento de Y. O conjunto X é 
chamado de domínio da função f, e Y é chamado de contradomínio.
Funções discretas 81
Aqui está um exemplo ilustrativo de uma função:
Domínio Contradomínio
a
b
c
d
e
X f Y
1
2
3
4
5
Notamos que f: X → Y, onde o conjunto X = {a, b, c, d, e} é o domínio e o contra-
domínio é o conjunto Y = {1, 2, 3, 4, 5}. Os elementos relacionados são unidos por 
uma seta e indicam que f mapeia:
 • a para 1.
 • b para 3.
 • c para 4.
 • d para 3.
 • e para 5.
De modo equivalente, f(a) = 1, f(b) = 3, f(c) = 4, f(d) = 3 e f(e) = 5.
É importante lembrarmos que para uma relação de um conjunto X em um con-
junto Y definir uma função de X em Y, é necessário que cada elemento de X esteja 
relacionado com um, e apenas um, elemento de Y. Observe, por exemplo, as rela-
ções a seguir:
a
b
c
d
e
X Y
1
2
3
4
5
a
b
c
d
e
X Y
1
2
3
4
5
As relações apresentadas não são funções; a primeira, porque a está relaciona-
do com dois elementos do contradomínio (1 e 2), e a segunda, porque b e d não 
estão relacionados com nenhum elemento do contradomínio.
Definição
Sejam X e Y conjuntos, A ⊂ X e f: X → Y uma função, a imagem direta de A é o conjunto
f(A) = {f(x) ∈ Y | x ∈ A}
Observe que dada uma função f: X → Y, a imagem direta de um conjunto 
A ⊂ X é formada pelos elementos y do contradomínio Y, tais que existe um x ∈ A 
que está relacionado com y. Além disso, a imagem direta de A é um subconjunto 
do contradomínio.
82 Matemática Discreta
Σxemρlo 1
Seja uma função f, com domínio X = {a, b, c, d, e} e contradomínio Y = {1, 2, 3, 4, 5}, 
onde f(a) = 1, f(b) = 3, f(c) = 4, f(d) = 3 e f(e) = 5. Determine a imagem direta dos sub-
conjuntos A1 = {a, b} e A2 = {c, d, e}.
Se A1 = {a, b}, temos que f(A1) = {1, 3}. Analogamente, se A2 = {c, d, e}, temos que 
f(A2) = {3, 4, 5}.
Teorema
Sejam A, B ⊂ X e f: X → Y uma função, a imagem direta é tal que:
a. f(A∪B) = f(A)∪f(B)
b. f(A∩B) ⊂ f(A)∩f(B)
Demonstração
Vamos provar apenas o item a. Se y ∈ f(A∪B), então, existe x ∈ A∪B, tal que 
f(x) = y. Se x ∈ A, temos que y ∈ f(A). Se, porém, x ∈ B, temos que y ∈ f(B). Em qual-
quer caso, y ∈ f(A)∪f(B). Logo, f(A∪B) ⊂ f(A)∪f(B).
Reciprocamente, seja z ∈ f(A)∪f(B), então z ∈ f(A) ou z ∈ f(B). No primeiro caso, 
existe x ∈ A, tal que z = f(x). No segundo, existe y ∈ B, tal que z = f(y). De qualquer 
modo, existe w ∈ A∪B, tal que z = f(w). Assim, z ∈ f(A∪B), isto é, f(A)∪f(B) ⊂ f(A∪B). 
Essas duas inclusões mostram que f(A∪B) = f(A)∪f(B).
Definição
Sejam X, Y conjuntos, B ⊂ Y e f: X → Y uma função, a imagem inversa de B é o conjunto
f–1(B) = {x ∈ X | f(x) ∈ B} ⊂ X
Observe que dada uma função f: X → Y, a imagem inversa de um conjunto B ⊂ Y 
é formada pelos elementos x do domínio X, tais que existe um y ∈ B que está rela-
cionado com x. Além disso, a imagem inversa de B é um subconjunto do domínio.
Σxemρlo 2
Seja uma função f, com domínio X = {a, b, c, d, e} e contradomínio Y = {7, 8, 9, 10, 
11}, onde f(a) = 7, f(b) = 8, f(c) = 10, f(d) = 9 e f(e) = 11. Determine a imagem inversa 
dos conjuntos B1 = {7, 8} e B2 = {7, 9, 10, 11}.
Se B1 = {7, 8}, temos que f
–1(B1) = {a, b}. Analogamente, se B2 = {7, 9, 10, 11}, temos 
que f–1(B2) = {a, c, d, e}.
Agora é com você: prove o item b.
Desafio
Funções discretas 83
Teorema
Sejam A, B ⊂ Y e f: X → Y uma função, a imagem inversa é tal que:
a. f–1(A∪B) = f–1(A)∪f–1(B)
b. f–1(A∩B) = f–1(A)∩f–1(B)
Demonstração
Vamos provar apenas o item b. Temos que
x ∈ f–1(A∩B) ↔ f(x) ∈ A∩B
	 							↔ f(x) ∈ A e f(x) ∈ B
	 							↔ x ∈ f–1(A) e x ∈ f–1(B)
	 							↔ x ∈ f–1(A)∩f–1(B)
Portanto, f–1(A∩B) = f–1(A)∩f–1(B).
Definição
Seja f: X → Y uma função, dizemos que f é injetora se f(x
1
) ≠ f(x
2
), sempre que x
1
 ≠
 
x
2
 para x
1
, x
2
 ∈
 
X.
Note que dizer que uma função f: X → Y é injetora equivale a dizer que, se 
f(x1) = f(x2), então x1 = x2. Vejamos um exemplo:
Σxemρlo 3
Sejam f: ℕ → ℕ dada por f(x) = 2x e g: ℤ → ℕ dada por g(x) = x2, verifique que f é 
injetora e que g não é injetora.
Suponhamos que existem x1, x2 ∈ ℕ tais que f(x1) = f(x2). Vamos mostrar que 
x1 = x2. De fato, se f(x1) = f(x2), então 2x1 = 2x2, onde x1 = x2 e, assim, f é injetora. É 
fácil ver que g não é injetora pela contrapositiva: se x1 ≠ x2, então f(x1) ≠ f(x2), mas se 
x1 = -2 e x2 = 2 ∈ ℤ, temos que g(-2) = g(2) = 4.
Funções injetoras são especiais, pois transformam f(A∩B) ⊂ f(A)∩f(B) em uma 
igualdade. Mais precisamente, temos o seguinte teorema.
Teorema
Seja A, B ⊂ X e f: X → Y uma função injetora, então:
f(A∩B) = f(A)∩f(B)
Demonstração
Dado y ∈ f(A)∩f(B), temos y ∈ f(A) e y ∈ f(B). Logo, existem x1 ∈ A e x2 ∈ B, com 
y = f(x1) e y = f(x2). Como f é injetora, deve ser x1 = x2 e, portanto, x1 ∈ A∩B. Segue-se 
que y = f(x1) pertence a f(A∩B), o que mostra f(A)∩f(B) ⊂ f(A∩B). Como a inclusão 
oposta é sempre verdadeira, concluímos que f(A∩B) = f(A)∩f(B).
84 Matemática Discreta
Definição
Definimos f: X → Y uma função sobrejetora (ou sobrejetiva) se, para todo y ∈ Y, existe x ∈ X tal que 
f(x) = y.
Note que dizer que uma função f: X → Y é sobrejetora equivale a dizer que todo 
elemento de Y está relacionado com, no mínimo, um elemento de X.
Σxemρlo 4
Sejam f: ℤ → ℤ dada por f(x) = x + 1 e g: ℤ → ℤ dada por g(x) = x2, vamos verificar 
que f é sobrejetora e que g não é sobrejetora.
De fato, para todo y ∈ ℤ, basta escolhermos x = y - 1 para termos
f(x) = f(y - 1) = (y - 1) + 1 = y
Portanto, f é sobrejetora.
Escolhendo y = -1 ∈ ℤ, não existe x ∈ ℤ, tal que g(x) = y, ou seja, g não é sobrejetora.
Definição
Definimos f: X → Y uma função bijetora se f é injetora e sobrejetora.
Vejamos um exemplo:
Σxemρlo 5
Sejam f: ℤ → ℤ dada por f(x) = x + 1 e g: ℝ → ℝ dada por g(x) = 6x + 5, vamos 
verificar que f e g são bijetoras.
Segue do Exemplo 4 que f é sobrejetora. Além disso, dados x1, x2 ∈ ℤ tais que 
f(x1) = f(x2), então x1 + 1 = x2 + 1, onde x1 = x2, provando que f também é injetora. 
Portanto, f é bijetora.
É fácil verificar que g é injetora. De fato, dados x1, x2 ∈ ℤ tais que g(x1) = g(x2), então 
6x1 + 5 = 6x2 + 5, onde x1 = x2, provando que g é injetora. Considere y ∈ ℝ e x
y� �
�
� 5
6
, 
temos que g(x) = y e, assim, g também é sobrejetora. Portanto, g é bijetora.
Definição
Seja n ∈ ℕ, definiremos os conjuntos [n] e [n]0 por:
[n] ≔ {1, 2, ..., n}.
[n]
0
 ≔ {0, 1, 2, ..., n}.O símbolo ≔ significa igual por 
definição.
Glossário
Funções discretas 85
Relacionamos funções e o conjunto [n] pelo seguinte teorema.
Teorema
Considere os conjuntos [n] e [m] com n ≠ m. Seja também f: [n] → [m] uma fun-
ção, então:
 • Se n < m, f não é sobrejetora.
 • Se n > m, f não é injetora.
Podemos utilizar o teorema anterior para demonstrar o seguinte resultado que 
relaciona conjuntos de cardinalidade finita e funções.
Teorema
Sejam A e B conjuntos de cardinalidade finita. Se existe uma bijeção f: A → B, 
então |A| = |B|.
Demonstração
Sejam |A| = n e |B| = m, podemos, então, corresponder cada elemento de 
ai ∈ A com i ∈ n�� �� , e cada elemento bj ∈ B com o elemento j ∈ m�� �� . Como f é in-
jetora, temos que n ≤ m e, como f é sobrejetora, temos que n ≥ m, onde n = m, ou 
seja, |A| = |B|.
Um exemplo simples de aplicação do teorema é apresentado a seguir.
Σxemρlo 6
Considerando X um conjunto formado por meninos e Y um conjunto formado 
por meninas, vamos formular uma função que nos ajude a verificar se o número de 
meninos é igual ao número de meninas.
Chamaremos um par ordenado da forma (menino, menina) de casal e defini-
remos f: X → Y como a função que define o modo que um casal é formado. f ser 
bijetora significa que para cada menino existe uma única menina que é seu par (in-
jetora) e que para toda menina existe um único menino que é seu par (sobrejetora), 
ou seja, o número de meninos é igual ao número de meninas. Portanto, |X| = |Y|.
5.2 Função composta e função inversa 
Vídeo Definiremos agora um procedimento que pode ser utilizado para construirno-
vas funções a partir de funções dadas. Esse procedimento é chamado de composi-
ção de funções.
Definição
Sejam X, Y e Z conjuntos e f: X → Y e g: Y → Z funções, a composição das funções f: X → Y e g: Y → Z é 
a função definida por
g ∘ f: X → Z
 x  g(f(x))
86 Matemática Discreta
Observe que a função g ∘ f está bem definida, pois f(x) ∈ Y, e Y é o domínio de g. 
Porém, a composição pela outra ordem (f ∘ g) não está definida. Além disso, f ∘ g só 
estaria definida se g(y) ∈ X para todo y ∈ Y, ou seja, se g(y) ⊂ X.
Σxemρlo 7
Sejam f: ℕ → ℝ a função definida por f(x) = log x e g: ℝ → ℝ dada por g(x) = x² + 1. 
Determine (g ∘ f)(x).
Note que g ∘ f: ℕ → ℝ é dada por (g ∘ f)(x) = g(f(x)) = (log x)² + 1. Além disso, observe 
que a função (f ∘ g) não está definida, pois 1,25 ∈ Im(g) = ℝ e 1,25 ∉ Dom(f) = ℕ.
Veja mais um exemplo sobre composição de funções:
Σxemρlo 8
Sejam f: ℕ → ℕ a função definida por f(x) = x + 1 e g: ℕ → ℕ dada por g(x) = x² + x + 1. 
Determine (g ∘ f)(x) e (f ∘ g)(x).
Note que ambas, (g ∘ f)(x) e (f ∘ g)(x), estão bem definidas. Inicialmente, vamos 
calcular (g ∘ f)(x).
(g ∘ f)(x) = g(f(x))
 = [f(x)]2 + f(x) + 1
 = (x + 1)2 + x + 1 + 1
 = x2 + 2x + 1 + x + 2
 = x2 + 3x + 3
Portanto, (g ∘ f)(x) = x2 + 3x + 3.
Agora, (f ∘ g)(x).
(f ∘ g)(x) = f(g(x))
 = g(x) + 1
 = x2 + x + 1 + 1
 = x2 + x + 2
Portanto, (f ∘ g)(x) = x2 + x + 2.
No exemplo, observamos que (g ∘ f)(x) ≠ (f ∘ g)(x). Esse fato nos diz que a com-
posição de funções não é, em geral, comutativa. Por outro lado, o teorema a seguir 
enuncia que a composição de funções é associativa.
Teorema
Quaisquer que sejam f: X → Y, g: Y → Z e h: Z → W, tem-se que:
(h ∘ g) ∘ f = h ∘ (g ∘ f)
Funções discretas 87
Demonstração
Considerando um elemento qualquer x de X e considerando f(x) = y, g(y) = z e 
h(z) = w, temos:
((h ∘ g) ∘ f)(x) = (h ∘ g)(f(x)) = (h ∘ g)(y) = h(g(y)) = h(z) = w
Notamos que
(g ∘ f)(x) = g(f(x)) = g(y) = z
Portanto,
(h ∘ (g ∘ f))(x) = h((g ∘ f)(x)) = h(z) = w
Então, para todo x de A:
((h ∘ g) ∘ f)(x) = (h ∘ (g ∘ f))(x)
Teorema
Se duas funções f: X → Y e g: Y → Z são sobrejetoras, então a função composta 
g ∘ f: A → C é sobrejetora.
Demonstração
Sendo g sobrejetora, então, para todo z ∈ Z, existe y ∈ Y tal que g(y) = z e, como 
a função f é sobrejetora, isto é, dado y ∈ Y, existe x ∈ X tal que f(x) = y. Logo, para 
todo z ∈ Z, existe x ∈ X tal que
z = g(y) = g(f(x)) = (g ∘ f)(x)
Provando que g ∘ f é sobrejetora.
O teorema anterior afirma que a composição de funções conserva a sobreti-
vidade, ou seja, informa que a composta de funções sobrejetoras é uma função 
sobrejetora. O mesmo ocorre com funções injetoras, como podemos observar no 
teorema a seguir.
Teorema
Se duas funções f: X → Y e g: Y → Z são injetoras, então a função composta 
g ∘ f: A → C é injetora.
Demonstração
Consideremos x1 e x2 dois elementos quaisquer de X e suponhamos 
que (g ∘ f)(x1) = (g ∘ f)(x2), isto é, g(f(x1)) = g(f(x2)). Como g é injetora, da última igual-
dade resulta que f(x1) = f(x2); como f é também injetora, temos que x1 = x2. Portanto, 
g ∘ f é injetora.
A operação de composição de funções é utilizada para definir a função inversa 
de uma função.
Definição
Seja f: X → Y uma função, se existe g: Y → X tal que (f ∘ g)(x) = x, ∀ x ∈ Y, e (g ∘ f )(x) = x, ∀ x ∈ A, 
então uma função g é chamada de função inversa de f e é denotada por f–1.
88 Matemática Discreta
Vejamos um exemplo:
Σxemρlo 9
Considere as funções f: ℝ → ℝ definida por f(x) = x + 2 e g: ℝ → ℝ dada por 
g(x) = x - 2. Calcule e mostre que g é a função inversa de f.
De fato, nota-se que
(f ∘ g)(x) = f(g(x)) = f(x - 2) = (x - 2) + 2 = x
e
(g ∘ f)(x) = g(f(x)) = g(x + 2) = (x + 2) - 2 = x
Portanto, g é a inversa de f, ou seja, g = f–1.
Já sabemos que podemos considerar uma função f: X → Y como uma relação de 
X em Y, isto é,
f = {(x, y) ∈ X × Y | y = f(x)} = {(x, f(x)) | x ∈ X}
Desse modo, você pode ser levado ao erro de relacionar função inversa com 
relação inversa. Mas não faça isso!
Relação inversa e função inversa são dois conceitos totalmente diferentes. Ade-
mais, possuem algumas propriedades que as diferenciam; por exemplo, a relação 
inversa sempre existe, o que não acontece com a função inversa.
A existência ou não da inversa de uma função está relacionada com sua sobre-
jetividade, como estabelece o seguinte teorema.
Teorema
Seja f: X → Y uma função, a inversa, f–1: Y → X, existe se, e somente se, f for bijetora.
Podemos concluir, com as funções do Exemplo 9, f(x) = x + 2 e g(x) = x - 2, que 
devido ao fato de g ser a inversa de f, ou seja, a inversa de f existir, temos que 
f(x) = x + 2 é bijetora. Analogamente, por f(x) = x + 2 ser bijetora, concluímos que f 
possui inversa g, dada por g(x) = x – 2.
Outra propriedade interessante da função inversa relaciona a inversa de uma 
função composta com a composta de suas inversas.
Teorema
Sejam f: X → Y e g: Y → Z duas funções bijetoras, então:
(g ∘ f)–1 = f–1 ∘ g–1
Funções discretas 89
Demonstração
Se as funções f e g são bijetoras, então a função composta g ∘ f de X em Z é bije-
tora; logo, existe a função inversa (g ∘ f)–1 de X em Z. Para provar que (g ∘ f)–1 = f–1 ∘ g–1, 
basta provar que (f–1 ∘ g–1) ∘ (g ∘ f)(x) = x e (g ∘ f) ∘ (f–1 ∘ g–1)(x) = x.
De fato,
(f–1 ∘ g–1) ∘ (g ∘ f)(x) = [(f–1 ∘ g–1) ∘ g] ∘ f(x)
 = [f–1 ∘ (g–1 ∘ g)] ∘ f(x)
 = f–1 ∘ [(g–1 ∘ g) ∘ f(x)]
 = f–1 ∘ f(x)
 = x
e
(g ∘ f) ∘ (f–1 ∘ g–1)(x) = [(g ∘ f) ∘ f–1] ∘ g–1(x)
 = [g ∘ (f ∘ f–1)] ∘ g–1(x)
 = g ∘ [(f ∘ f–1) ∘ g–1(x)]
 = g ∘ g–1(x)
 = x
Provamos, assim, que f–1 ∘ g–1 é a inversa da função composta g ∘ f.
5.3 Funções recursivas 
Vídeo Recursividade é um método utilizado para definir funções f: ℕ∪{0} → Y, onde Y é 
um conjunto numérico qualquer. Esse método consiste em duas etapas:
a. Definir um valor para a função f em zero.
b. Fornecer uma regra para encontrar o valor de f(x + 1) a partir dos valores de 
f(0), f(1), …, f(x).
Σxemρlo 10
Seja f: ℕ∪{0} → ℕ a função definida recursivamente por f(0) = 7 e 
f(x + 1) = 3f(x) + 1. Determine os valores de f(1), f(2) e f(3).
Por definição, temos que:
f(1) = f(0 + 1) = 3f(0) + 1 = 3 · 7 + 1 = 22
f(2) = f(1 + 1) = 3f(1) + 1 = 3 · 22 + 1 = 67
f(3) = f(2 + 1) = 3f(2) + 1 = 3 · 67 + 1 = 202
90 Matemática Discreta
Várias operações podem ser estudadas por meio de funções recursivas. Lem-
bramos, por exemplo, que a operação fatorial de um número natural x é definida 
como x! = 1 · 2 · 3 · … · x.
A operação fatorial pode ser definida por meio da seguinte função recursiva 
f: ℕ∪{0} → ℕ, dada por:
f(0) = 1
f(x + 1) = (x + 1)f(x)
Por exemplo, temos que:
 • f(1) = f(0 + 1) = (0 + 1)f(0) = 1 · 1 = 1!
 • f(2) = f(1 + 1) = (1 + 1)f(1) = 2 · 1! = 2 · 1 = 2!
Para finalizar este capítulo, apresentaremos uma função que é definida de ma-
neira recursiva e gera uma sequência de números, conhecidos como números de 
Fibonacci. Esses números foram introduzidos pelo matemático italiano Leonardo 
de Pisa (1170-1250), mais conhecido por Fibonacci, e possuem várias aplicações em 
ciência da computação e teoria de jogos. Além disso, essa sequência de números 
está intrinsecamente ligada à natureza, descrevendo perfeitamente, por exemplo, 
a reprodução das abelhas.
Σxemρlo 11
Os números de Fibonacci f(0), f(1), f(2), … são dados pela função f: ℕ∪{0} → ℕ, 
definida recursivamente por
 • f(0) = 0
 • f(1) = 1
 • f(x) = f(x - 1) + f(x - 2)
Calcule os valores de f(2), f(3), f(4) e f(5).
Temos, por definição, que
f(2) = f(2 - 1) + f(2 - 2) = f(1) + f(0) = 1 + 0 = 1
f(3) = f(3 - 1) + f(3 - 2) = f(2) + f(1) = 1 + 1 = 2
f(4) = f(4 - 1) + f(4 - 2) = f(3) + f(2) = 2 + 1 = 3
f(5) = f(5 - 1) + f(5 - 2) = f(4) + f(3) = 3 + 2 = 5
CONSIDERAÇÕES FINAIS 
Neste capítulo, vimos que uma função entre dois conjuntos X e Y pode ser vis-
ta como uma relação e que toda função é classificada conforme sua injetividade, 
sobrejetividadee bijetividade. Além disso, você aprendeu que dadas duas funções, 
f: X → Y e g: Y → Z, podemos produzir uma nova função g ∘ f: X → Z, chamada de 
função composta. Vimos a importância das funções para contar o número de ele-
mentos de um conjunto finito e como podemos utilizar funções recursivas para 
produzir uma sequência de números.
No filme O código da 
Vinci, o simbologista Robert 
Langdon e a criptóloga 
Sophie Neveu encontram 
números na cena de um 
crime ocorrido no Museu 
do Louvre, em Paris. 
Os números pintados a 
sangue, postos em ordem 
aleatória, revelam-se mais 
tarde um código, a série 
de Fibonacci, que os pro-
tagonistas usam para abrir 
um cofre e dar sequência à 
resolução do mistério.
Direção: Ron Howard. EUA: Sony 
Pictures, 2006.
Filme
Funções discretas 91
ATIVIDADES 
1. Sejam A, B ⊂ X e f: X → Y uma função, mostre que a imagem direta de f é tal que:
f(A∩B) ⊂ f(A)∩f(B)
2. Sejam A, B ⊂ Y e f: X → Y uma função, mostre que imagem inversa de f é tal que:
f–1(A∪B) = f–1(A)∪f–1(B)
3. Mostre que a função f: ℕ → ℕ dada por f(x) = 4x + 7 é injetora.
4. Mostre que a função f: ℤ → ℕ dada por f(x) = 2x2 não é injetora.
5. Mostre que a função f: ℝ → ℕ dada por f(x) = 4x + 7 é sobrejetora. Se o domínio de 
f fosse o conjunto dos números naturais f ainda seria sobrejetora?
REFERÊNCIAS 
GERSTING, J. L. Fundamentos Matemáticos para Ciência da Computação. 4. ed. São Paulo: LTC, 2001.
GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5 ed. Boston: Addison-
Wesley, 2004.
ROSEN, K. H. Matemática discreta e suas aplicações. 6 ed. São Paulo: McGraw-Hill, 2009.
92 Matemática Discreta
6
Análise combinatória
A análise combinatória é a área da matemática que se dedica a desen-
volver técnicas de contagem, preocupando-se em como, e não com o que, 
vamos contar. Muitos dos problemas de contagem tiveram sua origem 
ligada a jogos e loterias. As principais publicações da análise combinatória 
foram feitas pelos matemáticos Blaise Pascal e Pierre de Fermat.
Neste capítulo, vamos apresentar as principais técnicas de contagem, 
como combinações, arranjos e permutações, e demonstrar como utilizá-las 
em diferentes situações.
6.1 Princípios de contagem 
Vídeo A análise combinatória é baseada em alguns princípios de contagem muito sim-
ples e intuitivos. Você pode pensar que eles são tão fáceis que nem mesmo mere-
cem um nome. Mas, para levarmos a contagem a sério, devemos estar cientes de 
fatos simples que usamos implicitamente o tempo todo.
Definição (princípio da adição)
Dizemos que um conjunto finito A é particionado nas partes A
1
, …, A
k
 se as partes são disjuntas e sua 
união é A. Em outras palavras, temos A
i
∩A
j
 =
 
∅ para i ≠ j e A
1
∪A
2
∪…∪A
k
 =
 
A. Nesse caso,
|A| = |A
1
| + |A
2
| + … + |A
k
|
O princípio da adição mostra que se existem |A1| maneiras de tomar a decisão 
A1, |A2| maneiras de tomar a decisão A2, …, |Ak| maneiras de tomar a decisão Ak, 
então o número de maneiras de se tomar a decisão A1 ou a decisão A2, … ou a de-
cisão Ak é |A1| + |A2| + … + |Ak|.
Vejamos um exemplo:
Σxemρlo 1
Seja A o conjunto de alunos que assistem à aula de combinatória. Esse conjunto 
pode ser particionado nas partes A1 e A2, tais que:
 A1 = {Alunos que gostam de exemplos fáceis}.
 A2 = {Alunos que não gostam de exemplos fáceis}.
Análise combinatória 93
Se |A1| = 22 e |A2| = 8, de quantas maneiras distintas podemos escolher um 
aluno que assiste à aula de combinatória?
Como A = A1∪A2 com A1∩A2 = ∅, então podemos concluir, pelo princípio da adi-
ção, que existem |A| = |A1| + |A2| = 30 maneiras diferentes de escolher um aluno 
que assiste à aula de combinatória.
Acompanhe outro exemplo.
Σxemρlo 2
Você vai a um restaurante e, ao observar o cardápio, encontra 4 diferentes pra-
tos italianos e 3 diferentes pratos portugueses. De quantas maneiras você pode 
escolher um único prato para fazer sua refeição?
Considere os seguintes conjuntos:
 • A = {Pratos do restaurante}.
 • A1 = {Pratos italianos}.
 • A2 = {Pratos portugueses}.
Observamos que:
A = A1∪A2 com A1∩A2 = ∅ e |A| = |A1| + |A2| = 7
Logo, existem sete maneiras diferentes de se escolher um prato para realizar 
uma refeição.
Definição (princípio da subtração)
Seja A um subconjunto de um conjunto finito X, definimos A ≔ X\S como o complemento de A em 
X. Então:
|A| = |X| - | A |
Σxemρlo 3
Considere X o conjunto de alunos que estudam análise combinatória e A o con-
junto de alunos que não são do curso de Matemática nem do curso de Ciência da 
Computação. Considerando que o total de alunos é 23.905, se 20.178 não fazem 
parte do curso de Matemática e nem do curso de Ciência da Computação, quantos 
alunos estão cursando Matemática ou Ciência da Computação?
Sabemos que |X| = 23.905 e |A| = 20.178. Além disso,
94 Matemática Discreta
|A| = {Alunos que cursam Matemática ou Ciência da Computação}.
|A| = |X| - |A|
 = 23.905 – 20.178
 = 3.727
Ou seja, existem 3.727 alunos que cursam Matemática ou Ciência da Computação.
A seguir, apresentaremos dois outros princípios que são igualmente intuitivos e 
naturais e que ocorrerão com frequência na resolução de exercícios e nas demons-
trações de teoremas.
Definição (princípio da multiplicação)
Se A é um conjunto finito, definido pelo produto cartesiano de A
1
, 
.
..., A
k
, ou seja, A = A
1
 x
 
A
2
 x
 
... x A
k
, 
então:
|A| = |A
1
| x |A
2
| x ... x |A
k
|
O princípio da multiplicação mostra que se existem |A1|maneiras de tomar a 
decisão A1, |A2| maneiras de tomar a decisão A2, …, |Ak| maneiras de tomar a de-
cisão Ak, então o número de maneiras de se tomar sucessivamente as decisões A1, 
A2, …, Ak é |A1| x |A2| x … x |Ak|. Vejamos um exemplo:
Σxemρlo 4
Você vai a um restaurante e, ao observar o cardápio, encontra 4 opções de pra-
tos principais e 3 opções de sobremesa. De quantas maneiras você pode fazer uma 
refeição formada por um prato principal e uma sobremesa?
Considere os seguintes conjuntos:
 • A = {Refeições com um prato principal e uma sobremesa}.
 • A1 = {Pratos principais}.
 • A2 = {Sobremesa}.
Observamos que:
A = A1 × A2 e |A| = |A1| × |A2| = 12
Logo, existem 12 maneiras diferentes de realizar uma refeição formada por um 
prato principal e uma sobremesa.
Acompanhe mais um exemplo do princípio da multiplicação.
Σxemρlo 5
Quantos números de três dígitos podemos formar com os algarismos 2, 3, 4 e 6?
Análise combinatória 95
Considere os seguintes conjuntos:
 • A = {Números de três dígitos formados por 2, 3, 4 e 6}.
 • A1 = {Opções para o primeiro dígito}.
 • A2 = {Opções para o segundo dígito}.
 • A3 = {Opções para o terceiro dígito}.
Temos que:
A = A1 × A2 × A3 e |A1| = 4, |A2| = 4, |A3| = 4
Então:
|A| = |A1| × |A2| × |A3| = 4 × 4 × 4 = 64
Portanto, podemos formar 64 números de três dígitos com os algarismos 2, 3, 4 e 6.
Agora, um último exemplo utilizando o princípio da multiplicação.
Σxemρlo 6
Em uma cidade fictícia, as placas dos carros têm a seguinte forma:
CF – l1l2n1n2n3
Nessas placas, l1, l2 são letras do conjunto {A, …, Z} e n1, n2, n3 são dígitos do 
conjunto {0, …, 9}. No entanto, l2 e n3 podem ser omitidos. Quantas placas podem 
ser confeccionadas nessa cidade?
Vamos considerar o caso em que l2 é omitido, acrescentando um valor ⊥ para l2, 
que significa omitido. O mesmo vale para n3.
Seja A = {Placas válidas}, o conjunto de todas as placas válidas é dado como os 
produtos:
{T} × {T} × {–} × {A, …, Z} × {A, …, Z, ⊥} × {0, …, 9} × {0, …, 9} × {0, …, 9, ⊥}
Pelo princípio de multiplicação, temos que:
|A| = |{T}| × |{T}| × |{–}| × |{A, …, Z}| × |{A, …, Z, ⊥}| × |{0, …, 9}| × |{0, …, 9}| 
× |{0, …, 9, ⊥}|
|A| = 1 × 1 × 1 × 26 × 27 × 10 × 10 × 11 = 772.200
Ou seja, podem ser confeccionadas 772.200 placas.
Definição (princípio da casa dos pombos)
Sejam A
1
, 
.
..., A
m
 conjuntos finitos tais que A
i
∩A
j
 = ∅ para i ≠ j e |A
1
| + |A
2
| + ... + |A
m
| = n, então:
∃ i ∈ {1, …, m} | |S
i
| ≥ 
n
m
�
��
�
��
 e ∃ j ∈ {1, …, m} ||S
j
| ≤ 
n
m
�
��
�
��
96 Matemática Discreta
Lembramos que n
m
�
��
�
��
 é a função denominada de maior inteiro, ou seja, n
m
�
��
�
��
 = 
menor a ∈ , tal que a ≥ n
m
. Se, por exemplo, n = 10 e m = 3, então 10
3
�=�3,333 �=�4.�
��
�
��
 
Já a função n
m
��
��
�
��
é denominada de menor inteiro, ou seja, n
m
�
��
�
��
= maior a ∈ , tal que 
a ≤ n
m
. Temos, por exemplo, que se n = 10 e m = 3, então 10
3
3 333 3�
��
�
��
� �, � .
Vejamos um exemplo:
Σxemρlo 7
Suponha que haja 5 buracos na parede, nos quais 17 pombos se aninham. Uti-
lizando o princípio da casa dos pombos, o que podemos dizer sobre a distribuição 
dos pombos nesses buracos?
Pelo princípio da casa dos pombos, temos que m = 5 e n = 17. Então, podemos 
concluir que:
 • Existe algum buraco com pelo menos 17
5
�
��
�
��
 = 4 pombos.
 • Existe algum buraco com no máximo 17
5
�
��
�
��
 = 3 pombos.
Vejamos mais um exemplo.
Σxemρlo 8
Se as notas da disciplina de Matemática Discreta são graduadas por A, B, C e 
D, quantos alunos devem ter na sala de aula para garantirmos que no mínimo 4 
alunos tirem a mesma nota?
Vamos aplicar o princípio da casa dos pombos. Note que temos 4 possibilidades 
de notas (A, B, C e D). Logo, m = 4.
Queremos que alguma das notas seja atingida por no mínimo 3 alunos, ou seja, 
queremos que n
4
�
��
�
��
= 4, em que n é o número de alunos na turma. Sendo assim, 
devemos ter n = 13, pois, nesse caso, 
13
4
 =�4�
��
�
��
.
Note que se n = 12, então 12
4
�=�3�<�4�
��
�
��
. Portanto, o número mínimo de alunos 
que a sala de aula deve ter para garantirmos que no mínimo 3 alunos tirem a mes-
ma nota é 13.
A nomenclatura desse 
princípio chama a atenção, 
não é mesmo? Para saber 
mais sobre o princípio da 
casa dos pombos, assista 
ao vídeo Isto é Matemática 
T06E08: O Princípio do 
Pombal, publicado pelo 
canal sigma3web. Nele, 
o matemático Rogério 
Martins aborda o tema 
relacionando-o a uma 
modalidade de loteria 
regional.
Disponível em: https://www.
youtube.com/watch?v=IzaobO14n-
cA&feature=emb_logo. Acesso em: 
5 mar. 2021.
Vídeo
https://www.youtube.com/watch?v=IzaobO14ncA&feature=emb_logo
https://www.youtube.com/watch?v=IzaobO14ncA&feature=emb_logo
https://www.youtube.com/watch?v=IzaobO14ncA&feature=emb_logo
Análise combinatória 97
Definição (princípio da contagem dupla)
Se contarmos a mesma quantidade de duas maneiras diferentes, o processo pode fornecer uma identi-
dade não trivial.
Vamos aplicar esse princípio no famoso lema do aperto de mão (handshaking 
lemma).
Σxemρlo 9
Suponha que n pessoas estejam em uma festa e que todos irão apertar a mão 
um do outro. Quantos apertos de mão irão ocorrer?
Vamos fazer a contagem do número de apertos de mão utilizando duas estra-
tégias diferentes:
 • Primeira estratégia
Cada pessoa aperta um total de n - 1 mãos. Contudo, duas pessoas estão envol-
vidas em um aperto de mão, então se apenas multiplicarmos n(n - 1), cada aperto 
de mão será contado duas vezes. Logo, devemos dividir por dois. Portanto, o núme-
ro total de apertos de mão é n(n�-�1)
2
.
 • Segunda estratégia
Numeramos as pessoas de 1 a n. Para evitar a contagem de um aperto de mão 
duas vezes, contamos, para a pessoa i, apenas os apertos de mão com pessoas de 
números menores. Então, o número total de apertos de mão é:
i
n
i
n
i
n
i i i
� �
�
�
�
� � ��� � � �
1 0
1
1
1
1� �
Ou seja, utilizando as duas estratégias para contar o número de apertos de mão, 
obtemos a seguinte identidade não trivial:
i
n
i
n n
�
�
� �
�� �
0
1 1
2
6.2 Arranjos
Vídeo Denotamos o conjunto dos n primeiros números naturais por [n]. Ou seja, 
[n] ≔ {1, 2, …, n}.
Definição (princípio da contagem dupla)
Seja A um conjunto finito, um arranjo ordenado de A é uma função s: [n] → A.
98 Matemática Discreta
Arranjos ordenados são tão comuns que ocorrem em muitas situações e são 
conhecidos por nomes diferentes. Aprendemos que BANANA é uma palavra e que 
0815422372 é uma sequência de números, embora ambos sejam arranjos orde-
nados de elementos. BANANA é um arranjo ordenado dos elementos do conjunto 
A = {A, B, N} e 0815422372 é um arranjo ordenado dos elementos do conjunto 
B = {0, 1, 2, 3, 4, 5, 7, 8}.
A seguir, apresentamos as perspectivas mais comuns sobre o que é um arranjo 
ordenado e os nomes e notações que os acompanham.
Definição
Seja s: [n] → A um arranjo ordenado do conjunto finito A, temos que [n] é o domínio de s. A imagem de 
s é s(i), com i ∈ [n], e pode ser denotada pelo conjunto {x ∈ A | s(i) = x para algum i ∈ [n]}.
Vejamos um exemplo:
Σxemρlo 10
Seja A�=�{ ,� ,�|,� ,� }� �⊗  e o arranjo ordenado s: [7] → A dado pela tabela a seguir:
i 1 2 3 4 5 6 7
s(i)  ⊗ ⊗  ⊗  
Encontre o domínio de s, a imagem de 3 e a imagem de s.
Por definição, o domínio de s é [7] = {1, 2, 3, 4, 5, 6, 7}, a imagem de 3 é ⊗ 
e a imagem de s é s(i) = { ,� ,� ,� }� �⊗  . Observe que o elemento | não está na imagem 
de s.
Definição
Seja s: [n] → A um arranjo ordenado do conjunto finito A, chamamos s de uma A-string (ou apenas 
string) de comprimento n e escrevemos s = s(1)s(2)s(3)…s(n). A i-ésima posição (ou caractere) em s 
é denotada por s
i
 =
 
s(i). O conjunto A é chamado de alfabeto, e seus elementos são chamados de letras. 
Frequentemente, uma string s é chamada de palavra.
No Exemplo 10, escrevemos que s�=� � �⊗⊗ ⊗ é uma string (ou palavra) de 
comprimento n sobre o alfabeto A, de cinco letras. O quarto caractere de s é s4 �= .
Podemos ver s: [n] → A como um elemento do produto cartesiano.
A1 × … × An, em que Ai = A, para i ∈ [n]
Chamamos s de tupla e a escrevemos como s = (s1, s2, …, sn). O elemento 
si (i ∈ [n]) é chamado de i-ésima coordenada. Ver os arranjos como elementos de 
produtos torna mais fácil restringir o número de valores permitidos para uma de-
terminada coordenada (basta escolher Ai A ).
Análise combinatória 99
Arranjos ordenados são tão comuns que ocorrem em muitas situações e são 
conhecidos por nomes diferentes. Aprendemos que BANANA é uma palavra e que 
0815422372 é uma sequência de números, embora ambos sejam arranjos orde-
nados de elementos. BANANA é um arranjo ordenado dos elementos do conjunto 
A = {A, B, N} e 0815422372 é um arranjo ordenado dos elementos do conjunto 
B = {0, 1, 2, 3, 4, 5, 7, 8}.
A seguir, apresentamos as perspectivas mais comuns sobre o que é um arranjo 
ordenado e os nomes e notações que os acompanham.
Definição
Seja s: [n] → A um arranjo ordenado do conjunto finito A, temos que [n] é o domínio de s. A imagem de 
s é s(i), com i ∈ [n], e pode ser denotada pelo conjunto {x ∈ A | s(i) = x para algum i ∈ [n]}.
Vejamos um exemplo:
Σxemρlo 10
Seja A�=�{ ,� ,�|,� ,� }� �⊗  e o arranjo ordenado s: [7] → A dado pela tabela a seguir:
i 1 2 3 4 5 6 7
s(i)  ⊗ ⊗  ⊗  
Encontre o domínio de s, a imagem de 3 e a imagem de s.
Por definição, o domínio de s é [7] = {1, 2, 3, 4, 5, 6, 7}, a imagem de 3 é ⊗ 
e a imagem de s é s(i) = { ,� ,� ,� }� �⊗  . Observe que o elemento | não está na imagem 
de s.
Definição
Seja s: [n] → A um arranjo ordenado do conjunto finito A, chamamos s de uma A-string (ou apenas 
string) de comprimento n e escrevemos s = s(1)s(2)s(3)…s(n). A i-ésima posição (ou caractere) em s 
é denotada por s
i
 =
 
s(i). O conjunto A é chamado de alfabeto, e seus elementos são chamados de letras. 
Frequentemente, uma string s é chamada de palavra.
No Exemplo 10, escrevemos que s�=� � �⊗⊗ ⊗ é uma string (ou palavra) de 
comprimento n sobre o alfabeto A, de cinco letras. O quarto caractere de s é s4 �= .
Podemos ver s: [n] → A como um elemento do produto cartesiano.
A1 × … × An, em que Ai = A, para i ∈ [n]
Chamamos s de tupla e a escrevemos como s = (s1, s2, …, sn). O elemento 
si (i ∈ [n]) é chamado de i-ésima coordenada. Ver os arranjos como elementos de 
produtos torna mais fácil restringir o número de valores permitidos para uma de-
terminada coordenada (basta escolher Ai A ).
No exemplo mencionado anteriormente, temos s�=�(,� ,� ,� ,� ,� ,� )� � �⊗ ⊗ ⊗ , e sua pri-
meira coordenada é .
Utilizaremos as notações apresentadas nesta seção para, nas próximas seções, 
contarmos o número total de arranjos que podemos definir em um conjunto finito A.
6.3 Permutações
Vídeo Os arranjos ordenados mais importantes são aqueles em que a função é inje-
tiva, ou seja, s(i) ≠ s(j) para i ≠ j. Esse tipo de arranjo será chamado de permutação, 
como definido a seguir.
Definição
Seja A um conjunto finito, uma permutação de A é uma função bijetiva.
π: [n] → A
Quando A = [n], denotamos o conjunto de todas as permutações de [n] por Sn.
Geralmente, escrevemos permutações como sequências numéricas se n < 10. 
Vejamos um exemplo.
Σxemρlo 11
Seja A = [7], vamos descrever a permutação π: [7] → [7], dada por π = 2713546.
Ao denotarmos π = 2713546, estamos escrevendo que π é a função dada por:
i 1 2 3 4 5 6 7
π(i) 2 7 1 3 5 4 6
Ou seja, π(1) = 2, π(2) = 7, π(3) = 1, π(4) = 3, π(5) = 5, π(6) = 4 e π(7) = 6.
Definição
Para 0 ≤ k ≤ |A|, uma k-permutação de A é um arranjo ordenado de k elementos distintos de A, ou 
seja, uma função injetiva π: [k] → A.
Se A = [n], vamos denotar o conjunto de todas as k-permutações de A por 
P(n, k). Em particular, temos Sn = P(n, n).
100 Matemática Discreta
Σxemρlo 12
Seja A = [7], vamos descrever a 3-permutação π: [3] → [7] , dada por π = 312.
Ao denotarmos π = 312, estamos escrevendo que π é a função dada por:
i 1 2 3
π(i) 3 1 2
Ou seja, π(1) = 3, π(2) = 1 e π(3) = 2.
Essa relação de equivalência divide P(n, k) em classes de equivalência, e cada 
classe de equivalência é chamada de k-permutação circular. O conjunto de todas as 
k-permutações circulares é denotado por Pc(n, k).
Acompanhe um exemplo de k-permutação circular.
Σxemρlo 13
Sejam π1 = 76123, π2 = 12376 e π3 = 32167, verifique que π1 e π2 são circulares 
equivalentes e que π3 não é circular equivalente a π1 e π2.
Observe o seguinte desenho representando cada permutação:
π1
6
7
3
1
2
π2
2
1
6
3
7
π3
2
3
7
1
6
Nesse desenho, → indica a seta “circular” de um número ao outro, fechando a 
circunferência.
Observamos que conseguimos sair da permutação π1 para a permutação π2 reali-
zando três giros da direita para esquerda, ou seja, existem s = 3 ∈ [5] tal que se i + 3 ≡ 
j mod 5 → π1(i) = π2(j). Para conseguir chegar da permutação π1 (ou da permutação π2) 
à permutação π3, precisaríamos inverter os elementos 6 e 7, e isso não é permitido na 
definição de permutação circular equivalente, em que π3 não é equivalente a π1 e π2.
No próximo teorema, contaremos o número de k-permutações (circulares). 
Para isso, recordamos a notação e a definição de fatoriais:
n! = n · (n - 1) · (n - 2) · … · 2 · 1, em que 0! = 1.
Teorema
Para qualquer número natural 0 ≤ k ≤ n, temos:
a. P n, k n n n k n
n k
� � � � �� � ��� � �� � �
�� �1 1
!
� � !
b. P n �k n
k n� �kC
, !
!
� � �
�� �
No vídeo Lógica e Ma-
temática Discreta – Aula 
17 – Permutações circulares 
e caóticas, da professora 
Deborah M. Raphael, 
publicado no canal da 
UNIVESP, é possível en-
contrar mais exemplos de 
permutações circulares.
Disponível em: https://www.youtu-
be.com/watch?v=FrJSVVHvoIY&ab. 
Acsso em: 5 mar. 2021.
Vídeo
https://www.youtube.com/watch?v=FrJSVVHvoIY&ab
https://www.youtube.com/watch?v=FrJSVVHvoIY&ab
Análise combinatória 101
Demonstração
Para provar a, uma k-permutação é uma função injetiva π: [k] → [n]. Vamos contar 
as várias maneiras de escolher essa função, escolhendo as imagens uma após a outra.
Existem n maneiras de escolher π(1). Dado um valor para π(1), existem n - 1 ma-
neiras de escolher π(2), pois não podemos escolher π(1) novamente. Continuando 
desse modo, existem n – i + 1 maneiras de escolher π(1), e o último valor que esco-
lhemos é π(k), com n – k + 1 possibilidades.
Cada k-permutação pode ser construída exatamente de uma maneira. O núme-
ro total de k-permutações é, portanto, dado como o produto:
P n, k n n n k n
n k
� � � � �� � ��� � �� � �
�� �1 1
!
� � !
Para provar b, contamos duplamente |P(n, k)|.
A primeira estratégia é P n k n
n k
, !
� � !
� � �
�� � , que provamos em a.
A segunda estratégia é |P(n, k)| = |PC(n, k)| · k, pois cada classe de equivalência 
em PC(n, k) contém k permutações de P(n, k), uma vez que existem k maneiras para 
girar uma permutação k. Então, utilizando o princípio da contagem dupla, obtemos:
n
n k
P n k kC
!
!
,
�� � � � � � → P n k
n
k n kC
, !
!
� � �
�� �
Observe que pelo teorema anterior temos que |P(n, n)| = n!, ou seja, o número 
total de permutações de n elementos é n!
Podemos utilizar permutações para resolver alguns problemas de contagem.
Vejamos um exemplo:
Σxemρlo 14
Quantos anagramas podemos formar com as letras da palavra LETO?
Queremos encontrar o número de maneiras diferentes que podemos ordenar 
utilizando as letras da palavra LETO, ou seja, estamos interessados em saber qual é 
o número total de permutações que podemos fazer com os elementos do conjunto 
A = {E, L, O, T}.
Como |A| = 4, utilizando o fato de que o número total de permutações de n ele-
mentos é dado por |P(n, n)| = n!, temos que |P(4, 4)| = 4! = 4 · 3 · 2 · 1 = 24. Portanto, 
existem 24 anagramas diferentes com as letras da palavra LETO.
Acompanhe mais um exemplo de permutação.
Σxemρlo 15
Quantos resultados possíveis existem em uma prova de ciclismo disputada por 
6 atletas, desconsiderando os empates?
102 Matemática Discreta
Queremos encontrar o número de maneiras diferentes em que podemos clas-
sificar os atletas em primeiro, segundo, terceiro, quarto, quinto e sexto colocado.
Considerando A = {1, 2, 3, 4, 5, 6} como o conjunto das possíveis classificações, 
temos que |A| = 6; portanto, queremos encontrar |P(n, n)| com n = 6. Logo, exis-
tem |P(6, 6)| = 6! = 6 · 5 · 4 · 3 · 2 · 1 = 720 possíveis resultados.
Observamos que, em geral, o número de permutações de n elementos sem ne-
nhuma repetição de elementos é dado por Pn = P(n, n) = n!
Nem sempre os elementos que serão ordenados são distintos. Nesse caso, de-
notaremos por Pn
±,�³ ,�² ,& o número de permutações de n elementos, dos quais um 
é repetido α vezes, outro é repetido γ vezes, outro é repetido β vezes, e assim por 
diante. O número total dessa permutação é:
P n!
±! ³ ! ² !&n
±,�³ ,�² ,& =
Vejamos um exemplo:
Σxemρlo 16
Quantos anagramas diferentes podemos formar com as letras da palavra 
MATEMÁTICA, desconsiderando o acento agudo?
Considerando o multiconjunto B = {A, A, A, M, M, T, T, E, I, C}, temos que |B| = 10 e 
que A se repete 3 vezes, M 2 vezes, e T 2 vezes. Portanto, o número de anagramas dife-
rentes que podemos fazer com as letras da palavra MATEMÁTICA é dado por:
P10
3 2 2 10
3 2 2
151 200,� ,� !
! ! !
.= =
Ou seja, podemos formar 151.200 anagramas com as letras da palavra 
 MATEMÁTICA, sem considerarmos o acento agudo.
No vídeo Lógica e Mate-
mática Discreta – Aula 15 – 
Permutações sem repetição, 
da professora Deborah 
M. Raphael, publicado 
no canal da UNIVESP, é 
possível encontrar mais 
exemplos de permutações 
sem repetições.
Disponível em: https://www.youtu-
be.com/watch?v=SVXCfdtXdiI&ab. 
Acesso em: 5 mar. 2021.
Vídeo
6.4 Combinações
Vídeo Existem algumas situações em combinatória nas quais a escolha dos elementos 
para formar um determinado agrupamento não depende da ordem em que esses 
elementos são escolhidos ou dispostos. Esse fato nos leva à definição a seguir.
Definição
Seja A um conjunto finito e k ∈ ℕ, um arranjo não ordenado de k elementos de A é um multicon-
junto S de cardinalidade k com elementos de A.
Podemos considerar, por exemplo, A�=�{ ,� ,�|,� ,� }� �⊗  . Então, S�=�{ ,� ,� ,� ,� ,� ,� }� � �⊗    
é um arranjo não ordenado de sete elementos de A; note que | ∉ S. Como S é um 
multiconjunto e a ordem em que os elementos aparecem não importa, temos que 
S também pode ser escrito como S�=�{ ,� ,� ,� ,� ,� ,� }  � � � ⊗ .
https://www.youtube.com/watch?v=SVXCfdtXdiI&ab
https://www.youtube.com/watch?v=SVXCfdtXdiI&ab
Análise combinatória103
Durante o capítulo, utilizaremos a seguinte notação: cada elemento x ∈ A que 
está em S é escrito apenas uma vez, acompanhado de seu número de repetição rx. 
Nessa notação, o exemplo anterior será escrito como:
S = {2 · ⊡, 1 · ⊗, 0 ·�|, 3 · △, 1 · ⋆}
Dizemos que  tem r � = 2 repetições, ⊗ tem r� � 1 repetição, | tem r| = 0 repeti-
ção,  tem r

= 3 repetições e ⋆ tem r⋆ = 1 repetição.
Notamos a diferença entre os arranjos verificando que arranjos ordenados são 
seleções de elementos de A, feitas uma de cada vez, enquanto arranjos não orde-
nados são seleções de objetos feitas ao mesmo tempo.
Um exemplo típico de arranjos não ordenados é a lista de compras, pois você 
pode precisar de três bananas e duas peras, e isso é o mesmo que precisar de uma 
pera, três bananas e outra pera. Em certo sentido, você precisa de tudo de uma 
vez, sem ordenação temporal. Isso contrasta, por exemplo, com um número de 
telefone (o qual é um arranjo ordenado), em que discar primeiro o dígito 5 e depois 
o dígito 9 é diferente de discar 9 primeiro e 5 em seguida.
Tal como acontece com arranjos ordenados, o caso mais importante para arranjos 
não ordenados é o caso em que todos os elementos aparecem apenas uma vez, isto é, 
rx = 1 para todos os x ∈ S. Ou seja, o caso mais importante de arranjos não ordenados 
é aquele em que S é simplesmente um subconjunto de A, denotado por S ⊆ A.
Definição
Seja A um conjunto finito, uma k-combinação de A é um arranjo não ordenado de k elementos distintos de A.
Vejamos um exemplo:
Σxemρlo 17
Seja A = {Ana, Pedro, Maria, Tiago}, descreva duas 3-combinações de A e uma 
1-combinação de A.
Uma 3-combinação de A é um subconjunto de cardinalidade três. Então, pode-
mos tomar, por exemplo, as 3-combinações:
S1 = {Ana, Pedro, Maria} e S2 = {Pedro, Maria, Tiago}
Uma 1-combinação de A é um subconjunto de cardinalidade um. Podemos to-
mar, por exemplo, a 1-combinação:
S3 = {Maria}
O conjunto de todos os k-subconjuntos de A é denotado por 
A
k
�
�
�
�
�
�, e se |A| = n, 
denotamos:
n
k
A
k
Cn
k�
�
�
�
�
� �
�
�
�
�
�
� �:
104 Matemática Discreta
Teorema
Para 0 ≤ k ≤ n, temos:
P n,�k = 
n
k
k!� � �
�
�
�
�
�
Demonstração
Para construir um elemento de P(n, k), primeiro escolhemos k elementos de [n]. 
Pela definição de 
n
k
�
�
�
�
�
�, existem exatamente 
n
k
�
�
�
�
�
� maneiras de fazer isso. Então, esco-
lhemos uma ordem para esses k elementos. Existem P k,�k �=�k!
0!
�=�k!� � maneiras de 
fazer isso. Cada elemento de P(n, k) pode ser construído, assim, de exatamente 
uma maneira em que P n,�k �= 
n
k
k!� � �
�
�
�
�
� , o que prova a afirmação.
Note que o teorema anterior nos diz que o número de k-combinações de um 
conjunto finito A com |A| = n é dado por:
n
k
A
k
 =�C �=�
P n,�k
k!
�=� n!
k n�-�k !n
k�
�
�
�
�
� �
�
�
�
�
�
�
� �
� �:
Vejamos um exemplo:
Σxemρlo 18
Um grupo de 5 pessoas está organizando um evento científico, sendo que 2 
dessas 5 pessoas ficarão encarregadas de organizar a festa de encerramento. De 
quantas maneiras diferentes podemos escolher essas duas pessoas?
Queremos contar o número total de 2-combinações do conjunto A = {p1, p2, 
p3, p4, p5}, em que pi representa a pessoa i do conjunto. Como |A| = 5, quere-
mos encontrar:
C �=� 5!
2! 5�-�2 !
�=� 5!
2! 3!
�=�5�·�4�·�3!
2�·�3!
�=�20
2
�=�105
2
� � ·
Ou seja, existem 10 maneiras possíveis de escolher duas pessoas para organizar 
a festa de encerramento.
Acompanhe outro exemplo de combinação.
Σxemρlo 19
Considere um sistema de comunicação composto de quatro antenas.
De
ny
s D
ro
zd
/S
hu
tte
rs
to
ck
Análise combinatória 105
Quantas possibilidades existem de exatamente três antenas estarem com 
defeito?
Queremos contar o número total de 3-combinações do conjunto A = {A1, A2, 
A3, A4}, em que Ai representa a antena i do conjunto. Como |A| = 4, queremos 
encontrar:
C4
3 4
3 4 3
4
3 1
4 3
3
4� � !
! !
� � !
! !
� � � !
!
� ��
�� � � � �
�
�
Ou seja, existem 4 maneiras possíveis de exatamente três antenas estarem com 
defeito.
Vejamos mais um exemplo:
Σxemρlo 20
Em um campeonato de futebol, cada um dos 16 times joga uma única vez contra 
todos os demais. Quantas partidas serão realizadas?
Como cada partida é formada por dois times, queremos contar o número total 
de 2-combinações do conjunto A = {T1, T2, …, T16}, em que Ti representa o time i. 
Como |A| = 16, queremos encontrar:
C �=� 16!
2! 16�-�2 !
�= � 16!
2�·�14!
�= 16�·�15�·�14!
2�·�14!16
2
� � = 
16�·�15
2
�=�8�·�15�=�120
Ou seja, ocorrerão 120 partidas no campeonato.
A seguir, observe outro exemplo no qual usamos a combinatória.
Σxemρlo 21
De 5 mulheres e 7 homens, quantos comitês diferentes de 2 mulheres e 3 ho-
mens podem ser formados?
Vamos considerar A = {M1, M2, M3, M4, M5}, em que Mi denota a mulher i, e 
B = {H1, H2, H3, H4, H5, H6, H7}, sendo que Hj denota o homem j. Em cada comitê tere-
mos um conjunto de 2 mulheres. Como |A| = 5, precisamos calcular:
C =� 5!
2! 5�-�2 !
�=� 5!
2�·�3!
�=�5�·�4�·�3!
2�·�3!
�=�105�
2
� �
Analogamente, em cada comitê teremos um conjunto de 3 homens. Como 
|B| = 7, precisamos calcular:
C �=� 7!
3! 7�-�3 !
�=� 7!
3!�·�4!
�=�7�·�6�·�5�·�4!
6�·�4!
�=�357
3
� �
106 Matemática Discreta
Como cada comitê é formado por 2 mulheres e 3 homens, precisamos utilizar o 
princípio multiplicativo para obter o número total de comitês diferentes que pode-
mos formar. Ou seja, o número total T será:
T�=�C �·�C �=�10�·�35�=�3505
2
7
3
Portanto, podemos formar 350 comitês diferentes.
6.5 Binômio de Newton 
Vídeo Os números 
n
k
�
�
�
�
�
� para 0 ≤ k ≤ n são chamados também de coeficientes binomiais, 
pois são os coeficientes encontrados ao se expandir a enésima potência de uma 
soma de duas variáveis: (x + y)n. Coeficientes binomiais são utilizados no método 
conhecido como binômio de Newton. Para demonstrar o binômio de Newton, utili-
zaremos o teorema a seguir.
Teorema
Sejam m, n ∈ , então:
m
k
m
k
m
k�
�
�
�
�
�
� �
�
�
�
�
�
� �
��
�
�
�
�
�1
1
Vejamos um exemplo:
Σxemρlo 22
Verifique que:
4
2
4
3
5
3
�
�
�
�
�
� �
�
�
�
�
�
� �
�
�
�
�
�
�
Temos que:
4
2
4
2 4 2
12
2
6
�
�
�
�
�
� �
�� � � � �
!
! !
4 · 3�·�2!
2�·�2!
4
3
4
3 4 3
4
1
4
�
�
�
�
�
� �
�� � � � �
!
! !
�����4�·�3!
3!�·�1!
5
3
5
3 5 3
20
2
10
�
�
�
�
�
� �
�� � � � �
!
! !
5 · 4�·�3!
3!�·�2!
Portanto:
4
2
4
3
5
3
�
�
�
�
�
� �
�
�
�
�
�
� �
�
�
�
�
�
�
O binômio de Newton é descrito e demonstrado a seguir.
Teorema
Sejam x, y variáveis e n ∈ , então:
x y
n
k
x yn
k
n
n k k�� � � �
�
�
�
�
�
�
��
0
Análise combinatória 107
Demonstração
Vamos demonstrar, por indução, que o binômio de Newton é válido para qual-
quer n ≥ 1.
Para n = 1, temos (x + y)1 = x + y e
 
k
n k k
k
y x y x y x y
�
� � ��
�
�
�
�
�
� �
�
�
�
�
�
� �
�
�
�
�
�
� � �
0
1
1 0 0 1 1 11 1
0
1
1
x
Ou seja:
 x y
k
x y
k
n k k�� � � �
�
�
�
�
�
�
��
1
0
1 1
Logo, o binômio de Newton é válido para n = 1.
Agora, suponha que o resultado é verdadeiro para n = m, ou seja, vale
           x y
m
k
x ym
k
m
m k k�� � � �
�
�
�
�
�
�
��
0
Vamos demonstrar que o resultado é válido para n = m + 1.
De fato:
     x y x y x ym m�� � � �� � �� ��1
                                �� �� � �
�
�
�
�
�
�
��x y
m
k
x y
k
m
m k k
0
                                ��
�
�
�
�
�
� �
�
�
�
�
�
�
�
�
�
�� �x
m
k
x y y
m
k
x y
k
m
m k k
k
m
m k k
0 0
                                                ��
�
�
�
�
�
� �
�
�
�
�
�
�
�
� �
�
� �� �
k
m
m k k
k
m
m k km
k
x y
m
k
x y
0
1
0
1
A primeira soma pode ser escrita como:
           
k
m
m k k m
k
m
m k kx y x
m
k
x y
�
� � �
�
� �� �
�
�
�
�
�
� � �
�
�
�
�
�
�
0
1 1
1
1m
k
A segunda soma pode ser escrita como:
           
k
m
m k k m
k
m
m k km
k
x y y
m
k
x y
�
� � �
�
�
� �� �
�
�
�
�
�
� � �
�
�
�
�
�
�
0
1 1
0
1
1�� �
�
�
�
�
�
�
��
�
� ��y
m
k
x ym
k
m
m k k1
1
1
1
 
Então, temos:
                           x y x
m
k
x y y
m
k
xm m
k
m
m k k m
k
m
m�� � � � �
�
�
�
�
� � �
�
�
�
�
�
�
�
� �
�
� � �
�
� �
1 1
1
1 1
1
1
�� �1 k ky
                                                � � �
�
�
�
�
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
�
� ��x y
m
k
m
k
x ym m
k
m
m k k1 1
1
1
1
108 Matemática Discreta
Mas
                     m
k
m
k
m
k�
�
�
�
�
�
� �
�
�
�
�
�
� �
��
�
�
�
�
�1
1
Então:
                          x y x y
m
k
x ym m m
k
m
m k k�� � � � � ��
�
�
�
�
�
� � �
�
� ��
1 1 1
1
11
          � �
m
k
x y
k
m
m k k�
��
�
�
�
�
�
�
�
��
0
1 1
Assim, fica provado que o teorema é válido para todo n ∈ .
A fórmula binomial pode ser generalizada para mais de duas variáveis.
Definição
Para inteiros não negativos k
1
, 
.
..., k
r
, com k
1
 +
 
... + k
r
 =
 
n, os coeficientes multinomiais 
n
k , ..., k1 r
�
�
�
�
�
� são 
os coeficientes encontrados ao se expandir a n-ésima potência de uma soma de r variáveis. Em outras 
palavras, definimos os coeficientes multinomiais 
n
k , ..., k1 r
�
�
�
�
�
� como os únicos números que satisfaçam 
a seguinte identidade:
x x
n
k , ..., k
x xr
n
k kr n
k kr
1 r
1
k1
2
k2
1
1
1
���� � � �
�
�
�
�
�
� � �
�
...
,...,
....xr
kr
Vejamos um exemplo:
Σxemρlo 23
Utilize o polinômio (x1 + x2 + x3)
4
 para encontrar
4
2 11
4
2 0 2
4
0 0 4,� ,�
,�
,� ,�
,�
,� ,�
.
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
Temos que:
x x x x x x1 2� �� � � � � �� �3 4 14 24 341
         � � � � � � �� ��4 x x x x x x x x x x x x13 2 13 3 1 23 23 3 1 33 2 33
                                 � � � �� ��6 x x x x x x12 22 12 32 22 32
                                 � � � �� ��12 x x x x x x x x x12 2 3 1 22 3 1 2 32
Análise combinatória 109
O coeficiente de x x x1
2
2 3 é 12, o coeficiente de x x1
2
3
2 é 6 e o coeficiente de x3
4 é 1. 
De acordo com a definição de coeficiente multinomial, temos que:
4
2 11
12
4
2 0 2
6
4
0 0 4
1
,� ,�
�,�
,� ,�
�,�
,� ,�
.
�
�
�
�
�
� �
�
�
�
�
�
� �
�
�
�
�
�
� �
Note que, por exemplo, 
n
k ,�...,�k1 r
�
�
��
�
�
�� � 
4
2 11
12
,� ,�
�
�
�
�
�
� � → k1 = 2, k2 = 1 e k3 = 1
→ k1 + k2 + k3 = 4 = n.
Além disso, observe que em x x x1
2
2 3 temos que o expoente de x1 é k1 = 2, o ex-
poente de x2 é k2 = 1 e o expoente de x3 é k3 = 1, conforme a definição.
A seguir, apresentamos um teorema que nos ensina a calcular de modo prático 
os coeficientes multinomiais de uma expansão polinomial da forma x � xr
n
1 ���� � .
Teorema
Para inteiros não negativos k1, …, kr, com k1 + … + kr = n, tem-se:
n
k ,�...,k
n
k
n k
k1 r 1 2
�
�
��
�
�
�� �
�
�
��
�
�
���
��
�
��
�
�
��� ���
� �
��...�1 ��
� � � �... � !
! ! �... � !
n k k
k
n
k k k
r
r r
� � ��
�
��
�
�
�� � � � �
�1 1
1 2
Demonstração
Pela definição de potenciação, temos que x � � � �xr
n
1 � �� �... pode ser escrito como:
x � � x x x xr
n
i
r
i
r
in
r
i i in
n�somas
1
1 1 2 1 1
1 2
� �� � �
� � �
� � �... ... ...
� ������ �����
Nessa demonstração, os monômios xi1, xi2, …, xin são iguais a x ��x
k
r
kr
1
1,��..., se os 
índices i1, …, in são exatamente iguais a 1, 2 …, r. Contaremos o número de atribui-
ções de valores aos índices i1, …, in, satisfazendo isso.
 • Escolhendo os índices k1 iguais a 1
Existem 
n
k �1�
�
�
��
�
�
�� maneiras de fazer isso.
 • Escolhendo os índices k2 iguais a 2
Existem n-índices k1 restantes para escolher, então há 
�n�-�k �
k �
1
2
�
�
��
�
�
�� maneiras de es-
colher k2 deles.
 • Escolhendo índices kJ iguais a j (j ∈ [r])
Há n - k1 - … - kj-1 índices restantes para escolher, então há 
n� �k � � � �k �
k
j
j
� � ��
�
�
�
�
�
�
�
�1 1... 
maneiras de escolher kj deles.
Logo, o coeficiente multinomial (ou seja, o coeficiente de x x xk k r
kr
1
1
2
2 ... ) é:
n
k ,�...,k
n
k
n k
k
 
1 r
�
�
��
�
�
���
�
�
��
�
�
���
��
�
��
�
�
���� � �� � ...�
1
1
2
��
� ��
�
��
�
�
��
� �
�
�...� �� � �-��n k k k
k
r
r
1 2 1
110 Matemática Discreta
Assim, a primeira identidade é provada. Agora:
n
k
n k
k
n k k k
1
r�
�
��
�
�
�� �
��
�
��
�
�
��� �
� � � ��
�
��
��1
2
1 2 1��...��
...
kr ��
�� �
�
�� � �
�� �
� �� � � �
� � �� �n
k n k
n k
k n k k
n k kr!
! !
!
! !
...
...
1 1
1
2 1 2
1 1��
� � �� �
!
! ... !k n k kr r1
Convenientemente, muitos dos termos fatoriais se cancelam; desse modo 
teremos:
n
k
n k
k
� ��
n k k k
k
r
r1
1
2
1 2 1�
�
��
�
�
�� �
��
�
��
�
�
�� � �
� � � ��
�
��
�
�
�...
...
��� � � � �
n
k k � � kr
!
! ! ... !1 2
Σxemρlo 24
Utilize o teorema anterior para calcular 
5
1,�2,�2
�
�
�
�
�
�.
Temos que 1 + 2 + 2 = 5. Então, pelo teorema anterior, obtemos:
5
1 2 2
5
1 2 2
5 4 3 2
1 2 2
5
,� ,�
!
!�� !�� !
�� �� �� !
�� �� !
��
�
�
�
�
� �
� �
�
� � �
� �
�
��� ��4 3
2
5 2 3 30� � � � �
CONSIDERAÇÕES FINAIS 
Neste capítulo, vimos que a análise combinatória está fundamentada em alguns 
princípios básicos da contagem, como o princípio multiplicativo, o princípio aditivo e o 
princípio da casa dos pombos.
Além disso, você aprendeu que podemos utilizar funções para contar o número 
de elementos de subconjuntos especiais de um conjunto finito dado. Essas funções 
são utilizadas para definir novas fórmulas de contagem, que são importantíssimas em 
vários problemas de matemática, como no desenvolvimento polinomial.
ATIVIDADES 
1. Uma pequena comunidade tem 10 mulheres, cada uma delas com 3 filhos. Se, 
em um festival, uma mulher e uma criança forem selecionadas como “mãe e 
filho do ano” (independentemente de serem mãe e filho de fato), quantas são as 
possibilidades diferentes de escolhermos uma dupla vencedora?
2. Suponha que queremos colocar 10 livros na estante. Desses, 4 são de Matemática, 
3 são de Química, 2 são de História e 1 é de Literatura. Os livros de mesmo assunto 
devem ser colocados juntos. Quantos arranjos diferentes são possíveis?
Análise combinatória 111
3. Ao pendurar 9 bandeiras em uma linha, das quais 4 são brancas, 3 são vermelhas 
e 2 são azuis, quantas formas diferentes são possíveis?
4. Se em um grupo de 12 pessoas 3 delas são escolhidas para ganhar uma viajem, de 
quantas maneiras diferentes pode ocorrer a escolha?
REFERÊNCIAS 
GERSTING, J. L. Fundamentos matemáticos para ciência da computação. 4. ed. São Paulo: LTC, 2001.
GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5. ed. Boston: 
Addison-Wesley, 2004.
HAZZAN, S. Fundamentos da matemática elementar: combinatória, probabilidade. São Paulo: Atual, 2013. 
v. 5.
ROSEN, K. H. Matemática discreta e suas aplicações. 6. ed. São Paulo: McGraw-Hill, 2009.
SANTOS, J. P. O.; MELLO, M. P.; MURARI, I. T. C. Introdução à análise combinatória. Rio de Janeiro: Ciência 
Moderna, 2008.
112 Matemática Discreta
7
Funções geradoras e 
partição de um inteiro
Funções geradoras são uma das invenções mais surpreendentes, 
úteis e inteligentes da matemática discreta. De modo geral, funções ge-
radoras transformam problemas sobre sequências numéricas em pro-
blemas de funções de valor real. Isso é ótimo porque já conhecemos 
várias propriedades e técnicas matemáticas para manipular funções de 
valor real.
Graças às funções geradoras, podemos aplicar todo o nosso conhe-
cimento sobre funções aos problemas de sequências numéricas. Dessa 
forma, podemos utilizar funções geradoras para resolver todos os tipos 
de problemas de contagem. Há um grande espaço da matemática de-
dicada ao estudo de funções geradoras, portanto, neste capítulo, apre-
sentaremos apenas uma pequena abordagem do assunto.
Você irá aprender a calcular a função geradora ordinária e a fun-
ção geradora exponencial de uma sequência numérica, a realizar ope-
rações em funções geradoras e utilizá-las para resolver problemas de 
contagem. Por fim,aprenderá o conceito e a como representar a parti-
ção de um número inteiro positivo.
7.1 Funções geradoras 
Vídeo Iniciaremos com a definição formal de função geradora ordinária de uma se-
quência numérica.
Definição
A função geradora ordinária (FGO) para a sequência numérica infinita (g
0
, g
1
, g
2
, ...) é a série de potência 
formal
G x g g x g x g x g x
i
i
i� �� � � � ���
�
�
�0 1 2 2 3 3
0
Indicaremos a correspondência entre uma sequência e sua função de geração 
com uma seta dupla-face (↔), da seguinte forma:
(g 0, g1, g3, ...) ↔ g0 + g1 x + g2 x
2 + g3 x
3 + …
Funções geradoras e partição de um inteiro 113
Por exemplo, aqui estão algumas sequências e suas funções geradoras:
(0, 0, 0, 0, ...) ↔ 0 + 0x + 0x² + 0x³ + ... = 0
(1, 0, 0, 0, ...) ↔ 1 + 0x + 0x² + 0x³ + ... = 1
 (3, 2, 1, 0, ...) ↔ 3 + 2x + 1x² + 0x³ + ... = 3 + 2x + x²
Observamos que o padrão para fazermos correspondência entre uma sequên-
cia numérica e sua função geradora ordinária é: o i-ésimo termo na sequência (in-
dexação de 0) é o coeficiente de xi na função geradora.
Também podemos relacionar função geradora e sequências numéricas defini-
das por recorrência. Vejamos um exemplo.
Σxemρlo 1
Considere a sequência numérica (gk), onde gk = (k
2 + 1) para k = 0, 1, 2, 3. Descreva 
(gk) e sua função geradora.
Temos que (gk) = (g0, g1, g2, …) = ((0
2 + 1), (12 + 1), (22 + 1), …) = (1, 2, 5, ...).
Sendo assim, a função geradora de (gk) é
G x x x � k x
i
i� � � � � � �� �� �
�
�1 2 5 12
0
2
�
De maneira análoga, podemos definir a função geradora ordinária de uma se-
quência numérica infinita.
Definição
A função geradora ordinária (FGO) para a sequência numérica finita (g
0
, g
1
, g
3
, 
.
.., g
n
) é o polinômio
G x g g x g x g x g x g xn
n
i
n
i
i� �� � � � ��� �
�
�0 1 2 2 3 3
0
Observe que a função geradora ordinária para uma sequência numérica finita 
(g0, g1, g3, ..., gn) também pode ser vista como uma série infinita 
i=0
i
ig x
�
� , onde gi = 0 
para todo i > n.
Acompanhe um exemplo de FGO para uma sequência numérica finita.
Σxemρlo 2
Qual a função geradora da sequência numérica (2, 3, 5, 7, 11, 13)?
Tem-se, por definição, que
114 Matemática Discreta
G x g x x x x x x
i
i
i� � � � � � � � �
�
�
0
5
2 3 4 52 3 5 7 11 13
Lembre-se de que a soma de uma série geométrica infinita 
i
iz
�
�
0
�
, para |z| < 1, é
1 1
1
� � � � �
�
z z z �
�z
² ³ ...
Isto nos diz que a função 1
1� �x−
 é uma função geradora ordinária para a sequên-
cia numérica infinita (1, 1, 1, ...), pois G(x) = 1 + x + x² + x³ + ... = 1
1� ��x−
. Nesse caso, 
dizemos que 1
1� ��x−
 é a forma fechada da função geradora G(x) = 1 + x + x² + x³ + ...
Podemos utilizar a soma da série geométrica infinita para encontrar funções gera-
doras na forma fechada para uma ampla gama de sequências. Vejamos um exemplo:
Σxemρlo 3
Considere a sequência numérica infinita dada por (1, a, a2, a3, ...). Encontre uma 
função geradora na forma fechada para essa sequência.
Temos que (1, a, a2, a3, ...) ↔ 1 + ax + a²x² + a³x³ + ... = 1
1� �ax−
, pois
1
1
1
� �ax
ax a x a x �
�
� � � � � �² ² ³ ³
Quando |ax| < 1 ou equivalente, para |x| < 1
a
 com a ≠ 0.
7.2 Operações com funções geradoras 
Vídeo A mágica de gerar funções relacionadas com sequências numéricas é que po-
demos realizar todos os tipos de manipulações em sequências, executando ope-
rações matemáticas em suas funções geradoras associadas. Vamos realizar várias 
operações e analisar o seu efeito nas sequências relacionadas.
Teorema (regra de escala)
Seja (f0, f1, f2, ...) uma sequência numérica infinita e c ∈ ℝ. Se (f0, f1, f2, ...) ↔ F(x), então,
(cf0, cf1, cf2, ...) ↔ c · F(x)
Demonstração
(cf0, cf1, cf2, ...) ↔ cf0 + cf1x + cf2 x
2 + …
     = c · (f0 + f1x + f2x
2+ ...)
     = c · F(x).
O teorema anterior nos mostra que multiplicar uma função geradora por uma 
constante dimensiona cada termo na sequência associada pela mesma constante.
Funções geradoras e partição de um inteiro 115
Σxemρlo 4
Qual é a sequência numérica infinita associada à função geradora G x
� �x
� � �
�
10
1
 ?
Note que 10
1
10 1
1 10
10
� �x � �
F x
�
�
�
� � �· , onde F x
� �x
� � �
�
1
1
 é a função geradora 
associada à sequência numérica infinita (1, 1, 1, ...). Pelo teorema da regra de esca-
la, temos que a sequência (10, 10, 10, ...) é associada à função geradora G x
� �x
� � �
�
10
1
.
No teorema a seguir, veremos como a soma de sequências numéricas interfere 
nas suas funções geradoras ordinárias.
Teorema (regra da adição)
Seja (f0, f1, f2, ...) e (g0, g1, g2, ...) duas sequências numéricas infinitas tais que (f0, f1, 
f2, ...) ↔ F(x) e (g0, g1, g2, ...) ↔ G(x).
Então,
(f0 + g0, f1 + g1, f2 + g2, ...) ↔ F(x) + G(x).
Demonstração
f g f g f g f g x
n
n n
n
0 0 1 1 2 2
0
� � �� � � �� �
�
�
�, , ,...
��������������� ������������������������
�
�
�
�
�
�
�
�
�
�
�
�
n
n
n
n
f x
0 ��
�
�
�
�
�
�
�
�
�
�
0
g xn
n
= F(x) + G(x)
Acompanhe um exemplo:
Σxemρlo 5
Sejam (1, 3, 5, 7, 9 ...) e (g0, g1, g2, ...) duas sequências numéricas infinitas, onde 
g �g �g � G x
� �x0 1 2 2
7
1
, , , ...� � � � � �
�
, qual é a função geradora associada à sequência nu-
mérica (1 + g0, 3 + g1, 5 + g2, 7 + g3, 9 + g4, ...)?
Note que
1 3 5 7 9 1 3 5 7 2 12 3
0
, , , , ...� � � � x x x � i x
i
i� � � � � � � �� �� �
�
�
�
e G x
� �x � �x
� � �
�
�
�
7
1
7 1
12 2
, então, pela regra da escala, (g0, g1, g2, ...) = (7, 7, 7, ...).
Pelo teorema anterior, temos que
(1, 3, 5, 7, 9...) + (g0, g1, g2, ...) = (1 + g0, 3 + g1, 5 + g2, 7 + g3, 9 + g4, ...)
                 = (1 + 7, 3 + 7, 5 + 7, 7 + 7, 9 + 7, …)
116 Matemática Discreta
 = (8, 10, 12, 14, 16, …) ↔ H(x) = 8 + 10x + 12x2 + 14x3 + 16x5 + ...
O próximo teorema demonstra o efeito de inserir zeros à esquerda de uma 
sequência numérica dada.
Teorema (regra do deslocamento à direita)
Se (f0, f1, f2, ...) ↔ F(x), então,
0 0 0 0 1 2,� ,�...,� ,� , , ,�...
�k zeros
kf f f x F x��� ��
�
�
�
�
�
�
�
�
� � ��
Demonstração
Temos que
0 0 0 0 1 2 0 1,� ,�...,� ,� , , ,�...
�k zeros
kf f f f x f x
��� ���
�
�
��
�
�
�
��
� � kk k kf x f x� � �� � ��1 2
2
3
3 � �
 = xk · (f0 + f1x + f2x² + f3x³ + ...)
 = xk · F(x)
Σxemρlo 6
Qual é função geradora ordinária da sequência numérica (0, 0, 0, 10, 10, 10, 10, 
10, ...)?
No Exemplo 4 vimos que a sequência (10, 10, 10, ...) está relacionada com a 
função geradora ordinária G x
� �x
� � �
�
10
1
. Como adicionamos 3 zeros à esquerda da 
sequência (10, 10, 10, ...) para obter (0, 0, 0, 10,10,10, 10, 10, ...), podemos utilizar o 
teorema anterior e concluir que a sequência geradora ordinária de (0, 0, 0, 10,10,10, 
10, 10, ...) é G x
� �x
� � �
�
10
1
3x .
Vejamos agora como a derivada de uma função afeta funções geradoras e suas 
respectivas sequências numéricas.
Teorema (regra da derivada)
Se (f0, f1, f2, ...) ↔ F(x), então (f1, 2f2, 3f3, ...) ↔ F’(x).
Demonstração
Temos que
(f1, 2f2, 3f3, ...) = f1 + 2f2x + 3f3x² + ...
                               � ² ³ �...� � � � �� �d
dx
f f x f x f x0 1 2 3
                               � �� � �d
dx
F x
A regra da derivada é muito útil e importante. Vejamos um exemplo:
Funções geradoras e partição de um inteiro 117
Σxemρlo 7
Encontre uma função geradora fechada para a sequência de quadrados perfei-
tos (0, 1, 4, 9, 16, ...).
Utilizaremos as operações com funções geradoras da seguinte forma: vamos 
começar com a função geradora para (1, 1, 1, 1, ...), diferenciar e multiplicar por x e, 
em seguida, diferenciar e multiplicar por x novamente.
1111 1
1
,� ,� ,� ,�...
�
� � �
�x
	 									    1 2 3 4 1
1
1
1
,� ,� ,� ,�...
� � ²
� � �
�
�
�� �
d
dx x x
	 												    0 1 2 3 1
1 1
,� ,� ,� ,�...
� ² � ²
� � � �
�� � � �� �x x
x
x
 1 4 9 16
1
1
1
,� ,� ,� ,�...
� ² � ³
� � �
�� � �
�
�� �
d
dx
x
x
x
x
	 															   0 1 4 9 1
1
1
1
,� ,� ,� ,�...
� ³ � ³
� � � � �
�� � �
���
�� �x
x
x
x x
x
Assim, a função geradora da sequência numérica dos quadrados é: 
x � �x
� �x
1
1
�� �
�� � ³ .
Funções geradoras são particularmente úteis para resolver problemas de contagem. 
Especificamente, problemas envolvendo a escolha de itens de um conjunto geralmen-
te levam a funções de geração interessantes. Quando funções geradoras são usadas 
dessa forma, o coeficiente de xn é o número de maneiras de escolher n itens.
Antes de apresentarmos aplicações de funções geradoras, iremos enunciar uma 
versão estendida do teorema binomial.
Definição
Considere m um número real e k um número inteiro não negativo. Então, o coeficiente binomial esten-
dido 
m
k
�
�
�
�
�
� é dado por:
m
k
m m m k
k
se k
�
�
�
�
�
��
� �� ���� � �� �
�
1 1
0
!
, e 
m
k
se k
�
�
�
�
�
�� �1 0,
118 Matemática Discreta
Vejamos um exemplo:
Σxemρlo 8
Encontre os valores binomiais estendidos de 
��
�
�
�
�
�
3
2
 e 
1
2
3
�
�
�
��
�
�
�
��
.
Temos, por definição, que
��
�
�
�
�
� �
�� � �� �
�
�� � �� �
�
3
2
3 4
2
3 4
2
6
!
e
1
2
3
1
2
1
2
1 1
2
2
3
1
2
1
2�
�
�
��
�
�
�
��
�
�
�
�
�
�
� �
�
�
�
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
� �
�
�
!
��
�
�
� �
�
�
�
�
�
�
�
3
2
6
1
16
Se m = -n ∈ ℤ, com n ∈ ℕ, temos que
m
k
n
k
n k
k
k�
�
�
�
�
��
��
�
�
�
�
�� �� �
� ��
�
�
�
�
�1
1
Segundo a observação, se m é um número inteiro negativo, o coeficiente bino-
mial estendido pode ser escrito em termos do coeficiente binomial clássico. Agora, 
vamos enunciar o teorema binomial estendido.
Teorema
Considerando x um número real com |x| < 1 e n um número real, temos que
1
0
�� � � �
�
�
�
�
�
�
�x
n
k
xn
k
k
�
Não realizaremos a demonstração desse teorema, uma vez que precisaríamos 
nos aprofundar em séries numéricas, que não é objeto deste livro. Mas vamos ilus-
trá-lo com o seguinte exemplo:
Σxemρlo 9
Encontre uma função geradora para (1 + x)–n, em que n é um número inteiro 
positivo.
Do teorema binomial estendido, temos que
1
0
�� � � ��
�
�
�
�
�
�
�
�x
n
k
xn
k
k
�
Funções geradoras e partição de um inteiro 119
Pela observação apresentada anteriormente, temos que 
��
�
�
�
�
� � �� � � ��
�
�
�
�
�
n
k
n k
k
k1
1� � � �
.
Então,
1 1
1
0
�� � � �� � � ��
�
�
�
�
�
�
�
�x
n k
k
xn
k
k k
�
 � ³ ...�
��
�
�
�
�
� �
�
�
�
�
�
� �
��
�
�
�
�
� �
��
�
�
�
�
� �
n n
x
n
x
n
x �
1
0 1
1
2
2
3
2
Vejamos algumas aplicações de funções geradoras em problemas de contagem.
Σxemρlo 10
Quantas são as soluções inteiras de x1 + x2 + x3 = 7 sabendo que x1, x2 ∈ {1, 2, 3} 
e x3 ∈ {3, 4}?
Para resolvermos este tipo de problema basta associarmos a cada variável xi um 
polinômio pi(x), onde os expoentes i representam os valores que a variável xi pode 
assumir. Ou seja,
p1(x) = x + x
2 + x3, p2(x) = x + x
2 +x3 e p3(x) = x
3 + x4
Queremos, como solução, números x1, x2, x3 cuja soma seja 7 e que estejam, 
cada um, no conjunto cujos elementos são os expoentes do polinômio correspon-
dente. Sendo assim, a solução do problema será o coeficiente de x7 do polinômio
G(x) = p1(x) · p2(x) · p3(x)
 = (x + x2 + x3 )2 · (x3 + x4)
 = x10 + 3x9 + 5x8 + 5x7 + 3x6 + x5
Ou seja, existem cinco soluções para x1 + x2 + x3 = 7 com x1, x2 ∈ {1, 2, 3} 
e x3 ∈ {3, 4}.
Acompanhe outro exemplo:
Σxemρlo 11
De quantas maneiras podemos escolher 4 pessoas de um grupo de 6 pessoas?
Para resolvermos esse tipo de problema, consideramos (1 + x) como o poli-
nômio que representa a presença de uma pessoa. Como temos seis pessoas no 
total, então o número de maneiras que podemos formar um grupo com quatro 
pessoas é representado pelo coeficiente de x4 no desenvolvimento do polinômio 
G(x) = (1 + x)6. Observamos que
G(x) = (1 + x)6 = x6 + 6x5 + 15x4 + 20x3 + 15x2 + 6x + 1
Portanto, podemos escolher 4 pessoas de um grupo de 6 pessoas de 15 
maneiras.
120 Matemática Discreta
Acompanhe mais um exemplo:
Σxemρlo 12
De quantas maneiras podemos escolher 10 calças de 4 marcas diferentes?
A função geradora que determina o número de calças de uma marca é
1 + x + x2 + ... + x10
Como são quatro marcas diferentes, a solução será o coeficiente de x10 em
(1 + x + x2 + … + x10)4
Sabemos que
1 1
1
2 10
11
� � ��� �
�
�
x x x x
x
Logo
1 1
1
1 12 10
4 11
4
11 4 4� � ���� � � ��
�
�
��
�
�
�� � �� � �� �
�x x x x
x
x x
Como
(1 – x11)4 = 1 – 4x11 + 6x22 – 4x33 + x44
temos que o coeficiente de x10 em (1 + x + x2 + … + x10)4 é o coeficiente de x10 em 
(1 – x)–4. Como
1 1
4 14
0
�� � � �� � � ��
�
�
�
�
�
�
�
�x
k
k
x
k
k k
�
o coeficiente de x10 é
�� � � ��
�
�
�
�
� �1
4 10 1
10
28610
Portanto, existem 286 modos de se escolher 10 calças de 4 marcas diferentes.
7.3 Funções geradoras exponenciais
Vídeo Na seção anterior vimos alguns exemplos de como utilizar a função geradora 
ordinária para resolver problemas de contagem cuja ordem em que os objetos 
aparecem é irrelevante. Agora vamos estudar as funções geradoras exponenciais, 
utilizadas para solucionar problemas de contagem em que a ordem dos objetos 
retirados é importante.
Definição
A função geradora exponencial (FGE) para a sequência numérica infinita (g
0
, g
1
, g
3
, ...) é a série de po-
tência formal
G x g g
x
g
x
g
x
g
x
ii
i
i
� �� � � � ���
�
�
�0 1 2
2
3
3
01 2 3! ! ! !
Funções geradoras e partição de um inteiro 121
Essa definição tem como motivação o fato bem conhecido do cálculo de que
e x
i
x
i
i
�
�
�
0
�
!
Ou seja, a exponencial ex é igual à função geradora exponencial da sequência 
numérica (1, 1, 1, ...).
Vejamos dois exemplos:
Σxemρlo 13
Encontre a função geradora exponencial que determina o número de senhas 
com no máximo três dígitos e formadas pelos números 1, 2 e 3, em que 1 e 2 apa-
recem no máximo uma vez e 3 aparece no máximo duas vezes.
Precisamos considerar o produto dos polinômios a seguir, onde cada um deter-
mina a presença do dígito 1, 2 e 3:
f x x x x x� � � �� � �� � � �
�
�
��
�
�
��1 1 1 2
2
!
 �
! !
� �� � � � �
�
�
��
�
�
��1 1 2 3 2 2
2 3
x x x x
 �
! ! !
� � � � �1 3 7
2
4
2 2
2 3 4
x x x x
 �
! ! ! !
� � � � �1 3
1
7
2
4
3
1
4
2 3 4x x x x
Portanto, a função geradora exponencial que determina o número de senhas é
�
! ! ! !
� � � � �1 3
1
7
2
4
3
1
4
2 3 4x x x x
Σxemρlo 14
Uma rede de restaurantes contrata 6 pessoas para trabalhar em 3 unidades di-
ferentes. De quantas maneiras diferentes podemos distribuir esses 6 funcionários 
de modo que cada unidade receba ao menos um funcionário?
Nenhuma unidade pode receber mais de quatro funcionários, pois, do contrário, 
um restaurante não receberá nenhum funcionário. Como o número de funcionários 
que cada unidade vai receber importa, ou seja, a ordem de distribuição importa, usa-
remos para resolver esse problema a seguinte função geradora exponencial:
f x x x x x� � � � � �
�
�
��
�
�
��1 2 3 4
2 3 4 3
! ! ! !
122 Matemática Discreta
A resposta é o coeficiente de x
6
6!
 nessa função. Notemos que esse coeficiente é 
o mesmo se tomarmos
f x x x x x� � � � � � ��
�
�
��
�
�
��1 2 3 4
2 3 4 3
! ! ! !
 � x x x x� � � � � ���
�
�
��
�
�
��1 1 2 3 4
1
2 3 4 3
! ! ! !
 = (ex – 1)3
= e3x – 3e2x + 3ex – 1
uma vez que as potências extras não alteram o coeficiente de x
6
6!
.
Sabemos também que
e x x x xx � � � � � ��1
1 2 3 4
2 3 4
! ! ! !
Então,
e x
x x xx3
2 3 4
1 3
1
3
2
3
3
3
4
� � �
� �
�
� �
�
� �
��
! ! ! !
Assim, o coeficiente de x
6
6!
 é 36.
De maneira análoga, encontramos o coeficiente de x
6
6!
 em e2x, que é 26. Logo, o 
coeficiente de x
6
6!
 em
f x e e e ex x x x� � �� � � � � ��� 1 3 3 13 3 2
será 36 – 3 · 26 + 3 = 729 – 192 + 3 = 540. Portanto, existem 540 modos diferentes de 
distribuir os funcionários de modo que cada unidade receba ao mínimo um novo 
funcionário.
Esse tipo de solução pode ser resumido no seguinte teorema.
Teorema
O número de modos distintosque podemos distribuir n objetos diferentes em k 
compartimentos diferentes sem que nenhum fique vazio é dado por:
D n k
k
i
k i
i
k
i n,� � � �� � �
�
�
�
�
� �� �
�
�
0
1
Aplicando esse teorema ao Exemplo 14, temos que
D
i
i ���������������������������
i
i6 3 1
3
3
0
3
6,� � � �� � �
�
�
�
�
� �� �
�
� ����������������������������������������������������������������������������
               �� �� � �
�
�
�
�
� �� � � �� � �
�
�
�
�
� �� � � �� � �
�
�
�
�
� �� 1
3
0
3 0 1
3
1
3 1 1
3
2
30 6 1 6 2 22 06� � �
              = 36 – 3 · 26 + 3
              = 540
Na dissertação Resolução 
de problemas combinatórios 
utilizando funções gerado-
ras, defendida em 2013 por 
Domingos Boaes Garcia, 
ele apresenta a aplicação 
de funções geradoras e 
relações de recorrência 
no cálculo do tamanho de 
uma população de coelhos. 
Vale a pena conferir!
Disponível em: https://sca.profmat-sbm.
org.br/sca_v2/get_tcc3.php?id=37752. 
Acesso em: 5 mar. 2021.
Leitura
https://sca.profmat-sbm.org.br/sca_v2/get_tcc3.php?id=37752
https://sca.profmat-sbm.org.br/sca_v2/get_tcc3.php?id=37752
https://sca.profmat-sbm.org.br/sca_v2/get_tcc3.php?id=37752
Funções geradoras e partição de um inteiro 123
7.4 Sequência de Fibonacci 
Vídeo Às vezes podemos encontrar funções geradoras interessantes, e relativamente 
simples, para sequências mais complicadas. Por exemplo, aqui está uma função 
geradora para os números de Fibonacci:
0 1 1 2 3 5 8 13 21
1
, , , , , , , , , ...
²
� � � � � � � � � x
� �x� �x
� � �
� �
É sabido que a função de recorrência que define os números de Fibonacci é bas-
tante complicada, mas sua função geradora ordinária é bem simples!
Vamos demonstrar, no teorema a seguir, a função geradora para a sequência 
de Fibonacci.
Teorema
A sequência de Fibonacci, definida por: f0 = 0, f1 = 1 e fn = fn-1 + fn-2 (para n ≥ 2), 
possui função geradora ordinária dada por
G x x
� �x� �x
� � �
� �1 ²
Demonstração
Vamos utilizar a sequência F(x) = f0 + f1x + f2x
2 + f3x
3 + f4x
4 + ... para encontrar G(x), 
função geradora da sequência (0, 1, f1 + f0, f2 + f1, f2 + f3, ...). Observamos que
(0, 1, f1 + f0, f2 + f1, f2 + f3, …) = (0, 1, 0, 0, 0, …)
 + (0, f0, f1, f2, f3, …)
 + (0, 0, f0, f1, f2, ...)
e que
   (0,1, 0, 0, 0, ...) ↔ x
(0, f0, f1, f2, f3, ...) ↔ xF(x)
(0, 0, f0, f1, f2, ...) ↔ x²F(x)
Portanto,
(0, 1 + f0, f1 + f0, f2 + f1, f3 + f2, ...) ↔ x + xF(x) + x²F(x)
Essa sequência é quase idêntica aos lados direitos das equações de Fibonacci. 
O único defeito é que o segundo termo é 1 + f0, em vez de simplesmente 1. No 
entanto, isso não é um problema, já que f0 = 0. Agora, se igualarmos F(x) com a 
nova função x + xF(x) + x²F(x), calcularemos implicitamente todas as equações que 
definem os números de Fibonacci de uma só vez, pois
x + xF(x) + x2F(x) = 0 + (1 + f0)x + (f1 + f0)x
2 + (f2 + f1)x
3 + (f3 + f2)x
4 + ...
Resolvendo para F(x), teremos a função geradora para a sequência de Fibonacci:
F x x xF x x F x� � � � � � � � �²
 �� � � �
� �
F x x
� �x� �x1 2
124 Matemática Discreta
7.5 Partição de um inteiro
Vídeo Não é difícil perceber que quanto mais restrições possui um problema de con-
tagem, mais difícil é para encontrar sua solução. Vimos que uma ferramenta da 
análise combinatória que facilita a resolução desses problemas é a função geradora 
ordinária. Essa ferramenta é importante para resolver problemas que podem ser 
traduzidos em equação do tipo x1 + x2 + ... + xn = r de números inteiros não negativos.
Consideremos agora o seguinte problema: de quantas maneiras diferentes po-
demos colocar quatro bolas idênticas em duas caixas idênticas de modo que ne-
nhuma caixa fique vazia?
Podemos resolver esse problema de um modo mais simples, sem precisar re-
correr a uma equação do tipo x1 + x2 + ... + xn = r. Note que o número 4 pode ser 
escrito como:
 • 4.
 • 3 + 1.
 • 2 + 2.
 • 2 + 1 + 1.
 • 1 + 1 + 1 + 1.
As diferentes maneiras de escrever o número 4 são chamadas de partições do 
número 4.
Considerando cada parcela como uma caixa, temos que existem apenas duas 
opções diferentes de colocar quatro bolas idênticas em duas caixas idênticas. A 
saber, {3, 1} e {2, 2}.
Esse método, a princípio, é bem simples. Mas, ao considerarmos números maio-
res, notamos que o número de partições aumenta de maneira considerável. Por 
exemplo, o número 200 possui 3.972.999.029.388 partições. Vamos estudar em 
mais detalhes as partições de um número.
Definição
Dado um número inteiro positivo n, uma partição de n é uma coleção de números inteiros positivos 
cuja soma é n. O número de partições de n será denotado por p(n).
Já vimos, como exemplo, que p(4) = 5 e p(200) = 3.972.999.029.388. Vamos es-
crever pk(n) para indicar o número de partições com k parcelas de um número 
inteiro positivo n. Por exemplo, p2(4) = 2 e p3(4) = 1.
É fácil ver que
k
n
kp n p n
�
� � � � � �
0
Funções geradoras e partição de um inteiro 125
Observamos que uma partição de um número inteiro define uma sequência nu-
mérica. A partição p = {3, 2, 2, 1} do número n = 8, por exemplo, define a sequência 
numérica (3, 2, 2, 1). Vamos então relacionar partições de um inteiro e a função 
geradora de uma sequência numérica.
Teorema
Seja n um número inteiro positivo e p(n) o número de partições de n, a função 
geradora para p(n) é:
n
n
k
k
p x x
x� �
� �� � � �1 1
1
1
� �
Onde p(0) = 1.
Demonstração
Sabemos que
1
1
1 2 3
�
� � � � ��
x
x x x ,
1
1
1
2
2 4 6
�
� � � � ��
x
x x x ,

 1
1
1 2 3
�
� � � � ��
x
x x x
m
m m m
Portanto,
k
kx
x x x x x x �
�
� � � � � � ��� � � � � � �� ��1
2 3 2 4 61
1
1 1
�
Assim, notamos que os coeficientes do termo xn derivam de um termo xb1 da 
primeira série, de x b2 2 da segunda, e assim por diante, com bi ≥ 0 para todo i. Pela 
regra da potenciação, temos que
b1 + 2b2 + 3b3 +… + mbm = m
Cada bi deve ser visto como o número de i’s que aparecem na partição de n, ou 
seja, podemos escrever n como
N = (1 + 1 + ... + 1) + (2 + 2 + ... + 2) + ... + (m + m + ... + m)
onde temos b1 1’s no primeiro parêntese, b2 2’s no segundo e bm m’s no m-ésimo 
parêntese. Assim, cada partição de um n contribui em uma unidade para o coefi-
ciente de xn. Portanto,
k
kx
x x x � � x x x �
�
� � � � � �� � � � � � � �� � � � � � �� ��1
1 1 1 1 1 2 2 2 2 2 21
1
1 1
�
Ou seja, a função geradora para as partições de n, em que nenhuma parte su-
pera m, é dado por
k
m
kx�
� �1
1
1
126 Matemática Discreta
7.6 Gráfico de uma partição
Vídeo Seja n um número inteiro positivo, o gráfico de uma partição de n é representado 
por meio de um conjunto de n pontos no plano, onde em cada linha inserimos em or-
dem decrescente o número de pontos correspondentes a cada uma de suas partes.
Σxemρlo 15
Construa o gráfico para a partição {3, 2, 1, 1} do número 7.
Por definição, temos que a primeira linha do gráfico possui três pontos, a se-
gunda linha possui dois pontos e as duas últimas linhas possuem um ponto cada. 
Portanto, o gráfico da partição {3, 2, 1, 1} é dado por:
Note que ao invertemos as linhas e as colunas do gráfico de uma partição de 
um número inteiro n, obtemos o gráfico de outra partição de n. Isso nos leva à 
seguinte definição:
Definição
Dado um número inteiro positivo n e uma partição p de n, a partição conjugada de p é a partição p de n, 
obtida pela inversão das linhas e colunas do gráfico de p.
Vejamos um exemplo:
Σxemρlo 16
Determine a partição conjugada da partição p = {4, 2, 1} do número 7.
Temos, por definição, que o gráfico da partição {4, 2, 1} é dado por
Funções geradoras e partição de um inteiro 127
Se invertemos as linhas e colunas, vamos obter o seguinte gráfico:
que corresponde à partição {3, 2, 1, 1}, ou seja, p = {3, 2, 1, 1}.
Definição
Dado um número inteiro positivo n e uma partição p de n, a partição conjugada de p é chamada de 
autoconjugada se p = p.
Se considerarmos, por exemplo, a partição p = {3, 2, 1} de n = 6:
temos que p = p .
CONSIDERAÇÕESFINAIS 
Neste capítulo você aprendeu a relacionar sequências numéricas com funções 
geradoras, a função geradora polinomial e a função geradora exponencial, além de 
conceitos fundamentais de teoria de conjuntos, as diferentes formas de descrevê-
-los e como relacioná-los com objetos da vida real.
Aprendeu a realizar várias operações básicas entre as funções geradoras e 
como essas operações são traduzidas em termos de sequências numéricas, além 
de construir partições de um número inteiro não negativo e relacionar partições de 
um inteiro e funções geradoras.
Por fim, aprendeu como podemos resolver problemas de contagem por meio 
de funções geradoras.
ATIVIDADES 
1. Mostre que a função geradora da sequência (1, -1, 1, -1, ...) é
 G x � �x x � �x �
x
� � � � � � � �
�
1 1
1
² ³ ...
2. Encontre o coeficiente de x³ no desenvolvimento binomial de 1
1
2�� �x .
3. Encontre a sequência gerada pela função geradora ordinária
f x x
x
� � �
�� �
2
1 2
2
128 Matemática Discreta
REFERÊNCIAS 
GERSTING, J. L. Fundamentos Matemáticos para Ciência da Computação 4 ed. São Paulo: LTC, 2001.
GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5 ed. Boston: Addison-
Wesley, 2004.
ROSEN, K. H. Matemática discreta e suas aplicações. 6 ed. São Paulo: McGraw-Hill, 2009.
Gabarito 129
GABARITO 
1 Fundamentos de lógica matemática e métodos de 
demonstração
1. 
a) Teorema
Se a é um número inteiro par e b é um número inteiro ímpar, então a soma a + b é 
um número inteiro ímpar.
Demonstração
Seja a um número inteiro par e b um número inteiro ímpar, pela definição de 
número inteiro par, sabemos que a = 2k e, pela definição de número inteiro ímpar, 
b = 2t + 1. Logo, a soma a + b é
a + b = 2k + (2t + 1) = 2(k + t) + 1 = 2t1 + 1, ou seja, a + b = 2t1 + 1, onde t1 = k + t.
Isso mostra que a + b tem a forma de um número inteiro ímpar. Podemos, assim, 
concluir que a + b é um número inteiro ímpar.
b) Teorema
Se a é um número inteiro par e b um número inteiro ímpar, então o produto ab é 
um número par.
Demonstração
Seja a um número inteiro par e b um número inteiro ímpar, pela definição de 
número inteiro par, sabemos que a = 2k e, pela definição de número inteiro ímpar, 
b = 2t + 1. Logo, o produto ab é
ab = (2k)(2t + 1) = 2k2t + 2k = 2(2kt + k), ou seja, ab = 2k1, onde k1 = 2kt + k.
Isso mostra que ab tem a forma de um número inteiro par. Podemos, assim, 
concluir que ab é um número inteiro par.
2. Teorema
Se a é um número natural e a² é ímpar, então a é um número ímpar.
Demonstração
Nossa proposição é “p: a² é ímpar → q: a é ímpar”. Vamos demonstrar que a 
proposição equivalente “~q: a é par → ~p: a² é par” é verdadeira. Com efeito, se a é 
par existe k natural tal que a = 2k.
Logo, a² = (2k)² = 4k² = 2(2k²) = 2k2, onde k2 = 2k², ou seja, a² é um número par, 
provando que a contrapositiva do teorema é verdadeira. Podemos, então, concluir 
que o teorema é verdadeiro.
3. 
Teorema
Se a é um número inteiro par e b é um número inteiro ímpar, então a soma a + b é 
um número inteiro ímpar.
130 Matemática Discreta
Demonstração
Nossa hipótese é “p: a é um número inteiro par e b é um número inteiro ímpar” 
e nossa tese é “q: a + b é um número inteiro ímpar”. Vamos então negar q, isto é, 
“∼q: a + b é um número par”.
Suponha, então, que a = 2k1, b = 2t + 1 e a + b é um número par. Digamos que 
a + b = 2k2, onde, por um lado, a + b = 2k1 + (2t + 1) e, por outro lado, a + b = 2k2. 
Daí, 2k1 + (2t + 1) = 2k2 ⇒ 2(-k1 - t + k2) = 1. Isso nos diz que 1 é um número par, 
obviamente uma contradição, de onde devemos ter que a + b é um número ímpar.
4. 
Teorema
Se n é um número natural, 1² + 3² + 5² + ... + (2n - 1)² = 
n 2n�-�1 2n�+�1
3
� �� �
.
Demonstração
Vamos, inicialmente, mostrar que o resultado é válido para n = 1. Se n = 1 temos 
que 1² = 
1 2(1) -1) 2(1)�+�1
3
=1(1)(3)
3
= 3
3
� � � �
 = 1, provando que o teorema é válido no 
caso n = 1.
Assumindo que o teorema é válido para n = k, ou seja, assumindo que
1² + 3² + 5² + ... + (2k - 1)² = 
k 2k�-�1 2k�+�1
3
� �� � ,
Vamos mostrar que o teorema é válido para n = k + 1, ou seja, mostraremos que
1² + 3² + 5² + ... + (2k + 1)² = k�+�1 2k�+�1 2k�+�3
3
� �� �� � .
De fato,
1² + 3² + 5² + ... + (2k - 1)² + (2k + 1)² = 
k 2k�-�1 2k�+�1
3
� �� � + (2k + 1)²
����������������������������������������������������������������������=
2k+1 k 2k-1 +3 2k+1
3
� � � � � ��� ��
�=
3
(2k +1)(2k +5k +3)2
�=
k+1 2k+1 2k+3
.
6
� �� �� �
Provando, assim, que 1² + 2² + 3² + ... + (k + 1)² �=
k+1 2k+1 2k+3
.
6
� �� �� �
Desse modo, podemos concluir que o teorema é válido.
2 Teoria de conjuntos 
1. 
Demonstração
Seja x ∈ A∩B, significa que (x ∈ A e x ∈ B), que pode ser lido como (x ∈ B e x ∈ A). Isso 
significa que x ∈ B∩A, ou seja, A∩B ⊂ B∩A. De modo análogo, temos que B∩A ⊂ A∩B 
e podemos concluir que A∩B = B∩A.
Gabarito 131
2. 
Demonstração
Para provar essa propriedade, utilizaremos as leis distributivas da lógica matemática. 
Seja:
x ∈ A∪(B∩C) ↔ x ∈ A ou x ∈ B∩C ↔ x ∈ A ou (x ∈ B e x ∈ C)
 ↔ (x ∈ A ou x ∈ B) e (x ∈ A ou x ∈ C) ↔ x ∈ A∪B e x ∈ A∪C
 ↔ x ∈ (A∪B)∩(A∪C)
Provando que A∪(B∩C) = (A∪B)∩(A∪C).
3. 
Demonstração
Seja: 
x ∈ (A∪B)C ↔ x ∉ A∪B ↔ ~(x ∈ A∪B) ↔ ~(x ∈ A ou x ∈ B) 
 ↔ ~(x ∈ A) e ~(x ∈ B) ↔ x ∉ A e x ∉ B 
 ↔ x ∈ AC e x ∈ BC ↔ x ∈ AC∩BC.
Provando que (A∪B)C = AC∩BC.
4. 
Demonstração
Temos que: 
x ∈ A\B ↔ x ∈ A e x ∉ B ↔ x ∉ AC e x ∈ BC 
 ↔ x ∈ BC e x ∉ AC ↔ x ∈ BC\AC. 
Provando que A\B = BC\AC.
3 Conjuntos numéricos
1. 
Demonstração
Suponha que a, b > 0 e a | b, ou seja, b = ak com k ∈  . Como a e b são positivos, 
temos que k ≥ 1. Multiplicando por a > 0, temos que ak ≥ a, ou seja, a ≤ b. 
2. 
Demonstração
Note que:
p
q
+ r
s
+ c
d
=
sp+qr
qs
+ c
d
=
d sp+qr +qsc
qsd
=
dsp+dqr+qsc
qsd
�
�
�
�
�
�
� �
Por outro lado,
p
q
+ r
s
+ c
d
= p
q
+ dr�+�sc
sd
=
sdp�+�q dr�+�sc
qsd
= dsp��
�
�
�
�
�
�
�
�
�
�
�
� � ++�dqr�+�qsc
qsd
Ou seja, p
q
+ r
s
+ c
d
= p
q
+ r
s
+ c
d
�
�
�
�
�
�
�
�
�
�
�
� .
132 Matemática Discreta
3. 
Demonstração
Se a ≡ b mod m e c ≡ d mod m, então, por definição, existem k1, k2 ∈  , tais que 
a - b = mk1 e c - d = mk2, em que a - b + c - d = mk1 + mk2, ou seja, (a + c) - (b + d) = m(k1 + k2). 
Isso significa que a + c ≡ b + d mod m.
4. 
Demonstração
Temos que a é par se, e somente se, existe k ∈  , tal que a = 2k, e isso ocorre se, 
e somente se, a - 0 = 2k, ou seja, se, e somente se, a ≡ 0 mod 2.
Analogamente, temos que a é ímpar se, e somente se, existe k ∈  , tal que a = 2k + 1, 
e isso ocorre se, e somente se, a - 1 = 2k, ou seja, se, e somente se, a ≡ 1 mod 2.
4 Relações
1. Demonstração
Sabendo que A ⊂ B, queremos provar que A x C ⊂ B x C. Para isso, precisamos 
mostrar que se (x, y) ∈ A x C, então (x, y) ∈ B x C. Seja então (x, y) ∈ A x C, pela 
definição de produto cartesiano, temos x ∈ A e y ∈ C. Como A ⊂ B, temos que x ∈ B, 
ou seja, x ∈ B e y ∈ C, provando que (x, y) ∈ B x C. Portanto, A x C ⊂ B x C.
2. Demonstração
Temos que:
(x, y) ∈ (A∩B) x C ↔ x ∈ (A∩B) e y ∈ C 
↔ (x ∈ A e x ∈ B) e y ∈ C 
↔ (x ∈ A e y ∈ C) e (x ∈ B e y ∈ C) 
↔ (x, y) ∈ A x C e (x, y) ∈ B x C
↔ (x, y) ∈ (A x C)∩(B x C)
Portanto, (A∩B) x C = (A x C)∩(B x C).
3. Demonstração
Pela definição de A, temos que A = {1, 2, 3, 4, 5, 6, 7}. Sendo assim:
 � � �� � � � � � � � � � � � �{ , | }x �y A A �x y 9 2,�7 ,� 3,�6 ,� 4,�5 ,� 5,�4 ,� 6,�3�� � � �� �,� 7,�2
Onde, Dom 2,�3,�4,�5,�6,�7� � � � � e Im = 2,�3,�4,�5,�6,�7� � � � .
Observamos também que  � �1 . Sendo assim, Dom Dom �� � � � �1 e 
Im Im �� � � � �1 .
4. Demonstração
Para verificar que  � � � �{ x �y |x y�mod�m, } é uma relação de equivalência, vamos 
demonstrar que essa relação é reflexiva, simétrica e transitiva.
É reflexiva: note que, para todo x ∈ ℤ, temos x – x = 0 · m, ou seja, x ≡ x mod m.
É simétrica: suponha que x ≡ y mod m. Então, existe k ∈ ℤ, tal que x – y = km.
→ y – x = (-k) m → y ≡ x mod m.
Gabarito 133
É transitiva:suponha que x ≡ y mod m e y ≡ z mod m. Assim, existem k1, k2 ∈ ℤ, tal 
que x – y = k1m e y – z = k2m. Então, temos que:
→ (x – y) + (y – z) = k1m + k2m
→ x – z = (k1 + k2)m
Com k1 + k2 ∈ ℤ. Assim, x ≡ z mod m.
5 Funções discretas
1. 
Demonstração
Seja y ∈ f(A∩B), existe x ∈ A∩B tal que f(x) = y. Então, x ∈ A e, portanto, y ∈ f(A). Também, 
x ∈ B e, portanto, y ∈ f(B). Logo, y ∈ f(A)∩f(B). Provando que f(A∩B) ⊂ f(A)∩f(B).
2. 
Demonstração
Temos que:
x ∈ f–1(A∪B) ↔ f(x) ∈ A∪B
	 	 											↔ f(x) ∈ A ou f(x) ∈ B
	 	 																↔ x ∈ f–1(A) ou x ∈ f–1(B)
	 	 						↔ x ∈ f–1(A)∪f–1(B)
Provando que f–1(A∪B) = f–1(A)∪f–1(B).
3. 
Demonstração
Suponhamos que existem x1, x2 ∈ ℕ tais que f(x1) = f(x2). Vamos mostrar que x1 = x2. 
De fato, se f(x1) = f(x2), então 4x1 + 7 = 4x2 + 7, onde 4x1 = 4x2 e, assim, x1 = x2, onde 
f é injetora.
4. 
Demonstração
Basta escolhermos x1 = 1 e x2 = -1 e teremos f(x1) = f(x2) com x1 ≠ x2, ou seja, f não 
é injetora.
5. 
Demonstração
Para todo y ∈ ℕ, temos que, se x y�-�7
4
= , então:
f x = f y�-�7
4
 = 4 y�-�7
4
 + 7 = y - 7 + 7 = y� � �
�
�
�
�
�
�
�
�
�
�
� � �
Onde f é sobrejetora.
Se o domínio fosse o conjunto dos números naturais, então f não seria sobrejetora.
134 Matemática Discreta
6 Análise combinatória
1. Considerando M = {M1, M2, …, M10} o conjunto das mulheres e Fi = {Fi1, Fi2, Fi3} o 
conjunto dos filhos da mulher i, como não importa o laço de maternidade entre 
eles, temos que existem 10 possibilidades para escolher a mulher e 3 possibilidades 
para escolher o filho. Sendo assim, no total temos T = |M| · |F| = 10 · 30 = 300 
maneiras diferentes para realizar nossa escolha.
2. Considerando M = {Livros de Matemática}, Q = {Livros que Química}, H = {Livros de 
História}, L = {Livro de Literatura}, temos que existem 4! maneiras de organizar os 
livros de Matemática, 3! maneiras de organizar os livros de Química, 2! maneiras 
de organizar os livros de História e 1! maneira de organizar os livros de Literatura. 
Sendo assim, existem 4! · 3! · 2! · 1! = 288 modos de organizar os livros na seguinte 
ordem: MQHL. No entanto, a ordem em que os livros estão organizados pode ser 
diferente (por exemplo, QMHL), e sabemos que existem 4! maneiras diferentes de 
escolher a ordem de organização dos livros por tema. Sendo assim, o número total 
de arranjos em que podemos organizar os livros é 288 · 4! = 6.912.
3. Fazendo n1 = 4, n2 = 2, n3 = 3 e n = 9, temos que n1 + n2 + n3 = n, pois 4 + 2 + 3 = 9, 
e estamos interessados em encontrar
n
n ,�n ,�n
�=�
9
4,�2,�3
�=� 9!
4!�·�3!�·�2!
�=�1.
1 2 3
�
�
��
�
�
��
�
�
�
�
�
� 2260
pelo teorema multinomial. Portanto, existem 1.260 formas possíveis nessas 
configurações.
4. Basta escolhermos 3 pessoas entre as 12 disponíveis. Não estamos preocupados 
com a ordem da escolha, mas sim com quais pessoas serão escolhidas. O número de 
maneiras de fazer isso é:
C =
12
3
= 12!
3! 12-3 !
=12�·�11�·�10�·�9!
3!�·�9!
=12�·�12
3 �
�
�
�
�
� � �
111�·�10
3
=220
Portanto, existem 220 modos diferentes para escolher as 3 pessoas.
7 Funções geradoras e partição de um inteiro
1. Sabemos que
(1, 1, 1, 1, ...) ↔ 1+�x+x +�x +�...= 1
1�-�x
2 3
Substituindo x por -x nos dois lados da igualdade, temos que
1+ -x + -x +� -x +�...= 1
1- -x
2 3� � � � � � � �
Ou seja,
1-�x+x -x +�...= 1
1+x
2 3
Provando que a função geradora de (1, -1, 1, -1, ...) é
G x = 1
1+x
� �
2. Utilizando o teorema binomial, temos:
1+x =
1
2
p
x =
1
2
· 1
2
-1 ·&�· 1
2
-p+11
2
p=0
¥
p
p=0
¥
å å� �
�
�
�
��
�
�
�
��
�
�
�
�
�
�
�
��
�
�
�
�
p!
x ,p
Gabarito 135
Logo, o coeficiente de x3 é
1
2
1
2
-1 1
2
-3+1
3!
= 1
16
�
�
�
�
�
�
�
�
�
�
�
�
3. Sabemos que
1
1-x
=1+�x+x +�x +&�2 3
Substituindo x por 2x nos dois lados da igualdade, temos que
1
1-2x
=1+�2x+4x +�8x +16x +�...2 3 4
Multiplicando os dois lados por 2x², tem-se
2x
1-2x
=2x +�4x +8x +�16x +32x +�&
2
2 3 4 5 6
Logo, f(x) é a função geradora da sequência (0, 0, 2, 4, 8, 16, 32, …).
WELINGTON SANTOS
MATEMÁTICA DISCRETA
Código Logístico
59915
Fundação Biblioteca Nacional
ISBN 978-65-5821-012-2
9 7 8 6 5 5 8 2 1 0 1 2 2