A maior rede de estudos do Brasil

Grátis
59 pág.
Provas anteriores RESPOSTAS

Pré-visualização | Página 11 de 12

(Teresa,Maria),
(Teresa,Raimundo)}
10. Seja A = {1, 2, 3, 4}. Construa as relac¸o˜es R1, R2, R3 e R4 em A abaixo. “Con-
struir relac¸o˜es” significa definir seus pares. Por exemplo, R1 = {(1, 1), (2, 1)}.
a) {1, 0 pt} Construa R1, tal que ela seja a menor relac¸a˜o reflexiva, antis-
sime´trica e transitiva.
Resposta: R1 = {(1, 1), (2, 2), (3, 3), (4, 4)}
b) {0, 5 pt} Construa R2 tal que ela seja reflexiva e sime´trica.
Resposta: R1 = {(1, 1), (2, 2), (3, 3), (4, 4)}
c) {0, 5 pt} Contrua R3, tal que ela seja igual ao seu fecho sime´trico.
Resposta: R1 = {(1, 2), (2, 1)}
d) {0, 5 pt} Construa R4, tal que ela seja assime´trica.
Resposta: R1 = {(1, 2)}
11. {2, 0 pt} Seja A = {1, 2, 3}. Seja R = {(1, 2), (2, 2), (2, 3), (3, 1)}. Calcule
o fecho transitivo utilizando matrizes. Fac¸a uma matriz com linha e coluna
representando os elementos 1, 2 e 3 (nesta ordem).
Resposta:
MR =

0 1 00 1 1
1 0 0


MR◦R =

0 1 00 1 1
1 0 0

�

0 1 00 1 1
1 0 0

 =

0 1 11 1 1
0 1 0


M(R◦R)◦R =

0 1 11 1 1
0 1 0

�

0 1 00 1 1
1 0 0

 =

1 1 11 1 1
0 1 1


MR∗ =MR ∨MR◦R ∨M(R◦R)◦R =

1 1 11 1 1
1 1 1


12. SejaA = {1, 2, 3, 4}. SejamR1 = {(1, 2), (1, 3), (1, 4)}, R2 = {(1, 1), (2, 2), (3, 3)}
e R3 = {(3, 1), (4, 4)} relac¸o˜es em A. Defina que propriedades as relac¸o˜es
abaixo possuem: reflexividade, simetria, transitividade, antissimetria, ou qual-
quer combinac¸a˜o destas. Por exemplo, “reflexividade, antissimetria e transi-
tividade” e´ uma poss´ıvel resposta.
a) {0, 5 pt} Fecho sime´trico de (R2 ∪R3)
Resposta: R2∪R3 = {(1, 1), (2, 2), (3, 3), (3, 1), (4, 4)}. O fecho sime´trico
deR2∪R3 e´ {(1, 1), (2, 2), (3, 3), (3, 1), (4, 4), (1, 3)}, que e´ reflexivo, sime´trico
e transitivo.
b) {0, 5 pt} R1 ◦R2
Resposta: R1 ◦R2 = {(1, 2), (1, 3)}, que e´ antissime´trica e transitiva.
c) {0, 5 pt} R1 ∪R2 ∪R3
Resposta: R1∪R2∪R3 = {(1, 2), (1, 3), (1, 4), (1, 1), (2, 2), (3, 3), (3, 1), (4, 4)},
que e´ reflexiva.
d) {0, 5 pt} Fecho reflexivo de R2
Resposta: O fecho reflexivo de R2 e´ {(1, 1), (2, 2), (3, 3), (4, 4)}, que e´
reflexivo, sime´trico, antissime´trico e transitivo.
e) {0, 5 pt} R1 −R2
Resposta: R1 −R2 = R1, que e´ antissime´trico e transitivo.
13. Seja A = {Bicicleta,Fusca,Ferrari}.
Seja R = {(x, y) ∈ A2 | x e´ mais ra´pido que y}.
a) {0, 75 pt} Descreva os pares (x, y) que pertenc¸am a R.
Resposta: R = {(Fusca,Bicicleta), (Ferrari ,Bicicleta), (Ferrari ,Fusca)}
b) {0, 75 pt} Das propriedades reflexividade, simetria, antissimetria e transi-
tivade, quais destas R possui?
Resposta: R e´ antissime´trico e transitivo.
c) {1, 5 pt} Calcule o fecho transitivo utilizando matrizes. Fac¸a uma matriz
com linha e coluna representando os elementos Bicicleta, Fusca e Ferrari
(nesta ordem).
Resposta:
MR =

0 0 01 0 0
1 1 0


MR◦R =

0 0 01 0 0
1 1 0

�

0 0 01 0 0
1 1 0

 =

0 0 00 0 0
1 0 0


M(R◦R)◦R =

0 0 00 0 0
1 0 0

�

0 0 01 0 0
1 1 0

 =

0 0 00 0 0
0 0 0


MR∗ =MR ∨MR◦R ∨M(R◦R)◦R =

0 0 01 0 0
1 1 0


