Apostila cap-1 - MD, Notas de estudo de Informática

Baixe Apostila cap-1 - MD e outras Notas de estudo em PDF para Informática, somente na Docsity! MATEMÁTICA DISCRETA CAPÍTULO 1 – CONJUNTOS E LÓGICA 1.1 - Conceitos básicos de teoria dos conjuntos 1.1.1 Definição 1.1.2 Tipos de Conjuntos 1.1.3 Conjuntos em programação 1.2 - Lógica 1.2.1 Conceitos básicos 1.2.1.1 Conectivos 1.2.1.2 Tautologia e Contradição 1.2.1.3 Implicação e Equivalência 1.2.1.4 Quantificadores 1.2.2 Lógica em programação 1.2.3 Técnicas de demonstrações Matemáticas 1.3 - Álgebra dos conjuntos 1.3.1 Diagrama de Venn 1.3.2 Paradoxo de Russel 1.3.3 Operações reversíveis e não-reversíveis 1.3.4 Relação entre a Lógica e a Álgebra de Conjuntos 1.4 - Relações 1.4.1 Definição 1.4.2 Tipos de relação CAPÍTULO 1 – CONJUNTOS E LÓGICA Vamos iniciar esse capítulo com alguns conceitos básicos da teoria dos conjuntos, pois a Matemática Discreta é um estudo matemático baseado em conjuntos contáveis, finitos ou infinitos. Posteriormente, apresentamos também alguns conceitos básicos da lógica matemática e algumas técnicas de demonstrações matemáticas. Para finalizar esse capítulo vamos estudar a álgebra dos conjuntos e relações. 1.1 – CONCEITOS BÁSICOS DE TEORIA DOS CONJUNTOS 1.1.1 Definição Definição: Um conjunto não-vazio é uma coleção de objetos distintos que não possuem uma ordem associada. Observações: 1. Chamamos os objetos de um conjunto de elementos. 2. Quando o conjunto não possui elementos, o denominamos de conjunto vazio. Nos exemplos abaixo observe as formas que podemos representar um conjunto. Exemplos Conjunto das vogais Por propriedade: as vogais Por extensão: listando todos os elementos Vogais={a,e,i,o,u} Por compreensão: Vogais= {n| n é uma vogal}, que significa o conjunto de todos os elementos n, tal que n é uma vogal. Conjunto dos dígitos Por extensão: Dígitos={0,1,2,3,4,5,6,7,8,9} Conjunto dos números ímpares Para programar você, inicialmente, deve entender os conceitos de alfabeto, palavras e linguagens. Vamos por partes. Alfabeto – é um conjunto finito, cujos elementos são símbolos ou caracteres. Você sabia? O conjunto vazio, por ser considerado finito é um alfabeto. Palavra ou cadeia de caracteres ou sentença sobre um alfabeto é uma sequência finita de símbolos (do alfabeto) justapostos. O símbolo ε representa uma cadeia vazia, palavra vazia ou sentença vazia. Vamos denotar por ∑ um alfabeto, e *∑ o conjunto de todas as palavras possíveis sobre ∑ . Dizemos que ε é uma palavra sobre o alfabeto ∅ . E que { }* ε∅ = denota todas as palavras possíveis sobre o conjunto vazio. Vamos aos exemplos. a) Ae, aui, oe, aeiou são palavras sobre o alfabeto das Vogais. b) ε é uma palavra sobre o alfabeto {1,2,3}. c) O conjunto de todas as palavras possíveis do alfabeto { }1,2 é dado por { } { }*1, 2 ,11, 22,12,21,111, 222...ε= . Reflita! Explique porque o conjunto N não é um alfabeto. Linguagem Formal ou Linguagem: é um conjunto qualquer sobre um alfabeto. Você sabia? Seja o alfabeto { }1,2∑ = . Observe que o conjunto vazio ∅ e o conjunto formado pela palavra vazia { }ε são linguagens sobre ∑ . Perceba que { }ε∅ ≠ . Saiba mais As linguagens de programação JAVA, C Pascal etc. são linguagens sobre o alfabeto constituído por letras, dígitos e alguns símbolos especiais (parênteses, pontuação etc.). Assim, cada programa é uma palavra sobre o alfabeto. A linguagem consiste em todos os seus programas possíveis e, portanto qualquer linguagem de programação são conjuntos infinitos. Nos programas de computação precisamos representar os conjuntos com os símbolos utilizados. Assim, veja em Pascal como ficam algumas representações. Conjuntos Representação em Pascal {vermelho, amarelo, azul} [vermelho, amarelo, azul] ∅ [ ] {seg, ter, qua, qui, sex, sab, dom} [seg..dom] [seg..dom] {seg, ter, qua, qui, sex} [seg..sex] {a,e,i,o,u} [‘a’, ’e’, ’i’, ’o’, ’u’] Tabela 1: Representação de conjuntos em Pascal. Fonte própria. Para definir variáveis temos: Variáveis Representação em Pascal cores primárias cores_primárias := [vermelho,amarelo,azul] semana semana := [seg..dom] trabalho: dias da semana trabalho:= [seg..sex] vogais: alfabeto vogais := [‘a’, ’e’, ’i’, ’o’, ’u’] Tabela 2: Representação de variáveis em Pascal. Fonte própria. O símbolo “:= ” representa o termo “por definição”. O símbolo “ ⇐ ” é usado para indicar continência. O conectivo “in” simboliza pertinência. A igualdade é representada por “=”. Assim, veja como algumas sentenças são representadas. Sentenças Representação em Pascal cores primárias cores_primárias =[vermelho,amarelo,azul] (verdadeiro) semana semana = [seg..dom] (verdadeiro) trabalho ⊆ semana trabalho ⇐ semana (verdadeiro) e ∈ vogais ‘e’ in vogais (verdadeiro) Tabela 3: Representação de sentença em Pascal. Fonte própria. Sugestão de Atividades 1. Dos conjuntos abaixo indique quais são finitos ou infinitos. a) Conjunto dos números inteiros Z. b) Todos os rios do mundo. c) A linguagem de programação JAVA. d) Os números pares. 2. Dados os conjuntos A={a}, B={a,b} , C={{a},a} , assinale verdadeiro nas alternativas corretas ou falso nas alternativas incorretas. ( ) A B⊂ ( ) A B= ( ) A B⊆ ( ) A C⊂ ( ) A B∈ ( ) A C⊆ ( )1 A∈ ( )1 A⊂ ( ) B∅ ⊆ ( ){1} A⊂ 3. Observe cada conjunto abaixo e assinale os que são alfabetos. ( ) Conjunto dos números reais. ( ) {a, b} ( ) Letras do alfabeto brasileiro. ( ) Conjunto dos números racionais. ( ) Todos os números pares. ( ) Conjunto das cores primárias. ( ) Conjunto das consoantes. ( ) Conjunto de todos os brasileiros com mais de 40 anos. ( ) {1,2,3,4} ( ) Dias da semana. Atividade complementar Pesquise na internet sobre a linguagem Pascal e tente verificar como inserir outros tipos de sentenças. Essa já é uma forma de você se habituar com a parte de programação. 1.2 – Lógica Logo, verificando na tabela verdade p q∧ é falsa. Observe que na conjunção a proposição composta só é verdadeira se ambas p e q são verdadeiras. Disjunção Já na disjunção o conectivo usado é “ou”. Assim, dadas duas proposições p e q, denotamos a disjunção por p q∨ , e lemos p ou q. Observe a tabela-verdade e verifique que nesse caso a proposição composta só não é verdadeira se ambas as proposições p e q são falsas. Tabela 6 – Tabela-verdade da disjunção. Fonte própria. Condição Nesse caso o dispositivo é “então”. Dadas duas proposições p e q, a condição é denotada por p q→ (p então q). Veja a sua tabela–verdade a seguir. Tabela 7 – Tabela-verdade da condicional. Fonte própria. Bicondição A bicondição é denotada por p q↔ , lê-se “p se e somente se q”. A seguir, a sua tabela-verdade p q p q∨ V V V V F V F V V F F F p q p q→ V V V V F F F V V F F V p q p q↔ V V V V F F F V F F F V Tabela 8 – Tabela-verdade da bicondicional. Fonte própria. Observe que o valor lógico da proposição composta só é verdade quando ambas p e q são verdadeiras ou ambas são falsas. Agora vamos aprender a trabalhar com as fórmulas lógicas. Vamos ver alguns exemplos: 1) ( ) ( )p q p q∧ ¬ → ∨ 2) ( ) ( )p q p q p→ ∧ ∨ ↔ Muitas vezes há excesso de parênteses e podemos simplificar a fórmula. Para tanto, devemos seguir a seguinte ordem: 1. Conectivos entre parênteses, dos mais internos para os mais externos. 2. Negação ( ¬ ). 3. Conjunção ( ∧ ) e disjunção ( ∨ ). 4. Condição ( → ). 5. Bicondição ( ↔ ). Das fórmulas acima a primeira pode ser reescrita como p q p q∧ ¬ → ∨ , pois a retirada dos parênteses não atrapalha a ordem que a operação deve ser feita. Já na segunda fórmula a retirada dos parênteses vai comprometer o valor lógico da expressão. Sugestão de Atividades Observando a ordem verifique se a fórmula a seguir pode ser simplificada ( ) ( )p q p q¬ ∧ ↔ ¬ ∨ . Você Sabia? Cada uma das proposições simples pode ser denominada como: a) Fórmula atômica não constante, quando a proposição pode assumir os valores lógicos V e F. b) Fórmula atômica constante, quando a proposição assumir o valor fixo V ou F. E ainda tem mais! Uma tabela-verdade de uma fórmula lógica com n fórmulas atômicas (não- constantes) possui 2n linhas. Atenção: Para construir a tabela-verdade de uma fórmula qualquer, é necessário você conhecer todas as tabelas que foram apresentadas anteriormente: negação, conjunção, disjunção, condição e bicondição. Exemplo Vamos construir a tabela-verdade da fórmula ( )p q p q¬ ∧ ↔ ¬ ∨ ¬ . Observe que temos as fórmulas atômicas não-constantes p e q. Portanto, a nossa tabela possui 22 4= linhas. p q p¬ q¬ p q∧ p q¬ ∨ ¬ ( )p q p q¬ ∧ ↔ ¬ ∨ ¬ V V F F V F V V F F V F V V F V V F F V V F F V V F V V Tabela 9 – Tabela-verdade da proposição ( )p q p q¬ ∧ ↔ ¬ ∨ ¬ . Fonte própria. Exemplo Agora vamos construir a tabela verdade de uma fórmula lógica que contém uma fórmula atômica constante. Assim, vamos construir a tabela-verdade da fórmula p q V∨ ¬ → . As fórmulas atômicas p e q são não-constantes e a fórmula atômica V é constante com valor verdade V. Para a contagem de linhas, consideramos apenas as fórmulas não-constantes, assim teremos 4 linhas na tabela-verdade. p q q¬ p q∨ ¬ p q V∨ ¬ → V V F V V V F V V V F V F F V F F V V V Tabela 10 – Tabela-verdade da proposição p q V∨ ¬ ⇒ . Fonte própria. Observe que não é necessário colocarmos uma coluna para a fórmula atômica constante V, pois o valor lógico é sempre verdade. satisfazer a proposição p(x). Para negar isso, basta existir pelo menos um elemento em A que não satisfaça p(x). Assim, podemos escrever ( ) ( )( ) ( )x A p x x A p x¬ ∀ ∈ ⇔ ∃ ∈ ¬ . 1.2.2 Lógica em programação A pergunta é: Num programa de computação como utilizamos os conceitos da lógica? Vamos ver tais conceitos na linguagem Pascal. Para representar o tipo de dado lógico usamos o termo bolean, e os valores lógicos V e F, são representados por true e false. Temos também as representações a seguir: Igual = negação not menor < conjunção and maior > disjunção or menor ou igual ≤ condição <= maior ou igual ≥ bicondicão = Tabela 11 – Conceitos lógicos em Pascal. Fonte própria. Veja um programa que tem o objetivo de fornecer o valor lógico da fórmula p q r∧ → . program valor_logico (input, output); var p, q e r: bolean; begin read (p,q, r); if (p and q) <= r then write (‘verdadeiro’) else write(´falso’) end. Explicando... Na primeira linha os comandos input e output indicam a entrada e saída dos dados, respectivamente. Depois são definidas as variáveis lógicas com o termo “bolean”. “begin” indica o começo do programa e “end” o final. “read” (ler) as variáveis p, q e r. “if” (se) p q r∧ → é verdadeiro “then” (então) “write” (escreva) verdadeiro. “else” (caso contrário, se for falso) “write” (escreva) falso. 1.2.3 Técnicas de demonstrações Matemáticas Você sabe a diferença entre um teorema, um corolário e um lema? Vamos por partes! Teorema: Um teorema é uma proposição do tipo p q→ , que podemos provar que é sempre verdadeira, portanto é uma tautologia e podemos escrever p q⇒ (p implica q). Dizemos que p representa a hipótese, que são os dados, e q representa a tese, o que queremos provar. Corolário: é um teorema que é uma conseqüência tão imediata de outro teorema, que a sua prova é bastante trivial, imediata. Lema: é um teorema que possui um resultado importante, utilizado nas provas de outro teorema. Em computação, podemos ver um teorema como um algoritmo, que sempre funciona. Vamos agora ver alguns tipos de demonstrações matemáticas. 1) Prova direta; 2) Prova por contradição; 3) Prova por redução ao absurdo; 4) Prova por Indução. 1) Prova direta: Essa técnica de demonstração, mostra diretamente que a tese é verdadeira, considerando-se a hipótese verdadeira. Inicialmente devemos identificar a hipótese e a tese. Antes de demonstrarmos um teorema precisamos identificar claramente a hipótese e a tese. Muitas vezes temos que reescrever o teorema. Veja o exemplo: Vamos supor que queremos mostrar que a soma de dois números pares é um número par. O primeiro passo é reescrever na forma de um teorema através da proposição p q⇒ . Lembre-se que o conectivo “⇒ ” significa “então”. Portanto, podemos escrever a proposição como: Teorema: Se m e n são números pares então n+m é um número par . tesehipótese

 Prova. Por n e m serem números pares, existem números naturais r e s, tais que m=2r e n=2s. Assim, m+n = 2r + 2s=2(r+s). Como a soma de dois números naturais é um número natural então m+n é um número par.
