FundMatComp-2017b-lista2.pdf

Prévia do material em texto

UFF - Universidade Federal Fluminense
IC - Instituto de Computac¸a˜o
Fundamentos Matema´ticos da Computac¸a˜o
Prof. Luis Antonio Kowada
2017/2 - turma A1
Lista 2 - Relac¸o˜es
1. Classifique cada relac¸a˜o R ⊆ S × T , onde S = T = N como um-para-um, um-para-va´rios, va´rios-
para-um ou va´rios-para-va´rios:
(a) R = {(1, 2), (1, 4), (1, 6), (2, 3), (4, 3)}
(b) R = {(9, 7), (6, 5), (3, 6), (8, 5)}
(c) R = {(12, 5), (8, 4), (6, 3), (7, 12)}
(d) R = {(2, 7), (8, 4), (2, 5), (7, 6), (10, 1)}
2. Classifique cada uma das relac¸o˜es R ⊆ S × S como um-para-um, um-para-va´rios, va´rios-para-um
ou va´rios-para-va´rios:
(a) S = N; (x, y) ∈ R ⇐⇒ x = y + 1
(b) S = {conjunto de todas as mulheres de Nova Friburgo}; (x, y) ∈ R ⇐⇒ x e´ filha de y
(c) S = R; (x, y) ∈ R ⇐⇒ x = 5.
3. Sejam ρ e σ relac¸o˜es bina´rias em N definidas por (x, y) ∈ ρ ⇐⇒ x divide y e (x, y) ∈ σ ⇐⇒ 5x ≤
y. Determine quais dos pares ordenados satisfazem a`s relac¸o˜es dadas:
(a) ρ ∪ σ : (2, 6), (3, 17), (2, 1), (0, 0).
(b) ρ ∩ σ : (3, 6), (1, 2), (2, 12).
(c) ρ : (1, 5), (2, 8), (3, 15).
(d) σ : (1, 1), (2, 10), (4, 8).
4. Seja S = {0, 1, 2, 4, 6}. Verifique se as relac¸o˜es bina´rias em S sa˜o reflexivas, sime´tricas, anti-
sime´tricas e/ou transitivas:
(a) R = {(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (0, 1), (1, 2), (2, 4), (4, 6)}.
(b) R = {(0, 1), (1, 0), (2, 4), (4, 2), (4, 6), (6, 4)}.
(c) R = {(0, 1), (1, 2), (0, 2), (2, 0), (2, 1), (1, 0), (0, 0), (1, 1), (2, 2)}.
(d) R = {(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (4, 6), (6, 4)}.
(e) R = ∅.
5. Para cada caso abaixo, apresente um conjunto S e uma relac¸a˜o bina´ria R ⊆ S (diferente das
apresentadas anteriormente) que satisfac¸a a`s condic¸o˜es pedidas.
(a) R e´ reflexiva e anti-sime´trica, mas na˜o e´ transitiva.
(b) R e´ reflexiva e transitiva, mas na˜o e´ sime´trica.
(c) R na˜o e´ reflexiva nem sime´trica, mas e´ transitiva.
(d) R e´ reflexiva, mas na˜o e´ sime´trica nem transitiva.
6. Sejam R e S relac¸o˜es bina´rias em um conjunto A.
(a) Se R e S forem reflexivas, a unia˜o R ∪ S sera´ reflexiva? E a intersec¸a˜o R ∩ S?
(b) Se R e S forem sime´tricas, a unia˜o R ∪ S sera´ sime´trica? E a intersec¸a˜o R ∩ S?
(c) Se R e S forem anti-sime´tricas, a unia˜o R ∪ S sera´ anti-sime´trica? E a intersec¸a˜o R ∩ S?
(d) Se R e S forem transitivas, a unia˜o R ∪ S sera´ transitiva? E a intersec¸a˜o R ∩ S?
1