Complemento Relações e Funções

Prévia do material em texto

ESTRUTURAS DISCRETAS – Complemento - Relações e Funções - Prof. Alexandre Andreatta – 2017.2 1/9 
1 SUMÁRIO 
2 RELAÇÕES ......................................................................................................................... 1 
2.1 Relação “Congruência Módulo” ................................................................................. 1 
2.2 REPRESENTAÇÃO DE RELAÇÕES ................................................................................. 2 
2.2.1 Matriz Booleana ................................................................................................. 2 
2.2.2 Representação por Grafos .................................................................................. 3 
2.3 PROPRIEDADES DE RELAÇÕES BINÁRIAS .................................................................... 4 
2.4 FECHO DE RELAÇÕES ................................................................................................. 5 
2.4.1 Algoritmos para Fecho Transitivo ....................................................................... 5 
2.4.2 ALGORITMO DE WARSHALL................................................................................ 6 
2.5 ORDEM PARCIAL ........................................................................................................ 7 
2.6 Relações de Equivalência, Partições, e Classes de Equivalência .................................. 8 
 
2 RELAÇÕES 
 
2.1 RELAÇÃO “CONGRUÊNCIA MÓDULO” 
 
A relação congruência módulo n é a relação binária sobre os inteiros definida assim: 
R = { ( a, b ) ∈ ℤ2 : a mod n = b mod n } 
 
A congruência módulo é obviamente uma relação de equivalência, pois é 
reflexiva ( a mod n = a mod n); 
simétrica ( se a mod n = b mod n, então b mod n = a mod n ) ; e 
transitiva ( se a mod n = b mod n e b mod n = c mod n, então a mod n = c mod n ). 
 
Como a congruência módulo é uma relação de equivalência, ela define uma partição 
em ℤ, onde cada parte é uma classe de equivalência. 
Denotamos uma classe da relação mod n por: [ a ]n = { a + kn : k  ℤ } 
Ou seja, [ a ]n é o conjunto de inteiros cujo resto da divisão por n é a mod n 
 
Por exemplo, [3]7 = [-4]7 = { ..., -11, -4, 3, 10, 17, ... } 
 
O conjunto dos inteiros pode ser representado pela partição 
ESTRUTURAS DISCRETAS – Complemento - Relações e Funções - Prof. Alexandre Andreatta – 2017.2 2/9 
ℤn= { [a]n : 0  a  n-1 } 
 
Ou seja, ℤ = [0]n ∪ [1]n ∪ ... ∪ [n-1]n 
 
Sempre que esteja subentendido, num texto matemático, que a representa [a]n , 
pode-se representar o conjunto dos inteiros por ℤ = { 0, 1 , 2,  , n – 1 } 
 
2.2 REPRESENTAÇÃO DE RELAÇÕES 
 
2.2.1 Matriz Booleana 
 
Uma relação binária R em um conjunto finito A = { a1 , a2 , … , an } pode ser 
representado por uma matriz booleana MR onde cada elemento mij ( i-ésima linha, j-
ésima coluna) é 
 
Convencionamos que, se A e B são duas matrizes booleanas de mesma dimensão, e aij 
e bij são os elementos de A e B, respectivamente (i-ésima linha, j-ésima coluna), 
podemos obter a matriz C = A ∧ B tal que cada elemento cij = aij ∧ bij . Isto vale para as 
outras operações binárias também. 
Então, se R1 e R2 são relações em A = { a1 , a2 , … , an }, e MR1 e MR2 são matrizes 
booleanas representando estas duas relações, as relações R1 ∪ R2 e R1 ∩ R2 podem ser 
representadas pelas matrizes booleanas MR1 ∨ MR2 , e MR1 ∧ MR2 , respectivamente. 
Exemplo: 
 e 
 
 
Definimos também o produto de duas matrizes booleanas n × n , C = A ⨀ B , como 
sendo a matriz onde cada elemento , onde as 
ESTRUTURAS DISCRETAS – Complemento - Relações e Funções - Prof. Alexandre Andreatta – 2017.2 3/9 
operações ⋅ e + são o produto booleano (operação lógica ∧ ) e a soma booleana 
(operação lógica ∨ ) 
Por exemplo, se R e S são relações tais que suas matrizes booleanas são 
 e , então a relação S ∘ R pode ser representada 
pela matriz booleana MS ∘ R obtida por 
 
