L7D131

Prévia do material em texto

MAT 01375 � Matemática Discreta B 2013/1
Lista de Exercícios 7
1. Verifique se as relações definidas abaixo são relações de ordem parcial. Justifique.
(a) A relação em {a, b, c, d} representada pela matriz
1 1 1 1
0 1 0 1
0 0 1 0
0 0 0 1
 .
(b) A relação em {a, b, c, d} representada pela matriz
1 1 1 0
0 1 0 1
0 0 1 0
0 0 0 1
 .
(c) A relação em {1, 2, 3} representada pela matriz1 1 10 1 0
1 0 1
 .
(d) Seja S(R) o conjunto de todas as funções f : [0, 1] → [0, 1]. A relação R1 ⊆
S(R)× S(R) é definida por fR1g ⇐⇒ (∀x ∈ [0, 1])[f(x) ≤ g(x)].
(e) Seja A o conjunto das sequências binárias de comprimento menor ou igual a 3.
Para duas sequências a = a1 · · · am e b = b1 · · · bn, definimos aR1b se m = n.
(f) Seja A o conjunto das sequências binárias de comprimento menor ou igual a 3.
Para duas sequências a = a1 · · · am e b = b1 · · · bn, definimos aR2b se existem
inteiros positivos 1 ≤ `1 < `2 < · · · < `m ≤ n tais que ai = b`i para qualquer
i ∈ {1, 2, . . . ,m}.
(g) Seja B = P({1, 2, 3}). Para dois conjuntos C,D ∈ P({1, 2, 3}), definimos CR1D
se C = ∅ ou se C,D 6= ∅ e max{i : i ∈ C} ≤ max{i : i ∈ D}.
(h) Seja B = P({1, 2, 3}). Para dois conjuntos C,D ∈ P({1, 2, 3}), definimos CR2D
se C = D ou se max{i : i ∈ (C −D) ∪ (D − C)} ∈ D.
2. Para cada uma das relações de ordem da questão anterior, verifique se a ordem é
total. Além disso, decida se é possível utilizar um Diagrama de Hasse para representá-la.
Quando possível, faça tal diagrama.
1
2
3. Determine se os diagramas abaixo são diagramas de Hasse para alguma ordem
parcial. Justifique.
a
b
c
d
f
e
1 2 3
4 5
6 7
4. Considere a relação R1 ⊂ N × N dada por xRy se existe um inteiro t ≥ 1 tal que
y = xt. Prove que R1 é uma ordem parcial. Faça o diagrama de Hasse para (C,�R1),
onde C = {2m : m = 0, . . . , 10}.
5. Considere a relaçãoR2 ⊂ {2, 3, 4, . . .}×{2, 3, 4, . . .} dada por xR2y se {p primo : p|x} ⊆
{p primo : p|y}. Argumente que R2 não é uma relação de ordem parcial. Prove que te-
remos uma relação de ordem parcial se definirmos R3 ⊂ {2, 3, 4, . . .} × {2, 3, 4, . . .} por
xR3y se {p primo : p|x} ⊆ {p primo : p|y} ou se {p primo : p|x} = {p primo : p|y} e
x ≥ y. Além disso:
(a) Faça um diagrama de Hasse para essa relação em termos do conjunto S =
{2, 3, . . . , 18}.
(b) Para os conjuntos T1 = {x ∈ S : x é ímpar} e T2 = {x ∈ S : x é potência de 2},
indique os elementos mínimos, máximos, minimais e maximais, se existirem.
6. Seja R ⊂ A × A uma relação de ordem parcial. Como visto em aula, dizemos que
x ≺R y se xRy e x 6= y. Um elemento x ∈ A é predecessor imediato de y ∈ A se
(x ≺R y) ∧ (∀z ∈ A)[x �R z ∧ z �R y → z ∈ {x, y}].
(a) Prove que x é predecessor imediato de y se e somente se
(x ≺R y) ∧ (∀z ∈ A)[x ≺R z ∧ z �R y → z = y].
Considere a ordem parcial R2 ⊂ {2, 3, 4, . . .} × {2, 3, 4, . . .} na questão 5.
(b) Prove que todo n ≥ 2 tem um único predecessor imediato com relação a R2.
(c) Prove que, se n é primo se e somente se n não possui sucessor imediato com
relação a R2.
7. Uma ordem parcial R em um conjunto A é dita uma boa ordem se, dado qualquer
subconjunto ∅ 6= S ⊆ A, existe um elemento mínimo com relação a R (isto é, existe
x ∈ S tal que x � y para todo y ∈ S). Por exemplo, a ordem usual é uma boa ordem
para o conjunto dos números naturais.
(a) O conjunto dos números inteiros é bem ordenado pela ordem usual? Justifique.
(b) O conjunto dos números inteiros pode ser bem ordenado? (Isto é, existe uma
boa ordem para Z?)
(c) Mostre que toda boa ordem é uma ordem total.
8. Mostre que, se (A,�A) e (B,�B) são conjuntos parcialmente ordenados, então
(A×B,�) é um conjunto parcialmente ordenado, onde � é definida por
(a1, b1) � (a2, b2)⇐⇒ [a1 �A a2 ∧ b1 �B b2].
Se �A e �B são ordens totais, podemos concluir que � é uma ordem total?
3
9. Em cada item abaixo, determine se a afirmação é verdadeira ou falsa, assinalando
V ou F, respectivamente. Justifique suas respostas.
( ) É possível que um conjunto PO (parcialmente ordenado) tenha um elemento que
é, simultaneamente minimal e maximal, mas que não é nem máximo nem mínimo.
( ) Se um conjunto PO tem exatamente um elemento minimal, então ele deve ser o
mínimo
( ) Se (S, ≺ ) é um conjunto PO, finito e não vazio, então existe um elemento minimal
m e um elemento maximal M em S, para os quais vale que m≺M.