Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 Matemática Discreta Aula nº 9 Francisco Restivo 2006-03-30 2 Relações e suas representações Uma relação (binária) R entre (os conjuntos) A e B é um subconjunto do produto cartesiano A ´ B R Í A ´ B Exemplos: x é a Mãe de y x é maior que y x é a capital de y Representação: R = {(a, b): a é a capital do País b} a R b « (a, b) Î R A = {Porto, Lisboa, Madrid} B = {Portugal, Espanha, Brasil} R = {(Lisboa, Portugal), (Madrid, Espanha)} 2 3 Representações gráficas A = B = {1, 2, 3, 4, 5, 6} R = {(a, b): a divide b} 2 divide 4 grelha bidimensional 654321 x1 xx2 xx3 xxx4 xx5 xxxx6 A = {Deco, Figo, Lucho} B = {Porto, Benfica, Barcelona} R = {(a, b): a joga em b} Deco joga no Barcelona diagrama de setas Deco Figo Lucho Porto Benfica Barcelona 4 Representações gráficas A = B = {1, 2, 3, 4, 5, 6} R = {(a, b): a divide b} 3 divide 6 grafo orientado | digrafo A = B = {1, 2, 3, 4, 5, 6} R = {(a, b): a divide b} a nas linhas e b nas colunas 3 divide 3 e 3 divide 6 matriz binária 1 6 2 3 4 5 ú ú ú ú ú ú ú ú û ù ê ê ê ê ê ê ê ê ë é 100000 010000 001000 100100 101010 111111 3 5 Conjuntos tipificados Se R é uma relação entre A e B A: Set[S] B: Set[T] R: Set[S´T] Exemplo: Elementos de R? {(a,c), (a,d), (a,e), (b,e), (c,a), (c,b), (d,c), (d,e), (e,a), (e,b)} Matriz binária: a b c e d ú ú ú ú ú ú û ù ê ê ê ê ê ê ë é 00011 10100 00011 10000 11100 6 Propriedades das relações: Se R for uma relação num conjunto A, define-se Reflexiva se e só se "aÎA, aRa Simétrica se e só se "a,bÎA, aRb ® bRa Anti-simétrica se e só se "a,bÎA, aRb Ù bRa ® a = b Transitiva se e só se "a,b,cÎA, aRb Ù bRc ® a R c Exemplo: No conjunto dos números reais, xRy se e só se x £ y Reflexiva? Sim Simétrica? Não (contra-exemplo: x=1 e y=2) Anti-simétrica? Sim Transitiva? Sim 4 7 Outro exemplo: A = {a, b, c, d} R = {(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (b,d), (d,d)} Reflexiva? Não: ¬(cRc) Simétrica? Não: aRc mas ¬(cRa) Anti-simétrica? Não: aRb e bRa mas a¹b Transitiva? Não: aRb e bRd mas ¬(aRd) Mais um exemplo: Em Z+ ´ Z+, (a, b)R(c, d) se e só se a + d = b + c Propriedades: Reflexiva, Simétrica, Transitiva Anti-simétrica? (1, 2)R(2, 3) e (2, 3)R(1, 2) mas (1, 2)¹(2, 3) 8 Intersecção e união de relações: Uma vez que uma relação é um conjunto, podemos definir a intersecção e a união de relações. Se as relações R e S entre os conjuntos A e B são subconjuntos do conjunto A ´ B, então R Ç S e R È S também o são. Propriedades: Se R e S são reflexivas, então R Ç S e R È S também o são Se R e S são simétricas, então R Ç S e R È S também o são Se R e S são anti-simétricas, então R Ç S também o é, mas nada sabemos sobre R È S Se R e S são transitivas, então R Ç S também o é, mas nada sabemos sobre R È S 5 9 Composição de relações: A composição de R e S é uma relação S°R assim definida a(S°R)c se e só se $b, aRb Ù bRc aRb bSc a(S°R)c Exemplo: xRy se e só se x é a Mãe de y xSy se e só se x é o Pai de y Quais são as relações compostas S°R e R°S? Avó paterna e avô materno 10 Relação de equivalência: É uma relação que é reflexiva, simétrica e transitiva. Relações de equivalência e partições são conceitos relacionados. Uma relação de equivalência, no conjunto das pessoas vivas: xRy se e só se residem no mesmo País. É reflexiva (aRa), simétrica (se aRb então bRa) e transitiva (se aRb e bRc então aRc). A relação R divide o conjunto das pessoas vivas em partições, cada uma das quais corresponde a um País. Numa relação R num conjunto A, classe de equivalência de um elemento x é o conjunto de todos os elementos de A que estão relacionados com x: [x] = {y Î A: x R y} 6 11 Dois teoremas: Numa relação de equivalência R num conjunto A, "x,yÎA, [x] = [y] se e só se xRy Numa relação de equivalência R num conjunto A não vazio, a família das classes de R-equivalência distintas é uma partição de A. Exemplo: No conjunto dos números reais, xRy se e só se têm a mesma parte inteira ëxû = ëyû É uma relação de equivalência? Sim Quais são as classes de equivalência? {[n, n+1[: n Î Z} Constituem uma partição? Sim 12 Aritmética modular: A relação congruência módulo n, definida no conjunto dos inteiros, é uma relação de equivalência a ºn b se e só se a – b é um múltiplo de n Os restos da divisão de a e de b por n são iguais. Há n classes de equivalência distintas: [0], [1], ..., [n – 1] Operações em Z / n: Soma: [a] +n [b] = [a + b] Multiplicação: [a] ´n [b] = [a.b] Outro teorema: Uma partição {Si: i Î I} de um conjunto A define uma relação de equivalência: xRy se e só se $i Î I, x,y Î Si
Compartilhar