Definição: uma relação binária R entre domínios A e B é um subconjunto de A × B. Ou seja, determina pares ordenados (x, y) que satisfazem uma determinada propriedade. Assim, R ⊆ A × B.
Observação: as relações não precisam atuar apenas no mesmo conjunto; podem ligar elementos de conjuntos diferentes (relações entre conjuntos), quando R ⊆ A × B.
Tipologia comum de relações: podem ser 1–1 (função), 1–para–muitos, muitos–para–1 ou muitos–para–muitos, dependendo de quantos pares com um dado elemento aparecem.
Exemplo simples: considere A = {1,2,3} e B = {a,b}. Uma relação R = {(1,a), (2,b)} é uma relação binária entre A e B. Observamos que 1 se relaciona apenas com a, 2 com b, etc.
Observação prática: ao trabalhar com funções, estamos lidando com relações especiais que são do tipo “um elemento de A está relacionado com exatamente um elemento de B” (1–para–1, ou em geral função parcial/total).
Uma relação R em A é reflexiva se, para todo x ∈ A, (x, x) ∈ R. Em outras palavras, todo elemento está relacionado consigo mesmo.
Exemplo: a relação “≤” em Naturais é reflexiva, pois para todo x, x ≤ x.
R é transitiva se, sempre que (x, y) ∈ R e (y, z) ∈ R, então (x, z) ∈ R.
Exemplo: novamente a relação “≤” em naturais é transitiva: se x ≤ y e y ≤ z, então x ≤ z.
R é simétrica se, sempre que (x, y) ∈ R, então (y, x) ∈ R. Nem toda relação é simétrica.
Exemplo: a relação “x e y têm a mesma idade” é simétrica: se x tem a mesma idade de y, então y tem a mesma idade de x. Já a relação “x ≤ y” não é simétrica (pode haver x ≤ y sem ter y ≤ x).
R é antissimétrica se, sempre que (x, y) ∈ R e (y, x) ∈ R, então x = y. Não é o oposto de simétrica; é uma condição diferente. Uma relação pode ser simétrica e antissimétrica apenas no caso em que os elementos são iguais.
Exemplo clássico: a relação de divisibilidade “x divide y” em N é antissimétrica: se x | y e y | x, então x = y.
O fecho de uma relação P dentro de um conjunto S é o menor subconjunto de uma relação R que contenha P e satisfaça a propriedade desejada.
Constitui o menor conjunto que contém P e torna a relação reflexiva adicionando (x, x) para todo x que pertença ao domínio. Exemplo: dada R = {(1,2), (2,3)} sobre {1,2,3}, o fecho reflexivo é {(1,2),(2,3),(1,1),(2,2),(3,3)}.
Para tornar a relação simétrica, adicionamos (y, x) sempre que (x, y) ∈ R. Exemplo: se R = {(1,3)} sobre {1,2,3}, o fecho simétrico é {(1,3),(3,1)} (e, se necessário, pares adicionais para manter a consistência).
Para tornar R transitiva, adicionamos (x, z) sempre que existirem (x, y) e (y, z) em R. O fechamento transitivo pode exigir adicionar vários pares e pode exigir novas combinações para manter a transitividade até não haver mais novas adições. Exemplo simples: se R = {(1,2),(2,3)}, o fecho transitivo contém (1,3) além dos pares originais.
Uma relação binária em um conjunto S que é reflexiva, antissimétrica e transitiva é chamada de ordem parcial em S.
O exemplo clássico é a relação de divisibilidade “|” em N: x | x (reflexiva), se x | y e y | x então x = y (antissimétrica), e se x | y e y | z então x | z (transitiva).
Se x ≤ y e x ≠ y, diz-se que x é o predecessor (ou antecessor) de y, e y é o sucessor de x. Além disso, existe o conceito de predecessor imediato, que é o predecessor de y sem nenhum z com x < z < y.
A visualização gráfica (diagrama de ordem) ajuda a ver as relações de precedência; Pode-se usar diagramas de Hasse (diagramas de raiz) para simplificar, omitindo os pares reflexivos e os arcos redundantes.
Se a ordem parcial também garante que qualquer par de elementos seja comparável (para quaisquer x, y em S, ou x ≤ y ou y ≤ x), ela é chamada de ordem total (ou linear). Em uma ordem total, cada elemento pode ser colocado em uma linha de forma que a relação de precedência fique visível com uma linha contínua.
Em uma ordenação parcial, um elemento máximo não tem sucessor no conjunto, e um elemento mínimo não tem predecessor. Um conjunto pode possuir zero, um ou mais máximos (e mínimos) simultaneamente.
Uma relação R em S é de equivalência se for reflexiva, simétrica e transitiva. Cada elemento x de S define uma classe de equivalência [x] = {y ∈ S | (x,y) ∈ R}. Essas classes formam uma partição de S: são subconjuntos disjuntos cujos união é S.
Propriedade fundamental: uma relação de equivalência em S determina uma partição de S, e uma partição de S determina uma relação de equivalência, por meio das classes de equivalência.
Um caso clássico de relação de equivalência é a congruência módulo n em Z: x ≡ y (mod n) se e somente se n | (x − y). Isso particiona Z em classes de equivalência [0], [1], ..., [n−1], chamadas de classes residuais.
Exemplo com n = 5, Z dividido por 5 resulta nas quatro classes representadas por 0, 1, 2, 3, 4 (cinco classes distintas): cada inteiro pertence a uma dessas classes.
Principais observações: a partição e a relação de equivalência são duas faces da mesma ideia — dividir o conjunto em blocos não sobrepostos; cada bloco é uma classe de equivalência, e cada par de elementos no mesmo bloco está relacionado pela relação.
Baseado no conteúdo apresentado, qual afirmação é verdadeira sobre relações binárias?
Resposta correta: B) Uma relação binária pode relacionar elementos de dois conjuntos diferentes (R ⊆ A × B).
Observação: Relações podem ligar elementos de domínios distintos; quando isso ocorre, diz-se que é uma relação entre conjuntos diferentes.
Considere a relação de divisibilidade “x divide y” (x | y) no conjunto N. Qual das afirmações é verdadeira?
Resposta correta: B) A relação é reflexiva, transitiva e antissimétrica.
Justificativa: x|x para todo x (reflexiva); se x|y e y|x implica x = y (antissimétrica); se x|y e y|z implica x|z (transitiva).
Sobre o fecho de uma relação, qual é a definição correta do fecho reflexivo de R ⊆ S × S?
Resposta correta: A) O fecho reflexivo é a menor relação que contém R e que é reflexiva.
Justificativa: o fecho reflexivo adiciona os pares (x, x) necessários para tornar a relação reflexiva, mantendo o mínimo de novos pares.
Considere a relação de congruência módulo n em Z. Qual das afirmações é verdadeira?
Resposta correta: A) Existem exatamente n classes de equivalência em Z sob congruência módulo n.
Justificativa: as classes de equivalência são [0], [1], ..., [n−1], total de n classes. Além disso, cada inteiro pertence a exatamente uma dessas classes.
Colar alunas e alunos do procedimento de os matemáticos para a computação, na estovidóloga, eu vou falar de relações binários.
Vou começar estabelecendo conceitos de relações binárias, preen seguida apresentar as propriedades de relações e introduzir, portanto os conceitos de fechos de uma relação ordem parcial e relações de equivalência.
Uma relação binária, que se a gente considera esse domínio por esses espários ordenados, uma relação binária vai estabelecer uma propriedade entre alguns desses elementos, como por exemplo, que x-menu aqui y.
Então, nós temos que a relação rô é representada por x-menu aqui y e definem um subconjunto dentro desse domínio.
Dessa forma, nesse subconjunto, nós passamos a identificar aqueles que atendem a propriedade rô, da relação rô, que nesse caso seria um, dois, três, quatro.
E aí, a própria relação é definida com um subconjunto formado por esses elementos, que se a que se fazem a propriedade x-menu aqui y.
Dessa forma, eu posso ter uma relação estabelecida como aqui através de uma propriedade rô, tem mais que x mais y em ímpa e aí eu verifico que os pássios um, dois e dois, um atendem para esse domínio e eu posso ter estabelecida desse jeito.
Simplesmente, acho que estabelece uma relação que contém esses dois pontos por algum motivo e nesse contexto com um, dois esse para ordenado não pertence a relação.
Não, as relações, elas não são estabelecidas só no produto caso deseando de um mesmo conjunto.
Eu posso ter a relação entre conjunto diferentes, na mesma forma que eu posso ter uma relação entre ele e conjunto diferentes, que daí é chamada de relação enriária.
Uma característica das relações, uma propriedade, eu vou se ter as relações do tipo 1 para 1, identificadas como do tipo 1 para 1, que relaciona um elemento de 1, com o conjunto, com o elemento de outro conjunto, eu posso ter uma relação do tipo muitos para 1, ainda que eu tenho uma relação 1 para 1, como aqui nesse desenho.
Então, eu posso ter uma relação 1 para muitos.
Eu posso ter uma relação muitos para 1 e posso ter uma relação muitos para muitos.
Então, é interessante essas características de como você relaciona esses dois conjuntos de valores, porque isso vai na jogo de chamar atenção para isso, nós temos um introduzendo conceito de funções na próxima aula.
Bom, as propriedades dessa de relações, temos aqui a propriedade, vamos começar pela propriedade reflexiva que diz o seguinte, se x pertence ao domínio, a relação xx tem que ocorrer para ser x que está relacionado com x, para ser, para se você considerar uma relação binária tipo reflexiva.
Para se se metem, se x y pertence a relação com y x também pertence a relação.
E para ser transitiva, se x y pertence a relação e y z pertence a relação x e pertence a relação.
Vamos ver isso com exemplos.
Então, considera que uma relação binária no conjunto dos naturais do tipo x menor é igual a y com essa propriedade.
Então, essa relação é a R reflexiva.
Por quê? O parte x atende essa relação, já que x é igual a x, então, o ópti x é menor é igual a x atende a relação, ela é reflexiva.
Ela também é transitiva, por quê? Porque se x y pertence a relação e y pertence a relação, eu vou ter x menor é igual a x, y menor é igual a z, e consequentemente x menor é igual a z.
Então, essa propriedade, essa transitividade vale no conjunto dos naturais.
Por outro lado, ela não vai ser uma relação sinétrica.
Por quê? Porque isso implicaria em x y pertence a pt c rô e y x pertence a rô para todo y para todo x.
Para isso, para provar que não é, voltamos aquele conceito de contras.
O basta eu mostrar uma situação em que não funciona.
3, 4 para o ordenado 3, 4.
Ele pertença essa relação binária, 3 é menor é igual a 4, porém, 4, 3, que já não vai ser de seus e isso.
São fatos, não precisa provar que 4 é menor é igual a 3.
Então, eu tenho que isso me leva a mostrar que essa propriedade não é satisfeta por esse contras.
Então, ela não é simétrica.
Um outro conceito, uma outra propriedade é a de relação anti-symétrica, que diz o seguinte, se x e pt c na pertence a relação, e y x pertence a relação, x tem que ser igual a y para ela ser classificada com no anticemétrica.
E aqui, um cuidado, porque a gente pensa em anticemetria, você pode pensar em anticemetria como o contrário de simetria, isso não é verdade.
Uma relação pode ser simétrica e anticemetrica.
Por exemplo, uma relação que tem a íbola x pertence a roupa, ela é simétrica, e ela é anticemétrica se o x for igual a y.
Nesse caso, então, essa relação tem que estabelecer essa igualdade entre a necessidade dessa igualdade entre x e y.
Uma relação anti-symétrica, a gente também tem que tomar cuidado com ela no seguinte sentido dessa exclusão, né? A anticemétrica, então ela vai ser simétrica.
Não é bem assim.
Nesse caso, dessa relação aqui, que está pontuado dos elementos de roupa, estão pontuados dos elementos de roupa.
Então, ela não é simétrica, porque um, três pertence a roupa e três um não pertence.
E ela não é anticemétrica, porque um e dois pertence a roupa, dois um pertence a roupa, mas um é diferente de dois.
Então, ela não é simétrica e não é anticemétrica.
Uma par relação binária, ela vai ser chamada de texto em conjunto S, quando ela tem a seguinte propriedade.
O fecho, ele tem uma propriedade P, que ele estende a partir da relação rook, passa ser um subconjunto do fecho.
E o fecho, por sua vez, vai ser um subconjunto de qualquer outra relação, relação em S, que inclua P e a propriedade sob consideração.
Vamos ver isso com um exemplo.
Nós temos aqui essa relação rook, ela não é reflexiva, nem simétrica, nem transitiva.
Então, vamos estabelecer o fecho reflexivo dela.
Então, reflexividade é a propriedade sob consideração.
Para essa relação se tornar reflexiva, eu tenho que adicionar.
Eu já tenho um, eu teria que adicionar dois, dois e três, três.
Então, agora, o obitivo fecho se reflexivo da relação rook.
Eu soube conjunto desse fecho, e qualquer relação reflexiva em S, tem que conter os novos pares ordenados.
Então, dessa forma, qualquer relação reflexiva contendo rook tem o fecho com o subconjunto.
Bom, agora, fica fácil a gente ver também, que ela vai se pre.
.
.
Eu obtei o fecho simétrico, né? Eu vou ter que olhar para essa relação e identificar o que falta para a simetria.
Bom, nesse caso, eu tenho um, três, três, um, mas eu tenho um, dois, eu não tenho dois um.
Não tenho dois, três, não tenho três dois.
Tranquilo, estabelece um fecho simétrico.
Para fazer o fecho transitivo, o que vai acontecer? Mesma coisa, eu vou olhar aqui, eu vou verificar que eu consigo inferir.
Três dois, né? A partir de três um e um, dois, eu chego em três dois.
Da mesma forma, eu consigo inferir três, três e dois um, os demais pares.
Só que isso está em completo, porque é a uma adicionar, eu caimic, numa reconheência.
Ao adicionar esses pares, eu tenho que verificar se eles também não geram uma nova transitividade.
E é o que ocorre para dois dois que eu obtido a partir desses pares.
No caso aqui, do dois um e do um, dois, eu infero dois dois, por exemplo.
Bom, dessa forma, passamos agora para o conceito de ordem parcial.
Então, uma relação binária em conjunto, esse, que seja reflexiva, anti-cinétrica.
E transitiva é chamada de uma ordem parcial em S.
Uma relação binária, ela vai ser classificada como uma ordem parcial, quando atendesse as três propriedades, que é o caso do x dividido.
Por exemplo, para qualquer elemento x nos inteiros positivos, eu vou ter que x dividir o x dividi x.
Então, vai ser reflexiva.
Provei isso.
Ela vai ser anti-cinétrica, por quê? Porque se y dividi x, então y é o último de x.
E se x dividir, e se y dividir x, então, eu vou ter que x é um múltiplo de y.
E aí, o que vai acontecer nesse caso? Partindo do supondo, então, essa hipótese de que o x, o y dividir o x, ou seja, ele é um múltiplo de x.
Como x também é um múltiplo de y, eu tenho que y é um múltiplo e, mesmo, só vai ocorrer, se dá e a forem igual a 1 nesse domingo.
O que significa que a sendo 1, eu tenho y é igual a x.
Está provado.
A transitividade é a mesma coisa.
Se o x dividir, então, y é um múltiplo de x, e se o y dividir z é um múltiplo de y, usando essas informações, eu tenho que usar ele escrito, como y vezes b, que, por sua vez, vai ser x vezes a, já que o y é um múltiplo de x, o que me leva a z ser descrito com x vezes 1 inteiro.
E aí, consequentemente, o x dividir z.
Bom, nesse caso, a ordem parcial, para ilustrar esse ordenamento parcial, eu tenho aqui a ordem parcial estabelecida, a relação que é uma ordem parcial com todos os pares envolvidos.
E aí, algumas características interessantes.
Se nós tivermos que x obedece essa propriedade de uma relação que é uma ordem parcial em relação ao número y, ao valor y, mas o x é diferente de y, nós podemos escrever como x sendo predecesor de y, e consequentemente, y é um sucessor de x, desde que eles sejam diferentes.
Então, observe que, um número pela reflexividade, ele vai ser igual a ele mesmo, ou pela anitimetria, se x se relacionar com y, ele não vai poder relacionar de volta a y com x, então, eles vão ter que ser diferentes.
E eu vou ter a transitividade.
Então, essa questão da anitimetria me leva a perceber que, se o x foi diferente de y, então, eu tenho uma ordem estabelecida do x em relação a y.
E já já, a gente vai visualizar isso através do gráfico.
Então, se x é um predeceso do seu de y, e não existe nenhum z, então, entre o x e o y, o x é um predeceso imediato de y.
Vamos plorar isso.
Considerando aqui esse exemplo de ordem parcial, nós temos que os predecesores de 6 vão ser 1, 2, 3.
Onde, nesse caso, o predecesor imediato de 6 vai ser 2, 3.
O 1 não vai ser porque tem 2 entre eles, ou 3.
Certo? Nessa relação.
Isso fica muito mais simples de visualizar através do diagrama de raiz, que é composto pelos elementos e as relações entre eles.
Então, 1 se relaciona com 2 e com 3, de vídeo 2 e de vídeo 3.
O 2 e o 3 dividem 6.
O 6 dividem 2 e o 18.
E, consequentemente, pela reflexividade um dividi-lhe mesmo, 2 dividi-lhe mesmo e assim podiante, pela transitividade, se 1 dividi 3 e 3 dividi 6, 1 dividi 6, então nós temos, e a antecimetry é testa-belecida aqui.
Não tem a relação 3 levando para 1.
Então, entra aqui para cá.
Nesse caso, nós temos uma representação visual de onde você consegue inferir todas as relações desse.
.
.
dessa relação binária, que é uma ordem para se estabelecer, uma ordem parcial.
Nessa relação x menor e igual a y, a pessoa verifica que ela, que se chama de uma ordemação total, porque você vai ter simplesmente predecesores e sucessores ligados através dessa relação de menor e igual, que é bastante intuitivo.
Bom, então, isso tudo, numa ordem voltando agora para um diagrama aqui, nós vamos identificar os elementos maximais e elementos mínimais.
O que que seria o elemento máximo? O elemento.
.
.
os elementos maximais, eles não têm nenhum predecesor, nenhum sucessor, desculpa, nenhum sucessor.
Por um elemento, isso seria definição dos elementos maximais.
Por um elemento, ser um elemento máximo, ele teria que ser o sucessor de todos os demais elementos.
Então, ele teria.
.
.
nós teríamos o único elemento que sucede todos os demais.
Nesse caso, aqui não, nós temos dois elementos sucedentes, todos os demais e eles são os elementos maximais.
Não temos um elemento máximo.
Mesmo aqui já muda, que nós temos um elemento mínimo, nós temos um elemento que é predecesor de todos os demais e, da mesma forma, ele é um elemento mínimo, porque ele não tem ninguém precedendo ele.
Então, observe que nós podemos ter elementos aqui que não têm sucessores, mas eles não representam um elemento máximo, enquanto aqui nós temos um elemento mínimo, que também é um elemento mínimo.
Bom, uma relação binária vai ser chamada.
.
.
quando ela tem de a reflexividade, se metri transitividade, ela é chamada de relação de equivalência.
Então, nesse caso, o x mais y, por exemplo, ele é uma relação de equivalência, porque se eu sou mais x mais x, eu vou ter um número par, se x y é par, e eu mudasse a soma para y mais x, ela continua par, se x y é par e y z é par, e y mais z é par, se eu fizer essa troca aqui, x, eu adotasse a representação, x igual a 2a menos y, e eu resolvi subtrair menos 2a, do lado esquerdo, e direito da relação y mais y, eu não exbe, o que eu vou ter? Eu apareço com x, no lugar de y menos 2a, x mais y, e no lado direito, eu vou ter 2b menos 2a, que nada mais é do que é um número par.
Então, x mais y é par.
Bom, qual que é a característica dessa relação de equivalência? Ela define partições.
Então, uma partição de um conjunto s, ela é uma coleção de subconjuntos de juntos, ou seja, que não tem elementos incomum.
E aí, eu congego no conceito de classe de equivalência, porque para representar esses conjuntos de juntos, eu escolho um elemento x de modo a pegar todos os y que se relacionam com ele.
Em boa.
Então, nesse caso, o que eu vou ter? Eu vou ter um teoreno aqui disso seguinte.
Uma relação de equivalência ro, em um conjunto s, determina uma parte, são ela particiona s.
E uma partição de s, determina uma relação de equivalência em s.
Então, o que vai acontecer? Quando estabeleço uma relação, que nem aquela parte, nós vimos que é uma classe de equivalência, ela separa o universo, digamos assim, eu vou ter agora valores pares e valores não pares, valores íntanes.
Então, eu tenho aqui uma partição estabelecida por essa relação de equivalência.
Bom, outro caso disso é quando a gente pensa no conceito de congruência, é modo n.
Então, eu tenho x e y inteiros e n inteiro positivo, e você falar e usa-se essa lotação.
Que x é congruência, tipo, o modo n, significa que x menos y é um múltiplo de inteiro de n.
E o que significa isso? Significa que eu consigo.
Então, se eu pegar, por exemplo, o n como 5, eu vou ter x menos y, que são múltiples de 5, criando uma partição no domínio dos inteiros.
E quais são essas partições? São essas aqui.
Essas são todas as partições possíveis.
Elas vão só até 4.
Por quê? Vamos ver isso.
Quando eu começo com o zero, quando eu escolho zero para representar uma partição, uma classe de equivalência, ele tem que atender a propriedade de ser congruente o modo no 5.
Isso significa que seu múltiplo de 5.
Então, eu vou ter todos os x e y lançando com esse zero de modo a c, múltiplo de 5.
E aí, eu tenho essa formulinha para gerar essa classe de equivalência quira.
Perfeito.
Para x menos 1, para uma mesma coisa, vou ter x menos 1, passo para outro lado, eu tenho essa formulinha para gerar.
Repare que se eu fizer 6 menos 1, vai dar 5.
É múltiplo de 5.
O mesmo vai agulhar por que demais? Bom, o 2, a mesma coisa.
E assim vai até o 4.
Quando chega no 5, qualquer acontece.
Eu vou ter, passando 5 para outro lado, eu vou ter colocando 5 em evidência, eu recaio no caso anterior aqui do zero.
Eu recaio na classe de equivalência zero.
E o mesmo vai acontecer para 6, vai acontecer para 7, você vai recair numa dessas 4 classes que a gente viu no ex-médio anterior.
É certo? Bom, dessa forma é uma aula com bastante conceitos, mas são conceitos que, quando enunciados parecem complicados, mas que quando a gente vê os exemplos, isso dá um bom bem mais simples.
Muito obrigado, leio a acessar o 5.
1 do nosso material base e nos vemos na próxima aula.