Conjuntos, Relações e Funções

Prévia do material em texto

ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 1/23 
 
 
Sumário 
1 TEORIA DOS CONJUNTOS – CONCEITOS BEM BÁSICOS ...................................................... 2 
1.1 Lista ou tupla ............................................................................................................. 3 
1.2 Conjunto finito de inteiros positivos .......................................................................... 3 
1.3 Técnicas de demonstração – conceitos bem básicos .................................................. 3 
2 RELAÇÕES ......................................................................................................................... 5 
2.1 RELAÇÃO BINÁRIA R DE S EM T. CLASSIFICAÇÃO ........................................................ 6 
2.2 PROPRIEDADES DE RELAÇÕES BINÁRIAS .................................................................... 7 
2.3 FECHO DE RELAÇÕES ................................................................................................. 9 
2.4 ORDEM PARCIAL ...................................................................................................... 11 
2.4.1 Diagrama de Hasse........................................................................................... 11 
2.5 Relações de Equivalência, Partições, e Classes de Equivalência ................................ 12 
3 FUNÇÕES......................................................................................................................... 14 
3.1 PROPRIEDADES DAS FUNÇÕES ................................................................................. 15 
3.1.1 Composição de Funções ................................................................................... 16 
3.2 FUNÇÕES DE INTEIROS............................................................................................. 18 
3.2.1 Funções Piso e Teto ......................................................................................... 18 
3.2.2 Aplicações Funções Piso e Teto ........................................................................ 18 
3.2.3 Operação módulo ............................................................................................ 22 
 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 2/23 
 
1 TEORIA DOS CONJUNTOS – CONCEITOS BEM BÁSICOS 
 
Conjuntos são coleções de objetos. Mas que objetos? Podem ser números, podem ser 
coisas, podem ser conjuntos de coisas, etc. Portanto, é natural definir antes de quais 
objetos estamos falando. Normalmente esta definição está implícita no próprio tema 
que estamos discutindo. Em teoria de conjuntos esta definição é feita através da 
especificação do conjunto universo 𝒰 , ou universo do discurso. 
 
Subconjunto A do conjunto B 
A é subconjunto de B (ou contido em B), denotado por A  B, se, e só se, 
Se x  A, então x  B. 
Todos os conjuntos são subconjuntos do conjunto universo 𝒰 
 
Subconjunto próprio A do conjunto B 
A é subconjunto próprio de B (ou contido propriamente em B), denotado por A  B, 
se, e só se, 
quando x  A, então x  B e, além disso,  x  B tal que x  A 
Em outras palavras, A  B se A  B e A  B 
 
Conjunto Complementar 
O conjunto complementar de A é definido por 𝒰 – A e normalmente denotado por A¯ 
𝒰 = A ∪ A¯, qualquer que seja A  𝒰 
 
Cardinalidade de um conjunto A é o número de elementos que pertencem ao 
conjunto, e é denotado por | A | . Se o conjunto é infinito, como ℕ por exemplo, |ℕ| = 
 
Diferença entre dois conjuntos A e B 
x  A – B = A\B se, e somente se, x  A e x  B 
 
Diferença simétrica entre dois conjuntos A e B 
x  A  B se, e somente se, x  A \ B ou x  B \ A 
Ou seja, A  B = (A – B) ∪ (B – A) = (A ∪ B) – (A ∩ B) 
 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 3/23 
 
 
x  𝒰 – ( A ∪ B ) = (A∪B) 
y  (A – B)  A 
w  A ∩ B 
z  (B – A)  B 
{ y,z }  A  B = (A ∪ B ) – (A ∩ B) 
 
1.1 LISTA OU TUPLA 
 
Uma lista de elementos é diferente de um conjunto de elementos. Numa lista, está 
implícita uma ordem de apresentação que a caracteriza, enquanto em um conjunto não 
existe esta exigência. 
Numa lista é possível ter elementos duplicados, enquanto que num conjunto isto não é 
permitido. 
Por exemplo, supondo x  y, ( x , y ) é uma lista de dois elementos, e { x,y } é um 
conjunto de dois elementos. Mas, { x,y } = { y,x }, enquanto ( x,y )  ( y,x ). 
 
Uma lista de k elementos é denominada usualmente como uma k-tupla. 
Se k = 2 , a lista é uma dupla ou uma 2-tupla. 
Se k = 3, a lista é uma tripla ou uma 3-tupla. 
Se k = 4, a lista é uma quádrupla ou uma 4-tupla. etc.. 
 
1.2 CONJUNTO FINITO DE INTEIROS POSITIVOS 
 
O conjunto { 1, 2, 3 , ... , n } é denotado por [ n ] 
 
1.3 TÉCNICAS DE DEMONSTRAÇÃO – CONCEITOS BEM BÁSICOS 
 
Suponha que você queira demonstrar que 
“Se P é verdade, então Q é verdade” 
Denotamos esta proposição pela implicação P  Q 
Chamamos P de premissa ou hipótese, chamamos Q de conclusão ou conseqüência. 
Para provar que P implica Q há diversas possibilidades: 
U (conjunto universo) 
A B 
B – A 
A∩B 
A – B 
• y 
• x 
• w 
• z 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 4/23 
 
1) Partindo da premissa P, e de uma série de fatos que você lembrou e assume 
como verdadeiros (premissas normalmente não explicitadas na apresentação do 
problema) H1 , H2 , ... , Hn , você utiliza uma série de deduções até chegar em Q. 
Isto se chama demonstração direta. 
2) Provar que P  Q, é o mesmo que provar que P é condição suficiente para Q 
ser verdade. Então, se Q não é verdade, significa que P não é verdade. Isto é o 
mesmo que provar que “Se Q é falso, então P é falso”, ou, numa notação de 
lógica,  Q   P. Então podemos provar P  Q por dedução direta da 
implicação equivalente  Q   P. Esta técnica de demonstração é denominada 
demonstração por contraposição ou demonstração contrapositiva. 
3) Novamente, provar que P  Q, é o mesmo que provar que P é condição 
suficiente para Q ser verdade. Então, caso esta implicação seja verdadeira, é 
impossível termos P verdadeiro e Q falso ao mesmo tempo. A demonstração 
por contradição ou demonstração por absurdo consiste em assumir que P é 
verdade e Q é falso e obter, por meio de uma série de deduções, algum fato que 
seja contraditório a alguma premissa tomada como correta no início da 
demonstração. 
 
 
 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 5/23 
 
2 RELAÇÕES 
 
O conjunto S é denominado conjunto subjacente da relação R. 
Qualquer conjunto de pares ordenados de elementos de S é uma relação binária em S. 
Então, dois elementos de S, por exemplo x e y, se relacionam por R se, e só se, (x,y) R. 
 
Às vezes denotamos uma relação R entre elementos de S por um símbolo, como ‘ ‘, ‘≥’, 
Nestes casos, denotamos ( x,y )  R por x  y. 
 
Exemplo 1 Considere o conjunto A={1,2,3}. O número de pares ordenados de A são 
 |A  A| =3*3=9: A2={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)} 
 
Exemplo 2 A relação binária em S = {1,2,4}, definida por R={( x,y ) | x=y/2} é igual a 
R = { (1,2), (2,4) }. 
 
Exemplo 3 S = {1,2,4}, R = { (x,y) S2 : x ≤ y } = { (1,2), (1,4), (2,4) }, pois 1≤ 2, 1≤ 4, e 2≤ 4 
 
Dados n conjuntos S1,S2,…,Sn, n ≥ 2, uma relação n-ária destes n conjuntos, nesta 
ordem, é um subconjunto de S1  S2 … Sn. 
 
Exemplo 4 Considere os conjuntos S={1,2,3} e T={ a,b}. 
Sabemos que | S  T | = 3*2=6 
S  T ={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)} 
R = {(2,a), (3, b)}  S  TDizemos que o conjunto R é uma relação binária de S em T. 
Exemplo 5 Seja S = {1,2,3} e T ={2,4,7}. 
Defina a relação binária R = {(x,y)  S  T : x < y} 
R={(1,2),(1,4),(1,7),(2,4),(2,7),(3,4),(3,7)} 
Definição - RELAÇÕES BINÁRIAS e conjunto subjacente 
Dado um conjunto S qualquer (finito ou infinito, tanto faz), uma relação binária R 
em S é um conjunto R  S × S (ou S2 ). 
Definição - RELAÇÕES BINÁRIAS ENTRE CONJUNTOS DIFERENTES 
Dados dois conjuntos S e T, uma relação binária de S em T é um subconjunto de S  T 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 6/23 
 
2.1 RELAÇÃO BINÁRIA R DE S EM T. CLASSIFICAÇÃO 
 
▪ Relação um-para-um: 
o Se R  S  T é um-para-um, então, para todo par ( x,y )  R, nem x, nem y se 
relacionam com mais ninguém através da relação R. 
o Matematicamente, 
▪ ((x,y)  R)( (w,z)  R) (x = w  y = z)  (y = z  x = w ), ou 
▪ ⌐ ( (x,y)  R) ( (w,z)  R) (x= w  y≠ z)  (y=z  x≠ w ) 
 
 
 
▪ Relação um-para-muitos: 
o Se R  S  T é um-para-muitos, então, para todo par ( x,y )  R, somente x 
pode se relacionar por R com outro(s) elemento(s) de T, e existe pelo menos um caso 
em que isto acontece. Entretanto, y só se relaciona com x. 
o Matematicamente, 
▪ ((x,y) R)((w,z)R)(y=z x=w)  ( {(x,y), (x,z)}  R)( y  z) 
 
 
 
