Ordens Parciais

Prévia do material em texto

Ordens Parciais 
• Uma relação binária em um conjunto S que seja 
reflexiva, anti-simétrica e transitiva é chamada 
uma ordem parcial em S. 
• Exemplos: 
– x ρ y ↔ x ≤ y em ℕ 
– A ρ B ↔ A ⊆ B em ℘(ℕ) 
– x ρ y ↔ x divide y em ℤ+ 
 
• Se ρ é uma ordem parcial em S, então o par 
ordenado (S, ρ) é chamado um conjunto 
parcialmente ordenado. 
• Notação 
– (S, ≼) é um conjunto parcialmente ordenado. 
– Se x ≼ y e x ≠ y, então x ≺ y (x é um predecessor 
de y ou y é um sucessor de x) 
– Se ∄ z | x ≺ z ≺ y, então x é predecessor 
imediato de y 
Diagrama de Hasse 
• Representação visual de um conjunto 
parcialmente ordenado (S, ≼) 
– Cada elemento de S é um ponto (nó ou 
vértice) no diagrama 
– Se x ≺ y, então y é posicionado acima de x no 
diagrama e os dois pontos são conectados por 
um segmento de reta. 
Exemplo 
• Desenhe o diagrama de Hasse para (S, ≼) 
– S = {1, 2, 3, 6,12, 18} 
– x ≼ y ↔ “x divide y” 
Exemplo 
• Desenhe o diagrama de Hasse para (S, ≼) 
– S = {1, 2, 3, 6,12, 18} 
– x ≼ y ↔ “x divide y” 
1 
2 3 
6 
12 18 
Analisando o Diagrama de Hasse de um conjunto parcialmente 
ordenado podemos reconstruir o conjunto de pares ordenados. 
Os seguimentos de retas nos dão os sucessores e predecessores 
e os que faltarem podem ser inferidos através da propriedades 
de reflexividade e transitividade. 
Podemos concluir que o conjunto ≼ é? 
Exercício 
Analisando o Diagrama de Hasse de um conjunto parcialmente 
ordenado podemos reconstruir o conjunto de pares ordenados. 
Os seguimentos de retas nos dão os sucessores e predecessores 
e os que faltarem podem ser inferidos através da propriedades 
de reflexividade e transitividade. 
Podemos concluir que o conjunto ≼ é? 
Exercício 
{(a, a), (b, b), (c, c), (d, d), 
(e, e), (f, f), (a, b), (a, c), 
(a, d), (a, e), (d, e)} 
Ordem Total 
• Uma ordem total é uma ordem parcial 
na qual todo elemento do conjunto 
está relacionado a todos os outros 
elementos. 
• Exemplo: 
– x ρ y ↔ x ≤ y em ℕ 
Diagrama de Hasse 
para ordens totais. 
Elemento Mínimo 
• Seja (S, ≼) um conjunto parcialmente 
ordenado. 
• Se existe m ∈ S tal que (∀x)(m ≼ x), então 
m é um elemento mínimo. 
• Se existir um elemento mínimo, ele é 
único. 
• Em um diagrama de Hasse, um elemento 
mínimo está abaixo de todos os outros. 
Elemento Minimal 
• Seja (S, ≼) um conjunto parcialmente 
ordenado. 
• Se t ∈ S e (∄x)(x ≺ t), então t é um 
elemento minimal. 
• Em um diagrama de Hasse, um elemento 
minimal não tem elementos abaixo dele. 
• Um elemento pode ser, ao mesmo tempo, 
mínimo e minimal. Um elemento mínimo 
é sempre minimal. 
Máximo e maximal 
• Usando o mesmo raciocínio do mínimo e 
minimal podemos definir o máximo e 
maximal. 
• Se existe m ∈ S tal que (∀x)(m ≽ x), então m é 
um elemento máximo e máximo é único. 
• Se t ∈ S e (∄x)(x ≻ t), então t é um elemento 
maximal. 
 
Exercício 
1 
2 3 
6 
12 18 
Qual o mínimo, minimal, máximo e maximal no seguinte 
diagrama de Hasse? 
Exercício 
1 
2 3 
6 
12 18 
Qual o mínimo, minimal, máximo e maximal no seguinte 
diagrama de Hasse? 
1 é ao mesmo tempo, mínimo e minimal; 
12 e 18 são maximais, mas não existe elemento máximo. 
O menor elemento é sempre o minimal e o maior é sempre o 
maximal, mas a recíproca não é verdadeira. 
Ordem Parcial Uma relação binária em um conjunto S que 
seja reflexiva, anti-simétrica e transitiva 
Predecessor Se x ≼ y e x ≠ y, então x ≺ y (x é um 
predecessor de y) 
Sucessor Se x ≼ y e x ≠ y, então x ≺ y (y é um sucessor 
de x) 
 
