matematica_discreta

Prévia do material em texto

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/352648056
Uma Introdução à Matemática Discreta para a Computação: fundamentos
teóricos, exercícios e aplicações
Technical Report · June 2021
DOI: 10.13140/RG.2.2.17791.94882
CITATIONS
0
READS
517
1 author:
Some of the authors of this publication are also working on these related projects:
Encoded Blue Eyes Project (EBE) View project
Double Noise Filtering in CT: Pre- and Post-Reconstruction View project
Alexandre L M Levada
Universidade Federal de São Carlos
103 PUBLICATIONS   309 CITATIONS   
SEE PROFILE
All content following this page was uploaded by Alexandre L M Levada on 22 June 2021.
The user has requested enhancement of the downloaded file.
https://www.researchgate.net/publication/352648056_Uma_Introducao_a_Matematica_Discreta_para_a_Computacao_fundamentos_teoricos_exercicios_e_aplicacoes?enrichId=rgreq-e9d7cbbc760ba29a2247604099822a62-XXX&enrichSource=Y292ZXJQYWdlOzM1MjY0ODA1NjtBUzoxMDM3NDk3NTA1MTgxNjk2QDE2MjQzNzAwODkwMzk%3D&el=1_x_2&_esc=publicationCoverPdf
https://www.researchgate.net/publication/352648056_Uma_Introducao_a_Matematica_Discreta_para_a_Computacao_fundamentos_teoricos_exercicios_e_aplicacoes?enrichId=rgreq-e9d7cbbc760ba29a2247604099822a62-XXX&enrichSource=Y292ZXJQYWdlOzM1MjY0ODA1NjtBUzoxMDM3NDk3NTA1MTgxNjk2QDE2MjQzNzAwODkwMzk%3D&el=1_x_3&_esc=publicationCoverPdf
https://www.researchgate.net/project/Encoded-Blue-Eyes-Project-EBE?enrichId=rgreq-e9d7cbbc760ba29a2247604099822a62-XXX&enrichSource=Y292ZXJQYWdlOzM1MjY0ODA1NjtBUzoxMDM3NDk3NTA1MTgxNjk2QDE2MjQzNzAwODkwMzk%3D&el=1_x_9&_esc=publicationCoverPdf
https://www.researchgate.net/project/Double-Noise-Filtering-in-CT-Pre-and-Post-Reconstruction?enrichId=rgreq-e9d7cbbc760ba29a2247604099822a62-XXX&enrichSource=Y292ZXJQYWdlOzM1MjY0ODA1NjtBUzoxMDM3NDk3NTA1MTgxNjk2QDE2MjQzNzAwODkwMzk%3D&el=1_x_9&_esc=publicationCoverPdf
https://www.researchgate.net/?enrichId=rgreq-e9d7cbbc760ba29a2247604099822a62-XXX&enrichSource=Y292ZXJQYWdlOzM1MjY0ODA1NjtBUzoxMDM3NDk3NTA1MTgxNjk2QDE2MjQzNzAwODkwMzk%3D&el=1_x_1&_esc=publicationCoverPdf
https://www.researchgate.net/profile/Alexandre-Levada?enrichId=rgreq-e9d7cbbc760ba29a2247604099822a62-XXX&enrichSource=Y292ZXJQYWdlOzM1MjY0ODA1NjtBUzoxMDM3NDk3NTA1MTgxNjk2QDE2MjQzNzAwODkwMzk%3D&el=1_x_4&_esc=publicationCoverPdf
https://www.researchgate.net/profile/Alexandre-Levada?enrichId=rgreq-e9d7cbbc760ba29a2247604099822a62-XXX&enrichSource=Y292ZXJQYWdlOzM1MjY0ODA1NjtBUzoxMDM3NDk3NTA1MTgxNjk2QDE2MjQzNzAwODkwMzk%3D&el=1_x_5&_esc=publicationCoverPdf
https://www.researchgate.net/institution/Universidade_Federal_de_Sao_Carlos?enrichId=rgreq-e9d7cbbc760ba29a2247604099822a62-XXX&enrichSource=Y292ZXJQYWdlOzM1MjY0ODA1NjtBUzoxMDM3NDk3NTA1MTgxNjk2QDE2MjQzNzAwODkwMzk%3D&el=1_x_6&_esc=publicationCoverPdf
https://www.researchgate.net/profile/Alexandre-Levada?enrichId=rgreq-e9d7cbbc760ba29a2247604099822a62-XXX&enrichSource=Y292ZXJQYWdlOzM1MjY0ODA1NjtBUzoxMDM3NDk3NTA1MTgxNjk2QDE2MjQzNzAwODkwMzk%3D&el=1_x_7&_esc=publicationCoverPdf
https://www.researchgate.net/profile/Alexandre-Levada?enrichId=rgreq-e9d7cbbc760ba29a2247604099822a62-XXX&enrichSource=Y292ZXJQYWdlOzM1MjY0ODA1NjtBUzoxMDM3NDk3NTA1MTgxNjk2QDE2MjQzNzAwODkwMzk%3D&el=1_x_10&_esc=publicationCoverPdf
Departamento de Computação
Centro de Ciências Exatas e Tecnologia
Universidade Federal de São Carlos
Uma Introdução à Matemática
Discreta para a Computação
Fundamentos teóricos, exercícios e aplicações
Prof. Alexandre Luis Magalhães Levada
Email: alexandre.levada@ufscar.br
Sumário
Prefácio............................................................................................................................................3
Prólogo: Por que estudar matemática discreta?...............................................................................4
Aula 1: Métodos de prova................................................................................................................6
Aula 2: O princípio da indução matemática..................................................................................14
Aula 3: Conjuntos..........................................................................................................................24
Aula 4: Relações............................................................................................................................37
Aula 5: Relações de equivalência..................................................................................................47
Aula 6: Relações de ordem parcial................................................................................................53
Aula 7: Funções.............................................................................................................................65
Aula 8: Somatórios........................................................................................................................79
Aula 9: Sequências e relações de recorrência................................................................................86
Aula 10: Grafos e seus fundamentos básicos...............................................................................109
Aula 11: Árvores..........................................................................................................................120
Aula 12: Grafos Eulerianos e Hamiltonianos..............................................................................128
Aula 13: Grafos planares.............................................................................................................138
Aula 14: Coloração de vértices....................................................................................................147
Bibliografia..................................................................................................................................156
Sobre o autor................................................................................................................................158
“Experiência não é o que acontece com um homem; é o que ele faz com o que lhe acontece”
(Aldous Huxley)
Prefácio
Esta apostila sobre matemática discreta é um material recomendado para estudantes dos cursos de
Ciências e Engenharia da Computação como um primeiro contato com as definições, o formalismo
matemático e a abstração exigidos de um cientista da computação. Durante a apresentação de cada
tópicos, diversos exemplos e exercícios são apresentados como forma de motivar a resolução de
problemas por parte dos estudantes. Não há exigência de conhecimento prévio em área de
matemática e computação, de modo que o material pode ser utilizado tanto por iniciantes quanto
eventuais interessados de outras áreas da ciência.
Como a matemática discreta é uma área extremamente vasta, para que seja possível condensar o
conteúdo em um curso com duração de 1 semestre (60 horas/aula), foi necessário fazer uma seleção
dos tópicos mais relevantes. Como o público-alvo inicial era composto por estudantes dos cursos de
Ciência e Engenharia de Computação, o recorte dos assuntos abordados foi feito pensando neste
perfil de atuação. Isso não significa que o conteúdo omitido seja menos importante: trata-se apenas
de uma questão de prioridades.
Por fim, todo conteúdo aqui apresentado é fruto das notas de aula produzidas pelo professor durante
sua carreira como docente no Departamento de Computação da Universidade Federal de São
Carlos, de modo que pode ser utilizado sem fins lucrativos por qualquer pessoa interessada.
 
Alexandre L. M. Levada.
Prólogo: Por que estudar matemática discreta?
A matemática discreta apresenta de maneira sistemática o formalismo matemático necessário para a
modelagem e a resolução de problemas que envolvem estruturas discretas, que são objetos
matemáticos que não variam de forma contínua (o que ocorre em Cálculo, por exemplo). Em termos
abstratos, tais estruturas envolvem conjuntos finitos ou infinitos enumeráveis(que possuem uma
bijeção com o conjuntos dos inteiros, o que não é válido para o conjunto dos reais). Esse ramo da
matemática foi considerado a base para a revolução digital, pois ele fornece o embasamento teórico
da computação (onde tudo é discreto!). Podemos fazer uma analogia interessante: a matemática
discreta está para a revolução digital assim como o cálculo está para a revolução industrial.
Algumas perguntas relevantes que a matemática discreta nos permite responder são:
- De que formas podemos demonstrar que uma afirmação é válida (teoremas)?
- É possível utilizar o raciocínio indutivo para demonstrar um resultado? Porque?
- Para que serve a teoria dos conjuntos?
- O que são relações binárias e quais são suas propriedades?
- O que são funções e quais suas aplicações?
- Como podemos calcular somatórios de maneira analítica?
- Relações de recorrência e leis de formação: como resolvê-las?
- O que são grafos e quais suas aplicações?
Em suma, os objetivos deste curso são: 1) familiarizar os leitores com a estrutura das demonstrações
matemáticas, através da apresentação de diversos exemplos e exercícios; 2) capacitar os leitores a
deduzir e utilizar fatos e noções elementares sobre números, conjuntos, relações, funções e grafos;
3) estimular os leitores a utilizar raciocínio indutivo em seus pensamentos matemáticos; e 4)
mostrar como podemos utilizar matemática discreta para solucionar diversos tipos de problemas.
 Organização do conteúdo
Os tópicos a serem abordados neste material são organizados da seguinte maneira:
1. Métodos de prova
a) Contraexemplos
b) Método direto
c) Contrapositiva
d) Redução ao absurdo
e) Se e somente se
2. O princípio da indução matemática
3. Conjuntos e suas propriedades
4. Relações e suas propriedades
5. Relações de equivalência
6. Relações de ordem parcial
7. Funções e suas propriedades
a) Funções injetores
b) Funções sobrejetoras
c) Funções bijetoras
d) Composição de funções
e) Funções inversas
8. Somatórios
a) Progressões aritméticas
b) Progressões geométricas
c) Somas telescópicas
9. Sequências e relações de recorrência
10. Fundamentos básicos sobre grafos 
11. Árvores
12. Grafos Eulerianos e Hamiltonianos
13. Grafos Planares
14. Coloração de vértices
“Não trilhe apenas os caminhos já abertos. Por serem conhecidos eles nos levam somente até onde alguém já foi
um dia.” (Alexander Graham Bell)
Aula 1: Métodos de prova
Objetivo: demonstrar que uma determinada proposição é verdadeira.
Primeiramente, iremos definir a nomenclatura formal para os tipos distintos de proposições que
desejamos provar.
1. Conjectura: ideia, afirmação, ou fórmula que ainda não foi provada ser verdadeira.
2. Teorema: é uma ideia, afirmação ou fórmula demonstrada.
3. Lema: é um teorema demonstrado apenas para auxiliar na prova de outro(s) teorema(s).
4. Corolário: é um teorema que é uma consequência direta de outro teorema.
O que é uma definição?
É uma sentença que identifica exatamente um conceito definido.
Por exemplo, a seguir veremos diversas definições sobre a teoria dos números.
Def: ∀n , p∈N n é um múltiplo de p se e somente se ∃q∈N /n=qp
Def: ∀n , p∈N p divide n se e somente se n é múltiplo de p
Def: ∀n∈N n é par se e somente se ∃k∈N /n=2 k
Def: ∀n∈N n é ímpar se e somente se ∃k∈N /n=2 k+1
Def: ∀n∈N n é primo se e somente se n > 1 e n não tem divisor maior que 1, exceto o próprio n
Def: ∀m ,n∈N m e n são coprimos se e somente se o único divisor comum é 1.
Em alguns casos, é necessário mostrar que uma afirmação é falsa, o que, em geral, é bem mais fácil
do que provar sua veracidade, pois basta encontrarmos um contra-exemplo.
Ex: A afirmação a seguir é verdadeira ou falsa? Prove.
∀a ,b∈Z (a2=b2→a=b)
É trivial provar que essa afirmação é falsa, bastando para isso considerar um caso em que a2=b2
seja verdadeiro, mas a=b seja falso. Seja a = 1 e b = -1. Com isso, teremos um caso particular
para o qual a afirmação não é verdade. Isso é o suficiente para demonstrar que ela é falsa. Porém,
para provar que uma afirmação do tipo ∀ x∈N P(x )→Q (x) é verdadeira, não basta
selecionarmos um ou mais casos e verificar que ela é verdadeira. Isso não é suficiente! Precisamos
mostrar que ela é verdadeira para todos os possíveis elementos do conjunto N.
Prova direta (p → q)
- Em geral, partimos de uma hipótese p verdadeira.
- Devemos utilizar uma sequência de consequências lógicas para obter a conclusão q.
- Se conseguirmos chegar na conclusão q, provamos que p → q.
Teorema: Se m e n são inteiros pares, então m+n é par.
1. Supor m∈N par (hip)
2. Supor n∈N par (hip)
3. Então, ∃r∈N /m=2r
4. Então, ∃s∈N /n=2 s
5. Assim, m+n=2 r+2 s=2 (r+s )
6. Fazendo t=r+s , sabemos que t∈N pois N é fechado para adição (soma de inteiros é
inteiro)
7. Como ∃ t∈N /m+n=2 t , então m + n é par
Outra definição importante é a que define o que são números racionais. Dizemos que um número é
racional se ele pode ser expresso pela divisão de 2 inteiros. De modo mais formal, temos a seguinte
definição.
Def: ∀ x∈R x é racional se e somente se ∃a , b∈N / x=
a
b
 com b≠0 e de modo que a e b