Repare que para obter S ∘ R eu devo fazer a multiplicação na ordem MR ⨀ MS . 
Em particular, para obter Rn ( ou seja, R ∘ R ∘ … ∘ R, com n operações de composição), 
devemos fazer MR ⨀ MR ⨀ … ⨀ MR , a multiplicação booleana de MR n vezes, que 
podemos denotar por MR[n] 
2.2.2 Representação por Grafos 
 
Definição: Um grafo direcionado G é uma estrutura definida por um conjunto de 
vértices (ou nós) denotado por V( G ) , e um conjunto de arcos (ou arestas) denotado 
por A( G ), tal que A( G ) ⊆ V( G ) × V( G ). 
 
Uma relação binária R em um conjunto finito S pode ser representado graficamente por 
um grafo GR onde V( GR ) = S, e A( GR) = R 
Exemplo 1 
S = { a, b, c, d }, R = { (a , b), (a , d), (b , b), (b , d), (c, a), (c, b), (d, b) } 
 
 
Exemplo 2. 
S = { 1,2,3,4 }, R = { ( 1 , 1 ) , ( 1 , 3), (2 , 1 ), (2, 3), (2 , 4) , (3 , 1 ) , (3 , 2), (4 , 1) } 
ESTRUTURAS DISCRETAS – Complemento - Relações e Funções - Prof. Alexandre Andreatta – 2017.2 4/9 
 
Exemplo 3 
S = { 1,2,3,4 }, R = {(1 , 3), ( 1 , 4), (2, 1 ), (2, 2), (2 , 3), (3 , 1 ), (3 , 3), (4, 1 ) , (4, 3)} . 
 
 
2.3 PROPRIEDADES DE RELAÇÕES BINÁRIAS 
 
Uma relação R sobre um conjunto A é irreflexiva se para cada a ∈ A, ( a, a ) ∉ R. 
 
Uma relação R é assimétrica se ( a,b ) ∈ R implica que ( b,a ) ∉ R. 
 
Seja R uma relação do conjunto A para o conjunto B. 
A relação inversa do conjunto B para o conjunto A, denotada por R-1 , é o conjunto de 
pares ordenados { ( b, a ) : ( a, b ) ∈ R }. 
A relação complementar do conjunto A para o conjunto B, denotada por R’ (ou por ) , 
é o conjunto de pares ordenados { ( a, b ) : ( a, b ) ∉ R }. 
 
Definição 
Seja R uma relação de um conjunto A para um conjunto B, e S uma relação de B para 
um conjunto C. A relação composta de R e S é a relação que consiste no conjunto de 
ESTRUTURAS DISCRETAS – Complemento - Relações e Funções - Prof. Alexandre Andreatta – 2017.2 5/9 
pares ordenados (a, c), onde a ∈ A, c ∈ C e para a qual existe um elemento b ∈ B tal que 
(a, b) ∈ R e (b, c) ∈ S. Denominamos a relação composta de R e S por S ̇∘ R. 
Se S = R, então denotamos por R2 ou por S2. 
 
Definição Seja R uma relação binária em um conjunto C 
Se ( a, b ) ∈ R, podemos dizer que a pôde alcançar b com apenas um passo. 
Se ( a, b ) ∈ R2, podemos dizer que a pôde alcançar b com dois passos, porque deve 
existir um elemento c ∈ C tal que ( a, c ) ∈ R e ( c, b ) ∈ R. 
Se ( a, b ) ∈ R3, podemos dizer que a pôde alcançar b com três passos, porque deve 
existir um elemento c ∈ C tal que ( a, c ) ∈ R2 e ( c, b ) ∈ R. 
Então, dizemos que a alcança b com k passos quando ( a, b ) ∈ Rk . 
 
