propriedades das relações em A

Prévia do material em texto

FATEC - SCS 
 MATEMÁTICA DISCRETA I 
 PROF. EDISON 
 
 
 
PROPRIEDADES DAS RELAÇÕES BINÁRIAS INTERNAS 
 
 
P.1 REFLEXIVA 
 
R a b c d 
 a 1 
b 1 
c 1 
d 1 
 
Na tabela (matriz) a diagonal principal está totalmente preenchida 
No grafo todos os elementos têm um arco- seta 
São reflexivas as relações: mesma altura, mesma cor, divisor de, múltiplo de,etc 
 
P.2 NÃO REFLEXIVA 
 
R a b c d 
a 0 
b 1 
c 1 
d 0 
 
Na tabela (matriz) a diagonal principal está parcialmente preenchida 
No grafo, há pelo menos um elemento sem arco-seta 
 
P.3 ANTI-REFLEXIVA 
 
R a b c d 
a 0 
b 0 
c 0 
d 0 
 
Na tabela (matriz) a diagonal principal está vazia 
No grafo, nenhum elemento tem arco-seta 
São anti-reflexivas as relações: é pai de, é avô de, é filho de, é maior que, é menor 
que,etc 
 P.4 SIMÉTRICA 
 
 
 
 
 
 
 
 
Na tabela (matriz) os pares são simétricos em relação à diagonal principal 
No grafo, as ligações entre elementos distintos têm setas duplas 
São simétricas as relações: é irmão de, é amigo de, tem a mesma forma que, tem a 
mesma idade que, tem a mesma altura que, etc 
 
P.5 NÃO- SIMÉTRICA 
 
R a b c d 
a x 1 1 
b 1 x 1 1 
c 1 1 x 1 
d 1 1 1 x 
 
 Na tabela(matriz) há pelo menos um par que não tem o seu simétrico; a tabela não é 
simétrica em relação à diagonal principal 
No grafo, há pelo menos uma ligação que não tem setas nos dois sentidos (dupla) 
 
 
P.6 ANTI-SIMÉTRICA 
 
R a b c d 
a x 
b 1 x 
c 1 1 x 
d x 
 
Na tabela (matriz) não há pares em posições simétricas em relação à diagonal 
principal 
No grafo, não há qualquer ligação em ambos os sentidos 
São anti-simétricas as relações: é pai de, é filho de, é maior que, é menor que, etc 
 
 
 
 
 
 
 
R a b c d 
a x 1 
b x 
c 1 x 1 
d 1 x 
 
P.7 ASSIMÉTRICA 
 
 
 
 
 
 
 
 
Na tabela(matriz) a diagonal principal deve ser igual a zero e não pode ocorrer pares 
simétricos. 
No grafo, se de algum elemento partir seta para outro elemento, não pode haver seta 
em sentido contrário 
 
 
P.8 TRANSITIVA 
 
 
 
 
 
 
 
Se (a,b) e (b,d) são pares de R então (a,d) também é par de R. 
No grafo, se houver uma seta de a para b e outra de b para d, deverá haver uma seta 
de a para d 
São transitivas as relações: é menor que, é maior que, mora na mesma rua que, é da 
mesma altura que, etc 
 
 
P.9 NÃO- TRANSITIVA 
 
 
 
 
 
 
 
 
R é não-transitiva se houver pelo menos um caso em que (a,b) e (b,c) são pares de R 
mas (a,c) não é par de R. 
 
 
 
 
 
R a b c d 
a 0 0 
b 1 0 1 
c 0 0 
d 0 
R a b c d 
a 1 1 
b 1 
c 
d 
R a b c d 
a 1 
b 1 
c 
d 
 
RELAÇÃO DE EQUIVALÊNCIA 
 
 
R é chamada relação de equivalência se R for simultaneamente 
 
REFLEXIVA SIMÉTRICA E TRANSITIVA 
 
 
Uma relação de equivalência sobre um conjunto determina uma partição desse 
conjunto. 
 
Partição de um conjunto A é o conjunto das partes de A tais que: 
-a sua união é o conjunto A 
-nenhuma é vazia 
-sua intersecção é vazia 
 
Essas partes são denominadas classes de equivalência 
 
Chama-se classe de equivalência de um elemento 
Aa
, segundo uma relação R e 
representa-se por 
 a
 ao conjunto de todos os elementos de A que lhe são 
equivalentes, isto é, todos os elementos de A que estão relacionados com o elemento a 
segundo a relação de equivalência R 
 
 
RELAÇÃO DE ORDEM 
 
Uma Relação R sobre um conjunto A é de ordem parcial se for simultaneamente 
 
REFLEXIVA ANTI-SIMÉTRICA E TRANSITIVA 
 
 
SE, ALÉM DAS PROPRIEDADES MENCIONADAS ACIMA, UMA RELAÇÃO R 
VERIFICAR TAMBÉM : 
 
 
RabRbaAba  ),(),(,,
 a relação R é considerada de ordem total. 
 
O efeito de uma relação de ordem sobre um conjunto A é a formação de uma série 
ordenada de elementos de A.