não possuem fatores comuns (a e b são coprimos). 
Teorema: Se x e y são racionais, então x + y é racional.
1. Supor x e y racionais (hip)
2. Então, podemos expressar x=
a
b
 e y=
c
d
, com a , b , c , d∈N e b≠0 , d≠0
3. Assim, temos que x+ y=
a
b
+
c
d
=
ad+bc
bd
4. Seja p=ad+bc e q=bd .
5. Então p ,q∈N , pois os naturais são fechados para adição e multiplicação.
6. Portanto, x+ y=
p
q
 é racional.
Em alguns casos, para provar uma afirmação do tipo p → q, não temos acesso direto a p. Nessas
situações, podemos utilizar uma lógica reversa (backtracking). O exemplo a seguir ilustra essa ideia.
Ex: Prove que a média aritmética de dois números distintos é sempre maior ou igual a média
geométrica dos mesmos números.
Note que sabemos onde queremos chegar, mas não está claro de onde devemos partir. Neste caso, p
não é fornecido de maneira explícita. Iniciamos definindo as médias aritméticas e geométricas
como:
mA=
x+ y
2
 e mG=√xy
Podemos escolher alguns valores de x e y para verificar que aparentemente a média aritmética é
sempre maior ou igual que a geométrica.
a) x = 1 e y = 3: mA=2 > mG=√3
b) x = 2 e y = 4: mA=3 > mG=√8
c) x = 3 e y = 5: mA=4 > mG=√15
Como podemos provar que mA>mG para x≠ y ?
Vamos tentar partir da conclusão e ver onde podemos chegar.
1. Vamos partir de 
x+ y
2
>√xy
2. Elevando ambos os lados ao quadrado temos 
(x+ y)2
4
>xy
3. Multiplicando ambos os lados por 4 temos (x+ y)2>4 xy
4. Expandindo o quadrado temos (x+ y)2>4 xy
5. Subtraindo 4xy de ambos os lados temos x2−2 xy+ y2>0
6. Fatorando o polinômio quadrático temos (x− y )2>0
Note que (x− y )2>0 é sempre verdadeiro para x≠ y . Então, se invertermos os passos da
prova direta, ou seja, se partirmos de 6 e chegarmos em 1, fazendo os devidos ajustes (como somar
4xy ao invés de subtrair), temos uma sequência de consequências lógicas válidas e portanto uma
prova direta.
Lema de Euclides: se p é um número primo e p é um fator de ab, então p é um fator de a ou de b.
Para a = b, temos que se p divide a2 , então p divide a
1. Pelo Teorema Fundamental da Aritmética: “Todos os inteiros positivos maiores que 1 possuem
uma decomposição única em fatores primos”, então a=p1 p2 p3 ... pn
2. Assim, a2=( p1 p2 p3 ... pn)( p1 p2 p3 ... pn)=( p1 p1)( p2 p2)( p3 p3)...( pn pn)
3. Logo, se p é um dos fatores primos de a2 , então p também é um fator primo de a.
Prova por contrapositiva
Muitas vezes, para provar p → q, podemos utilizar a consequência lógica a seguir:
p→q≡¬q→¬p
pois as duas expressões lógicas são equivalentes. Veja a tabela verdade a seguir.
p q ¬p ¬q p→q ¬q→¬p
 
 V V F F V V
 V F F V F F
 F V V F V V
 F F V V V V
Vejamos um exemplo no teorema a seguir.
Teorema: Se n2 é um inteiro par, então n é par.
É fácil notar que as proposições são:
p : n2 é par ¬p : n2 não é par (é ímpar)
q : n é par ¬q : nnão é par (é ímpar)
Utilizando a contrapositiva, temos que p→q≡¬q→¬p , o que se traduz para:
Se n é ímpar, então n2 é ímpar.
Essa afirmação é mais fácil de ser provada, sendo essa uma das grandes vantagens da prova por
contrapositiva, simplificar a prova direta em algumas situações.
1. Se n é ímpar, então n=2k+1 , para algum k inteiro.
2. Então, n2=(2k+1)2=4 k2+4 k+1=2(2k2+2 k )+1
3. Como o conjunto dos inteiros é fechado para adição e produto, p=2k2+2k é inteiro.
4. Como n2=2 p+1 , com p∈N , temos que n2 é ímpar.
Ex: Demonstre que ∀n∈N , se n3+5 é ímpar, então n é par.
Ex: Demonstre que se p é um inteiro ímpar, então x2+x−p=0 não tem solução inteira.
Iremos utilizar a prova por contrapositiva. Note que as proposições p e q são:
p : p é inteiro ímpar
q : x2+x− p=0 não admite solução inteira
Assim, a negação das proposições fica:
¬p : p é inteiro par
¬q : x2+x−p=0 admite solução inteira
Então, devemos provar que ¬q→¬p .
1. Se x2+x−p=0 admite solução inteira, então:
x=
−1±√1−4 p
2
2. Para que x seja inteiro, então
√1−4 p−1 e −√1−4 p−1 devem ser pares, o que ocorre apenas se √1−4 p for ímpar.
3. Isso significa que √1−4 p=2k+1 para algum k inteiro, o que implica em
1−4 p=(2 k+1)2
1−4 p=4k2+4k+1
4 p=4 k2+4 k
p=k2+k=k (k+1)
Note que p é sempre par, pois ou k ou k+1 é sempre par e o produto de um inteiro ímpar com um
inteiro par, sempre resulta em um inteiro par.
(2 k )(2k+1)=4 k2+2k=2(2 k2+k )
Portanto, a prova está concluída.
Ex: Prove que para n∈N se 3n + 2 é ímpar, então n é ímpar.
Prova por redução ao absurdo (ou contradição)
A justificativa matemática da prova por contradição vem da seguinte equivalência lógica:
p→q≡( p∧¬q)→F
p q ¬q p∧¬q p→q ( p∧¬q)→F
 
 V V F F V V
 V F V V F F
 F V F F V V
 F F V F V V
Ideia: para provar p→q supomos que tanto a hipótese p quanto a negação da conclusão
¬q são verdadeiras e buscamos deduções lógicas que terminem numa contradição (afirmação
falsa).
Ex: Prove que se m e n são inteiros pares, então m + n é inteiro par.
1. Suponha m ,n∈N pares e m+n∈N ímpar.
2. Então, m=2 p para p∈N e n=2q para q∈N
3. Pela hipótese inicial, m + n é ímpar, ou seja, ∃k∈N tal que m+n=2 k+1
4. Logo, 2 p+2q=2k+1 , o que implica em p+q−k=
1
2
5. Porém, isso é falso uma vez que p+q−k é um inteiro.
Contradição! A afirmação é verdadeira.
Teorema: Não há limite superior nos naturais N.
1. Suponha que ∃n∈N que seja o máximo elemento do conjunto.
2. Então n≥x para ∀ x∈N
3. Seja m=n+1 . Como os inteiros são fechados para a adição, m∈N
4. Ora, temos que m>n .
5. Então, m é maior que o máximo elemento do conjunto dos naturais.
Contradição para hipótese (1). A afirmação é verdadeira.
Teorema: √2 é um número irracional.
1. Iremos supor que √2 pertence aos conjunto dos racionais (Q)
2. Então, √2=
a
b
 , com b≠0 sendo que a e b não possuem fatores comuns (coprimos)
3. Assim, 2=
a2
b2
, o que implica em a2=2b2
4. Temos que a2 é um número par.
5. Para que a2 seja par, é necessário que a também seja par, ou seja a=2k , para k∈N
6. Isso implica que 2b2=a2=4 k2 , ou seja, b2=2k 2
7. Então, b2 é um número par, e assim, b também é par
8. Note que 2 divide tanto a quanto b, o que nos leva a uma contradição.
Teorema: Existem infinitos números primos.
1. Suponha que o conjunto dos números primos seja finito: P = {2, 3, 5, 7, … p}
2. Seja n o inteiro definido pela multiplicação de todos os números primos adicionado de uma
unidade, ou seja: n=(2×3×5×7×...×p)+1
3. Como ele é maior que 1, n deve ter algum fator primo
4. Note que n não é divisível por nenhum número do conjunto dos números primos P, uma vez que
terá resto 1.
5. Do Teorema Fundamental da Aritmética, sabemos que: “Todos os inteiros positivos maiores que
1 possuem uma decomposição única em fatores primos”
6. Portanto, o número primo r que é um dos fatores de n, não pode ser nenhum dos primos em P.
7. Isso contradiz a suposição de que P contém todos os números primos.
Contradição. Portanto, o teorema é válido.
Teorema: √2 é irracional.
1. 1. Iremos supor que √2 pertence aos conjunto dos racionais (Q)
2. Então, √3=
a
b
 , com b≠0 sendo que a e b não possuem fatores comuns (coprimos)
3. Assim, 3=
a2
b2
, o que implica em a2=3b2
4. Temos que a2 é um número divisível por 3
5. Pelo Lema de Euclides, se a2 é divisível por 3, então a também é divisível por 3
6. Isso implica que a=3k e portanto a2=9k2
7. Sendo assim, 3 b2=9 k2 , o que implica em b2=3 k2 , e assim b2 é divisível por 3
7. Então, novamente pelo Lema de Euclides, b também é divisível por 3.
8. Portanto, a e b não são coprimos, pois ambos são divisíveis por 3.
Contradição! Portanto, o teorema é válido.
Demonstrações com se e somente se
Sabemos que da lógica matemática, é válida a seguinte equivalência:
p⇔q≡( p⇒q)∧(q⇒ p)
Assim, dividimos a prova em 2 partes: a ida e a volta.
Teorema: Dois inteiros x e y são ambos ímpares se e somente se o produto xy é ímpar.
p: x , y∈N são ímpares q: o produto xy é ímpar
Parte 1: p → q (ida)
1. Se x e y são ambos números ímpares, então:
x=2 r+1
y=2 s+1
2. Assim, o produto vale:
xy=(2r+1)(2 s+1)=4 rs+2 r+2 s+1=2(2rs+r+s)+1
3. Como o conjunto dos inteiros é fechado para adição e produto, k=2rs+r+s∈N
4. Portanto, como xy=2 k+1 , o produto é um número ímpar
Parte 2: q → p (volta)
Pela contrapositiva, devemos provar ¬q→¬p , u seja:
Se x ou y é par, então o produto xy é par
Caso a) x é par
∃r∈N /x=2r . Assim, xy=(2r ) y=2(ry)=2 k e portanto o produto é par.
Caso b) y é par
∃s∈N / y=2 s . Assim, xy=x (2 s)=2(sx)=2k ' e portanto o produto é par.
A prova está concluída.
Ex: Prove que um inteiro positivo n é ímpar se e somente se 5n + 6 é ímpar.
Demonstração por vacuidade
Se E é o conjunto vazio, temos que a proposição ∀ x∈E Q (x) é verdadeira para qualquer que
seja o predicado Q.
Ex: Todos os inteiros pares e primos maiores que 2 são quadrados perfeitos.
Supondo que D represente o domínio dos inteiros pares e
A(x): x é um inteiro primo maior que 2
B(x): x é um inteiro quadrado perfeito
∀ x∈D A (X )→B(x )
Como não existem inteiros primos maiores que 2, a proposição é verdadeira por vacuidade, uma vez
que A(x) sempre retorna F (falso) e F implica tanto F quanto V é sempre verdade.
Ex: ∀ x∈N , se x2=5 então x é par.
Uma das principais conjecturas ainda não demonstradas na teoria dos números é a conjectura de
Goldbach que diz: todo inteiro par maior que 2 é a soma de dois números primos.
Note que:
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 5 + 5
12 = 5 + 7
14 = 7 + 7
16 = 5 + 13
…
Apesar de todos os inteiros pares até 4 x 1018 já terem sido testados com sucesso, até hoje, nenhuma
prova matemática foi construída. Para maiores detalhes, verificar:
https://en.wikipedia.org/wiki/Goldbach%27s_conjecture
“The real voyage of discovery consists not in seeking new landscapes, but in having new eyes.”
(Marcel Proust)
https://en.wikipedia.org/wiki/Goldbach's_conjecture
Aula 2: O princípio da indução matemática
Suponha uma escada com infinitos degraus. Queremos saber se podemos alcançar todo degrau
dessa escada. Para isso, devemos garantir duas condições:
1. Podemos alcançar o primeiro degrau;
2. Se podemos alcançar um degrau particular i, então podemos alcançar o próximo degrau i+1.
Essa é a intuição que guia o princípio da indução matemática.
Veremos uma introdução a essa importante técnica de demonstração, que nos permite provar
afirmações matemáticas que são definidas em um conjunto infinito (porém enumerável) de casos.
Def: O princípio da indução matemática
Para provar que a proposição matemática P(n) é válida para todo inteiro positivo n, devemos seguir
dois passos:
i) BASE: deve-se verificar que P(1) (ou P(0) em alguns casos) é verdadeira.
ii) PASSO DE INDUÇÃO: deve-se mostrar que P(k)→P(k+1) para todo k (escolha um k arbitrário)
Em termos matemáticos, escrevemos:
[P(1)∧∀ k (P(k )→P(k+1))]→∀ n∈N+ P (n)
Porque a indução matemática é válida?
Primeiramente, iremosapresentar um princípio fundamental para entendermos a resposta a essa
pergunta.
Princípio da boa ordenação (PBO) : Todo subconjunto não vazio de N possui um menor elemento.
Iremos provar por contradição que a indução matemática é válida.
1. Vamos supor que P(1) é verdadeira e que para todo k, P(k)→P(k+1)
2. Desejamos mostrar que P(n) é verdadeira ∀n∈N
3. Assuma que exista pelo menos um inteiro positivo para o qual P(n) é falso.
4. Então, o conjunto S dos inteiros positivos para os quais P(n) é falso não é vazio.
5. Pelo PBO, S tem um menor elemento, denotado por m.
6. Sabemos que m≠1 pois P(1) é verdadeira.
7. Como m é positivo, m > 1. Assim, m – 1 > 0.
8. Como m – 1 < m, então m−1∉S . Então, P(m – 1) deve ser verdadeira.
9. Mas pela suposição inicial, para todo k, P(k)→P(k+1), o que implica em: P(m–1) → P(m) é
verdade.
10. Isso faz com que P(m) tenha que ser verdadeira, o que gera uma contradição.
Portanto, P(n) é verdadeira para todo n.
Ex: Prove que se n é um inteiro positivo, então 
P(n):1+2+3+ ...+n=
n(n+1)
2
 é verdadeira para todo n.
BASE: P(1): 1 = 1 (OK)
PASSO DE INDUÇÃO: Assumiremos que P(k) é válida para um k arbitrário, ou seja:
P(k ) :1+2+3+...+k=
k (k+1)
2
Sob essa hipótese, devemos mostrar que P(k+1) é verdadeira. Note que:
1+2+3+...+k+(k+1)=(1+2+3+...+k )+(k+1)
Mas podemos substituir o primeiro parêntesis, uma vez que P(k) é válida:
k (k+1)
2
+(k+1)=
k (k+1)+2(k+1)
2
=
(k+1)(k+2)
2
o que nos leva a proposição P(k+1):
P(k+1) :1+2+3+ ...+k+(k+1)=
(k+1)(k+2)
2
que é justamente o que deveríamos obter ao substituir k por k+1 em P(k).
Portanto, a prova está completa.
Ex: Elabore uma fórmula para computar a soma dos n primeiros inteiros positivos ímpares. Prove
por indução que sua equação vale para qualquer valore de n.
Vamos iniciar observando o padrão a seguir:
n números soma
1 1 1
2 1+3 4
3 1+3+5 9
4 1+3+5+7 16
5 1+3+5+7+9 25
…
A sugestão parece óbvia a esse ponto. A conjectura parecer ser definida pela proposição:
P(n):1+3+5+...+2n−1=n2
Desejamos provar que essa proposição é válida para todo n inteiro maior que zero.
BASE: P(1): 1 = 1 (OK)
PASSO DE INDUÇÃO: Para k arbitrário, supor P(k) válido, ou seja:
P(k ) :1+3+5+...+2 k−1=k2
e mostrar que P(k+1) :1+3+5+...+2 k−1+2k+1=(k+1)2 . Para isso, note que:
(1+3+5+...+2k−1)+(2 k+1)=k2+2k+1=(k+1)2
o que conclui a prova.
Ex: Use a indução matemática para provar que:
P(n):1+2+22+23+...+2n=2n+1−1
é válida para todo inteiro n não negativo.
BASE: P(0): 20=1=2−1=1 (OK)
PASSO DE INDUÇÃO: Para k arbitrário, supor P(k) válido, ou seja:
P(k ) :1+2+22+23+...+2k=2k+1−1
e mostrar que P(k+1) :1+2+22+23+...+2k+2k +1=2(k+1)+1−1
Note que:
(1+2+22+23+ ...+2k)+2k+1=2k +1−1+2k+1=2×2k +1−1=2(k+1)+1−1
e portanto a prova está completa.
Ex: Uma sequência do tipo 1 ,
1
2
,
1
4
,
1
8
, ... é uma P.G. (progressão geométrica) em que o primeiro
termo é a0 = 1/2 e a razão é r = 1/2. Sabemos que o k-ésimo termo de uma PG é computado como:
ak=a0 r
k
Use a indução matemática para provar que a soma dos termos de uma P.G. finita com a0 = a e razão
r é dada por:
P(k ) :a+ar+ar2+ar3+...+ar k=
ark+1−a
r−1
 , com r≠1
onde k é um inteiro não negativo.
BASE: P(0): a=
ar−a
r−1
=
a (r−1)
(r−1)
=a (OK)
PASSO DE INDUÇÃO: Para k arbitrário, supor P(k) válido e mostrar que
P(k+1) :a+ar+ar2+ ...+ark+ar k+1=
ark +2−a
r−1
Note que:
(a+ar+ar2+...+ar k)+ar k+1=
ark +1−a
r−1
+ar k+1=
ark+1−a+(r−1)ark +1
r−1
=
ark+1−a+ark +2−ar k+1
r−1
o que nos leva diretamente a:
a+ar+ar2+...+ark+ark+1=
ar k+2−a
r−1
concluindo a prova.
Ex: Use a indução matemática para provar a desigualdade:
n<2n
para todo inteiro positivo n.
BASE: P(1): 1 < 2 (OK)
PASSO DE INDUÇÃO: Para k arbitrário, supor P(k): k < 2k válido
Sabemos que P(k) é verdadeira, portanto:
k<2k
Somando um de ambos os lados:
k+1<2k+1
Mas como 1≤2k ,∀ k∈N
k+1<2k+1≤2k+2k=2×2k=2k +1
mostrando que P(k+1) é verdadeira. Portanto, a prova está concluída.
Ex: Use a indução matemática para provar a desigualdade 2n<n! para n≥4 .
Ex: Os números harmônicos são definidos como:
H j=1+
1
2
+
1
3
+...+
1
j
 para j = 1, 2, …, n
Por exemplo, temos que H 4=1+
1
2
+
1
3
+
1
4
=
25
12
Use a indução matemática para provar que H
2n
≥1+
n
2
 , ou seja, que essa soma é divergente.
BASE: P(0): H1=1=1 (OK)
PASSO DE INDUÇÃO: Para k arbitrário, mostrar que se:
H
2k
>1+
k
2
 (*)
então
H
2k+1
>1+
k+1
2
Primeiramente, note que:
H
2k+1
=(1+
1
2
+
1
3
+...+
1
2k )+
1
2k+1
+
1
2k+2
+...+
1
2k+1
O somatório entre parêntesis é justamente H 2k :
H
2k+1
=H
2k
+
1
2k+1
+
1
2k+2
+...+
1
2k+1
Utilizando a hipótese de indução (*):
H
2k+1
>(1+ k2 )+[
1
2k+1
+
1
2k+2
+...+
1
2k+1 ]
Note que cada um dos 2k termos do somatório entre colchetes é maior ou igual a 
1
2k+1
, de
modo que a desigualdade continuará sendo válida se substituirmos o somatório por 2k
1
2k +1
:
H 2k+1>(1+ k2 )+2
k 1
2k+1
o que nos leva a:
H2k+1>(1+ k2 )+
1
2
=(1+ k+12 )
concluindo a prova.
Ex: Use a indução matemática para provar que 7n+2+82 n+1 é divisível por 57.
Temos nossa proposição P(k) definida por: 
P(k ) :(7k+2+82k +1) mod 57=0
BASE: P(0): (72+8) mod 57=0 (OK)
PASSO DE INDUÇÃO: Para k arbitrário, mostrar que P(k) → P(k+1)
Note que:
P(k+1) :(7(k+1)+2+82 (k +1)+1) mod 57=0
 
Asim, devemos mostrar que 7k +3+82 k+3 é divisível por 57.
Uma observação importante consiste em lembrar que 
∀a ,b , x∈N se a mod x = 0 e b mod x = 0, então (a + b) mod x = 0.
7k +3+82 k+3=7×7k+2+82×82 k+ 1=7×7k+2+64×82k+1
Mas note que 64 = 7 + 57, ou seja:
7×7k+2+64×82 k+1=7×7k+2+(7+57)×82 k +1=7×7k+2+7×82 k +1+57×82 k+1
Colocando em evidência o fator 7, temos:
7×(7k+2+82 k +1)+57×82 k+1
Mas, pela hipótese indutiva, sabemos que a primeira parcela da soma é divisível por 57. 
A segunda parcela da soma é trivialmente divisível por 57, pois é múltiplo de 57.
Portanto, 7k +3+82 k+3 é de fato divisível por 57 e P(k+1) é verdadeira.
A prova está concluída.
Ex: Use a indução matemática para provar que (n3−n) mod 3=0 ,∀n∈N+
Ex: Um pesquisador desenvolveu uma fórmula para calcular o somatório do quadrado dos n
primeiros inteiros positivos. Mostre por indução que essa fórmula vale ∀n∈N .
P(k ) :12+22+32+...+k2=
k (k+1)(2 k+1)
6
BASE: P(1): 1 = 6 / 6 = 1 (OK)
PASSO DE INDUÇÃO: 
Note que P(k+1) é dada por:
P(k+1) :12+22+32+...+k 2+(k+1)2=
(k+1)(k+2)(2(k+1)+1)
6
=
(k+1)(k+2)(2k+3)
6
Utilizando a hipótese de indução, o somatório dos (k+1) primeiros inteiros ao quadrado pode ser
expressa como:
(12+22+32+ ...+k2)+(k+1)2=
k (k+1)(2 k+1)
6
+(k+1)2
o que pode ser escrito como:
k (k+1)(2 k+1)+6(k+1)2
6
=
(k+1)(k (2k+1)+6 (k+1))
6
=
(k+1)(2 k2+k+6 k+6)
6
Note que temos k + 6k = 7k = 3k + 4k, o que nos permite escrever:
(k+1)(2 k2+3 k+4 k+6)
6
=
(k+1)(k (2k+3)+2(2 k+3))
6
=
(k+1)(k+2)(2 k+3)
6
Portanto, a prova está concluída.
Ex: Utilizando a indução matemática, prove que 3 divide 5n+2×11n para todo inteiro positivo n
Ex: Um estudante de matemática discreta observou o seguinte padrão:
1 x 1! --------------------------------------------------------------------------------------- 2! - 1 = 1
1 x 1! + 2 x 2! ------------------------------------------------------------------------------ 3! - 1 = 5
1 x 1! + 2 x 2! + 3 x 3! -------------------------------------------------------------------- 4! - 1 = 23
1 x 1! + 2 x 2! + 3 x 3! + 4 x 4! ---------------------------------------------------------- 5! - 1 = 119
…
1 x 1! + 2 x 2! + 3 x 3! + 4 x 4! + … + n x n! ------------------------------------------ (n+1)! - 1
Esse padrão observado é válido para todo inteiro k > 0? Prove sua resposta.
Seja a proposição P(k) definida por:
1×1 !+2×2!+3×3 !+4×4 !+…+k×k !=(k+1)!−1
BASE: P(1) = 1 = 2 – 1 = 1 (OK)
PASSO DE INDUÇÃO: Para k arbitrário, mostrar que P(k) → P(k+1)
Note que:
P(k+1) :1×1!+2×2 !+3×3 !+4×4 !+…+k×k !+(k+1)×(k+1)!=(k+2)!−1
Partindo do lado esquerdo da igualdade, temos:
(1×1 !+2×2!+3×3 !+4×4 !+…+k×k!)+(k+1)×(k+1)!
que, utilizandoa hipótese de indução, pode ser reescrito como:
(k+1)!−1+(k+1)×(k+1)!
Aplicando a distributiva, temos:
(k+1)!−1+k×(k+1)!+(k+1)!=2×(k+1)!+k×(k+1)!−1
Colocando (k + 1)! em evidência:
(k+2)(k+1)!−1=(k+2)!−1
pois k(k-1)! = k!
A prova está concluída.
Ex: Utilizando a indução matemática, prove a desigualdade de Bernoulli:
(1+h)n≥1+nh para ∀n∈N , n≥0 com h > 0 (taxa de juros)
A ideia dessa desigualdade consiste em comparar o avanço de um capital a juros compostos com o
avanço de um capital a juros simples, mostrando que juros compostos sempre rendem pelo menos
igual aos juros simples.
Podemos expressar a proposição P(k) como:
P(k ) :(1+h)k≥1+kh
BASE: P(0): 1≥1 (OK)
PASSO DE INDUÇÃO: Para k arbitrário, mostrar que P(k) → P(k+1)
Sabemos que 
(1+h)k≥1+kh
Multiplicando ambos os lados por (1 + h)
(1+h)k+1≥(1+nh)(1+h)
Aplicando a distributiva, temos:
(1+h)k+1≥1+h+kh+kh2 (*)
Mas, pela definição de P(k), sabemos que P(k + 1) é dada por:
P(k+1) :(1+h)k+1≥1+(k+1)h=1+h+kh
Ora, mas como kh2 é estritamente positivo, temos que se a equação (*) é verdade, P(k+1) é
verdadeira com mais folga ainda. Portanto, a prova está completa.
Ex: Prove por indução que 12+32+52+ ...+(2n−1)2=
n(2 n−1)(2 n+1)
3
Podemos expressar a proposição P(k) como:
P(k ) :12+32+52+...+(2k−1)2=
k (2 k−1)(2k+1)
3
BASE: P(1) = 1 = 3/3 = 1 (OK)
PASSO DE INDUÇÃO: Para k arbitrário, mostrar que P(k) → P(k+1), ou sjea:
P(k+1) :12+32+52+...+(2 k−1)2+(2 k+1)2=
(k+1)(2 k+1)(2 k+3)
3
Primeiramente, note que pela hipótese indutiva temos:
(12+32+52+...+(2 k−1)2)+(2 k+1)2=
k (2 k−1)(2k+1)
3
+(2 k+1)2
Unificando os denominadores:
k (2k−1)(2 k+1)+3(2 k+1)2
3
Colocando em evidência:
(2 k+1)(k (2 k−1)+3 (2 k+1))
3
=
(2 k+1)(2 k2−k+6 k+3)
3
Como 6k – k = 5k = 2k + 3k, podemos escrever:
(2 k+1)(2 k2+2k+3 k+3)
3
=
(2k+1)(2k2+3 k+2 k+3)
3
=
(2 k+1)(k (2 k+3)+(2 k+3))
3
Colocando 2k + 3 em evidência, finalmente chegamos em:
(k+1)(2 k+1)(2k+3)
3
concluindo a prova.
Exercícios
1. Prove por indução que:
 13+23+33+ ...+n3=[ n (n+1)2 ]
