Baixe Apostila Matemática Discreta (By LCCP) e outras Notas de estudo em PDF para Cultura, somente na Docsity! Universidade de Caxias do Sul Centro de Ciências Exatas e Tecnologia Departamento de Informática Matemática Discreta Márcia Rodrigues Notare Caxias do Sul, julho de 2003. Matemática Discreta Márcia Rodrigues Notare 2 ÍNDICE 1 TEORIA DOS CONJUNTOS............................................................................................................4 1.1 RELAÇÃO DE PERTINÊNCIA............................................................................................................4 1.2 ALGUNS CONJUNTOS IMPORTANTES..............................................................................................4 1.3 RELAÇÃO DE INCLUSÃO ................................................................................................................5 1.4 IGUALDADE DE CONJUNTOS ..........................................................................................................6 1.5 PERTINÊNCIA X INCLUSÃO.............................................................................................................6 2 INTRODUÇÃO À LÓGICA MATEMÁTICA ................................................................................7 2.1 CONECTIVOS LÓGICOS ..................................................................................................................7 2.1.1 Negação ................................................................................................................................7 2.1.2 Conjunção.............................................................................................................................8 2.1.3 Disjunção..............................................................................................................................8 2.1.4 Condicional (Implicação) .....................................................................................................8 2.1.5 Bicondicional........................................................................................................................9 2.2 FÓRMULAS BEM-FORMADAS.........................................................................................................9 2.3 TABELAS-VERDADE PARA WFFS ....................................................................................................9 2.4 EQUIVALÊNCIA............................................................................................................................10 2.5 QUANTIFICADORES......................................................................................................................11 3 ÁLGEBRA DE CONJUNTOS ........................................................................................................13 3.1 OPERAÇÃO DE UNIÃO..................................................................................................................13 3.1.1 Propriedades da União.......................................................................................................14 3.2 OPERAÇÃO DE INTERSEÇÃO.........................................................................................................15 3.2.1 Propriedades da Interseção................................................................................................16 3.3 OPERAÇÃO COMPLEMENTO .........................................................................................................16 3.3.1 Propriedades de DeMorgan ...............................................................................................17 3.4 OPERAÇÃO DE DIFERENÇA ..........................................................................................................17 3.5 CONJUNTO DAS PARTES...............................................................................................................18 3.6 PRODUTO CARTESIANO ...............................................................................................................18 3.7 UNIÃO DISJUNTA.........................................................................................................................19 4 RELAÇÕES ......................................................................................................................................20 4.1 RELAÇÃO BINÁRIA ......................................................................................................................20 4.2 ENDORRELAÇÃO COMO GRAFO ...................................................................................................21 4.3 RELAÇÃO COMO MATRIZ.............................................................................................................21 4.4 PROPRIEDADES DAS RELAÇÕES ...................................................................................................22 4.4.1 Relação Reflexiva ...............................................................................................................22 4.4.2 Relação Irreflexiva .............................................................................................................23 4.4.3 Relação Simétrica...............................................................................................................24 4.4.4 Relação Anti-Simétrica .......................................................................................................24 4.4.5 Relação Transitiva..............................................................................................................25 4.5 FECHOS DE RELAÇÕES.................................................................................................................25 4.5.1 Fecho Reflexivo ..................................................................................................................26 4.5.2 Fecho Simétrico ..................................................................................................................26 4.5.3 Fecho Transitivo.................................................................................................................26 4.6 RELAÇÃO DE ORDEM...................................................................................................................26 4.6.1 Elemento Mínimo................................................................................................................28 4.6.2 Elemento Minimal...............................................................................................................28 4.6.3 Elemento Máximo ...............................................................................................................28 4.6.4 Elemento Maximal ..............................................................................................................28 4.7 RELAÇÃO DE EQUIVALÊNCIA.......................................................................................................29 4.7.1 Congruência em Z...............................................................................................................30 4.8 RELAÇÃO INVERSA......................................................................................................................30 4.9 COMPOSIÇÃO DE RELAÇÕES ........................................................................................................31 4.9.1 Composição de Relações como Produto de Matrizes .........................................................32 5 TIPOS DE RELAÇÕES...................................................................................................................33 Matemática Discreta Márcia Rodrigues Notare 5 - N, que representa o conjunto dos números naturais; - Z, que representa o conjunto dos números inteiros; - Q, que representa o conjunto dos números racionais; - I, que representa o conjunto dos números irracionais; - R, que representa o conjunto dos números reais; - C, que representa o conjunto dos números complexos. Definição de Alfabeto: um alfabeto é um conjunto finito, ou seja, um conjunto que pode ser denotado por extensão. Os elementos de uma alfabeto são chamados de símbolos ou caracteres. Definição de Palavra: uma palavra sobre um alfabeto é uma seqüência finita de símbolos do alfabeto, justapostos. ε palavra vazia Σ alfabeto Σ* conjunto de todas as palavras possíveis sobre o alfabeto Σ Exemplos: - ∅ é um alfabeto - {a, b, c, d} é uma alfabeto - N não é um alfabeto - ε é uma palavra sobre {a, b, c] - ε é uma palavra sobre ∅ - ∅* = {ε} Aplicações na Computação Chamamos de Linguagem Formal a um conjunto de palavras sobre um alfabeto. Portanto, podemos entender que uma linguagem de programação é o conjunto de todos os seus possíveis programas e que um programa é uma palavra da linguagem de programação. 1.3 Relação de Inclusão Se todos os elementos de um conjunto A são também elementos de um conjunto B, então dizemos que: BA ⊆ ou que AB ⊇ Neste caso, podemos dizer que A é um subconjunto de B. Por outro lado, se A ⊆ B e A ≠ B, ou seja, existe b∈B tal que b∉A, então dizemos que: BA ⊂ ou que AB ⊃ Neste caso, dizemos que A é um subconjunto próprio de B. Exemplos: - {1, 2, 3} ⊆ {3, 2, 1} - {1, 2} ⊆ {1, 2, 3} - {1, 2} ⊂ {1, 2, 3} A está contido em B B contém A A está contido propriamente em B B contém propriamente A Matemática Discreta Márcia Rodrigues Notare 6 Definição de Conjunto Universo: denotado por U, é o conjunto que contém todos os conjuntos que estão sendo considerados, ou seja, define o contexto de discussão. Dessa forma, U não é um conjunto fixo e, para qualquer conjunto A, temos que A ⊆ U. 1.4 Igualdade de Conjuntos Dois conjuntos A e B são ditos iguais se, e somente se, possuem os mesmos elementos, ou seja: ( )ABBABA ⊆∧⊆↔= Exemplos: - { } { }302,1,0 <∧≥Ν∈= xxx - { }0≥Ζ∈=Ν xx - {a, b, c} = {a, b, b, c, c, c} 1.5 Pertinência x Inclusão Os elementos de um conjunto podem ser conjuntos. Portanto, preste atenção nos conceitos de pertinência e inclusão. Exemplos: Considere o conjunto S = {a, b, c, d, ∅, {0}, {1, 2}}. Então: - {a} ∉ S - {a} ⊆ S - ∅ ∈ S - ∅ ⊆ S - {0} ∈ S - {1,2} ∈ S - {a, b, c, d} ∉ S - {a, b, c, d} ⊆ S Matemática Discreta Márcia Rodrigues Notare 7 2 INTRODUÇÃO À LÓGICA MATEMÁTICA Lógica é o estudo dos princípios e métodos usados para distinguir sentenças verdadeiras de falsas. Definição de Proposição: uma proposição é uma construção que se pode atribuir juízo, ou seja, que pode ser apenas verdadeira ou falsa. São exemplos de proposições: - Quatro é maior do que cinco. - Ela é muito inteligente. - São Paulo é uma cidade grande Exemplos que não são proposições: - Como vai você? - Como isso pode acontecer! - Bom dia! 2.1 Conectivos Lógicos As proposições podem ser simples (atômicas) ou compotas e os conectivos têm a função de combinar sentenças simples para formar sentenças compostas. Proposição Atômica: são proposições que não podem ser decompostas em proposições mais simples. Proposição Composta: são proposições mais complexas, compostas por proposições mais simples através dos conectivos lógicos (ou operadores lógicos). Exemplos: - Animais são peludos e aves têm penas. - Vou comprar um carro ou uma bicicleta. - Se chover então ficarei em casa. - Um triângulo é equilátero se e somente se tiver os três lados iguais. 2.1.1 Negação A negação de uma proposição é construída a partir da introdução da palavra não ou não é o caso que. Exemplos: - Brasil não é um país. - Não é o caso que quatro é maior do que cinco. Considerando que P denota uma proposição, então sua negação é denotada por: P¬ ou P~ Interpretamos a negação da seguinte forma: se P é verdadeira, então ¬P é falsa; se P é falsa, então ¬P é verdadeira. Para visualizar os valores lógicos de um conectivo utilizamos a tabela-verdade, que descreve as possíveis combinações dos valores lógicos das proposições. (lê-se "não P") Matemática Discreta Márcia Rodrigues Notare 10 a) preenchemos as colunas das letras sentenciais P e Q (à esquerda da tabela); b) preenchemos as colunas da ocorrência de ¬P e Q; c) por fim, preenchemos a coluna ∨, que é o operador principal e, portanto, determina o valor verdade da fórmula. 3. Construa a tabela verdade para a fórmula (P ∨ Q) ∧ ¬ (P ∧ Q). P Q P ∨ Q ∧ ¬ P ∧ Q V V V V V F F V V V V F V V F V V V F F F V F V V V V F F V F F F F F F V F F F O operador principal dessa fórmula é o ∧ (veja: (P ∨ Q) ∧ ¬(P ∧ Q)). Assim a coluna deste operador determina o valor-verdade da fórmula. Então, as etapas de construção são como segue: a) preenchemos as colunas das letras sentenciais P e Q (à esquerda da tabela); b) preenchemos as colunas da ocorrência de P e Q na fórmula; c) preenchemos as colunas da ocorrência de ∨ e ∧ na fórmula (mas não o ∧ principal); d) preenchemos a coluna da ocorrência da negação do operador ∧; e) finalmente, preenchemos a coluna do operador principal ∧, que determina o valor- verdade da fórmula. (Observe que o operador principal ∧ conecta as colunas de ∨ e ¬). 4. Construa a tabela verdade para a fórmula P ∨ ¬ P. P P ∨ ¬ P V V V F F F V V 5. Construa a tabela verdade para a fórmula P ∧ ¬ P. P P ∧ ¬ P V V F F F F F V Uma fórmula que assume sempre o valor lógico V, como no exemplo 4, é denominada uma tautologia. Uma tautologia é intrinsecamente verdadeira pela sua própria estrutura, ou seja, é verdadeira independentemente dos valores lógicos atribuidos as suas letras sentenciais. Por outro lado, uma fórmula que assume sempre o valor lógico F, como no exemplo 5, é denominada uma contradição. Uma contradiação é intrinsecamente falsa pela sua própria estrutura, ou seja, é falsa independentemente dos valores lógicos atribuidos as suas letras sentenciais. 2.4 Equivalência Dizemos que duas fórmulas P e Q são equivalentes se a fórmula P ↔ Q é uma tautologia. Denotamos essa propriedade por QP ⇔ A seguir, exemplos de algumas equivalências tautológicas importantes, onde 1 representa uma tautologia e 0 representa uma contradição: Matemática Discreta Márcia Rodrigues Notare 11 - Comutatividade: A ∨ B ⇔ B ∨ A A ∧ B ⇔ B ∧ A - Associatividade: (A ∨ B) ∨ C ⇔ A ∨ (B ∨ C) (A ∧ B) ∧ C ⇔ A ∧ (B ∧ C) - Distributividade: A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C) A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C) - Elemento Neutro: A ∨ 0 ⇔ A A ∧ 1 ⇔ A - Complementares: A ∨ ¬A ⇔ 1 A ∧ ¬A ⇔ O - DeMorgan: ¬(A ∨ B) ⇔ ¬A ∧ ¬B ¬(A ∧ B) ⇔ ¬A ∨ ¬B Aplicações na Computação Os conectivos lógicos E (AND), OU (OR) e NÃO (NOT), respectivamente ∧, ∨ e ¬, estão disponíveis em muitas linguagens de programação. Eles agem sobre combinações e expressões verdadeiras e falsas para produzir um valor lógico final. Tais valores lógicos permitem a decisão do fluxo de controle em programas de computador. Assim, em uma ramificação condicional de um programa, se o valor lógico da expressão condicional for verdadeiro, o programa executará um trecho do seu código; se o valor lógico da expressão condicional for falso, ele execurá outro trecho do seu código. Se a expressão condicional for substituída por outra expressão equivalente mais simples, o valor lógico não será afetado, assim como o fluxo de controle do programa, mas o novo código será mais fácil de ser entendido e poderá ser executado mais rapidamente. Veja o exemplo a seguir: if ((x < y) and not ((x < y) and (z < 1000))) do AlgumaCoisa; else do OutraCoisa; Nesse exemplo, a expressão condicional tem a forma A ∧ ¬(A ∧ B), onde A é "x < y" e B é "z < 1000". Podemos simplificar essa expressão utilizando as equivalências vistas anteriormente. A ∧ ¬(A ∧ B) ⇔ A ∧ (¬A ∨ ¬B) ⇔ (DeMorgan) (A ∧ ¬A) ∨ (A ∧ ¬B) ⇔ (Distributividade) 0 ∨ (A ∧ ¬B) ⇔ (Complemetar) (A ∧ ¬B) ∨ 0 ⇔ (Comutatividade) A ∧ ¬B (Elemento Neutro) Podemos então reecrever a proposição da seguinte forma: if ((x < y) and not (z < 1000)) do AlgumaCoisa; else do OutraCoisa; 2.5 Quantificadores Wffs formadas apenas pelos cinco operadores lógicos (¬ ∧ ∨ → ↔) têm possibilidade limitada de expressões. Por exemplo, não conseguiríamos simbolizar a sentença "Para todo x, x>0" como sendo uma proposição verdadeira sobre os inteiros positivos. Portanto novos conceitos, como o de quantificador, deve ser introduzido. Quantificadores são frases do tipo para todo, para cada ou para algum, isto é, frases que dizem "quantos objetos" apresentam determinada propriedade. Quantificador Universal: é simbolizado por ∀ e lê-se para todo, para qualquer ou para cada. Assim, a sentença acima pode ser simbolizada por: Matemática Discreta Márcia Rodrigues Notare 12 ( )( )0>∀ xx O valor lógico da expressão (∀x)(x>0) depende do domínio dos objetos sobre os quais estamos nos referindo, que chamamos de conjunto universo. Qual seria o valor lógico da expressão (∀x)P(x) em cada uma das seguintes interpretações? - P(x) é a propriedade que x é amarelo e o conjunto universo é o conjunto de todos os botões- de-ouro. - P(x) é a propriedade que x é amarelo e o conjunto universo é o conjunto de todas as flores. - P(x) é a propriedade que x é positivo ou negativo e o conjunto universo é conjunto de todos os inteiros. Quantificador Existencial: é simbolizado por ∃ e lê-se existe, existe algum, para pelo menos um, para algum. Assim, a expressão ( )( )0>∃ xx pode ser lida como "existe um x tal que x é maior do que zero". A expressão (∀x)(∃y)Q(x, y) é lida como "para todo x existe um y tal que Q(x, y)". Considerando que o conjunto universo é conjuntos dos números inteiros e que Q(x, y) é a propriedade x < y, a expressão diz que para todo inteiro x existe um inteiro maior. Esta expressão é verdadeira. Entretanto, se invertermos a ordem dos quantificadores escrevendo (∃y)(∀x)Q(x, y), a mesma interpretação diz que existe um inteiro y que é maior que qualquer outro inteiro x. Neste caso, o valor lógico da expressão é falso. Isto ressalta o fato de que a ordem dos quantificadores é importante! Matemática Discreta Márcia Rodrigues Notare 15 Logo, A ∪ A = A Comutatividade: A ∪ B = B ∪ A Prova: Caso 1: Seja x ∈ A ∪ B. x ∈ A ∪ B ⇒ x ∈ A ∨ x ∈ B ⇒ (definição de união) x ∈ B ∨ x ∈ A ⇒ (comutatividade do conectivo ∨) x ∈ (B ∪ A) (definição de união) Logo, pela definição de inclusão, (A ∪ B) ⊆ (B ∪ A). Caso 2: Seja x ∈ B ∪ A. x ∈ B ∪ A ⇒ x ∈ B ∨ x ∈ A ⇒ (definição de união) x ∈ A ∨ x ∈ B ⇒ (comutatividade do conectivo ∨) x ∈ A ∪ B (definição de união) Logo, (B ∪ A) ⊆ (A ∪ B). Portanto, pela definição de igualdade de conjuntos, podemos concluir que A ∪ B = B ∪ A. Associatividade: A ∪ (B ∪ C) = (A ∪ B) ∪ C Prova: Caso 1: Seja x ∈ A ∪ (B ∪ C). x ∈ A ∪ (B ∪ C) ⇒ x ∈ A ∨ x ∈ (B ∪ C) ⇒ (definição de união) x ∈ A ∨ (x ∈ B ∨ x ∈ C) ⇒ (definição de união) (x ∈ A ∨ x ∈ B) ∨ x ∈ C ⇒ (associatividade do conectivo ∨) x ∈ (A ∪ B) ∨ x ∈ C ⇒ (definição de união) x ∈ (A ∪ B) ∪ C (definição de união) Logo, pela definição de inclusão, temos que A ∪ (B ∪ C) ⊆ (A ∪ B) ∪ C. Caso 2: Seja x ∈ (A ∪ B) ∪ C. x ∈ (A ∪ B) ∪ C ⇒ x ∈ (A ∪ B) ∨ x ∈ C ⇒ (definição de união) (x ∈ A ∨ x ∈ B) ∨ x ∈ C ⇒ (definição de união) x ∈ A ∨ (x ∈ B ∨ x ∈ C) ⇒ (associatividade do conectivo ∨) x ∈ A ∨ x ∈ (B ∪ C) ⇒ (definição de união) x ∈ A ∪ (B ∪ C) (definição de união) Logo, (A ∪ B) ∪ C ⊆ A ∪ (B ∪ C). Portanto, pela definição de igualdade de conjuntos, podemos concluir que A ∪ (B ∪ C) = (A ∪ B) ∪ C. 3.2 Operação de Interseção Sejam A e B conjuntos. A interseção dos conjuntos A e B, denotada por BA ∩ , é como segue: { }BxAxxBA ∈∧∈=∩ Em outras palavras, a interseção de dois conjuntos A e B considera todos os elementos que pertencem ao conjunto A e ao conjunto B, ou seja, resulta em um conjunto cujos elementos pertencem aos conjuntos A e B, simultaneamente. Matemática Discreta Márcia Rodrigues Notare 16 A operação de interseção pode ser visualizada através de um diagrama de Venn, como mostrado a seguir. Exemplos: - Dados os conjuntos D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, V = {a, e, i, o, u} e P = {0, 2, 4, 6, 8, ...}, temos que D ∩ P = {0, 2, 4, 6, 8} D ∩ V = ∅ Chamamos conjuntos cuja interseção é o conjunto vazio de conjuntos disjuntos. - Dados os conjuntos A = {x ∈ Ν | x > 2} e B = { x ∈ Ν | x2 = x}, temos que A ∩ B = ∅ (conjuntos disjuntos) - Considere R, Q e I. Temos que R ∩ Q = Q R ∩ I = I Q ∩ I = ∅ - Para qualquer conjunto universo U e qualquer conjunto A ⊆ U, temos que ∅ ∩ ∅ = ∅ U ∩ A = A U ∩ ∅ = ∅ U ∩ U = U 3.2.1 Propriedades da Interseção Elemento Neutro: A ∩ U = U ∩ A = A Idempotência: A ∩ A = A Comutatividade: A ∩ B = B ∩ A Associatividade: A ∩ (B ∩ C) = (A ∩ B) ∩ C As provas são análogas à operação de união e ficam sugeridas como exercício. Propriedades que envolvem União e Interseção a) Distributividade da Interseção sobre a União: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) b) Distributividade da União sobre a Interseção: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) 3.3 Operação Complemento Suponha o conjunto universo U. O complemento de um conjunto A ⊆ U, denotado por A~ , é como segue: { }AxxA ∉∈= ~ Matemática Discreta Márcia Rodrigues Notare 17 A operação complemento pode ser visualizada através de um diagrama de Venn, como mostrado a seguir. Exemplos: - Dados o conjunto universo U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} e o conjunto A = {0, 1, 2}, temos que ~A = {3, 4, 5, 6, 7, 8, 9} - Dados o conjunto universo U = N e o conjunto A = {0, 1, 2}, temos que ~A = {x ∈ N | x > 2} - Para qualquer conjuntos universo U, temos que ~∅ = U ~U = ∅ - Considerando R como conjunto universo, temos que ~Q = I ~I = Q - Suponha U qualquer. Então para qualquer conjunto A ⊆ U, temos que A ∪ ~A = U A ∩ ~A = ∅ ~ ~A = A Podemos provar o último caso da seguinte forma: Suponha um elemento x ∈ A. x ∈ A ⇒ para ~A, x ∉ A, ou seja ¬(x ∈ A) ⇒ (definição de complemento) para ~ ~A, ¬¬(x ∈ A), ou seja, x ∈ A. 3.3.1 Propriedades de DeMorgan a) ~(A ∪ B) = ~A ∩ ~B ⇔ A ∪ B = ~(~A ∩ ~B) b) ~(A ∩ B) = ~A ∪ ~B ⇔ A ∩ B = ~(~A ∪ ~B) 3.4 Operação de Diferença Sejam A e B conjuntos. A diferença entre os conjuntos A e B, denotada por BA − , é como segue: { }BxAxxBA ∉∧∈=− Em outras palavras, a diferença entre dois conjuntos A e B considera todos os elementos que pertencem ao conjunto A e que não pertencem ao conjunto B. A operação de diferença pode ser visualizada através de um diagrama de Venn, como mostrado a seguir. Matemática Discreta Márcia Rodrigues Notare 20 4 RELAÇÕES 4.1 Relação Binária Dados dois conjuntos A e B, uma relação binária R de A em B é um subconjunto de um produto cartesiano BA× , ou seja BAR ×⊆ , onde: - A é o domínio, origem ou conjunto de partida de R - B é o contra-domínio, destino ou conjunto de chegada de R Para BAR ×⊆ , se Rba ∈, , então afirmamos que "a relaciona-se com b". Podemos denotar uma relação R da seguinte forma: BAR →: e, para um elemento Rba ∈, , podemos denota-lo como aRb . Exemplos: Sejam A = {a}, B = {a, b} e C = {0, 1, 2}. São exemplos de relações: - ∅ é uma relação de A em B - { }baaaBA ,,,=× é uma relação de A em B - Relação de Igualdade de A em A: { }aa, - Relação "menor" de C em C: { }2,1,2,0,1,0 - Relação de C em B: { }ba ,1,,0 - )()(: BPBP →⊆ - ≤ : CC → - = : AA → Endorrelação ou Auto-Relação: dado um conjunto A, uma relação do tipo AAR →: é dita uma Endorrelação ou Auto-Relação. Assim, temos que origem e destino são o mesmo conjunto e podemos denota-la por RA, . Exemplos: Seja A um conjunto. Então, são endorrelações: - ≤Ν, - ≤Ζ, - =,Q - ⊆),(AP - ⊂),(RP Uma relação binária pode ser representada no diagrama de Venn, como mostram as figuras abaixo. { }2,1,2,0,1,0, =<C A seguir, algumas definições referentes ao conceito de relação: A B a b 0 1 2 0 1 2 C C par ba, de BAR →: Matemática Discreta Márcia Rodrigues Notare 21 a) Rba ∈, : dizemos que R está definida para a e que b é a imagem de a. b) Domínio de definição: é o conjunto de todos os elementos de A para os quais R está definida. c) Conjunto imagem: conjunto de todos os elementos de B que estão relacionados com algum elemento de A. Exemplos: Dados os conjuntos A = {a}, B = {a, b} e C = {0, 1, 2}, temos que - para a endorelação <,C , o domínio de definição é o conjunto {0, 1} e o conjunto imagem é o conjuto {1, 2] - para a relação = : BA → , o domínio de definição é o conjunto {a} e o conjunto imagem também é o conjunto {a}. 4.2 Endorrelação como Grafo Toda endorrelação AAR →: pode ser representada como um grafo, onde: a) cada elemento do conjunto A é representado como um nodo do grafo; b) cada par ba, da relação é representada como uma aresta do grafo, com origem em a e destino em b. Exemplos: ∅: AA → = : { }bbaaBB ,,,=→ { }2,1,2,0,1,0, =<C CCR →: tal que { }2,2,0,2,2,0=R 4.3 Relação como Matriz Sejam A = {a1, a2, ..., an} e B = {b1, b2, ..., bm} dois conjuntos finitos. A representação da relação BAR →: como matriz é como segue: a) o número de linhas é n (número de elementos do domínio); b) o número de colunas é m (número de elementos da imagem); c) a matriz resultante possui m x n células; d) cada uma das m x n células possuem um valor lógico associado; e) se Rba ji ∈, , então a posição determinada pela linha i e pela coluna j da matriz contém valor verdadeiro (1); caso contrário, seu valor será falso (0). a a b 0 1 2 0 1 2 Matemática Discreta Márcia Rodrigues Notare 22 Exemplo: Dados os conjuntos A = {a}, B = {a, b} e C = {0, 1, 2}, temos que ∅ a a 0 = a b a 1 0 b 0 1 < 0 1 2 0 0 1 1 1 0 0 1 2 0 0 0 R 0 1 2 0 0 0 1 1 0 0 0 2 1 0 1 BA× a b a 1 1 S a b 0 1 0 1 0 1 2 0 0 ⊆ ∅ {a} {b} {a, b} ∅ 1 1 1 1 {a} 0 1 0 1 4.4 Propriedades das Relações Uma endorrelação binária em um conjunto A pode ter determinadas propriedades. A seguir serão apresentadas as propriedades que envolvem as endorrelações. 4.4.1 Relação Reflexiva Sejam A um conjunto e R uma endorrelação em A. R é uma relação reflexiva se: ( )( )aRaAa ∈∀ A negação da propriedade reflexiva é como segue: ( ) ( )( )aRaAa ¬∈∃ Exemplos: Dado o conjunto A = {0, 1, 2}, temos que as seguintes relações são reflexivas - ≤Ν, , pois todo elemento é igual a si mesmo - ⊆),(AP , pois todo conjunto está contido em si mesmo - AAA →:2 , pois esta relação contém os pares 1,1,0,0 e 2,2 - =,A , pois todo elemento é igual a si mesmo A matriz e o grafo de uma relação reflexiva apresentam uma característica especial: a diagonal principal da matriz contém somente valores lógicos verdadeiro (1) e qualquer nodo do grafo ∅: A → A =,B CCR →: tal que { }2,2,0,2,2,0=R <,C BABA →=× { } BCbaS →= :,1,,0 )()(: BPAP →⊆ Matemática Discreta Márcia Rodrigues Notare 25 - =,X - =),(XP - ∅: X → X - R,Ν , se { }22, xyyxR =Ν∈= Exemplo de relação nem simétrica, nem anti-simétrica: - SA, , se { }2,1,0,1,1,0=S A matriz e o grafo de uma relação anti-simétrica apresentam uma característica especial: na matriz, para qualquer célula verdadeira (1) em uma das metades da matriz, a correspondente célula na outra metade é falsa (0); no grafo, entre dois nodos quaisquer, existe no máximo uma aresta. Veja a matriz e o grafo referentes a um dos exemplos apresentado acima. R 0 1 2 0 1 0 0 1 0 1 1 2 0 0 0 4.4.5 Relação Transitiva Sejam A um conjunto e R uma endorrelação em A. R é uma relação transitiva se: ( )( )( )( )aRcbRcaRbAcAbAa →∧∈∀∈∀∈∀ Exemplos: Dado um conjunto X qualquer, temos que as seguintes relações são transitivas - X2: X → X - ∅: X → X - =,X - ≤Ν, - <Ζ, - ⊆),(XP - ⊂),(XP Exemplos: Dado um conjunto X qualquer, temos que as seguintes relações não são transitivas - ≠Ζ, - RA, , se { }1,2,0,2,1,0=R - RA, , se { }2,2,0,2,2,0=R 4.5 Fechos de Relações Sejam R: A → A uma endorrelação e P um conjunto de propriedades. Então, o fecho de R em relação a P é a menor endorrelação em A que contém R e que satisfaz as propriedades de P. Se a relação R já contém as propriedades de P, então ela é a seu próprio fecho em relação a P. ( )RPFECHOR −⊆ { }2,1,1,1,0,0=R 0 1 2 Matemática Discreta Márcia Rodrigues Notare 26 4.5.1 Fecho Reflexivo Suponha R: A → A uma endorrelação. Então o fecho reflexivo de R é definido como segue: { }( ) { }AaaaRRreflexivaFecho ∈∪=− , Exemplo: Dados o conjunto A = {1, 2, 3, 4, 5} e R: A → A uma endorrelação, tal que { }4,3,3,2,5,1,2,1=R , temos que - { }( ) { }5,5,4,4,4,3,3,3,3,2,2,2,5,1,2,1,1,1=− RreflexivaFecho 4.5.2 Fecho Simétrico Suponha R: A → A uma endorrelação. Então o fecho simétrico de R é definido como segue: { }( ) { }RbaabRRsimétricaFecho ∈∪=− ,, Exemplo: Dados o conjunto A = {1, 2, 3, 4, 5} e R: A → A uma endorrelação, tal que { }4,3,3,2,5,1,2,1=R , temos que - { }( ) { }1,5,3,4,4,3,2,3,3,2,1,2,5,1,2,1=− RsimétricaFecho 4.5.3 Fecho Transitivo Suponha R: A → A uma endorrelação. Então o fecho transitivo de R é definido como segue: a) se Rba ∈, , então { }( )RtransitivaFechoba −∈, ; b) se { }( )RtransitivaFechoba −∈, e { }( )RtransitivaFechocb −∈, , então { }( )RtransitivaFechoca −∈, . Exemplo: Dados o conjunto A = {1, 2, 3, 4, 5} e R: A → A uma endorrelação, tal que { }4,3,3,2,5,1,2,1=R , temos que - { }( ) { }4,3,4,2,3,2,5,1,4,1,3,1,2,1=− RtransitivaFecho Algumas notações são importantes e podem ser utilizadas para simplificar e representar as seguintes relações: a) { }( )RtransitivaFechoR −=+ b) { }( )RtransitivareflexivaFechoR ,* −= Portanto, considerando o exemplo acima, temos que - { }5,5,4,4,4,3,3,3,4,2,3,2,2,2,5,1,4,1,3,1,2,1,1,1* =R 4.6 Relação de Ordem Intuitivamente, podemos pensar numa relação de ordem quando lembramos de uma fila no banco, de uma fila de alunos dispostos numa sala de aula, na relação "menor ou igual" no números naturais, etc. Matemática Discreta Márcia Rodrigues Notare 27 Ordem parcial: é toda relação binária em um conjunto A que é, simultaneamente, reflexiva, anti-simétrica e transitiva. São exemplos de relação de ordem parcial: - ≤Ν, - ⊆Ν),(P - ydividex __,+Ζ Se R é uma relação de ordem parcial em A, então dizemos que RA, é um conjunto parcialmente ordenado. Se A é um conjunto finito, então podemos representar visualmente um conjunto parcialmente ordenado em A por um diagrama de Hasse. Cada elemento de A é representado por um ponto (vértice) do diagrama. O diagrama de Hasse pode ser construído com base num grafo, onde as arestas que representam as relações reflexivas e transitivas ficam implícitas no diagrama. Veja o exemplo a seguir. Exemplo: Dados o conjunto A = {1, 2, 3} e a relação de ordem ≤,A , temos seus respectivos grafo e diagrama de Hasse representados abaixo. Observe que os elementos da relação são representados no diagrama em ordem crescente de baixo para cima, ou seja, como 1 ≤ 2, então o elemento 1 aparece abaixo do elemento 2. As orientação das arestas torna-se, dessa forma, desnecessária, já que a disposição dos elementos no diagrama preserva essa informação. Exemplos: - Dada a relação de ordem { }( ) ⊆,2,1P , seu diagrama de Hasse está representado abaixo. - Dados o conjunto A = {1, 2, 3, 6, 12, 18} e a relação de ordem "x divide y", o diagrama de Hasse está representado abaixo. 1 2 3 3 1 2 (grafo) (diagrama de Hasse) ∅ {1} {2} {1,2} Matemática Discreta Márcia Rodrigues Notare 30 Exemplo: Considere o conjunto dos números naturais e a relação de equivalência "__", paréyx +Ν . Tal relação divide o conjunto N em duas partes, ou seja, em duas classes de equivalências. Se x é par, então x + y é par, para todo número par; se x é ímpar, então x + y é ímpar para todo número ímpar. Assim, todos os números pares formam uma classe de equivalência e todos os números ímpares formam uma segunda classe de equivalência. Podemos representar essa partição de N como mostra figura abaixo. Observe que as classes de equivalência podem ser representadas por qualquer objeto pertencente à ela: - classe dos pares: [2] = [6] = [1034] = {0, 2, 4, 6, ...} - classe dos ímpares: [1] = [11] = [2451] = {1, 3, 5, 7, ...} Exemplo: Para cada uma das relações a seguir, descreva as classes de equivalência correspondentes. a) =Ν, Possui n classes de equivalência, tais que cada classe de equivalência contém um único elemento. [n] = {n} b) Em A = {1, 2, 3} e { }1,2,2,1,3,3,2,2,1,1=R As classes de equivalência são as seguintes: [1] = {1, 2} = [2] [3] = {3} 4.7.1 Congruência em Z Considere o conjunto dos números inteiros Z e um número inteiro 1>m . Dizemos que x é congruente a y módulo m, denotada por ( )myx mod≡ se yx − é divisível por m, ou seja, se kmyx += para algum inteiro k. A relação de congruência em Z define uma relação de equivalência em Z. Para verificar que isso é válido, temos que mostrar que a relação de congruência em Z é uma relação reflexiva, simétrica e transitiva. Acompanhe o raciocínio a seguir: para qualquer inteiro x, temos que ( )mxx mod≡ , pois 0=− xx é divisível por m. Logo, temos que a relação é reflexiva. Suponha que ( )myx mod≡ , então yx − é divisível por m. Então ( ) xyyx −=−− também é divisível por m. Logo, temos que a relação é simétrica. Suponha agora que ( )myx mod≡ e que ( )mzy mod≡ , então yx − e zy − são divisíveis por m. Então, temos que a soma ( ) ( ) zxzyyx −=−+− também é divisível por m. Logo, ( )mzx mod≡ e a relação é transitiva. Assim, mostramos que a relação de congruência módulo m em Z é, simultaneamente, reflexiva, simétrica e transitiva e, portanto, é uma relação de equivalência. 4.8 Relação Inversa Seja uma relação R: A → B. Então, a relação inversa é como segue: Matemática Discreta Márcia Rodrigues Notare 31 { }RbaabABR ∈=→− ,,:1 Exemplos: - Dados os conjuntos A = {a, b} e B = {2, 3, 4} e a relação { }baABR ,3,,2: =→ , temos que a relação inversa de R, R-1 é dada por { }3,,2,:1 baBAR =→− - Dados o conjunto C = {2, 3, 4} e a relação <,C , a relação inversa pode ser visualizada no diagrama a seguir: < : CC → =><−1 : CC → 4.9 Composição de Relações Sejam A, B e C conjuntos, e R: A → B e S: B → C relações. A composição de R e S, denotada por CASR →: , é tal que ( )( )( ) ( )( )cSRabScaRbCcBbAa $→∧∈∀∈∀∈∀ Ou seja, { }ScbRbaBbcaSR ∈∧∈∧∈∃= ,,,$ Exemplo: Dados os conjuntos A = {a, b, c, d}, B = {1, 2, 3, 4, 5} e C = {x, y, z} e as relações { }5,,4,,3,,1,: dbbaBAR =→ e { }zyyxCBS ,5,,5,,2,,1: =→ , temos que a composição de R e S é como segue { }zdydxaSR ,,,,,=$ e pode ser visualizada no diagrama a seguir: A composição de relações é associativa, ou seja: Sejam as relações R: A → B, S: B → C e T: C → D. Então, temos que ( ) ( ) RSTRSTRST $$$$$$ == 2 3 4 2 3 4 2 3 4 2 3 4 a b c d 1 2 3 4 5 x y z SR SR A B C Matemática Discreta Márcia Rodrigues Notare 32 4.9.1 Composição de Relações como Produto de Matrizes A composição de relações pode ser vista como o produto de matrizes. Veja o exemplo a seguir. Exemplo: Sejam R e S relações em X = {a, b, c} definidas por { }abcabaR ,,,,,= e { }acbbabcaS ,,,,,,,= . Determinaremos a composição de R e S através da multiplicação das correspondentes matrizes. Abaixo, temos as correspondentes matrizes que representam as relações R e S. R a b c a 0 1 1 b 1 0 0 c 0 0 0 S a b c a 0 0 1 b 1 1 0 c 1 0 0 A multiplicação das matrizes R e S é dada como segue:      ++ ++ ++ =⋅ 000 000 110 SR 000 000 010 ++ ++ ++      =      ++ ++ ++ 0 0 2 000 001 000 0 0 1      0 1 0 Assim, temos que a composição SR é dada pela matriz SR ⋅ , ou seja, { }cbbaaaSR ,,,,,=$ . Matemática Discreta Márcia Rodrigues Notare 35 5.5 Monomorfismo Uma relação R: A → B é um monomorfismo se, e somente se, for simultaneamente uma relação total e injetora. Dessa forma, o domínio de definição é o próprio conjunto A e cada elemento de B está relacionado com no máximo um elemento de A. A matriz de um monomorfismo tem a seguinte característica: existe pelo menos um valor verdadeiro em cada linha da matriz (o que carateriza a relação total) e existe no máximo um valor lógico verdadeiro em cada coluna (o que carateriza a relação injetora). Exemplo: A relação BA →=: , onde A = {a} e B = {a, b}, é um monomorfismo. 5.6 Epimorfismo Epimorfismo é o conceito dual (inverso) de monomorfismo. Uma relação R: A → B é um epimorfismo se, e somente se, for simultaneamente uma relação funcional e sobrejetora. Dessa forma, o conjunto imagem é o próprio conjunto B e cada elemento de A está relacionado com no máximo um elemento de B. A matriz de um epimorfismo tem a seguinte característica: existe pelo menos um valor verdadeiro em cada coluna da matriz (o que carateriza a relação sobrejetora) e existe no máximo um valor lógico verdadeiro em cada linha (o que carateriza a relação funcional). Exemplo: São exemplos epimorfismo, sendo que onde A = {a}, B = {a, b} e C = {0, 1, 2}: - AA →=: - S: C → B, tal que { }baS ,1,,0= 5.7 Isomorfismo Uma relação R: A → B é um isomorfismo se, e somente se, existe uma relação S: B → A tal que: =SR idA =RS idB onde idA é uma endorrelação de igualdade em A =,A e idB é uma endorrelação de igualdade em B =,B , chamadas de relação identidade. Assim, se =SR idA e =RS idB, podemos afirmar que a relação R possui inversa. Ainda, se existe um isomorfismo entre dois conjuntos, podemos chama-los de conjuntos isomorfos. a b a c b A B Matemática Discreta Márcia Rodrigues Notare 36 Exemplo: Dados os conjuntos A = {a, b, c} e B = {e, f, g} e a relação R: A → B tal que { }gcfbeaR ,,,,,= . R é um isomorfismo, pois considerando a relação inversa de R, { }cgbfaeABR ,,,,,:1 =→− , temos que { }==− ccbbaaRR ,,,,,1$ idA { }==− ggffeeRR ,,,,,1 $ idB Logo, a relação R possui inversa e os conjuntos A e B são conjuntos isomorfos. Teorema: Seja R: A → B uma relação. Então R é um isomorfismo se, e somente se, R for simultaneamente um monomorfismo e um epimorfismo. Dessa forma, uma relação é um isomorfismo se, e somente se, for simultaneamente uma relação total, injetora, funcional e sobrejetora. Podemos observar que para uma relação ser um isomorfismo, os conjuntos origem e destino devem possuir o mesmo número de elementos. Matemática Discreta Márcia Rodrigues Notare 37 6 FUNÇÕES PARCIAIS E TOTAIS Uma função parcial nada mais é do que um relação que é funcional. Se a relação funcional for também total, então a denominamos de função total. Portanto, podemos dizer que toda função total é uma função parcial e que toda função parcial é uma relação. Entretanto, nem toda relação é uma função parcial, assim como nem toda função parcial é uma função total. 6.1 Função Parcial Uma função parcial é uma relação funcional, ou seja, cada elemento do domínio está relacionado a no máximo um elemento do contra-domínio. Um elemento pertencente à função parcial fba ∈, pode ser representado por ( ) baf = . Exemplo: Dados os conjuntos A = {a} e B = {x, y} temos que as seguintes relações são funções parcias: - { }ayaxABR ,,,: =→ - = : B → B Vale observar que a relação inversa de uma função parcial não necessariamente é uma função parcial. Se considerarmos o conjunto A = {0, 1, 2} e a função parcial f: A → A tal que { }1,2,1,0=f , temos que a relação inversa de f, { }2,1,0,11 =−f não é uma relação funcional e, consequentemente, não é uma função parcial. Para que a relação inversa de uma relação funcional seja uma função parcial, ela deve ser também injetora (que é o dual de funcional). 6.2 Função Total Uma função total é uma função parcial que é total. Em outras palavras, é uma função parcial definida para todos os elementos do domínio. Se uma função é total, dizemos apenas que é uma função, ou seja, sempre que mencionarmos apenas função, estamos nos referindo a funções totais. Assim, podemos verificar as seguintes propriedades: - Função Injetora = monomorfismo - Função Sobrejetora = epimorfismo - Função Bijetora = isomorfismo Ou seja, uma função bijetora é uma função injetora e sobrejetora. Da mesma forma que para funções parciais, a relação inversa de uma função não necessariamente é uma função. Considerando os conjuntos A = {0, 1} e B = {0, 1, 2} e a função { }0,2,1,1,0,0: =→ ABf , temos que a relação inversa de f, { }2,0,1,1,0,01 =−f não é uma relação funcional e, portanto, não é uma função. Podemos considerar também a função g: A → B, tal que { }1,1,0,0=g . A inversa de g, { }1,1,0,01 =−g não é uma relação total e, portanto, não é uma função. Para que a relação inversa de uma função f seja uma função, f deve ser uma função bijetora. Matemática Discreta Márcia Rodrigues Notare 40 ( ){ }agaAaB ∉∈= Como A é um conjunto, ele pode ser um conjunto de conjuntos. Suponha b ∈ A, tal que ( ) Bbg = . Neste caso: - se b ∈ B, então, pela definição de B, tem-se que b ∉ g(b) = B. - se b ∉ g(B), então, pela definição de B, tem-se que b ∈ g(b) = B. O que é uma contradição! Logo, não existe uma função bijetora entre A e 2A. O conjunto das partes de N é equipotente ao conjunto dos números reais R. Considerando que 2k denota o cardinal do conjunto das partes com cardinalidade k, tem-se que 02χ é a cardinalidade do conjunto dos números reais, ou seja, é a cardinalidade do continuum. Teorema: O conjunto I = [0, 1] de todos os números reais entre 0 e 1 é não-contável. Prova (por absurdo): Suponha I contável. Então, existe uma função bijetora Ι→Ν:f . Seja ( ) ( ) ( ) ,...3,2,1 321 afafaf === , isto é, { },...,, 321 aaaI = . Vamos listar seus elementos em uma coluna com sua expansão decimal: ... ...,0 ...,0 ...,0 ...,0 444342414 343332313 242322212 141312111 xxxxa xxxxa xxxxa xxxxa = = = = onde { }9,...,2,1,0∈ijx . Seja ...,0 4321 yyyyb = um número real obtido da seguinte forma:    = 2 1 iy Portanto, Ι∈b . Mas 1ab ≠ , pois 111 xy ≠ 2ab ≠ , pois 222 xy ≠ 3ab ≠ , pois 333 xy ≠ ... Portanto, { },...,, 321 aaab =Ι∉ , o que é uma contradição, já que Ι∈b ! Logo, a suposição de que I é contável é falsa e, portanto, I é não-contável, como queríamos provar. se 1≠iix se 1=iix Matemática Discreta Márcia Rodrigues Notare 41 8 INDUÇÃO MATEMÁTICA Para entender intuitivamente o que é a Indução Matemática, vamos ilustrar a técnica: - Você está subindo uma escada infinitamente alta. Como saber se será capaz de chegar a um degrau arbitrariamente alto? - Suponha as seguintes hipóteses: 1. Você consegue alcançar o primeiro degrau 2. Uma vez chegando a um degrau, você sempre é capaz de chegar ao próximo - Pela hipótese 1, você é capaz de chegar ao primeiro degrau; pela hipótese 2, você consegue chegar ao segundo; novamente pela hipótese 2, chega ao terceiro degrau; e assim sucessivamente. Essa mesma propriedade é utilizada para provar propriedades dos números inteiros positivos! Considere que P(n) denota que o número inteiro positivo n possui a propriedade P. 1. Assumimos que o número 1 tem a propriedade P: P(1) 2. Supomos que a propriedade P é válida para qualquer inteiro positivo k: P(k) 3. Provamos que, se a propriedade P é válida para qualquer número inteiro k, então é válida para o próximo inteiro positivo k+1: P(k) → P(k+1) 8.1 Primeiro Princípio de Indução Matemática O Primeiro Princípio de Indução Matemática é formulado da seguinte forma: 1. P(1) é verdade 2. (∀k)(P(k) é verdade → P(k+1) é verdade) E com isto, provamos que a propriedade é verdadeira para todo inteiro positivo n, ou seja, que P(n) é verdade. Exemplo: Suponha que um ancestral casou-se e teve dois filhos. Vamos chamar esses dois filhos de geração 1. Suponha agora que cada um desses filhos teve dois filhos. Então a geração 2 contém quatro descendentes. Imagine que esse processo continua de geração em geração. A figura abaixo ilustra esse processo: Então, podemos deduzir que: - A geração 1 possui 2 descendentes - A geração 2 possui 4 descendentes - A geração 3 possui 8 descendentes - E assim sucessivamente... Geração 1 2 3 ... Descendentes 2 = 21 4 = 22 8 = 23 ... Matemática Discreta Márcia Rodrigues Notare 42 Então, podemos fazer a seguinte conjectura: a geração n possui 2n descendentes. Ou seja, podemos escrever que: ( ) nnP 2= Agora, vamos provar que nossa conjectura está correta, através do primeiro princípio de indução matemática: Base de Indução (estabelecemos a veracidade da propriedade para n = 1): ( ) 221 1 ==P Hipótese de Indução (supomos que a propriedade é válida para algum inteiro k, k ≥ 1): ( ) kkP 2= Passo de Indução (provamos que a propriedade é válida para o inteiro seguinte k+1, ou seja, que P(k) → P(k+1)): ( ) 121 +=+ kkP ( ) ( ) 122221 +=⋅=⋅=+ kk HI kPkP (o número de descendentes dobra de uma geração para outra) A tabela abaixo, resume os três passos necessários para uma demonstração que usa o primeiro princípio de indução. Demonstração por Indução Passo 1 Prove a base de indução Passo 2 Suponha ( )kP Passo 3 Prove ( )1+kP Vejamos mais alguns exemplos: Exemplo: Prove que a equação a seguir é verdadeira para qualquer inteiro positivo n. ( ) 212...531 nn =−++++ Base de Indução - P(1) Verificamos que a propriedade é válida para n = 1. ( ) 211:1 =P Hipótese de Indução - P(k) Supomos que a propriedade é válida para n = k. ( ) ( ) 212...531: kkkP =−++++ Passo de Indução - P(k + 1) Tentamos provar que a propriedade é válida para n = k + 1, ou seja, que: ( ) ( )[ ] ( )2 ? 1112...531:1 +=−++++++ kkkP Matemática Discreta Márcia Rodrigues Notare 45 Base de Indução - P(1) Verificamos que a propriedade é válida para n = 1. ( ) 31412:1 12 =−=−⋅P é divisível por 3 Hipótese de Indução - P(k) Supomos que a propriedade é válida para n = k. ( ) 12: 2 −kkP é divisível por 3, ou seja, que mk 3122 =− e que, portanto, 1322 += mk Passo de Indução - P(k + 1) Provamos que a propriedade é válida para n = k + 1. ( ) ( ) 12:1 12 −+ +kkP é divisível por 3? ( ) ( ) ( )143 312 1412 1132 1)22( 12 12 2 22 22 12 +⋅ =+ =−+ =−+⋅ =−⋅ =− =− + +⋅ m m m m HI k k k Exemplo: Prove que nn 32 > para 4≥n . Base de Indução - P(4) Verificamos que a propriedade é válida para n = 4. ( ) 4312164:4 2 ⋅=>=P Hipótese de Indução - P(k) Supomos que a propriedade é válida para n = k. ( ) 4,3: 2 ≥> kkkkP Passo de Indução - P(k + 1) Provamos que a propriedade é válida para n = k + 1. ( ) ( ) ( )131:1 ? 2 +⋅>++ kkkP ( ) ( )13 33 183 123 12 1 2 2 +⋅ =+ >++ ≥++ >++ =+ k k k kk kk k HI Exemplo: Prove que nn 32 1 <+ para todo 1>n . Base de Indução - P(2) Verificamos que a propriedade é válida para n = 2. (pois 4≥k ) Matemática Discreta Márcia Rodrigues Notare 46 ( ) 212 3982:2 =<=+P Hipótese de Indução - P(k) Supomos que a propriedade é válida para n = k. ( ) 1,32: 1 ><+ kkP kk Passo de Indução - P(k + 1) Provamos que a propriedade é válida para n = k + 1. ( ) )1( ? 1)1( 32:1 +++ <+ kkkP 111)1( 33323222 ++++ =⋅<⋅<⋅= kk HI kkk Matemática Discreta Márcia Rodrigues Notare 47 9 RECURSÃO E RELAÇÕES DE RECORRÊNCIA 9.1 Definições Recorrentes Uma definição onde o item definido aparece como parte da definição é chamada de definição por recorrência, ou definição recorrente, ou ainda definição por indução. Uma definição recorrente é formada por duas partes: 1. Base ou condição básica, onde algum(s) caso(s) simples do item que está sendo definido é dado explicitamente. 2. Um passo de indução ou recorrência, onde novos casos do item que está sendo definido são dados em função de casos anteriores. A parte 1 da definição nos permite começar, fornecendo alguns casos simples e concretos. A parte 2 nos permite construir novos casos, a partir destes mais simples e assim por diante. Daí o nome definição por indução, devido à analogia com as demonstrações por indução. 9.2 Seqüências Definidas por Recorrência Uma seqüência S é uma lista de objetos numerados em determinada ordem. Existe um primeiro objeto, um segundo objetos, e assim por diante. S(k) denota o k-ésimo objeto da seqüência. Uma seqüência é definida por recorrência nomeando-se o primeiro valor da seqüência e depois definindo os valores subseqüentes na seqüência em termos de valore anteriores. Exemplo: A seqüência S é definida por recorrência por 1. S(1) = 2 2. S(n) = 2S(n - 1) para 2≥n Assim, o primeiro valor da seqüência é 2; o segundo valor da seqüência é S(2) = 2S(2-1) = 2S(1) = 2 ⋅ 2 = 4; o terceiro valor da seqüência é S(3) = 2S(2) = 2 ⋅ 4 = 8; e assim por diante. Continuando a seqüência, temos 2, 4, 8, 16, 32, ... Exemplo: Escreva os cinco primeiro valores da seqüência T, tal que: 1. T(1) = 1 2. T(n) = T(n - 1) + 3, para 2≥n 1, 4, 7, 10, 13 Seqüência de Fibonacci: é uma seqüência introduzida pelo matemático italiano Fibonacci e é definida por recorrência da seguinte forma: F(1) = 1 F(2) = 1 F(n) = F(n – 2) + F(n – 1), para n ≥ 2 Traduzindo, qualquer valor da seqüência de Fibonacci, exceto os dois primeiros, é dado pela soma de seus dois valores anteriores. Matemática Discreta Márcia Rodrigues Notare 50 Elemento Inverso: Seja AAA →×⊕ : uma operação binária interna e fechada e x elemento qualquer de A. Então, a operação ⊕ tem elemento inverso se: ( )( )( )exxxxxx =⊕=⊕∃∀ −−− 111 Exemplos: a) A operação de união )()()(: APAPAP →×∪ satisfaz as propriedades comutativa, associativa e elemento neutro (conjunto vazio). b) A operação de adição nos números naturais Ν→Ν×Ν+ : satisfaz as propriedades comutativa, associativa e elemento neutro (zero). c) A operação de adição nos números inteiros Ζ→Ζ×Ζ+ : , além de satisfazer as propriedades comutativa, associativa e elemento neutro (zero) satisfaz também a propriedade elemento inverso, já que, para qualquer inteiro n, basta tomar –n como elemento inverso, ou seja: ( ) 0=+−=−+ nnnn 10.3 Grupóides Um grupóide é uma álgebra interna (operação binária interna) cuja operação interna é fechada. Seja AAA →×⊕ : uma operação binária e interna. Se a operação for fechada, então ⊕,A é um grupóide. Se, adicionalmente, a operação for comutativa, então ⊕,A é um Grupóide Abeliano. Exemplos: a) Seja Σ um alfabeto não-vazio. A operação de concatenação ***: Σ→Σ×Σ• é fechada, mas não é comutativa. Portanto, •Σ ,* é um grupóide. b) Seja A um conjunto. As operações de união e interseção, )()()(: APAPAP →×∪ e )()()(: APAPAP →×∩ respectivamente, são fechadas e comutativas. Portanto, ∪),(AP e ∩),(AP são grupóides abelianos. c) As seguintes operações são grupóides abelianos: - +Ν, e ×Ν, - +Ζ, e ×Ζ, - +,R e ×,R d) As seguintes operações não são grupóides: - −Ν, - ÷,R 10.4 Semigrupos Um semigrupo é um grupóide cuja operação interna é associativa. Portanto, é uma álgebra cuja operação é fechada e associativa. Matemática Discreta Márcia Rodrigues Notare 51 Seja AAA →×⊕ : um grupóide. Se ⊕,A for associativa, então ⊕,A é um semigrupo. Se, adicionalmente, a operação for comutativa, então ⊕,A é um Semigrupo Abeliano. Exemplos: a) A operação de concatenação ***: Σ→Σ×Σ• é fechada e associativa. Portanto, •Σ ,* é um semigrupo. b) As operações de união e interseção, )()()(: APAPAP →×∪ e )()()(: APAPAP →×∩ respectivamente, são fechadas, associativas e comutativas. Portanto, ∪),(AP e ∩),(AP são semigrupos abelianos. c) As seguintes operações são semigrupos abelianos: - +Ν, e ×Ν, - +Ζ, e ×Ζ, - +,R e ×,R d) As seguintes operações não são semigrupos: - −Ζ, - { }÷− ,0R 10.5 Monóides Um monóide é um semigrupo cuja operação possui elemento neutro. Portanto, um semigrupo é, simultaneamente, fechado, associativo e possui elemento neutro. Seja ⊕,A um semigrupo. Se AAA →×⊕ : possui elemento neutro, então eA ,,⊕ é um monóide. Se, adicionalmente, a operação for comutativa, então eA ,,⊕ é um Monóide Abeliano. Exemplos: a) As operações de união e interseção, )()()(: APAPAP →×∪ e )()()(: APAPAP →×∩ respectivamente, são fechadas, associativas, comutativas e possuem elemento neutro. Portanto, ,),( ∪AP ∅ e AAP ,),( ∩ são monóides abelianos. b) As seguintes operações são monóides abelianos: - 0,,+Ν e 1,,×Ν - 0,,+Ζ e 1,,×Ζ - 0,,+R e 1,,×R c) A operação de concatenação •Σ ,* e um semigrupo e possui elemento neutro (a palavra vazia ε). Portanto, ε,,* •Σ é um monóide. Matemática Discreta Márcia Rodrigues Notare 52 10.6 Grupos Um grupo é um monóide cuja operação é possui elemento inverso. Portanto, um grupo é uma operação que é, simultaneamente, fechada, associativa, possui elemento neutro e elemento inverso. Seja ⊕,A um monóide. Se AAA →×⊕ : possui elemento inverso, então eA ,,⊕ é um grupo. Se, adicionalmente, a operação for comutativa, então eA ,,⊕ é um Grupo Abeliano. Exemplos: a) A operação ×+ , *R é um grupo abeliano, pois é uma operação fechada, associativa, comutativa, possui elemento neutro 1 e elemento inverso. b) A operação ×,R não é um grupo, pois não há número real x tal que: 100 =⋅=⋅ xx Ou seja, o número 0 não possui elemento inverso! A tabela abaixo apresenta um resumo das estruturas algébricas estudadas e suas respectivas propriedades. Propriedades Tipo de Álgebra Fechada Associativa Elemento Neutro Elemento Inverso Grupóide Semigrupo Monóide Grupo Exemplo: Seja ( )ΖΜ 2 o conjunto de todas as matrizes 22 × com elementos inteiros. ( ) +ΖΜ ,2 é um grupo abeliano? Para verificarmos se a operação ( ) +ΖΜ ,2 é um grupo abeliano, precisamos verificar quais propriedades ela satisfaz: - ( ) +ΖΜ ,2 é fechada, pois a adição de duas matrizes 22 × é uma matriz 22 × . - ( ) +ΖΜ ,2 é associativa, pois    c a      +   g e d b    +   k i h f    =     c a m j    + +   +   kg ie d b =     + + mh jf ( ) ( )  ++ ++ kgc iea ( ) ( ) ( ) ( )  ++ ++ =   ++ ++ kgc iea mhd jfb ( ) ( ) =  ++ ++ mhd jfb      c a    +   g e d b    +     k i h f    m j