▪ Relação muitos-para-um: 
o É análoga à anterior. Apenas a 2ª componente pode aparecer em mais de 
um par, e existe pelo menos uma situação deste tipo. 
S 
T • 
• 
• 
• 
• 
• 
S T 
• 
• 
• 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 7/23 
 
 
 
 
▪ Relação muitos-para-muitos: 
o Se R  S  T é muitos-para-muitos, então, existe pelo menos um caso em 
que um elemento de S se relaciona por R com mais de um elemento de T, e existe pelo 
menos um caso em que isto ocorre com um elemento de T. 
o Matematicamente, 
▪ ( {(x,y), (x,z)}  R)( y  z)  ( {(x,y), (w,y)}  R)( x  w) 
 
Exercício 1 
Seja S = {2,5,7,9}. Classifique as relações em S2 de acordo com a classificação anterior. 
a) R={(5,2),(7,5),(9,2)} 
b) R={(2,5),(5,7),(7,2)} 
c) R={(7,9),(2,5),(9,9),(2,7)} 
 
Exercício 2 
Seja S o conjunto de seres humanos. Classifique as relações abaixo de acordo com a 
classificação anterior. 
a) ( x,y )  R ↔ x é pai biológico de y 
b) ( x,y )  R ↔ x e y têm pai ou mãe (biológicos) em comum. 
c) ( x,y )  R ↔ x é filho biológico de y 
2.2 PROPRIEDADES DE RELAÇÕES BINÁRIAS 
 
As relações binárias que estamos interessados são aquelas sobre um único conjunto 
subjacente S. As propriedades que serão vistas são as seguintes: 
• Reflexividade, Simetria, Transitividade, e Anti-simetria 
 
S T 
• 
• 
• 
• 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 8/23 
 
Definição - Relação reflexiva 
Seja R uma relação binária em S. 
R é reflexiva, se, e somente se,  x S, (x,x)  R 
 
S = {1,2,3} e R={(1,1),(2,2),(3,3),(2,3),(1,2)}  Reflexiva 
 
Definição - Relação Simétrica 
Seja R uma relação binária em S. 
R é simétrica, se ( (x,y) R )( (y,x) R) 
 
S = {1,2,3} e R={(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)}  Simétrica 
 
Definição - Relação Transitiva 
Seja R uma relação binária em S. R é transitiva, se 
( (x,y) R)( (y,z)  R  (x,z) R) 
 
S = {1,2,3} e R={(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)}  transitiva 
 
Definição - Relação Anti-simétrica 
Seja R uma relação binária em S. R é antisimétrica, se 
( (x,y) R )( (y,x) R y = x ) 
 
S = {1,2,3} e R={(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)} 
R’={(1,1),(1,2),(1,3),(3,1),(2,2),(2,3),(3,3)} 
não é anti-simétrica (por conta da presença de (1,3) e (3,1)), 
não é simétrica (por conta da ausência de (2,1) e (3,2) 
Exemplo Seja S = {1,2,3} 
• Se uma relação R em S é reflexiva, que pares ordenados têm que pertencer a R? 
• Se uma relação R em S é simétrica e se (a,b) R, que outro par ordenado tem que 
pertencer a R? 
• Se uma relação R em S é anti-simétrica, e se (a,b) R e (b,a) R, o que tem que ser 
verdade? 
• A relação R={(1,2)} em S é transitiva? 
 
Não simetria 
As propriedades de simetria e anti-simetria não são opostas. 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 9/23 
 
A relação R não é simétrica se: ( (x,y) R)( (y,x)  R) 
S={1,2,3} e R={(1,1),(2,2),(3,3)}. R é Reflexiva, Simétrica, Transitiva, e Anti-simétrica 
 
Exemplo S={1,2,3} e R={(1,2),(2,1),(1,3)} 
Não é reflexiva, Não é simétrica, Não é transitiva, Não é anti-simétrica 
 
Exercícios 
a) S = Z e (x,y) R  x+y é par (pares obtidos com x e y ímpares ou x e y pares). 
b) S = N+ e (x,y) R  x divide y. 
c) S={0,1} e (x,y) R  x=y2. 
2.3 FECHO DE RELAÇÕES 
 
Exemplo ilustrativo: 
Seja S = ℕ - {0} o conjunto subjacente da relação R definida por 
(x,y)  R  S × S  x divide y. 
A relação R é reflexiva, transitiva, anti-simetrica, e não simétrica. 
 
Seja F o conjunto formado apenas pelos pares necessários para que a propriedade 
simetria passe a ser válida, F={ (x,y)  ℕ2: y divide x , e x  y } 
O conjunto R* = R ∪ F é o fecho simétrico da relação R. 
Repare que R* não é transitiva! Por exemplo, (2,4)  R*, (2,6)  R*, e (4, 2 )  R*, mas 
(4,6)  R*. Obviamente, por ser simétrica, R* também não é anti-simétrica. 
 