2
 
para todo n inteiro positivo.
2. Encontre uma fórmula para calcular
 
1
2
+
1
4
+
1
8
+...+
1
2n
. 
Prove que sua fórmula vale para todo inteiro n> 0.
3. Prove por indução que
1
1×2
+
1
2×3
+
1
3×4
+...+
1
(n−1)n
=
n−1
n
para todo inteiro n > 1.
Antes de desistir, lembre-se: a última parte de uma árvore a crescer são os frutos
(Anônimo)
Aula 3: Conjuntos
Um conjunto é uma coleção não ordenada de objetos distintos. A teoria dos conjuntos é o ramo da
ciência que estuda definições e propriedades de conjuntos particularmente relevantes à matemática.
Por exemplo, seja o conjunto A = {1, 2, 3, 4, 5}. Trata-se de um conjunto finito com 5 elementos e
por isso dizemos que sua cardinalidade é igual a 5, ou matematicamente, |A| = 5. Em matemática
discreta, o interesse maior é no estudo de conjuntos finitos ou infinito enumeráveis. Um conjunto X
é dito infinito enumerável, se é possível encontrar uma bijeção entre os seus elementos e o conjunto
dos inteiros. Um exemplo de conjunto infinito não enumerável é o conjunto dos reais, uma vez que
entre quaisquer dois números reais existem infinitos outros números reais.
Uma noção importante na teoria dos conjuntos é a pertinência. Dizemos que um elemento x
pertence a um conjunto A se x é um dos elementos de A. Matematicamente, dizemos que x∈A
Definindo conjuntos
Há diversas maneiras de definir um conjunto. A mais simples delas é basicamente enumerar todos
seus elementos. Por exemplo, o conjunto dos números primos menores que 10 é dado por:
A = {2, 3, 5, 7}
Outra forma de especificar conjuntos, particularmente interessante para definir conjuntos infinitos, é
através de propriedades. Por exemplo:
A={x : x∈P∧x<10}
onde P é o conjunto dos números primos. Outro exemplo é o conjunto dos naturais que consiste no
conjunto dos inteiros maiores ou iguais a zero.
N={x : x∈Z∧x≥0 }
Dizemos que um conjunto A é vazio se ele não contém elementos. Denota-se por A=∅ .
Um exemplo de conjunto vazio é definido a seguir:
A={x : x∈N∧0<x<1 }
A seguir veremos algumas definições básicas da teoria dos conjuntos.
Def: Subconjunto
Dizemos que A é um subconjunto de B se todo elemento de A está em B. Matematicamente:
A⊆B⇔(∀ x , x∈A→x∈B) ( A está contido em B)
A⊈B⇔∃x / x∈A∧x∉B (A não está contido em B)
Def: Subconjunto próprio
Dizemos que A é um subconjunto próprio de B se todo elemento de A está em B, mas existe ao
menos um elemento de B que não está em A. Matematicamente:
A⊂B⇔ A⊆B∧∃x∈B /x∉A
Def: Igualdade de conjuntos
Dados dois conjuntos quaisquer A e B, A = B se e somente se A⊆B e B⊆A
Operações entre conjuntos e diagramas de Venn
Diagramas de Venn são representações gráficas muito úteis para a visualização de conjuntos e suas
relações. A seguir mostramos operações básicas sobre dois conjuntos e seus diagramas de Venn.
1. Conjunto universo (U): é o conjunto que contém todos os elementos de interesse.
2. Complementar de A: A={x : x∉A }
A=U−A
B=U−B
3. União: A∪B={x : x∈A∨x∈B }
4. Intersecção: A∩B={x : x∈A∧x∈B }
Se A∩B=∅ , dizemos que A e B são disjuntos
5. Diferença: B−A={x : x∈B∧x∉A }=B∩A , onde A denota o complementar de A.
Observação: Note que se A⊆B , então A∪B=B , A∩B=A e B⊆A .
Ex: Forneça exemplos em que temos:
a) (A∪B)−B=A
b) (A∪B)−B≠A
Ex: Seja o conjunto universo U={x∈N /0≤x≤9 } e os conjuntos A, B e C definidos como:
A={1,2,3,4 }
B={x∈N /(x−1)(x−3)2=0 }
C={x∈N /x mod 2=0}
Calcule:
a) A∪B
b) A∩(B∪C)
c) C – A
d) |A|, |B| e |C|
e) A∪C
Def: A diferença simétrica entre A e B é definida como:
A⊖B=(A−B)∪(B−A)
Se A = B, então A⊖B=∅
Se A∩B=∅ , então A⊖B=A∪B
Pergunta: se A⊖B=A , o que podemos dizer sobre os conjuntos A e B?
Até o presente momento vimos como definir as operações de união e intersecção entre dois
conjuntos. Mas elas podem ser generalizados para coleções de conjuntos.
Def: União e intersecção de coleções de conjuntos 
Dados conjuntos A0 , A1, ... , An que são subconjuntos de um universo U e um inteiro positivo n:
 = {x∈U / x∈Ai pelo menos para um i=0,1,2... , n }
 = {x∈U / x∈Ai para todo i=0,1,2 ,... , n }
Ex: Para todo inteiro i positivo, seja A i={x∈R :−1i <x
1
i }=(−
1
i
,
1
i )
a) Encontre 
Como x∈(−1 , 1 )∨x∈(−12 ,
1
2 )∨x∈(−
1
3
,
1
3 ) , temos 
b) Encontre 
Como x∈(−1 , 1 )∧x∈(−12 ,
1
2 )∧x∈(−
1
3
,
1
3 ) , temos 
c) Encontre 
Como x∈(−1 , 1 )∧x∈(−12 ,
1
2 )∧...∧x∈(−
1
∞ ,
1
∞ ) , temos 
Note que o resultado é o conjunto contendo um único elemento: o zero. Isso é diferente de ser o
conjunto vazio! Pense a respeito.
Princípio da inclusão-exclusão para 2 conjuntos
A seguir veremos um importante resultado da teoria dos conjuntos sobre a contagem de elementos
na união de dois conjuntos quaisquer A e B.
Teorema: O princípio da inclusão-exclusão (n = 2)
Dados dois conjuntos finitos A e B. Então podemos afirmar que:
|A∪B|=|A|+|B|−|A∩B|
Prova: 
1. Note que A∪B pode ser descomposto em 3 conjuntos disjuntos: 
A−B , A∩B e B−A
2. Isso implica em:
A∪B=(A−B)∪(A∩B)∪(B−A)
de modo que 
|A∪B|=|(A−B)∪(A∩B)∪(B−A)|=|A−B|+|A∩B|+|B−A|
3. Mas note que:
|A−B|=|A|−|A∩B| e
|B−A|=|B|−|A∩B|
4. Portanto, temos:
|A∪B|=|A−B|+|A∩B|+|B−A|=|A|−|A∩B|+|A∩B|+|A|−|A∩B|=|A|+|B|−|A∩B|
Ex: Dentre 4689 estudantes, 2112 cursaram pelo menos 60 créditos e 2678 cursaram no máximo 60
créditos. Quantos deles cursaram exatamente 60 créditos?
Se A denota o conjunto dos alunos que cursaram pelo menos 60 créditos e B denota o conjunto dos
alunos que cursaram no máximo 60 créditos, então temos:
|A∪B| : número total de estudantes = 4689
|A| = 2112
|B| = 2678
Pelo princípio da inclusão-exclusão, temos:
|A∪B|=|A|+|B|−|A∩B|
4689 = 2112 + 2678 - |A∩B|
|A∩B| = 2112 + 2678 – 4689 = 4790 – 4689 = 101 estudantes
Princípio da inclusão-exclusão para 3 conjuntos
Podemos generalizar o princípio anterior para o caso de 3 conjuntos: A, B e C.
Mas como podemos calcular o número de elementos de |A∪B∪C| ?
O diagrama a seguir nos ajuda a visualizar todos osconjuntos envolvidos.
Note que temos 7 conjuntos disjuntos, que são:
A – (B∪C)
B – (A∪C)
C – (A∪B)
(A ∩B)−C
(B∩C)−A
(A∩C)−B
A∩B∩C
Assim, podemos expressar a união de A, B e C como:
A∪B∪C=(A – (B∪C))∪(B – (A∪C))∪(C – (A∪B))∪((A∩B)−C)∪((B∩C)−A )∪((A∩C)−B)∪(A∩B∩C )
o que nos leva a:
|A∪B∪C|=|A – (B∪C )|+|B – (A∪C)|+|C – (A∪B)|+|(A∩B)−C|+|(B∩C)−A|+|(A∩C )−B|+|A∩B∩C|
Calculando o número de elementos em cada um dos 7 conjuntos disjuntos, temos:
|A – (B∪C)|=|A|−|A∩B|−|A∩C|+|A∩B∩C|
|B – (A∪C)|=|B|−|A∩B|−|B∩C|+|A∩B∩C|
|C – (A∪B)|=|C|−|A∩C|−|B∩C|+|A∩B∩C|
|(A∩B)−C|=|A∩B|−|A∩B∩C|
|(B∩C)−A|=|B∩C|−|A∩B∩C|
|(A∩C)−B|=|A∩C|−|A∩B∩C|
|A∩B∩C|=|A∩B∩C|
Somando tudo, chegamos finalmente a:
|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|
Ex: Um total de 1232 estudantes cursaram Espanhol, 879 cursaram Francês e 114 cursaram Russo.
Além disso, 103 cursaram Espanhol e Francês. 23 cursaram Espanhol e Russo, e 14 cursaram
Francês e Russo. Se 2092 cursaram pelo menos um dos 3 cursos, quantos cursaram os 3 cursos?
|E∪F∪R|=|E|+|F|+|R|−|E∩F|−|F∩R|−|E∩R|+|E∩F∩R|
Desejamos calcular |E∩F∩R|
|E∩F∩R|=|E∪F∪R|−|E|−|F|−|R|+|E∩F|+|F∩R|+|E∩R|
|E∩F∩R|=2092−1232−879−114+103+23+14=7
Portanto, apenas 7 alunos cursaram os 3 cursos.
A esta altura, já é possível observarmos um padrão: a fórmula possui 2n – 1 termos, onde n é o
número de conjuntos. Para n = 2, tivemos 3 termos na equação, para n = 3 tivemos 7 termos na
equação. Note que 2n – 1 é exatamente o número máximo de subconjuntos disjuntos que podem ser
descritos quando temos n conjuntos. Outro padrão que pode ser observado consiste na soma e
subtração de elementos: os termos envolvendo uma quantidade ímpar de intersecções de conjuntos
devem ser somados, enquanto os termos envolvendo uma quantidade par de interseções de
conjuntos devem ser subtraídos. Sendo assim, podemos desenvolver uma fórmula para calcular a
quantidade de elementos na união de 4 conjuntos.
Princípio da inclusão-exclusão para n = 4
Note que para n = 4 conjuntos, podemos ter até 15 subconjuntos disjuntos, conforme indicado nas
figuras a seguir.
 
 
Note que há 2 subconjuntos ocultos aqui
AC e BD (devido ao desenho não estão
totalmente visíveis, mas podem existir)
Dessa forma, a fórmula para esse caso fica:
O teorema a seguir generaliza o princípio da inclusão-exclusão para um número n arbitrário de
conjuntos.
Teorema: Sejam A1 , A2 , ... , An conjuntos finitos. Então:
Uma prova por indução para esse resultado pode ser encontrada em:
https://faculty.math.illinois.edu/~nirobles/files453/iep_proof.pdf
Def: Sejam A1 , A2 , ... , An conjuntos. Dizemos que eles são mutualmente disjuntos se:
∀ i , j A i∩A j=∅ para i , j∈{1 , 2 ,... , n } (não há intersecção entre nenhum par)
Def: Uma coleção de conjuntos não vazios é uma partição de A, se e somente se:
a) (a união das partições é igual a todo conjunto A)
b) ∀ i , j∈{1,2 ,... , n } A i∩A j=∅ (os conjuntos são mutualmente disjuntos)
https://faculty.math.illinois.edu/~nirobles/files453/iep_proof.pdf
Ex: Seja N o conjunto dos naturais e sejam:
T 0={n∈N :∃k∈N /n=3 k }
T1={n∈N :∃k∈N /n=3 k+1 }
T2={n∈N :∃k∈N /n=3 k+2 }
A coleção {T 0 ,T 1 ,T 2} é uma partição de N? Justifique sua resposta.
Note que:
T 0 é o subconjunto dos naturais múltiplos de 3, ou seja, n mod 3 = 0
T1 é o subconjunto dos naturais tais que n mod 3 = 1 (sobra resto 1)
T2 é o subconjunto dos naturais tais que n mod 3 = 2 (sobra resto 2)
Sendo assim, T 0∩T 1=∅ , T1∩T2=∅ e T 0∩T 2=∅
Além disso, T 0∪T1∪T2=N
Portanto, temos uma partição válida dos naturais.
Def: Dado um conjunto A, o conjunto potência de A, denotado por 2A ou P(A), é o conjunto de
todos os subconjuntos de A.
Ex: A = {1, 2, 3}
2|A|={∅ ,{1 },{2}, {3 }, {1 , 2}, {1 ,3 },{2 ,3 },{1 ,2 ,3 }}
Note que |2A|=2|A|
Def: Dados conjuntos A1 , A2 , ... , An o produto cartesiano, denotado por A1×A2×...×An , é o
conjunto de todas as n-tuplas ordenadas em que a1∈A1 , a2∈A2 , …, an∈An , ou seja:
A1×A2×...×An={(a1 , a2 ,... , an): a1∈A1 , a2∈A2 ,... , an∈An } 
Em particular, no caso de n = 2, temos pares ordenados:
A×B={(a , b): a∈A∧b∈B }
Observação: note que o produto cartesiano não é comutativo! A ordem dos conjuntos altera sim o
produto.
Ex: Seja A1 = {x, y}, A2 = {1, 2, 3} e A3 = {a, b}
a) Encontre A1×A2 
A1 x A2 = {(x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3)}
b) Encontre A1×A2×A3
A1 x A2 x A3 = {(x, 1, a), (x, 1, b) (x, 2, a), (x, 2, b), (x, 3, a), (x, 3, b), 
 (y, 1, a), (y, 1, b) (y, 2, a), (y, 2, b), (y, 3, a), (y, 3, b)}
