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:ST é 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, (tT)(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 :ST. 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:ST, 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:ST, 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