Teorema Se o conjunto C tem n elementos, e ( a, b ) ∈ Rk , a ≠ b , então k < n; 
e se ( a, a ) ∈ Rk , então k ≤ n. 
Prova 
Suponha que a alcança b , a ≠ b, e k = n, então , supondo e0 = a e en = b temos 
( e0, e1 ) ∈ R , ( e1 , e2 ) ∈ R, ( e2 , e3 ) ∈ R,… , ( en-2 , en-1 ) ∈ R, ( en-1, en ) ∈ R, onde cada ei ∈ C. 
Isto significa que existe algum par i, j , i < j , tal que ei = ej . Então 
( e0, e1 ) ∈ R , ( e1 , e2 ) ∈ R,…, ( ei-1 , ei ) ∈ R, ( ei , ei+1 ) ∈ R,…, ( ej-1 , ei ) ∈ R,…, ( en-1, en ) ∈ R, 
e podemos encurtar o caminho 
( e0, e1 ) ∈ R , ( e1 , e2 ) ∈ R,…, ( ei-1 , ei ) ∈ R, ( ei , ej+1 ) ∈ R,…, ( en-1, en ) ∈ R, 
Ou seja, ( a, b ) ∈ Rm com m < k, o que contradiz o fato de que a deve alcançar b com k 
passos. 
Entretanto, se b = a, só teremos a necessidade de algum par i, j , i < j , tal que ei = ej 
quando k = n+1 
fim-prova 
 
2.4 FECHO DE RELAÇÕES 
 
2.4.1 Algoritmos para Fecho Transitivo 
 
O Fecho transitivo de uma relação R em um conjunto C é dado por 
 
Então, se MR é a matriz booleana que representa R, temos que 
 
ESTRUTURAS DISCRETAS – Complemento- Relações e Funções - Prof. Alexandre Andreatta – 2017.2 6/9 
Exemplo: 
 
 
 
 
Então, podemos descrever um algoritmo para obter o fecho transitivo de uma relação R 
representada por uma matriz booleana assim: 
algoritmo fechoTransitivo( MR ) // matriz booleana n × n 
 A ← MR ; 
 B ← A ; 
 para i = 2 até n faça 
 A ← A ⨀ MR ; 
 B ← B ∨ A ; 
 fim-para 
fim-algoritmo 
 
2.4.2 ALGORITMO DE WARSHALL 
 
Dada uma relação R em um conjunto { 1,2,3,…, n }, gostaríamos de determinar o fecho 
transitivo de R. Isto significa que, em R*, para cada par ( i, j ) ∈ R*, é possível que i 
alcance j em até n passos (utilizando até n-1 vértices distintos de i e j como 
intermediários). O algoritmo de Warshall trabalha com a ideia de, dada a matriz 
booleana MR que representa R, construir a matriz de alcançabilidade que representa R* 
iterativamente, disponibilizando um a um os vértices que podem fazer parte do 
caminho. 
Suponha que exista um caminho P entre i e j utilizando como intermediários somente 
elementos do conjunto {1, 2, ...,k}. 
ESTRUTURAS DISCRETAS – Complemento - Relações e Funções - Prof. Alexandre Andreatta – 2017.2 7/9 
Se o elemento k não estiver no caminho P, então P utiliza somente elementos em 
{1,2,...,k-1}. 
Se k é um intermediário em P, então existe um subcaminho P1 de i até k, e um 
subcaminho P2 de k até j. Neste caso, P1 é um caminho que utiliza como intermediários 
somente elementos do conjunto {1,2,...,k-1}. O mesmo acontece com P2 em relação aos 
elementos k e j. 
 
Seja Wk é a matriz booleana que representa a alcançabilidade de todos os elementos 
utilizando somente elementos do conjunto {1,2,...,k}. Então, cada elemento W[ i][ j ] de 
Wk pode ser determinado assim: 
 
 
A expressão reflete se i alcança j com k – 1 intermediários ou com menos do que isto. 
 
algoritmo Warshall( matriz booleana MR ) // o fecho vai ficar em W também 
1 W  MR ; 
2 para k  2 até n faça 
3 para i  1 até n faça 
4 para j  1 até n faça 
5 se ( W[i ][ k] = 1 ∧ W[k ][ j] = 1) então W[i ][ j]  1 ; fim-se 
 fim-para fim-para fim-para fim-algoritmo 
 
Não há necessidade de se manter n matrizes representando as relações R1, R2, …, Rn, 
conforme está indicado na expressão recursiva que fundamenta o algoritmo. Isto pode 
ser demonstrado analisando-se as duas formas alcance de i para j: ou o alcance foi feito 
com intermediários em { 1, 2, … , k – 1}, aí Wk[i ][ j] = Wk-1[i ][ j], obtido na iteração 
anterior, ou o elemento k foi usado, e Wk-1[i ][ k] = Wk-1[k ][ j] = 1 
 