Note que o número de elementos em A1 x A2 x A3 é |A1| x |A2| x |A3|
Propriedades de conjuntos
A seguir veremos propriedades de subconjuntos.
a) ∀ A , B A∩B⊆A∧A∩B⊆B (inclusão da intersecção)
b) ∀ A , B A⊆A∪B∧B⊆A∪B (inclusão da união)
c) ∀ A , B ,C (A⊆B∧B⊆C)→ A⊆C (transitividade do operador “está contido”)
Identidades
 
1. Leis comutativas da união e intersecção
∀ A , B(A∪B=B∪A)∧(A∩B=B∩A)
2. Leis associativas da união e intersecção
∀ A , B ,C ((A∪B)∪C=A∪(B∪C ))
∀ A , B ,C ((A∩B)∩C=A∩(B∩C ))
3. Leis distributivas da união e intersecção
∀ A , B ,C (A∪(B∩C )=(A∪B)∩(A∪C))
∀ A , B ,C (A∩(B∪C )=(A∩B)∩(A∩C))
4. Leis da identidade
∀ A , A∪∅=A
∀ A , A∩U=A
5. Leis da complementaridade
A∪A=U
A∩A=∅
A=A
6. Leis de De Morgan
a) A∩B=A∪B
b) A∪B=A∩B
Iremos provar o item a). Para isso, temos que mostrar que os conjuntos A∩B e A∪B são
idênticos. Lembre que dois conjuntos A e B são iguais se e somente se A⊆B∧B⊆A .
Parte 1:
i. Suponha x∈A∩B (arbitrário)
ii. Então, x∉A∩B
iii. Para não estar na interseção, pode estar em A ou B mas não em ambos:
x∉A∨x∉B
iv. Sendo assim, x∈A∨x∈B
v. Portanto, x∈A∪B
 
Como x∈A∩B→x∈A∪B , temos que A∩B⊆A∪B (I)
Parte 2: 
i. Suponha y∈A∪B (arbitrário)
ii. Então, y∈A∨ y∈B 
iii. Assim, temos que y∉A∨ y∉B
iv. Se y não está em A ou não está em B, ele não pode estar em A e B simultaneamente:
y∉A∩B
v. Portanto, y∈A∩B
Como y∈A∪B→A∩B , temos que A∪B⊆A∩B (II)
Portanto, de I e II concluímos que A∩B=A∪B .
Uma prova similar pode ser feita para demonstrar a validade do item b) Deixaremos a cargo do
leitor efetuar tal procedimento.
7. Leis da absorção
∀ A , B A∪(A∩B)=A
∀ A , B A∩(A∪B)=A
8 Lei da diferença
∀ A , B A−B=A∩B
Para demonstrar essa lei basta lembrar que: 
A−B={x : x∈A∧x∉B }={x : x∈A∧x∈B }=A∩B
Teorema: Lei de De Morgan generalizada
 para n > 1
A proposição P(k) pode ser expressa como:
P(k ) : A1∩A2∩...∩Ak=A1∪A2∪...∪Ak
BASE: P(2): A1∩A2=A1∪A2 (já provado anteriormente) - OK
PASSO DE INDUÇÃO: Para k arbitrário, P(k) → P(k+1)
Note que P(k+1) pode ser escrita como:
Mas pela Lei de De Morgan para n = 2 (já provada), temos:
Pela hipótese indutiva, o primeiro termo da união pode ser reescrito como:
o que conclui a prova.
Ex: Utilizando as leis da teoria dos conjuntos, prove as seguintes identidades:
a) A−(A∩B)=A−B
A−(A∩B)=A∩A∩B=A∩(A∪B)=(A∩A)∪(A∩B)=∅∪(A∩B)=A∩B=A−B
b) (A∪B)−C=(A−C)∪(B−C)
(A∪B)−C=(A∪B)∩C=(A∩C )∪(B∩C)=(A−C)∪(B−C)
c) A∪(B−C)=(A∪B)−(C−A)
A∪(B−C)=A∪(B∩C)=(A∪B)∩(A∪C)=(A∪B)−(A∪C)=(A∪B)−(A∩C )=
=(A∪B)−(C∩A)=(A∪B)−(C−A )
Ex: Mostre que a diferença simétrica entre A e B pode ser expressa como a diferença entre a união 
de A e B e a intersecção de A e B.
Sabemos que a diferença simétrica é definida como:
A⊖B=(A−B)∪(B−A)
Pela lei da diferença, temos:
A⊖B=(A∩B)∪(B∩A)
Aplicando a lei distributiva:
A⊖B=(A∪B)∩(A∪A)∩(B∪B)∩(B∪A)
Pelas leis do complemento, temos:
A⊖B=(A∪B)∩U∩U∩(B∪A )
Aplicando a lei da identidade:
A⊖B=(A∪B)∩(B∪A)
Pela lei da diferença, temos:
A⊖B=(A∪B)−(B∪A)
Pela lei de De Morgan, podemos escrever:
A⊖B=(A∪B)−(B∩A)=(A∪B)−(A∩B)
finalizando a prova.
Mathematics is merely the etherealization of common sense.
― Lord Kelvin 
Aula 4: Relações
Uma relação é uma estrutura matemática discreta muito importante para a computação, pois nos
permite modelar diversos conceitos abstratos utilizados em várias de suas subáreas, como bancos de
dados relacionais, grafos e redes, teoria de autômatos e linguagens formais. Nesta aula,
apresentamosuma introdução às relações binárias, discutindo suas principais propriedades, em
particular a reflexividade, a simetria e a transitividade. Além disso, demonstramos alguns resultados
importantes com o auxílio de casos ilustrativos, como por exemplo o teorema que nos diz que em
uma relação transitiva R, a operação de composição com si mesma sempre retorna uma relação R'
contida em R. 
Def: Relação binária
Sejam A e B conjuntos quaisquer. Uma relação binária de A em B é qualquer subconjunto do
produto cartesiano A×B .
Por exemplo, sejam A = {0, 1, 2} e B = {a, b}. Então, R = {(0, a), (0, b), (1, a), (1, b)} é uma
relação binária de A em B. Introduziremos aqui uma notação para indicar a pertinência de um par
ordenado em uma relação R. Para dizer que o par (a, b) pertence a relação R, escrevemos:
(a , b)∈R≡aRb
Def: Domínio e imagem
dom(R)={a:∃b , aRb }
img(R)={b :∃a , aRb}
Def: Endorrelação
É uma relação binária definida em A×A
Def: Relação inversa de R
R−1={(x , y) : yRx } (basta inverter todos os pares ordenados)
Ex: Seja A = {1, 2, 3, 4, 5, 6} e B = {1, 2, 3, 4}. Defina R = {(a, b): (a – b) mod 2 = 0} de A em B.
R = {(1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4), (5, 1), (5, 3), (6, 2), (6, 4)}
Note que os pares (5, 5) e (6, 6) não pertencem a relação!
Eles deveriam aparecer apenas se a relação fosse definida de A em A.
Ex: Seja A = {1, 2 ,3, 4}. Defina R como a relação binária de A em A a seguir:
aRb ⇔ a divide b
Uma pergunta interessante que surge neste momento é: quantas relações binárias de A em A existem
em um conjunto de n elementos A = {1, 2, 3…, n}?
Se R⊆A×A , então temos que o produto cartesiano terá |A×A|=n2 elementos
Lembrando do conjunto potência, definido como o conjunto de todos os subconjuntos, em que o
número de elementos é dado por |2R|=2|R| e como |R|≤n2 , temos que no máximo
|2R|=2|R|=2n
2
 (dois elevado a n2). Por exemplo, um simples conjunto A = {1, 2, 3, 4, 5} admite