Definição - Fecho de uma relação binária 
A relação binária R* é o fecho de uma relação R em S, relativa a uma propriedade 
(reflexividade, simetria, ou transitividade), se, e só se, R* tem a propriedade, R R*, e 
R* é a relação minimal com estas características que tem o menor número de 
elementos. 
R* é minimal porque é a relação com estas características que tem o menor número de 
elementos. 
Dependendo da propriedade que estamos tratando, dizemos que R* é o fecho 
reflexivo; ou o fecho simétrico; ou o fecho transitivo. 
 
Exemplo 1 S={1,2,3} e R={(1,1),(1,2),(1,3),(3,1),(2,3)} 
Fecho reflexivo: R*ref =R ∪.{(2,2),(3,3)}, 
Fecho simétrico: R*sim =R ∪ {(2,1),(3,2)} 
Fecho transitivo: R*tr =R ∪ {(3,2),(3,3),(2,1)}∪ {(2,2)} 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 10/23 
 
Exercício S={a,b,c,d} e R={(a,a),(b,b),(c,c),(a,c),(a,d),(b,d),(c,a),(d,a)} 
Obtenha os fechos reflexivo, simétrico, e transitivo de R 
 
Para obter o fecho transitivo, cada vez que introduzimos um elemento novo no 
conjunto, abrimos a possibilidade para a introdução de outros elementos. No Exemplo 
1 acima, a introdução do elemento (2,1) fez com que (2,2) tivesse que ser inserido 
também, pois (1,2)  R e o fecho transitivo deve preservar a propriedade de 
transitividade. 
 
Uma forma de obter o fecho transitivo de uma relação R é a seguinte 
algoritmo FechoTransitivo ( R ) 
 F  R , Q ← R ; T ←  