2.5 ORDEM PARCIAL 
 
Quando se fala de forma genérica de um ordem parcial qualquer em um conjunto S, é 
comum usar o símbolo ≼ para denotá-la. Então, para representar um conjunto 
parcialmente ordenado ( c.p.o. ) usamos o par ( S, ≼ ). O símbolo ≼ é particularmente 
conveniente porque lembra o símbolo ≤ que representa uma ordem parcial nos 
conjuntos de números. De fato, por analogia, utiliza-se o símbolo ≺ para representar 
uma relação tal que a ≺ b ⟺ a ≼ b ∧ a ≠ b 
ESTRUTURAS DISCRETAS – Complemento - Relações e Funções - Prof. Alexandre Andreatta – 2017.2 8/9 
 
Suponha que temos um conjunto parcialmente ordenado (A, ≼ ). Podemos definir uma 
ordem lexicográfica no conjunto SA de strings de elementos de A, da seguinte maneira: 
Se | s | = | t | = n 
 
Se | s | < | t | , s ≼ t 
 
Definição – elementos comparáveis 
Dado um conjunto parcialmente ordenado ( S , ≼ ), e { a, b } ⊆ S, dizemos que estes 
elementos de S são comparáveis se a ≼ b ou b ≼ a. 
 
Definição – Limite Superior e Limite Inferior de um subconjunto A ⊆ S de um 
conjunto parcialmente ordenado ( S, ≼ ) 
Dizemos que x é limite superior de A em ( S, ≼ ) se a ≼ x, para cada a ∈ A; e 
Dizemos que x é limite inferior de A em ( S, ≼ ) se x ≼ a , para cada a ∈ A; 
 
Exemplo 
 
Se A = { a, b, c } , então e, f, j, e h são limites superiores de A 
Se A = { h, j , f } , então e, b, a, c são limites inferiores de A 
 
2.6 RELAÇÕES DE EQUIVALÊNCIA, PARTIÇÕES, E CLASSES DE EQUIVALÊNCIA 
 
Definição – Refinamento de Partição 
Dizemos que uma partição P de um conjunto S é um refinamento de uma partição Q 
do mesmo conjunto S se cada conjunto p ∈ P é subconjunto de algum conjunto q ∈ Q. 
ESTRUTURAS DISCRETAS – Complemento - Relações e Funções - Prof. Alexandre Andreatta – 2017.2 9/9 
FUNÇÕES 
 
Definição – Imagem de um subconjunto do Domínio 
Seja f uma função do conjunto A sobre o conjunto B. Seja S um subconjunto do domínio 
B. Definimos a imagem de S como sendo o subconjunto de B cujos elementos são 
imagens da aplicação de f sobre os elementos de S. 
f( S ) = { y ∈ B : ∃ x ∈ S tal que f( x ) = y } 
 
Definição – Imagem Inversa de um subconjunto do Contra-Domínio 
Seja f uma função do conjunto A sobre o conjunto B. Seja S um subconjunto do contra-
domínio B. Definimos a imagem inversa de S como sendo o subconjunto de A cujos 
elementos têm imagem de f em S. 
f -1( S ) = { x ∈ A : f( x ) ∈ S } 
 
Definição – Função Parcial e Função Total 
Uma função f de A em B é uma função total se simplesmente ela é uma função tal 
como o conceito foi definido. 
Dizemos que f é uma função parcial de A em B se existe um subconjunto S ⊆ A tal que 
todo x ∈ S não está no domínio de f, e neste caso dizemos que a função não é definida 
para os elementos de S. 
O uso da denominação função parcial é uma conveniência para falar de um domínio 
restrito de uma forma mais ampla, sem se preocupar em dizer que a função não é 
definida para tais e tais elementos. Repare que toda função total é uma função parcial. 
Em alguns contextos, quando necessário (na definição de um programa, por exemplo), 
é conveniente transformar uma função parcial f de A em B em uma função total f * 
definida assim: 
f *( a ) = f ( a ) quando f é definida para a ( isto é, quando a está no domínio de f ) 
f *( a ) = u quando f não é definida para a 
onde u ∉ B, é escolhido de forma deliberada 
 
Definição – Função Característica 
Seja S um subconjunto de U. A função característica fS de S é a função de U em {0,1} tal 
que f( x ) = 1 se x ∈ S, e f( x ) = 0 se x ∉ S.