A internet: o poder das pessoas

Disponível somente no TrabalhosFeitos
  • Páginas : 14 (3473 palavras )
  • Download(s) : 0
  • Publicado : 16 de dezembro de 2011
Ler documento completo
Amostra do texto
1 MATEMATICA DISCRETA: RELAÇÃO

1. Definições inicias: relação binária

Além de frequentemente usado no cotidiano, o conceito intuitivo de relação também é usual na matemática e, conseqüentemente, na computação e na Informática.
Essas relações são ditas binárias, pois relacionam dois elementos de cada vez. Seguindo o mesmo raciocínio, existem ternárias, quaternárias, unárias,etc. Algumas relção podem ser definidas sobre coleções que não são conjuntos como, por exemplo, a continência sobre todos os conjuntos.
Dados dois conjuntos A e B, uma relação binária R de A em B é um subconjunto de um produto cartesiano A× B , ou seja R ⊆ A× B , onde:
- A é o domínio, origem ou conjunto de partida de R
- B é o contra-domínio, destino ou conjunto de chegada de R
Para R ⊆ A×B , se a,b ∈ R , então afirmamos que "a relaciona-se com b". Podemos denotar uma relação R da seguinte forma: R : A→ B e, para um elemento a,b ∈ R , podemos denota-lo como aRb.
Exemplos: Sejam A = {a}, B = {a, b} e C = {0, 1, 2}. São exemplos de relações:
- ∅ é uma relação de A em B
- A× B ’ {a,a , a,b }é uma relação de A em B
- Relação de Igualdade de A em A: {a, a }
- Relação "menor"de C em C: {0,1 , 0,2 , 1,2 }
- Relação de C em B: {0, a , 1,b }
- ⊆: P(B) → P(B)
- ≤ : C →C
- ’: A→ A

1.2 ENDORRELAÇÃO OU AUTO-RELAÇÃO

Dado um conjunto A, uma relação do tipo R : A→ A é dita uma Endorrelação ou Auto-Relação. Assim, temos que origem e destino são o mesmo conjunto e podemos denota-la por A, R .
Exemplos: Seja A um conjunto. Então, são endorrelações:
- Ν,≤- Ζ,≤
- Q,’
- P(A),⊆
- P(R),⊂

Uma relação binária pode ser representada no diagrama de Venn, como mostram as figuras abaixo.
[pic]
par a,b de R : A→ B C,< ’ {0,1 , 0,2 , 1,2 }

A seguir, algumas definições referentes ao conceito de relação:
a) a,b ∈ R : dizemos que R está definida para a e que b é a imagem de a.
b)Domínio de definição: é o conjunto de todos os elementos de A para os quais R está definida.
c) Conjunto imagem: conjunto de todos os elementos de B que estão relacionados com algum elemento de A.
Exemplos: Dados os conjuntos A = {a}, B = {a, b} e C = {0, 1, 2}, temos que :
- para a endorrelação C,< , o domínio de definição é o conjunto {0, 1} e o conjunto imagem é o conjunto {1, 2].
- para arelação ’: A→ B , o domínio de definição é o conjunto {a} e o conjunto imagem
também é o conjunto {a}.

1.2.1 Endorrelação como grafo

Toda endorrelação R : A→ A pode ser representada como um grafo, onde:
a) cada elemento do conjunto A é representado como um nodo do grafo;
b) cada par a,b da relação é representada como uma aresta do grafo, com origem em a e destino em b.Exemplos:
[pic]

∅: A→ A ’: B → B ’ {a,a , b,b } C,< ’ {0,1 , 0,2 , 1,2 } R :C →C tal que R ’ {0,2 , 2,0 , 2,2 }

1.3 RELAÇÃO COMO MATRIZ

Sejam A = {a1, a2, ..., an} e B = {b1, b2, ..., bm} dois conjuntos finitos. A representação da relação R : A→ B como matriz é como segue:
a) o número de linhas é n (número de elementos do domínio);
b) o número de colunas é m (número deelementos da imagem);
c) a matriz resultante possui m x n células;
d) cada uma das m x n células possuem um valor lógico associado;
e) se a b R i j , ∈ , então a posição determinada pela linha i e pela coluna j da matriz contém valor verdadeiro (1); caso contrário, seu valor será falso (0).
Exemplo: Dados os conjuntos A = {a}, B = {a, b} e C = {0, 1, 2}, temos que
[pic]
[pic]

1.4PROPRIEDADES DAS RELAÇÕES

Uma endorrelação binária em um conjunto A pode ter determinadas propriedades. A seguir serão apresentadas as propriedades que envolvem as endorrelações.

1.4.1 Relação reflexiva

Sejam A um conjunto e R uma endorrelação em A. R é uma relação reflexiva se:
(∀a∈ A)(aRa)
A negação da propriedade reflexiva é como segue: (∃a∈ A)(¬(aRa))
Exemplos: Dado...
tracking img