6 Grafos
1. {2 pt} Use o teorema das cores para definir se os grafos abaixo sa˜o bipartidos.
Caso na˜o tenha la´pis/caneta colorido: coloque um quadrado ao redor de um
ve´rtice para representar azul e um triaˆngulo para representar vermelho.
a) b) c) d)
Resposta: a) Na˜o bipartido. b) Bipartido. c) Bipartido. d) Na˜o bipartido.
2. Seja G = (V,A) um grafo na˜o dirigido. Seja V = {a, b, c, d, e, f}. Sejam
deg(a) = deg(d) = 0, deg(b) = 3, deg(c) = deg(e) = 2, deg(f) = 5.
a) {1 pt} Quantas arestas este grafo possui?
Resposta:∑
v∈V
deg(v) = 0 + 3 + 2 + 2 + 5 = 12 = 2|A| ∴ |A| = 6
b) {1 pt} Desenhe o grafo (lembre-se que pode haver lac¸os).
Resposta:
c
b
d
a
e
f
3. {1 pt} Remova exatamente 1 aresta ou adicione exatamente 1 aresta (ou am-
bos) de cada grafo abaixo de forma a transforma´-los em a´rvore. Desenhe a
a´rvore resultante da remoc¸a˜o/adic¸a˜o.
a) b)
Resposta:
a) b)
4. Utilize o teorema das cores e defina se os grafos abaixo sa˜o bipartidos ou na˜o
(exiba os desenhos pintados).
a) {0, 5 pt} b) {0, 5 pt} c) {0, 5 pt} d) {0, 5 pt}
Q3 (hipercubo de 3 dimenso˜es)
Resposta: a) Na˜o bipartido b) Bipartido c) Na˜o bipartido d) Bipartido
T ≡ ¬F (1)
¬T ≡ F (2)
p ∧ T ≡ p (3)
p ∨ F ≡ p (4)
p ∨ T ≡ T (5)
p ∧ F ≡ F (6)
p ∨ p ≡ p (7)
p ∧ p ≡ p (8)
¬(¬p) ≡ p (9)
p ∨ q ≡ q ∨ p (10)
p ∧ q ≡ q ∧ p (11)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (12)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (13)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (14)
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) (15)
¬(p ∧ q) ≡ ¬p ∨ ¬q (16)
¬(p ∨ q) ≡ ¬p ∧ ¬q (17)
p ∨ (p ∧ q) ≡ p (18)
p ∧ (p ∨ q) ≡ p (19)
p ∨ ¬p ≡ T (20)
p ∧ ¬p ≡ F (21)
p→ q ≡ ¬p ∨ q (22)
p→ q ≡ ¬q → ¬p (23)
p ∨ q ≡ ¬p→ q (24)
p ∧ q ≡ ¬(p→ ¬q) (25)
¬(p→ q) ≡ p ∧ ¬q (26)
(p→ q) ∧ (p→ r) ≡ p→ (q ∧ r) (27)
(p→ r) ∧ (q → r) ≡ (p ∨ q)→ r (28)
(p→ q) ∨ (p→ r) ≡ p→ (q ∨ r) (29)
(p→ r) ∨ (q → r) ≡ (p ∧ q)→ r (30)
p↔ q ≡ (p→ q) ∧ (q → p) (31)
p↔ q ≡ ¬p↔ ¬q (32)
p↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q) (33)
¬(p↔ q) ≡ p↔ ¬q (34)
¬∃xP (x) ≡ ∀x¬P (x) (35)
¬∀xP (x) ≡ ∃x¬P (x) (36)
p
p→ q
∴ q
(37)
¬q
p→ q
∴ ¬p (38)
p→ q
q → r
∴ p→ r (39)
p ∨ q
¬p
∴ q
p ∨ q
¬q
∴ p
(40)
p
∴ p ∨ q
p
∴ q ∨ p (41)
p ∧ q
∴ p
p ∧ q
∴ q
(42)
p
q
∴ p ∧ q (43)
p→ q
∴ ¬q → ¬p (44)
p ∨ q
¬p ∨ r
∴ q ∨ r (45)
a /∈ A ≡ ¬(a ∈ A) (46)
{x | x ∈ A} = A (47)
P (a) ≡ a ∈ {x | P (x)} (48)
(A = B) ≡ ∀x(x ∈ A↔ x ∈ B) (49)
(A ⊆ B) ≡ ∀x(x ∈ A→ x ∈ B) (50)
(A ⊂ B) ≡ ∀x(x ∈ A→ x ∈ B) ∧
∃x(x ∈ B ∧ x /∈ A) (51)
∅ ⊆ S, para todo S (52)
∅ = {x | F} (53)
x ∈ ∅ ≡ F (54)
S ⊆ S, para todo S (55)
(A× ∅) = (∅ ×A) = ∅ (56)
A ∪B = {x | x ∈ A ∨ x ∈ B} (57)
(x ∈ A ∨ x ∈ B) ≡ (x ∈ (A ∪B)) (58)
A ∩B = {x | (x ∈ A) ∧ (x ∈ B)} (59)
(x ∈ A ∧ x ∈ B) ≡ (x ∈ (A ∩B)) (60)
|A ∪B| = |A|+ |B| − |A ∩B| (61)
A−B = {x | x ∈ A ∧ x /∈ B} (62)
(x ∈ A ∧ x /∈ B) ≡ (x ∈ (A−B)) (63)
A = {x | x /∈ A} (64)
(x /∈ A) ≡ (x ∈ A) (65)
A ∪ ∅ = A (66)
A ∩ U = A (67)
A ∪ U = U (68)
A ∩ ∅ = ∅ (69)
A ∪A = A (70)
A ∩A = A (71)
(A) = A (72)
A ∪B = B ∪A (73)
A ∩B = B ∩A (74)
A ∪ (B ∪ C) = (A ∪B) ∪ C (75)
A ∩ (B ∩ C) = (A ∩B) ∩ C (76)
A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C) (77)
A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C) (78)
A ∪B = A ∩B (79)
A ∩B = A ∪B (80)
A ∪ (A ∩B) = A (81)
A ∩ (A ∪B) = A (82)
A ∪A = U (83)
A ∩A = ∅ (84)