loop 
T ← Q , Q ←  
/* T é o conjunto de elementos recém introduzidos em F 
/* Q agora receberá os elementos novos 
Para cada elemento ( x,y )  F, com x ≠ y faça 
Para cada ( y,z )  T, com y ≠ z faça 
se ( x,z )  F ∧ ( x,z ) ∉ Q então 
insira ( x,z ) em Q 
 fim-se 
 fim-para fim-para 
Para cada elemento ( x,y )  T, com x ≠ y faça 
Para cada ( y,z )  F, com y ≠ z faça 
se ( x,z )  F ∧ ( x,z ) ∉ Q então 
insira ( x,z ) em Q 
 fim-se 
 fim-para fim-para 
 F ← Q ∪ F ; 
 se ( Q =  ) então retorne F fim-se 
 fim-loop 
fim-algoritmo 
 
Cada elemento do F parcial deve ser testado com cada elemento do T que foi obtido na 
iteração anterior do loop (ou do T inicial) para ver se é possível criar uma nova 
transição. Da mesma forma, cada elemento do T deve sertestado com cada elemento 
do F para ver se é possível criar uma nova transição. 
 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 11/23 
 
2.4 ORDEM PARCIAL 
 
Definição - Ordem Parcial 
Uma ordem parcial é uma relação binária reflexiva, anti-simétrica e transitiva. 
 
Exemplo: S = N+ e (x,y) R  x divide y , 
O par (S,R) é chamado conjunto parcialmente Ordenado 
 
Exemplo S={1,2,3,6,12,18} e R: x divide y 
R={...}, Predecessores de 6, Predecessores imediatos de 6 
Note que um mínimo é um minimal. 
Note que um máximo é um maximal. 
 
2.4.1 Diagrama de Hasse 
 
Podemos representar qualquer conjunto parcialmente ordenado (S,R) por um 
diagrama de Hasse, desde que S seja um conjunto finito. No diagrama, cada elemento 
x S deve ser representado. Se x é predecessor imediato de y, y é colocado acima de x e 
os dois são ligados por um segmento de reta. 
Definições - Predecessor, sucessor e predecessor imediato 
Seja (S,R) um conjunto parcialmente ordenado. Se (x,y)  R, dizemos que x é um 
predecessor de y ou que y é um sucessor de x. 
Se (x,y)  R, e não existe z tal que (x, z )  R e ( z, y)  R, então x é um predecessor 
imediato de y. 
Definições - Elemento mínimo e elemento minimal 
Seja (S,R) um conjunto parcialmente ordenado. Se existe um y S tal que y é 
predecessor de todos os elementos de S, então y é um elemento mínimo. Se y  S 
não tem predecessor, então y é dito minimal. 
Definições - Elemento máximo e elemento maximal 
Seja (S,R) um conjunto parcialmente ordenado. Se existe um y S tal que y é 
sucessor de todos os elementos de S, então y é um elemento máximo. Se y  S não 
tem sucessor, então y é dito maximal. 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 12/23 
 
Exemplo Ilustrativo 
S = ({1,2,3}), S é o conjunto de todos os subconjuntos de {1,2,3}, e R é a relação R = { 
(A,B)  S2 : A  B }. 
 
 
Repare que  é predecessor imediato de três subconjuntos, indicando que ele se 
relaciona com estes três conjuntos. Dado um elemento qualquer, ele vai se relacionar a 
todos os elementos que consegue alcançar, de baixo para cima, no diagrama de Hasse, 
refletindo a transitividade da ordem parcial. 
 
Repare também que a relação R deste exemplo tem um mínimo, o conjunto  , e um 
máximo, o conjunto {1,2,3}. 
 
Exercício S={a,b,c,d,e,f}, R={(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(a,b),(a,c),(a,d),(a,e),(d,e)} 
e (S,R) um conjunto parcialmente ordenado. Faça o diagrama de Hasse 
 
Definição - Ordem Total 
Uma ordem parcial R onde todo elemento do conjunto está relacionado a todos os 
outros elementos é chamada ordem total ou cadeia. 
Exemplo: S = ℕ e R é a relação “menor ou igual”  
 
2.5 RELAÇÕES DE EQUIVALÊNCIA, PARTIÇÕES, E CLASSES DE EQUIVALÊNCIA 
 
Definição - Relação de Equivalência 
Uma relação binária em um conjunto S é uma relação de equivalência se, e somente se, 
é uma relação reflexiva, simétrica e transitiva 
 
 
{ 1 , 3 } { 1, 2 } 
{ 2 } { 1 } 
{ 1 , 2 , 3 } 
 
{ 2 , 3 } 
{ 3 } 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 13/23 
 
Definição - Partição de um Conjunto 
Uma partição de um conjunto S é uma coleção de subconjuntos disjuntos não vazios 
de S cuja união é igual a S. 
 
Dizendo de outra forma, suponha que S é um conjunto qualquer (finito ou infinito, 
tanto faz) e {S1,S2,…,Sn} é uma coleção de n subconjuntos de S, onde n é um inteiro 
positivo (ou seja, Si  S, i = 1,2,..., n ). Suponha que S1 ∪ S2 ∪ ... ∪ Sn = S. Suponha que os 
conjuntos da coleção são todos disjuntos (ou seja, Si ∩ Sj =  , onde 1 ≤ i < j ≤ n ). Então a 
coleção {S1,S2,…,Sn} é uma partição de S. 
 
Observação: Uma partição pode até ser feita com uma coleção de um número infinito 
de subconjuntos. 
 
Teorema 1 
Toda relação de equivalência em um conjunto S determina uma partição em S. 
Prova 
Seja R uma relação de equivalência. 
Considere um elemento qualquer x  S. Considere o conjunto [ x ] = { y : ( x , y )  R }. 
Considere um outro elemento qualquer z  S tal que z  [ x ]. 
Então, necessariamente, [ z ] ∩ [ x ] = . 
Se isto não é verdade, ou seja, se existe algum y  [ z ] ∩ [ x ] , 
então ( y, z)  R, ( x, y)  R e, pela transitividade de R, ( x,z )  R. 
Ora, isto contradiz a hipótese de que z  [ x ]. 
Como R é uma relação de equivalência, cada elemento x  S pertence a algum par da 
relação (lembre-se que, por reflexividade ( x,x )  R ... ). 
Portanto, a relação de equivalência R determina uma partição de S dada pelos 
subconjuntos de S formados pelos elementos que se relacionam por R em S. 
fim-prova 
 
Teorema 2 
Toda partição de um conjunto S determina uma relação de equivalência em S. 
Prova 
Definição - Classes de Equivalência (ou Parte da Partição) 
Seja {S1,S2,…,Sn} uma partição de S. Então, cada subconjunto Si , i = 1,2,...,n, da 
coleção é uma classe de equivalência ou parte da partição. É comum denotar Si pela 
notação [ s ], onde s  Si é um elemento qualquer de Si , geralmente s é aquele mais 
facilmente identificável da classe. 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 14/23 
 
Seja {S1,S2,… } uma partição de S (infinita neste caso, mas pode ser finita também, tanto 
faz). Então podemos definir uma relação R onde ( x,y )  R se, e só se, x e y pertencem à 
mesma parte da partição. 
Ora, R é reflexiva, pois, para todo x  S, ( x,x )  R. A relação R é obviamente simétrica, 
por sua definição. 
Finalmente, R é transitiva; pois se ( x,y )  R e ( y,z )  R, isto quer dizer que x, y, e z 
pertencem à mesma parte da partição de S e, portanto, ( x,z )  R. 
fim-prova 
 
Exemplo 1 (número finito de partes) 
S=Z+ e R={(x,y) : x mod 2 = y mod 2} 
[0], classe de equivalência dos pares; [1] , classe de equivalência dos ímpares 
 
Exemplo 2 (número infinito de partes) 
S = ℝ e R = { (x,y) :  x  =  y  } 
S = { ... , [ -2 ] , [ -1 ], [ 0 ] , [ 1 ] , [ 2 ] , ... } 
 
3 FUNÇÕES 
 
Definição 
Sejam S e T dois conjuntos quaisquer . Uma função f , de S em T, f:ST é uma relação 
de S em T (ou seja, um subconjunto de S  T) tal que cada elemento de S aparece 
exatamente uma vez como a primeira componente de um par ordenado. 
 
Uma função não pode ser uma relação “um-para-muitos” nem “muitos-para-muitos”, 
mas pode ser uma relação “um-para-um” ou “um-para-muitos”. 
 
• S é o domínio, T é o contradomínio 
• Se (s,t)  f, então diz-se que f(s) = t 
• f(s) é a imagem de s sob a função f 
• s é uma imagem inversa de f(s) 
• O conjunto Im(f ) de todas as imagens é o conjunto imagem de f, Im(f )  T 
Note que o conjunto das imagens inversas é o próprio domínio S. 
 
 
Exemplos 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 15/23 
 
• S=T={1,2,3}, f  S  T, f={(1,1),(2,3),(3,1),(2,1)} não é função 
• f:ℝ  ℝ , f(x)=|x|, é função com domínio ℝ,. contradomínio ℝ, e imagem ℝ+∪ {0}... 
 
Função de mais de uma variável 
A função de mais de uma variável f:S1  S2  …  Sn  T associa a cada tupla de n 
elementos (s1,s2, …, sn), si Si, um único elemento de T. 
 
Seja f a função f :ℝ  ℝ  {1,2}  ℝ dada por f (x,y,z)=xy+z 
f (-4,3,1)=(-4)3+1=-64+1=-63 
 
Exemplo 
Função piso f:ℝ  ℤ , f(x)= x associa a x  ℝ o maior inteiro  x; f(2,8)= 2,8 = 2 
Função teto f:ℝ  ℤ , f(x)= x  , associa a x  ℝ o menor inteiro ≥ x; f(2,8)=2,8 =3 
 
Definição - Funções Iguais 
Duas funções são ditas iguais se têm o mesmo domínio, o mesmo contradomínio e a 
mesma associação de valores do contradomínioa valores do domínio. 
 
Definição - Função Identidade em um conjunto S 
É a função Is = { ( x,x ) : x  S }. 
Ou seja, a função identidade IS leva cada elemento x  S ao elemento x, ou seja deixa 
cada elemento de S fixo. 
3.1 PROPRIEDADES DAS FUNÇÕES 
 
• Sobrejetividade 
• Injetividade 
• Bijetividade 
 
Definição - Função Sobrejetora (Sobrejeção) 
Uma função f:S T é dita sobrejetora se sua imagem é igual a seu contradomínio, ou 
seja, (tT)(s S)(t=f(s)) 
 
Definição - Função Injetora (Injeção) 
Uma função f:S T, é dita injetora se nenhum elemento de T é a imagem de dois 
elementos distintos de S; ou seja, ( t  T )( t = f( s1 )  t = f( s2 )  s1 = s2 ) 
 
Definição - Função Bijetora (Bijeção) 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 16/23 
 
Uma função é bijetora se é ao mesmo tempo injetora e sobrejetora 
Uma bijeção é uma relação um-para-um. Portanto, se f : S → T é uma bijeção, cada 
imagem inversa de y  T é única. Neste caso, podemos definir a função inversa de f. 
 
Definição - Função Inversa 
Seja f uma bijeção f :ST. Então existe função f-1:T S tal que, se f( s )= t, então f-1( t )= s. 
 
Exercícios 
1. Seja S={1,2,3} e T={2,3,4}, f={(1,2),(2,4),(3,3)}. Determine f-1 
2. Seja f:ℝ  ℝ dada por f(x)=3x+4. f é uma bijeção? Em caso positivo descreva f-1 
 
3.1.1 Composição de Funções 
 
Definição - Função Composta 
Dadas duas funções f e g , onde f:ST, e g:T U, a função g○ f: S  U , definida por 
g○ f = { ( x , z ) : z = g( f ( x ) ) }, ou seja, g○f( x)=g( f ( x ) ), é função composta de f e g 
 
O diagrama abaixo ilustra a composição g ○ f. Repare que o conjunto imagem da 
função composta é subconjunto do conjunto imagem da função g. 
 
Exercício 
f:ℝ  ℝ definida por f(x)=x2 e g: ℝ  ℝ definida por g(x)= x  
Qual o valor de g ○ f(2,3)? Qual o valor de f ○ g(2,3)? 
 
Propriedades: A composição de funções preserva a Sobrejetividade, a Injetividade e a 
Bijetividade. Ou seja, dadas duas funções f:ST, e g:T U 
▪ se ambas são sobrejetoras, então f ○ g é sobrejetora; 
▪ se ambas são injetoras, então f ○ g é injetora; 
▪ se ambas são bijetoras, então f ○ g é bijetora, e g ○ f é a inversa de f ○ g 
 
S 
Im( g ○ f ) 
Im( f ) 
f: S → T 
T 
U 
g: T → U 
g: Im( f ) → U 
Im( g ) 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 17/23 
 
Diagrama - Manutenção da sobrejetividade 
 
 
 
Diagrama - Manutenção da Injetividade 
 
Nas funções injetoras, a imagem inversa de um elemento da imagem é única (relação 
um-para-um). Os elementos e as projeções em vermelho, portanto, não podem existir. 
 
 
Diagrama - Manutenção da Bijetividade 
 
 
 
Prove as afirmações: 
S 
Im( f ) = Im( g-1 ) =T 
T 
U 
Im( g ) = Im( g ○ f ) = U 
 
f: S → T 
Im( f -1 ) = Im( f ○ g ) = S 
 
f: S → T 
f -1: T → S g -1: U → T 
g: T → U 
S 
Im( g ○ f ) 
Im( f ) 
f: S → T 
T 
U 
g: T → U 
g: Im( f ) → U 
Im( g ) 
S 
S 
Im( f ) = T 
f: S → T 
T 
U 
g: T → U 
Im( g ) = Im( g ○ f ) = U 
 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 18/23 
 
a) se f e g são injetoras, então g ○ f é injetora; 
b) se f e g são sobrejetoras, então g ○ f é sobrejetora; 
c) se f e g são bijetoras, então g ○ f é bijetora; 
d) Existe uma injeção de A em B se, e só se, existe uma sobrejeção de B em A. 
A mais difícil é a (d). Vamos lá: 
Se f é injeção de A em B, para cada b ∈ Imagem( f ) ⊆ B , existe um único a ∈ A tal que 
f(a) = b. Portanto, podemos montar uma sobrejeção de B em A fazendo assim: 
- associar a cada b ∈ Imagem( f ) ⊆ B, este único a ∈ A tal que f(a) = b; 
- associar a cada b ∈ B \ Imagem( f ) um elemento qualquer de A. 
Agora suponha que existe uma sobrejeção g de B em A. Vamos criar uma injeção f de A 
em B assim: 
Para cada a ∈ A tal que exista um conjunto Ba ⊆ B tal que para cada b ∈ Ba , g(b) = a, 
escolha um único elemento de Ba para que f(a) seja este elemento. 
 
3.2 FUNÇÕES DE INTEIROS 
 
3.2.1 Funções Piso e Teto 
 
 x  ℝ , o piso de x,  x   o maior inteiro menor do que x 
 
 x  ℝ , o teto de x,  x   o menor inteiro maior do que x 
 
Ex.:   ℝ ,    = 3 ,  -   = -4 ,    = 4 ,  -  = -3 
 
a) x  ℤ   x  = x   x  = x 
b)  x  -  x  = bool_isInteiro( x ) 
c) x – 1 <  x   x   x  < x + 1 
d)  - x  = -  x  , -  x  = -x  
e)  x  = n  n  x < n + 1, ou x – 1 < n  x 
f)  x  = n  n - 1 < x  n , ou x  n < x + 1 
g)  x + n  =  x  + n , n  ℤ 
h) x =  x  + parteFracionaria( x ) 
 
3.2.2 Aplicações Funções Piso e Teto 
 
Exemplo 1 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 19/23 
 
25  35 < 26   log2 35  = 5 
35 = (100011)2 , são 6 bits 
25  32 < 26   log232  = log232 = 5 
32 = (100000)2 , são 6 bits 
 
São necessários m bits para escrever um inteiro n tal que 2m-1  n < 2m 
m-1 =  log2n   m =  log2n  + 1 
 são necessários  log2n  + 1 bits para escrever um inteiro n > 0 na base 2 
 
103  2456 < 104 , é escrito com 4 algarismos 
103  1000 < 104 , é escrito com 4 algarismos 
 
São necessários m algarismos para escrever um inteiro n tal que 10m-1  n < 10m 
m-1 =  log n   m =  log n  + 1 
 são necessários  log n  + 1 algarismos para escrever um inteiro n > 0 na base 
decimal 
 
Exemplo 2 
  x   =  x  , pois teto ou piso de qualquer inteiro é o próprio inteiro... 
 
Exemplo 3 
Prove que para x ≥ 0 
 
 (1) 
m2   x  < (m + 1)2 
m2  x < (m + 1)2 
 
 (2) 
 
de (1) e (2) provamos o teorema... 
 
De forma análoga podemos provar que 
 
Exemplo 4 
Se f( x ) é uma função contínua de ℝ em ℤ, monotonicamente crescente, então, 
 f ( x )  =  f (  x  )  , e  f ( x )  =  f ( x  )  
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 20/23 
 
Prova: 
Se x =  x  , não há o que provar. 
Para x >  x  , 
 f ( x ) > f ( x  ), uma vez que f é crescente 
  f ( x )  ≥  f ( x  )  , uma vez que piso é não decrescente 
Se  f ( x )  >  f ( x  ) , então deve existir y tal que  x  < y  x , e f( y ) =  f( x )  , uma 
vez que f é contínua 
Mas y deve ser inteiro, pela propriedade da função dada pela hipótese. 
Mas não pode haver um inteiro entre x e  x  . Esta contradição indica que 
 f ( x )  =  f ( x  )  
 
Caso especial: f( x ) = ( x + m ) / n 
onde m e n são inteiros 
 ( x + m ) / n  =  (  x  + m ) / n  
da mesma forma 
 ( x + m ) / n  =  (  x  + m ) / n  
 
Exemplo 5 
m = 0, n = 10  f( x ) = x / 10   x / 10 =   x  / 10  
 
Exemplo 6 
 [ a,b ]  intervalo fechado de a até b 
( a,b )  intervalo aberto de a até b 
[ a,b )  intervalo que inclui a e exclui b 
( a,b ]  intervalo que exclui a e inclui b 
n  número de inteiros no intervalo 
Suponha x  ℤ 
Quantos inteiros há no intervalo? 
 
a,b  ℤ 
x  [ a,b ]  n = b – a + 1 
x  [ a,b )  n = b – a 
x  ( a,b ]  n = b – a 
x  ( a,b )  n = b – a – 1 
 
 Generalizando para a,b  ℝ 
x  [ a,b ]   a   x   b   n =  b  -  a  + 1 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 21/23 
 
x  [ a,b )   a   x <  b   n =  b  -  a  
x  ( a,b ]   a  < x   b   n =  b  -  a  
x  ( a,b )   a  < x <  b   n =  b  -  a  - 1 
 
Exemplo 7 
Seja W o número de inteiros n  [1,1000]tal que é divisor de n. 
Determine W 
Solução: Vou usar bool( proposição) como uma função booleana que verifica se a 
proposição é verdadeira ou falsa. E a \ b é a proposição que diz que a é divisor de b 
 
 
 
 
 
 
Podemos eliminar n dessa equação, uma vez que para n = 1, k =1 e para n=1000, k = 10 
 
 
 
Se x  [ k2 , (k + 1)3/ k ) , então (pelo que vimos anteriormente) 
 k2   x <  (k + 1)3/ k  
Portanto, 
 
 
 
 
 
 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 22/23 
 
Podemos generalizar o resultado lembrando que o valor máximo k = 10 foi obtido 
porque 
 
Portanto, se n  [1, N ] , então o valor máximo de k seria 
 
 
 
 
 
3.2.3 Operação módulo 
 
n = m q + r (teorema fundamental da aritmética) 
Qualquer inteiro n pode ser escrito como esta soma, onde q e r são o quociente e o resto 
da divisão pelo inteiro m. 
 
n = m  n / m  + n mod m 
 
Então, o resto da divisão de um inteiro n por outro inteiro m é 
n mod m = n - m  n / m  
 
Cuidado com os números negativos! 
5 mod 3 = 5 – 3  5/3  = 5 – 3  1 = 2 
5 mod (-3) = 5 – (-3)  5/(-3)  = 5 + 3 -5/3 =5 + 3( -2) = -1 
(-5) mod 3 = -5 – 3  (-5)/3  = -5 -3 -5/3 =-5+6 = 1 
(-5) mod (-3) = -5 – (-3)  (-5)/(-3)  = -5 + 3  5/3  = -5 + 3  1= -2 
 
Podemos generalizar para números reais arbitrários 
x mod y = x – y  x / y  
 
O significado pode ser percebido intuitivamente considerando um círculo com 
perímetro y marcado como um intervalo de [0.. y ). O valor x seria a distância 
percorrida no círculo. Se o percurso começa em 0, então depois de percorrer a distância 
x estaríamos no ponto x mod y. O número de voltas (passagem pelo ponto 0) seria x/y 
 
0  x mod y < y, para y > 0 
ESTRUTURAS DISCRETAS – Relações e Funções - Prof. Alexandre Andreatta – 2017.2 23/23 
 
0 ≥ x mod y > y para y < 0 
Não há aplicações relevantes para considerar o caso em que y = 0, e 0 não é divisor de 
nenhum número. 
 
A parte fracionária de um número pode ser escrita como x mod 1, pois 
x =  x / 1  + x mod 1 
x =  x  + x mod 1 
Para a função módulo, a mais importante propriedade algébrica é a lei distributiva: 
t ( x mod y ) = ( tx ) mod ( ty ) 
Basta verificar pela definição de x mod y