Relações e Conjuntos

Prévia do material em texto

2017.2 CB 0661 - MATEMÁTICA DISCRETA (PROF. FABRICIO)
LISTA 1.2
Cada
√
denota um nível de dificuldade:
√
fácil,
√√
médio e
√√√
difícil.
1 Conjuntos
1.(
√
) Complete com ∈ e/ou ⊆. (quando ambos forem válidos, coloque ambos símbolos)
(a) {∅}__{∅, {∅}}
(b) {∅}__{∅, {{∅}}}
(c) {{∅}}__{∅, {∅}}
(d) {{∅}}__{∅, {{∅}}}
2.(
√√
) Prove ou desprove:
(a) A ⊆ B sse A ∩B = A sse A ∪B = B sse A−B = ∅
(b) A− (B − C) = (B − C)
(c) A ∩B = A− (A−B)
(d) A ∩B ⊂ A
3.(
√√√
) É possível que exista um conjunto ao qual pertença todos os conjuntos unitários? (Sugestão: mostre
primeiro que não existe um conjunto cujos elementos são todos os conjuntos.)
4.(
√
) Prove ou desprove:
(a) A×B = ∅ se e somente se A = ∅ ou B = ∅.
(b) Para todo conjunto A, (A×A)×A = A× (A×A)
2 Relações (equivalência e ordens)
Veja primeiro as questões marcadas do livro “Matemática Discreta - uma introdução”, Scheinerman: no
arquivo listaRelacoes.pdf já disponível no SIGAA.
5.(
√
) Prove ou desprove: Se R é uma relação antissimétrica, então R é assimétrica.
6.(
√
) Considere as propriedades de relações: reflexividade, simetria, antissimetria, assimetria e transitividade
(ver glossário ao final). Para cada uma das relações abaixo, indique quais propriedades valem e quais são
violadas.
(a) Relação “foi casado com” sobre o conjunto de todas as pessoas do Ceará;
(b) Relação “tem mesma marca” sobre o conjunto de todos os automóveis de Fortaleza;
(c) Relação “⊆” sobre o conjunto das partes de {1, 2, 3, 4, 5, 6, 7};
(d) Relação “tem mesmo comprimento de lado” sobre o conjunto de todos os polígonos equiláteros;
(e) Relação “tem ordem de crescimento maior” sobre o conjunto de todos os polinômios.
7.(
√
) Se R é uma relação binária reflexiva e transitiva em {1, 2, 3, 4} e 1R2, 2R3 e 3R4, que outros pares devem
ocorrer em R? É possível afirmar que R é uma ordem total? Argumente.
8.(
√√
) Prove que se R é assimétrica, então R é antissimétrica. Isso significa que toda ordem estrita é também
parcial?
1
3 Glossário
Reflexividade: ∀a ∈ A, aRa;
Antireflexividade: ∀a ∈ A,¬aRa;
Simetria: ∀a, b ∈ A, (aRb→ bRa);
Assimetria: ∀a, b ∈ A, (aRb→ ¬bRa);
Antissimetria: ∀a, b ∈ A, (aRb ∧ bRa)→ (a = b);
• Composta: dadas relações P e Q,
P ◦Q = {(a, b) | existe c para o qual aQc e cPb}
• Inversa: a inversa de R é R−1 = {(a, b) | (b, a) ∈ R}
• Função: relação tal que ∀a ∈ domf, (f(a) = b ∧ f(a) = b′)⇒ b = b′.
• Relação de equivalência: reflexiva, simétrica e transitiva.
• Ordem Parcial: reflexiva, antissimétrica e transitiva.
• Ordem Estrita: assimétrica e transitiva.
• Ordem Total: ordem parcial ou estrita tal que ∀a, b ∈ A, aRb ∨ bRa
2
	Conjuntos
	Relações (equivalência e ordens)
	Glossário