Aula 3 - Relações pt2

Prévia do material em texto

FUNDAMENTOS MATEMÁTICOS PARA COMPUTAÇÃO
Professor: Jean Carlos Gentilini
Curso: Sistemas de Informação
Período: 1º/2014
RELAÇÕES
Uma relação binária em um conjunto S pode 
ter certas propriedades. Por exemplo, a 
relação de S2, ={(x, y) ∈ S2 / x = y}, tem três propriedades:
1- Reflexiva: Se todo elemento de S está relacionado com ele próprio; para 
todo x∈S: (x,x)∈ .
2- Simétrica: Uma relação :S→S é simétrica se xy, implicar necessariamente 
que yx; 
Se xy ⇒ (x, y) ∈ ⇒ (y, x) ∈ ⇒ yx.
3- Transitiva: Uma relação :S→S é transitiva, se xy e yz, implicar que xz;
Se xy e yz ⇒ (x, y), (y, z) ∈ ⇒ (x, z) ∈ ⇒ xz
RELAÇÕES
Considerando o conjunto S={1, 2, 3, 4} e as 
relações
 R1={(1,1), (1,2), (2,1), (2,2), (3,4), (4,1), (4,4)}.
 R2={(1,1), (1,2), (2,1)}.
 R3={(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), 
(4,4)}.
 R4={(2,1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}.
R5 ={(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), 
(3,3), (3,4), (4,4)}.
As relações R3 e R5 são reflexivas.
RELAÇÕES
Dado o conjunto dos números Inteiros Z, 
considere as seguintes relações sobre ZxZ:
R1={(a, b) / a <= b}.
R2={(a, b) / a < b}.
R3={(a, b) / a = b ou a = -b}.
R4={(a, b) / a = b}.
R5 ={(a, b) / a = b+1}.
As relações R1, R3 e R4 são reflexivas.
RELAÇÕES
Considerando o conjunto S={1, 2, 3, 4} e as 
relações
 R1={(1,1), (1,2), (2,1), (2,2), (3,4), (4,1), (4,4)}.
 R2={(1,1), (1,2), (2,1)}.
 R3={(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), 
(4,4)}.
 R4={(2,1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}.
R5 ={(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), 
(3,3), (3,4), (4,4)}.
As relações R2 e R3 são simétricas.
RELAÇÕES
Dado o conjunto dos números Inteiros Z, 
considere as seguintes relações sobre ZxZ:
R1={(a, b) / a <= b}.
R2={(a, b) / a < b}.
R3={(a, b) / a = b ou a = -b}.
R4={(a, b) / a = b}.
R5 ={(a, b) / a = b+1}.
As relações R3 e R4 são simétricas.
RELAÇÕES
Dado o conjunto dos números Inteiros Z, 
considere as seguintes relações sobre ZxZ:
R1={(a, b) / a <= b}.
R2={(a, b) / a < b}.
R3={(a, b) / a = b ou a = -b}.
R4={(a, b) / a = b}.
R5 ={(a, b) / a = b+1}.
As relações R1, R2, R3 e R4 são transitivas.
RELAÇÕES
Anti-simétrica: Sejam x∈A e y∈A. Uma 
relação 
:A→A é anti-simétrica se (x,y)∈e (y,x)∈ 
implicar que x=y. 
Se xy e yx ⇒ (x, y), (y, x) ∈ R ⇒ (x, x)∈⇒ x = y.
Ex.: Seja A = {a, b, c} e R1 e R2 relações em 
AxA. 
R1 = {(a, a), (b, b), (a, b), (a, c)}.
R2 = {(a, b), (b, a), (a, c), (c, a)}.
R1 é anti-simétrica, enquanto R2 não é. 
RELAÇÕES
Considerando o conjunto S={1, 2, 3, 4} e as 
relações
 R1={(1,1), (1,2), (2,1), (2,2), (3,4), (4,1), (4,4)}.
 R2={(1,1), (1,2), (2,1)}.
 R3={(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), 
(4,4)}.
 R4={(2,1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}.
R5 ={(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), 
(3,3), (3,4), (4,4)}.
As relações e R4 e R5 são anti-simétricas.
RELAÇÕES
Exercício: Defina uma relação binária no 
conjunto A={1,2,3,4} que seja: 
a) Reflexiva.
b) Simétrica.
c) Anti-simétrica.
d) Reflexiva, simétrica e não transitiva.
RELAÇÕES
Definição(Relação de Equivalência): 
Uma relação binária em um conjunto S 
que seja reflexiva, simétrica e transitiva 
é chamada de uma relação
de equivalência em S.
RELAÇÕES
Grafo da relação.
Uma relação definida de um conjunto A no 
próprio conjunto A é chamada relação 
binária de A para A.
Uma representação gráfica de uma 
relação binária onde o conjunto A é 
desenhado somente uma vez e uma seta é 
desenhada para cada par de pontos 
relacionados entre si é chamada de GRAFO 
DIRIGIDO.
RELAÇÕES
Ex.; Se A={1, 2, 3, 4} e p é uma relação 
binária em AxA, onde p={(1,1), (1,3), (3, 
1)}
Ex.: Construa os grafos dirigidos da relação 
R={(a,b),(a,c),(b,c)}.
RELAÇÕES
Exemplo: Seja A={3, 4, 5, 6, 7, 8} e a relação 
binária R definida por todos os pares 
ordenados (x, y) em que 2 divide a diferença x 
– y. Veja o diagrama de R e os grafos dirigidos.
RELAÇÕES
Exercício: Seja A={3, 4, 5, 6, 7, 8} e a 
relação binária R definida por todos os 
pares ordenados (x, y) em que 3 divide a 
diferença x – y. Determine quais os pares 
ordenados da relação e os descreva 
utilizando grafos dirigidos.
RELAÇÕES
Definição: Relação n-ária
Dados os conjuntos S1, S2,..., Sn, uma relação n-ária em 
S1, S2, ... , Sn, é um subconjunto de S1xS2...xSn. 
Um caso especial de relação n-ária é uma relação unária em um 
conjunto S, que é apenas um subconjunto particular de S. Um elemento x 
satisfaz se e somente se x pertencer ao subconjunto.
RELAÇÕES
Frequentemente estaremos 
interessados em relações binárias ou n-
árias onde todos os conjuntos dados são 
o mesmo conjunto S. Essas relações são 
chamadas de relações no conjunto S, 
como definimos a seguir.
RELAÇÕES
Definição: Relações em um conjunto 
S: Uma relação binária em um conjunto 
S é um subconjunto de S2(o conjunto de pares 
ordenados de elementos de S). Analogamente, uma relação n-ária em 
um conjunto S é um subconjunto de Sn (um conjunto de n-uplas 
ordenadas de elementos de S).
RELAÇÕES
Seja S = {0, 1, 2, 4, 6}. Verifique se as 
relações binárias em S são reflexivas, 
simétricas, anti-simétricas e/ou transitivas:
a) = {(0,0}, (1, 1), (2, 2), (4, 4), (6,6), (0, 1), 
(1, 2), (2, 4), (4, 6)}
b) = {(0, 1), (1, 0), (2, 4), (4, 2), (4, 6), (6, 4)}
c) = {(0, 1), (1, 2), (0, 2), (2, 0), (2, 1), (1, 0), 
(0, 0), (1, 1), (2, 2)}
d) = {(0, 0), (1,1), (2, 2), (4, 4), (6, 6), (4, 6), 
(6, 4)}
RELAÇÕES
Desenhe os grafos das seguintes 
relações :
a) S = {a, b, c, d}.
 = {(a,a), (b,b), (c,c), (a,b), (b,c), (a,c)}
b) S = {a, b, c, d}.
 = {(a,a), (b,b), (c,c), (d,d), (a,b), (a,c)}
c) S={1, 2, 3, 4, 5, 6}.
 = {(x,y) ∈ SxS / x divide y }
REFERÊNCIAS:
FLEMIMING, D. M.; GONÇALVES, M. B. Cálculo 
A: funções, limite, derivação, integração. 5. ed. 
São Paulo: Pearson Makron Books, 1992. 
GERSTING, J, L. Fundamentos Matemáticos 
para a Ciência da Computação. 3. ED. Rio de 
Janeiro: LTC, 1993.
Notas de aula adaptadas do: Prof. Luiz 
Gonzaga Damasceno
	FUNDAMENTOS MATEMÁTICOS PARA COMPUTAÇÃO
	Relações
	Relações
	Relações
	Relações
	Relações
	Relações
	relações
	Relações
	Relações
	relações
	relações
	relações
	relações
	Relações
	Relações
	Relações
	Relações
	Relações
	Relações
	Referências: