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: