Matemática Discreta - Somatórios, Matrizes, Contagem e Relações

Recife 2010 Matemática Discreta Francisco Flávio Modesto de Andrade Universidade Federal Rural de Pernambuco Reitor Prof Valmar Corrêa de Andrade ViceReitor Prof Reginaldo Barros PróReitor de Administração Prof Francisco Fernando Ramos Carvalho PróReitor de Extensão Prof Paulo Donizeti Siepierski PróReitor de Pesquisa e PósGraduação Prof Fernando José Freire PróReitor de Planejamento Prof Rinaldo Luiz Caraciolo Ferreira PróReitora de Ensino de Graduação Profª Maria José de Sena Coordenação Geral de Ensino a Distância Profª Marizete Silva Santos Produção Gráfica e Editorial Capa e Editoração Allyson Vila Nova Rafael Lira Italo Amorim e Gláucia Micaele Revisão Ortográfica Marcelo Melo Ilustrações Allyson Vila Nova e Diego Almeida Coordenação de Produção Marizete Silva Santos Sumário Apresentação 5 Capítulo 1 Somatório representando somas 6 11 Conhecendo o somatório 6 12 Propriedades do somatório e algumas somas especiais 8 13 Dígito Verificador 12 Capítulo 2 Matrizes armazenando dados 25 21 Matriz 25 22 Definição 27 23 Tipos especiais de matrizes 27 24 Operações com matrizes 30 25 Matrizes Booleanas 34 Capítulo 3 Princípios de Contagem como contar 45 31 Listas 45 32 Princípio multiplicativo contagem de listas de comprimento dois 46 33 Listas de comprimento maior do que dois 47 34 Listas de comprimento k sem repetição de elementos 48 35 Princípio Aditivo 48 36 Fatorial 54 37 Permutações 55 38 Combinações 55 Capítulo 4 Relações uma abordagem 65 41 Tipos de Relações Binárias 66 42 Relações binárias em um conjunto A 68 43 Operações com relações como operar com relações binárias 69 44 Propriedades das Relações definidas em um conjunto A 71 45 Representação gráfica de Relações Binárias 73 46 Grafo de uma relação em um conjunto A 73 47 Relação nária 75 48 Álgebra Relacional 79 Considerações Finais 90 Apresentação Caroa cursista Seja bemvindoa a mais um módulo de Matemática Discreta Dando continuidade à disciplina abordaremos neste segundo fascículo alguns tópicos de importância e aplicabilidade nas áreas de informática tais como somatórios matrizes princípios de contagem e relações No primeiro capítulo você estudará as propriedades do somatório e como elas são úteis na determinação de somas especiais e de uso frequente na matemática No segundo capítulo você descobrirá como as matrizes podem ser utilizadas para armazenamento de dados e as operações aritméticas que nelas podem ser efetuadas Além disso conhecerá as matrizes booleanas muito empregadas na informática No terceiro capítulo você terá oportunidade de conhecer diversas técnicas de contagem empregadas no cálculo e na diferenciação dos agrupamentos que se podem formar com os elementos de um dado conjunto Por fim no quarto capítulo será abordado o conceito de relações entre dois ou mais conjuntos as operações entre relações e como elas podem ser usadas para manipulação de um banco de dados Esperamos que você aproveite ao máximo este segundo módulo estudando detalhadamente o assunto e realizando todos os exercícios propostos Bons estudos 6 Matemática Discreta Capítulo 1 Somatório representando somas Neste capítulo mostraremos o uso do somatório na escrita de somas de parcelas variáveis ou constantes Estudaremos as propriedades do somatório e como elas são úteis na determinação de somas especiais e de uso frequente na matemática Por fim apresentaremos métodos de geração de dígitos verificadores em sequências especiais de algarismos tais como o CPF código de barras e número de conta corrente bancária 11 Conhecendo o somatório Você já se deparou com a necessidade de escrever expressões que envolvem somas com termos que obedecem a certa lei de formação do tipo 1 2 3 4 100 Se temos uma soma de n parcelas x1 x2 x3 xn saiba que podemos codificála através do uso de somatório assim x1 x2 x3 xn n i ix 1 A letra maiúscula grega sigma é o símbolo utilizado para representar as operações de adição entre as parcelas e xi é a parcela genérica Para representar a parte variável de cada parcela utilizamos a letra i e indicamos a variação de i no caso i varia de 1 até n A expressão n i ix 1 é lida assim soma dos valores xi para i variando de 1 até n Você deve estar atento para o fato de que é fundamental que o índice i assuma todos os valores inteiros consecutivos entre dois valores dados inclusive Assim a soma x1 x2 x3 pode ser escrita 3 i 1 ix 7 Matemática Discreta Compreenda melhor a aplicação do conceito de somatório através dos exemplos seguintes Exemplo 1 5 i 1 ix x1 x2 x3 x4 x5 é a soma de 5 parcelas Exemplo 2 7 1 i ix x x2 x3 x7 representa a soma de 7 parcelas O índice i variando de 1 a 7 indica quantas parcelas contém a soma como identifica as parcelas como potências de expoente inteiro Exemplo 3 7 i 3 ix x3 x4 x5 x6 x7 indica a soma de 7 3 1 5 parcelas conforme a observação ao lado Exemplo 4 2x1 3x2 4x3 5x4 indica a soma de 4 parcelas xi multiplicadas por coeficientes variáveis i1 Exemplo 5 Para representar por meio da notação de somatório a soma dos números pares iniciando por 2 até 40 isto é 2 4 6 8 40 denotaremos as parcelas variáveis por xi 2i com o índice i variando de 1 até 20 de forma que podemos escrever 2 4 6 8 40 Exemplo 6 A soma dos números ímpares 1 3 5 7 9 11 se escreve na notação de somatório tomando as parcelas xi 2i 1 com i variando de 1 até 6 conforme podemos observar na tabela seguinte i 1 2 3 4 5 6 xi 2i1 211 1 211 3 231 5 241 7 251 9 261 11 Exemplo 7 A expressão 128 1 8 1 4 1 2 1 indica a soma de parcelas iguais a uma fração onde o numerador é 1 e os denominadores são potências inteiras de 2 21 22 23 até 27 de modo que podemos escrever a soma sob a forma de somatório com xi i2 1 do seguinte modo 128 1 8 1 4 1 2 1 7 1 2 1 i i Lembrete Para contar quantos termos uma soma tem basta calcular no somatório a diferença entre o índice superior e o inferior e somar 1 A soma ak ak1 ak2 an n i k ia tem n k 1 termos 8 Matemática Discreta Exemplo 8 Para escrever a expressão sob a forma de somatório você deve notar que os denominadores assumem valores crescentes de 1 até 50 indicando que a soma é constituída por 50 parcelas e que a variação do índice i é de i 1 até i 50 Além disso verificase que os numeradores são números ímpares da forma 2i 1 com a mesma variação do índice i A soma acima pode ser então escrita assim 50 1 2 1 i i i Exemplo 9 A soma S dos 30 primeiros termos da série pode ser expressa por meio de um somatório lembrando que as parcelas xi são frações cujos numeradores constituem uma progressão aritmética de termo inicial 480 e razão r 5 com termo de ordem i 480 i15 485 5i Os denominadores formam uma sequência natural de inteiros iniciando por 10 logo da forma 9 i com o índice i variando de 1 até 30 Então a soma pode ser escrita assim 30 1 485 5 9 i i i Confira os valores de xi i i 9 5 485 na tabela seguinte i 1 2 3 4 30 i i 9 5 485 Exemplo 10 O somatório expressa a soma de cinco parcelas xi 10i 1 conforme tabela seguinte i 1 2 3 4 5 xi 10i1 1011 9 1021 19 1031 29 1041 39 1051 49 Logo temos 9 19 29 39 49 12 Propriedades do somatório e algumas somas especiais No desenvolvimento de somatórios algumas propriedades merecem destaque pela simplificação que emprestam aos cálculos 9 Matemática Discreta 121 Propriedades a n i k i n i k i i n i k i y x y x b n i k i n i k i x c x c c 1 c n i k c n k d 1 1 1 1 m n n m ij ij i j j i x x somatório duplo 122 Demonstrações a i n i k i y x xk yk xk1 yk1 xn yn xk xk1 xn yk yk1 yn n i k i n i k i y x b n i k c ix cxk cxk1 cxk2 cxn cxk xk1 xk2 xn c n i k ix c n i k c c c c c cnk1 d Consultar as referências bibliográficas 123 Somas Especiais As identidades seguintes são bastante úteis no cálculo de somas notadamente quando se deseja calcular quantas operações são executadas em programas de computador envolvendo laços for a n i i 1 2 1 n n Prova Bem desenvolvendo o somatório obtemos n i i 1 1 2 3 4 n Tratase da soma S dos termos de uma Progressão Aritmética cujo termo inicial a1 1 e termo final an n e razão r 1 Sabemos que a soma S 2 1 n a a n Lembrete 1 2 3 4 n 2 1 n n É a soma dos n primeiros números inteiros positivos 10 Matemática Discreta Assim 1 2 3 4 n 2 1 n n b n i i 1 1 2 n2 Prova n i i 1 1 2 1 3 5 7 2n 1 é a soma S dos n primeiros números inteiros ímpares positivos Tratase da soma S dos termos de uma Progressão Aritmética de termos inicial 1 e termo final 2n 1 logo podemos escrever S 2 2 2 2 2 1 2 1 n n n n c 1 2 1 n n i n i Prova n i i 1 2 2 4 6 8 2n é a soma S dos n primeiros números inteiros ímpares positivos Tratase da soma S dos termos de uma Progressão Aritmética de termos inicial 2 e termo final 2n logo podemos escrever S 1 2 2 2 n n n n d Veja demonstração nas referências Bom como você poderá utilizar as somas especiais Veja alguns exemplos Exemplo 1 Se você quer saber a soma S 1 2 3 4 100 poderá fazer uso da identidade n i i 1 2 1 n n De fato 1 2 3 4 100 Exemplo 2 Qual é o valor da soma 21 22 23 79 Observe que 21 22 23 79 1 2 3 79 1 2 3 20 Lembrete 1 3 5 7 2n1 n2 É a soma dos n primeiros números ímpares Lembrete A soma dos n primeiros inteiros pares positivos é 2 4 6 8 2n nn1 Lembrete 12 22 32 42 n2 É a soma dos quadrados dos n primeiros números inteiros positivos 11 Matemática Discreta Exemplo 3 Qual o valor da soma S dos números ímpares entre 1 e 79 Observe que S 1 3 5 79 Como os números são ímpares eles são da forma xi 2i 1 para valores inteiros de i de modo que para i 40 temos x40 240 1 79 Assim usando a identidade n i i 1 1 2 n2 a soma S pode ser escrita da forma seguinte S 1 3 5 79 402 1600 Exemplo 4 Como calcular a soma S de todos os números pares entre 98 e 234 Você pode calcular essa soma fazendo uso da identidade 1 2 1 n n i n i Observe que 98 100 102 104 234 2 4 6 234 2 4 6 96 117118 4849 13806 2352 11454 Exemplo 5 Como proceder para calcular a soma dos quadrados dos 30 primeiros números inteiros positivos Você quer calcular a soma S 12 22 32 42 302 e deverá fazer uso da identidade De modo que S 12 22 32 42 302 Como demonstração de que você entendeu o emprego da identidade calcule a soma 172 182 192 452 12 Matemática Discreta 13 Dígito Verificador Você já percebeu que alguns números de fundamental importância para nós como o CPF Conta Bancária número de agência bancária códigos de barras constituem uma sequência de algarismos que ao final tem a adição de um ou mais dígitos Esse dígito adicional é denominado Dígito Verificador DV e é importante para se evitar erros na digitação de tais sequências numéricas Como é calculado o dígito verificador Você vai conhecer alguns exemplos de cálculos desses dígitos verificadores A maioria dos casos consiste em multiplicar cada um dos algarismos da sequência por um peso em geral inteiros em ordem crescente ou decrescente e tomar a soma S desses produtos Em seguida dividir essa soma por um inteiro p em geral 10 ou 11 e calcular o resto da divisão da soma S por p Os restos da divisão de S por p são 0 1 2 p 1 Esses restos serão indicados pela expressão S mod p Em seguida tomar como dígito verificador o próprio resto se menor do que 10 Se não alternativas podem ser usadas Conheça agora alguns exemplos da concepção e cálculos de dígitos verificadores Exemplo 1 Considere o número de matrícula de uma escola constituído por sete algarismos N1N2N3N4N5N6 D onde D é o dígito verificador calculado da seguinte maneira Vamos multiplicar os algarismos da matrícula da esquerda para direita pelos pesos 7 6 5 4 3 e 2 Em seguida calculemos a soma S 7N1 6N2 5N3 4N4 3N5 2N6 Observe que S 13 Matemática Discreta Definimos D 11 Smod 11 onde Smod 11 resto da divisão de S por 11 Se o valor encontrado para D for 10 ou 11 ponha D 0 Vamos calcular o dígito D da seguinte matrícula 240134D Inicialmente calculemos a soma S Observe que a matrícula 240134 D tem os dígitos N1 2 N2 4 N3 0 N4 1 N5 3 e N6 4 de modo que podemos escrever S 7N1 6N2 5N3 4N4 3N5 2N6 7 2 6 4 5 0 4 1 3 3 2 4 14 24 0 4 9 8 59 O valor de Smod 11 59mod 11 4 Isto é 59mod11 4 pois o resto da divisão de 59 por 11 é 4 O digito verificador é calculado assim D 11 Smod 11 11 4 7 A matricula é 2401347 Agora verifique se entendeu como o digito verificador dessa matrícula foi calculado efetuando os cálculos do dígito D da matrícula 451236 D Você deve encontrar o valor D 7 E então acertou Exemplo 2 Uma rotina muito utilizada por programadores em softwares comerciais é a validação do Cadastro de Pessoas Físicas CPF que serve para identificar cada indivíduo no país O número do CPF é constituído de 11 dígitos D1D2D3 D7D8D9 D10D11 sendo os dois últimos os dígitos de verificação calculados da seguinte maneira Dígito D10 D10 11 onde S1 Caso D10 resulte em 11 ou 10 ponha D10 0 Dígito D11 D11 11 S2 mod 11 onde S2 14 Matemática Discreta Caso D11 resulte em 10 ou 11 ponha D11 0 Vamos calcular os valores dos dígitos D10 e D11 do CPF 234939448 D10D11 Inicialmente o CPF apresenta os seguintes dígitos D1 2 D2 3 D3 4 D4 9 D5 3 D6 9 D7 4 D8 4 e D9 8 No cálculo do digito D10 é necessário calcular inicialmente a soma S1 S1 10D1 9D2 8D3 7D4 6D5 5D6 4D7 3D8 2D9 102 93 84 79 63 59 44 34 28 20 27 32 63 18 45 16 12 16 249 S1mod11 249mod 11 7 O digito D10 11 7 4 A rotina do dígito D11 requer a soma S2 S2 11D1 10D2 9D3 8D4 7D5 6D6 5D7 4D8 3D9 2D10 112 103 94 89 73 69 54 44 38 24 22 30 36 72 21 54 20 16 24 8 303 S2mod 11 303mod11 6 De modo que o dígito D11 11 6 5 E o CPF é 234939448 45 Você observou que os pesos que multiplicam os nove primeiros algarismos do CPF são 10 9 8 2 no cálculo do primeiro digito verificador D10 e que os pesos usados no cálculo do segundo digito verificador D11 são 11 10 9 2 E agora como teste experimente calcular os dois dígitos verificadores do seu próprio CPF 15 Matemática Discreta Exemplo 3 O Código de Barras EAN 13 desenvolvido nos Estados Unidos por volta de 1970 é um dos mais usados no mundo na identificação dos produtos Por ser lido por leitura ótica os códigos de barras agilizam processos de armazenagem transporte de produtos controle do estoque e de vendas As barras armazenam informações sobre o produto no computador O código EAN consiste em uma sequência de 13 dígitos N1N2N3N4 N13 distribuídos em três campos de modo que os três primeiros dígitos identificam o país onde o produto foi fabricado 789 no caso do Brasil o segundo campo identifica o fabricante os próximos dígitos determinam o produto O último dígito N13 é o dígito de controle Para o cálculo do dígito verificador do EAN 13 inicialmente devemos multiplicar os algarismos de ordem ímpar da sequência N1N2N3N4 N12 pelo peso 1 e os algarismos de ordem par pelo peso 3 em seguida somar os produtos A soma S correspondente será S 1N1 3N2 1N3 3N4 1N11 3N12 que escrita sob a forma se somatório tomará a expressão S 3 1 6 1 2 6 1 2 1 i i i i N N O digito N13 é definido por N13 10 Smod 10 Caso N13 resulte em 10 ponha N13 0 Vamos verificar se o digito verificador do EAN da figura acima está calculado corretamente A figura acima mostra o EAN 789 12345 6789 5 o valor da soma S será 16 Matemática Discreta S 17 38 19 31 12 33 14 35 16 37 18 39 7 24 9 3 2 9 4 15 6 21 8 27 135 Como Smod 10 135mod 10 5 temos que o digito N13 10 5 5 Está correto o digito verificador do EAN Agora você tem a tarefa de calcular o digito verificador do EAN 789 61894 2011 N13 de uma garrafa de vinho produzido no Rio Grande do Sul E então achou N13 0 Aprenda Praticando Exercícios Propostos 11 Demonstre que você entendeu bem os assuntos desse capítulo resolvendo os exercícios propostos As respostas dos exercícios de número par são apresentadas logo a seguir Se tiver dúvidas procure sanálas com professores executores e tutores da disciplina em fóruns de discussão que serão formados 1 Escreva as expressões abaixo usando a notação de somatório a 1 3 5 7 9 35 b 3 5 7 9 57 c 2 4 6 220 d 53 73 93 1233 e 1 2 2 3 3 4 4 5 30 31 f g 11 21 31 41 121 h 1 4 9 16 25 36 i j k 2 1 3 2 2 5 2 3 7 2 15 31 l 2 2 2 2 2 2 2 m 3 3 3 4 3 5 3 17 17 Matemática Discreta 2 Desenvolver os seguintes somatórios a b 5 0 2 i i c 1 7 5 1 i i d 2 4 0 2 1 i i e 5 0 6 i i a f 6 1 j j x g 6 4 3 1 2 1 2 1 i i i i h 5 1 1 2 i Di i i j 5 1 i Ni i k 6 i 1 ia l n i ib 1 1 m 3 1 4 2 i j j i n 2 3 3 1 4 2 i j j i o 5 1 5 1 i j ibj a p q r 4 1 4 1 i j ia j 18 Matemática Discreta 3 Escrever sob a forma de somatório as seguintes expressões 4 Escrevam na forma de somatório os seguintes dados a A soma S dos 50 primeiros termos da série 4 991 3 994 2 997 1 1000 b A soma S dos 15 primeiros termos de S 1 16384 144 8 169 4 196 2 225 1 5 As contas do Banco Baú da Sorte apresentam numeração com seis dígitos N1N2N3N4N5N6 seguidos de um dígito D de controle calculado por Se o valor encontrado para D for 10 ou 11 ponha D 0 Calcule o dígito verificador D para as contas de números 134792D 245318D e 875346D 6 Suponha que o CNPJ de uma empresa seja N1 N2 N3 N4 N5 N6 N7 N8 N9 N10 N11 N12 C1 C2 Rotina para se obter os dígitos verificadores C1 e C2 Cálculo de C1 1º Multiplicamos da direita para esquerda os algarismos do CNPJ de N12 até N1 pelos pesos 2 3 e assim sucessivamente até 9 e em seguida recomeçamos multiplicando por 2 3 etc até encontrar o algarismo mais à esquerda N1 2º Calculamos a soma S1 dos resultados dessas multiplicações 3º Calculamos o resto R da divisão de S1 por 11 4º O dígito verificador será C1 11 R Se C1 10 ou 11 ponha C1 0 19 Matemática Discreta Cálculo de C2 1º Incorpore ao CNPJ o dígito C1 calculado fazendoo ocupar a posição N13 Multiplique da direita para esquerda os algarismos da forma utilizada para o calculo de C1 2º Proceda com a mesma rotina para calcular C1 a Forneça uma expressão matemática para a rotina acima descrita b Calcular os dígitos do CNPJ 055597480001C1C2 7 Livros são identificados pelo ISBN International Standard Book Number com 9 dígitos N1 N2 N3 N9 que identificam a sua publicação Esses nove dígitos são distribuídos em blocos que identificam a língua a editora o número designado pela companhia editora e são seguidos de um dígito verificador D que pode ser um número inteiro de 0 a 9 ou a letra X usada para representar o número 10 O cálculo de D é feito da seguinte maneira a Calcule o dígito verificador D do ISBN 853630361D encontrado no livro de Matemática Discreta do autor Seymour Lipschutz editado pela Bookman b Repetir o exercício para o ISBN encontrado no livro de Programação utilizado por você c Certo livro tem ISBN 8522102Q1 0 Calcule o valor de Q 8 Calcule os dígitos verificadores do CPF 033939844D10D11 usando os métodos descritos no Exemplo 2 9 Pesquisar na Internet wwwgooglecombr o seguinte Dígito Verificador Você encontrará diversas formas do uso de dígito verificador notadamente em inscrições de firmas comerciais na Secretaria da Fazenda dos estados brasileiros Conheça alguns exemplos e expresse a fórmula do cálculo da inscrição por meio de somatório 10 Calcule i i i y x 6 1 sabendo que xi 7 i e yi 1 i2 20 Matemática Discreta 11 Dado que x1 1 x2 3 x3 5 x4 7 x5 9 e f1 1 f2 5 f3 3 f4 3 f5 5 calcule a 5 i 1 ix b 5 i 1 if c 5 1 i i fi x d 5 1 2 i i i f x e Mostre que 0 5 1 x x i i onde é a média aritmética dos xi 12 Sabendo que 2 1 1 n n i n i k n k n i 1 e que n i 1 i 1 x k n i k ix calcule a 100 i 1 i b c d e 51 52 53 183 f 31 32 33 101 g 1055 1056 1057 1099 13 Sabendo que 2 1 1 2 n i n i calcule N7 a 100 1 1 2 i i b 100 41 1 2 i i c 1 3 5 7 31 d 21 23 25 251 e 21 23 25 27 87 f 441 443 445 487 21 Matemática Discreta Respostas dos Exercícios Propostos 11 2 a 1 3 5 7 9 b 1 2 4 8 16 32 c 6 13 20 27 34 d 12 32 52 72 e a6 a5 a4 a3 a2 a1 f x1 x2 x6 g h 1D1 3D2 5D3 7D4 9D5 i 9X1 8X2 7X3 1X9 j 1N1 2N2 3N3 4N4 5N5 k a1 a2 a6 l bn b b b 1 1 1 1 3 2 1 m 3 1 4 2 i j j i 1 2 1 3 1 4 2 2 2 3 2 4 3 2 3 3 3 4 12 15 18 45 4 a 6 a C1 11 Se C1 10 ou 11 ponha C1 0 C2 11 Se C2 10 ou 11 ponha C2 0 b 05559748000177 8 03393984420 22 Matemática Discreta 10 i i i y x 6 1 6 1 2 1 7 i i i 62 55 410 317 226 137 12 a 5050 b 3825 c 9800 d 1220 Conclusão No primeiro capítulo deste fascículo você aprendeu o uso do somatório e como as suas propriedades facilitam o cálculo de somas Além disso conheceu o emprego de somatório na definição do dígito de verificação em numerações especiais como CPF código de barras ISBN CNPJ entre outros Saiba Mais Você poderá aprender mais sobre somatório consultando os seguintes livros e sites GERSTING Judith L Fundamentos Matemáticos para a Ciência da Computação Tradução Valéria de Magalhães Iorio Rio de Janeiro LTC 2004 LIPSCHUTZ Seimour LIPSON Marc Lars Teoria e Problemas de Matemática Discreta Porto Alegre Bookman 2004 httpproblemasteoremaswordpresscom20071120somatorioduplo httpwwweancombr 23 Matemática Discreta Orientações de Estudos A demonstração da propriedade 121 letra d pode ser feita por você Tente fazêla e discuta o resultado com seus colegas nos fóruns de discussão que serão formados com esse objetivo A propriedade 1 1 1 1 m n n m ij ij i j j i x x é uma identidade que mostra como podemos somar os elementos de uma tabela constituída por m linha e n colunas como a soma dos elementos xij situados nas linhas da tabela ou como soma dos elementos situados nas colunas Mostre a igualdade 1 1 1 1 m n n m ij ij i j j i x x se verifica provando que a soma S dos elementos da tabela pode ser feita de duas maneiras somandose as linhas i ou somandose as colunas j de modo que S l m l l l S S S S 3 2 1 e S c S1 c Sn S S c 3 c 2 o que justifica a troca da ordem no somatório duplo TEM RAZÃO MARIA NÃO POSSO SER UMA MULHER COMO NOSSAS MÃES QUE SE CONFORMARAM EM APRENDER CORTE E COSTURA NOSSA GERAÇÃO É DIFERENTE É A GERAÇÃO DA TECNOLOGIA DA ERA ESPACIAL DA ELETRÔNICA ETC QUANDO EU CRESCER VOU COMPRAR UMA MÁQUINA DE TRICÔ A CIBERNÉTICA ME ATRAI ADORO A CIBERNÉTICA PORTANTO NÃO VOU CAIR NA MEDIOCRIDADE DO CORTE E COSTURA NUNCA A CIÊNCIA ME CHAMA 25 Matemática Discreta Capítulo 2 Matrizes armazenando dados Neste capítulo serão feitas revisões sobre matrizes de entradas reais os diversos tipos de matrizes e as operações de soma multiplicação de matriz por um número real e multiplicação de matrizes apropriadas Trataremos também de matrizes booleanas e as operações definidas nesse tipo de matriz Na literatura de informática as matrizes são conhecidas por diversos nomes entre os quais arranjos arrays etc Nesse caso as matrizes são estruturas que armazenam dados 21 Matriz Uma matriz m x n é uma tabela de mn números dispostos em m linhas e n colunas e será denotada assim A aijm x n O tamanho da matriz é a dimensão m x n da tabela seguinte A A iésima linha de é 26 Matemática Discreta A jésima coluna de A é Exemplo 1 A matriz A seguinte é do tipo 4 x 3 sua 3ª linha é e sua 3ª coluna é 8 2 0 3 A 9 1 8 2 2 2 7 1 0 2 3 1 Existem duas maneiras de denotar um elemento individual de uma matriz aij ou representam o elemento da matriz A situado na posição ij ou seja que está na linha i na coluna j Exemplo 2 Podemos usar matrizes como modelo para representar dados As observações sobre as temperaturas médias em três cidades diferentes ao longo de uma semana podem ser representadas por uma matriz T do tamanho 3x7 cujo elemento genérico tij é a temperatura média em graus Celsius da cidade i no dia j A matriz T é a tabela seguinte 1 Dom 2 Seg 3 Ter 4 Qua 5 Qui 6 Sex 7 Sab Cidade 1 23 23 24 25 21 24 25 Cidade 2 17 16 18 19 15 16 17 Cidade 3 29 27 28 29 31 30 30 Na matriz T podemos verificar que a temperatura média na cidade 2 no dia 5 é t25 15C e que a temperatura mínima na cidade 3 ocorreu no dia 2 com valor t32 27C 27 Matemática Discreta 22 Definição Duas matrizes A aijm x n e B bijr x s são iguais se e somente se elas têm o mesmo tamanho ou seja m r e n s e se os elementos que ocupam posições iguais são iguais Exemplo 3 O valor de x nas matrizes 4 8 1 e B x x 8 x 2 3 2 A tal que A B é x 2 23 Tipos especiais de matrizes Ao trabalharmos com matrizes observamos que existem algumas que seja pela quantidade de linhas ou colunas ou pela natureza de seus elementos têm propriedades que as diferenciam das demais Além disso estes tipos de matrizes surgem com frequência na prática e assim recebem nomes especiais Recordaremos alguns tipos Matriz Quadrada é uma matriz n x n isto é tem o número de linhas igual ao número de colunas Como exemplo temos as matrizes A e B do Exemplo 2 Numa matriz quadrada por exemplo A3x3 os elementos aij tais que i j são a11 a22 e a33 e constituem a diagonal principal de A Caso a matriz seja A 5 1 7 0 2 6 4 5 8 a diagonal principal é constituída pelos elementos 8 2 e 7 Matriz Nula é aquela em que aij 0 para todo i e j Por exemplo A 0 0 0 0 0 0 0 0 e B 0 0 0 0 Matriz Coluna matriz unidimensional é aquela matriz A ai ji x 1 i 1 2 3 m que possui uma única coluna 28 Matemática Discreta Exemplo 8 2 0 3 Matriz Linha matriz unidimensional é a matriz A ai jixj j 1 2 3 n que possui apenas uma linha Exemplo Array Frequentemente em programação dados são armazenados em vetores arrays isto é listas em que os elementos são indexados por um ou mais índices Um array unidimensional é uma matriz linha ou matriz coluna e sua dimensão é o número de índices Por exemplo as notas em Matemática Discreta de dez alunos do Curso de Sistemas de Informação podem ser listados no seguinte array 81 50 87 60 95 60 20 78 100 57 Podemos denotar todas as notas da lista pelo símbolo n e índices diferentes que indicam a posição de cada nota no array n1 n2 n3 n10 De modo que n3 87 e n7 20 Matriz Diagonal é uma matriz quadrada onde aij 0 para i j isto é os elementos que não estão na diagonal principal são nulos Exemplo 0 1 0 3 0 0 0 0 2 Matriz Identidade Quadrada é a matriz quadrada em que aij 1 se i j e aij 0 para i j Exemplos I3 0 1 0 1 0 0 0 0 1 e I2 0 1 0 1 Matriz Simétrica é aquela matriz quadrada onde aij aji Observe que numa matriz simétrica a parte superior é uma reflexão da parte inferior em relação à diagonal 29 Matemática Discreta Exemplos 3 8 5 6 8 2 2 3 1 e 8 3 1 8 Os elementos simétricos em relação à diagonal principal são iguais Matriz Transposta Dada uma matriz A aijm x n podemos obter uma matriz AT bijn x m denominada transposta de A cujas linhas são as colunas de A isto é bij aji Exemplo A 1 8 2 3 5 2 AT 5 2 3 8 1 2 Observe que é uma matriz quadrada A é simétrica se e só se A AT Exemplo 4 Considere a matriz A do tipo 4 x 4 a A soma dos elementos situados na 3ª linha de A é S a31 a32 a33 a34 20 18 17 16 71 b O somatório S 4 1 2 i ia representa a soma dos elementos da matriz A situados na 2ª coluna c Se queremos escrever a soma dos elementos da matriz A situados na diagonal escrevemos S 4 1 i ia i de modo que S a11 a22 a33 a44 10 13 17 24 64 d O duplo somatório SL 4 1 4 1 i j ia j representa a soma de todos os elementos da matriz A Para cada valor do índice i no primeiro somatório o somatório interno calcula a soma dos elementos da linha i fazendo o índice j variar de 1 a 4 Desse modo obtemos 30 Matemática Discreta SL 4 1 4 1 i j j ia 4 1 4 3 2 1 i i i i i a a a a a11 a12 a13 a14 a21 a22 a23 a24 a31 a32 a33 a34 a41 a42 a43 a44 10 12 15 20 12 13 14 15 20 18 17 16 21 22 23 24 57 54 71 90 272 Observe que somamos os elementos de A tomando a soma de cada linha Agora se você quer obter a soma dos elementos de S tomando a soma dos elementos das colunas experimente fazer SC 4 1 4 1 ji i ia j obtido do somatório anterior trocando a ordem dos índices i e j É claro que a soma SC resulta em 272 24 Operações com matrizes Podemos definir operações numéricas entre matrizes cujos elementos entradas são numéricos Essas operações tornam não só as matrizes muito interessantes como objeto de estudo como úteis na solução de diversos problemas 241 Adição de matrizes A adição de matrizes é definida para matrizes de mesmo tamanho Isto é se A e B são duas matrizes de mesmo tamanho m x n a soma dessas duas matrizes denotada por A B é também uma matriz Cm x n cujo elemento na posição ij é definido como sendo a soma dos elementos de A e B que ocupam a posição ij Ou seja se A aijm x n e B bijm x n então C A B é a matriz cijm x n definida por cij aij bij Exemplo 5 Se 5 73 B 8 5 2 3 23 2 3 2 A então C 31 Matemática Discreta Bem você provavelmente está se perguntando de que modo podese empregar a soma de matrizes em situações reais O exemplo seguinte responde ao questionamento Exemplo 6 Um fabricante de um produto produz três modelos A B e C Cada um deles é produzido parcialmente na fábrica F1 em Campinas e então finalizado na fábrica F2 em São Paulo O custo de cada produto é composto pelo custo de produção e pelo custo de transporte As matrizes F1 e F2 seguintes descrevem o custo dos três produtos em cada fábrica F1 F2 A matriz F1 F2 FT fornece o total dos custos de produção e transporte para cada produto Assim F1 F2 242 Multiplicação de uma matriz por um escalar Na seção anterior você conheceu como as matrizes podem ser somadas Bem agora vamos mostrar quando é possível multiplicar uma matriz de qualquer tamanho por um número real Se A é uma matriz m x n e k é um escalar o produto da matriz A pelo escalar k denotado por kA é também uma matriz m x n cujo elemento na posição ij é definido como sendo o produto do elemento de A que ocupa a posição ij pelo escalar k Isto é se A aijm x n então C kA é a matriz cijm x n definida por cij k aij 32 Matemática Discreta Exemplo 7 Uma empresa de material fotográfico tem loja numa cidade Um marca específica de câmera está disponível para venda nos modelos automático semiautomático e nãoautomático Cada uma dessas câmeras tem uma unidade de flash correspondente que é vendida juntamente com a câmera Os preços de venda das câmeras e das unidades de flash são fornecidos pela matriz V do tipo 2x3 V Bem se a empresa planeja reduzir os preços de venda de seus produtos oferecendo desconto de 10 para pagamentos à vista então a tabela de preços sofrerá alteração de modo que cada produto terá seu preço multiplicado por 09 A matriz dos novos preços será obtida multiplicando a matriz V por 09 09 V 243 Multiplicação de matrizes A multiplicação de matrizes está definida quando o número de colunas da primeira matriz é igual ao número de linhas da segunda matriz Assim se A é uma matriz m x p e B é uma matriz p x n o produto AB é possível Além disso a matriz C AB é do tipo m x n Para encontrarmos o elemento ij da matriz produto AB multiplicamos cada um dos elementos da linha i da matriz A pelo correspondente elemento da coluna j da matriz B e somamos os produtos obtidos Como as linhas da matriz A tem o mesmo número de elementos que as colunas de B não sobram nem faltam elementos A B C 33 Matemática Discreta cij ai1b1j ai2b2j ai3b3j aipbpj cij p k k j k i b a 1 i 1 2 3 j 1 2 3 Exemplo 8 Considere as matrizes A e B O produto AB é possível pois A é do tipo 2x3 e B do tipo 3x2 a matriz C AB é 2x2 onde C c11 c12 c21 c22 Exemplo 9 Caso as matrizes A e B do Exemplo 6 sejam A 3 0 4 2 3 1 e B 3 2 0 2 3 1 o produto AB será uma matriz de tamanho 2x2 obtida multiplicando os elementos de cada linha de A Li pelos respectivos elementos de cada coluna de B Cj Assim AB 0 4 3 2 3 1 2 2 3 3 0 1 2 2 1 2 2 1 1 1 L L L C C L C C 31 00 43 33 02 42 12 32 13 23 30 21 Exemplo 10 Considere a matriz F1 do Exemplo 6 que fornece o custo dos produtos A B e C produzidos na fábrica F1 Se a matriz 34 Matemática Discreta Q3x1 representa a quantidade produzida de cada produto A B e C por mês o que representa a matriz produto QF1 Bom multiplicando Q por F1 obtemos QF1 15020 20080 15070 10040 20050 10032 23000 23700 A matriz QF1 apresenta o custo de produção e de transporte de toda a produção mensal dos três produtos Que informações sobre o custo dos produtos A B e C a matriz F1TQT fornece Recorde o conceito de matriz transposta 25 Matrizes Booleanas Na grande maioria dos casos nós utilizamos matrizes cujos elementos são números reais Desse modo os cálculos nas operações de adição multiplicação por escalar e multiplicação de matrizes são feitos com os elementos escritos na base decimal Mas na tecnologia da informação o uso de dados na notação binária é necessário Os dados codificados em binário são muito importantes e tem aplicações variadas no computador notadamente em videogames comunicação por fax transferências de dinheiro por meio de caixas eletrônicos etc Seja A aij uma matriz cujos elementos são os bits 0 e 1 entendendo que esses dígitos como valores lógicos 0 representando FALSO e 1 representando VERDADEIRO Essas matrizes são chamadas matrizes booleanas homenagem ao matemático inglês do século XIX George Boole 35 Matemática Discreta Exemplo 11 Suponha que numa sala de aula com 30 alunos queremos registrar a presença 1 e a ausência 0 nos 22 dias de aulas do mês A matriz booleana que apresenta o registro da presença às aulas é uma matriz A30x22 da seguinte forma A 1 1 1 1 1 1 11 0 1 1 1 1 1 00 0 1 1 1 0 1 1 1 O elemento aij 1 significa que o aluno i esteve presente à aula do dia j O elemento aij 0 quando o aluno i faltou à aula do dia j Exemplo 12 Considere que uma rede de comunicações tem cinco estações com transmissores de potências diferentes Na matriz A abaixo estabelecemos que aij 1 significa que a estação i pode transmitir diretamente à estação j aij 0 significa que a transmissão da estação i não alcança a estação j Veja o diagrama abaixo A 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 1 1 1 0 O elemento a13 1 significa que a estação 1 transmite diretamente à estação 3 e a31 0 significa que a estação 3 não transmite diretamente à estação 1 Qual o significado da diagonal nula de A A matriz A é simétrica A diagonal nula de A significa que uma estação não transmite para si mesma Além disso observe que A AT logo a matriz A não é simétrica Isso significa a não comutatividade da comunicação entre duas estações 36 Matemática Discreta 251 Adição e multiplicação de matrizes booleanas Podemos definir a adição v e produto booleano de duas matrizes de mesmo tamanho da maneira usual exceto pelo fato de que agora usamos as operações booleanas de adição e multiplicação conforme tabelas a seguir v 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 Tabela da Adição Tabela da Multiplicação As tabelas acima definem a adição booleana v e o produto booleano de acordo com a seguinte notação x v y Max x y e x y Min xy Se A aijn x m e B bijn x m são matrizes booleanas então A v B aij v bijn x m e A B aij bijn x m Exemplo 13 a A soma booleana das matrizes A 0 1 0 1 0 1 B 1 0 e é dada por 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 B 1 0 A b O produto booleano das matrizes A 1 0 0 1 B 1 1 1 1 é dado por A B 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 Agora é com você Considere as matrizes booleanas A 1 1 1 0 1 0 0 1 1 B 1 0 0 1 1 0 1 0 1 C 0 1 0 1 1 1 0 1 1 Efetue as seguintes operações booleanas a A B b A v B c B v C d A v A e B B f A B v C g A v C B 37 Matemática Discreta 252 Multiplicação de matrizes booleanas A multiplicação de matrizes booleanas Aijm x p e Bijp x n denotada por A B é definido como a matriz C do tipo m x n tal que cij ai1 b1j v ai2 b2j v ai3 b3j v v aip bpj Perceba que esse produto é obtido multiplicando cada linha de A pelo produto booleano e somando esses produtos pela soma booleana Exemplo 14 Calcule o seguinte A B nos seguintes casos a A 0 1 1 1 0 1 B 0 0 1 1 1 0 b A 1 1 1 0 1 0 0 1 1 B 1 0 0 1 1 0 1 0 1 a A B 0 1 1 1 0 1 0 0 1 1 1 0 Agora faça o exercício b Você deverá chegar à matriz booleana A Exemplo 15 Os aeroportos 1 2 e 3 estão interligados por voos diretos eou com escala A matriz M aij3x3 é tal que aij 1 se há voo direto do aeroporto i para o aeroporto j e aij 0 se não há voo direto do aeroporto i para o aeroporto j é M 0 0 1 0 1 1 1 0 0 Os voos de um aeroporto para outro são representados no diagrama seguinte 38 Matemática Discreta Observe que não há voos diretos do aeroporto 1 para o aeroporto 3 nem do 3 para 2 Mas há esses voos com escala Isto é partido de 1 podemos alcançar 3 passado por 2 Além disso partindo de 3 podemos atingir 2 passando por 1 A matriz M2 bij onde M2 M M tal que bij 1 significa que há voo do aeroporto i para o aeroporto j com escala caso contrário bij 0 De fato M M 0 0 1 0 1 1 1 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0 0 1 1 O diagrama ao lado indica os voos com escala Aprenda Praticando Exercícios Propostos 21 Verifique se você entendeu bem os assuntos desse capítulo resolvendo os exercícios propostos As respostas dos exercícios de número par são apresentadas logo a seguir Se tiver dúvidas procure sanálas com professores e tutores da disciplina em fóruns de discussão que serão montados para esse fim 1 Considere a matriz B 0 3 1 3 2 1 4 1 3 0 1 2 2 2 1 1 Calcule a 4 1 2 j j b b 4 1 j bi3 Voos Diretos Voos com Escala 39 Matemática Discreta c 4 1 i 4 1 i bij d 2 Calcule o produto AB nos seguintes casos a A 1 1 0 e B 2 1 2 b A 3 1 2 1 e B 1 1 2 2 c A 2 1 1 3 0 2 e B 2 2 1 1 2 1 3 Se A 3 1 5 2 e B 1 3 4 2 calcule a A2 AA b A3 c B2 d B3 e Mostre que AB BA f A BT g AB AT h ATBT B 4 Considere as matrizes A 1 2 1 3 0 2 B 2 2 1 1 2 1 Calcule quando possível os seguintes produtos a ATBT b BA c BTAT 40 Matemática Discreta 5 Suponha que A B e C são matrizes de números respectivamente de ordens 3 x 7 7 x 2 e 2 x 5 Qual o modo mais eficiente de calcular o produto ABC é ABC ou ABC Justifique sua resposta computando o número de multiplicações que se efetua em cada caso 6 Considere as matrizes indexadas 2 x 2 Bi definidas por Bi 2 1 i i 1 i i com i N a Escreva as matrizes B1 B2 B5 b Calcule o valor da soma S 5 i 1 iB c Determine o valor da soma S t i iB 5 1 d Calcule a soma S 3 1 T i i Bi B 7 Considere a matriz A aij do tipo 30 x 30 a Escreva os elementos de A b Expresse sob a forma de somatório a soma dos elementos situados na 12ª linha de A c Expresse sob a forma de somatório a média aritmética dos elementos situados na 25ª coluna de A d Expresse sob a forma de somatório a soma dos elementos de A situados na 13ª coluna e O que significa o valor encontrado para o seguinte somatório MP 8 Seja A 1 0 2 2 x 2 x Qual o valor de x tal que AT A 9 Os aeroportos 1 2 3 e 4 estão interligados por voos diretos e ou com escala A matriz M aij4x4 é tal que aij 1 se há voo direto do aeroporto i para o aeroporto j e aij 0 se não há voo direto do aeroporto i para o aeroporto j é 41 Matemática Discreta M 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 a Faça um diagrama representando os voos diretos b Calcule a matriz M2 bij onde M2 M M tal que bij 1 significa que há voo do aeroporto i para o aeroporto j com escala e faça um diagrama representativo da situação 10 Uma fabricante produz janelas e portas e cada um desses produtos passa por um processo de montagem e por um processo de acabamento O tempo gasto em cada um desses processos é fornecido em horas pela matriz A 2 2 Porta 4 Janela 3 Acabamento Montagem O fabricante tem uma fábrica em Caruaru e outra em Campina Grande e o custo de cada um desses processos por hora trabalhada é fornecido pela matriz B Calcule a matriz AB e diga o significado dos elementos do produto AB 11 Suponha seis pessoas Adriano A Bernardo B Carla C Daniele D Eunice E e Fábio F que adoram uma fofoca via telefone Cada dia Adriano conversa com Bernardo e Fábio Bernardo conversa com Adriano Carla e Daniela Carla com Bernardo Daniele e Eunice Daniele com Bernardo Carla Eunice e Fábio Eunice conversa com Carla Daniele e Fábio e Fábio conversa com Adriano Daniele e Eunice Tudo que uma pessoa conversa com outra num dia ela repassa a fofoca para as outras no dia seguinte a Modele este esquema de fofocas por telefone utilizando uma matriz booleana M mij6x6 onde mij 1 significa que a pessoa i conversa com a pessoa j Caso contrário mij 0 42 Matemática Discreta b M é simétrica c Quantos dias no mínimo uma fofoca recebida por Adriano na segundafeira leva para chegar aos ouvidos de Daniele 12 Na matriz booleana A3x3 abaixo a letra L significa ligado 1 e a letra D significa desligado 0 A D L L D L D L D L a Encontre uma matriz B3x3 do tipo ligadodesligado tal que A v B seja uma matriz em que todos os elementos sejam ligado b Encontre uma matriz B3x3 do tipo ligadodesligado tal que A B seja uma matriz em que todo elemento seja desligado Respostas dos Exercícios Propostos 21 2 a b 5 5 0 0 c 2 1 5 1 4 a 1 1 2 8 1 2 1 2 5 b 2 2 2 1 1 1 5 8 1 c 6 a B1 3 B2 2 0 1 B2 3 4 1 2 B3 4 5 3 2 B4 e B 6 7 5 4 b S 5 i 1 iB c S t i iB 5 1 d S 3 1 T i i Bi B 1 3 2 3 0 2 0 1 2 4 3 4 1 3 2 1 4 5 3 2 3 5 4 2 5 6 4 3 4 6 5 3 6 7 5 4 5 7 4 6 43 Matemática Discreta 8 x 1 10 AB A matriz AB indica o custo total de fabricação de janela e portas nas duas fábricas 12 a L D D L L L D L D b D D L D L L D D D Conclusão No segundo capítulo deste fascículo você aprendeu sobre matrizes as operações que nelas podemos efetuar e como as matrizes podem ser usadas como estrutura de armazenamento de dados Conheceu também as matrizes booleanas cujos elementos são varáveis booleanas tipo SimNão LigadoDesligado As operações entre matrizes booleanas foram apresentadas através de exemplos Saiba Mais Você poderá aprender mais sobre matrizes consultando os seguintes livros e sites GERSTING Judith L Fundamentos Matemáticos para a Ciência da Computação Tradução Valéria de Magalhães Iorio Rio de Janeiro LTC 2004 KOLMAN Bernard Introdução à Álgebra Linear com aplicações Tradução de Alessandra Bosquilha Rio de Janeiro LTC 2006 LIPSCHUTZ Seimour LIPSON Marc Lars Teoria e Problemas de Matemática Discreta Porto Alegre Bookman 2004 httpwwwmatufmgbrelaineGAALgaalt1pdf 44 Matemática Discreta httpwwwfunepeedubr91funepeprofessoresmateriais57MATRIZES ppt2561matrizes Orientações de Estudos Você sabe como funcionam os mecanismos de busca para encontrar informações e acessar a internet Eles utilizam matrizes para rastrear as localizações da informação cada tipo de informação em uma localização determinam a palavrachave que aparece na informação e os sites da Web que tem informações em comum O mecanismo utilizado no site do Google por exemplo em vez de rastrear diretamente uma determinada página real na Web ou de um único assunto de pesquisa ele usa uma estrutura matricial focalizando buscas de páginas que correspondam ao assunto pretendido A busca é feita utilizando uma matriz booleana Anxn chamada matriz de conectividade onde n é o número de páginas acessíveis na Web durante um determinado mês de modo que todos os elementos assumem inicialmente o valor zero Quando o site j está relacionado com o site i definese o elemento aij 1 caso contrário aij 0 Dado que o número de sites é bastante grande a maioria dos elementos da matriz A é igual a zero Em seguida são listados todos os sites que tem conexão com o site j Se você quer mais informações sobre o assunto acesse o site wwwgooglecomtechnologyindexhtml e participe dos fóruns de discussão para debater o assunto com seus colegas e professores da disciplina 45 Matemática Discreta Capítulo 3 Princípios de Contagem como contar A Combinatória é a parte da matemática que tem como objetivo o estudo de problemas de contagem do número de agrupamentos que podem ser obtidos com os elementos de um dado conjunto Fazer contagem é uma tarefa que temos em diversas situações Por exemplo quando queremos dimensionar quantos espaços um banco de dados consome quantos usuários a configuração de um computador suporta quantos cálculos certo algoritmo resolve quantas linhas tem a tabelaverdade de uma proposição composta por n proposições simples quantas senhas de acesso a um caixa eletrônico podem ser formadas com quatro algarismos entre outros casos Inicialmente o que é uma lista 31 Listas Uma lista é uma sequência ordenada de objetos Para escrevermos uma lista escrevemos os seus elementos entre parênteses Por exemplo 2 a 3 X é uma lista cujo primeiro elemento é 2 o segundo é a o terceiro é 3 e o quarto elemento é X Isso significa que a ordem em que os elementos figuram na lista é relevante a lista a c h é diferente da lista c a h Além disso uma lista pode conter elementos repetidos 1 a 2 2 O número de elementos de uma lista é dito comprimento da lista A lista 1 a 2 2 tem comprimento 4 Uma lista de comprimento 2 é chamada de par ordenado como por exemplo 1 2 Claro que é uma lista vazia de comprimento 0 46 Matemática Discreta Dizemos que duas listas são iguais se tem o mesmo comprimento e se os elementos nas posições correspondentes são iguais Exemplo 1 a Senha numérica com quatro algarismos é uma lista de comprimento 4 b CPF é uma lista de comprimento 11 c Matricula de aluno de uma faculdade 2008 2 169 034 é uma lista de comprimento 11 d O Código de Endereçamento Postal CEP é uma lista de comprimento 8 Veja exercício 15 Como se calcula o número de listas O cálculo é feito por meio de princípios de contagem Estudaremos dois deles 32 Princípio multiplicativo contagem de listas de comprimento dois Considere as listas de dois elementos em que o primeiro pode ser escolhido de n maneiras e para cada uma dessas escolhas há m escolhas do segundo elemento da lista Então o número de listas de comprimento dois é nm Exemplo 1 Com os números 1 2 3 4 e 5 podemos formar quantas dezenas Bom uma dezena é uma lista de comprimento dois constituída por dois algarismos escolhidos dentre 1 2 3 4 e 5 Assim queremos formar listas do tipo x y Temos 5 escolhas para o primeiro elemento x e para cada escolha do primeiro existem 5 escolhas para o segundo elemento Logo podemos formar 5 x 5 25 dezenas Exemplo 2 Suponha agora que queremos formar dezenas de dois algarismos diferentes com os algarismos 1 2 3 4 e 5 A escolha do primeiro elemento do par pode ser feita de 5 maneiras Escolhido o primeiro restam 4 escolhas para o segundo elemento da lista De modo que podemos formar 5 x 4 20 listas de comprimento 2 com elementos distintos 47 Matemática Discreta Exemplo 3 Uma sequência de dois bits é uma lista de comprimento dois formada por zero 0 e um 1 de comprimento dois Podemos formar 2 x 2 4 listas 00 01 10 e 11 E quando as listas têm comprimento maior do que dois Como é feito o cálculo delas 33 Listas de comprimento maior do que dois Suponhamos que temos n elementos e queremos formar listas de comprimento k O primeiro elemento da lista pode ser escolhido de n formas diferentes o segundo também de n maneiras diferentes e assim até o késimo elemento que pode ser escolhido de n maneiras Logo a quantidade de listas será k Fatores n n n n n nk Exemplo 4 Um número binário é uma lista de zero e um Um número binário com 8 dígitos é chamado byte a Quantos bytes podemse formar Como um byte é uma lista de comprimento 8 tal que cada posição pode ser ocupada por zero 0 ou um 1 podemos formar 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 28 256 bytes b Quantos bytes começam por 10 e terminam por 01 As duas primeiras posições e as duas últimas são ocupadas cada uma delas por um único determinado bit então podemos formar 1 x 1 x 2 x 2 x 2 x 2 x 1 x 1 16 bytes c Quantos bytes começam por 10 e não terminam por 01 Existe apenas uma maneira de preencher as duas primeiras posições e três maneiras de preencher as duas últimas 00 10 e 11 De modo que podemos formar 1 x 2 x 2 x 2 x 2 x 3 48 bytes Exemplo 5 Os aeroportos embora tendo nomes diferentes têm códigos de três letras Por exemplo o aeroporto que serve Recife é REC o aeroporto que serve São Paulo Guarulhos é GRU e o que serve Brasília é BSB Com as 26 letras do nosso alfabeto podemos formar 262626 263 códigos diferentes 48 Matemática Discreta Quando as listas têm repetição de elementos como se processa o seu cálculo 34 Listas de comprimento k sem repetição de elementos Agora dispondo de n elementos se queremos formar listas de k elementos k n sem repetições procedemos assim temos n escolhas para o 1º elemento da lista n1 escolhas para o 2º elemento da lista n 2 escolhas para o 3º e finalmente n k 1 escolhas para o kº elemento da lista De modo que podemos formar n x n 1 x n 2 x x n k 1 listas de comprimento k Exemplo 6 As placas de licença de carros em certo estado dos Estados Unidos consistem em sete elementos os três primeiros são letras maiúsculas AZ e os quatro últimos são algarismos 09 Podemos formar 263 x 104 placas distintas das quais 26 x 25 x 24 x 10 x 9 x 8 x 7 são placas em que nenhum elemento é repetido 35 Princípio Aditivo Se dois eventos A e B disjuntos não ocorrem simultaneamente tem n e m possibilidades respectivamente então o número total de possibilidades para o evento A ou B é m n Exemplo 7 Se A é o evento de escolher um número primo entre 10 e 20 inclusive e B escolher um número par entre 10 e 20 inclusive de quantas maneiras podemos escolher um número primo ou um número par entre 10 e 20 inclusive Bom A 11 13 17 19 e B 10 12 14 16 18 20 então A B A B 4 6 10 Os dois princípios podem ser usados simultaneamente num problema Sim veja o seguinte exemplo Lembrete O Princípio Aditivo pode ser usado apenas quando os eventos são disjuntos isto é quando não houver possibilidade em comum 49 Matemática Discreta Exemplo 8 Uma rede de computadores é constituída por quatro nodos ou nós 1 2 3 e 4 Existem dois caminhos entre 1 e 3 dois entre 2 e 4 três entre 1 e 2 e quatro entre 3 e 4 Uma mensagem pode ser enviada do nodo 1 para o nodo 4 por meio 32 24 6 8 14 caminhos distintos Observe que os caminhos do nó 1 até o nó 4 indo pelo nó 2 ou nó 3 são eventos distintos Exemplo 9 Qual o valor de A após o seguinte código em C ter sido executado int A 0 for int I 0 I 10 I A A 1 for int J 1 J 9 J A A 1 for int K 1 K 8 K A A 1 Exemplo 10 Qual o valor de A após o seguinte código em C ter sido executado int A 0 for int I 1 I 10 I for int J 1 J 9 J for int K 1 K 8 K A A 1 50 Matemática Discreta Aprenda Praticando Exercícios Propostos 31 Bem agora é a sua vez Verifique se você entendeu os assuntos desse capítulo resolvendo os exercícios propostos As respostas dos exercícios de número par serão apresentadas logo a seguir Se tiver dúvidas tente esclarecêlas com os professores executores e tutores nos dos fóruns de discussão da disciplina que serão formados 1 O número de telefone no país X é composto de dez algarismos onde o primeiro não pode ser nem zero nem um Quantos telefones são possíveis 2 Um número de inscrição no Seguro Social de um país X é composto de nove algarismos 09 a Quantos números de Seguro Social são possíveis b Quantos deles são números pares c Quantos têm todos os algarismos números pares d Quantos podem ser lidos igualmente para trás e para frente por exemplo 122070221 e Quantos não têm nenhum dos seus algarismos igual a 8 f Quantos têm exatamente um algarismo igual a 8 g Quantos têm ao menos um algarismo igual a 8 3 Um sistema de computador permite atribuir nomes aos arquivos utilizando qualquer combinação de letras maiúsculas AZ e de algarismos 09 mas o número de caracteres no nome deve ser no máximo oito e deve haver ao menos um caractere no nome do arquivo Por exemplo A423 WJ 4AA e CDEF4321 são nomes de arquivo válidos mas J31 e TURBINADA não são válidos Quantos nomes de arquivo diferentes podem ser formados nesse sistema 4 Uma prateleira contém 20 livros De quantas maneiras diferentes esses livros podem ser dispostos na prateleira 5 Um compact disc player tem espaço para 5 CDs há cinco bandejas numeradas de 1 a 5 em que se colocam os CDs 51 Matemática Discreta Possuo 50 CDs a De quantas maneiras o CD player pode ser carregado se todas as bandejas são ocupadas por CDs b De quantas maneiras o CD player pode ser carregado se eu coloco apenas um CD no aparelho 6 Uma prova de múltiplaescolha tem 15 perguntas cada qual com quatro respostas possíveis e 15 perguntas adicionais cada uma das quais com cinco respostas possíveis Quantas folhas de respostas diferentes são possíveis 7 Uma senha de um usuário em um computador de grande porte consiste em três letras seguidas de dois dígitos Quantas senhas diferentes são possíveis considere o alfabeto com 26 letras 8 Quantas senhas são possíveis na questão anterior se diferenciarmos as letras maiúsculas das minúsculas 9 Quantos números de CPF são possíveis 10 Uma pessoa pode viajar no trecho RecifeNatalRecife de ônibus automóvel avião navio ou trem Se o meio de transporte da ida não é o mesmo da volta de quantas maneiras essa pessoa pode realizar a viagem 11 Um alfabeto consiste em três letras A B C Nessa língua uma palavra é uma sequência arbitrária de no máximo três letras Quantas palavras existem nessa língua 12 Qual o valor de A após o seguinte código em C ter sido executado int A 1 for int I 1 I 10 I for int J 1 J 9 J for int K 1 K 8 K A A 1 13 Qual o valor de A após o seguinte código em C ter sido executado 52 Matemática Discreta int A 2 for int I 1 I 10 I A A 1 for int J 1 J 10 J A A 1 for int K 1 K 10 K A A 1 14 Qual o valor de A após o seguinte código em C ter sido executado int A 1 for int I 1 I 10 I for int J 1 J 9 J for int K 1 K 8 K A A 2 15 O Código de Endereçamento Postal CEP usado no Brasil tem como objetivo principal orientar e acelerar o tratamento e distribuição de objetos de correspondência É constituído de 8 dígitos cada um variando de 0 a 9 de modo que o 1º dígito representa a Região do Brasil o 2º a Sub região o 3º o Setor o 4º o Subsetor o 5º o Divisor de Sub setor e os três últimos recebem o nome de Sufixo e destinam se à identificação individual de localidades Caixas Postais Comunitárias Logradouros códigos especiais etc Região SubRegião Setor Subsetor Div de Setor Sufixo Sufixo Sufixo 53 Matemática Discreta a Quantos são os CEPs possíveis b Quantos são os CEPs possíveis para atender à região 3 Sede em Salvador c Quantos são os CEPs possíveis para atender à região 5 Sede em Recife 16 Um cofre tem três discos cada um com as mesmas 26 letras e só pode ser aberto quando se colocar uma determinada letra de cada um dos discos numa determinada posição Supondo que se ignora o segredo do cofre de quantas maneiras diferentes se podem colocar as letras dos discos nas referidas posições 17 Quantos números diferentes de 3 algarismos podemos formar com os algarismos 1 3 e 9 no sistema decimal 18 Quantos números de quatro algarismos podemos formar com os algarismos 0 2 4 6 e 8 no sistema decimal 19 Com cinco pedaços de tecidos nas cores amarela azul verde vermelha e branca quantas bandeiras tricolores podemos formar supondo que os tecidos são colocados só em tiras verticais 20 Uma senha de computador é constituída por seis caracteres três letras de 26 letras seguidas de três dígitos de 09 Determinar o número de senhas possíveis nos seguintes casos a tanto as letras como os dígitos podem ser repetidos b os dígitos não podem ser repetidos c as letras não podem ser repetidos d nem as letras nem os dígitos podem ser repetidos 21 Quantas senhas são possíveis no exercício anterior se elas apresentam as três letras e os três dígitos de forma alternada LDLDLD ou DLDLDL 22 Com os dígitos 0 1 2 5 e 8 quantos números de quatro algarismos diferentes podemos formar Quantos são múltiplos de 5 Quantos são múltiplos de 10 54 Matemática Discreta Respostas dos Exercícios Propostos 31 2 a 109 b 5x108 c 59 d 105 e 99899 f 99 g 109 99 4 20 x 19 x 18 x 17 x x 2 x 1 20 6 420 x 510 8 523 x 102 10 20 12 721 14 1441 16 263 18 453 500 20 a 263 x 103 b 263 x 10 x 9 x 8 c 26 x 25 x 24 x 103 d 26 x 25 x 24 x 10 x 9 x 8 22 a 96 b 42 c 24 36 Fatorial Definimos o fatorial de um número inteiro n 1 como o produto de todos os inteiros de n até 1 Notação n n n 1 n 2 2 1 Exemplos 5 54321 120 3 321 6 2 21 2 Obs Sabemos que 4 4321 43 5 54321 54 De modo geral podemos escrever n n n 1 Além disso definimos 1 1 e 0 1 Simplifique a 8 6 b 3 5 4 c d 3 8 6 5 e 4 2 6 f g 4 0 5 55 Matemática Discreta 37 Permutações O Princípio Multiplicativo e suas generalizações aplicamse frequentemente quando fazemos várias escolhas de um único conjunto e temos interesse na ordem em que são feitas Suponha que temos n elementos n 1 e queremos formar grupos com p elementos distintos 0 p n que diferem entre si pela ordem ou pela natureza dos p elementos que compõem cada grupo Qualquer um desses arranjos será chamado de permutação Pelo Princípio Multiplicativo temos que a 1ª escolha pode ser feita de n maneiras diferentes a segunda pode ser feita de n 1 formas a 3ª de n 2 formas e assim sucessivamente até que o pésimo elemento é escolhido de n p 1 maneiras Assim o número de permutações n p P que podemos formar com p elementos é n n1 n2 n p1 n n1 n2 n p1 np np1 2 1 np np1 2 1 p n n P n p Quando p n cada grupo é formado de n elementos e P n n n 38 Combinações Desejamos selecionar p objetos de um grupo de n objetos onde 0 p n mas não desejamos relevar a ordem na qual eles aparecem no agrupamento Queremos assim encontrar o número de agrupamentos de p elementos que sejam diferentes apenas pela natureza de pelo menos um elemento Esses agrupamentos são chamados de combinações e o número de combinações é dado por C p p n n n p Como distinguir agrupamento tipo permutação do tipo combinação Suponha que dispomos dos objetos A B e C e queremos formar agrupamento de dois elementos 56 Matemática Discreta Primeiro forme um agrupamento AB em seguida mude a ordem de seus elementos BA Pergunte se AB BA ou AB BA Se AB BA devemos fazer combinações Se AB BA devemos fazer permutações Exemplo 1 Com cinco pedaços de tecidos nas cores amarela azul verde vermelho e branco quantas bandeiras tricolores podemos formar supondo que os tecidos são colocados só em tiras verticais Dispomos de n 5 pedaços de tecido e queremos escolher p 3 pedaços de tecido para formar uma bandeira de três cores distintas Formase uma bandeira com os pedaços de cores A B V Mude a ordem dos pedaços de tecidos BVA Agora pergunte a bandeira ABV é igual ou diferente da bandeira BVA É claro que as bandeiras são diferentes pela ordem com que os pedaços de tecido aparecem a partir da haste da bandeira Logo bandeiras tricolores são agrupamentos que diferem pela ordem ou pela natureza de seus elementos pedaços de tecido constituindose permutações de 3 elementos escolhidos dentre 5 Assim podemos formar bandeiras Exemplo 2 Uma pessoa manifestou interesse por cinco livros diferentes numa feira de livros Todos os livros estavam em promoção por um preço único No entanto a pessoa só dispõe de dinheiro para adquirir apenas três deles De quantos modos podem ser feita a escolha de três desses livros Ora dispondo de n 5 livros escolher p 3 entre os cinco é formar agrupamentos de três livros ABC Agora mude a ordem dos livros CAB e indague se a escolha é a mesma ou diferente É claro que elas são iguais pois foram escolhidos os mesmos livros Para uma escolha diferente será necessária a troca de pelo menos um dos livros escolhidos inicialmente Tratase portanto de agrupamento tipo combinação O número de escolhas é Exemplo 3 Há 15 estações num ramal de uma estrada de ferro Quantos tipos de bilhetes de passagem são necessários para permitir a viagem entre duas estações quaisquer A viagem entre as estações C e D é diferente da viagem entre 57 Matemática Discreta D e C Tratase portanto de permutação de n 15 com p 2 estações De modo que teremos Exemplo 4 Numa empresa de Tecnologia da Informação trabalham 22 pessoas todas disponíveis para exercer diversas atividades em quatro projetos atualmente em execução Há necessidade de escolher seis pessoas para o projeto um quatro pessoas para o projeto 2 seis para o projeto 3 e duas pessoas responsáveis pelo projeto 4 De quantas formas é possível fazer a escalação Aprenda Praticando Exercícios Propostos 32 Os exercícios seguintes referemse ao Capítulo 3 Para resolvêlos você fará uso dos princípios de contagem estudados e das técnicas de classificação de agrupamentos em permutação ou combinação Você deve responder as questões discutir com seus colegas e em caso de dúvidas consulte seus tutores 1 Quantos anagramas de duas letras diferentes podemos formar com um alfabeto de 26 letras 2 Em um congresso há 12 professores de Física De quantas maneiras podemos formar uma comissão composta por 3 professores 3 Considerando os dígitos 1 2 3 4 e 5 quantos números de 2 algarismos diferentes podemos formar 4 Considere os algarismos 1 2 3 4 e 5 Quantos números com algarismos distintos superiores a 100 e inferiores a 1000 podemos formar se a o número é par b o número é ímpar c o número é par ou ímpar 5 De quantas formas podem ser escolhidos um presidente e um vicepresidente dentre um grupo de 20 pessoas 6 Quantas palavras de 6 letras distintas podemos formar com as letras da palavra MAXWEL 58 Matemática Discreta 7 Uma biblioteca tem 4 livros sobre Sistemas Operacionais 7 sobre Programação e 3 sobre Estrutura de Dados De quantas maneiras os livros podem ser arrumados numa prateleira sabendo os livros de uma mesma matéria precisam ficar juntos 8 Considere a palavra NUMERO a Quantos são os anagramas que podemos formar com as letras da palavra NUMERO b Quantos anagramas começam e terminam por vogal c Quantos começam e terminam por consoante d Quantos anagramas começam por consoante e terminam por vogal 9 O corpo docente de um curso de Sistemas de Informação de uma faculdade é composto por nove professores portadores do título de mestrado e quatro professores com título de doutorado De quantas maneiras podemos formar uma comissão para revisão curricular do curso composta por cinco professores sendo dois mestres e três doutores 10 Em um congresso há 12 professores de Física e 10 de Matemática e queremos formar comissões de 8 professores Quantas comissões podem ser formadas a sem restrições b havendo pelo menos um professor de Matemática c havendo pelo menos 4 professores de Matemática e 2 de Física 11 Um time de futebol leva 18 jogadores na comitiva 11 jogadores compõem o time titular De quantas maneiras o time titular pode ser formado 12 De quantas formas um júri popular de 5 homens e 7 mulheres pode ser selecionado dentre um elenco de 17 homens e 23 mulheres 13 Uma rede de computadores consiste em 60 nós Perguntase a A rede é projetada para resistir à falha de quaisquer dois nós De quantas formas esse tipo de falha pode ocorrer 59 Matemática Discreta b De quantas maneiras podem falhar um ou dois nós c Se um dos nós falhar de quantas maneiras podemos selecionar sete nós sem que estes sejam quaisquer um dos nós que falharam d Se dois nós falharem de quantas maneiras podemos selecionar sete nós de forma que eles incluam um dos nós que falharam 14 Uma caixa contém cinco fichas vermelhas e sete pretas Quatro fichas são retiradas da caixa todas de uma só vez sem reposição a De quantas formas podem ser retiradas quatro fichas b De quantas formas podem ser retiradas 4 fichas duas pretas e duas vermelhas c De quantas formas podemos retirar todas as quatro fichas vermelhas ou todas as quatro pretas d De quantas formas podemos retirar quatro sendo três ou quatro fichas pretas 15 Numa classe existem 8 alunas uma das quais se chama Maria e sete alunos um dos quais se chama José Formamse comissões de 5 alunas e 4 alunos Quantas são as comissões das quais a Maria participa b Maria participa sem José c José participa d José participa sem Maria e Maria e José participam simultaneamente f Maria e José são excluídos g Ou Maria ou José participa 16 Calcule C60 C61 C62 C63 C64 C65 e C66 Algumas dessas combinações são iguais Quais Que relação existe entre as combinações iguais Teste 17 Há quatro estradas diferentes entre as cidades A e B 3 estradas diferentes entre B e C e 2 estradas diferentes entre A e C De quantas maneiras podemos 60 Matemática Discreta a ir de A para C passando por B b ir de A até C passando ou não por B c ir de A até C e voltar d ir de A até C e voltar passando pelo menos uma vez por B e ir de A até C e voltar sem passar duas vezes pela mesma estrada 18 Quantas senhas de três letras podemos formar com as letras A B C D e E Quantas senhas de três letras sem repetição Quantas senhas de três letras diferentes não contêm a letra A Quantas senhas de três letras diferentes contêm a letra B 19 Cinquenta corredores competem em uma corrida de 10 quilômetros Quantos resultados são possíveis nos seguintes casos sem considerar empates a Quando queremos saber em que lugar cada corredor terminou a corrida b A corrida é uma prova de qualificação e desejamos apenas saber quais são os dez corredores mais rápidos c A corrida é um evento olímpico final e só interessa quem ganha medalha de ouro prata e bronze 20 Um saco contém 20 fichas idênticas numeradas de 1 a 20 Extraemse aleatoriamente cinco fichas Calcular de quantas formas cinco fichas podem ser extraídas nos seguintes casos a As fichas são extraídas uma a uma sem reposição Uma vez extraída uma ficha ela não é reposta no saco Assim extrair as fichas 1 2 3 4 e 5 é diferente de extrair as fichas 5 4 3 2 e 1 b As fichas são extraídas todas de uma vez sem reposição Assim extrair as fichas 1 2 3 4 e 5 é o mesmo que extrair as fichas 5 4 3 2 e 1 c As fichas são extraídas uma de cada vez com reposição Cada ficha extraída é devolvida ao saco Assim extrair as fichas 1 2 2 4 5 é diferente de extrair 2 4 1 2 5 61 Matemática Discreta 21 ENADE 2005 Para o desenvolvimento de um projeto determinada organização precisa definir dois grupos de trabalho um com três membros e outro com quatro membros Para o grupo de três elementos o primeiro indivíduo nomeado será o presidente o segundo o relator e o terceiro será o auxiliar enquanto que para o grupo de quatro elementos a ordem de nomeação não é relevante Essa organização conta com um quadro de quatorze funcionários todos igualmente aptos a compor qualquer um dos grupos de trabalho em qualquer função sendo que cada um integrará no máximo um desses grupos Nessa situação representando por Cm p a combinação de m elementos p a p e por Pm p o permutação de m elementos p a p concluise que a quantidade de maneiras distintas que a organização citada dispõe para compor os seus dois grupos é igual a 22 O jogo da Mega Sena consiste no sorteio de 6 números distintos escolhidos ao acaso entre os números 1 2 3 60 Uma aposta é uma escolha de 6 números distintos entre os 60 possíveis sendo premiadas aquelas que acertarem 4 quadra 5 quina ou todos os 6 números sorteados Um grupo de apostadores escolhe 20 números para jogar a Quantos são os jogos de 6 números que o grupo pode fazer com esses 20 números b Caso o grupo acerte na sena quantas quinas premiadas além da sena c Caso o grupo acerte na sena quantas quadras premiadas além da sena e das quinas 23 Considere o seguinte algoritmo void MaxMin vetor A vetor intMax int Min integer Max A1 Min A1 for int I 2 I 15 I if AI Max Max Ai if AI Min Min Ai 62 Matemática Discreta Quantas comparações entre os elementos do vetor A A1 A2 A15 são efetuadas 24 Numa certa comunidade dois homens sempre se cumprimentam na chegada com um aperto de mão e se despedem na saída com outro aperto de mão Um homem e uma mulher se cumprimentam com um aperto de mão mas se despedem com um aceno Duas mulheres só trocam acenos tanto para se cumprimentarem quanto para se despedirem Em uma comemoração na qual participaram 20 homens e 17 mulheres todos se cumprimentaram e se despediram na forma acima descrita Calcule quantos apertos de mão e quantos acenos foram dados 25 A partir de 64 cubos brancos todos iguais formase um novo cubo A seguir este novo cubo tem cinco de suas seis faces pintadas de vermelho Qual o número de cubos menores que tiveram pelo menos duas de suas faces pintadas de vermelho 26 As permutações da palavra PROVA foram listadas em ordem alfabética como se fossem palavras de cinco letras em um dicionário Qual a 73ª palavra dessa lista 27 Calcule a 8 5 5 4 36 P P P b n n P P 2 3 c 5 2 3 3 8 5 P P C d n n n C C P 2 3 2 e 63 Matemática Discreta Respostas dos Exercícios Propostos 32 2 C3 12 220 4 a 24 b 36 c 60 6 6 8 a 720 b 144 c 144 d 216 10 a b c 12 14 a b 5 7 2 C2 C c 7 4 5 4 C C d 7 4 5 7 1 3 C C C 16 Cn p Cn np 18 a 53 b 5 x 4 x 3 c 4 x 3 x 2 d 1 x 4 x 3 x 3 20 a b c 2020202020 205 22 a C b 6 c 1 24 720 apertos de mão e 612 acenos 26 RAOPV Saiba Mais Neste capítulo você teve oportunidade de conhecer técnicas de contagem de elementos de um dado conjunto fazendo uso do princípio aditivo e do princípio multiplicativo Além disso conheceu técnicas de diferenciação de agrupamentos tipo combinação e permutação Para conhecer mais sobre combinatória consulte o seguinte livro SANTOS José Plínio de Oliveira Introdução a análise combinatória Campinas Editora da Unicamp 1995 64 Matemática Discreta Desafio Tito Flavius Josephus foi um historiador que viveu em Jerusalém no século I DC conseguiu escapar da morte graças ao seu conhecimento em matemática e sua habilidade de pensar rápido Conta a lenda que Josephus como era conhecido e mais quarenta companheiros estavam numa caverna cercados por soldados romanos Sem alternativas decidiram cometer suicídio Fariam da seguinte maneira eles se posicionariam em forma de um circulo e começariam a se matar sempre o companheiro da esquerda Como Josephus não queria morrer ele sentouse num lugar seguro na verdade o lugar seguro e todos os seus companheiros morreram e apenas ele escapou Como ele conseguiu isso Você está desafiado a resolver esse problema Para melhor equacionálo pense em n pessoas entre as quais se encontra Josephus Decidese eliminar n1 pessoas do grupo da seguinte forma as pessoas são colocadas em um círculo com lugares marcados em ordem crescente no sentido horário o círculo é percorrido no sentido horário tantas vezes quanto necessário começando pela pessoa no lugar 1 e toda segunda pessoa viva nesta visitação é eliminada até que apenas uma sobreviva Qual é a posição que a pessoa sobrevivente ocupa Participe de um fórum de discussão que será orientado pelos professores executores e tutores para auxiliálo a resolver esse problema Boa sorte 65 Matemática Discreta Capítulo 4 Relações uma abordagem Intuitivamente o conceito de relação é próximo do conceito formal de relação No cotidiano são exemplos de relação irmão de maior ou igual faz fronteira com Em computação e Informática muitas construções são baseadas em relações como Banco de Dados Relacional Trataremos inicialmente de um tipo de relações as relações binárias Sejam A e B dois conjuntos Uma relação binária R de A para B é um conjunto de pares ordenados x y com x A e y B Se x y R dizemos que x está relacionado a y por meio de R e indicamos o fato escrevendo x R y Para exprimir que R é uma relação de A para B escrevemos R A B onde o conjunto A é chamado de conjunto de partida e B é o conjunto de chegada da relação R É claro que uma relação R de A para B é um subconjunto do produto cartesiano A x B Assim o produto cartesiano A x B é ele próprio uma relação de A para B Podemos então dizer que dados dois conjuntos A e B uma relação binária de A em B é um subconjunto de A x B Se R é uma relação binária em A x B então escrevemos x R y x y R Exemplo 1 Sejam os conjuntos A 1 2 3 e B 2 3 O produto cartesiano dos dois conjuntos A x B 12 13 22 23 3 2 3 3 a Se estivermos interessados na relação de igualdade então os pares 22 e 33 são os únicos que apresentam essa propriedade Então a relação R que contém esses pares é R1 x y A x B x y 66 Matemática Discreta b Se estivermos interessados na propriedade do primeiro número do par ser maior que o segundo escolheremos o par 32 Nesse caso a relação será R2 x y A x B x y c A relação R3 x y A x B y x1 1 2 2 3 A notação x R y indica que o par ordenado x y satisfaz à relação R A relação R pode ser descrita com palavras ou simplesmente pela enumeração dos pares ordenados que a satisfazem Exemplo 2 Considere S 1 2 e T 2 3 4 e R a relação dada pela descrição x R y x y é ímpar Então R 1 2 1 4 2 3 Exemplo 3 Considere o conjunto A 1 2 3 4 e a relação R definida de A em A pela condição x y R x divide y A divisão no conjunto dos números naturais é aquela que não deixa resto de modo que 1 divide 1 1 divide 2 2 divide 4 2 não divide 3 etc Assim a relação R é constituída pelos pares 1 1 1 2 1 3 1 4 22 2 4 3 3 e 4 4 41 Tipos de Relações Binárias Em relação ao número de elementos que se relaciona com um dado elemento como se classificam as relações binárias Se R é uma relação binária em S x T então R consiste em um conjunto de pares ordenados x y Uma determinada primeira componente x e uma determinada segunda componente y podem ser relacionadas diversas vezes na relação R a A relação R é dita umparaum ou injetiva se cada primeiro componente x e cada segundo componente y aparecem apenas uma vez na relação Exemplo 4 A relação do conjunto S 1 2 3 4 no conjunto 67 Matemática Discreta T a b c d e constituída pelos pares 1 b 2 c 3 a e 4 d é uma relação umparaum Exemplo 5 A relação R definida no conjunto S x x é um CPF no conjunto T x x é aluno do curso de Sistemas de Informação da UAB UFRPE é uma relação umparaum b A relação R é dita umparavários se alguma primeira componente x aparece mais de uma vez isto é se um determinado x faz par com mais de um y Exemplo 6 A relação do conjunto S 1 2 3 4 no conjunto T a b c d e constituída pelos pares 1 b 1 c 3 a 2 d é uma relação umparavários Exemplo 7 A relação R que faz corresponder um departamento S de uma empresa a uma seção T desse departamento c A relação R é dita váriosparaum se alguma segunda componente y faz par com mais de uma primeira componente x Exemplo 8 A relação definida do conjunto S 2 2 1 1 3 no conjunto T 1 4 5 9 pela condição x y R y x2 Exemplo 9 A relação definida no conjunto A de todas as mulheres 68 Matemática Discreta da cidade de Trindade PE com correspondentes em A através da condição x y R x filha de y é uma relação váriosparaum d A relação R é dita váriosparavários se pelo menos um y faz par com mais de um x e pelo menos um x faz par com mais de um y Exemplo 10 A relação definida do conjunto S 0 1 1 no conjunto T 0 1 1 pela condição x y R x2 y2 2 é uma relação vários para vários Exemplo 11 Uma relação R definida no conjunto C de clientes de uma empresa no conjunto P dos produtos que esta empresa vende tal que x y R x compra produto y é uma relação vários para vários 42 Relações binárias em um conjunto A Uma relação em um conjunto A é uma relação do conjunto A em A Tratase de um subconjunto do produto cartesiano A x A A2 Exemplo 12 Considere o conjunto A 1 2 3 Os pares da relação R definida em A pela condição x y R x 2y são R 11 12 13 21 22 23 32 3 3 Exemplo 13 Seja A Mara Cláudia Anamaria Beth João Clara José um conjunto de pessoas tais que Anamaria é mãe de Clara e de Cláudia Clara é mãe de Beth e Beth é mãe de Mara de João e de José Escreva os pares das seguintes relações definidas em A a x R y x é irmã ão de y b x S y x é ancestral de y x é ancestral de y se x é pai mãe avô ou avó de y Podemos escrever as relações na forma de tabelas 69 Matemática Discreta Relação R Relação S irmã ao de ancestral de x y Anamaria Clara Clara Cláudio Anamaria Cláudia Cláudio Clara Anamaria Beth Mara João Anamaria Mara João Mara Anamaria João Mara José Anamaria José José Mara Clara Beth João José Clara Mara José João Clara João Clara José Beth Mara Beth João Beth José 43 Operações com relações como operar com relações binárias Ora as relações binárias são conjuntos de pares ordenados portanto podemos definir a união a interseção de relações Podemos também definir a relação complementar Além disso definimos a relação diferença e a relação diferença simétrica Sejam R1 e R2 relações binárias em num conjunto A Isso significa que R1 e R2 são subconjuntos de A x A Então podemos realizar seguintes operações que resultem em novos subconjuntos de A x A isto é novas relações binárias denotadas por 70 Matemática Discreta Exemplo 14 Considere R1 e R2 duas relações binárias em A 1 2 3 definidas por x R1 y x y e x R2 y x y Escreva os pares ordenados de R1 e R2 Forneça descrições verbais para as relações abaixo e escreva os seus elementos As tabelas representativas das relações R1 e R2 são as seguintes Relação R1 Relação R2 Relação R1 R2 1 1 1 1 1 1 1 2 2 1 1 2 1 3 2 2 1 3 2 2 3 1 2 1 2 3 3 2 2 2 3 3 3 3 2 3 3 1 3 2 3 3 Relação R1 R2 Relação Relação 1 1 2 1 1 2 1 2 3 1 1 3 1 3 3 2 2 3 Dizemos que x y R1 R2 x y ou x y x y R1 R2 x y x y x y x y x y Exemplo 15 Seja A o conjunto de todos os estudantes de uma faculdade e B o conjunto de todos os livros de sua biblioteca Sejam R e S duas relações definidas respectivamente por a b R o estudante a é obrigado ler livro b no seu curso 71 Matemática Discreta a b S o estudante a leu o livro b Descreveremos os pares ordenados a b em cada uma das seguintes a a b R S o estudante a é obrigado ler livro b no seu curso ou já leu o livro b b a b R S o estudante a já leu o livro obrigatório b no seu curso c a b o estudante a não é obrigado ler livro b no seu curso d a b o estudante a não leu o livro b e a b R S o estudante a é obrigado ler livro b no seu curso e não o leu f a b S R o estudante a já leu livro não obrigatório b g a b R S o estudante a é obrigado ler livro b no seu curso e não o leu ou o Estudante a já leu livro não obrigatório b 44 Propriedades das Relações definidas em um conjunto A Seja R uma relação binária em A Dizemos que a R é reflexiva se x A x R x isto é x A x x R R não é reflexiva se x A tal que x x R b R é simétrica se x y A se x R y então y R x isto é se x y R então y x R para x y em A R não é simétrica se x y R mas y x R c R é transitiva se x y z A se x R y e y R z então x R z isto é se xy R e y z R então x z R para xy z em A R não é transitiva se x y R e y z R mas x z R d R é antisimétrica xy A se x y então xy R ou yx R mas não ambos R não é antisimétrica se x y com xy R e yx R 72 Matemática Discreta Exemplo 16 Considere as seguintes relações em S 1 2 3 4 Quais dessas relações são reflexivas simétricas antisimétricas e transitivas R1 11 12 21 22 34 41 44 R2 11 12 21 R3 11 12 14 21 22 33 41 44 R4 21 31 32 33 41 42 43 R5 11 12 13 14 22 23 24 33 34 44 R6 34 23 R7 34 R8 11 22 33 44 Reflexivas R3 R5 e R8 Simétricas R2 R3 e R8 Transitivas R4 R5 R7 e R8 Antisimétricas R4 R5 R6 R7 e R8 Exemplo 17 Quais das relações abaixo são reflexivas simétricas transitivas e antisimétricas Considere A a b c R1 aabbcc R2 abbaaaac R3 abaccaba R4 abbbcc Relação R1 Reflexiva simétrica antisimétrica e transitiva Relação R2 Não é reflexiva não simétrica não é antisimétrica e não é transitiva Relação R3 Não é reflexiva não é antisimétrica não é transitiva É simétrica Relação R4 Não é reflexiva nem simétrica É antisimétrica e transitiva 73 Matemática Discreta 45 Representação gráfica de Relações Binárias Uma relação binária R de um conjunto finito A para um conjunto finito B pode ser representada graficamente da seguinte maneira a cada elemento de A e cada elemento de B corresponde um nó nodo ou aresta e a cada par da relação a b corresponde uma seta flecha ou linha ligando o elemento a A ao elemento b B Veja o exemplo seguinte Exemplo 18 A relação R a1 b1 a1 b2 a2 b1 a2 b3 a3 b3 do conjunto A a1 a2 a3 a4 no conjunto B b1 b2 b3 pode ser representada por 46 Grafo de uma relação em um conjunto A Uma relação R de A em A pode ser representada por um grafo onde cada elemento do conjunto A é denominado nodo e cada par a b é representado por uma seta aresta do grafo com origem em a e destino em b Os pares a a R são representados por um laço A tal representação dáse o nome de grafo orientado ou dígrafo Exemplo 19 Seja R é uma relação de A em A 123 definida por R 11 12 13 21 31 32 A figura abaixo é o grafo de R Lembrete Observe que uma relação em A é reflexiva se para todo x A x R x ou seja o par xx A Isso significa que o grafo de R tem um laço em cada nó ou seja um ligando cada elemento a si mesmo 74 Matemática Discreta Exemplo 20 Seja A 123 R 11 22 33 12 13 32 é uma relação reflexiva Exemplo 21 A relação em A a b c onde R aa ab ba ac ca bc não é simétrica O grafo de apresenta uma seta de b para c mas não apresenta seta de c para b Exemplo 22 A relação em A a b c onde R a a a b b a a c c a b c não é transitiva pois apresenta seta de c para a seta de a para c mas não apresenta laço de c para c Também apresenta seta ligando c ao elemento a seta do a ao b mas não apresenta seta ligando c ao b Observe que também falta um laço em b Uma relação de A em A a b c é dita antisimétrica se x y então x y R ou y x R Exemplo 23 Considere a relação em A a b c definida por R a a a b b c c a c c A relação R é antisimétrica No seu grafo existe no máximo uma seta ligando dois nodos diferentes Lembrete O grafo de uma relação simétrica de A em A apresenta para cada seta entre dois nodos outra seta no sentido contrário indicando que para cada par a b R existe o par inverso b a Lembrete Uma relação R de A em A é transitiva se x R y e y R z então x R z Isto significa que se existe uma seta de x para y e uma seta de y para z então existe uma seta de x para z Lembrete Observe que uma relação R é anti simétrica se no seu grafo existe no máximo uma seta ligando dois nodos diferentes 75 Matemática Discreta Exemplo 24 A relação no conjunto dos números naturais N é reflexiva porque para qualquer x N x x é verdadeira É também transitiva pois para quaisquer x y z N se x y e y z então x z A relação não é simétrica pois 3 4 não implica 4 3 A relação é antisimétrica pois para quaisquer x y N se x y e y x então x y Exemplo 25 Seja X 1 2 34 e S P X Y Y é subconjunto de X Definimos a relação em S por A B A B Verificase que é reflexiva simétrica transitiva e não é antisimétrica 47 Relação nária Dados os conjuntos A1 A2 A3 An uma relação nária em A1 x A2 x A3 x x An é um subconjunto de A1 x A2 x A3 x x An Os conjuntos A1 A2 An são chamados de domínios da relação e n é o seu grau Um elemento da relação é chamado uma nupla Quando A1 A2 An a relação é dita interna Caso A1 A2 An a relação é chamada relação externa Exemplo 26 a Seja R uma relação interna ternária em N x N x N onde x y z R x2 y2 z2 Alguns ternos da relação R são apresentados na tabela a seguir 0 5 5 5 0 5 3 4 5 4 3 5 6 8 10 8 6 10 b Considere o conjunto A 1 2 3 4 e a relação interna R definida no produto cartesiano A x A x A pela sentença x y z R x divide y z A tabela apresenta os ternos dessa relação 76 Matemática Discreta 1 1 1 1 2 3 1 4 1 2 2 2 3 1 2 4 2 2 1 1 2 1 2 4 1 4 2 2 2 4 3 2 1 4 3 1 1 1 3 1 3 1 1 4 3 2 3 1 3 2 4 4 4 4 1 1 4 1 3 2 1 4 4 2 3 3 3 3 3 1 2 1 1 3 3 2 1 1 2 4 2 3 4 2 1 2 2 1 3 4 2 1 3 2 4 4 4 1 3 Exemplo 27 Seja R uma relação externa consistindo de 5uplas A N P D H representando uma viagem aérea onde A é a companhia aérea N é o número do voo P é o ponto de partida D é o ponto de destino e H é a hora da partida Se TAM tem um voo de número JJ 3501 de Recife para São Paulo às 02h35min então TAM JJ 3501 Recife São Paulo 02h35min pertence a R Os seus domínios são o conjunto de todas as companhias aéreas o conjunto dos números naturais o conjuntos das cidades o conjunto das cidades e o conjunto das horas Companhia Voo Partida Destino Horário TAM JJ 3501 RECIFE SÃO PAULO 235 TAM JJ 3515 RECIFE SÃO PAULO 1000 GOL G3 1992 FORTALEZA NATAL 1150 TAM JJ 3817 BELO HORIZONTE CURITIBA 2000 GOL G3 1629 PORTO SEGURO RECIFE 320 Exemplo 28 Na Informática a grande aplicação das relações externas são os bancos de dados que utilizam os modelos relacionais Os modelos relacionais são compostos de relações ou tabelas bidimensionais cujas operações são descritas em termos de álgebra relacional Com este modelo as tabelas de dados podem ser manipuladas para retornar outras tabelas de dados oferecendo aos usuários informações Por exemplo um banco de dados contendo registro dos vestibulandos de uma faculdade feito em domínios contendo o nome do estudante a inscrição do estudante o curso pretendido e a média alcançada O modelo relacional representa o banco de dados de 77 Matemática Discreta registros como uma relação nária Esses registros são representados por uma 4upla da forma Nome Inscrição Curso Média Abaixo relacionamos alguns exemplos de registros desse banco de dados sob a forma de tabela Nome Inscrição Curso Média FREDERICO 234565 DIREITO 79870 ANA 456292 DIREITO 69847 ROBERTA 123457 SI 87654 HUGO 987340 ADMINISTRAÇÃO 69834 Exemplo 29 Seja A A B C D E F G H o conjunto de alguns estudantes de uma universidade e B L1 L2 L3 L10 o conjunto de alguns livros de sua biblioteca Sejam R e S duas relações definidas de A em B respectivamente por a b R o estudante a é obrigado ler livro b no seu curso a b S o estudante a leu o livro b de acordo com as tabelas abaixo Relação R Relação S Aluno Livro Aluno Livro A L1 B L4 B L2 D L9 A L3 C L2 B L4 E L2 C L2 F L10 D L5 G L7 E L6 C L3 F L3 A L4 G L7 H L8 78 Matemática Discreta As tabelas abaixo apresentam as relações R S R S R S S R e R S Relação R S Aluno Livro Aluno Livro A L1 D L9 B L2 E L2 A L3 F L10 B L4 C L3 C L2 A L4 D L5 H L8 E L6 F L3 G L7 Relação R S Relação R S Aluno Livro Aluno Livro B L4 A L1 C L2 B L2 G L7 A L3 D L5 E L6 F L3 79 Matemática Discreta Relação S R Relação R S Aluno Livro Aluno Livro Aluno Livro D L9 A L1 D L9 E L2 B L2 E L2 F L10 A L3 F L10 C L3 D L5 C L3 A L4 E L6 A L4 H L8 F L3 H L8 48 Álgebra Relacional É o conjunto de operações formais realizadas sobre relações produzindo como resultado relações Considere o seguinte banco de dados composto pelas tabelas relações seguintes Aluno Nome CódDisc Aline da Silva MAT0285 Aline da Silva SIS0214 Carina Sousa MAT0285 Carlos André MAT0285 Carlos André SIS0225 Carlos André MAT0331 Fernando Antunes SIS0214 Laura Abreu MAT0285 Vivian Peixoto MAT0285 Vivian Peixoto SIS0214 80 Matemática Discreta Cadastro Nome Endereço Sexo Aline da Silva Rua das Flores 10 Feminino Carina Sousa Rua Vargas 23 Feminino Carlos André Rua Abreu 18 Masculino Fernando Antunes Rua 24 de Abril1 Masculino Laura Abreu Rua do Padre1 Feminino Marcelo Silva Rua Getulio90 Masculino Vivian Peixoto Rua Jacinto38 Feminino Disciplina CódDisc Nomedadisciplina Curso MAT0285 Matemática Discreta Ciência da Comp SIS0214 Lógica Ciência da Comp SIS0237 Informática Administração SIS0225 Teoria da Comp Ciência da Comp MAT0331 Matemática I Licenciatura em Comp Podemos usar duas operações unárias com as relações A operação Restrição seleciona cria uma nova tabela composta pelas linhas da tabela original que satisfaça a uma certa propriedade predicado A sintaxe utilizada é predicado Relação Exemplo 30 Restrição de Aluno onde Sexo Masculino fornecendo Resultado 1 sexo Masculino Aluno 81 Matemática Discreta Resultado 1 Carlos André Rua Abreu 18 Masculino Fernando Antunes Rua 24 de Abril 100 Masculino Marcelo Silva Rua Getulio90 Masculino Exemplo 31 Restrição de Disciplina onde Curso Ciência da Computação fornecendo Resultado 2 curso Ciência da Computação Disciplina Resultado 2 CódDisc Nomedadisciplina Curso MAT0285 Matemática Discreta Ciência da Comp SIS0214 Lógica Ciência da Comp SIS0225 Teoria da Comp Ciência da Comp Exemplo 32 Restrição de Cadastro onde CódDisc SIS0214 fornecendo Resultado 3 CodDisc SIS 0214 Cadastro Resultado 3 Nome CódDisc Aline da Silva SIS0214 Fernando Antunes SIS0214 Vivian Peixoto SIS0214 A operação Project projeção cria uma nova tabela composta por determinadas colunas da tabela original eliminando quaisquer linhas duplicadas A sintaxe usada é lista de atributos Relação Exemplo 33 Projeção de Aluno baseada em Nome Endereço fornecendo Resultado 4 nome endereço Aluno 82 Matemática Discreta Resultado 4 Nome Endereço Aline da Silva Rua das Flores 10 Carina Sousa Rua Vargas 23 Carlos André Rua Abreu 18 Fernando Antunes Rua 24 de Abril 100 Laura Abreu Rua do Padre 1 Marcelo Silva Rua Getulio 90 Vivian Peixoto Rua Jacinto 38 Exemplo 34 Projeção de Disciplina baseada em Nomeda disciplina Curso fornecendo Resultado 5 nomedadisciplina curso Disciplina Resultado 5 Nomedadisciplina Curso Matemática Discreta Ciência da Comp Lógica Ciência da Comp Informática Administração Teoria da Comp Ciência da Comp Matemática I Licenciatura em Comp Exemplo 35 Projeção de Disciplina baseada em Código da disciplina Nome da disciplina fornecendo Resultado 6 coddadisc momedadisciplina Disciplina 83 Matemática Discreta Resultado 6 CódDisc Nomedadisciplina MAT0285 Matemática Discreta SIS0214 Lógica SIS0237 Informática SIS0225 Teoria da Comp MAT0331 Matemática I A operação junção natural natural join cria uma relação pela combinação dos campos de uma relação com aquelas de outra baseada nos valores comuns em um conjunto de colunas comuns É realizada pela seleção das linhas e a projeção das colunas do produto cartesiano das relações A sintaxe é Relação A X condição de junção Relação B Exemplo 36 Junção de Aluno e Cadastro baseada em Nome fornecendo Resultado 7 Aluno X Nome Cadastro Resultado 7 Nome Endereço Sexo Cód Disc Aline da Silva Rua das Flores 10 Feminino MAT0285 Aline da Silva Rua das Flores 10 Feminino SIS0214 Carina Sousa Rua Vargas 23 Feminino MAT0285 Carlos André Rua Abreu 18 Masculino MAT0285 Carlos André Rua Abreu 18 Masculino SIS0225 Carlos André Rua Abreu 18 Masculino MAT0331 Fernando Antunes Rua 24 de Abril 100 Masculino SIS0214 Laura Abreu Rua do Padre 1 Feminino MAT0285 Vivian Peixoto Rua Jacinto 38 Feminino MAT0285 Vivian Peixoto Rua Jacinto 38 Feminino SIS0214 84 Matemática Discreta Exemplo 37 Junção de Cadastro e Disciplina baseada em Códigodedisciplina fornecendo Resultado 8 Cadastro X CodDisc Disciplina Resultado 8 Nome CódDisc Nomedadisciplina Curso Aline da Silva MAT0285 Matem Discreta Ciência da Comp Carina Sousa MAT0285 Matem Discreta Ciência da Comp Carlos André MAT0285 Matem Discreta Ciência da Comp Laura Abreu MAT0285 Matem Discreta Ciência da Comp Vivian Peixoto MAT0285 Matem Discreta Ciência da Comp Aline da Silva SIS0214 Lógica Ciência da Comp Fernando Antunes SIS0214 Lógica Ciência da Comp Vivian Peixoto SIS0214 Lógica Ciência da Comp Carlos André SIS0225 Teoria da Comp Ciência da Comp Carlos André MAT0331 Matemática I Licenc em Comp Aprenda Praticando Exercícios Propostos 41 Agora é a sua vez Verifique se você entendeu os assuntos desse capítulo referentes ao conceito de relações resolvendo os exercícios propostos As respostas dos exercícios de número par serão apresentadas logo a seguir Caso persistam dúvidas tente esclarecê las com os professores executores e tutores nos fóruns de discussão da disciplina que serão formados 1 Considere as seguintes relações definidas de Z em Z R1 a b a b R2 a b a b R3 a b a b ou a b R4 a b a b R5 a b a b 1 R6 a b a b 3 Faça tabelas de cada uma das relações acima indicadas cada uma com pelo menos cinco pares 85 Matemática Discreta 2 Classifique cada uma das relações abaixo definidas de A em A onde A 1 2 3 12 como umparaum umparavários váriosparaum e váriosparavários a R1 1 2 14 1 6 2 3 4 3 b R2 97 65 3 6 8 5 c R3 12 5 8 4 6 3 7 12 d R4 27 8 4 2 5 7 6 101 3 Classifique cada uma das relações definidas de A em A como umparaum umparavários váriosparaum e vários paravários a A N x R y x y 1 b A conjunto de todas as mulheres de Recife x R y x é filha de y c A P1 2 3 A R B A B d A N x R y x 5 4 Sejam R e S relações binárias em N definidas por xRy x divide y e x S y 5x y Quais pares pertencem às relações seguintes 5 Determine as relações R definidas no conjunto de todas as pessoas são reflexivas simétricas antisimétricas ou transitivas onde a b R se e somente se a a é mais alto que b b a e b nasceram no mesmo dia c a tem o mesmo primeiro nome que b d a é primo de b a é primo de b se um dos pais de a é irmão de um dos pais de b e a é ancestral de b 6 Dados os conjuntos A de alunos do Curso de SI D de disciplinas oferecidas no segundo semestre de 2008 L de salas onde 86 Matemática Discreta serão ministradas as aulas e H de horários de aulas A José Joana Bianca Tiago D SI101 SI103 SI201 SI203 SI304 L 13 34 26 Lab2 Lab5 H 08h00min09h50min 10h00min11h50min 18h45min 20h15min 20h30min22h00min Simule tabelas um mínimo de 5uplas representando as seguintes relações a R1 de A em D que fornece a relação das disciplinas de cada aluno b R2 de D em L relação entre as disciplinas e o seu local c R3 de L em H que relaciona a sala de aula com horários 7 Seja o conjunto S Mara Cláudia Anamaria Beth João Clara José Sabendo que Anamaria é mãe de Clara e de Cláudia Clara é mãe de Beth e Beth é mãe Mara de João e de José e as seguintes relações definidas em S x R y x é irmã ão de y x S y x é ancestral de y desenhe os grafos das relações R S S R R S Quais relações R e S são reflexivas simétricas antisimétricas e transitivas 8 Classifique as relações a seguir definidas nos conjuntos S dados como reflexivas simétricas antisimétricas e transitivas a S Z x R y x y b S N x R y xy é par c S 1 2 3 x 1 2 3 x1 y1 R x2 y2 x1 x2 e y1 y2 d S P123 A R B A B 9 Tomando por base as tabelas apresentadas no item 48 expresse cada pesquisa abaixo em álgebra relacional e apresente o resultado em forma de tabela a Dê os nomes de todos os alunos que são do sexo feminino b Dê os nomes de todas as disciplinas do Curso de Ciência da Computação c Dê os nomes de todos os alunos que cursam Matemática Discreta 87 Matemática Discreta d Dê os nomes de todas as disciplinas que Carlos André cursa e Dê os nomes de todos os alunos do sexo feminino que cursam SIS0214 Respostas dos Exercícios Propostos 41 2 a vários para vários b vários para um c um para um d um para vários 4 a 2 6 3 17 e 10 b 2 12 c 3 17 d 215 Conclusão No último capítulo deste fascículo abordamos o conceito de relação Conhecemos como as relações se classificam quanto ao número de elementos relacionados aprendemos a distinguir as propriedades das relações binárias internas e representar as relações por grafos por n uplas e por tabelas Aprendemos como efetuar operações com relações notadamente as operações de restrição seleção projeção e junção em tabelas de banco de dados relacional Saiba Mais As relações binárias podem ser também representadas por matrizes booleanas da seguinte forma Suponhamos que R é uma relação do conjunto A a1 a2 an 88 Matemática Discreta no conjunto B b1 b2 bm A relação R é representada pela matriz n x m MR mij onde mij 1 se ai bj R e mij 0 se ai bj R Por exemplo considere a relação em A 2 3 6 definida por a R b a b A matriz de R é M A matriz de uma relação é uma excelente maneira de representar relacionamentos e através dela podemos verificar se uma dada relação de A em A é reflexiva simétrica transitiva e antisimétrica Se você se interessa pelo assunto consulte as obras abaixo indicadas GERSTING Judith L Fundamentos Matemáticos para a Ciência da Computação Tradução Valéria de Magalhães Iorio Rio de Janeiro LTC 2004 LIPSCHUTZ Seimour LIPSON Marc Lars Teoria e Problemas de Matemática Discreta Porto Alegre Bookman 2004 89 Matemática Discreta Referências ABE Jair Minoro PAPAVERO Nelson Teoria intuitiva dos conjuntos São Paulo McGraw Hill 1997 ALENCAR Filho Edgard de Iniciação à Lógica Matemática São Paulo Nobel 1995 GERSTING Judith L Fundamentos Matemáticos para a Ciência da Computação Tradução Valéria de Magalhães Iorio Rio de Janeiro LTC 2004 KOLMAN Bernard Introdução à Álgebra Linear com aplicações Tradução de Alessandra Bosquilha Rio de Janeiro LTC 2006 LIPSCHUTZ Seimour LIPSON Marc Lars Teoria e Problemas de Matemática Discreta Porto Alegre Bookman 2004 SANTOS José Plínio de Oliveira Introdução a analise combinatória Campinas Editora da Unicamp 1995 SCHEINERMAN Edward R Matemática Discreta uma introdução Tradução de Alfredo Alves de Farias São Paulo Pioneira Thomson Learning 2003 ROSS Kenneth A WRIGHT Charles R B Discrete Mathematics PrenticeHall 1999 TRUSS J K Discrete mathematics for computer scientist Addison Wesley 1999 httpproblemasteoremaswordpresscom20071120somatorio duplo httpwwweancombr httpwwwmatufmgbrelaineGAALgaalt1pdf httpwwwfunepeedubr91funepeprofessoresmateriais57 MATRIZESppt2561matrizes 90 Matemática Discreta Considerações Finais Caro cursista nesse fascículo você teve oportunidade de conhecer os conceitos de somatório matrizes contagem e relações Percebeu através de exemplos que existem muitas aplicações nas áreas de computação e informática No próximo fascículo abordaremos os seguintes temas da Matemática Discreta que são também utilizados nos cursos das áreas de computação e informática Sequência e Recursão Técnicas de Provas e o Princípio de Indução Finita Recife 2010 Matemática Discreta Francisco Flávio Modesto de Andrade Universidade Federal Rural de Pernambuco Reitor Prof Valmar Corrêa de Andrade ViceReitor Prof Reginaldo Barros PróReitor de Administração Prof Francisco Fernando Ramos Carvalho PróReitor de Extensão Prof Paulo Donizeti Siepierski PróReitor de Pesquisa e PósGraduação Prof Fernando José Freire PróReitor de Planejamento Prof Rinaldo Luiz Caraciolo Ferreira PróReitora de Ensino de Graduação Profª Maria José de Sena Coordenação Geral de Ensino a Distância Profª Marizete Silva Santos Produção Gráfica e Editorial Capa e Editoração Allyson Vila Nova Rafael Lira e Italo Amorim Revisão Ortográfica Marcelo Melo Ilustrações Diego Almeida Coordenação de Produção Marizete Silva Santos Sumário Apresentação 4 Capítulo 1 Função uma ferramenta importante 6 11 O que é função 7 12 Domínio e Contradomínio 7 13 Função Injetora 9 14 Função Sobrejetora 10 15 Função Bijetora 10 16 Função Inversa 11 17 Função Composta 13 18 Sequência 16 Capítulo 2 Recursão um método de definição 24 21 O que é recursão 24 22 Recursão 24 Capítulo 3 Teoremas e Técnicas de Provas 41 31 O que é um teorema 41 32 Estratégias de Provas 43 Capítulo 4 Princípio de Indução Finita 49 Considerações Finais 63 Apresentação Caro a cursista Seja bemvindo a ao terceiro módulo de Matemática Discreta Ao finalizar a disciplina abordaremos neste terceiro fascículo alguns temas relevantes em aplicações nas áreas de informática como função recursão teoremas e técnicas de provas e o princípio de indução matemática No primeiro capítulo você estudará as funções Estudaremos as funções injetoras sobrejetoras bijetoras e a função inversa Apresentaremos exemplos de funções utilizadas na informática tais como sequências numéricas a função mod e a função hash No segundo capítulo você descobrirá o que é uma definição recursiva ou indutiva Serão apresentados exemplos de sequências e funções definidas recursivamente objetivando introduzir o conceito de um algoritmo recursivo No terceiro capítulo você terá oportunidade de conhecer diversas técnicas de provas de proposições matemáticas muito úteis na resolução de problemas da disciplina Por fim no quarto capítulo será abordado o princípio de indução matemática que é usado quando se quer provar afirmações sobre propriedades dos números naturais Esperamos que você tenha bom proveito neste terceiro fascículo estudando com afinco os assuntos e realizando todos os exercícios propostos Bons estudos Coitada da mamãe está preocupada porque amanhã vou começar o jardimdeinfância e ela tem medo de que eu não goste Eu poderia dar uma acalmada nela dizendo que estou com vontade de ir ao jardimdeinfância depois para o primeiro grau o colegial a universidade etc Sabe mamãe eu quero ir para o jardimdeinfância e estudar bastante assim mais tarde eu não vou ser uma mulher frustrada e medíocre como você É tão bom confortar a mãe da gente 6 Matemática Discreta Capítulo 1 Função uma ferramenta importante Disponível em httpwwwipeagovbr A figura acima representa o gráfico de uma função que relaciona o percentual da renda total do Brasil auferido em 2004 pelos x dos brasileiros de menor renda Constatase que a renda total dos 60 de menor renda representou apenas 20 da renda total do país e que 60 da renda total correspondem a 20 dos brasileiros de maior renda Esta curva é chamada Curva de Lorenz e faz parte da prova do ENADE que examinou os estudantes dos cursos das áreas de computação e informática no ano de 2008 O conceito de funções é largamente empregado em todos os ramos de atividade por isso é comum os testes de avaliação conter questões versando sobre o assunto No caso da computação e informática a sua importância torna se clara quando queremos associar a cada elemento de um conjunto um elemento particular de outro conjunto Desta forma podemos definir sequências e somas estabelecer relações de causa e efeito processar informações dos mais diferentes tipos além de estimar o tempo necessário para que um computador realize uma determinada tarefa num determinado algoritmo 7 Matemática Discreta 11 O que é função Sejam A e B dois conjuntos Uma função de A em B é a associação de exatamente um elemento de B a cada elemento de A As seguintes notações são usadas f A B se f é uma função de A em B fa b se b é o único elemento de B associado pela função f ao elemento a de A 12 Domínio e Contradomínio Se f é uma função de A em B dizse que A é o domínio de f e B é o contradomínio de f Se fa b dizse que b é a imagem de a por f Chamase também de imagem de f o conjunto de todas as imagens dos elementos de A denotado por Imf Se f é uma função de A em B dizse que f mapeia A em B A figura acima apresenta uma função cujo domínio é A 1 4 7 e contradomínio B 1 4 6 7 8 9 12 e conjunto imagem Imf 6 9 12 Apresentaremos a seguir exemplos de funções a maioria empregada em construções nas áreas de computação Exemplo 1 Consideremos que f seja uma função que associa um número a cada um dos cursos de uma faculdade de modo que esse número represente a demanda relação candidatovaga para cada um dos seus cursos no Vestibular de 2009 Se domínio da função f é o conjunto C Administração Direito Sistema de Informação Fonoaudiologia Fisioterapia Psicologia Relações Internacionais Turismo O contradomínio é o conjunto dos números reais Podemos escrever por exemplo fDireito 78 fAdministração 26 fFisioterapia 74 fPsicologia 54 e fSistemas de Informação 20 8 Matemática Discreta fRelações Internacionais 14 fFonoaudiologia 17 fTurismo 24 Exemplo 2 Seja S o conjunto de todas as pessoas do Recife cadastradas na Receita Federal e T o conjunto de todos os CPF A função f S T associa cada pessoa x ao seu CPF y Exemplo 3 Se f é uma função de Z para Z que associa a cada inteiro o seu quadrado Neste caso fx x2 onde o domínio é o conjunto dos números inteiros assim como o contradomínio é conjunto dos números inteiros A imagem de f é constituída de todos os inteiros não negativos Exemplo 4 Em linguagens de programação domínio e o contradomínio das funções são sempre especificados Tomemos por exemplo a declaração de uma função em Pascal seguinte function QUAD x real real Ela especifica que o domínio da função QUAD é o conjunto dos números reais e o contradomínio é o conjunto dos números reais Exemplo 5 A definição de função inclui função de mais de uma variável Podemos ter uma função f A1xA2xA3 B que associa a cada terno do produto cartesiano A1xA2xA3 um elemento de B Por exemplo f Z x N x 1 2 Z dada por fx y z xy z Podemos escrever f4 3 1 43 1 64 1 63 Exemplo 6 A função chão fx x associa a cada número real x o maior inteiro menor ou igual a x A função teto gx x associa a cada real x o menor inteiro maior ou igual a x Ambas são funções de R em Z Como exemplo temos f235 235 2 f09 0 g478 478 5 e g13 1 Exemplo 7 Considere x um número real O valor inteiro de x denotado por INTx converte x em um inteiro deletando a parte fracionária de x É uma função de R em Z Exemplos INT785 7 INT49 4 Exemplo 8 O valor absoluto de um número real x denotado por ABSx é definido como o maior dos valores entre x e x É uma função de R em R Pois ABS3 3 ABS47 47 e ABS0 0 Exemplo 9 Dado um inteiro positivo m a função f N N definida por fx resto da divisão euclidiana de x por m m 0 será denotada por fx xmod m É também chamada função mod m 9 Matemática Discreta Por exemplo para m 5 temos que f7 7mod 5 2 f2 2mod 5 2 f13 13mod 5 3 f8 3 f10 10mod 5 0 f5 5mod 5 0 13 Função Injetora Uma função f é dita injetora ou injetiva se e somente se x y então fx fy para quaisquer x e y do domínio de f Figura 1 Figura 2 O gráfico mostrado na figura acima à esquerda ilustra uma função definida no conjunto A em B Como elementos diferentes do domínio a função tem imagens diferentes então f é injetora A figura acima à direita ilustra uma função não injetora pois existem dois elementos diferentes com a mesma imagem Exemplo 10 A função f N em N tal que fn 2n é uma função injetora pois se n1 n2 então Mas a função fx x2 definida em Z não é injetora pois se tomarmos x 2 e x 2 obteremos f2 f2 4 Exemplo 11 A função f N em N tal que fn nmod 3 é uma função que não é injetora pois existem diferentes valores de N com a mesma imagem De fato f0 0 f3 0 f6 0 f1 1 f4 1 f9 1 f2 2 f5 2 f11 2 10 Matemática Discreta 14 Função Sobrejetora Uma função f de A em B é dita sobrejetora se e somente se para cada elemento bB existe um elemento aA tal que fa b Figura 3 Figura 4 O gráfico da figura acima à esquerda ilustra uma função de A em B Como para cada um dos três elementos do contradomínio B faz parte do conjunto imagem de f a função é sobrejetora O gráfico acima à direita ilustra uma função que não é sobrejetora pois existem elementos no conjunto B que não são imagem de nenhum elemento de A Observe que a figura à esquerda é o gráfico de uma função sobrejetora mas não injetora 15 Função Bijetora Uma função é dita bijetora se ela é injetora e sobrejetora Figura 6 O gráfico acima referese a uma função f de X a b c d em Y A B C D com fa A fb B fc C e fd D Como cada valor do domínio a função tem um valor diferente de imagem e como cada um dos elementos do contradomínio faz parte do conjunto 11 Matemática Discreta imagem da função ele é ao mesmo tempo injetora e sobrejetora ou seja bijetora Outro exemplo de função bijetora pode ser construído considerando como domínio um grupo de pessoas e como contradomínio o conjunto das impressões digitais dessas pessoas É impossível que duas pessoas compartilhem exatamente as mesmas impressões digitais Além disso todas as impressões digitais pertencem a não mais que uma pessoa 16 Função Inversa Seja f uma função bijetora de A em B A função inversa de f é a função que associa a um elemento bB um único elemento aA tal que fa b Esta função é representada por f1 Nesse caso escrevemos f1b a A figura abaixo ilustra a função inversa da função f de X a b c d em Y A B C D com fa A fb B fc C e fd D Assim temos f1A a f1B b f1C c e f1D d Figura 7 Exemplo 12 A função mod tem muitas aplicações em Matemática Discreta e Ciência da Computação Uma das mais importantes aplicações envolve a criptologia que trata do estudo das mensagens secretas Uma das formas de escrever mensagens secretas é associar uma letra do nosso alfabeto a outra letra Por exemplo cada letra do nosso alfabeto que contém 26 letras está associada a sua posição no alfabeto Por exemplo a letra A ocupa a posição 0 a letra B a posição 1 e a letra E a posição 4 de modo que Z ocupa a posição 25 12 Matemática Discreta a b c d e f g h i j k l m 0 1 2 3 4 5 6 7 8 9 10 11 12 n o p q r s t u v w x y z 13 14 15 16 17 18 19 20 21 22 23 24 25 Assim podemos construir uma mensagem secreta por meio da troca de uma letra que ocupa a posição p pela letra que ocupa a 3ª posição após a letra p Assim A função definida por fp p 3mod 26 tem a ação de cifrar a mensagem por meio da troca da letra de posição p pela letra que ocupa a posição representada pelo número p 3mod 26 Se quisermos enviar a seguinte mensagem O SPORT ESTÁ EM ALTA faríamos a seguinte mensagem codificada 17 21 18 17 20 22 7 21 22 3 7 15 3 14 22 3 R V S R U X H V X D H P D O W D Ao receber a mensagem para decodificar o receptor usaria a função inversa de f dada por f1p p3mod 26 De modo que f117 17 3mod 26 14mod 26 14 f121 21 3mod 26 18 e assim por diante de modo que a mensagem decifrada seria 14 18 15 14 17 19 4 18 19 0 4 12 0 11 19 0 O S P O R T E S T Á E M A L T A 13 Matemática Discreta Uma função injetora mas não sobrejetora não é inversível pois não temos como associar cada elemento do contradomínio com o elemento correspondente no domínio Isto ocorre porque para alguns pontos do contradomínio esta associação não existe conforme pode ser observado na figura 4 Analogamente uma função sobrejetora mas não injetora não é inversível pois pelo menos para um ponto do contradomínio teremos dois pontos correspondentes conforme pode ser observado na figura 3 17 Função Composta Considere a função g de A em B e a função f de B em C a função composta de f e g é a composição das funções f e g escrita f o g definida de A em C como f o g x f gx A figura abaixo ilustra o conceito de composição de funções f e g Exemplo 13 Sejam f e g as funções do conjunto dos inteiros no conjunto dos inteiros definidas como fx 5x 2 e gx 2x 4 Qual a composição f o g E g o f f o g x f 2x 4 52x 4 2 10x 20 2 10x 22 g o f x g5x 2 25x 2 4 10x 4 4 10x Exemplo 14 Neste exemplo recordaremos a representação de números nas bases decimal binária e hexadecimal Considere a função f definida no conjunto dos números naturais escritos na base gx fx fgx 14 Matemática Discreta decimal por fx xbase 2 e gx xbase 16 A função composta fgx transforma um número natural escrito na base dez em um número natural na base dois Assim para x 21base 10 temos fg21base 10 f15base 16 10101base 2 para x 10base 10 temos fg10 fA 1010base 2 para x 200base 10 temos fg200 fC8 11001000base 2 Exemplo 15 Se quisermos armazenar e recuperar informações de forma eficiente em termos de espaço de armazenamento e de tempo de recuperação podemos supor que os dados estejam armazenados em uma tabela e usar a chave de identificação por exemplo a matrícula de alunos CPF RG etc Quando o número de entradas identificadas pelas chaves é muito superior ao número de registros efetivamente armazenados como o cadastro de clientes de uma empresa usando o CPF como chave como podemos proceder sem que isso resulte em um espaço de armazenamento excessivamente grande Suponha que o conjunto das chaves identificáveis C k1 k2 k3 km n seja o número de entradas na tabela e que m seja possivelmente muito maior que n podemos definir uma função hash C 1 2 3 n dito função de endereçamento função de randomização ou função de hashing da seguinte forma hash k kmod n 1 Considere uma chave de identificação numérica constituída de números entre 0 e 1000 e uma tabela de armazenamento com entradas de 1 a 17 Assim a função de hash que podemos definir é hash k kmod 17 1 Abaixo apresentamos um conjunto de valores de chaves e os correspondentes endereços de armazenamento calculados pela função hash Chave k 365 634 2178 7615 730 974 2065 1222 3417 Endereço 9 6 3 17 17 6 9 16 1 A função ideal é aquela que gera para cada chave um endereço diferente isto é uma função injetiva de modo que se k1 k2 se tenha fk1 fk2 15 Matemática Discreta A função hash acima definida não é injetora de modo que pode gerar o mesmo endereço para chaves diferentes correndo assim colisões na alocação dos dados Observe que hash365 hash2065 9 hash7615 hash730 17 Para se obter o efeito de uma função injetora no cálculo do endereçamento serão utilizados métodos de tratamento de colisões que são estudados em profundidade na disciplina Estruturas de Dados Exemplo 16 Existem vários métodos de tratamento de colisões Um deles chamase endereçamento aberto Nesse caso é necessário que m n e consiste em procurar sucessivos endereços alternativos para o novo registro até que um endereço livre seja encontrado Usa se uma função hik com i variando de 0 até n1 hik kmod n fimod n onde fi pode ser fi i fi i2 etc Se tomarmos hik kmod 7 imod 7 teremos um endereçamento aberto com teste linear Para armazenar sequencialmente os registros com chaves 33 44 63 66 84 93 teremos k i hik kmod 7 imod 7 Situação 33 0 hi33 33mod 7 0mod 7 5 0mod 7 5mod 7 5 ok 44 0 hi44 44mod 7 0mod 7 2 0mod 7 2mod 7 2 ok 63 0 hi63 63mod 7 0mod 7 0 0mod 7 0mod 7 0 ok 66 0 hi66 66mod 7 0mod 7 3 0mod 7 3mod 7 3 ok 84 0 1 hi84 84mod 7 0mod 7 0 0mod 7 0mod 7 0 hi84 84mod 7 1mod 7 1 0mod 7 1mod 7 1 Colisão ok 93 0 1 2 hi93 93mod 7 0mod 7 2 0mod 7 2mod 7 2 hi93 93mod 7 1mod 7 2 1mod 7 3mod 7 3 hi93 93mod 7 2mod 7 2 2mod 7 4mod 7 4 Colisão Colisão ok Os dados serão alocados nos seguintes endereços 0 1 2 3 4 5 6 63 84 44 66 93 33 16 Matemática Discreta 18 Sequência Uma sequência é uma função definida em um subconjunto dos números naturais com imagens num subconjunto dos números reais A imagem de um número natural n é denotada por Fn Usamos a notação Fn para descrever uma sequência O termo Fn é o termo de ordem n ou termo geral da sequência definição fechada Exemplo 17 Considere a sequência cujo termo geral é Fn 1 n A lista dos termos da sequência é F1 1 F2 1 2 F3 1 3 F4 1 4 F5 1 5 Exemplo 18 a Os cinco primeiros termos da sequência definida por An 2 3n1 são A1 2 A2 5 A3 8 A4 11 A5 14 Observe que tratase de uma Progressão Aritmética PA cujo termo inicial é 2 e razão r 3 Lembrese que uma PA de termo inicial A1 e razão r tem termo geral An A1 n1r b Os cinco primeiros termos da sequência definida por An 3 2n1 são A1 3 A2 6 A3 12 A4 24 A5 48 Tratase de uma Progressão Geométrica PG cujo termo inicial é 3 e razão q 2 17 Matemática Discreta Recorde que uma PG de termo inicial A1 e razão q tem termo geral An A1qn1 Exemplo 19 Calcular os termos A1 A2 A3 e A4 das seguintes sequências An cujo termo geral Na n 1 é definido por a An n2 b An 1 10n c An 1nn d An 2n 1 e An n f An 2 3n1 Solução a 1 4 9 16 b 11 101 1001 10001 c 1 2 3 4 d 3 5 9 17 e 1 2 6 24 f 2 5 8 11 Exemplo 20 Escrever uma definição fechada ou termo geral para as seguintes sequências numéricas a 19 14 9 4 b 400 200 100 50 c 17 27 37 47 57 d 7 97 997 9997 e 2 2 2 2 2 f 1 13 15 17 19 g 1 3 6 10 15 h 1 2 5 10 17 Solução a An 24 5n n 1 18 Matemática Discreta b An 1 400 2n n 1 c An 7 10n n 1 d An 10n 3 n 1 e An 1n 1 2 n 1 f An 1 2 1 n n 1 g An 1 2 n n n 1 h An 1 n 12 n 1 Aprenda Praticando Exercícios Propostos 11 Agora é com você Apresentamos vários exercícios sobre função Você deve procurar solucionálos e caso tenha alguma dificuldade discuta com seus colegas nos chats que foram formados Além disso procure orientação dos professores executores e tutores da disciplina nos fóruns de discussão Apresentaremos as respostas dos exercícios de números pares 1 Verificar se cada uma das funções definidas abaixo é injetora sobrejetora e bijetora a f 1 2 3 a b c f 1a 2b 3c b g 1 2 3 a b c d g 1a 2b 3c c h 1 2 3 1 2 3 h 1 2 21 32 d p N N p j j2 2 e m N N mx xmod 5 f q N N qj 1 se j é ímpar qj 0 se j é par g r N 0 1 rj 1 se j é ímpar rj 0 se j é par h t 0 1 2 3 6 0 1 2 3 6 tx 3xmod 7 19 Matemática Discreta i f Z Z tal que fx 10 x j f N N tal que fx 10 x k g Z Z tal que fx x2 se x é par e fx x 12 se x é impar l f N Z tal que fx x2 se n é par e fx x 12 se x é impar 2 Determine quais das seguintes funções de R em R são bijetoras Apresente a função inversa quando existir a fx 3x 4 b fx 3x2 7 c fx x1 x22 d fx x5 1 e fx x 3 Para cada uma das funções bijetora f de R em R encontre a inversa f1 a fx 2x b fx x3 c fx 2x 43 4 Dê uma fórmula explícita para uma função do conjunto dos inteiros Z com imagens no conjunto dos inteiros Z tal que seja a injetora e não sobrejetora b sobrejetora e não injetora c injetora e sobrejetora d não injetora e não sobrejetora 5 Sejam f g N N definidas por fx x 1 e gx 3x Calcule o seguinte a f o g b g o f c f o f 20 Matemática Discreta d g o g e f o g o f f g o g o f 6 Sejam f e g as funções do conjunto dos inteiros no conjunto dos inteiros definidas como fx 5x 2 e gx 2x 4 Qual a composição de f o g e g o f 7 As funções a seguir são aplicações de R em R Forneça equações que descrevam as funções compostas g o f e f o g para cada item a fx 6x3 gx 2x b fx x gx x 8 As funções a seguir são aplicações de R em R Forneça equações que descrevam as funções compostas g o f e f o g para cada item a fx x12 gx 4x2 b fx 1 1 x x gx 1 1 x x 9 Para cada uma das seguintes funções de Hash abaixo mostre como os dados seriam inseridos na ordem dada supondo inicialmente células vazias Use tratamento de colisões o endereçamento aberto com teste linear a Hashx xmod 11 imod 11 células indexadas de 0 a 10 dados 53 13 281 743 377 20 10 796 b Hashx xmod 17 imod 17 células indexadas de 0 a 16 dados 714 631 26 373 775 906 509 2032 42 4 136 1028 10 Armazenar sequencialmente os registros com chaves 33 44 65 66 84 93 numa tabela hash de tamanho 7 com tratamento de colisões endereçamento aberto com teste quadrático dado por hik kmod 7 i2mod 7 i 0 1 2 3 4 5 6 21 Matemática Discreta Respostas dos Exercícios Propostos 11 2 a fx 3x 4 é bijetora e a função inversa é f1x 4 3 x b fx 3x2 7 não é uma função injetora pois f2 f2 5 Além disso não é sobrejetora em R De fato não existe xR tal que fx 10 c fx x1 x22 não é sobrejetora Por exemplo não existe xR tal que fx 1 Se existisse teríamos x1x22 1 ou seja x2 2 x 1 que acarreta x2 x 1 0 Esta equação não tem solução real pois b2 4ac 3 d fx x5 1 é bijetora A inversa é f1x 5 1 x e fx x não é injetora nem sobrejetora Observe que f13 f14 1 e que não existe xR tal que fx 05 4 a fx 3x 1 se x 0 fx 3x 2 se x 0 b fx x2 se x 0 fx x2 8 se x 0 c fx 2x 1 se xZ d fx x2 2 se xZ 6 f o gx f2x 4 52x 4 2 10x 20 2 10x 22 g o f x g 5x 2 25x 2 4 10x 4 4 10x 8 a gfx g 1 2 x 2 2 1 4 1 2 x x fgx f4x2 4 2 1 2 x b gfx g 1 1 x x 1 1 1 1 1 1 1 x x x x x fgx f 1 1 x x 1 1 1 1 1 1 x x x x x 22 Matemática Discreta 10 k i hk kmod 7 i2mod 7 Situação 33 0 h33 33mod 7 02mod 7 5 0mod 7 5 ok 44 0 h44 44mod 7 02mod 7 2 0mod 7 2 ok 65 0 1 h65 65mod 7 02mod 7 2 0mod 7 2 h65 65mod 7 12mod 7 2 1mod 7 3 Colisão ok 66 0 1 h66 66mod 7 02mod 7 3 0mod 7 3 h66 66mod 7 12mod 7 3 1mod 7 4 Colisão ok 84 0 h84 84mod 7 02mod 7 0 0mod 7 0 ok 93 0 1 2 h93 93mod 7 02mod 7 2 0mod 7 2 h93 93mod 7 12mod 7 2 1mod 7 3 h93 93mod 7 22mod 7 2 4mod 7 6 Colisão Colisão ok Os dados serão alocados nos seguintes endereços 0 1 2 3 4 5 6 84 44 65 66 33 93 Conclusão No primeiro capítulo deste fascículo você aprendeu sobre as funções como podem ser utilizadas em aplicações da informática e computação Em particular conheceu a função mod e a função hash que serão empregadas em aplicações da disciplina Estrutura de Dados Saiba Mais Você poderá aprender muito mais sobre funções consultando os seguintes livros e sites 23 Matemática Discreta GERSTING Judith L Fundamentos Matemáticos para a Ciência da Computação Tradução Valéria de Magalhães Iorio Rio de Janeiro LTC 2004 LIPSCHUTZ Seimour LIPSON Marc Lars Teoria e Problemas de Matemática Discreta Porto Alegre Bookman 2004 SCHEINERMAN Edward R Matemática Discreta uma introdução Tradução de Alfredo Alves de Farias São Paulo Pioneira Thomson Learning 2003 Orientações de Estudos O exemplo 12 deste capítulo versou sobre processos de transmissão de informações de forma segura como por exemplo informações de dados financeiros pela internet Nesse processo usamos uma chave de codificação Daí a informação é codificada e enviada ao receptor Ao recebêla o receptor pode decodificála usando uma chave de decodificação No sistema criptográfico com chave pública a chave de decodificação pode ser obtida da chave de decodificação O sistema criptográfico com chave pública inventado por R L Rivest A Shamir e L Adleman usa a função mod e alguns conceitos da teoria dos números inteiros Se você tem interesse no assunto leia os livros acima indicados que tratam do assunto de uma forma muito simples e visite os seguintes sites httpwwwupisbrrevistavirtualCavalcante20Teoria20dos20 NFAmeros20e20Criptografia2005UPISpdf httpwwwinfowestercomcriptografiaphp httpdomenicoderisitesuolcombrexemploshtml httpwwwpentaufrgsbrgere96segurcriptohtm 24 Matemática Discreta Capítulo 2 Recursão um método de definição 21 O que é recursão A figura acima é um triângulo equilátero No seu interior maior triângulo equilátero branco de lado L1 tem em cada um de seus lados vértices de um triângulo equilátero de lado L2 1 2 L Por sua vez cada triângulo equilátero de lado L2 tem em cada um dos seus lados vértices de triângulos equiláteros de lados L3 2 2 L e assim sucessivamente De modo que a figura mostra uma sucessão de triângulos equiláteros de lados Ln 1 2 n L onde o lado de cada triângulo é metade do lado do triângulo anterior Essa é uma figura construída por recorrência Faremos agora uma definição de recursão 22 Recursão Uma definição na qual o item que está sendo definido aparece como parte da definição é chamada definição recursiva ou indutiva Isto é o item é definido por meio de uma regra que permite calcular qualquer caso do item em função do item ou dos itens anteriores Assim uma definição recursiva é constituída de duas partes a Um passo inicial onde alguns casos simples do item que está sendo definido são dados explicitamente e b Um passo indutivo ou recursivo onde os outros casos do item que está sendo definido são dados em termos dos casos anteriores 25 Matemática Discreta Como podemos fazer uso de uma definição recursiva Podemos usar recursão para definir funções ou operações algoritmos conjuntos e sequências Lembrese Toda definição recursiva é constituída por duas partes A primeira parte é do passo inicial onde serão fornecidos os dados iniciais do item que se define A segunda parte é o passo recursivo onde é feita de forma recorrente o calcule dos demais itens em termos dos itens anteriores Exemplo 1 Uma sequência é definida recursivamente explicitandose seu primeiro valor ou seus primeiros valores e a partir daí definindose outros valores na sequência em termos dos valores iniciais A sequência 3 6 12 24 é definida recursivamente por Passo inicial A1 3 Passo Recursivo An 2 An1 para n 2 O cálculo do 5º termo se faz assim A5 2 A4 A4 2 A3 A3 2 A2 A2 2 A1 A1 3 A2 2 3 6 A3 2 6 12 A4 2 12 24 A5 2 24 48 Exemplo 2 A sequência 2 5 8 11 14 é definida recursivamente por Passo inicial A1 2 Passo recursivo An An1 3 para n 2 Para calcular recursivamente o quinto termo A5 procedemos assim 26 Matemática Discreta A5 A4 3 A4 A3 3 A3 A2 3 A2 A1 3 A1 2 A2 2 3 5 A3 5 3 8 A4 8 3 11 A5 11 3 14 Exemplo 3 A sequência de Fibonacci é definida recursivamente por Passo inicial F1 1 F2 1 Passo recursivo Fn Fn1 Fn2 n 3 é constituída dos termos 1 1 2 3 5 8 13 21 34 Calcule recursivamente F6 F6 F5 F4 F5 F4 F3 F4 F3 F2 F3 F2 F1 F2 1 F1 1 F3 1 1 2 F4 2 1 3 F5 3 2 5 F6 5 3 8 Exemplo 4 Uma função pode ser definida por recursividade Por exemplo a função MDC calcula o máximo divisor comum de dois inteiros positivos pode ser definida assim MDCx y y se x y e xmod y 0 MDCx y MDCyx se x y MDCx y MDCy xmod y caso contrário O cálculo do MDC de x 72 e y 20 se processa dessa maneira 27 Matemática Discreta MDC 72 20 MDC20 12 MDC 12 8 MDC8 4 4 Exemplo 5 Recursão em programação referese a um procedimento ou função que chama a si mesmo um módulo recursivo Para alguns tipos de problemas um módulo recursivo possibilita soluções mais simples e naturais conforme exemplo seguinte Função recursiva para multiplicação de dois inteiros Efetua a multiplicação por somas sucessivas função multiplica m n inteiro inteiro Executa multiplicação utilizando somas sucessivas Entrada dois operandos m e n e assume que n 0 Saída Retorna m n inicio multiplica se n 1 então multiplica m senão multiplica m multiplica m n 1 fim multiplica Observação Para definir um módulo recursivo precisamos identificar dois elementos o passo recursivo e a condição de parada No exemplo citado a condição de parada é satisfeita quando n 1 enquanto o passo recursivo aparece na linha multiplica m multiplica m n 1 onde aparece a função chamando ela mesma De um modo geral um módulo recursivo segue o algoritmo seguinte se condição de parada é satisfeita então Resolva senão Divida o problema num caso mais simples utilizando recursão No exemplo acima qual o valor de saída para m 5 e n 4 multiplica54 5 multiplica53 multiplica53 5 multiplica52 multiplica52 5 multiplica51 multiplica51 5 multiplica52 5 5 10 multiplica53 5 10 15 multiplica54 5 15 20 28 Matemática Discreta Exemplo 6 Forneça uma definição recursiva para cada uma das seguintes sequências a 7 97 997 9997 b sequência Tn de números triangulares T1 1 T2 3 T3 6 T4 10 n 1 n 2 n 3 n 4 c 231 é um número triangular d Quais os números triangulares entre 200 e 300 a A sequência 7 97 997 9997 tem termo geral An 10n 3 com n 1 Logo podemos escrever An1 10n1 7 de modo que 10 An1 1010n1 3 10n 30 10n 3 27 An 27 Assim An 10An1 27 para n 2 A1 7 é a definição recursiva da sequência b Observe que T1 1 T2 T1 2 T3 T2 3 logo Tn Tn1 n para n 2 A definição recursiva é T1 1 Tn Tn1 n n 2 c Uma fórmula fechada para Tn é Tn 2 2 n n para n 1 Prove Assim para 231 seja um número triangular devemos encontrar n tal que 231 2 2 n n Isto é n2 n 462 0 Resolvendo a equação temos que n 1 1 1848 1 43 2 2 Assim T21 231 d 231 253 276 e 300 Exemplo 7 A função chão fx x associa a cada número real x o maior inteiro menor ou igual a x Definimos a sequência T por T1 1 29 Matemática Discreta Tn 2 T n2 para n 2 Vamos calcular recursivamente T73 T73 2 T 732 2 T36 T36 2 T 362 2 T18 T18 2 T 182 2 T9 T9 2 T 92 2 T 4 T4 2 T 42 2 T2 T2 2 T 22 2 T1 T1 1 T2 2 1 2 T4 2 2 4 T9 2 4 8 T18 2 8 16 T36 2 16 32 T73 2 32 64 Exemplo 8 Considere o seguinte algoritmo recursivo em C que ordena os elementos de uma lista L L1 L2 L3 Lj onde j é o comprimento da lista Lista ORD lista L int J if J 1 return L A lista está ordenada imprima a lista else if J 1 Procure o índice I entre 1 e J do maior elemento tal que LI LJ Troque LI por LJ return ORDL J1 Simule a saída para a entrada L 2 7 4 3 8 5 e j 6 Solução ORD2 7 4 3 8 5 6 2 7 4 3 5 8 ORD2 7 4 3 5 8 5 2 5 4 3 7 8 ORD2 5 4 3 7 8 4 2 3 4 5 7 8 ORD2 3 4 5 7 8 3 2 3 4 5 7 8 30 Matemática Discreta ORD2 3 4 5 7 8 2 3 2 4 5 7 8 ORD2 3 4 5 7 8 1 3 2 4 5 7 8 Exemplo 9 Considere a função F definida no conjunto dos números naturais do seguinte modo F1 1 Fn n Fn1 para n 2 Vamos calcular F5 F5 5 F4 5 4 F3 5 4 3 F2 5 4 3 3 2 F1 5 4 3 2 1 5 4 3 2 1 15 Você percebeu que Fn é a soma de todos os números inteiros positivos menores ou iguais a n Assim Fn 1 n i i 1 2 3 4 5 n 31 Matemática Discreta Aprenda Praticando Exercícios Propostos 21 Chegou a sua vez Apresentamos vários exercícios sobre recursão Você deve tentar solucionálos e caso tenha alguma dificuldade discuta com seus colegas nos chats que foram formados Procure orientação dos professores executores e tutores da disciplina nos fóruns de discussão caso persistam dúvidas Apresentaremos a seguir resposta dos exercícios de numeração par 1 Nos exercícios seguintes calcular o quinto termo das sequências dadas a A1 10 An An1 10 para n 2 b A1 1 An 1 A n 1 para n 2 c B1 1 Bn Bn1 n2 para n 2 d A1 1 An An1 1 n para n 2 e P1 1 Pn n2Pn1 n1 para n 2 f D1 3 D2 5 Dn n1Dn1 n2Dn2 para n 3 2 Calcule recursivamente o sexto termo de cada uma das sequências definidas abaixo a A1 1 An An1 2 n 2 b A1 1 An 3An1 n 2 c A1 2 An An12 n 2 d A1 91 An An1 910n n 2 e A1 3 An 2An1 n 2 f A1 3 An 3An1 7 n 2 3 Forneça uma definição recursiva para a a progressão geométrica com termo inicial 7 e razão 3 32 Matemática Discreta b a progressão aritmética com termo inicial 12 e razão 5 c o fatorial n n 1 d o produto de dois números inteiros positivos e o MDC de dois números naturais a e b a b f a sequência 5 9 13 17 g a sequência 4 2 1 ½ ¼ h a sequência a 2a b 3a 2b 4a 3b i a sequência a 2a b 3a 2b 4a 3b j a sequência An 3n 1 com n 0 k a sequência An n2 com n 0 l a sequência An n2 n 1 m a sequência 1 1 1 1 n a divisão de dois inteiros positivos o a sequência 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 2 0 1 2 3 p a sequência 2 92 992 9992 4 Uma quantia de 500 unidades monetárias foi investida em uma conta remunerada a uma taxa de juro composto anual de 10 Descreva a definição recursiva para Pn a quantia na conta no início do nésimo ano 5 A sequência de números 16 144 304 768 1232 2000 é uma subsequência finita obtida da sequência de Fibonacci Descubra os termos que estão faltando 6 Que valor é computado pelo seguinte algoritmo para um valor de entrada especificado int Fint n if n 1 return 1 else return n 2Fn1 Qual o valor de saída para a entrada n 6 33 Matemática Discreta 7 Que valor é computado pelo seguinte algoritmo para um valor de entrada especificado int MDC int a int b if a 0 return b else return MDC bmod a a Qual o valor de saída para a 20 e b 72 Qual o valor de saída para a 232 e b 432 8 Que valor é computado pelo seguinte algoritmo para um valor de entrada especificado int FIB int n if n 0 return 0 else if n 1 return 1 else return FIBn1 FIBn2 Qual o valor de saída para n 6 9 A função teto gx x associa a cada real x o menor inteiro maior ou igual a x Definimos uma sequência T por a T1 1 b Tn 2 T n2 para n 2 Calcule recursivamente T85 10 Definimos a sequência FACT da seguinte forma FACT 0 1 FACT n1 n1 FACT n para n 0 Escreva os seis primeiros termos de FACT 11 Considere a relação de recorrência dada por Y0 1 Yn1 1 2 2 n n Y Y onde n 0 Essa relação produz uma sequência de valores tais que pode ser usado para aproximar 2 com qualquer grau de precisão 34 Matemática Discreta 12 Considere a sequência definida recursivamente por F1 1 e Fn 1 F n 1 1 para n 1 a Ache os valores dos seis primeiros termos dessa sequência b Observe o numerador de cada um dos termos da parte a Que sequência formam 13 Que valor é computado pelo seguinte algoritmo para um valor de entrada especificado int Qint a int b if a b return 0 else return Qab b 1 Qual o valor de saída para Q152 E para Q55 E Q58617 14 Considere o seguinte algoritmo recursivo int MAX int A int B if A 0 or B 0 return A B else return MAXA1 B1 1 Calcule o valor de retorno para a entrada A 7 e B 13 15 Considere o seguinte algoritmo recursivo que ordena os elementos de uma lista L L1 L2 L3 Lj onde j é o comprimento da lista Lista ORDlista L int J if j 1 return L A lista está ordenada Imprima a lista else if j 1 Procure o índice I entre 1 e J do maior elemento tal que LI LJ Troque LI por LJ return ORDL J1 Simule a saída para a entrada L 10 7 9 5 0 5 2 e j 7 35 Matemática Discreta 16 Considere o seguinte algoritmo recursivo int COMBint n int p if n p or p 0 return 1 else return COMBn1 p1 COMBn1 p Calcule o valor de saída para a entrada de n 6 e p 3 O que calcula COMB para quaisquer inteiros não negativos n e p 17 As figuras abaixo mostram quantos pedaços obtemos com n cortes numa pizza Dê uma definição recursiva para o número de pedaços Pn em função do número de cortes n Resp n 1 n 2 n 3 n 4 Pn 2 Pn 4 Pn 7 Pn 11 Definição recursiva P1 2 Pn Pn1 n para n 2 18 Forneça uma definição fechada e uma definição recursiva para cada uma das seguintes sequências a 9 99 999 9999 b sequência Pn de números pentagonais n 1 n 2 n 3 n 4 n 5 P1 1 P2 5 P3 12 P4 22 P5 5 36 Matemática Discreta 19 Ache uma definição fechada fórmula para as seguintes sequências definidas recursivamente por Resultados importantes que podem ser usados A soma dos termos de uma PA Sn 1 2 n a a n A soma dos termos de uma PG Sn 1 1 1 a qn q a S1 1 Sn 3Sn1 1 n 2 b S1 1 Sn 2 Sn1 n 2 c S1 1 Sn 3Sn1 n n 2 d S1 0 S2 1 Sn 1 2 2 S n S n n 2 20 Considere o seguinte algoritmo recursivo Função Fn inteiro inteiro Se n 5 então Retorne 3x Senão Retorne 2Fn1 7 Fim Se Fim Calcular F4 F5 F12 21 Considere o seguinte algoritmo recursivo Função Fn inteiro m inteiro inteiro Se n m então Retorne 3 Senão Retorne Fnm m3 m Fim Se Fim Calcular F27 F53 e F153 37 Matemática Discreta Respostas dos Exercícios Propostos 21 2 a 11 b 243 c 4294967296 d 9999991 e 64 f 523 4 P0 500 Pn 11Pn1 n 1 38 Matemática Discreta 6 187 8 8 10 1 2 6 24 120 720 12 a 1 1 2 3 5 8 5 2 3 8 13 b Formas a sequência de Fibonacci 14 MAX7 13 MAX6 12 1 MAX6 12 MAX5 11 1 MAX5 11 MAX410 1 MAX4 10 MAX39 1 MAX3 9 MAX28 1 MAX2 8 MAX1 7 1 MAX17 MAX0 6 1 MAX06 6 MAX17 7 MAX2 8 8 MAX3 9 9 MAX4 10 10 MAX5 11 11 MAX6 12 12 MAX7 13 13 A função MAX retorna o maior valor entre A e B 16 a 20 b O algoritmo retorna C 18 a Sn 10n 1 para n 1 é uma definição fechada para a sequência 9 99 999 9999 Uma definição recursiva é S1 1 Sn 10Sn1 9 para n 2 b Observe que P1 1 39 Matemática Discreta P2 5 1 4 P1 4 P3 12 1 4 7 P2 7 P4 22 1 4 7 10 P3 10 P5 35 1 4 7 10 13 P4 13 Pn Pn1 3n 2 pois a sequência 1 4 7 10 13 é uma PA de razão 3 e termo inicial 1 de modo que an 1 n13 1 3n 3 3n 2 Assim a definição recursiva é P1 1 Pn Pn1 3n 2 para n 2 A definição fechada é obtida análoga P1 1 P2 5 1 4 P3 12 1 4 7 P4 22 1 4 7 P5 35 1 4 7 10 13 Pn 1 4 7 10 13 3n2 Observe que Pn é a soma dos termos de uma PA de termo inicial 1 e razão 3 logo Pn 2 1 3 2 3 1 3 2 2 2 n n n n n n para n 1 20 F4 12 F5 2F4 7 212 7 31 F6 2F5 7 62 7 69 Conclusão Você conheceu no segundo capítulo deste fascículo o método da recursão Ele é usado na definição de funções sequências algoritmos 40 Matemática Discreta e diversos outros procedimentos computacionais Aprendeu como formular um algoritmo recursivo em aplicações da informática e computação Saiba Mais Você poderá aprender muito mais sobre recursão consultando os seguintes livros e sites GERSTING Judith L Fundamentos Matemáticos para a Ciência da Computação Tradução Valéria de Magalhães Iorio Rio de Janeiro LTC 2004 LIPSCHUTZ Seimour LIPSON Marc Lars Teoria e Problemas de Matemática Discreta Porto Alegre Bookman 2004 SCHEINERMAN Edward R Matemática Discreta uma introdução Tradução de Alfredo Alves de Farias São Paulo Pioneira Thomson Learning 2003 41 Matemática Discreta Capítulo 3 Teoremas e Técnicas de Provas 31 O que é um teorema Você lembra o Teorema de Pitágoras não é A figura acima ilustra muito bem o que esse teorema afirma A soma dos quadrados dos catetos de um triângulo retângulo é igual ao quadrado da hipotenusa Definimos um teorema como qualquer afirmação declarativa sobre matemática para a qual existe uma prova Afirmações cuja veracidade não se pode garantir são chamadas de conjecturas Os teoremas em geral são expressos sob a forma se P então Q P Q onde P e Q podem representar sentenças compostas Na afirmação se P então Q P é chamado de hipótese e Q é a conclusão Podemos escrever teoremas também na forma P Q onde se lê P se e somente se Q Recorde que P Q é equivalente a P Q Q P Por exemplo considere a afirmação Se x e y são números pares então x y é também um número par Aqui a hipótese P é x e y são números pares e a conclusão Q é a soma x y é um número par O teorema afirma que se x e y são ambos pares então x y é um número par A sentença não exclui a possibilidade de x y ser par quando x ou y não for par Na verdade se x e y não são pares então x y é par A única circunstância em que a afirmação é falsa é quando P é verdadeira x e y pares e Q é falsa x y ímpar 42 Matemática Discreta Numa afirmação P Q podemos ter a condição P verdadeira ou falsa e a condição Q verdadeira ou falsa Se a afirmação P Q é verdadeira temos o seguinte Hipótese P Conclusão Q P Q V x 2 y 4 V x y 6 possível V x 2 y 4 F x y 7 impossível F x 3 y 5 V x y 8 possível F x 2 y 5 F x y 7 possível Exemplo 1 Como podemos escrever afirmações sob a forma Se P então Q Veja os exemplos a O produto de um inteiro ímpar e um inteiro par é par Se x é um inteiro ímpar e y é um inteiro par então xy é um inteiro par b O quadrado de um inteiro ímpar é ímpar Se x um inteiro ímpar então x2 é impar c O quadrado de um inteiro primo não é primo Se x é um número primo então x2 não é primo d A soma de um inteiro par com um ímpar é par Se x é par e y é ímpar então x y é ímpar Exemplo 2 Suponha uma conjectura P Q e queremos mostrar que é falsa Devemos encontrar um contraexemplo ou seja uma situação em que P é verdadeira e Q é falsa No caso da afirmação Se x é um número primo então x é ímpar Claramente tratase de uma proposição falsa Basta escolher x 2 No exemplo acima vimos que quando queremos refutar uma conjectura um contraexemplo é suficiente Mas para provar uma afirmação em geral muitos exemplos não provam a suposição A única exceção dessa situação ocorre quando uma afirmação é feita sobre um conjunto finito Nesse caso podemos verificar se a proposição é verdadeira para todos os elementos do conjunto No caso da asserção Se um inteiro entre 2 e 13 é divisível por 4 então também é divisível por 2 ela pode ser provada verdadeira quando mostramos que é verdadeira para cada um dos números inteiros entre 2 e 13 É claro que não podemos usar o mesmo procedimento para provar que todo número inteiro divisível por 4 também é divisível por 2 43 Matemática Discreta 32 Estratégias de Provas Diversas formas podem ser usadas para provar uma asserção do tipo Se P então Q Abordaremos algumas delas 321 Prova Direta Quando você quer provar que uma proposição P Q é verdadeira devese supor que a hipótese P é verdadeira e deduzir que a conclusão Q é verdadeira Exemplo 3 Provar Se x e y são inteiros pares então x y é par Prova Suponha que x e y são inteiros pares Hipótese Isto significa que x e y são ambos divisíveis por 2 Logo existem inteiros m e n tais que x 2m e y 2n Como x y 2 m 2 n 2 m n concluímos que existe um inteiro c m n tal que x y 2c Portanto x y é divisível por 2 Logo x y é par Conclusão Exemplo 4 Se um inteiro é divisível por 6 então ele também é divisível por 3 Prova Seja x um inteiro divisível por 6 Então existe um inteiro k tal que x 6 k Pondo 6 3 2 podemos escrever x 3 2 k 3 2 k Como 2 k é um inteiro e escrevendo 2 k m temos que x 3m com m inteiro Logo x é divisível por 3 Exemplo 5 Se x é um inteiro par então y x 5 é inteiro ímpar Prova Assumimos que x é um inteiro par Então existe um inteiro n tal que x 2 n Como y x 5 então y 2 n 5 2n 4 1 2 n2 1 Pondo n 2 m temos que y 2 m 1 onde m é um inteiro Consequentemente y é um número ímpar Exemplo 6 A soma de um inteiro com o seu quadrado é um número par Pondo na forma P Q temos Se x é um número inteiro então x x2 é par 44 Matemática Discreta Prova Seja x um número inteiro Se x é par então x 2 n e x2 2 n2 4 n2 de modo que x x2 2 n 4 n2 2n 2n2 Pondo m n 2n2 temos que x x2 2m Consequentemente x x2 é par Se x é ímpar x 2n 1 para algum inteiro n Assim x x2 2n 1 2n 12 2n 1 4n2 4n 1 4n2 6n 2 22n2 3n 1 De modo que x x2 2m onde m é o inteiro 2n2 3n 1 Consequentemente x x2 é par 322 Prova Indireta Você deve lembrar que no fascículo 1 provamos algumas equivalências entre proposições Uma delas foi que P Q é logicamente equivalente a Q P A tabela seguinte mostra isso P Q P Q Q P Q P V V V F F V V F F V F F F V V F V V F F V V V V Assim uma segunda estratégia de prova tem inicio quando assumimos que a conclusão Q é falsa e então mostrar que a hipótese P é falsa A afirmação Q P é chamada de contrapositiva da afirmação P Q A prova indireta é também chamada de contrapositiva Exemplo 7 Formularemos contrapositiva Q P das seguintes proposições P Q a P Q Se x é ímpar então x2 é ímpar Q P Se x2 não é ímpar então x não é ímpar Equivalentemente podemos escrever Se x2 é par então x é par b Se n é um inteiro ímpar então 3n 5 é um inteiro par P Q Se x é inteiro ímpar então 3x 5 um inteiro é par Exemplo 8 Use a prova indireta para provar a seguinte proposição P Q Se x é um número par então x 3 é ímpar 45 Matemática Discreta A contrapositiva Q P é Se x 3 não é ímpar então x não é par Isto é se x 3 é par então x é ímpar Inicialmente suponha que x 3 é par Desse modo existe nZ tal que x 3 2n Assim x 2n 3 2n 4 1 2n2 1 Consequentemente x 2m 1 onde m n 2 é inteiro Logo x é ímpar Exemplo 9 Prove pela contrapositiva que se o quadrado de um inteiro é par então x é par A contrapositiva de n2 par n par é n ímpar n2 ímpar Assuma que n 2x 1 com x inteiro Então n2 2x 12 4x2 4x 1 22x2 2x 1 2p 1 onde p 2x2 2x é inteiro Assim n2 é ímpar 323 Prova por contradição Redução ao absurdo Suponhamos que queremos provar P Q Sabemos porém que P Q Falso Assim para provarmos P Q admitimos P e não Q e mostraremos que isso implica algo falso Veja tabelaverdade abaixo P Q P Q Q P Q F P Q Falso V V V F F F V V F F V V F F F V V F F F V F F V V F F V Exemplo 10 Se x é um número par então x 3 é ímpar Aqui x é um número par é a hipótese P e a conclusão Q é x 3 é ímpar Admitimos P e não Q Isto é suponhamos que x é um número par e que x 3 é par Então x 2n e x 3 2m para inteiros n e m Assim por um lado x 2n e por outro x 2m 3 2m 4 1 2m2 1 isto é x é par e x é ímpar o que é uma contradição Assim x 3 é impar Exemplo 11 O conjunto dos números primos é infinito Suponha que o conjunto dos números primos seja finito Então existem n primos a saber p1 p2 p3 pn 46 Matemática Discreta Considere o número x p1 p2 p3 pn 1 O número x não é divisível por nenhum dos primos p1 p2 p3 pn deixa resto 1 Logo x é mais um primo além dos n primos existente inicialmente O que é uma contradição Logo é verdadeira a proposição de que existem infinitos primos Aprenda Praticando Exercícios Propostos 31 1 Forneça um contraexemplo para a Se x é um inteiro par e y é um inteiro ímpar então o produto xy é impar b Se um número inteiro é primo então o seu quadrado é primo 2 Forneça uma prova direta das seguintes afirmações a A soma de dois inteiros ímpares é par b A soma de um inteiro ímpar e um par é ímpar c O produto de dois inteiros consecutivos é par d O quadrado de um inteiro par é divisível por 4 3 Dê uma prova direta para as seguintes proposições ou apresente um contraexemplo a O produto de quaisquer três inteiros consecutivos é par b A soma de quaisquer três inteiros consecutivos é par c O produto de um inteiro pelo seu quadrado é par d A soma de um inteiro com o seu cubo é par e Se x é um inteiro primo então x 4 é primo f Se a e b são inteiros tais que a divide b e b divide a então a b g Se x é um inteiro positivo então x2 x 41 é primo 4 Prove por contradição que a A soma de dois inteiros negativos é um inteiro negativo 47 Matemática Discreta b Se x é um número real tal que x 0 então 1 x 0 c Se a soma de dois números primos é primo então um dos primos deve ser 2 d Se x é diferente de zero então x2 é positivo e Se n é um inteiro tal que 3n 2 é par então n é par 5 Prove ou dê um contraexemplo a Se x e y são números irracionais então o produto xy é irracional b Se n é um inteiro positivo qualquer então 2n 1 é primo c Se n é um inteiro positivo então n2 79n 1601 é primo 6 Prove que o quadrado de um inteiro par é um inteiro par usando a prova direta b prova indireta c prova por contradição 7 Prove que se n é um inteiro ímpar então n3 5 é um inteiro par usando a prova direta b prova por contradição c prova pela contrapositiva 8 Prove ou dê um contraexemplo Se x e y são inteiros primos então xy 1 é primo Conclusão Ao final deste terceiro capitulo você aprendeu sobre técnicas de provas de teoremas Dentre elas destacamos a prova direta a prova pela contrapositiva prova por contradição e aprendeu a fornecer um contraexemplo de uma proposição falsa 48 Matemática Discreta Saiba Mais Caso você queira aprofundar seus conhecimentos sobre técnicas de provas consulte os seguintes livros GERSTING Judith L Fundamentos Matemáticos para a Ciência da Computação Tradução Valéria de Magalhães Iorio Rio de Janeiro LTC 2004 LIPSCHUTZ Seimour LIPSON Marc Lars Teoria e Problemas de Matemática Discreta Porto Alegre Bookman 2004 SCHEINERMAN Edward R Matemática Discreta uma introdução Tradução de Alfredo Alves de Farias São Paulo Pioneira Thomson Learning 2003 49 Matemática Discreta Capítulo 4 Princípio de Indução Finita O Princípio de Indução Finita é uma técnica frequentemente usada para demonstrar proposições sobre números inteiros positivos do tipo nN nN Pn onde Pn é uma propriedade relativa aos números inteiros positivos n Algumas vezes nos defrontamos com afirmações envolvendo os números naturais tais como 1 Pn A soma dos n primeiros números ímpares é n2 1 3 5 2n1 n2 2 Pn A soma dos n primeiros números inteiros positivos é 1 2 n n 1 2 3 4 n 1 2 n n 3 Pn 22n 1 é divisível por 3 n 1 nN Para verificar se tais afirmações são verdadeiras para qualquer inteiro n 1 não basta testar a veracidade das fórmulas substituindo valores específicos para n Por mais que as igualdades ganhem credibilidade não poderemos garantir sua validade para algum valor de n que não tenha sido testado Vejamos alguns exemplos Exemplo 1 Calculando o valor numérico da expressão Pn n2 n 17 em vários casos particulares de números inteiros positivos n os resultados encontrados são sempre números primos 50 Matemática Discreta Vejamos Para n 1 temos P1 12 1 17 17 primo Para n 2 temos P2 22 2 17 19 primo Para n 3 temos P3 9 3 17 23 primo Para n 4 temos P4 16 4 17 29 primo Podemos afirmar que para todo número inteiro positivo n Pn é um número primo É claro que não Continuando o cálculo até n 16 encontraremos sempre números primos porém para n 17 encontramos que P17 172 17 17 172 17 17 que não é primo pois é divisível por 17 Então Pn n2 n 17 não é primo para todo inteiro positivo n Exemplo 2 Ao somar os n primeiros números ímpares positivos O que encontramos Se tentarmos valores pequenos de n obtemos S1 1 12 S2 1 3 22 S3 1 3 5 32 S4 1 3 5 7 42 S5 1 3 5 7 9 52 S6 1 3 5 7 9 11 62 S7 1 3 5 7 9 11 13 72 É fácil observar que obtemos quadrados como soma Na verdade pelos exemplos a soma dos n primeiros números ímpares positivos é Sn 1 3 5 7 2n1 n2 Mas a observação é válida apenas para os sete primeiros valores de n Será que isso é válido para todos os valores de n Como podemos provar essa afirmação 51 Matemática Discreta A demonstração de que uma propriedade P relativa aos números naturais é verdadeira para todo numero natural n 1 pode ser feita pelo método que chamamos de Princípio de Indução Finita que pode ser enunciado assim Seja Pn uma proposição que queremos provar que é verdadeira para todo número natural n 1 Se provarmos que a P1 é verdadeira b Se Pk verdadeira implica que Pk1 é verdadeira k 1 então a proposição Pn é verdadeira para todo inteiro n 1 Para melhor entender o princípio de indução finita vamos utilizar a metáfora do dominó Se você tem uma longa fila de dominós em pé e você puder assegurar que 1 O primeiro dominó cairá quando se aplica uma força suficiente na peça do dominó 2 Sempre que uma peça de dominó cair a peça vizinha também cairá Então você pode concluir que todas as peças de dominó cairão Como é na prática o principio de indução finita Alguns exemplos mostrarão isso 52 Matemática Discreta Exemplo 3 Queremos provar que a proposição Pn seguinte é verdadeira para todo numero natural n 1 Pn 1 3 5 7 2n 1 n Parte 1 Devemos provar que P1 é verdadeira isto é 1 12 1 1 Parte 2 Supondo que Pn é verdadeira para n k devemos mostrar que Pn é verdadeira para n k 1 Pk verdadeira significa que 1 3 5 2k1 k2 Devemos mostrar que Pk1 é também verdadeira isto é devemos mostrar que Pk1 1 3 5 2k1 2k1 1 k12 Como 1 3 5 2k1 2k1 1 1 3 5 2k 1 2k1 1 k2 2k 1 Hipótese k12 Logo pelo Princípio de Indução Finita a fórmula vale para todo n 1 Exemplo 4 Provar que 1 2 3 4 n 1 2 n n n 1 Parte 1 Vamos provar que PI é verdadeira De fato 1 11 1 2 1 12 2 1 1 Parte 2 Suponha que Pn seja verdadeira para n k isto é que 1 2 3 4 k 1 2 k k Queremos provar que Pk1 é verdadeira isto é que 1 2 3 4 k k1 1 2 2 k k Como 1 2 3 4 k k1 1 2 3 4 k k1 53 Matemática Discreta 1 2 k k k1 Por hipótese 1 2 1 2 k k k 1 2 2 k k Logo pelo Princípio de Indução Finita a fórmula vale para todo n 1 Exemplo 5 Mostre que a proposição Pn 22n 1 é divisível por 3 n 1 nN é verdadeira Parte 1 Devemos provar que P1 é verdadeira isto é que para n 1 221 1 é divisível por 3 múltiplo de 3 De fato 221 1 22 1 4 1 3 múltiplo de 3 Parte 2 Suponha que Pn seja verdadeira para n k isto é que 22k 1 é múltiplo de 3 Então 22k 1 3m para algum inteiro m Quero provar que Pn é verdadeira para n k1 Ou seja quero provar que 22k1 1 é múltiplo de 3 Como 22k1 1 22k2 1 22k 22 1 22k 4 1 22k 3 22k 1 3 22k 22k 1 3 22k 3m 322k m múltiplo de 3 Logo pelo Princípio de Indução Finita a fórmula vale para todo n 1 Exemplo 6 Pn 2n n1 nN Parte 1 Para n 0 temse que 20 01 1 1 verdadeiro Parte 2 Devemos mostrar que Pn é verdadeira para n k1 sempre que Pn é verdadeira para n k Ou seja que 2k1 k2 sempre que 2k k 1 Ora 2k1 2 2k 2k1 hipótese 2k 2 k 2 54 Matemática Discreta Logo pelo Princípio de Indução Finita a fórmula vale para todo n 1 Exemplo 7 Seja Sn o termo geral de uma sequência tal que S1 2 e Sn 3Sn1 1 para n 1 a Escreva os cinco primeiros termos de S b Mostre por indução que Sn 3 1 2 n Solução a S1 2 S2 3S1 1 32 1 5 S3 3S2 1 35 1 14 S4 3S3 1 314 1 41 S5 3S4 1 341 1 122 b Queremos provar que Sn 3 1 2 n Parte 1 Para n 1 temos que S1 13 1 4 2 2 2 Parte 2 Suponha que Sk 3 1 2 k queremos provar que Sk1 3 1 1 2 k Ora pelo passo recursivo temos que Sk1 3Sk 1 33 1 2 k 1 1 1 1 3 3 3 3 2 3 1 1 2 2 2 k k k Exemplo 8 Prove por indução matemática que 23n 1 é divisível por 7 n 1 nN Parte 1 É claro que para n 1 231 1 8 1 7 é divisível por 7 Parte 2 Suponha que para um inteiro k 1 23k 1 seja divisível por 7 ou seja que existe inteiro m tal que 23k 1 7m Queremos provar que 23k1 1 é divisível por 7 isto é que existe inteiro p tal que 23k1 1 3p 55 Matemática Discreta De fato 23k1 1 23k 3 1 23k 23 1 23k8 1 23k 7 23k 1 Como 23k 7 é divisível por 7 e 23k 1 é divisível por 7 por hipótese então 23k1 1 é divisível por 7 tendo em vista ser soma de dois números divisíveis por 7 Assim podemos escrever 23k1 1 23k 7 7m 723k m 7p com p 23k m Exemplo 9 Uma sequência Fn é definida recursivamente assim F1 3 Fn Fn1 n para n1 a Quais os cinco primeiros termos de F b Use indução para provar que Fn 2 4 2 n n n 1 a F1 3 F2 F1 2 3 2 5 F3 F2 3 5 3 8 F4 F3 4 8 4 12 F5 F4 5 12 5 17 b Fn 2 4 2 n n n 1 Queremos provar que a fórmula dá os termos da sequência 3 5 8 12 17 Parte 1 Para n 1 temos que F1 21 1 4 6 3 2 2 a fórmula está correta Parte 2 Suponha que Fk 2 4 2 k k queremos provar que Fk1 2 1 1 4 2 k k Ora pela definição recursiva temos que Fk1 Fk k1 logo podemos escrever Fk1 2 4 2 k k k 1 56 Matemática Discreta 2 4 2 2 2 k k k 2 2 1 1 4 2 k k k 2 1 1 4 2 k k Está completa a prova por indução Aprenda Praticando Exercícios Propostos 41 1 Nos exercícios seguintes use a indução matemática para demonstrar que os resultados abaixo indicados são válidos para qualquer inteiro positivo n n 1 a 2 6 10 4n 2 2n2 b 2 4 6 2n nn 1 c 1 5 9 4n 3 n2n 1 Nossa Pedrinho Por que você está descalço com um tempo desses É que o armazém do meu pai está em balanço E como não dá pra contar tudo só com os dedos das mãos Eu venho descalço esse é o meu computador 57 Matemática Discreta d 1 3 6 nn 1 1 2 2 6 n n n e 4 10 16 6n 2 n3n 1 f 5 10 15 5n 5nn 1 2 g 12 22 32 n2 12 1 6 n n n h 13 23 33 n3 2 2 1 4 n n i 12 32 52 2n 12 2 12 1 3 n n n j 13 24 35 nn2 nn 12n 7 6 k 1 1 1 1 12 23 34 1 1 n n n n l 1 1 1 1 57 13 35 2 12 1 n n 2 1 n n m 11 22 33 nn n1 1 2 No exercício anterior escreva sob a forma de somatório o primeiro membro de cada uma das igualdades 3 Prove por meio de indução matemática que as sentenças seguintes são verdadeiras para todo inteiro n 1 a 32n 7 é divisível por 8 b 7n 2n é divisível por 5 c 13n 6n é divisível por 7 d 25n 1 5n 2 é divisível por 27 4 Considere a sequência Sn definida recursivamente por S1 1 Sn 2Sn1 1 para n 1 Mostre por indução que Sn 2n 1 para n 1 5 Seja Sn o termo geral de uma sequência tal que S1 2 e Sn 3Sn1 1 para n 1 a Escreva os cinco primeiros termos de S b Mostre por indução que Sn 3 1 2 n 58 Matemática Discreta 6 Descobrir e provar por indução uma fórmula para An 1 1 0 1 n com n 1 7 A sequência Dn é definida assim D1 2 D2 5 Dn 5Dn1 6Dn2 para n 2 a Escreva os cinco primeiros termos da sequência b Mostre por indução que Dn 2n1 3n1 para n 1 Respostas dos Exercícios Propostos 41 2 a 1 4 2 n i i c 1 4 3 n i i e 1 6 2 n i i g 2 1 n i i i 2 1 2 1 n i i k 1 1 1 n i i i m 1 n i i i 4 Para provar que Sn 2n 1 para n 1 provaremos inicialmente que a fórmula é válida para n 1 De fato S1 21 1 1 Agora suponha que a fórmula é válida para um inteiro k 11 Isto é Sk 2k 1 Queremos provar que Sk1 2k1 1 Ora pelo passo recursivo temos que Sk1 2Sk 1 2 2k 1 1 2k1 2 1 2k1 1 59 Matemática Discreta 6 A1 1 1 1 0 1 1 1 0 1 A2 1 1 0 1 1 1 0 1 1 2 0 1 A3 1 2 0 1 1 1 0 1 1 3 0 1 Conjectura An 1 n 0 1 n 1 Prova por indução Para n 1 A1 1 1 0 1 Suponha Ak 1 k 0 1 queremos provar que Ak1 1 k 1 0 1 Ora Ak1 1 k 1 0 1 Ak A 1 k 0 1 1 1 0 1 1 k 1 0 1 Está provado por indução que An 1 n 0 1 n 1 Conclusão Ao finalizar este fascículo você teve oportunidade de conhecer mais um método de prova de proposições relativas aos números naturais o princípio de indução finita Você aplicará esse método quando quiser garantir que um algoritmo ou sua implementação está correta Saiba Mais O Princípio de Indução Finita é usado também na correção de algoritmos Por exemplo queremos saber se o procedimento descrito pelo fluxograma abaixo termina para quaisquer que sejam os valores dos dados de entrada 60 Matemática Discreta O algoritmo de Euclides é usado no cálculo do Máximo Divisor Comum entre dois inteiros positivos m e n conforme figura seguinte Mostrar que o procedimento acima termina para quaisquer valores dos dados de entrada equivale a mostrar que Se no passo 2 do procedimento os valores de x e y são inteiros então os passos 2 3 e 4 serão executados apenas um número finito de vezes com os cálculos terminando no passo 4 Faremos a prova por indução sobre o valor de y Parte 1 Se y 1 então após o passo 2 r 0 Assim os passos 2 3 e 4 são executados uma única vez e o cálculo termina no passo 4 Parte 2 Suponhamos que a proposição é verdadeira para qualquer x 0 e qualquer y tal que 1 y k e mostraremos que ela é verdadeira para y k 61 Matemática Discreta Por definição de resto da divisão de números inteiros positivos teremos depois da execução do passo 2 0 r k Se r 0 a execução termina numa única vez Se r 0 com a execução dos passos 3 e 4 teremos x k e y r e a execução volta ao passo 2 Assim pela hipótese de indução os passos 2 3 e 4 serão executados um número finito p de vezes com os cálculos finalizando no passo 4 De modo que ao todo teremos p 1 execuções para y k Concluímos então que o algoritmo termina para quaisquer valores das entradas Caso você queira conhecer mais sobre o princípio de indução finita notadamente em provas de correção de algoritmos consulte as seguintes obras GERSTING Judith L Fundamentos Matemáticos para a Ciência da Computação Tradução Valéria de Magalhães Iorio Rio de Janeiro LTC 2004 LIPSCHUTZ Seimour LIPSON Marc Lars Teoria e Problemas de Matemática Discreta Porto Alegre Bookman 2004 SCHEINERMAN Edward R Matemática Discreta uma introdução Tradução de Alfredo Alves de Farias São Paulo Pioneira Thomson Learning 2003 62 Matemática Discreta Referências ABE J M Teoria Intuitiva dos Conjuntos São Paulo Makron 199 266p GERSTING J L Fundamentos Matemáticos para a Ciências da Computação 3 ed Rio de Janeiro LTC 1993 512p LIPSCHUTZ S LIPSON M L Teoria e Problemas de Matemática Discreta 2 ed Porto Alegre Bookman 2004 511p MENEZES P B Matemática Discreta para Computação e Informática Porto Alegre Editora Sagra Luzzatto 2004 272p PINTO S J Tópicos de Matemática Discreta Departamento de Matemática Universidade de Aveiro 1999122p ROSEN K H Discrete Mathematics and its Applications 4 ED New York WCBMcGrawHill 1999 654p SCHEINERMAN E R Matemática Discreta Uma Introdução São Paulo Thomson 2003 523p httpwwwinteraulacommatwebalegriafibonseqfib1htm httpwwwupisbrrevistavirtualCavalcante20Teoria20dos20 NFAmeros20e20Criptografia2005UPISpdf httpwwwinfowestercomcriptografiaphp httpdomenicoderisitesuolcombrexemploshtml httpwwwpentaufrgsbrgere96segurcriptohtm httpwwwipeagovbr 63 Matemática Discreta Considerações Finais Ao final desse fascículo você aprendeu sobre as funções o que é recursividade como os teoremas podem ser provados usando algumas técnicas de provas e conheceu o princípio de indução finita empregado quando se deseja verificar a veracidade de proposições relativas aos números inteiros Em todos esses assuntos foram abordados exemplos relacionados às áreas de Informática e Computação Espero que você utilize esses métodos matemáticos na solução de problemas de outras disciplinas do curso