Predecessor Imediato Se ∄ z | x ≺ z ≺ y, então x é predecessor 
imediato de y 
Ordem Total Uma ordem total é uma ordem parcial na 
qual todo elemento do conjunto está 
relacionado a todos os outros elementos. 
Mínimo Se existe m ∈ S tal que (∀x)(m ≼ x), então m 
é um elemento mínimo. Mínimo é único 
Minimal Se t ∈ S e (∄x)(x ≺ t), então t é um elemento 
minimal. 
Máximo Se existe m ∈ S tal que (∀x)(m ≽ x), então m 
é um elemento máximo. Máximo é único 
Maximal Se t ∈ S e (∄x)(x ≻ t), então t é um elemento 
maximal. 
Relações de Equivalência 
• Uma relação binária em um conjunto S que é 
reflexiva, simétrica e transitiva é chamada 
uma relação de equivalência em S 
• Exemplos: 
– x ρ y ↔ x+y é par 
– x ρ y ↔ x = y 
Partição de um Conjunto 
• Uma partição de um conjunto S é uma 
coleção de subconjuntos disjuntos não-
vazios de S, cuja união é igual a S. 
• Exemplo 
– S = {a, b, c, d, e, f, g} 
– {{a, b}, {c, d}, {e, f, g}} é uma partição de S 
Teorema 
• Uma relação de equivalência ρ em um 
conjunto S determina uma partição de S. 
• Uma partição de S determina uma relação 
de equivalência em S. 
• Uma relação de equivalência divide o conjunto 
onde ela está definida em uma partição. 
• Os subconjuntos que compõem a partição são 
formados agrupando-se os elementos 
relacionados. 
• Exemplo 
– S é o conjunto dos alunos em uma sala 
– x ρ y ↔ “x senta na mesma fila que y” 
 
 
Classes de Equivalência 
• Seja ρ é uma relação de equivalência 
em um conjunto S e x ∈ S 
• Denota-se por [x] o conjunto de todos 
os elementos de S relacionados a x; 
• Esse conjunto é chamado de classe de 
equivalência de x. 
– [x] = {y | y ∈ S ∧ x ρ y} 
Classes de Equivalência 
• No caso em que x ρ y ↔ “x senta na mesma fila 
que y”, suponha que João, Carlinhos, José, Judite e 
Téo sentam-se todos na terceira fileira. 
• Então [João] = {João, Carlinhos, José, Judite,Téo} 
• Além disso, [João] = [José] = [Téo] = [Judite], e assim por 
diante. 
• Essas são as mesmas classes com nomes diferentes. 
• Uma classe de equivalência pode usar o nome de 
qualquer de seus elementos. 
Congruência Módulo n 
• Sejam x e y inteiros e n um inteiro positivo 
– x ≡ y (mod n) se x-y é um múltiplo inteiro de n 
• Exemplos 
– 9 ≡ 1(mod 4), pois 9-1 é múltiplo de 4 
• A relação binária “congruência módulo n” 
é sempre uma relação de equivalência em 
ℤ 
• Conceito importante no projeto de 
arquitetura de computadores. 
Relação de equivalência Uma relação binária em um conjunto S que é 
reflexiva, simétrica e transitiva 
Partição de um conjunto S É uma coleção de subconjuntos disjuntos não-vazios 
de S, cuja união é igual a S. 
Classe de equivalência Denota-se por [x] o conjunto de todos os elementos 
de S relacionados a x: [x] = {y | y ∈ S ∧ x ρ y} 
Congruência módulo n Se x e y são inteiros e n é um inteiro positivo, x ≡ y 
(mod n) se x – y é um múltiplo inteiro de n 
Tipo de relação Reflexiva Simétrica Antissimétrica Transitiva Caracteristica 
Ordem Parcial Sim Não Sim Sim Predecessores 
e Sucessoes 
Relação de 
Equivalência 
Sim Sim Não Sim Determina 
uma partição 
Funções 
Função Aplicação de um conjunto em outro que leva cada 
elemento do conjunto inicial em exatamente um 
elemento do conjunto final 
Domínio Conjunto inicial de uma função 
Contradomínio Conjunto final de uma função 
Imagem Ponto que resulta de uma aplicação 
Imagem inversa Ponto inicial de uma aplicação 
Sobrejetora (sobrejetiva) A imagem é todo o contradomínio; todo elemento no 
contradomínio tem uma imagem inversa 
Injetora (injetiva, um para um) Dois elementos no domínio não podem ser levados em 
um mesmo ponto 
Bijeção Injetora e sobrejetora 
Função identidade Leva cada elemento de um conjunto em si mesmo 
Função inversa Para uma bijeção, uma nova função que leva cada 
elemento no contradomínio de volta ao elemento de 
onde ele veio 
Sobrejetora 
A imagem é todo o contradomínio; 
Todo elemento no contradomínio tem uma imagem 
inversa 
 
Injetora 
• Dois elementos no domínio não podem ser 
levadosem um mesmo ponto 
 
Bijetora 
• É uma função Injetora e sobrejetora ao 
mesmo tempo 
Função Identidade 
• Leva cada elemento de um conjunto em si 
mesmo 
Função Inversa 
• Para uma bijeção, uma nova função que leva 
cada elemento no contradomínio de volta ao 
elemento de onde ele veio 
 
Exercício 
• Para a relação de equivalência ρ = {(a, a), (b, b), (c, c), (a, 
c), (c, a)}, qual o conjunto [a] ? Esse conjunto tem 
outros nomes? 
 
• Para a relação de equivalência ρ = {(1, 1), (2, 2), (1, 2), 
(2, 1), (1, 3), (3, 1), (3, 2), (2, 3), (3, 3), (4, 4), (5, 5), (4, 
5), (5, 4)}, qual o conjunto [3]? E o conjunto [4]? 
 
• Para a relação de equivalência congruência módulo 2 no 
conjunto ℤ, qual o conjunto [1]? 
 
• Para a relação de equivalência congruência módulo 2 no 
conjunto ℤ, qual o conjunto [-3]? 
Exercício