Você sabia? Para sinalizar o final da prova matemática, usamos o quadrado, ou pode ser também a sigla c.q.d., que significa como queríamos demonstrar. 2) Prova por Contradição: Nessa prova em vez de considerarmos que a hipótese é verdadeira e mostrar que a tese é verdadeira, como fizemos na prova direta, devemos considerar que a tese é falsa e mostrar que a hipótese também é falsa, desde quando p q q p→ ⇔ ¬ → ¬ . Veja como é fácil a prova por contradição observando o exemplo abaixo. Exemplo Suponha que x N∈ . Vamos provar que 2 1 3 2 qp x x− > → >
 . Para tanto, vamos usar a prova por contradição considerando que p q q p→ ⇔ ¬ → ¬ . Observe que em vez de provar p q→ , fica muito mais fácil provar q p¬ → ¬ . Provaremos, portanto que: 2 2 1 3 q p x x ¬ ¬ ≤ → − ≤
 . Verifique que a prova fica bastante fácil, pois basta provar a condição para e 0, 1 2x x x= = = . Na condição anterior, teríamos que provar para todos os números naturais maiores que 3. Percebeu que ficou muito mais fácil? 3) Prova por Redução ao Absurdo Nessa prova por redução ao absurdo, dizemos que a condição p q→ equivale a ( )p q F∧ ¬ → , ou seja, ( )p q p q F→ ⇔ ∧ ¬ → . Nesse caso, ao negarmos a tese verificamos uma contradição ao considerarmos a hipótese. Exemplo: Vamos provar que existem infinitos números primos. Prova: Queremos mostrar que existem infinitos números primos. Vamos supor por absurdo, que existe uma quantidade finita,n, de números primos, Posteriormente, durante o curso vamos definir o conceito de álgebra. Dessa forma você vai entender porque o nome “Álgebra dos Conjuntos”. 1.3.1 Diagrama de Venn Os diagramas de Venn foram criados pelo matemático inglês John Venn (1834- 1923) e são usados nos estudos da Teoria dos conjuntos. Existem várias figuras para representarmos conjuntos. Geralmente o conjunto universo é representado por um quadrado e os demais conjuntos podem ser representados por círculos, elipses, etc. Assim, os diagramas podem representar pertinência e continência de conjuntos, como também algumas operações entre conjuntos. Vamos mostrar um importante resultado, que é a Transitividade da Continência. Veja teorema abaixo. Teorema: Sejam A, B e C conjuntos quaisquer. Se A B e B C⊆ ⊆ , então A C⊆ . Prova. Inicialmente vamos representar o teorema anterior através dos diagramas de Venn. Figura 1 – Transitividade da Continência. Fonte própria. Sejam A e B conjuntos quaisquer. Temos por hipótese que A B e B C⊆ ⊆ e queremos provar que A C⊆ . Vamos tomar um elemento “a” pertencente ao conjunto A. Como A é subconjunto de B, por hipótese, pela definição de subconjunto, o elemento “a” também pertence ao conjunto B. Por outro lado, como “a” pertence a B, pertencerá também a C pelo mesmo motivo. Logo, para qualquer elemento “a” pertencente a A, “a” pertence também a C, como queríamos demonstrar. 1.3.2 Paradoxo de Russel O paradoxo de Russel mostra que nem toda coleção de elementos é um conjunto. Para evitar esse paradoxo, devemos representar os conjuntos por compressão na forma { }| ( )a A p a∈ . O nosso objetivo é estudar a álgebra dos conjuntos, portanto para garantir isso devemos sempre trabalhar com um conjunto universo. Assim, devemos ficar a par das operações entre conjuntos, que veremos a seguir. Saiba mais... Para verificar a prova do paradoxo de Russel, consulte MENEZES, 2005. Ver referências! Indicação de Leitura Se informe melhor sobre o Paradoxo de Russel através da história. Recomendo a leitura no livro indicado abaixo. BENTHEY, Peter. O Livro dos Números. Uma história ilustrada da matemática. Tradução Maria Luíza X. de A. Borges, revisão técnica Samuel Jurkiewiez. Rio de Janeiro, Jorge Zahar Ed, 2009, p. 99. 1.3.3 Operações não-reversíveis e reversíveis Inicialmente vamos estudar as operações não reversíveis. União: Dados dois conjuntos A e B a união de A com B consiste de elementos que pertencem a A ou a B. Veja o diagrama a seguir. Figura 2 – União de Conjuntos. Fonte própria. Simbolicamente, { }|A B x x A x B∪ = ∈ ∨ ∈ . Veja que utilizamos o símbolo disjunção lógica. Propriedades da União Sejam os conjuntos A,B e C. Temos as seguintes propriedades: a) Elemento Neutro: o elemento neutro da união é o conjunto vazio. A A A∪ ∅ = ∅ ∪ = b) Idempotência: o conjunto identidade do conjunto A é o próprio conjunto A. A A A∪ = c) Comutativa: a união de conjuntos é uma operação comutativa. A B B A∪ = ∪ d) Associativa: ( ) ( )A B C A B C∪ ∪ = ∪ ∪ . Das propriedades acima, veja como podemos provar a associatividade. Associatividade da união: Se A, B e C são conjuntos quaisquer, então ( ) ( )A B C A B C∪ ∪ = ∪ ∪ . Prova: Para provar a igualdade devemos mostrar que 1º caso: ( ) ( )A B C A B C∪ ∪ ⊆ ∪ ∪ . Como ( )x A B C∈ ∪ ∪ , por definição de união, ( )x A x B C∈ ∨ ∈ ∪ . Isso implica que ( )x A x B x C∈ ∨ ∈ ∨ ∈ . Sabemos que o conectivo ∨ é Complemento: A operação do complemento de um conjunto A é em relação ao conjunto Universo U. Assim, o complemento de um conjunto A U⊆ consiste de todos os elementos do conjunto universo U que não pertencem ao conjunto A. Utilizamos as notações ~ A , 'A ou cA para representar o complementar de A. O complemento está relacionado a negação lógica. Veja a representação nos diagramas de Venn a seguir. Figura 4 – conjunto A. Figura 5 – Complemento de um conjunto. Fonte própria. Fonte própria. Simbolicamente podemos representar o complemento do conjunto A da seguinte forma: { }~ |A x U x A= ∈ ∉ . Diferença: Dados os conjuntos A e B, a diferença, A B− , é igual à interseção entre o conjunto A e o complementar de B. Simbolicamente, ~A B A B− = ∩ , ou seja, { }|A B x x A x B− = ∈ ∧ ∉ . Proposta de Atividade: Agora é com você! Represente a diferença entre conjuntos através dos diagramas de Venn. Conjunto das Partes: O conjunto das partes de um conjunto A é um conjunto que contém todos os subconjuntos do conjunto A. Denotamos o conjunto das partes de A, por ( )P A ou 2A e podemos representá-lo como { }( ) |P A X X A= ⊆ . Se o conjunto A possui n elementos o conjunto das partes de A, ( )P A contém 2n . Exemplo: { } { } { } { } { } { }{ } ( ) , , ( ) , , , , A a P A a B a P B a a = = ∅ = ∅ = ∅ ∅ ∅ Proposta de Atividade: Agora é com você! Dado o conjunto { }, ,C a b c= encontre o conjunto das partes de C, ( )P C e verifique que o número de elementos é 2n . Produto Cartesiano Sejam dois conjuntos A e B. O produto cartesiano dos conjuntos A e B, denotado por A B× é dado por { }( , ) |A B a b a Ae b B× = ∈ ∈ . Você sabia... O produto cartesiano não é comutativo e também não é associativo. Proposta de Atividade: Agora é com você! Dado o conjunto { } { } { }, , , 1,2A a b B c d e C= = = encontre o produto cartesiano A B× e B A× e verifique que essa operação não é comutativa. Similarmente, mostre que também não é associativa, ou seja, ( )A B C× × é diferente de ( )A B C× × . Não se esqueça. Qualquer dúvida acesse o ambiente virtual de aprendizagem! União Disjunta A união disjunta de conjuntos acontece quando precisamos identificar todos os elementos do conjunto A e todos os elementos do conjunto B, de forma que a interseção será sempre o conjunto vazio. Assim, a união desses conjuntos consta de todos os elementos do conjunto A e todos os elementos do conjunto B. Dados os conjuntos A e B, a união disjunta dos conjuntos é denotada por A B • ∪ ou A B+ . 1.3.4 Relação entre a Lógica e a Álgebra de Conjuntos Existe uma relação entre a lógica e a álgebra de conjuntos. Como por exemplo, a continência de conjuntos é representada logicamente pela implicação e a igualdade com a equivalência. Vamos ver como fica isso simbolicamente. Considerando { }| ( )A x p x= e { }| ( )B x q x= temos: Continência: A B⊆ se e somente se ( ) ( )( ) ( )x U p x q x∀ ∈ ⇒ . Igualdade: A B= se e somente se ( )( )( ) ( )x U p x q x∀ ∈ ⇔ . Vamos ver como fica a representação do conjunto vazio e o conjunto universo. Conjunto universo: A U= se e somente se ( )( )( )x U p x V∀ ∈ ⇔ . Conjunto vazio: A U= se e somente se ( )( )( )x U p x F∀ ∈ ⇔ . E a união e interseção como ficam? União: A B∪ se e somente se p q∨ . União: A B∩ se e somente se p q∧ . Proposta de Atividade Agora vamos propor uma atividade interessante. No quadro a seguir estão relacionadas as propriedades tanto da lógica quanto da teoria dos conjuntos. Observem algumas as relações já colocadas e tente completar a tabela a seguir. Se tiver dificuldades acesse o ambiente virtual. Propriedade Lógica Teoria dos Conjuntos Idempotência p p p∧ ⇔ p p p∨ ⇔ A A A∩ = Comutativa p q q p∧ ⇔ ∧ p q q p∨ ⇔ ∨ Associativa ( ) ( )p q r p q r∧ ∧ ⇔ ∧ ∧ ( ) ( )p q r p q r∨ ∨ ⇔ ∨ ∨ ( ) ( )A B C A B C∩ ∩ = ∩ ∩ Distributiva ( ) ( ) ( )p q r p q p r∧ ∨ ⇔ ∧ ∨ ∧ Para facilitar a visualização podemos representar as endorrelações em grafos, pois toda endorrelação é um grafo, mas nem todo grafo é uma endorrelação. Na representação de uma endorrelação :R A A→ como grafo cada elemento do conjunto A é representado por um ponto ou círculo (nodos) e cada elemento da relação ,a b é representado por uma seta, arco ou aresta que liga o elemento a ao elemento b. Dados os {3,8,10}A = , { , }B a b= e {3,7}C = . Vamos representar por grafos as seguintes endorrelações. a) : A A∅ → b) A endorrelação de igualdade em C, ,C = , dada por { }( , ), ( , )a a b b . c) A endorrelação ,A < , tal que { }(3,8), (3,10), (8,10) . Grafos a) Figura 8 – Grafo sem aresta. Fonte própria. b) Figura 9 – Endorrelação de igualdade. Fonte própria. c) Figura 10 – Endorrelação menor o que. Fonte própria. Tabela 13 – Endorrelações representada por Grafos. Fonte própria. Proposta de Atividade Represente através de um grafo a relação em A { }(3,10), (10,3), (10,10) . Dica: Observe que o elemento 8 não aparece na relação, mas ele deve aparecer no grafo isoladamente, ou seja sem arestas. O elemento 10 está relacionado com ele mesmo, portanto você deve usar a representação da letra b. Relação com matrizes Podemos também representar uma relação :R A B→ através de matrizes em que o número de linhas n é a quantidade de elementos do domínio (número de elementos do conjunto A) e o número de colunas m é a quantidade de elementos do contra-domínio (número de elementos do conjunto B). Dados os {3,8,10}A = , { , }B a b= , {3,7}C = e { }D b= , vamos representar as seguintes relações através de matrizes. a) : A A∅ → b) A endorrelação de igualdade em B, ,B = , dada por { }( , ), ( , )a a b b . c) A endorrelação ,A < , tal que { }(3,8), (3,10), (8,10) . Tabela 14 – Relações com Matrizes. Fonte própria. d) A relação “maior que”, :R A C→ { }(8,3), (10,3), (8,7), (10,7) . Proposta de Atividade Represente através de matrizes a relação : ( ) ( )P D P B⊆ → . Dica: Inicialmente construa os conjuntos das partes de D e B. Depois encontre os elementos da relação, observando se cada elemento pertencente a ( )P D estão contidos nos elementos de ( )P B , pois a relação é de continência. Relação Dual A relação dual pode também ser chamada de relação oposta ou inversa. Se :R A B→ é uma relação, a relação dual denotada por 1 :R B A− → é dada por { }1 , | ,R b a a b R− = ∈ . (a) 0 a a ∅ (b) 1 0 0 1 a b a b = (c) 3 8 10 3 0 1 1 8 0 0 1 10 0 0 0 < (d) 3 7 3 0 0 8 1 1 10 1 1 > Exemplo: Dada a relação “maior que”, :R A C→ { }(8,3), (10,3), (8,7), (10,7) , a relação dual é :R C A→ { }(3,8), (3,10), (7,8), (7,10) . Proposta de Atividade Encontre a relação dual das endorrelações a seguir. a) A endorrelação de igualdade em B, ,B = , dada por { }( , ), ( , )a a b b . b) A endorrelação ,A < , tal que { }(3,8), (3,10), (8,10) . Composição de Relações Sejam as relações :R A B→ e :S B C→ , a composição de R e S, denotada por :S R A C→ é dada por ( ) ( ){ }, |S R a c b B aRb bSc= ∃ ∈ ∧ . Exemplo: Dados os mesmos conjuntos do exemplo anterior {3,8,10}A = , { , }B a b= , {3,7}C = e as relações :R A B→ tal que { }(3, ), (8, ), (10, ), (3, )a a a b e :S B C→ tal que { }( ,3), ( ,7)a a . A relação composta :S R A C→ é { }(3,3), (3,7), (8,3), (8,7), (10,3), (10,7)S R = . 1.4.2 Tipos de relação Os tipos de relações são: funcional, injetora, total, sobrejetora, monomorfismo, epimorfismo e isomorfismo. Vamos definir cada um desses tipos. Relação funcional Dados os conjuntos A e B, a relação funcional :R A B→ relaciona cada elemento do conjunto A está relacionado com no máximo um elemento do conjunto B. Simbolicamente: ( ) ( ) ( ) ( )1 2 1 2 1 2a A b B b B aRb aRb b b∀ ∈ ∀ ∈ ∀ ∈ ∧ → = . O diagrama de Venn abaixo mostra uma situação que não pode acontecer na relação funcional. Epimorfismo ou epirrelação Dados os conjuntos A e B, uma relação :R A B→ é um epimorfismo se e somente se é uma relação funcional e sobrejetora. Ou seja, o conjunto imagem é B e cada elemento do conjunto A está relacionado com no máximo um elemento do conjunto B. Notação: :R A B−−>> Isomorfismo ou isorrelação Dados os conjuntos A e B, uma relação :R A B→ é um isomorfismo ou isorrelação se e somente se existe uma relação :S B A→ tal que AS R id= e BR S id= . Notação: :R A B↔ Dois conjuntos são isomorfos se existe uma relação de isomorfismo entre eles. Saiba mais... Para provarmos que uma relação é um isomorfismo mostrarmos que ela possui inversa, e nesse caso a relação é dual. Vimos que uma relação :R A B→ é um isomorfismo se existe uma relação :S B A→ tal que AS R id= e BR S id= . Para que isso aconteça, a relação S precisa necessariamente ser inversa da relação R e vice-versa, pois 1S S id− = e 1R R id− = . Veja o exemplo! Dados os conjuntos { , }A a b= e {3,7}C = , a relação { }( ,3), ( ,7)R a b= é um isomorfismo, pois existe a relação dual ou inversa { }1 (3, ), (7, )R a b− = , tal que { }1 ( , ), ( , ) AR R a a b b Id− = = e { }1 (3,3), (7,7) CR R Id− = = . Importante Tem um resultado interessante que envolve isorrelação ou isomorfismo, monorelação e epirrelação. Seja uma relação :R A B→ . R á uma isorrelação se, e somente se R é uma monorelação e R é uma epirrelação. Ou seja, uma relação é um isomorfismo, se e somente se for uma relação total, injetora, funcional, sobrejetora. Caso não atenda a uma dessas condições a relação não é um isomorfismo. Com esse resultado fica mais fácil verificar se uma dada relação não é um isomorfismo. Proposta de Atividade Dado o conjunto {3,8,10}A = , mostre que a endorrelação ,A < , tal que { }(3,8), (3,10), (8,10) não é um isomorfismo. Recomendações de Leitura Um banco de dados é um conjunto de dados integrado cujo objetivo é atender a um grupo de usuários. Um banco de dados pode relacionar conjuntos e nesse caso é um banco de dados relacional. Para representar um banco de dados com suas relações normalmente é utilizado um diagrama E-R. Outra curiosidade interessante é sobre as redes de Petri, que podem ser vistas como uma relação. Consulte MENEZES (2005), ver referências, para saber mais sobre bancos de dados e ver vários modelos de rede de Petri. Aproveite para pesquisar também na internet. Sucesso!