até 225 relações distintas!
Considere o caso mais simples em que A = {1, 2}. Então, é claro que o produto cartesiano de A com
ele mesmo é definido como:
A×A={(1 ,1) ,(1 ,2) ,(2 ,1) ,(2 ,2)} 
e por isso tem 4 elementos. Quantos subconjuntos distintos podemos formar com apenas esses 4
pares ordenados? Esse será o número de possíveis relações de A em A. O conjunto potência de
A×A terá 24 = 16 elementos, portanto termos 16 possíveis relações binárias (incluindo a
relação vazia que não associa nenhum elemento com nenhum outro).
Propriedades de relações
Assim como outros objetos matemáticos, podemos listar diversas propriedades de relações binárias.
A seguir apresentamos algumas das principais delas.
D ef: Relação reflexiva
Seja A um conjunto qualquer e R⊆A×A uma relação binária. Dizemos que R é reflexiva se:
∀ x∈A , xRx
Ex: Seja A = {1, 2, 3} e as relações a seguir:
R1 = {(1, 2), (2, 2), (3, 1), (3, 3)}
R2 = {(1, 1), (2, 1), (2, 2), (3, 2), (3, 3)}
Ambas são exemplos de relações reflexivas.
Dizemos que uma relação é irreflexiva se ∀ x∈A ,(a , a)∉R (não pode haver nenhum par x, x)
Def: Relação simétrica
Seja A um conjunto qualquer e R⊆A×A uma relação binária. Dizemos que R é simétrica se:
∀ x , y∈A(xRy→ yRx)
Dizemos que R é anti-simétrica se:
∀ x , y∈A((xRy∧ yRx)→ x= y )
Ex: Considere as relações a seguir definidas em A = {1, 2, 3, 4}.
R1 = {(1, 1), (1, 2), (2, 1)} simétrica
R2 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)} simétrica
R3 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)} anti-simétrica
Note que existe (2, 1), retorna V, mas como não existe (1, 2) temos F e a conjunção (AND) no
antecedente da definição da propriedade antisimétrica resulta em V∧F=F . O resultado de uma
implicação é sempre V quando o antecedente é F (não importa o consequente). Esse mesmo
raciocínio vale para os pares (3, 1), (3, 2), (4, 1), (4, 2) e (4, 3). 
Suponha agora que a relação R3 fosse a seguinte:
R = {(2, 1), (2, 3), (3, 2), (4, 1), (4, 2), (4, 3)}
Os pares (2, 3) e (3, 2) ferem a propriedade anti-simétrica. Portanto, a relação não seria nem
simétrica, nem anti-simétrica. Alguns autores a chamam de assimétrica.
R4 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)} anti-simétrica
R5 = {(3, 4)} anti-simétrica
Outra forma de entender a propriedade anti-simétrica é a partir da contrapositiva:
x≠ y→(xRy∧ yRx)
Para dois elementos distintos de A, x e y, não pode aparecer xRy e yRx.
Seja A = {1, 2, 3}. O que podemos dizer da relação R = {(3, 3)}?
Note que R é simétrica (pois o par inverso de (3, 3) é igual a ele mesmo) e também anti-simétrica, 
Esse é um exemplo que mostra que é possível uma relação ser simétrica e anti-simétrica ao mesmo
tempo.
Teorema: Seja R uma relação binária qualquer em A. Se R é simétrica, então a relação inversa R -1
também é simétrica.
1. Sejam x , y∈A arbitrários, tal que xRy.
2. Como R é simétrica, então yRx
3. De xRy e yRx, temos xR-1y e yR-1x
4. Portanto, R-1 é simétrica
Def: Relação transitiva
Seja A um conjunto qualquer e R⊆A×A uma relação binária. Dizemos que R é transitiva se:
∀ x , y , z∈A ((xRy∧ yRz)→ xRz)
Ex: Considere as relações a seguir definidas em A = {1, 2, 3, 4}. 
R1 = {(1, 1), (1, 2), (2, 1)} não é transitiva - falta (2, 2)
R2 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)} não é transitiva - falta (4, 2)
R3 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)} transitiva
R4 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)} transitiva
R5 = {(3, 4)} transitiva (por vacuidade)
Em R5, o antecedente da implicação é sempre F, portanto a implicação é sempre V.
Ex: Considere as seguintes relações binárias definidas no conjuntos dos inteiros (Z):
R1={(x , y ): x≤ y }
R2={(x , y ) :x> y }
R3={(x , y ) : x= y∨x=− y }
R4={(x , y ): x= y }
R5={(x , y ) : x= y+1}
R6={(x , y) : x+ y≤3 }
a) Quais delas são reflexivas?
R1 pois ∀ x∈Z , x≤ x
R3 e R4 são trivialmente reflexivas
b) Quais delas são simétricas?
R3 pois (x = y ou x = -y) → (y = x ou y = -x)
R4 pois x = y → y = x
R6 pois (x+ y≤3)→( y+x≤3)
c) Quais delas são anti-simétricas?
R1 pois ((x≤ y)∧( y≤x ))→ x= y
R2 por vacuidade pois (x < y) and (y < x) é sempre F.
R4 pois ((x = y) and (y = x)) → x = y
R5 por vacuidade pois (x = y + 1) and (y = x + 1) é sempre F.
d) Quais delas são transitivas?
R1 pois (x≤ y∧ y≤z)→ x≤z
R2 pois (x> y∧ y>z )→x>z
R3 pois (x=± y∧ y=±z )→x=±z
R4 pois (x= y∧ y=z)→ x=z
Note que R5 não é transitiva pois 2R1 e 1R0 mas (2,0)∉R
Note que R6 não é transitiva pois 2R1 e 1R2 mas (2,2)∉R
Ex: Seja A = {1, 2, 3, 4} e R = {(1, 1), (2, 3), (2, 4), (3, 3), (3, 4)}.
Pergunta-se:
a) R é reflexiva? Não, pois (2 ,2)∉R
b) R é irreflexiva: Não, pois 1R1 e 3R3
c) R é simétrica? Não, pois 2R3 mas (3,2)∉R
d) R é anti-simétrica? Sim, pois para a≠b não temos aRb∧bRa
e) R é transitiva? Sim, pois sempre que aRb∧bRc temos aRc
Composição de relações
Def: Sejam R e S relações arbitrárias. A composição de R com S denotada por S∘R é definida
por:
S∘R={(a ,c) :∃b(aRb∧bRc)}
Ex: Sejam as relações a seguir:
R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)}
S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}
Calcule a composição de R com S (primeiro aplica R e depois S).
S∘R=(1,0) ,(1,1) ,(2,1) ,(2,2) ,(3,0) ,(3,1)
Representação gráfica
Note que a composição de S com R é dada por:
R∘S={(3,1) ,(3,4 ),(3,3) ,(4,1) ,(4,4)}
e portanto a operação composição não é comutativa, ou seja, em geral, S∘R≠R∘S .
Duas observações importantes são:
dom(S∘R)⊆dom R
img(S∘R)⊆img(S)
Def: Para toda relação binária R de A em B existem as relações identidades IA e IB que são as
menores relações reflexivas definidas nesses conjuntos, tais que R∘ I A=I b∘R=R .
Ex: Sejam A = {1, 2, 3}, B = {10, 20, 30, 40} e R = {(1, 20), (1, 30), (2, 30)}.
Então as relações identidade são:
IA = {(1, 1), (2, 2), (3, 3)}
IB = {(10, 10), (20, 20), (30, 30), (40, 40)}
Sendo assim, note que:
R∘ I A={(1, 20) ,(1 ,30) ,(2 , 30)}=R
I B∘R={(1,20) ,(1 ,30) ,(2 ,30)}=R
Def: Composição com a relação inversa
Seja R uma relação binária em A. Ao contrário do que ocorre com funções, como veremos mais
adiante no curso, a composição de R com sua inversa R-1 em geral não resulta na identidade.
Ex: A = {1, 2, 3}
R = {(1, 2), (1, 3), (2, 3)}
R-1 = {(2, 1), (3, 1), (3, 2)}
IA = {(1, 1), (2, 2), (3, 3)}
Note que as duas composições possíveis são dadas por:
R−1∘R={(1,1),(1,2) ,(2,1),(2,2)}≠I A
R∘R−1={(2,2),(2,3) ,(3,2) ,(3,3)}≠I A
Portanto, R−1∘R≠R ∘R−1≠I A
Teorema: Sejam R e S duas relações binárias em A. Então, (S∘R)−1=R−1∘S−1
Prova:
1. Suponha ( y , x )∈(S∘R)−1 arbitrário
2. Então, (x , y )∈S∘R
3. Pela definição da composição de duas relações, temos: ∃z / xRz∧zRy
4. Dessa forma, (z , x )∈R−1 e ( y , z )∈S−1
5. Novamente, pela composição de duas relações: ( y , x )∈R−1∘S−1
Def: Seja R uma relação em A. As potências Rn, para n = 1, 2, …, n, são definidas recursivamente:
 R1 = R 
Rn+1=Rn∘R
ou seja
R2=R ∘R , R3=R2 ∘R=(R∘R)∘R , …
Ex: Seja R = {(1 ,1), (2, 1), (3, 2), (4, 3)}. Encontre Rn, para n = 2, 3, 4, …
R2=R ∘R={(1,1) ,(2,1) ,(3,1) ,(4,2)}
R3=R2 ∘R={(1,1) ,(2,1) ,(3,1) ,(4,1)}
R4=R3∘R={(1,1) ,(2,1) ,(3,1) ,(4,1)}
R5=R4∘R={(1,1) ,(2,1) ,(3,1) ,(4,1)}
…
Rn = R3, para n > 3.
Veremos a seguir um resultado muito importante que relaciona a propriedade transitiva com a
operação de composição.
Teorema: Seja R uma relação binária em A. R é transitiva se e somente se R∘R⊆R
Em outras palavras, o que esse teorema nos diz é que se R é transitiva, ao compor ela com ela
mesma, sempre obtenho uma relação com o mesmo número ou menos de pares ordenados.
Para provar que R2⊆R devemos mostrar que se (x , y )∈R2 , então (x , y )∈R
Prova:
Parte 1 (ida): R é transitiva → R2⊆R
1. Seja (x , y )∈R ∘R
2. Pela definição de composição, temos ∃z∈A/ xRz∧zRy
3. Mas como R é transitiva, ∀ x , y , z∈A (xRy∧ yRz)→ xRz
4. Portanto, (x , y )∈R
Parte 2 (volta): R2⊆R → R é transitiva
1. Sejam x , y , z∈A arbitrários
2. Suponha que xRz∧zRy
3. Pela definição de composição, temos que (x , y )∈R ∘R
4. Como pela hipótese R2⊆R , temos que xRy
5. Logo, R é transitiva
Na realidade, o teorema anterior pode ser generalizado para um n arbitrário, ou seja, ao continuar
compondo uma relação transitiva com ela mesma, o número de pares ordenados tende a diminuir
ainda mais.
Teorema: Seja R uma relação binária em A. R é transitiva se e somente se Rn⊆R para qualquer n
maior que zero
Prova:
Parte 1 (ida): R é transitiva → Rn⊆R
Supor R transitiva e provar que Rn⊆R , para qualquer n > 0.
Utilizar indução em n
BASE: n = 1, R⊆R (OK)
PASSO DE INDUÇÃO: Supor Rk⊆R para k > 0 e mostrar que Rk+1⊆R
1. Seja (x , y )∈Rk+1 arbitrário
2. Então, (x , y )∈R k∘R
3. Pela definição de composição, ∃z∈A/ xRz∧zRk y
4. Note que pela hipótese de indução, Rk⊆R , e portanto zRy
5. Como R é transitiva e temos xRz∧zRy , então temos xRy
A prova está concluída, pois acabamos de mostrar que xRk+1y → xRy, o que significa que Rk⊆R
Parte 2 (volta): Rn⊆R para qualquer n > 0 → R é transitiva
A prova é trivial, pois já que a hipótese Rn⊆R vale para todo n, basta tomarmos n = 2 e invocar
o teorema anterior já demonstrado. A prova está completa.
A seguir estudaremos os fechamentos de uma relação. Eles são importantes pois definem a menor
relação que contém R e possuem a propriedade especificada pelo fecho (reflexivo, simétrico,
transitivo, etc.)
Def: Fecho reflexivo
Seja R uma relação binária em A. Se R não é reflexiva, então ∃x∈A /( x , x)∉R . Se
acrescentarmos todos esses pares (x, x) faltantes a R, obtemos a menor relação reflexiva que contém
R, a qual denominamos de fecho reflexivo de R.
Ex: Sejam A = {a, b, c} e R = {(a, a), (a, b), (b, a), (c, b)}. Obtenha o fecho reflexivo R’ de R.
Pela definição, é trivial que 
R’ = {(a, a), (a, b), (b, a), (b, b), (c, b), (c, c)}
Def: Fecho simétrico
Seja R uma relação binária em A. O fecho simétrico de R é a menor relação simétrica que contém
R. É a relação R’ obtida acrescentando a R todos os pares necessários para torná-la simétrica.
Ex: Sejam A = {a, b, c} e R = {(a, a), (a, b), (b, b), (b, c), (c, a), (c, b)}
Pela definição, o fecho simétrico é dado por:
R’ = {(a, a), (a, b), (a,c), (b, a), (b, b), (b, c), (c, a), (c, b)}
Def: Fecho transitivo
Seja R uma relação binária em A. O fecho transitivo de R é a menor relação transitiva que contém
R. Porém, ao contrário dos fechos reflexivos e simétricos, não é tão trivial encontrá-lo. A seguir
iremos discutir o porque disso.
Podemos examinar todos os pares (x, y) e (y, z) que pertencem a R. Note porém que isso não é
suficiente. Considere A = {1, 2, 3, 4} e a relação R = {(1, 2), (2, 3), (3, 4)}.
É fácil ver que R não é transitiva, uma vez que:
1R2 e 2R3 mas (1,3)∉R
2R3 e 3R4 mas (2,4)∉R
Assim, acrescentando esses dois pares a R temos a relação R’ a seguir:
R’ = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)}
Porém, note que R’ ainda não é transitiva pois 1R3 e 3R4 mas (1,4)∉R ' .
Finalmente, acrescentando o par (1, 4) em R’, temos a relação R’’ dada por:
R’ = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}
que é transitiva.
Note que os pares que faltam em R são da forma (x, y) tal que existe z para o qual (x, z) e (z, y). Ou
seja são exatamente os pares de R2=R ∘R . Ao adicionarmos esses pares, estamos construindo a
relação R '=R∪R2 .
Da mesma forma, os pares que faltam em R’ estão em R '∘R '=(R∪R2)2 . Note que:
(R∪R2)2=(R∪R2)∘(R∪R2)=(R∘R)∪(R ∘R2)∪(R2 ∘R)∪(R2 ∘R2)=R2∪R3∪R4
Assim, acrescentando esses pares a R’, temos a relação R’’ dada por:
R ' '=R '∪(R2∪R3∪R4)=R∪R2∪R3∪R4
Continuando o processo, note que os pares que faltam a R’’ estão em R ' '∘R ' ' . Pelo mesmo
procedimento anterior, podemos verificar que:
R ' '∘R ' '=R∪R 2∪R3∪...∪R8
Por essa razão, o fecho transitivo R, denotado por R*, é definido como a união de todas as potencias
de R, ou seja:
Em outras palavras, (a ,b)∈R* se e somente se existe k > 0, tal que (a , b)∈R k .
Pode-se mostrar que se A = {1, 2, 3, …, n} (conjunto é finito), o processo termina com o termo Rn
no máximo (pode ser até antes). Caso o conjunto A seja infinito (enumerável), o processo pode
nunca ter fim (problema intratável).
A pergunta que surge é: mas quem garante que a relação R* construída dessa forma é de fato
transitiva? O teorema a seguir nos prova essa afirmação.
Teorema: Seja R uma relação binária em A. Para qualquer que seja R (arbitrária), a relação R* é
transitiva.
Prova:
1. Sejam x, y, z elementos tais que (x , y )∈R* e ( y , z )∈R*
2. Desejamos provar que (x , z )∈R*
3. Pela definição de fecho transitivo R*, temos que ∃i , j>0 /(x , y )∈Ri∧( y , z)∈R j
4. Assim, (x , z )∈R j∘Ri=R i+ j , que é uma das componentes de R*, uma vez que:
R*=R∪R2∪...∪R i∪...∪R j∪...∪R i+ j∪...
5. Portanto, (x , z )∈R*
A seguir, iremos demonstrar que de fato o fecho transitivo R* é a menor relação transitiva que
contém R. Em outras palavras, não existe nenhum par supérfluo em R*. Para isso, usaremos alguns
resultados importantes.
Def: Para quaisquer relações R1, R2, S1, S2 se R1⊆R2 e S1⊆S2 então R1∘S1⊆R2∘S2 .
Essa propriedade é intuitiva, uma vez que se fizermos a composição de duas relações com poucos
pares ordenados, a relação resultante será composta por um número reduzido de pares ordenados.
Teorema: Para quaisquer relações binárias R e S e n > 0 arbitrário, se R⊆S , então Rn⊆Sn .
Prova (por indução):
BASE: Para n = 1, R⊆S (OK)
PASSO DE INDUÇÃO: Supor que Rk⊆Sk para k arbitrário e mostrar que Rk+ 1⊆Sk+1 .
1. Como R⊆S , sabemos que Rk⊆Sk .
2. Pela propriedade anterior, então Rk∘R⊆Sk ∘S
3. Pela definição de conjunto potencia, temos Rk+ 1⊆Sk+1
Teorema: Para qualquer relação R, toda relação transitiva S que contém R, contém o fecho
transitivo R* de R. Em outras palavras, R* é a menor relação que contém R e é transitiva.
Prova:
1. Seja R uma relação qualquer tal que R⊆S , onde S é uma relação transitiva
2. Pelo teorema anterior, ∀n>0 temos que Rn⊆Sn
3. Como S é transitiva,Sn⊆S e assim Rn⊆S para todo n.
4. Uma vez que todo termo individual Rn, n = 1, 2, … está contido em S, a união de todos eles, que
é justamente a definição de R*, também está.
“The beauty of mathematics only shows itself to more patient followers”
Maryam Mirzakhani
Aula 5: Relações de equivalência
Assim como diversos objetos matemáticos, relações podem ser categorizadas de acordo com suas
propriedades básicas. Dentre as classes de relações mais conhecidas que existem, podemos destacar
as relações de equivalência. Relações de equivalência são importantes, pois elas induzem uma
partição no conjunto A em classes de equivalência, o que é uma característica desejada para
diversos modelos abstratos presentes na fundamentação teórica na computação.
Def: Relação de equivalência
Seja R uma relação binária em A. R é uma relação de equivalência se é reflexiva, simétrica e
transitiva. Em uma relação de equivalência R, se aRb, a é equivalente a b, ou simplesmente a ~ b.
Ex: Frações equivalentes
Seja o conjunto S definido como:
S={ xy : x , y∈Z , y≠0}
Defina a relação binária R⊆S×S como:
x
y
R
z
w
⇔xw= yz
Por exemplo, temos que:
1
2
R
2
4
 pois 2×2=4×1
2
3
R
4
6
 pois 2×6=3×4
Prove que R é uma relação de equivalência.
1. Reflexiva: note que 
x
y
R
x
y
 uma vez que xy = yz. (OK)
2. Simetria: suponha 
x
y
,
z
w
∈S tal que 
x
y
R
z
w
 . Então, xw = yz. Mas como a ordem dos
fatores não altera o produto, zy = wx, o que nos leva a 
z
w
R
x
y
 (OK)
3. Transitividade: suponha 
x
y
,
z
w
,
p
q
∈S tal que 
x
y
R
z
w
∧
z
w
R
p
q
. Note que devemos ter
necessariamente xw = yz e zq = wp. Usando a substituição x=
yz
w
 , podemos calcular xq como
xq=
yzq
w
. Mas zq = wp e assim temos xq=
ywp
w
= yp , o que implica em 
x
y
R
p
q
 (OK)
Portanto, R é uma relação de equivalência.
Def: Seja R uma relação de equivalência em A. Para todo x∈A , o conjunto:
[a]R=x∈A : xRa (conjunto de todos os x que se relacionam com a)
é denominado classe de equivalência de a. 
Ex: Congruência em módulo 3
Seja o conjunto A = {-2, -1, 0, 1, 2, 3, 4} e R a relação definida como:
xRy⇔(a−b)mod 3=0 
Responda:
a) Escreva a relação como um conjunto finito de pares ordenados.
R = {(-2, -2), (-1, -1), (0, 0), (1, 1), (2, 2), (3, 3), (4, 4)
 (-2, 1), (-2, 4),
 (-1, 2),
 (0, 3),
 (1, -2), (1, 4), 
 (2, -1),
 (3, 0),
 (4, -2), (4, 1)}
Note que existem no total 17 pares ordenados na relação R.
b) Verifique que R é uma relação de equivalência.
i. Reflexiva: (-2, -2), (-1, -1), (0, 0), (1, 1), (2, 2), (3, 3), (4, 4) - OK
ii. Simétrica: (-2, 1) → (1, -2) OK
(-2, 4) → (4, -2) OK
(-1, 2) → (2, -1) OK
(0, 3) → (3, 0) OK
(1, 4) → (4, 1) OK
(2, -1) → (-1, 2) OK
iii. Transitividade: (-2, 1) e (1, -2) → (-2, -2) OK
(-2, 1) e (1, 4) → (-2, 4) OK
(-2, 4) e (4, -2) → (-2, -2) OK
(-2, 4) e (4, 1) → (-2, 1) OK
(-1, 2) e (2, -1) → (-1, -1) OK
(0, 3) e (3, 0) → (0, 0) OK
(1, -2) e (-2, 1) → (1, 1) OK
(1, -2) e (-2, 4) → (1, 4) OK
(1, -2) e (-2, 4) → (1, 4) OK
(1, 4) e (4, -2) → (1, -2) OK
(1, 4) e (4, 1) → (1, 1) OK
(2, -1) e (-1, 2) → (2, 2) OK
(3, 0) e (0, 3) → (3, 3) OK
(4, -2) e (-2, 1) → (4, 1) OK
(4, -2) e (-2, 4) → (4, 4) OK
(4, 1) e (1, -2) → (4, -2) OK
(4, 1) e (1, 4) → (4, 4) OK
Portanto, como R é reflexiva, simétrica e transitiva, temos que R é uma relação de equivalência.
c) Defina as classes de equivalência de R.
[-2]R = {-2, 1, 4}
[-1]R = {-1, 2}
[0]R = {0, 3}
[1]R = {1, -2, 4}
[2]R = {2, -1}
[3]R = {3, 0}
[4]R = {4, -2, 1}
Note que temos 3 classes de equivalência, sendo elas as seguintes:
- Classe de equivalência 1: elementos cujos módulos por 3 são zero - {0, 3}
- Classe de equivalência 2: elementos cujos módulos por 3 são um - {-2, 1, 4}
- Classe de equivalência 3: elementos cujos módulos por 3 são dois - {-1, 2}
OBS: Lembre se que há duas versões utilizadas em computação: remainder (rem) e modulo (mod).
A função remainder (que calcula simplesmente o resto) permite valores negativos e modulo retorna
valores estritamente não negativos.
Nos exemplos, estamos adotando modulo (mod) em que o retorno da função é sempre maior ou
igual a zero, cuja implementação em linguagem C é dada por:
int mod(int x, int m) {
 int r = x % m;
 return r < 0 ? r+m : r;
}
Dessa forma, temos que -1 mod 3 é calculado pelo retorno de mod(-1, 3)
O resto da divisão é negativo:
r = -1 % 3 = -1
Como r < 0, então, o valor de retorno será -1 + 3 = 2.
A seguir veremos um teorema que generaliza esse exemplo visto anteriormente.
Teorema: Seja m∈N /m>1 . A relação congruência em módulo m, dada por:
R={(x , y) :(x− y )mod m=0 }
é uma relação de equivalência no conjunto dos inteiros Z.
Prova:
Essa relação pode ser reescrita como: xRy⇔m divide (x− y )
1. Reflexiva: como x – x = 0 e zero é divisível por m, temos que xRx para todo x em Z.
2. Simétrica: suponha que m divida x – y, ou seja:
(x – y) = km
Multiplicando ambos os lados por -1, temos:
(y – x) = -km
Isso mostra que y – x também é múltiplo de m, ou seja m divide y – x.
Portanto, (y – x) mod m = 0 e R é simétrica.
3. Transitiva: suponha que m divida (x – y) e m divida (y – z). Então:
(x – y) = km
(y – z) = pm
Somando as duas identidades, chegamos em:
(x – z) = (k + p)m
Isso mostra que (x – z) também é múltiplo de m, ou seja, m divide (x – z).
Portanto, (x – z) mod m = 0 e R é transitiva.
Como R é reflexiva, simétrica e transitiva, temos que R é uma relação de equivalência.
Quantas e quais são as classes de equivalência de R?
Temos exatamente m classes de equivalência, que são:
[0]R – inteiros com resto 0
[1]R – inteiros com resto 1
[2]R – inteiros com resto 2
...
[m - 1]R – inteiros com resto m – 1
Teorema: Seja R uma relação de equivalência sobre um conjunto A. As seguintes informações são
equivalentes.
i. xRy
ii. [x]R = [y]R
iii. [x ]R∩[ y ]R≠∅
Primeiro, iremos provar que i. implica ii., ou seja: xRy → [x]R = [y]R
A ideia aqui consiste em mostrar que [x ]R⊆[ y ]R∧[ y ]R⊆[x ]R .
Parte I
1. Seja a∈[x ]R arbitrário. Então, por definição, temos aRx
2. Como R é relação de equivalência, por transitividade, (aRx∧xRy)→aRy
3. Assim, temos que a∈[ y ]R
4. Concluímos então que [x ]R⊆[ y ]R
Parte II
1. Seja a∈[ y ]R arbitrário. Então, por definição, temos aRy
2. Como R é relação de equivalência, por simetria, xRy → yRz
3. Como R é relação de equivalência, por transitividade, (aRy∧ yRx)→aRx
4. Assim, temos que a∈[x ]R
5. Logo, concluímos que [ y ]R⊆[ x ]R
Portanto, temos que [x]R = [y]R (os dois conjuntos são iguais)
Agora, iremos provar que [x]R = [y]R → [x ]R∩[ y ]R≠∅
1. Se [x]R = [y]R então [x ]R∩[ y ]R=[ x ]R∩[x ]R=[x ]R
2. Como R é reflexiva, temos xRx, ou seja, x∈[x ]R
3. Logo, [x ]R≠∅ e portanto [x ]R∩[ y ]R≠∅
Finalmente, iremos provar que [x ]R∩[ y ]R≠∅→ xRy
1. Como [x ]R∩[ y ]R≠0 , ∃a∈A /a∈[ x ]R∧a∈[ y ]R
2. Por definição das classes de equivalência, temos aRx e aRy
3. Como R é simétrica, temos aRx → xRa
4. Como R é transitiva, temos (xRa∧aRy)→xRy
O teorema anterior é um resultado muito importante pois nos garante que:
a) Como ∀ x∈A está em alguma classe de equivalência, a união das classes é igual a A:
b) Como [x ]R∩[ y ]R≠∅→ xRy e xRy→[x ]R=[ y ]R , temos que
[x ]R∩[ y ]R≠∅→[ x ]R=[ y ]R
Pela contrapositiva temos:
[x ]R≠[ y ]R→[x ]R∩[ y ]R=∅
ou seja, isso mostra que as classes de equivalência são disjuntas duas a duas. Portanto, a partir das
conclusões dos itens a) e b) acima, podemos enunciar o seguinte resultado.
Teorema: Seja A um conjunto e R uma relação de equivalência em A. Então, as classes de
equivalência de R formam uma partição de A.
Vamos mostrar a seguir que uma partição de um conjunto A pode ser utilizada para construir uma
relação de equivalência em A: dois elementos estão relacionados se e somente se estão no mesmo
bloco da partição.
Teorema: Seja P uma partição de A e seja S a relação 
S={(x , y) :∃C∈P /x∈C∧ y∈C }
Ou seja, xSy se e somente se x está no mesmo bloco que y. Então S é uma relação de equivalência e
suas classes de equivalênciassão os blocos da partição P.
Prova:
1. Note que S é reflexiva pois ∀a∈A ,aSa , pois todo a pertence a alguma partição.
2. Note que S é simétrica pois temos aSb se os elementos a, b pertencem a um mesmo bloco de P.
Logo, por definição, bSa, uma vez que b, a continuam pertencendo ao mesmo bloco de P.
3. Note que S é transitiva pois temos a seguinte situação: suponha aSb e bSc.
a. Então, existem blocos C e D em P tais que a ,b∈C∧b , c∈D
b. Logo, b∈C∩D
c. Como os blocos de P são disjuntos dois a dois, conclui-se que como |C∩D|>0 , C e D 
são na verdade o mesmo conjunto, ou seja C = D. Portanto, a e b pertencem ao mesmo bloco
Ex: Seja R uma relação sobre o conjuntos dos pares ordenados de inteiros positivos definida por:
(a, b) R (c, d) se e somente se a + d = b + c
a) Prove que R é uma relação de equivalência.
b) Descreva a classe de equivalência de (3, 1) segundo R (quem são os pares desse bloco).
c) Descreva as classes de equivalência de R.
What is mathematics? It is only a systematic effort of solving puzzles posed by nature.
— Shakuntala Devi
Aula 6: Relações de ordem parcial
Relações de ordem parcial (ROP’s) são estruturas discretas muito importantes no estudos de
conjuntos parcialmente ordenados (POSET’s). A intuição por trás de um conjunto parcialmente
ordenado é que desejamos comparar dois a dois os elementos desse conjunto, porém em alguns
casos essa comparação não é necessária ou possível, surgindo a noção de ordenação parcial. Essas
noções são fundamentais para a caracterização de estruturas abstratas estudadas na matemática e na
computação, como diagramas de Hasse e reticulados por exemplo.
Def: Relação de ordem parcial (ROP)
Seja A um conjunto e R uma relação binária em A. Dizemos que R é uma relação de ordem parcial
(ROP) se R é reflexiva, anti-simétrica e transitiva.
OBS: Note que a mudança de uma única propriedade faz com que a classe de relações de
equivalência seja diferente da classe de relações de ordem parcial.
Def: Conjunto parcialmente ordenado (POSET)
A tupla (A, R) em que R é uma relação de ordem parcial é um conjunto parcialmente ordenado.
Ex: Sejam A=ℜ (números reais) e a relação R={(x , y)∈A×A /x≤ y } . Prove que R é ROP
1. Reflexiva: ∀ x∈A ,x≤x (OK)
2. Anti-simétrica: ∀ x , y∈A((x≤ y∧ y≤x)→ x= y ) (OK)
3. Transitiva: ∀ x , y , z∈A ((x≤ y∧ y≤z )→x≤ z) (OK)
Como R satisfaz as três propriedades simultaneamente, R é relação de ordem parcial.
Ex: Seja A um conjunto finito e seja 2A o conjunto potência de A. Defina S como:
S={(X ,Y )∈2A×2A /X⊆Y }
Mostre que S é uma relação de ordem parcial.
1. Reflexiva: ∀ X∈2A , X⊆X (OK)
2. Anti-simétrica: ∀ X , Y∈2A((X⊆Y∧Y⊆X)→ X=Y ) (OK)
3. Transitiva: ∀ X , Y , Z∈2A((X⊆Y∧Y⊆Z)→X⊆Z ) (OK)
Como R satisfaz as três propriedades simultaneamente, R é relação de ordem parcial. Assim, a tupla
(2A ,⊆) representa um conjunto parcialmente ordenado (POSET). Veremos mais adiante como
representar graficamente POSET’s através de um digrama de Hasse.
Ex: Seja A = {1, 2, 3} e a relação R em 2A dada por: XRY⇔X⊆Y . Defina os pares ordenados
que compõem R.
Ex: Seja A = {1, 2, 3, 4, 6, 12} e R a relação binária em A dada por: xRy⇔ x divide y .
a) Define os pares ordenados que compõem R. 
R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 6), (1, 12),
(2, 2), (2, 4), (2, 6), (2, 12),
(3, 3), (3, 6), (3, 12),
(4, 4), (4, 12),
(6, 6), (6, 12),
(12, 12)}
b) R é uma relação de equivalência? Prove sua resposta.
i. Reflexiva: (1, 1), (2, 2), (3, 3), (4, 4), (6, 6), (12, 12)
ii. Anti-simétrica: (1, 2) mas não (2, 1)
(1, 3) mas não (3, 1)
(1, 4) mas não (4, 1)
(1, 6) mas não (6, 1)
(1, 12) mas não (12, 1)
(2, 4) mas não (4, 2)
(2, 6) mas não (6, 2)
(2, 12) mas não (12, 2)
(3, 6) mas não (6, 3)
(3, 12) mas não (12, 3)
(4, 12) mas não (12, 4)
(6, 12) mas não (12, 6)
iii. Transitiva: (1, 2) e (2, 4) → (1, 4)
(1, 2) e (2, 6) → (1, 6)
(1, 2) e (2, 12) → (1, 12)
(1, 3) e (3, 6) → (1, 6)
(1, 3) e (3, 12) → (1, 12)
(1, 4) e (4, 12) → (1, 12)
(1, 6) e (6, 12) → (1, 12)
(2, 4) e (4, 12) → (2, 12)
(2, 6) e (6, 12) → (2, 12)
(3, 6) e (6, 12) → (3, 12)
Portanto, como a relação R é reflexiva, anti-simétrica e transitiva, temos que R é uma relação de
ordem parcial.
OBS: Em uma ROP R, dizemos que os elementos a e b são comparáveis por R se aRb ou bRa.
Por exemplo, na relação R divide listada acima temos que 2 e 4 são comparáveis, mas 2 e 3 não.
Def: Relação de ordem total (ROT)
Uma relação binária R em A é de ordem total se e somente se R é uma relação de ordem parcial e
quaisquer dois elementos de A são comparáveis por R.
ROT = ROP + ∀ x , y∈A(aRb∨bRa)
Nesse caso, dizemos que a tupla (A, R) é um conjunto totalmente ordenado. Um exemplo de relação
de ordem total é a relação R={(x , y)∈A / x≤ y }
Def: Ordenação lexicográfica
Seja A um conjunto qualquer e seja a relação ≤2 definida em A×A como:
(a1 , a2)≤2(b1, b2)⇔(a1<b1)∨((a1=b1)∧(a2≤b2))
A relação ≤2 induz uma ordenação lexicográfica no conjunto A×A .
Na prática, isso significa que podemos impor uma ordem para pontos do plano, percorrendo linha a
linha o conjunto bidimensional.
Ex: (Z×Z ,≤2 ) é um conjunto parcialmente ordenado.
Note que (3,5)≤2(4,8) pois o ponto (3, 5) vem antes de (4, 8) se percorrermos o conjunto de
pontos linha a linha. O mesmo vale para os pontos (3, 8) e (4, 5). Mesmo 8 sendo maior que 5, o
primeiro elemento do par ordenado é menor, por isso dizemos que (3, 8) antecede (4, 5).
Ex: Mostre que a relação ≤2 definida em N×N é uma relação de ordem parcial.
Devemos mostrar que a relação é reflexiva, simétrica e transitiva.
1. Reflexiva: ∀(a , b)∈N×N (a , b)≤2(a , b) pois a≤a e b≤b (OK)
2. Anti-simétrica: ∀(a , b) ,(c , d)∈N×N ((a , b)≤2(c ,d )∧(c , d )≤2(a , b))→(a , b)=(c , d )
Note que:
i. se , então (a<c)∨(a=c∧b≤d )
ii. se , então (c<a)∨(c=a∧d≤b)
De i) e ii) temos que (a=c)∧(b=d ) e portanto (a , b)=(c ,d)
3. Transitiva: ∀(a , b) ,(c , d) ,(e , f )∈N×N ((a , b)≤2(c ,d)∧(c , d)≤2(e , f ))→(a ,b)≤2(e , f )
Note que:
i. se (a ,b)≤2(c , d ) , então (a<c)∨(a=c∧b≤d )
ii. se (c , d)≤2(e , f ) , então (c<e)∨(c=e∧d≤f )
Combinando i) e ii), temos (a<e)∨(a=e∧b≤f ) , o que implica em (a , b)≤2(e , f )
Representação gráfica de conjuntos parcialmente ordenados
Def: Diagrama de Hasse
Seja A um conjunto e R uma relação de ordem parcial em A. Então, a tupla (A, R) é um conjunto
parcialmente ordenado. O diagrama de Hasse de conjunto é definido como segue:
i. ∀a∈A é representado por um ponto.
ii. ∀(a ,b)∈R , com a≠b , a deve estar abaixo de b, sendo representado por uma linha que
liga os pontos a e b.
iii. Não existem loops, nem triângulos no diagrama, ou seja, não representamos reflexividade, nem
transitividade.
Ex: Seja A = {1, 2, 3, 4, 5, 6, 7, 8, 9} e R dada por:
R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7),
 (2, 2), (2, 3), (2, 4), (2, 5),
 (3, 3), (3, 4), (3, 5),
 (4, 4), (4, 5),
 (5, 5),
 (6, 6), (6, 5), (6, 9),
 (7, 7), (7, 4), (7, 5),
 (8, 8), (8, 7), (8, 5),
 (9, 9), (9, 5),
}
Note que alguns pares não são comparáveis
(4, 9), (7, 9), (8, 6), …
Apesar de existir (2, 4) em R, não há linha
no diagrama pois há (2, 3) e (3, 4)
Ex: A = {1, 2, 3, 5, 6, 10, 15, 30} e seja R a relação binária dada por:
R={(a ,b)∈A×A /a divide b }
Responda:
a) Forneça os pares ordenados que compõem a relação R.
R = {(1, 1), (1, 2), (1, 3), (1, 5), (1, 6), (1, 10), (1, 15), (1, 30),
 (2, 2), (2, 6), (2, 10), (2, 30),
 (3, 3), (3, 6), (3, 15), (3, 30),
 (5, 5), (5, 10), (5, 15), (5, 30),
 (6, 6), (6, 30),
 (10, 10), (10, 30),
 (15, 15), (15, 30),
 (30, 30)}
b) Desenhe o diagrama de Hasse do conjunto parcialmente ordenado.
Ex: Seja A = {1, 2, 3} e 2A o conjunto potência de A. Seja a relação R dada por:
R={(X ,Y )∈2A×2A : X⊆Y }
Escreva os pares ordenados que compõem a relação R e desenhe o diagrama de Hasse do POSET.
Ex: Seja A = {1, 2, 3, 4, 5} e seja R a relação definida como:
R={(x , y)∈A×A : x≤ y }
Escreva os pares ordenados que compõem a relação R e desenhe o diagrama de Hasse do