Matematica discreta

Prévia do material em texto

<p>WELINGTON SANTOS</p><p>MATEMÁTICA DISCRETA</p><p>Código Logístico</p><p>59915</p><p>ISBN 978-65-5821-012-2</p><p>9 7 8 6 5 5 8 2 1 0 1 2 2</p><p>Matemática Discreta</p><p>Welington Santos</p><p>IESDE BRASIL</p><p>2021</p><p>© 2021 – IESDE BRASIL S/A.</p><p>É proibida a reprodução, mesmo parcial, por qualquer processo, sem autorização por escrito do autor e</p><p>do detentor dos direitos autorais.</p><p>Projeto de capa: IESDE BRASIL S/A. Imagem da capa: devotchkah/a_slowik/envatoelements</p><p>Todos os direitos reservados.</p><p>IESDE BRASIL S/A.</p><p>Al. Dr. Carlos de Carvalho, 1.482. CEP: 80730-200</p><p>Batel – Curitiba – PR</p><p>0800 708 88 88 – www.iesde.com.br</p><p>CIP-BRASIL. CATALOGAÇÃO NA PUBLICAÇÃO</p><p>SINDICATO NACIONAL DOS EDITORES DE LIVROS, RJ</p><p>S239m</p><p>Santos, Welington</p><p>Matemática discreta / Welington Santos. - 1. ed. - Curitiba [PR] : Iesde,</p><p>2021.</p><p>136 p. : il.</p><p>Inclui bibliografia</p><p>ISBN 978-65-5821-012-2</p><p>1. Matemática. 2. Lógica simbólica e matemática. 3. Teoria dos conjun-</p><p>tos. 4. Análise combinatória. 5. Funções (Matemática). I. Título.</p><p>21-69713 CDD: 510</p><p>CDU: 51</p><p>Welington Santos Doutor e Mestre em Matemática pela Universidade</p><p>Federal do Paraná (UFPR). Graduado em Licenciatura</p><p>em Matemática pela Universidade Estadual de Ponta</p><p>Grossa (UEPG). Participou de programa de doutoramento</p><p>sanduíche na Universidade de Maryland, EUA. Tem</p><p>experiência na área de Matemática com ênfase em</p><p>Teoria algébrica dos códigos corretores de erros, Teoria</p><p>de invariantes, Self-dual codes, Decodificação fracionária</p><p>e Teoria de matróides. Tem experiência em ensino</p><p>superior, ministrando aulas no formato presencial e a</p><p>distância.</p><p>SUMÁRIO</p><p>1 Fundamentos de lógica matemática e métodos de demonstração 9</p><p>1.1 Fundamentos de lógica matemática 9</p><p>1.2 Demonstração direta e demonstração por contraposição 20</p><p>1.3 Demonstração por contradição 24</p><p>1.4 Demonstração por absurdo 25</p><p>1.5 Demonstração por indução finita 26</p><p>2 Teoria de conjuntos 30</p><p>2.1 Noção intuitiva de conjuntos 30</p><p>2.2 Descrição e igualdade de conjuntos 31</p><p>2.3 Subconjuntos 34</p><p>2.4 Operações com conjuntos 36</p><p>3 Conjuntos numéricos 47</p><p>3.1 Conjunto dos números naturais 47</p><p>3.2 Conjunto dos números inteiros 51</p><p>3.3 Conjunto dos números racionais 54</p><p>3.4 Números reais e cardinalidade 56</p><p>3.5 Aritmética modular 58</p><p>4 Relações 61</p><p>4.1 Produto cartesiano e par ordenado 61</p><p>4.2 Conceito de relação 64</p><p>4.3 Relação inversa 68</p><p>4.4 Propriedades das relações 69</p><p>4.5 Operações e fecho de relações 72</p><p>4.6 Relação de ordem e de equivalência 74</p><p>5 Funções discretas 80</p><p>5.1 Conceito e classificação 80</p><p>5.2 Função composta e função inversa 85</p><p>5.3 Funções recursivas 89</p><p>6 Análise combinatória 92</p><p>6.1 Princípios de contagem 92</p><p>6.2 Arranjos 97</p><p>6.3 Permutações 99</p><p>6.4 Combinações 102</p><p>6.5 Binômio de Newton 106</p><p>6 Matemática Discreta</p><p>7 Funções geradoras e partição de um inteiro 112</p><p>7.1 Funções geradoras 112</p><p>7.2 Operações com funções geradoras 114</p><p>7.3 Funções geradoras exponenciais 120</p><p>7.4 Sequência de Fibonacci 123</p><p>7.5 Partição de um inteiro 124</p><p>7.6 Gráfico de uma partição 126</p><p>Gabarito 129</p><p>APRESENTAÇÃO</p><p>Esta obra oferece uma abordagem introdutória à matemática discreta,</p><p>área da matemática dedicada ao estudo de objetos que são formados</p><p>por elementos desconexos entre si, chamados de elementos discretos.</p><p>Apresentamos, com detalhes, conceitos fundamentais de teoria de</p><p>conjuntos, conjuntos numéricos e aritmética modular, diferentes problemas</p><p>de combinatória e funções úteis para a resolução de problemas de contagem.</p><p>Para tanto, no primeiro capítulo, discorremos sobre os fundamentos</p><p>básicos da lógica matemática, apresentando operações entre proposições</p><p>lógicas e suas implicações nas técnicas de demonstração para resultados</p><p>matemáticos.</p><p>A matemática é fundamentada por axiomas, lemas, corolários e</p><p>teoremas, que são validados por meio das demonstrações. Nesse sentido,</p><p>ao longo de toda a obra, apresentamos e aplicamos as principais técnicas de</p><p>demonstração (direta, contraposição, contradição, absurdo e indução) para</p><p>provar fatos bem conhecidos da matemática.</p><p>No segundo capítulo, abordamos a teoria fundamental de conjuntos, que</p><p>embasa toda a matemática discreta, apresentando as técnicas básicas de</p><p>contagem do número de elementos dos conjuntos e as principais operações</p><p>entre eles, como a intersecção, a união e a diferença.</p><p>O terceiro capítulo propõe um estudo aprofundado dos principais</p><p>conjuntos numéricos, explorando as diferentes propriedades e operações</p><p>que cada um desses conjuntos possui. Além disso, classificamos os</p><p>conjuntos numéricos em termos de sua cardinalidade, descrevendo o</p><p>conceito de conjunto enumerável e não enumerável. Diante da importância</p><p>da aritmética modular em problemas que envolvem contagem, discorremos</p><p>detalhadamente sobre essa matéria, que é observada na leitura de um CD e</p><p>na validação do número do Cadastro de Pessoa Física (CPF).</p><p>No quarto capítulo, com objetivo de introduzir o conceito de relações</p><p>entre conjuntos, nos debruçamos sobre a operação de produto cartesiano</p><p>entre conjuntos. Além disso, apresentamos as principais propriedades das</p><p>relações entre conjuntos e dois tipos especiais de relação: relação de ordem</p><p>e de equivalência, que são utilizadas na alocação de frota de empresas</p><p>aéreas, por exemplo.</p><p>No quinto capítulo, utilizamos o conceito de relações entre conjuntos</p><p>para definir funções discretas, apresentando os principais elementos que</p><p>compõem uma função: domínio, contradomínio e imagem. Exploramos</p><p>também as principais propriedades operatórias entre funções. Por fim,</p><p>apresentamos os fundamentos básicos de funções recursivas, apontando</p><p>sua aplicação para a criação de sequências numéricas, como a famosa</p><p>sequência de Fibonacci.</p><p>Vídeo</p><p>8 Matemática Discreta</p><p>No sexto capítulo, nos debruçamos sobre os princípios fundamentais de contagem:</p><p>princípio da adição, da subtração, da multiplicação e o princípio da casa dos pombos,</p><p>exibindo exemplos de aplicações para cada um deles. Além disso, o capítulo define,</p><p>classifica e ilustra diferentes problemas de contagem. Por fim, são exploradas as principais</p><p>propriedades do binômio de Newton e do teorema multinomial.</p><p>No capítulo final, abordamos a função geradora ordinária de uma sequência numérica,</p><p>identificando as relações entre operação com sequências numéricas e funções geradoras.</p><p>Exibimos, por meio de exemplos, como podemos utilizar funções geradoras para</p><p>solucionar problemas de contagem. Por fim, as ideias básicas de partição de um número</p><p>inteiro são apresentadas.</p><p>O livro também apresenta, ao final de cada capítulo, exercícios cuidadosamente</p><p>selecionados para que você exercite e explore, na prática, os temas apresentados.</p><p>Bons estudos!</p><p>Fundamentos de lógica matemática e métodos de demonstração 9</p><p>1</p><p>Fundamentos de lógica</p><p>matemática e métodos</p><p>de demonstração</p><p>Você já se perguntou como surgiram as diversas fórmulas da ma-</p><p>temática, como as famosas fórmulas de Bhaskara e de Pitágoras? Já</p><p>imaginou o porquê de elas sempre funcionarem? Isso se deve ao fato</p><p>de que essas (e muitas outras) fórmulas foram demonstradas, isto é,</p><p>alguém, utilizando um método lógico dedutivo, provou que elas são</p><p>sempre válidas.</p><p>Neste capítulo, você irá aprender os principais fundamentos da lógica</p><p>matemática, por exemplo, qual é o principal objetivo de se estudá-la, o</p><p>que é um paradoxo, o que é uma proposição e como podemos operar</p><p>com proposições. Além disso, aprenderá os principais métodos de de-</p><p>monstrações, isto é, as principais técnicas utilizadas para demonstrar que</p><p>alguma fórmula ou propriedade é verdadeira. Por fim, você realizará suas</p><p>primeiras demonstrações matemáticas.</p><p>1.1 Fundamentos de lógica matemática</p><p>Vídeo A lógica matemática teve origem no século IV antes de Cristo na Grécia Antiga,</p><p>com os trabalhos de Parmênides (530-460 a.C) e Zenão (510-470 a.C), mas ganhou</p><p>status de ciência apenas após os trabalhos do filósofo Aristóteles (384-322 a.C),</p><p>em especial na obra Organum, na qual ele estabelece os princípios dela e, por esse</p><p>motivo, é chamado de</p><p>naturais satisfaz as propriedades</p><p>a seguir:</p><p>a. Associativa da multiplicação:</p><p>(ab)c = a(bc), para todo a, b, c ∈  .</p><p>b. Comutativa da multiplicação:</p><p>ab = ba, para todo a, b ∈  .</p><p>c. Elemento neutro da multiplicação:</p><p>a · 1 = a, para todo a ∈  .</p><p>d. Distributiva da multiplicação relativamente à adição:</p><p>a(b + c) = ab + ac, para todo a, b, c ∈  .</p><p>Outra propriedade importante que os números naturais satisfazem é a proprie-</p><p>dade conhecida como tricotomiaI, enunciada a seguir.</p><p>Dados a, b ∈  , pode ocorrer exatamente uma das três alternativas seguintes:</p><p>• a = b.</p><p>• Existe p ∈  tal que a = b + p.</p><p>• Existe q ∈  com b = a + q.</p><p>Além das suas propriedades operatórias e da propriedade da tricotomia, o con-</p><p>junto dos números naturais possui outra propriedade muito importante: a orde-</p><p>nação dos números naturais, que diz que dados dois números naturais diferentes,</p><p>existe sempre um maior que o outro.</p><p>A ordenação dos números naturais é chamada de relação de ordem. A relação de</p><p>ordem no conjunto dos números naturais é definida da seguinte forma:</p><p>Conjuntos numéricos 49</p><p>Definição</p><p>Dados a, b ∈  , dizemos que a é menor que b, e escrevemos a b, existe n ∈  tal que a = b + n, em que ac = (b + n)c = bc + nc. Logo, ac > bc.</p><p>Sendo assim, se ac = bc, então a = b.</p><p>Agora é com você: prove o item b.</p><p>Desafio</p><p>50 Matemática Discreta</p><p>Existem infinitos números naturais, ou seja, a cardinalidade do conjunto dos</p><p>números naturais é infinita. Esse fato é enunciado e demonstrado no teorema</p><p>a seguir:</p><p>Teorema</p><p>O conjunto dos números naturais tem cardinalidade infinita, isto é, n() = ∞.</p><p>Demonstração</p><p>Suponhamos que  é um conjunto finito. Então, utilizando a tricotomia para</p><p>comparar todos os elementos de  , dois a dois, obtemos um natural b maior que</p><p>todos os elementos de  . Mas b + 1 também é natural e é maior que b, uma con-</p><p>tradição, provando que  tem cardinalidade infinita.</p><p>Para encerrar esta seção, demonstraremos um teorema muito importante, pois</p><p>possui várias aplicações, em especial na computação. Esse teorema é conhecido</p><p>como teorema fundamental da aritmética e indica que todo número natural pode</p><p>ser escrito como a multiplicação de números primos. Lembramos que a definição</p><p>de número primo é dada por:</p><p>Definição</p><p>Um número natural p é chamado de número primo quando p ≠ 1 e não existem a, b ∈  tais que</p><p>p = ab.</p><p>Entre os cem primeiros números naturais, temos os seguintes números primos:</p><p>2 3 5 7 11</p><p>13 17 19 23 29</p><p>31 37 41 43 47</p><p>53 59 61 67 71</p><p>73 79 83 89 97</p><p>Teorema (teorema fundamental da aritmética)</p><p>Se b ∈  , então b pode ser escrito (de maneira única) como o produto de nú-</p><p>meros primos.</p><p>Demonstração</p><p>Vamos utilizar um método de demonstração conhecido como segundo princípio</p><p>da indução. Seja b ∈  e suponha que todo número natural menor que b pode ser</p><p>escrito como o produto de fatores primos, então b é primo (nesse caso, b é trivial-</p><p>mente um produto de fatores primos) ou b = cd, com c</p><p>a(b ± c) =</p><p>ab ± ac, para todo a, b, c ∈  .</p><p>O elemento 0 ∈  é chamado de elemento absorvente da multiplicação, pois</p><p>0 · b = b · 0 = 0, para todo b ∈  . Além disso, a multiplicação de números inteiros</p><p>satisfaz a chamada regra de sinais. Vejamos: dados a, b ∈  , então a multiplicação</p><p>de a e b é tal que:</p><p>• a(-b) = -(ab).</p><p>• (-a)(-b) = (ab).</p><p>• ab = 0 se, e somente se, a = 0 ou b = 0.</p><p>A lei do corte pode ser estendida para números inteiros da seguinte forma:</p><p>Teorema (lei do corte para números inteiros)</p><p>Se 0 ≠ a ∈  , então ab = ac ↔ b = c, para todo b, c ∈  .</p><p>Outra operação fundamental entre números inteiros é a operação de divisão</p><p>inteira. Essa operação é esquematizada pelo algoritmo da divisão de Euclides:</p><p>sejam a, b ∈  com b ≠ 0, podemos escrever a da seguinte forma:</p><p>a = bq + r</p><p>em que q, r ∈  são únicos para 0 ≤ r 0 e a | b, então a ≤ b.</p><p>Demonstração</p><p>Vamos demonstrar apenas o item a. Se a | b e b | c, então existem m, n ∈  tais</p><p>que b = na e c = mb, em que c = mna, e isso significa que a | c.</p><p>Lembramos que o módulo, ou valor absoluto, de um número a ∈  é defi-</p><p>nido por:</p><p>|a| =</p><p>a se�a</p><p>a �� se�a</p><p>,</p><p>,</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>��</p><p>0</p><p>0</p><p>Agora é com você: prove os itens</p><p>b e c.</p><p>Desafio</p><p>Note que, pela definição de valor</p><p>absoluto, é sempre válido que</p><p>|a| ≥ 0 e |a| = |-a| para qualquer</p><p>a ∈  .</p><p>Importante</p><p>54 Matemática Discreta</p><p>3.3 Conjunto dos números racionais</p><p>Vídeo A fim de definir a divisão de dois números, iremos estender o conjunto dos</p><p>números inteiros para um conjunto maior, chamado de conjunto dos números racio-</p><p>nais. Note que a divisão de dois números inteiros nem sempre tem como resultado</p><p>um número inteiro, por exemplo, 3 e 2 ∈  , porém 3</p><p>2</p><p>∉  , ou seja, não é um</p><p>número inteiro. O conjunto dos números racionais é definido da seguinte maneira:</p><p>Definição</p><p>Chamamos de conjunto dos números racionais, denotado por  , o conjunto formado pelas frações</p><p>p</p><p>q , em que p, q ∈  e q ≠ 0.</p><p>Para b = p</p><p>q</p><p>∈  , chamamos p de numerador e q de denominador de b. Dizemos</p><p>que dois números racionais p</p><p>q e r</p><p>s são iguais se ps = rq. Note, por exemplo, que os</p><p>números racionais 9</p><p>4</p><p>e 18</p><p>8</p><p>são iguais.</p><p>As operações de adição, subtração, multiplicação e divisão de números racio-</p><p>nais são definidas da seguinte forma:</p><p>Definição (operações fundamentais de números racionais)</p><p>Sejam p</p><p>q e r</p><p>s ∈  , então as operações de adição, subtração, multiplicação e divisão são definidas</p><p>como:</p><p>a. p</p><p>q</p><p>r</p><p>s</p><p>ps ± rq</p><p>qs</p><p>± =</p><p>b. p</p><p>q</p><p>r</p><p>s</p><p>pr</p><p>qs</p><p>. =</p><p>c.</p><p>p</p><p>q p</p><p>qr</p><p>s</p><p>s</p><p>r</p><p>ps</p><p>qr</p><p>.= =</p><p>O conjunto dos números racionais possui alguns subconjuntos notáveis,</p><p>a saber:</p><p>•  +, chamado de conjunto dos números racionais não negativos.</p><p>•  –, chamado de conjunto dos números racionais não positivos.</p><p>• </p><p>*, chamado de conjunto dos números racionais não nulos.</p><p>Teorema</p><p>As operações de adição e subtração de números racionais satisfazem as pro-</p><p>priedades a seguir:</p><p>Note que se a ∈  ou a ∈  ,</p><p>então a ∈  .</p><p>Importante</p><p>Conjuntos numéricos 55</p><p>a. Associativa da adição e da subtração:</p><p>p</p><p>q</p><p>r</p><p>s</p><p>c</p><p>d</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � =</p><p>p</p><p>q</p><p>r</p><p>s</p><p>± c</p><p>d</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� , para todo</p><p>�p</p><p>q</p><p>r</p><p>s</p><p>c</p><p>d</p><p>, , ∈  .</p><p>b. Comutativa da adição:</p><p>p</p><p>q</p><p>r</p><p>s</p><p>ps rq</p><p>qs</p><p>� �</p><p>�</p><p>p</p><p>q</p><p>r</p><p>s</p><p>r</p><p>s</p><p>p</p><p>q</p><p>p</p><p>q</p><p>r</p><p>s</p><p>c</p><p>d</p><p>p</p><p>q</p><p>r</p><p>s</p><p>c</p><p>d</p><p>�para�todo�p</p><p>q</p><p>r</p><p>s</p><p>c</p><p>� � � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � � � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� , ,</p><p>dd</p><p>�, para todo</p><p>p</p><p>q</p><p>r</p><p>s</p><p>, � ∈  .</p><p>c. Elemento neutro da adição e da subtração: p</p><p>q</p><p>± 0 = p</p><p>q</p><p>, para todo</p><p>p</p><p>q</p><p>∈  .</p><p>d. Elemento oposto da adição:</p><p>p</p><p>q</p><p>+ p</p><p>q</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � 0 , para todo p</p><p>q</p><p>∈  .</p><p>Demonstração</p><p>Vamos demonstrar apenas o item b. Temos, por um lado, que:</p><p>p</p><p>q</p><p>r</p><p>s</p><p>ps rq</p><p>qs</p><p>sp qr</p><p>sq</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>Por outro lado, r</p><p>s</p><p>p</p><p>q</p><p>rq sp</p><p>sq</p><p>sp qr</p><p>sq</p><p>� �</p><p>�</p><p>�</p><p>� .</p><p>Sendo assim, p</p><p>q</p><p>r</p><p>s</p><p>r</p><p>s</p><p>p</p><p>q</p><p>� � � .</p><p>Teorema</p><p>A operação de multiplicação de números racionais satisfaz as propriedades</p><p>a seguir:</p><p>a. Associativa da multiplicação:</p><p>p</p><p>q</p><p>r</p><p>s</p><p>c</p><p>d</p><p>p</p><p>q</p><p>r</p><p>s</p><p>c</p><p>d</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� , para todo</p><p>p</p><p>q</p><p>r</p><p>s</p><p>c</p><p>d</p><p>, , ∈ .</p><p>b. Comutativa da multiplicação: p</p><p>q</p><p>r</p><p>s</p><p>r</p><p>s</p><p>p</p><p>q</p><p>�� � � , para todo p</p><p>q</p><p>r</p><p>s</p><p>, ∈ .</p><p>c. Elemento neutro da multiplicação: p</p><p>q</p><p>1= p</p><p>q</p><p>⋅ , para todo</p><p>p</p><p>q</p><p>∈ .</p><p>d. Elemento inverso da multiplicação: p</p><p>q</p><p>q</p><p>p</p><p>� � 1, para todo</p><p>p</p><p>q</p><p>∈ .</p><p>e. Distributiva da multiplicação relativamente à adição e à subtração:</p><p>p</p><p>q</p><p>r</p><p>s</p><p>c</p><p>d</p><p>p</p><p>q</p><p>r</p><p>s</p><p>p</p><p>q</p><p>c</p><p>d</p><p>�, para todo p</p><p>q</p><p>r</p><p>s</p><p>c</p><p>d</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � � � � �, ,  .</p><p>Demonstração</p><p>Vamos demonstrar apenas o item b. Pela definição de igualdade de números ra-</p><p>cionais, verificamos que o produto pr · sq = qs · rp; isso, é claro, pelas propriedades</p><p>de números inteiros.</p><p>Todo número racional pode ser escrito na forma decimal. Quando transforma-</p><p>mos um número racional que está na forma de fração para a notação na forma</p><p>decimal, pode ocorrer um dos seguintes casos:</p><p>Agora é com você: prove os itens</p><p>a, c e d.</p><p>Desafio</p><p>Agora é com você: prove os itens</p><p>a, c, d e e.</p><p>Desafio</p><p>56 Matemática Discreta</p><p>I. O número decimal é exato, ou seja, o número de algoritmos é finito. Por</p><p>exemplo:</p><p>a. 1</p><p>2</p><p>= 0,5.</p><p>b. 6</p><p>2</p><p>= 3,0.</p><p>II. O número decimal é uma dízima periódica, ou seja, tem infinitos algoritmos</p><p>que se repetem periodicamente. Por exemplo:</p><p>a. 13 = 0,333...</p><p>b. 2</p><p>7</p><p>= 0,285714285714...</p><p>O caminho inverso nem sempre é verdadeiro, ou seja, dado um número escrito</p><p>em sua forma decimal, nem sempre é possível escrevê-lo na forma de fração. Esses</p><p>números são chamados de números irracionais.</p><p>3.4 Números reais e cardinalidade</p><p>Vídeo Para finalizar nosso estudo sobre conjuntos numéricos, vamos definir um con-</p><p>junto numérico maior, que abrange todos os conjuntos já estudados. Esse conjunto</p><p>recebe o nome de conjunto dos números reais.</p><p>Definição</p><p>Chamamos de conjunto dos números reais, denotado por  , o conjunto formado pelos números</p><p>com representação decimal finita ou periódica (chamados de números racionais) e pelos decimais</p><p>infinitos não periódicos (chamados de números irracionais).</p><p>Observamos que, pela definição de números reais:</p><p>•  ,  ,  ⊂  .</p><p>• As operações de adição, subtração, multiplicação e divisão de números reais</p><p>satisfazem todas as propriedades operatórias já enunciadas para os demais</p><p>conjuntos numéricos.</p><p>O conjunto dos números reais possui alguns subconjuntos notáveis. A saber:</p><p>•  +, chamado de conjunto dos números reais não negativos.</p><p>•  –, chamado de conjunto dos números reais não positivos.</p><p>• </p><p>*, chamado de conjunto dos números reais não nulos.</p><p>Ao estudarmos conjuntos, definimos a cardinalidade de um conjunto finito</p><p>como seu número de elementos. Desse modo, dizemos que dois conjuntos pos-</p><p>suem a mesma cardinalidade se apresentam o mesmo número de elementos.</p><p>Vamos estender a ideia de igualdade entre cardinalidade para</p><p>conjuntos com in-</p><p>finitos elementos.</p><p>O número irracional mais fa-</p><p>moso que existe é o número</p><p>3,141592653589…, o qual</p><p>possui infinitas casas deci-</p><p>mais e é conhecido como π.</p><p>No vídeo Para que serve o Pi</p><p>e por que esse número causa</p><p>tanto fascínio?, produzido</p><p>pela BBC News Brasil, você</p><p>vai encontrar uma pequena</p><p>descrição e várias curiosida-</p><p>des sobre o número π.</p><p>Disponível em: https://www.youtube.</p><p>com/watch?v=vY6965UdcLI. Acesso</p><p>em: 5 mar. 2021.</p><p>Vídeo</p><p>https://www.youtube.com/watch?v=vY6965UdcLI</p><p>https://www.youtube.com/watch?v=vY6965UdcLI</p><p>Conjuntos numéricos 57</p><p>Definição</p><p>Dois conjuntos A e B possuem a mesma cardinalidade se, e somente se, existe uma bijeção f: A → B.</p><p>Uma bijeção f: A → B é uma função que associa cada elemento de A a um único</p><p>elemento de B e vice-versa, a cada elemento de B, um único elemento de A. Tam-</p><p>bém chamamos esse tipo de associação de associação biunívoca ou um para um.</p><p>Utilizaremos a definição anterior para classificar os conjuntos de cardinalidade</p><p>infinita em dois grupos diferentes: o grupo dos conjuntos que possuem a mesma</p><p>cardinalidade do conjunto dos números naturais e o grupo dos conjuntos que pos-</p><p>suem cardinalidade diferente.</p><p>Definição</p><p>Um conjunto que é finito ou tem a mesma cardinalidade do conjunto dos números naturais é chama-</p><p>do de conjunto enumerável ou conjunto contável.</p><p>Quando um conjunto infinito A é enumerável, indicamos a cardinalidade de A</p><p>por n(A) = ℵ0 (ℵ é alef, a primeira letra do alfabeto hebraico) e dizemos que A tem</p><p>cardinalidade alef zero.</p><p>Definição</p><p>Um conjunto que não é contável é chamado de incontável ou não enumerável.</p><p>Vejamos um exemplo:</p><p>Σxemρlo 3</p><p>Vamos mostrar que o conjunto dos números inteiros é enumerável.</p><p>Demonstração</p><p>Basta considerarmos f:  →  , dada por:</p><p>f n</p><p>n se�n�é�par</p><p>n - �� se�n�é�ímpar</p><p>� � �</p><p>�</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�</p><p>2</p><p>1</p><p>2</p><p>,</p><p>,</p><p>É fácil perceber que f é uma bijeção.</p><p>58 Matemática Discreta</p><p>3.5 Aritmética modular</p><p>Vídeo Para finalizar este capítulo, iremos introduzir a ideia de congruência modular.</p><p>A teoria de congruência modular é muito rica e extensa. Além disso, possui várias</p><p>aplicações; por exemplo, na leitura de um CD. Durante esta seção iremos estudar</p><p>os conceitos básicos de congruência modular.</p><p>Definição</p><p>Seja m ∈  um número natural, dizemos que a, b ∈  são congruentes módulo m, e escrevemos</p><p>a ≡ b mod m</p><p>se m divide a - b, ou seja, se b = a + km para um certo k ∈  .</p><p>Vejamos um exemplo:</p><p>Σxemρlo 4</p><p>a. Se m = 10, temos 32 ≡ 2 mod 10, já que 32 - 2 = 3(10).</p><p>b. Se m = 2, temos 27 ≡ -5 mod 2, já que 27 - (-5) = 16(2).</p><p>Consideremos as seguintes congruências:</p><p>• 28 ≡ 7 mod 3</p><p>• 26 ≡ -4 mod 3</p><p>Note que 28 + 26 ≡ 7 + (-4) mod 3, pois 28 + 26 - (7 + (-4)) = 51 = 17(3). Esse fato</p><p>nos indica que podemos somar congruências. Podemos resumir essa propriedade</p><p>no seguinte teorema:</p><p>Teorema</p><p>Sejam m ∈</p><p></p><p>e a, b, c, d ∈  tais que a ≡ b mod m, c ≡ d mod m. Então,</p><p>a ± c ≡ b ± d mod m.</p><p>Além disso, podemos multiplicar congruências, conforme enunciado no próxi-</p><p>mo teorema.</p><p>Teorema</p><p>Sejam m ∈</p><p></p><p>e a, b, c, d ∈  tais que a ≡ b mod m, c ≡ d mod m. Então,</p><p>ac ≡ bd mod m.</p><p>Vejamos um exemplo:</p><p>Σxemρlo 5</p><p>Sejam 2 ≡ -5 mod 7 e -5 ≡ 16 mod 7. Então, pelo teorema da multiplicação de</p><p>congruências, temos que 2(-5) ≡ (-5)(16) mod 7.</p><p>A aritmética modular está presente</p><p>em vários campos da nossa vida.</p><p>No site Campus Code, , você irá en-</p><p>tender como funciona a validação</p><p>de documentos como o CPF.</p><p>Disponível em: https://www.</p><p>campuscode.com.br/conteudos/o-</p><p>-calculo-do-digito-verificador-</p><p>-do-cpf-e-do-cnpj. Acesso em:</p><p>5 mar. 2021.</p><p>Saiba mais</p><p>Conjuntos numéricos 59</p><p>Uma outra propriedade da congruência é que para qualquer a ∈  e</p><p>m ∈ , a ≡ 0 mod m se, e somente se, a é múltiplo de m. Além disso, dado um</p><p>número natural m fixo, qualquer número inteiro pode ser descrito por uma con-</p><p>gruência com m.</p><p>Teorema</p><p>Sejam m ∈  e a ∈  , então existe um único r ∈ {0, 1, …, m - 1} tal que</p><p>a ≡ r mod m</p><p>Demonstração</p><p>Dividindo a por m, utilizando o algoritmo da divisão de Euclides, temos a = qm + r,</p><p>com r ∈ {0, 1, …, m - 1}. Logo, a - r = qm, e isso significa que a ≡ r mod m. A unicidade</p><p>de r é clara, pois o resto da divisão é único.</p><p>Σxemρlo 6</p><p>Se m = 6, temos 40 ≡ 4 mod 6, já que 40 - 4 = 6(6). Nesse caso, temos a = 40 e</p><p>r = 4 ∈ {0, 1, 2, 3, 4, 5}.</p><p>A operação de congruência módulo m é uma relação de equivalência, ou seja,</p><p>satisfaz as propriedades a seguir:</p><p>Teorema</p><p>Sejam m ∈  e a, b, c ∈  .</p><p>a. Reflexiva: a ≡ a mod m.</p><p>b. Simétrica: se a ≡ b mod m, então b ≡ a mod m.</p><p>c. Transitiva: se a ≡ b mod m e b ≡ c mod m, então a ≡ c mod m.</p><p>Demonstração</p><p>Vamos provar apenas o item c. Como m | (a - b) e m | (b - c), existem inteiros</p><p>s e t tais que b = a + sm, c = b + tm, em que c = a + (s + t)m, e isso significa que</p><p>a ≡ c mod m.</p><p>Σxemρlo 7</p><p>Se m = 6, temos 40 ≡ 4 mod 6 e 4 ≡ 22 mod 6. Sendo assim, pelo item c do teo-</p><p>rema apresentado, temos que 40 ≡ 22 mod 6.</p><p>Agora é com você: prove os itens</p><p>a e b.</p><p>Desafio</p><p>No livro Códigos correto-</p><p>res de erros, você pode</p><p>aprofundar seus conheci-</p><p>mentos sobre aritmética</p><p>modular por meio de</p><p>reflexões valiosas sobre as</p><p>propriedades operatórias</p><p>das classes residuais e apli-</p><p>cações do tema na teoria</p><p>de informação.</p><p>HEFEZ, A.; VILLELA, M. L. T. Rio de</p><p>Janeiro: IMPA, 2017.</p><p>Livro</p><p>60 Matemática Discreta</p><p>CONSIDERAÇÕES FINAIS</p><p>Neste capítulo, você aprendeu conceitos fundamentais dos principais conjun-</p><p>tos numéricos, as operações essenciais e suas propriedades operatórias. Com-</p><p>preendeu o conceito de divisibilidade e como podemos aplicá-lo para resolver</p><p>problemas matemáticos.</p><p>Por fim, você aprendeu a trabalhar com aritmética modular, presente em várias</p><p>aplicações de tecnologia e de segurança, como na criação de um código de barras ou</p><p>de um número de CPF.</p><p>ATIVIDADES</p><p>1. Mostre que se a, b ∈  , com a, b > 0 e a | b, então a ≤ b.</p><p>2. Sejam p</p><p>q</p><p>r</p><p>s</p><p>c</p><p>d</p><p>, , ∈  , mostre que p</p><p>q</p><p>r</p><p>s</p><p>c</p><p>d</p><p>p</p><p>q</p><p>r</p><p>s</p><p>c</p><p>d</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � � � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� .</p><p>3. Demonstre o seguinte teorema: sejam m ∈</p><p></p><p>e a, b, c, d ∈  , tais que a ≡ b mod m,</p><p>c ≡ d mod m, então a + c ≡ b + d mod m.</p><p>4. Mostre que a ∈  é par se, e somente se, a ≡ 0 mod 2 e que a é ímpar se,</p><p>e somente se, a ≡ 1 mod 2.</p><p>REFERÊNCIAS</p><p>GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5. ed. Boston:</p><p>Addison-Wesley, 2004.</p><p>IEZZI, G.; MURAKAMI, C. Fundamentos da matemática elementar 1: conjuntos, funções. São Paulo: Atual,</p><p>2013.</p><p>LIPSCHUTZ, S.; LIPSON, M. Matemática discreta. 2. ed. Porto Alegre: Bookman, 2004.</p><p>ROSEN, K. H. Matemática discreta e suas aplicações. 6. ed. São Paulo: McGraw-Hill, 2009.</p><p>Relações 61</p><p>4</p><p>Relações</p><p>Ao estudarmos a teoria elementar de conjuntos, aprendemos a realizar</p><p>diversas operações e comparações entre conjuntos. Porém, quando apro-</p><p>fundamos nossos estudos em matemática, geralmente também estamos</p><p>interessados em comparar os elementos dos conjuntos e não apenas os</p><p>conjuntos. Por exemplo, é mais comum comparar números em relação</p><p>à ordem e divisibilidade do que conjuntos numéricos. Em matemática, a</p><p>comparação entre elementos de um ou mais conjuntos é chamada de</p><p>relação entre os conjuntos.</p><p>No nosso dia a dia, estamos frequentemente utilizando o conceito</p><p>de relações, como quando comparamos objetos (maior, menor, igual).</p><p>Relações podem ser usadas para resolver problemas tais como determi-</p><p>nar quais pares de cidades são ligadas por linhas aéreas em uma rede.</p><p>Neste capítulo serão apresentadas as principais propriedades opera-</p><p>tórias entre relações, com destaque para dois tipos muito especiais: rela-</p><p>ção de ordem e relação de equivalência.</p><p>4.1 Produto cartesiano e par ordenado</p><p>Vídeo O principal objetivo deste capítulo é estudar relações entre elementos que per-</p><p>tencem a um ou mais conjuntos. Para isso precisamos definir uma maneira espe-</p><p>cial de organizar elementos.</p><p>Definição</p><p>Dados dois objetos quaisquer, a e b, chamamos de par ordenado um terceiro objeto (a, b). Nesse caso,</p><p>dizemos que a é a primeira coordenada</p><p>e b é a segunda coordenada de (a, b).</p><p>Observe alguns fatos importantes que decorrem da definição:</p><p>a. A ordem dos elementos importa! Ou seja, o par ordenado (a, b) é diferente do</p><p>par ordenado (b, a).</p><p>b. Não devemos confundir um par ordenado (a, b) com um conjunto {a, b}.</p><p>c. Dois pares ordenados (a, b) e (c, d) são iguais se, e somente se,</p><p>a = c e b = d.</p><p>62 Matemática Discreta</p><p>São exemplos triviais de pares ordenados:</p><p>• (1, 4), (4, 1), (100, 0).</p><p>• (carro, motocicleta), (Maria, José), (futebol, voleibol).</p><p>Durante seus estudos no ensino médio, você provavelmente aprendeu geometria</p><p>analítica e conheceu uma forma de representar pontos ordenados em um plano cha-</p><p>mado cartesiano. Para construirmos um plano cartesiano, basta que fixemos uma ori-</p><p>gem e dois eixos perpendiculares.</p><p>O plano cartesiano que conhecemos é, então, um conjunto de todos os pares or-</p><p>denados de números reais. Esse conjunto é chamado de produto cartesiano e pode</p><p>ser generalizado para o produto de conjuntos quaisquer, conforme a definição:</p><p>Definição</p><p>Dados dois conjuntos A e B, o conjunto de todos os pares ordenados (a, b), com a ∈ A e b ∈ B, é chama-</p><p>do de produto cartesiano de A e B, e é denotado por A x B. Em linguagem de conjuntos:</p><p>A x B = {(a, b) | a ∈ A e b ∈ B}</p><p>Vejamos um exemplo:</p><p>Σxemρlo 1</p><p>Sejam A � � ��,�� e B � �� � �0 1 2, , , então:</p><p>A × B � � � � � � � � � � � � �� �� � �,�� ,� ,�� ,� ,�� , ,�� ,� ,�� ,�� ,��0 1 2 0 1 2  </p><p>B × A � � � � � � � � � � � � �� �0 0 1 1 2 2,�� ,� ,�� ,� ,�� ,� ,�� ,� ,�� ,� ,��� � �  </p><p>Observamos no exemplo que, em geral, A x B ≠ B x A. Além disso, podemos pro-</p><p>var que se n(A) e n(B) são finitos, então:</p><p>n(A x B) = n(B x A) = n(A)n(B)</p><p>A ideia de produto cartesiano de dois conjuntos pode ser estendida para o pro-</p><p>duto cartesiano de um número finito de conjuntos.</p><p>Definição</p><p>Dados n conjuntos A</p><p>1</p><p>, A</p><p>2</p><p>, ..., A</p><p>n</p><p>. O conjunto de todas as n-uplas ordenados (a</p><p>1</p><p>, a</p><p>2</p><p>, ..., a</p><p>n</p><p>) com a</p><p>i</p><p>∈ A</p><p>i</p><p>é chamado de produto cartesiano de A</p><p>1</p><p>, A</p><p>2</p><p>, ..., A</p><p>n,</p><p>e é denotado por A</p><p>1</p><p>x A</p><p>2</p><p>x ... x A</p><p>n</p><p>. Em linguagem de</p><p>conjuntos:</p><p>A</p><p>1</p><p>x A</p><p>2</p><p>x ... x A</p><p>n</p><p>= {(a</p><p>1</p><p>, a</p><p>2</p><p>, ..., a</p><p>n</p><p>) | a</p><p>i</p><p>∈ A</p><p>i</p><p>}</p><p>n-upla: é uma lista ordenada,</p><p>denotada por (a</p><p>1</p><p>, a</p><p>2</p><p>, ..., a</p><p>n</p><p>),</p><p>onde a</p><p>1</p><p>, a</p><p>2</p><p>, ..., a</p><p>n</p><p>são elementos</p><p>pertencentes a um conjunto A</p><p>i.</p><p>Glossário</p><p>Observamos novamente que a ordem dos elementos de uma n-upla importa,</p><p>ou seja, (a1, ..., aj, ..., ak, ..., an) ≠ (a1, ..., ak, ..., aj, ..., an) se ak ≠ (aj). Além disso, se todos</p><p>os n conjuntos Ai são finitos, vale que:</p><p>n(A1 x A2 x ... x An) = n(A1) n(A2) ...n(An)</p><p>Relações 63</p><p>Σxemρlo 2</p><p>Sejam A ��� { , }�  , B = {0, 1, 2} e C = {00, 11}, então:</p><p>A × B × C � � � � � � � � �{ ,� ,� ,� ,� ,� ,� ,� ,� , ,� ,� ,� ,�� � � � �0 00 0 11 1 00 111 2,,� , ,� ,� ,�00 2 11� � � ��</p><p>����������������� , , , , , , , , , , ,   � � � � � � � � � �0 00 0 11 1 00 1� � � � � � 111 2 00 2 11� � � � � �, , , , , , }� � � � � </p><p>E observamos que:</p><p>(Δ, 0, 11) ∈ A x B x C, (0, Δ, 11) ∈ B x A x C, (Δ, 11, 0) ∈ A x C x B</p><p>A operação de produto cartesiano possui algumas propriedades operatórias.</p><p>Observe algumas no teorema a seguir:</p><p>Teorema</p><p>Sejam A, B e C conjuntos, então são válidas as seguintes propriedades:</p><p>a. A x B = Ø ↔ A = Ø ou B = Ø.</p><p>b. Se A ≠ Ø e B ≠ Ø, então A x B = B x A ↔ A = B.</p><p>c. Se A ⊂ B, então A x C ⊂ B x C e C x A ⊂ C x B.</p><p>d. Se A ≠ Ø, então A x B ⊂ A x C ↔ B ⊂ C.</p><p>Demonstração</p><p>Vamos provar apenas o item d. Note que se B = Ø, então o resultado é trivial.</p><p>Vamos supor que B ≠ Ø. Seja b ∈ B um elemento qualquer. Como A ≠ Ø, existe no</p><p>mínimo um elemento em A. Vamos considerar que esse elemento seja a, então</p><p>a ∈ A. Assim, se A x B ⊂ A x C, temos:</p><p>a ∈ A e b ∈ B → (a, b) ∈ A x B → (a, b) ∈ A x C → a ∈ A e b ∈ C</p><p>Onde B ⊂ C.</p><p>Suponha agora que B ⊂ C. Seja (a, b) ∈ A x B, então, pela definição de produto</p><p>cartesiano, a ∈ A e b ∈ B. Como B ⊂ C, temos que b ∈ C, ou seja, (a, b) ∈ A x C. Pro-</p><p>vando que A x B ⊂ A x C.</p><p>A operação de produto cartesiano também pode ser combinada com as demais</p><p>operações entre conjuntos (interseção, união e diferença), satisfazendo as seguin-</p><p>tes propriedades distributivas.</p><p>Teorema</p><p>Sejam A, B e C conjuntos, então são válidas as seguintes propriedades</p><p>distributivas:</p><p>a. A x (B∩C) = (A x B)∩(A x C).</p><p>b. (A∩B) x C = (A x C)∩(B x C).</p><p>c. A x (B∪C) = (A x B)∪(A x C).</p><p>d. (A∪B) x C = (A x C)∪(B x C).</p><p>a. A x (B\C) = (A x B)\(A x C).</p><p>b. (A\B) x C = (A x C)\(B x C).</p><p>Agora é com você: prove os itens</p><p>a, b e c.</p><p>Desafio</p><p>64 Matemática Discreta</p><p>Demonstração</p><p>Vamos provar apenas os itens c e e.</p><p>Para o item c, temos que:</p><p>(a, b) ∈ A x (B∪C) ↔ a ∈ A e b ∈ (B∪C)</p><p>↔ a ∈ A e (b ∈ B ou b ∈ C)</p><p>↔ (a ∈ A e b ∈ B) ou (a ∈ A e b ∈ C)</p><p>↔ (a, b) ∈ A x B ou (a, b) ∈ A x C</p><p>↔ (a, b) ∈ (A x B) U (A x C)</p><p>Provando que A x (B∪C) = (A x B)∪(A x C).</p><p>Para o item e, temos que:</p><p>(a, b) ∈ A x (B\C) ↔ a ∈ A e b ∈ (B\C)</p><p>↔ a ∈ A e (b ∈ B e b ∉ C)</p><p>↔ (a ∈ A e a ∈ A) e (b ∈ B e b ∉ C)</p><p>↔ a ∈ A e (b ∈ B e a ∈ A) e b ∉ C)</p><p>↔ (a ∈ A e b ∈ B) e (a ∈ A e b ∉ C)</p><p>↔ (a, b) ∈ A x B e (a, b) ∉ A x C</p><p>↔ (a, b) ∈ (A x B)\(A x C)</p><p>Provando que A x (B\C) = (A x B)\(A x C).</p><p>O produto cartesiano A x A é chamado de quadrado cartesiano de A, o qual é</p><p>denotado por A2, ou seja, A2 = {(x, y) | x, y ∈ A}. Denotamos por Da o conjunto cha-</p><p>mado de diagonal de A2, o qual é formado pelos pares ordenados (x, x) ∈ A2, ou seja,</p><p>Da = {(x, x) | x ∈ A}.</p><p>Por exemplo, considerando o conjunto A = {1, 2}, temos:</p><p>A2 = {(1, 1), (1, 2), (2, 1), (2, 2)} e Da = {(1, 1), (2, 2)}</p><p>Observamos também que se A é um conjunto com cardinalidade finita, digamos</p><p>n(A) = m, então n(A2) = m2 e n(Da) = m.</p><p>4.2 Conceito de relação</p><p>Vídeo Uma relação é uma ferramenta matemática que considera o vínculo de certo</p><p>elemento de um conjunto com elementos de um ou mais conjuntos. As relações</p><p>são amplamente utilizadas na ciência da computação, especialmente em bancos de</p><p>dados e códigos corretores de erros.</p><p>No artigo Modelagem do problema de alocação de frota de uma empresa aérea brasileira, dos auto-</p><p>res Daniel J. Caetano e Nicolau D. F. Gualda, publicado em 2008 no congresso anual da Associação</p><p>Nacional de Pesquisa e Ensino em Transportes (ANPET), você pode conhecer mais a respeito de</p><p>resolução de problemas com relações entre conjuntos.</p><p>Acesso em: 5 mar. 2021.</p><p>https://www.caetano.eng.br/trabalhos/getfile.php?fn=2008_XXII_ANPET_Anais.pdf</p><p>Artigo</p><p>Agora é com você: prove os itens</p><p>a, b, d e f.</p><p>Desafio</p><p>https://www.caetano.eng.br/trabalhos/getfile.php?fn=2008_XXII_ANPET_Anais.pdf</p><p>Relações 65</p><p>Notemos as seguintes relações matemáticas:</p><p>• Menor que: 1</p><p>em B.</p><p>Vejamos um exemplo:</p><p>Σxemρlo 4</p><p>Considere os conjuntos A = {4, 5, 6} e B = {a, b, c}. Qual é o domínio da relação</p><p>R3 de A em B, dada por R 4, a , 5, b3 � � � � �� �?</p><p>66 Matemática Discreta</p><p>Temos por definição que o domínio de R3 é Dom R = 4, �53� � � �.</p><p>Definição</p><p>Seja R A B � � uma relação de A em B, a imagem de R, denotada por Ran R� � ou Im R� � , é o con-</p><p>junto de todos os termos de B que são os segundos termos dos pares de R.</p><p>Vamos considerar um exemplo:</p><p>Σxemρlo 5</p><p>Considere os conjuntos A = {8, 9, 10} e B = {x, y, z}. Qual é a imagem da relação</p><p>R1</p><p>de A em B, onde R1</p><p>é dada por R = 8, x , 9, y ,� 10,� y 1 � � � � � �� �?</p><p>Temos por definição que a imagem de R1</p><p>é Im R x �y1� � � � �, , pois x e y são os se-</p><p>gundos termos dos pares (8, x), (9, y) e (10, y), ou seja, pares de R1</p><p>.</p><p>Definição</p><p>Seja R A B� � uma relação de A em B, se x ∈ A, definimos o conjunto R x� � dos R-relativos de</p><p>x como sendo o conjunto de todos os y ∈ B com a propriedade de que x está relacionado a y por R ,</p><p>ou seja:</p><p>R x = {y B | xRy}� � �</p><p>Esclarecemos a definição de R -relativos de x com o seguinte exemplo:</p><p>Σxemρlo 6</p><p>Sejam A e B dois conjuntos, onde A = {8, 9, 10}, B = {x, y, z} e R1</p><p>a relação de A</p><p>em B dada por:</p><p>R = 8,�x , 9,�y ,� 10,�y ,� 8,�z ,� 9,�z 1 � � � � � � � � � �� �</p><p>Descreva o conjunto R1 8� �.</p><p>Pela definição de conjunto dos 1-relativos de 8, tem-se R y B � R y1 18 8� � � �{ | }.</p><p>Como em R1</p><p>temos 8 nos pares (8, x) e (8, z), ou seja, o 8 está relacionado a x e z,</p><p>temos que R x �z1 8� � � � �, .</p><p>Relações 67</p><p>Definição</p><p>Seja R A B� � uma relação de A em B, se A</p><p>1</p><p>⊂ A, definimos o conjunto R A1� � dos R-relativos de</p><p>A</p><p>1</p><p>como sendo o conjunto de todos os b ∈ B com a propriedade de que x está relacionado a y por R e</p><p>x ∈ A</p><p>1</p><p>. Em símbolos:</p><p>R A b B xRy e x A1 1� �� � �{ | }</p><p>Esclareceremos a definição de -relativos de A1 com o exemplo a seguir.</p><p>Σxemρlo 7</p><p>Considere A e B dois conjuntos, onde A = {8, 9, 10} e B = {x, y, z}, sendo R1</p><p>a re-</p><p>lação entre eles dada por:</p><p>R = 8, x ,� 8, y , 9, y ,� 10,�y ,� 8, z ,� 9,�z 1 � � � �� � � � � � � � � � � �� �</p><p>Considerando A1 ⊂ A dado por A1 = {9, 10}, descreva o conjunto R A1 1� �.</p><p>Pela definição de conjunto dos R1</p><p>-relativos de um subconjunto A1 de A, tem-se</p><p>R A b B� �xR y�e�x A1 1� � � � �{ | }1 1 . Ou seja, R A = y,�z1 1� � � � .</p><p>Para finalizar esta seção, destacamos as seguintes relações triviais para um con-</p><p>junto A:</p><p>• Relação vazia: corresponde ao conjunto vazio Ø ⊂ A2.</p><p>• Relação total: corresponde ao próprio produto cartesiano A2.</p><p>• Relação diagonal: �</p><p>A</p><p>a b A b a2</p><p>2� � �� �� �, ; .</p><p>A relação diagonal também é chamada de relação identidade e é denotada por</p><p>Ia ou Ida. Observamos também que o número de elementos da relação diagonal é</p><p>igual ao número de elementos do conjunto A.</p><p>Σxemρlo 8</p><p>Considere os conjuntos A = {0, 1, 2, 3} e B = {x, y}. Determine a relação diagonal</p><p>de cada conjunto.</p><p>Pela definição, temos que �</p><p>A</p><p>a b A b a2</p><p>2� � �� �� �, ; , ou seja, a relação diagonal</p><p>do conjunto A é dada por �</p><p>A2 � � � � � � � � �� �0,�0 , 1,�1 , 2,�2 , 3,�3 , e a relação diagonal do</p><p>conjunto B é dada por �</p><p>B2 � � � � �� �x,�x , y,�y .</p><p>68 Matemática Discreta</p><p>4.3 Relação inversa</p><p>Vídeo Nesta seção aprenderemos a definir uma relação do conjunto B no conjunto A,</p><p>com base em uma relação de A em B.</p><p>Definição</p><p>Dada uma relação binária R de A em B, chamamos de relação inversa de R o conjunto</p><p>R y, x B A x, y R� � � �� � � ��1 { | }</p><p>Notamos que se R é uma relação binária de A em B, então R-1 é subconjunto de</p><p>B x A, ou seja, R-1 é uma relação binária de B em A. Além disso, temos que:</p><p>y,�x R x, y R� �� � ����1</p><p>Segue da definição que R−1 é o conjunto dos pares ordenados obtidos a partir</p><p>dos pares ordenados de R, invertendo-se a ordem dos termos em cada par. Veja-</p><p>mos um exemplo:</p><p>Σxemρlo 9</p><p>Dados A = {0, 1, 2, 3} e B = {1, 3, 5, 7} com relação R entre esses conjuntos dada</p><p>por R x �y A B� �x y� � �� � � �{ , | }1 , determine os elementos de R e de R−1, usando a</p><p>notação de conjunto.</p><p>Pela definição de R, temos que:</p><p>R= 0,�3 ,� 0,�5 ,� 0,�7 ,� 1,�3 ,� 1,�5 ,� 1,�7 ,� 2,�5 ,�� � � � � � � � � � � � � � 22,�7 ,� 3,�5 ,� 3,�7� � � � � �� �</p><p>E pela definição de relação inversa, teremos:</p><p>R = 3,�0 ,� 5,�0 ,� 7,�0 ,� 3,�1 ,� 5,�1 ,� 7,�1 ,� 5,�2-1 � � � � � � � � � � � � � � ,,� 7,�2 ,� 5,�3 ,� 7,�3� � � � � �� �</p><p>Teorema</p><p>Sejam A e B conjuntos, R uma relação de A em B e R−1 sua relação inversa, então</p><p>são válidas as seguintes propriedades:</p><p>• Dom R = Im R-1� � � �;</p><p>• Im R = Dom R-1� � � �;</p><p>• R = R-1 -1� � .</p><p>Não demonstraremos o teorema anterior, mas vamos ilustrá-lo com um exemplo.</p><p>Σxemρlo 10</p><p>Dados A = {a, b, c} e B = {1, 3}, e a relação R de A em B dada por</p><p>R = a,�1 , b,�1 ,� b,�3 ,� c,�3� � � � � � � �� �, vamos comparar o domínio e a imagem de R e de R−1.</p><p>Relações 69</p><p>Como R = a,�1 , b,�1 ,� b,�3 ,� c,�3� � � � � � � �� �, tem-se por definição que Dom R = a,�b,�c� � � �</p><p>e Im R = 1,�3� � � �. Determinando R−1, temos que R = 1,�a , 1,�b ,� 3,�b ,� 3,�c -1 � � � � � � � �� �,</p><p>onde Dom R = 1,�3-1� � � � e Im R = a,�b,�c-1� � � � .</p><p>Sendo assim, são verdadeiras as afirmações do teorema anterior.</p><p>4.4 Propriedades das relações</p><p>Vídeo Ao definirmos relações de A em B como subconjuntos do produto cartesiano A</p><p>x B, adquirimos a grande vantagem de colocar à nossa disposição todo o nosso co-</p><p>nhecimento sobre teoria de conjuntos para descrever propriedades a respeito de</p><p>relações. Entretanto, é comum encontrarmos na literatura a descrição de relação</p><p>entre dois elementos por meio de um símbolo entre eles. Por exemplo, x + y e x > y</p><p>expressam duas relações matemáticas: a relação de soma e a relação de maior que.</p><p>As relações x + y e x > y podem ser escritas na linguagem de conjuntos como:</p><p>• x y x,�y� � � ���</p><p>• x y x,�y� � � ����</p><p>Em geral, para uma dada relação R de A em B, escrevemos:</p><p>aRb a �b R� � ��,</p><p>para representar que a está relacionado com b.</p><p>Ao considerarmos um conjunto A não vazio e uma relação interna R em A, isto</p><p>é, uma relação R de A em A, podemos explorar algumas propriedades importantes.</p><p>São elas o objeto de estudo desta seção.</p><p>Definição</p><p>Dado um conjunto A não vazio, uma relação binária R em A é reflexiva se para todo a ∈ A temos que</p><p>a está relacionado com a. Em símbolos:</p><p>R é reflexiva se� �a A aRa, .</p><p>A relação de igualdade (=) é reflexiva em qualquer conjunto numérico, uma vez</p><p>que escrever, por exemplo, 2 = 2 é equivalente a escrever 2 = 2 (invertendo a ordem</p><p>dos números dois).</p><p>Nem toda relação em um conjunto é reflexiva, como podemos observar no se-</p><p>guinte exemplo.</p><p>Σxemρlo 11</p><p>Dado o conjunto A = {1, 2, 3}, considere a relação R1</p><p>em A dada por</p><p>R = 1,1 , 2,2 , 1,2 , 2,1 1 � � � � � � � �� �. Verifique que R1</p><p>não é reflexiva.</p><p>Claramente R1</p><p>não é reflexiva, pois 3 ∈ A e 3 3 1, .� R� ��</p><p>70 Matemática Discreta</p><p>Definição</p><p>Dado um conjunto A não vazio, uma relação binária R em A é simétrica se, para todo a, b ∈ A, temos</p><p>que a está relacionado com b se, e somente se, b está relacionado com a. Em símbolos:</p><p>R é simétrica se � , ,� � ��a �b A �aRb bRa</p><p>A relação de diferença (≠) é simétrica em qualquer conjunto numérico, uma vez</p><p>que escrever, por exemplo, 3 ≠ 2 é equivalente a escrever 2 ≠ 3.</p><p>Nem toda relação em um conjunto é simétrica, como podemos observar no</p><p>seguinte exemplo.</p><p>Σxemρlo 12</p><p>Dado o conjunto A = {a, b, c}, considere a relação R2 em A dada por</p><p>R = a, a , b, b , c, c , a, b , b, c , a, c 2 � � � � � � � � � � � �� � . Verifique que R2 não é simétrica.</p><p>Claramente R2 não é simétrica, pois a �c A � a �c R �e� c �a R �, , , , .� � �� � ��2 2</p><p>Definição</p><p>Dado um conjunto A não vazio, uma relação binária R em A é assimétrica se, para todo a, b ∈ A, tal</p><p>que a está relacionado com b, temos que b não está relacionado com a. Em símbolos.</p><p>R é assimétrica se� � � �� �� ��a b A se a, b R b, a R, .</p><p>Vejamos um exemplo:</p><p>Σxemρlo 13</p><p>Dado o conjunto A = {1, 2, 3}, claramente a relação R1</p><p>em A, dada por</p><p>R = 1,�2 ,�� 3,1 1 � � � ��</p><p>�, é assimétrica.</p><p>Novamente, nem toda relação em um conjunto é assimétrica, como podemos</p><p>observar no seguinte exemplo:</p><p>Σxemρlo 14</p><p>Dado o conjunto A = {a, 3, d}, considere a relação R2 em A dada por</p><p>R = a, a , d, d , d, a ,� a, d2 � � � � � � � �� �. Verifique que R2 não é assimétrica.</p><p>Relações 71</p><p>Claramente 2 não é assimétrica, pois a �d A � a �d R �e� d �a R �, , , , .� � �� � ��2 2</p><p>Definição</p><p>Dado um conjunto A não vazio, uma relação binária R em A é antissimétrica se, para todo a, b ∈ A,</p><p>tal que a está relacionado com b e b está relacionado com a, então a = b. Em símbolos:</p><p>R é antissimétrica se� � � �� � �� �a b A se a, b R e b, a R a = b,</p><p>A relação “menor que” (</p><p>o Diagrama de Hasse de uma relação de ordem parcial</p><p>formada apenas por relações reflexivas.</p><p>76 Matemática Discreta</p><p>Σxemρlo 23</p><p>Considere P A �� � �,  o poset definido sobre o conjunto A = {1, ..., n} e com ordem</p><p>parcial  formado apenas pelas relações reflexivas dos elementos, ou seja,</p><p>    :� , , , ,� �� �� � � �n n1 1 2 2 3 3</p><p>Descreva o Diagrama de Hasse de P.</p><p>Como não existem elementos a, b ∈ A distintos, tais que a ≠ b e a b , isso signi-</p><p>fica que não existirá nenhuma aresta no Diagrama de Hasse de P A �� � �,  . Sendo</p><p>assim, o Diagrama de Hasse de P A �� � �,  é:</p><p>1 2 n – 1 n…</p><p>O poset do exemplo anterior é muito importante e recebe o nome de poset de</p><p>Hamming ou poset anticadeia. Sua importância se dá pelo fato de estar relacionado</p><p>com a famosa métrica de Hamming, a qual é utilizada para identificar erros em</p><p>teoria de informação.</p><p>Definição</p><p>Dado um conjunto A não vazio, uma relação binária R em A é dita relação de equivalência em A se for</p><p>reflexiva, simétrica e transitiva.</p><p>O exemplo mais óbvio de relação de equivalência é a igualdade em um conjunto</p><p>numérico.</p><p>Σxemρlo 24</p><p>Verifique que a igualdade no conjunto dos números reais  é uma relação de</p><p>equivalência.</p><p>Para verificar que a igualdade é uma relação de equivalência, analisamos suas</p><p>propriedades:</p><p>• É reflexiva: ∀ a ∈ , a = a.</p><p>• É simétrica: ∀ a, b ∈ , a = b → b = a.</p><p>• É transitiva: ∀ a, b, c ∈ , a = b e b = c → a = c.</p><p>Portanto, é uma relação de equivalência.</p><p>Para saber mais sobre a</p><p>identificação de erros na</p><p>teoria de informação, re-</p><p>comendamos o Capítulo 1</p><p>do livro Códigos corretores</p><p>de erros. Nele, é abordado</p><p>o conceito e equivalên-</p><p>cia de códigos, além da</p><p>métrica de Hamming. Uma</p><p>excelente complementa-</p><p>ção para seus estudos.</p><p>HEFEZ, A.; VILLELA, M. L. Rio de</p><p>Janeiro: IMPA, 2017.</p><p>Saiba mais</p><p>Relações 77</p><p>Observe que existe uma pequena diferença entre relação de ordem e relação</p><p>de equivalência: Toda relação de ordem é antissimétrica e toda relação de equi-</p><p>valência é simétrica.</p><p>Vejamos mais um exemplo de relação de equivalência:</p><p>Σxemρlo 25</p><p>Verifique que se a, b ∈ , a relação a ≡ b mod 2 é uma relação de equivalência</p><p>em .</p><p>Para verificarmos que é relação de equivalência, vamos mostrar que é uma re-</p><p>lação reflexiva, simétrica e transitiva. De fato,</p><p>• É reflexiva:</p><p>Para cada a ∈ , temos:</p><p>a – a = 0 = 2 · 0 → a ≡ a mod 2</p><p>• É simétrica:</p><p>Se a, b ∈ , tais que a ≡ b mod 2, então existe k ∈ , tal que:</p><p>a – b = 2k → b – a = 2(–k) → b ≡ a mod 2</p><p>• É transitiva:</p><p>Se a, b, c ∈ , tais que a ≡ b mod 2 e b ≡ c mod 2, então existe k1, k2 ∈ , tais que</p><p>b – a = 2k1 e c – b = 2k2. Adicionando essas duas igualdades, temos:</p><p>(c – b) + (b – a) = 2k1 + 2k2 → c – a = 2(k1 + k2) →</p><p>c – a = 2k, com k = k1 + k2 ∈ </p><p>Portanto, a ≡ c mod 2.</p><p>Logo, a relação a ≡ b mod 2 é de equivalência.</p><p>Há outra maneira de pensarmos sobre as relações de equivalência, mas vamos</p><p>precisar de algumas definições para entender essa perspectiva alternativa.</p><p>Definição</p><p>Dado que R é uma relação de equivalência em um conjunto A, então, a classe de equivalência de um</p><p>elemento x ∈ A é o conjunto de todos os elementos em A relacionados a x por R. A classe de equiva-</p><p>lência de x é denotada por [x]. Assim, em símbolos:</p><p>x x� �xRy�� �� � { | } .</p><p>78 Matemática Discreta</p><p>Vejamos um exemplo:</p><p>Σxemρlo 26</p><p>Seja A =  e R x �y�mod�� �� �5 � uma relação de A. Determine a classe de equiva-</p><p>lência [7] e a compare com as classes [12] e [17].</p><p>Nesse caso, temos que [7] é o conjunto de todos os elementos em  que estão</p><p>relacionados a 7 por R x �y�mod�� �� �� �5 , assim:</p><p>[7] = {..., -3, 2, 7, 12, 17, 22, ...}.</p><p>Ao comparar [7] com as classes [12] e [17], observamos que [7] = [12] = [17].</p><p>Definição</p><p>Uma partição de um conjunto A é uma coleção de subconjuntos disjuntos e não vazios A</p><p>1</p><p>, A</p><p>2</p><p>, ..., A</p><p>n</p><p>cuja</p><p>união é A.</p><p>Vejamos um exemplo:</p><p>Σxemρlo 27</p><p>Considere o conjunto A = {a, b, c, d, e}. Vamos encontrar uma partição de A.</p><p>Existe mais de uma partição possível para A. Podemos considerar, por exem-</p><p>plo, a partição formada pelos conjuntos A1 = {a, c}, A2 = {b, e}, A3 = {d}. Existe uma</p><p>correspondência entre relações de equivalência em A e partições de A. Podemos</p><p>simplificar essa correspondência no seguinte teorema.</p><p>Teorema</p><p>As classes de equivalência de uma relação de equivalência em um conjunto A</p><p>formam uma partição de A.</p><p>Vejamos um exemplo do teorema:</p><p>Σxemρlo 28</p><p>Considere o conjunto dos números inteiros ℤ e a relação de congruência mó-</p><p>dulo 5 (≡ mod 5). Determine a quantidade e quais são as classes de equivalência</p><p>dessa relação.</p><p>Relações 79</p><p>Essa relação particiona o conjunto dos números inteiros em cinco classes de</p><p>equivalência, a saber:</p><p>• [0] = {..., -5, 0, 5, 10, 15, 20, ...}</p><p>• [1] = {..., -4, 1, 6, 11, 16, 21, ...}</p><p>• [2] = {..., -3, 2, 7, 12, 17, 22, ...}</p><p>• [3] = {..., -2, 3, 8, 13, 18, 23, ...}</p><p>• [4] = {..., -1, 4, 9, 14, 19, 24, ...}</p><p>CONSIDERAÇÕES FINAIS</p><p>Neste capítulo, você aprendeu a realizar o produto cartesiano entre conjuntos</p><p>e viu que essa operação pode ser utilizada para definir relações entres conjun-</p><p>tos que, por sua vez, podem ser empregadas para solucionar problemas práticos,</p><p>como na malha aérea de uma empresa.</p><p>Além disso, estudamos que é possível realizar operações entre relações e como</p><p>definir a relação inversa de uma dada relação. E, por fim, nos debruçamos sobre dois</p><p>tipos especiais de relações, as de ordem – que podem ser encontradas em aplicações</p><p>de teoria da informação – e as de equivalência – aprendendo a relacioná-las com par-</p><p>tição de um conjunto.</p><p>ATIVIDADES</p><p>1. Sejam A, B e C conjuntos. Prove que:</p><p>Se A ⊂ B, então A x C ⊂ B x C.</p><p>2. Sejam A, B e C conjuntos. Prove que:</p><p>(A∩B) x C = (A x C)∩(B x C).</p><p>3. Sejam A = {x ∈ ℕ | x ≤ 7} e R a relação em A dada por:</p><p>R { x �y A A�|x y 9� � �� � � �, }</p><p>Determine os conjuntos R,�R ,�Dom R ,�Dom R ,�Im R ,�Im R-1 -1 -1� � � � � � � � .</p><p>4. Seja m ∈ N, m > 1. Mostre que R { x,�y |x y�mod�m� � � � } é uma relação de</p><p>equivalência em Z.</p><p>REFERÊNCIAS</p><p>GERSTING, J. L. Fundamentos matemáticos para Ciência da Computação. 4. ed. São Paulo: LTC, 2001.</p><p>GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5. ed. Boston: Addison-</p><p>Wesley, 2004.</p><p>IEℤℤI, G.; MURAKAMI, C. Fundamentos da matemática elementar 1: conjuntos, funções. São Paulo: Atual,</p><p>2013.</p><p>ROSEN, K. H. Matemática discreta e suas aplicações. 6. ed. São Paulo: McGraw-Hill, 2009.</p><p>80 Matemática Discreta</p><p>5</p><p>Funções discretas</p><p>O objetivo primordial de estudar matemática é aprender técnicas para</p><p>conseguir descrever objetos da natureza por meio de ferramentas mate-</p><p>máticas, a fim de solucionar problemas e desenvolver novas tecnologias. A</p><p>principal ferramenta é o conceito de função, o qual nos ajuda a agrupar e</p><p>descrever elementos por meio de uma regra.</p><p>Neste capítulo, vamos apresentar as principais propriedades de fun-</p><p>ções. Você aprenderá a definir uma função entre dois conjuntos A e B</p><p>por meio de uma relação entre esses conjuntos e a classificá-la em inje-</p><p>tora, sobrejetora e bijetora. Além disso, aprenderá a realizar uma opera-</p><p>ção muito importante entre funções: a composição. Iremos ainda utilizar</p><p>funções para contar o número de elementos em um conjunto e, por fim,</p><p>definiremos funções de maneira recursiva.</p><p>5.1 Conceito e classificação</p><p>Vídeo Funções como f(x) = x2 + x – 1 e g(x) = x · tg–1(x) são certamente bastante fami-</p><p>liares nas disciplinas de cálculo. Em matemática discreta, usaremos funções para</p><p>contagem, mas de uma forma que pode não ser familiar. Em vez de utilizarmos fun-</p><p>ções que mapeiam um número real para outro, usaremos funções que relacionam</p><p>elementos de conjuntos finitos.</p><p>Para contar com precisão, precisamos definir cuidadosamente a noção de</p><p>função.</p><p>Definição</p><p>Uma função f entre os conjuntos X e Y é uma regra que associa a cada elemento x ∈ X um único ele-</p><p>mento de Y, denotado por f(x) ∈ Y.</p><p>É comum representarmos uma função de um conjunto X em um conjunto Y por:</p><p>f: X → Y</p><p>x  y = f(x)</p><p>Uma função f: X → Y</p><p>também pode ser considerada uma relação entre dois con-</p><p>juntos, X e Y, que relaciona cada elemento de X a um elemento de Y. O conjunto X é</p><p>chamado de domínio da função f, e Y é chamado de contradomínio.</p><p>Funções discretas 81</p><p>Aqui está um exemplo ilustrativo de uma função:</p><p>Domínio Contradomínio</p><p>a</p><p>b</p><p>c</p><p>d</p><p>e</p><p>X f Y</p><p>1</p><p>2</p><p>3</p><p>4</p><p>5</p><p>Notamos que f: X → Y, onde o conjunto X = {a, b, c, d, e} é o domínio e o contra-</p><p>domínio é o conjunto Y = {1, 2, 3, 4, 5}. Os elementos relacionados são unidos por</p><p>uma seta e indicam que f mapeia:</p><p>• a para 1.</p><p>• b para 3.</p><p>• c para 4.</p><p>• d para 3.</p><p>• e para 5.</p><p>De modo equivalente, f(a) = 1, f(b) = 3, f(c) = 4, f(d) = 3 e f(e) = 5.</p><p>É importante lembrarmos que para uma relação de um conjunto X em um con-</p><p>junto Y definir uma função de X em Y, é necessário que cada elemento de X esteja</p><p>relacionado com um, e apenas um, elemento de Y. Observe, por exemplo, as rela-</p><p>ções a seguir:</p><p>a</p><p>b</p><p>c</p><p>d</p><p>e</p><p>X Y</p><p>1</p><p>2</p><p>3</p><p>4</p><p>5</p><p>a</p><p>b</p><p>c</p><p>d</p><p>e</p><p>X Y</p><p>1</p><p>2</p><p>3</p><p>4</p><p>5</p><p>As relações apresentadas não são funções; a primeira, porque a está relaciona-</p><p>do com dois elementos do contradomínio (1 e 2), e a segunda, porque b e d não</p><p>estão relacionados com nenhum elemento do contradomínio.</p><p>Definição</p><p>Sejam X e Y conjuntos, A ⊂ X e f: X → Y uma função, a imagem direta de A é o conjunto</p><p>f(A) = {f(x) ∈ Y | x ∈ A}</p><p>Observe que dada uma função f: X → Y, a imagem direta de um conjunto</p><p>A ⊂ X é formada pelos elementos y do contradomínio Y, tais que existe um x ∈ A</p><p>que está relacionado com y. Além disso, a imagem direta de A é um subconjunto</p><p>do contradomínio.</p><p>82 Matemática Discreta</p><p>Σxemρlo 1</p><p>Seja uma função f, com domínio X = {a, b, c, d, e} e contradomínio Y = {1, 2, 3, 4, 5},</p><p>onde f(a) = 1, f(b) = 3, f(c) = 4, f(d) = 3 e f(e) = 5. Determine a imagem direta dos sub-</p><p>conjuntos A1 = {a, b} e A2 = {c, d, e}.</p><p>Se A1 = {a, b}, temos que f(A1) = {1, 3}. Analogamente, se A2 = {c, d, e}, temos que</p><p>f(A2) = {3, 4, 5}.</p><p>Teorema</p><p>Sejam A, B ⊂ X e f: X → Y uma função, a imagem direta é tal que:</p><p>a. f(A∪B) = f(A)∪f(B)</p><p>b. f(A∩B) ⊂ f(A)∩f(B)</p><p>Demonstração</p><p>Vamos provar apenas o item a. Se y ∈ f(A∪B), então, existe x ∈ A∪B, tal que</p><p>f(x) = y. Se x ∈ A, temos que y ∈ f(A). Se, porém, x ∈ B, temos que y ∈ f(B). Em qual-</p><p>quer caso, y ∈ f(A)∪f(B). Logo, f(A∪B) ⊂ f(A)∪f(B).</p><p>Reciprocamente, seja z ∈ f(A)∪f(B), então z ∈ f(A) ou z ∈ f(B). No primeiro caso,</p><p>existe x ∈ A, tal que z = f(x). No segundo, existe y ∈ B, tal que z = f(y). De qualquer</p><p>modo, existe w ∈ A∪B, tal que z = f(w). Assim, z ∈ f(A∪B), isto é, f(A)∪f(B) ⊂ f(A∪B).</p><p>Essas duas inclusões mostram que f(A∪B) = f(A)∪f(B).</p><p>Definição</p><p>Sejam X, Y conjuntos, B ⊂ Y e f: X → Y uma função, a imagem inversa de B é o conjunto</p><p>f–1(B) = {x ∈ X | f(x) ∈ B} ⊂ X</p><p>Observe que dada uma função f: X → Y, a imagem inversa de um conjunto B ⊂ Y</p><p>é formada pelos elementos x do domínio X, tais que existe um y ∈ B que está rela-</p><p>cionado com x. Além disso, a imagem inversa de B é um subconjunto do domínio.</p><p>Σxemρlo 2</p><p>Seja uma função f, com domínio X = {a, b, c, d, e} e contradomínio Y = {7, 8, 9, 10,</p><p>11}, onde f(a) = 7, f(b) = 8, f(c) = 10, f(d) = 9 e f(e) = 11. Determine a imagem inversa</p><p>dos conjuntos B1 = {7, 8} e B2 = {7, 9, 10, 11}.</p><p>Se B1 = {7, 8}, temos que f–1(B1) = {a, b}. Analogamente, se B2 = {7, 9, 10, 11}, temos</p><p>que f–1(B2) = {a, c, d, e}.</p><p>Agora é com você: prove o item b.</p><p>Desafio</p><p>Funções discretas 83</p><p>Teorema</p><p>Sejam A, B ⊂ Y e f: X → Y uma função, a imagem inversa é tal que:</p><p>a. f–1(A∪B) = f–1(A)∪f–1(B)</p><p>b. f–1(A∩B) = f–1(A)∩f–1(B)</p><p>Demonstração</p><p>Vamos provar apenas o item b. Temos que</p><p>x ∈ f–1(A∩B) ↔ f(x) ∈ A∩B</p><p>↔ f(x) ∈ A e f(x) ∈ B</p><p>↔ x ∈ f–1(A) e x ∈ f–1(B)</p><p>↔ x ∈ f–1(A)∩f–1(B)</p><p>Portanto, f–1(A∩B) = f–1(A)∩f–1(B).</p><p>Definição</p><p>Seja f: X → Y uma função, dizemos que f é injetora se f(x</p><p>1</p><p>) ≠ f(x</p><p>2</p><p>), sempre que x</p><p>1</p><p>≠</p><p>x</p><p>2</p><p>para x</p><p>1</p><p>, x</p><p>2</p><p>∈</p><p>X.</p><p>Note que dizer que uma função f: X → Y é injetora equivale a dizer que, se</p><p>f(x1) = f(x2), então x1 = x2. Vejamos um exemplo:</p><p>Σxemρlo 3</p><p>Sejam f: ℕ → ℕ dada por f(x) = 2x e g: ℤ → ℕ dada por g(x) = x2, verifique que f é</p><p>injetora e que g não é injetora.</p><p>Suponhamos que existem x1, x2 ∈ ℕ tais que f(x1) = f(x2). Vamos mostrar que</p><p>x1 = x2. De fato, se f(x1) = f(x2), então 2x1 = 2x2, onde x1 = x2 e, assim, f é injetora. É</p><p>fácil ver que g não é injetora pela contrapositiva: se x1 ≠ x2, então f(x1) ≠ f(x2), mas se</p><p>x1 = -2 e x2 = 2 ∈ ℤ, temos que g(-2) = g(2) = 4.</p><p>Funções injetoras são especiais, pois transformam f(A∩B) ⊂ f(A)∩f(B) em uma</p><p>igualdade. Mais precisamente, temos o seguinte teorema.</p><p>Teorema</p><p>Seja A, B ⊂ X e f: X → Y uma função injetora, então:</p><p>f(A∩B) = f(A)∩f(B)</p><p>Demonstração</p><p>Dado y ∈ f(A)∩f(B), temos y ∈ f(A) e y ∈ f(B). Logo, existem x1 ∈ A e x2 ∈ B, com</p><p>y = f(x1) e y = f(x2). Como f é injetora, deve ser x1 = x2 e, portanto, x1 ∈ A∩B. Segue-se</p><p>que y = f(x1) pertence a f(A∩B), o que mostra f(A)∩f(B) ⊂ f(A∩B). Como a inclusão</p><p>oposta é sempre verdadeira, concluímos que f(A∩B) = f(A)∩f(B).</p><p>84 Matemática Discreta</p><p>Definição</p><p>Definimos f: X → Y uma função sobrejetora (ou sobrejetiva) se, para todo y ∈ Y, existe x ∈ X tal que</p><p>f(x) = y.</p><p>Note que dizer que uma função f: X → Y é sobrejetora equivale a dizer que todo</p><p>elemento de Y está relacionado com, no mínimo, um elemento de X.</p><p>Σxemρlo 4</p><p>Sejam f: ℤ → ℤ dada por f(x) = x + 1 e g: ℤ → ℤ dada por g(x) = x2, vamos verificar</p><p>que f é sobrejetora e que g não é sobrejetora.</p><p>De fato, para todo y ∈ ℤ, basta escolhermos x = y - 1 para termos</p><p>f(x) = f(y - 1) = (y - 1) + 1 = y</p><p>Portanto, f é sobrejetora.</p><p>Escolhendo y = -1 ∈ ℤ, não existe x ∈ ℤ, tal que g(x) = y, ou seja, g não é sobrejetora.</p><p>Definição</p><p>Definimos f: X → Y uma função bijetora se f é injetora e sobrejetora.</p><p>Vejamos um exemplo:</p><p>Σxemρlo 5</p><p>Sejam f: ℤ → ℤ dada por f(x) = x + 1 e g: ℝ → ℝ dada por g(x) = 6x + 5, vamos</p><p>verificar que f e g são bijetoras.</p><p>Segue do Exemplo 4 que f é sobrejetora. Além disso, dados x1, x2 ∈ ℤ tais que</p><p>f(x1) = f(x2), então x1 + 1 = x2 + 1, onde x1 = x2, provando que f também é injetora.</p><p>Portanto, f é bijetora.</p><p>É fácil verificar que g é injetora. De fato, dados x1, x2 ∈ ℤ tais que g(x1) = g(x2), então</p><p>6x1 + 5 = 6x2 + 5, onde x1 = x2, provando que g é injetora. Considere y ∈ ℝ e x y� �</p><p>�</p><p>� 5</p><p>6</p><p>,</p><p>temos que g(x) = y e, assim, g também é sobrejetora. Portanto, g é bijetora.</p><p>Definição</p><p>Seja n ∈ ℕ, definiremos os conjuntos [n] e [n]0 por:</p><p>[n] ≔ {1, 2, ..., n}.</p><p>[n]</p><p>0</p><p>≔ {0, 1, 2, ..., n}.O símbolo ≔ significa igual por</p><p>definição.</p><p>Glossário</p><p>Funções discretas 85</p><p>Relacionamos funções e o conjunto [n] pelo seguinte teorema.</p><p>Teorema</p><p>Considere os conjuntos [n] e [m] com n ≠ m. Seja também f: [n] → [m] uma fun-</p><p>ção, então:</p><p>• Se n m, f não é injetora.</p><p>Podemos utilizar o teorema anterior para demonstrar o seguinte resultado que</p><p>relaciona conjuntos de cardinalidade finita e funções.</p><p>Teorema</p><p>Sejam A e B conjuntos de cardinalidade finita. Se existe uma bijeção f: A → B,</p><p>então |A| = |B|.</p><p>Demonstração</p><p>Sejam |A| = n e |B| = m, podemos, então, corresponder cada elemento de</p><p>ai ∈ A com i ∈ n�� �� , e cada elemento bj ∈ B com o elemento j ∈ m�� �� . Como f é in-</p><p>jetora, temos que n ≤ m e, como f é sobrejetora, temos que n ≥ m, onde n = m, ou</p><p>seja, |A| = |B|.</p><p>Um exemplo simples de aplicação do teorema é apresentado a seguir.</p><p>Σxemρlo 6</p><p>Considerando X um conjunto formado por meninos e Y um conjunto formado</p><p>por meninas, vamos formular uma função que nos ajude a verificar se o número de</p><p>meninos é igual ao número de meninas.</p><p>Chamaremos um par ordenado da forma (menino, menina) de casal e defini-</p><p>remos f: X → Y como a função que define o modo que um casal é formado. f ser</p><p>bijetora significa que para cada menino existe uma única menina que é seu par (in-</p><p>jetora) e que para toda menina existe um único menino que é seu par (sobrejetora),</p><p>ou seja, o número de meninos é igual ao número de meninas. Portanto, |X| = |Y|.</p><p>5.2 Função composta e função inversa</p><p>Vídeo Definiremos</p><p>agora um procedimento que pode ser utilizado para construir no-</p><p>vas funções a partir de funções dadas. Esse procedimento é chamado de composi-</p><p>ção de funções.</p><p>Definição</p><p>Sejam X, Y e Z conjuntos e f: X → Y e g: Y → Z funções, a composição das funções f: X → Y e g: Y → Z é</p><p>a função definida por</p><p>g ∘ f: X → Z</p><p>x  g(f(x))</p><p>86 Matemática Discreta</p><p>Observe que a função g ∘ f está bem definida, pois f(x) ∈ Y, e Y é o domínio de g.</p><p>Porém, a composição pela outra ordem (f ∘ g) não está definida. Além disso, f ∘ g só</p><p>estaria definida se g(y) ∈ X para todo y ∈ Y, ou seja, se g(y) ⊂ X.</p><p>Σxemρlo 7</p><p>Sejam f: ℕ → ℝ a função definida por f(x) = log x e g: ℝ → ℝ dada por g(x) = x² + 1.</p><p>Determine (g ∘ f)(x).</p><p>Note que g ∘ f: ℕ → ℝ é dada por (g ∘ f)(x) = g(f(x)) = (log x)² + 1. Além disso, observe</p><p>que a função (f ∘ g) não está definida, pois 1,25 ∈ Im(g) = ℝ e 1,25 ∉ Dom(f) = ℕ.</p><p>Veja mais um exemplo sobre composição de funções:</p><p>Σxemρlo 8</p><p>Sejam f: ℕ → ℕ a função definida por f(x) = x + 1 e g: ℕ → ℕ dada por g(x) = x² + x + 1.</p><p>Determine (g ∘ f)(x) e (f ∘ g)(x).</p><p>Note que ambas, (g ∘ f)(x) e (f ∘ g)(x), estão bem definidas. Inicialmente, vamos</p><p>calcular (g ∘ f)(x).</p><p>(g ∘ f)(x) = g(f(x))</p><p>= [f(x)]2 + f(x) + 1</p><p>= (x + 1)2 + x + 1 + 1</p><p>= x2 + 2x + 1 + x + 2</p><p>= x2 + 3x + 3</p><p>Portanto, (g ∘ f)(x) = x2 + 3x + 3.</p><p>Agora, (f ∘ g)(x).</p><p>(f ∘ g)(x) = f(g(x))</p><p>= g(x) + 1</p><p>= x2 + x + 1 + 1</p><p>= x2 + x + 2</p><p>Portanto, (f ∘ g)(x) = x2 + x + 2.</p><p>No exemplo, observamos que (g ∘ f)(x) ≠ (f ∘ g)(x). Esse fato nos diz que a com-</p><p>posição de funções não é, em geral, comutativa. Por outro lado, o teorema a seguir</p><p>enuncia que a composição de funções é associativa.</p><p>Teorema</p><p>Quaisquer que sejam f: X → Y, g: Y → Z e h: Z → W, tem-se que:</p><p>(h ∘ g) ∘ f = h ∘ (g ∘ f)</p><p>Funções discretas 87</p><p>Demonstração</p><p>Considerando um elemento qualquer x de X e considerando f(x) = y, g(y) = z e</p><p>h(z) = w, temos:</p><p>((h ∘ g) ∘ f)(x) = (h ∘ g)(f(x)) = (h ∘ g)(y) = h(g(y)) = h(z) = w</p><p>Notamos que</p><p>(g ∘ f)(x) = g(f(x)) = g(y) = z</p><p>Portanto,</p><p>(h ∘ (g ∘ f))(x) = h((g ∘ f)(x)) = h(z) = w</p><p>Então, para todo x de A:</p><p>((h ∘ g) ∘ f)(x) = (h ∘ (g ∘ f))(x)</p><p>Teorema</p><p>Se duas funções f: X → Y e g: Y → Z são sobrejetoras, então a função composta</p><p>g ∘ f: A → C é sobrejetora.</p><p>Demonstração</p><p>Sendo g sobrejetora, então, para todo z ∈ Z, existe y ∈ Y tal que g(y) = z e, como</p><p>a função f é sobrejetora, isto é, dado y ∈ Y, existe x ∈ X tal que f(x) = y. Logo, para</p><p>todo z ∈ Z, existe x ∈ X tal que</p><p>z = g(y) = g(f(x)) = (g ∘ f)(x)</p><p>Provando que g ∘ f é sobrejetora.</p><p>O teorema anterior afirma que a composição de funções conserva a sobreti-</p><p>vidade, ou seja, informa que a composta de funções sobrejetoras é uma função</p><p>sobrejetora. O mesmo ocorre com funções injetoras, como podemos observar no</p><p>teorema a seguir.</p><p>Teorema</p><p>Se duas funções f: X → Y e g: Y → Z são injetoras, então a função composta</p><p>g ∘ f: A → C é injetora.</p><p>Demonstração</p><p>Consideremos x1 e x2 dois elementos quaisquer de X e suponhamos</p><p>que (g ∘ f)(x1) = (g ∘ f)(x2), isto é, g(f(x1)) = g(f(x2)). Como g é injetora, da última igual-</p><p>dade resulta que f(x1) = f(x2); como f é também injetora, temos que x1 = x2. Portanto,</p><p>g ∘ f é injetora.</p><p>A operação de composição de funções é utilizada para definir a função inversa</p><p>de uma função.</p><p>Definição</p><p>Seja f: X → Y uma função, se existe g: Y → X tal que (f ∘ g)(x) = x, ∀ x ∈ Y, e (g ∘ f )(x) = x, ∀ x ∈ A,</p><p>então uma função g é chamada de função inversa de f e é denotada por f–1.</p><p>88 Matemática Discreta</p><p>Vejamos um exemplo:</p><p>Σxemρlo 9</p><p>Considere as funções f: ℝ → ℝ definida por f(x) = x + 2 e g: ℝ → ℝ dada por</p><p>g(x) = x - 2. Calcule e mostre que g é a função inversa de f.</p><p>De fato, nota-se que</p><p>(f ∘ g)(x) = f(g(x)) = f(x - 2) = (x - 2) + 2 = x</p><p>e</p><p>(g ∘ f)(x) = g(f(x)) = g(x + 2) = (x + 2) - 2 = x</p><p>Portanto, g é a inversa de f, ou seja, g = f–1.</p><p>Já sabemos que podemos considerar uma função f: X → Y como uma relação de</p><p>X em Y, isto é,</p><p>f = {(x, y) ∈ X × Y | y = f(x)} = {(x, f(x)) | x ∈ X}</p><p>Desse modo, você pode ser levado ao erro de relacionar função inversa com</p><p>relação inversa. Mas não faça isso!</p><p>Relação inversa e função inversa são dois conceitos totalmente diferentes. Ade-</p><p>mais, possuem algumas propriedades que as diferenciam; por exemplo, a relação</p><p>inversa sempre existe, o que não acontece com a função inversa.</p><p>A existência ou não da inversa de uma função está relacionada com sua sobre-</p><p>jetividade, como estabelece o seguinte teorema.</p><p>Teorema</p><p>Seja f: X → Y uma função, a inversa, f–1: Y → X, existe se, e somente se, f for bijetora.</p><p>Podemos concluir, com as funções do Exemplo 9, f(x) = x + 2 e g(x) = x - 2, que</p><p>devido ao fato de g ser a inversa de f, ou seja, a inversa de f existir, temos que</p><p>f(x) = x + 2 é bijetora. Analogamente, por f(x) = x + 2 ser bijetora, concluímos que f</p><p>possui inversa g, dada por g(x) = x – 2.</p><p>Outra propriedade interessante da função inversa relaciona a inversa de uma</p><p>função composta com a composta de suas inversas.</p><p>Teorema</p><p>Sejam f: X → Y e g: Y → Z duas funções bijetoras, então:</p><p>(g ∘ f)–1 = f–1 ∘ g–1</p><p>Funções discretas 89</p><p>Demonstração</p><p>Se as funções f e g são bijetoras, então a função composta g ∘ f de X em Z é bije-</p><p>tora; logo, existe a função inversa (g ∘ f)–1 de X em Z. Para provar que (g ∘ f)–1 = f–1 ∘ g–1,</p><p>basta provar que (f–1 ∘ g–1) ∘ (g ∘ f)(x) = x e (g ∘ f) ∘ (f–1 ∘ g–1)(x) = x.</p><p>De fato,</p><p>(f–1 ∘ g–1) ∘ (g ∘ f)(x) = [(f–1 ∘ g–1) ∘ g] ∘ f(x)</p><p>= [f–1 ∘ (g–1 ∘ g)] ∘ f(x)</p><p>= f–1 ∘ [(g–1 ∘ g) ∘ f(x)]</p><p>= f–1 ∘ f(x)</p><p>= x</p><p>e</p><p>(g ∘ f) ∘ (f–1 ∘ g–1)(x) = [(g ∘ f) ∘ f–1] ∘ g–1(x)</p><p>= [g ∘ (f ∘ f–1)] ∘ g–1(x)</p><p>= g ∘ [(f ∘ f–1) ∘ g–1(x)]</p><p>= g ∘ g–1(x)</p><p>= x</p><p>Provamos, assim, que f–1 ∘ g–1 é a inversa da função composta g ∘ f.</p><p>5.3 Funções recursivas</p><p>Vídeo Recursividade é um método utilizado para definir funções f: ℕ∪{0} → Y, onde Y é</p><p>um conjunto numérico qualquer. Esse método consiste em duas etapas:</p><p>a. Definir um valor para a função f em zero.</p><p>b. Fornecer uma regra para encontrar o valor de f(x + 1) a partir dos valores de</p><p>f(0), f(1), …, f(x).</p><p>Σxemρlo 10</p><p>Seja f: ℕ∪{0} → ℕ a função definida recursivamente por f(0) = 7 e</p><p>f(x + 1) = 3f(x) + 1. Determine os valores de f(1), f(2) e f(3).</p><p>Por definição, temos que:</p><p>f(1) = f(0 + 1) = 3f(0) + 1 = 3 · 7 + 1 = 22</p><p>f(2) = f(1 + 1) = 3f(1) + 1 = 3 · 22 + 1 = 67</p><p>f(3) = f(2 + 1) = 3f(2) + 1 = 3 · 67 + 1 = 202</p><p>90 Matemática Discreta</p><p>Várias operações podem ser estudadas por meio de funções recursivas. Lem-</p><p>bramos, por exemplo, que a operação fatorial de um número natural x é definida</p><p>como x! = 1 · 2 · 3 · … · x.</p><p>A operação fatorial pode ser definida por meio da seguinte função recursiva</p><p>f: ℕ∪{0} → ℕ, dada por:</p><p>f(0) = 1</p><p>f(x + 1) = (x + 1)f(x)</p><p>Por exemplo, temos que:</p><p>• f(1) = f(0 + 1) = (0 + 1)f(0) = 1 · 1 = 1!</p><p>• f(2) = f(1 + 1) = (1 + 1)f(1) = 2 · 1! = 2 · 1 = 2!</p><p>Para finalizar este capítulo, apresentaremos uma função que é definida de ma-</p><p>neira recursiva e gera uma sequência de números, conhecidos como números de</p><p>Fibonacci. Esses números foram introduzidos pelo matemático italiano Leonardo</p><p>de Pisa (1170-1250), mais conhecido por Fibonacci, e possuem várias aplicações em</p><p>ciência da computação e teoria de jogos. Além disso, essa sequência de números</p><p>está intrinsecamente ligada à natureza, descrevendo perfeitamente, por exemplo,</p><p>a reprodução das abelhas.</p><p>Σxemρlo 11</p><p>Os números de Fibonacci f(0), f(1), f(2), … são dados pela função f: ℕ∪{0} → ℕ,</p><p>definida recursivamente por</p><p>• f(0) = 0</p><p>• f(1) = 1</p><p>• f(x) = f(x - 1) + f(x - 2)</p><p>Calcule os valores de f(2), f(3), f(4) e f(5).</p><p>Temos, por definição, que</p><p>f(2) = f(2 - 1) + f(2 - 2) = f(1) + f(0) = 1 + 0 = 1</p><p>f(3) = f(3 - 1) + f(3 - 2) = f(2) + f(1) = 1 + 1 = 2</p><p>f(4) = f(4 - 1) + f(4 - 2) = f(3) + f(2) = 2 + 1 = 3</p><p>f(5) = f(5 - 1) + f(5 - 2) = f(4) + f(3) = 3 + 2 = 5</p><p>CONSIDERAÇÕES FINAIS</p><p>Neste capítulo, vimos que uma função entre dois conjuntos X e Y pode ser vis-</p><p>ta como uma relação e</p><p>que toda função é classificada conforme sua injetividade,</p><p>sobrejetividade e bijetividade. Além disso, você aprendeu que dadas duas funções,</p><p>f: X → Y e g: Y → Z, podemos produzir uma nova função g ∘ f: X → Z, chamada de</p><p>função composta. Vimos a importância das funções para contar o número de ele-</p><p>mentos de um conjunto finito e como podemos utilizar funções recursivas para</p><p>produzir uma sequência de números.</p><p>No filme O código da</p><p>Vinci, o simbologista Robert</p><p>Langdon e a criptóloga</p><p>Sophie Neveu encontram</p><p>números na cena de um</p><p>crime ocorrido no Museu</p><p>do Louvre, em Paris.</p><p>Os números pintados a</p><p>sangue, postos em ordem</p><p>aleatória, revelam-se mais</p><p>tarde um código, a série</p><p>de Fibonacci, que os pro-</p><p>tagonistas usam para abrir</p><p>um cofre e dar sequência à</p><p>resolução do mistério.</p><p>Direção: Ron Howard. EUA: Sony</p><p>Pictures, 2006.</p><p>Filme</p><p>Funções discretas 91</p><p>ATIVIDADES</p><p>1. Sejam A, B ⊂ X e f: X → Y uma função, mostre que a imagem direta de f é tal que:</p><p>f(A∩B) ⊂ f(A)∩f(B)</p><p>2. Sejam A, B ⊂ Y e f: X → Y uma função, mostre que imagem inversa de f é tal que:</p><p>f–1(A∪B) = f–1(A)∪f–1(B)</p><p>3. Mostre que a função f: ℕ → ℕ dada por f(x) = 4x + 7 é injetora.</p><p>4. Mostre que a função f: ℤ → ℕ dada por f(x) = 2x2 não é injetora.</p><p>5. Mostre que a função f: ℝ → ℕ dada por f(x) = 4x + 7 é sobrejetora. Se o domínio de</p><p>f fosse o conjunto dos números naturais f ainda seria sobrejetora?</p><p>REFERÊNCIAS</p><p>GERSTING, J. L. Fundamentos Matemáticos para Ciência da Computação. 4. ed. São Paulo: LTC, 2001.</p><p>GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5 ed. Boston: Addison-</p><p>Wesley, 2004.</p><p>ROSEN, K. H. Matemática discreta e suas aplicações. 6 ed. São Paulo: McGraw-Hill, 2009.</p><p>92 Matemática Discreta</p><p>6</p><p>Análise combinatória</p><p>A análise combinatória é a área da matemática que se dedica a desen-</p><p>volver técnicas de contagem, preocupando-se em como, e não com o que,</p><p>vamos contar. Muitos dos problemas de contagem tiveram sua origem</p><p>ligada a jogos e loterias. As principais publicações da análise combinatória</p><p>foram feitas pelos matemáticos Blaise Pascal e Pierre de Fermat.</p><p>Neste capítulo, vamos apresentar as principais técnicas de contagem,</p><p>como combinações, arranjos e permutações, e demonstrar como utilizá-las</p><p>em diferentes situações.</p><p>6.1 Princípios de contagem</p><p>Vídeo A análise combinatória é baseada em alguns princípios de contagem muito sim-</p><p>ples e intuitivos. Você pode pensar que eles são tão fáceis que nem mesmo mere-</p><p>cem um nome. Mas, para levarmos a contagem a sério, devemos estar cientes de</p><p>fatos simples que usamos implicitamente o tempo todo.</p><p>Definição (princípio da adição)</p><p>Dizemos que um conjunto finito A é particionado nas partes A</p><p>1</p><p>, …, A</p><p>k</p><p>se as partes são disjuntas e sua</p><p>união é A. Em outras palavras, temos A</p><p>i</p><p>∩A</p><p>j</p><p>=</p><p>∅ para i ≠ j e A</p><p>1</p><p>∪A</p><p>2</p><p>∪…∪A</p><p>k</p><p>=</p><p>A. Nesse caso,</p><p>|A| = |A</p><p>1</p><p>| + |A</p><p>2</p><p>| + … + |A</p><p>k</p><p>|</p><p>O princípio da adição mostra que se existem |A1| maneiras de tomar a decisão</p><p>A1, |A2| maneiras de tomar a decisão A2, …, |Ak| maneiras de tomar a decisão Ak,</p><p>então o número de maneiras de se tomar a decisão A1 ou a decisão A2, … ou a de-</p><p>cisão Ak é |A1| + |A2| + … + |Ak|.</p><p>Vejamos um exemplo:</p><p>Σxemρlo 1</p><p>Seja A o conjunto de alunos que assistem à aula de combinatória. Esse conjunto</p><p>pode ser particionado nas partes A1 e A2, tais que:</p><p>A1 = {Alunos que gostam de exemplos fáceis}.</p><p>A2 = {Alunos que não gostam de exemplos fáceis}.</p><p>Análise combinatória 93</p><p>Se |A1| = 22 e |A2| = 8, de quantas maneiras distintas podemos escolher um</p><p>aluno que assiste à aula de combinatória?</p><p>Como A = A1∪A2 com A1∩A2 = ∅, então podemos concluir, pelo princípio da adi-</p><p>ção, que existem |A| = |A1| + |A2| = 30 maneiras diferentes de escolher um aluno</p><p>que assiste à aula de combinatória.</p><p>Acompanhe outro exemplo.</p><p>Σxemρlo 2</p><p>Você vai a um restaurante e, ao observar o cardápio, encontra 4 diferentes pra-</p><p>tos italianos e 3 diferentes pratos portugueses. De quantas maneiras você pode</p><p>escolher um único prato para fazer sua refeição?</p><p>Considere os seguintes conjuntos:</p><p>• A = {Pratos do restaurante}.</p><p>• A1 = {Pratos italianos}.</p><p>• A2 = {Pratos portugueses}.</p><p>Observamos que:</p><p>A = A1∪A2 com A1∩A2 = ∅ e |A| = |A1| + |A2| = 7</p><p>Logo, existem sete maneiras diferentes de se escolher um prato para realizar</p><p>uma refeição.</p><p>Definição (princípio da subtração)</p><p>Seja A um subconjunto de um conjunto finito X, definimos A ≔ X\S como o complemento de A em</p><p>X. Então:</p><p>|A| = |X| - | A |</p><p>Σxemρlo 3</p><p>Considere X o conjunto de alunos que estudam análise combinatória e A o con-</p><p>junto de alunos que não são do curso de Matemática nem do curso de Ciência da</p><p>Computação. Considerando que o total de alunos é 23.905, se 20.178 não fazem</p><p>parte do curso de Matemática e nem do curso de Ciência da Computação, quantos</p><p>alunos estão cursando Matemática ou Ciência da Computação?</p><p>Sabemos que |X| = 23.905 e |A| = 20.178. Além disso,</p><p>94 Matemática Discreta</p><p>|A| = {Alunos que cursam Matemática ou Ciência da Computação}.</p><p>|A| = |X| - |A|</p><p>= 23.905 – 20.178</p><p>= 3.727</p><p>Ou seja, existem 3.727 alunos que cursam Matemática ou Ciência da Computação.</p><p>A seguir, apresentaremos dois outros princípios que são igualmente intuitivos e</p><p>naturais e que ocorrerão com frequência na resolução de exercícios e nas demons-</p><p>trações de teoremas.</p><p>Definição (princípio da multiplicação)</p><p>Se A é um conjunto finito, definido pelo produto cartesiano de A</p><p>1</p><p>,</p><p>.</p><p>..., A</p><p>k</p><p>, ou seja, A = A</p><p>1</p><p>x</p><p>A</p><p>2</p><p>x</p><p>... x A</p><p>k</p><p>,</p><p>então:</p><p>|A| = |A</p><p>1</p><p>| x |A</p><p>2</p><p>| x ... x |A</p><p>k</p><p>|</p><p>O princípio da multiplicação mostra que se existem |A1|maneiras de tomar a</p><p>decisão A1, |A2| maneiras de tomar a decisão A2, …, |Ak| maneiras de tomar a de-</p><p>cisão Ak, então o número de maneiras de se tomar sucessivamente as decisões A1,</p><p>A2, …, Ak é |A1| x |A2| x … x |Ak|. Vejamos um exemplo:</p><p>Σxemρlo 4</p><p>Você vai a um restaurante e, ao observar o cardápio, encontra 4 opções de pra-</p><p>tos principais e 3 opções de sobremesa. De quantas maneiras você pode fazer uma</p><p>refeição formada por um prato principal e uma sobremesa?</p><p>Considere os seguintes conjuntos:</p><p>• A = {Refeições com um prato principal e uma sobremesa}.</p><p>• A1 = {Pratos principais}.</p><p>• A2 = {Sobremesa}.</p><p>Observamos que:</p><p>A = A1 × A2 e |A| = |A1| × |A2| = 12</p><p>Logo, existem 12 maneiras diferentes de realizar uma refeição formada por um</p><p>prato principal e uma sobremesa.</p><p>Acompanhe mais um exemplo do princípio da multiplicação.</p><p>Σxemρlo 5</p><p>Quantos números de três dígitos podemos formar com os algarismos 2, 3, 4 e 6?</p><p>Análise combinatória 95</p><p>Considere os seguintes conjuntos:</p><p>• A = {Números de três dígitos formados por 2, 3, 4 e 6}.</p><p>• A1 = {Opções para o primeiro dígito}.</p><p>• A2 = {Opções para o segundo dígito}.</p><p>• A3 = {Opções para o terceiro dígito}.</p><p>Temos que:</p><p>A = A1 × A2 × A3 e |A1| = 4, |A2| = 4, |A3| = 4</p><p>Então:</p><p>|A| = |A1| × |A2| × |A3| = 4 × 4 × 4 = 64</p><p>Portanto, podemos formar 64 números de três dígitos com os algarismos 2, 3, 4 e 6.</p><p>Agora, um último exemplo utilizando o princípio da multiplicação.</p><p>Σxemρlo 6</p><p>Em uma cidade fictícia, as placas dos carros têm a seguinte forma:</p><p>CF – l1l2n1n2n3</p><p>Nessas placas, l1, l2 são letras do conjunto {A, …, Z} e n1, n2, n3 são dígitos do</p><p>conjunto {0, …, 9}. No entanto, l2 e n3 podem ser omitidos. Quantas placas podem</p><p>ser confeccionadas nessa cidade?</p><p>Vamos considerar o caso em que l2 é omitido, acrescentando um valor ⊥ para l2,</p><p>que significa omitido. O mesmo vale para n3.</p><p>Seja A = {Placas válidas}, o conjunto de todas as placas válidas é dado como os</p><p>produtos:</p><p>{T} × {T} × {–} × {A, …, Z} × {A, …, Z, ⊥} × {0, …, 9} × {0, …, 9} × {0, …, 9, ⊥}</p><p>Pelo princípio de multiplicação, temos que:</p><p>|A| = |{T}| × |{T}| × |{–}| × |{A, …, Z}| × |{A, …, Z, ⊥}| × |{0, …, 9}| × |{0, …, 9}|</p><p>× |{0, …, 9, ⊥}|</p><p>|A| = 1 × 1 × 1 × 26 × 27 × 10 × 10 × 11 = 772.200</p><p>Ou seja, podem ser confeccionadas 772.200 placas.</p><p>Definição (princípio da casa dos pombos)</p><p>Sejam A</p><p>1</p><p>,</p><p>.</p><p>..., A</p><p>m</p><p>conjuntos finitos tais que A</p><p>i</p><p>∩A</p><p>j</p><p>= ∅ para i ≠ j e |A</p><p>1</p><p>| + |A</p><p>2</p><p>| + ... + |A</p><p>m</p><p>| = n,</p><p>pai da lógica matemática.</p><p>O norte da lógica matemática é a busca pela verdade; sendo assim, possui como</p><p>objeto de estudo as leis de formação do pensamento e as regras para se aplicar</p><p>essas leis para investigar a verdade. Outro grande objetivo dessa ciência é entender</p><p>como podemos utilizar noções previamente estabelecidas como verdadeiras para</p><p>deduzir novos conhecimentos.</p><p>Com o objetivo de estudar a verdade, precisamos definir o principal objeto de</p><p>estudo da lógica matemática: as proposições.</p><p>10 Matemática Discreta</p><p>Definição</p><p>Uma proposição é uma declaração que pode ser verdadeira ou falsa.</p><p>De modo mais preciso, poderíamos dizer que uma proposição é um conjunto de</p><p>símbolos e palavras que exprimem um pensamento, o qual pode ser verdadeiro ou</p><p>falso. Observe os seguintes exemplos de proposições.</p><p>Σxemρlo 1</p><p>São proposições:</p><p>• p: Tóquio é a capital da China.</p><p>• q: Wellington é a capital da Nova Zelândia.</p><p>• r: 1 + 5 = 6.</p><p>• s: π</p><p>então:</p><p>∃ i ∈ {1, …, m} | |S</p><p>i</p><p>| ≥</p><p>n</p><p>m</p><p>�</p><p>��</p><p>�</p><p>��</p><p>e ∃ j ∈ {1, …, m} | |S</p><p>j</p><p>| ≤</p><p>n</p><p>m</p><p>�</p><p>��</p><p>�</p><p>��</p><p>96 Matemática Discreta</p><p>Lembramos que n</p><p>m</p><p>�</p><p>��</p><p>�</p><p>��</p><p>é a função denominada de maior inteiro, ou seja, n</p><p>m</p><p>�</p><p>��</p><p>�</p><p>��</p><p>=</p><p>menor a ∈ , tal que a ≥ n</p><p>m</p><p>. Se, por exemplo, n = 10 e m = 3, então 10</p><p>3</p><p>�=�3,333 �=�4.�</p><p>��</p><p>�</p><p>��</p><p></p><p>Já a função n</p><p>m</p><p>��</p><p>��</p><p>�</p><p>��</p><p>é denominada de menor inteiro, ou seja, n</p><p>m</p><p>�</p><p>��</p><p>�</p><p>��</p><p>= maior a ∈ , tal que</p><p>a ≤ n</p><p>m</p><p>. Temos, por exemplo, que se n = 10 e m = 3, então 10</p><p>3</p><p>3 333 3�</p><p>��</p><p>�</p><p>��</p><p>� �, � .</p><p>Vejamos um exemplo:</p><p>Σxemρlo 7</p><p>Suponha que haja 5 buracos na parede, nos quais 17 pombos se aninham. Uti-</p><p>lizando o princípio da casa dos pombos, o que podemos dizer sobre a distribuição</p><p>dos pombos nesses buracos?</p><p>Pelo princípio da casa dos pombos, temos que m = 5 e n = 17. Então, podemos</p><p>concluir que:</p><p>• Existe algum buraco com pelo menos 17</p><p>5</p><p>�</p><p>��</p><p>�</p><p>��</p><p>= 4 pombos.</p><p>• Existe algum buraco com no máximo 17</p><p>5</p><p>�</p><p>��</p><p>�</p><p>��</p><p>= 3 pombos.</p><p>Vejamos mais um exemplo.</p><p>Σxemρlo 8</p><p>Se as notas da disciplina de Matemática Discreta são graduadas por A, B, C e</p><p>D, quantos alunos devem ter na sala de aula para garantirmos que no mínimo 4</p><p>alunos tirem a mesma nota?</p><p>Vamos aplicar o princípio da casa dos pombos. Note que temos 4 possibilidades</p><p>de notas (A, B, C e D). Logo, m = 4.</p><p>Queremos que alguma das notas seja atingida por no mínimo 3 alunos, ou seja,</p><p>queremos que n</p><p>4</p><p>�</p><p>��</p><p>�</p><p>��</p><p>= 4, em que n é o número de alunos na turma. Sendo assim,</p><p>devemos ter n = 13, pois, nesse caso,</p><p>13</p><p>4</p><p>=�4�</p><p>��</p><p>�</p><p>��</p><p>.</p><p>Note que se n = 12, então 12</p><p>4</p><p>�=�3�</p><p>(basta escolher Ai A ).</p><p>No exemplo mencionado anteriormente, temos s�=�( ,� ,� ,� ,� ,� ,� )� � �⊗ ⊗ ⊗ , e sua pri-</p><p>meira coordenada é .</p><p>Utilizaremos as notações apresentadas nesta seção para, nas próximas seções,</p><p>contarmos o número total de arranjos que podemos definir em um conjunto finito A.</p><p>6.3 Permutações</p><p>Vídeo Os arranjos ordenados mais importantes são aqueles em que a função é inje-</p><p>tiva, ou seja, s(i) ≠ s(j) para i ≠ j. Esse tipo de arranjo será chamado de permutação,</p><p>como definido a seguir.</p><p>Definição</p><p>Seja A um conjunto finito, uma permutação de A é uma função bijetiva.</p><p>π: [n] → A</p><p>Quando A = [n], denotamos o conjunto de todas as permutações de [n] por Sn.</p><p>Geralmente, escrevemos permutações como sequências numéricas se n</p><p>https://www.youtube.com/watch?v=SVXCfdtXdiI&ab</p><p>Análise combinatória 103</p><p>Durante o capítulo, utilizaremos a seguinte notação: cada elemento x ∈ A que</p><p>está em S é escrito apenas uma vez, acompanhado de seu número de repetição rx.</p><p>Nessa notação, o exemplo anterior será escrito como:</p><p>S = {2 · ⊡, 1 · ⊗, 0 ·�|, 3 · △, 1 · ⋆}</p><p>Dizemos que  tem r � = 2 repetições, ⊗ tem r� � 1 repetição, | tem r| = 0 repeti-</p><p>ção,  tem r</p><p></p><p>= 3 repetições e ⋆ tem r⋆ = 1 repetição.</p><p>Notamos a diferença entre os arranjos verificando que arranjos ordenados são</p><p>seleções de elementos de A, feitas uma de cada vez, enquanto arranjos não orde-</p><p>nados são seleções de objetos feitas ao mesmo tempo.</p><p>Um exemplo típico de arranjos não ordenados é a lista de compras, pois você</p><p>pode precisar de três bananas e duas peras, e isso é o mesmo que precisar de uma</p><p>pera, três bananas e outra pera. Em certo sentido, você precisa de tudo de uma</p><p>vez, sem ordenação temporal. Isso contrasta, por exemplo, com um número de</p><p>telefone (o qual é um arranjo ordenado), em que discar primeiro o dígito 5 e depois</p><p>o dígito 9 é diferente de discar 9 primeiro e 5 em seguida.</p><p>Tal como acontece com arranjos ordenados, o caso mais importante para arranjos</p><p>não ordenados é o caso em que todos os elementos aparecem apenas uma vez, isto é,</p><p>rx = 1 para todos os x ∈ S. Ou seja, o caso mais importante de arranjos não ordenados</p><p>é aquele em que S é simplesmente um subconjunto de A, denotado por S ⊆ A.</p><p>Definição</p><p>Seja A um conjunto finito, uma k-combinação de A é um arranjo não ordenado de k elementos distintos de A.</p><p>Vejamos um exemplo:</p><p>Σxemρlo 17</p><p>Seja A = {Ana, Pedro, Maria, Tiago}, descreva duas 3-combinações de A e uma</p><p>1-combinação de A.</p><p>Uma 3-combinação de A é um subconjunto de cardinalidade três. Então, pode-</p><p>mos tomar, por exemplo, as 3-combinações:</p><p>S1 = {Ana, Pedro, Maria} e S2 = {Pedro, Maria, Tiago}</p><p>Uma 1-combinação de A é um subconjunto de cardinalidade um. Podemos to-</p><p>mar, por exemplo, a 1-combinação:</p><p>S3 = {Maria}</p><p>O conjunto de todos os k-subconjuntos de A é denotado por</p><p>A</p><p>k</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�, e se |A| = n,</p><p>denotamos:</p><p>n</p><p>k</p><p>A</p><p>k</p><p>Cn</p><p>k�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �:</p><p>104 Matemática Discreta</p><p>Teorema</p><p>Para 0 ≤ k ≤ n, temos:</p><p>P n,�k =</p><p>n</p><p>k</p><p>k!� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>Demonstração</p><p>Para construir um elemento de P(n, k), primeiro escolhemos k elementos de [n].</p><p>Pela definição de</p><p>n</p><p>k</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�, existem exatamente</p><p>n</p><p>k</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� maneiras de fazer isso. Então, esco-</p><p>lhemos uma ordem para esses k elementos. Existem P k,�k �=�k!</p><p>0!</p><p>�=�k!� � maneiras de</p><p>fazer isso. Cada elemento de P(n, k) pode ser construído, assim, de exatamente</p><p>uma maneira em que P n,�k �=</p><p>n</p><p>k</p><p>k!� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� , o que prova a afirmação.</p><p>Note que o teorema anterior nos diz que o número de k-combinações de um</p><p>conjunto finito A com |A| = n é dado por:</p><p>n</p><p>k</p><p>A</p><p>k</p><p>=�C �=�</p><p>P n,�k</p><p>k!</p><p>�=� n!</p><p>k n�-�k !n</p><p>k�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>� �:</p><p>Vejamos um exemplo:</p><p>Σxemρlo 18</p><p>Um grupo de 5 pessoas está organizando um evento científico, sendo que 2</p><p>dessas 5 pessoas ficarão encarregadas de organizar a festa de encerramento. De</p><p>quantas maneiras diferentes podemos escolher essas duas pessoas?</p><p>Queremos contar o número total de 2-combinações do conjunto A = {p1, p2,</p><p>p3, p4, p5}, em que pi representa a pessoa i do conjunto. Como |A| = 5, quere-</p><p>mos encontrar:</p><p>C �=� 5!</p><p>2! 5�-�2 !</p><p>�=� 5!</p><p>2! 3!</p><p>�=�5�·�4�·�3!</p><p>2�·�3!</p><p>�=�20</p><p>2</p><p>�=�105</p><p>2</p><p>� � ·</p><p>Ou seja, existem 10 maneiras possíveis de escolher duas pessoas para organizar</p><p>a festa de encerramento.</p><p>Acompanhe outro exemplo de combinação.</p><p>Σxemρlo 19</p><p>Considere um sistema de comunicação composto de quatro antenas.</p><p>De</p><p>ny</p><p>s D</p><p>ro</p><p>zd</p><p>/S</p><p>hu</p><p>tte</p><p>rs</p><p>to</p><p>ck</p><p>Análise combinatória 105</p><p>Quantas possibilidades existem de exatamente três antenas estarem com</p><p>defeito?</p><p>Queremos contar o número total de 3-combinações do conjunto A = {A1, A2,</p><p>A3, A4}, em que Ai representa a antena i do conjunto. Como |A| = 4, queremos</p><p>encontrar:</p><p>C4</p><p>3 4</p><p>3 4 3</p><p>4</p><p>3 1</p><p>4 3</p><p>3</p><p>4� � !</p><p>! !</p><p>� � !</p><p>! !</p><p>� � � !</p><p>!</p><p>� ��</p><p>�� � � �</p><p>�</p><p>�</p><p>�</p><p>Ou seja, existem 4 maneiras possíveis de exatamente três antenas estarem com</p><p>defeito.</p><p>Vejamos mais um exemplo:</p><p>Σxemρlo 20</p><p>Em um campeonato de futebol, cada um dos 16 times joga uma única vez contra</p><p>todos os demais. Quantas partidas serão realizadas?</p><p>Como cada partida é formada por dois times, queremos contar o número total</p><p>de 2-combinações do conjunto A = {T1, T2, …, T16}, em que Ti representa o time i.</p><p>Como |A| = 16, queremos encontrar:</p><p>C �=� 16!</p><p>2! 16�-�2 !</p><p>�= � 16!</p><p>2�·�14!</p><p>�= 16�·�15�·�14!</p><p>2�·�14!16</p><p>2</p><p>� � = 16�·�15</p><p>2</p><p>�=�8�·�15�=�120</p><p>Ou seja, ocorrerão 120 partidas no campeonato.</p><p>A seguir, observe outro exemplo no qual usamos a combinatória.</p><p>Σxemρlo 21</p><p>De 5 mulheres e 7 homens, quantos comitês diferentes de 2 mulheres e 3 ho-</p><p>mens podem ser formados?</p><p>Vamos considerar A = {M1, M2, M3, M4, M5}, em que Mi denota a mulher i, e</p><p>B = {H1, H2, H3, H4, H5, H6, H7}, sendo que Hj denota o homem j. Em cada comitê tere-</p><p>mos um conjunto de 2 mulheres. Como |A| = 5, precisamos calcular:</p><p>C =� 5!</p><p>2! 5�-�2 !</p><p>�=� 5!</p><p>2�·�3!</p><p>�=�5�·�4�·�3!</p><p>2�·�3!</p><p>�=�105�</p><p>2</p><p>� �</p><p>Analogamente, em cada comitê teremos um conjunto de 3 homens. Como</p><p>|B| = 7, precisamos calcular:</p><p>C �=� 7!</p><p>3! 7�-�3 !</p><p>�=� 7!</p><p>3!�·�4!</p><p>�=�7�·�6�·�5�·�4!</p><p>6�·�4!</p><p>�=�357</p><p>3</p><p>� �</p><p>106 Matemática Discreta</p><p>Como cada comitê é formado por 2 mulheres e 3 homens, precisamos utilizar o</p><p>princípio multiplicativo para obter o número total de comitês diferentes que pode-</p><p>mos formar. Ou seja, o número total T será:</p><p>T�=�C �·�C �=�10�·�35�=�3505</p><p>2</p><p>7</p><p>3</p><p>Portanto, podemos formar 350 comitês diferentes.</p><p>6.5 Binômio de Newton</p><p>Vídeo Os números</p><p>n</p><p>k</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� para 0 ≤ k ≤ n são chamados também de coeficientes binomiais,</p><p>pois são os coeficientes encontrados ao se expandir a enésima potência de uma</p><p>soma de duas variáveis: (x + y)n. Coeficientes binomiais são utilizados no método</p><p>conhecido como binômio de Newton. Para demonstrar o binômio de Newton, utili-</p><p>zaremos o teorema a seguir.</p><p>Teorema</p><p>Sejam m, n ∈ , então:</p><p>m</p><p>k</p><p>m</p><p>k</p><p>m</p><p>k�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�1</p><p>1</p><p>Vejamos um exemplo:</p><p>Σxemρlo 22</p><p>Verifique que:</p><p>4</p><p>2</p><p>4</p><p>3</p><p>5</p><p>3</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>Temos que:</p><p>4</p><p>2</p><p>4</p><p>2 4 2</p><p>12</p><p>2</p><p>6</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�� � � � �</p><p>!</p><p>! !</p><p>4 · 3�·�2!</p><p>2�·�2!</p><p>4</p><p>3</p><p>4</p><p>3 4 3</p><p>4</p><p>1</p><p>4</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�� � � � �</p><p>!</p><p>! !</p><p>�����4�·�3!</p><p>3!�·�1!</p><p>5</p><p>3</p><p>5</p><p>3 5 3</p><p>20</p><p>2</p><p>10</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�� � � � �</p><p>!</p><p>! !</p><p>5 · 4�·�3!</p><p>3!�·�2!</p><p>Portanto:</p><p>4</p><p>2</p><p>4</p><p>3</p><p>5</p><p>3</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>O binômio de Newton é descrito e demonstrado a seguir.</p><p>Teorema</p><p>Sejam x, y variáveis e n ∈ , então:</p><p>x y</p><p>n</p><p>k</p><p>x yn</p><p>k</p><p>n</p><p>n k k�� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>��</p><p>0</p><p>Análise combinatória 107</p><p>Demonstração</p><p>Vamos demonstrar, por indução, que o binômio de Newton é válido para qual-</p><p>quer n ≥ 1.</p><p>Para n = 1, temos (x + y)1 = x + y e</p><p>k</p><p>n k k</p><p>k</p><p>y x y x y x y</p><p>�</p><p>� � ��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � �</p><p>0</p><p>1</p><p>1 0 0 1 1 11 1</p><p>0</p><p>1</p><p>1</p><p>x</p><p>Ou seja:</p><p>x y</p><p>k</p><p>x y</p><p>k</p><p>n k k�� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>��</p><p>1</p><p>0</p><p>1 1</p><p>Logo, o binômio de Newton é válido para n = 1.</p><p>Agora, suponha que o resultado é verdadeiro para n = m, ou seja, vale</p><p>x y</p><p>m</p><p>k</p><p>x ym</p><p>k</p><p>m</p><p>m k k�� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>��</p><p>0</p><p>Vamos demonstrar que o resultado é válido para n = m + 1.</p><p>De fato:</p><p>x y x y x ym m</p><p>�� � � �� � �� ��1</p><p>�� �� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>��x y</p><p>m</p><p>k</p><p>x y</p><p>k</p><p>m</p><p>m k k</p><p>0</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�� �x</p><p>m</p><p>k</p><p>x y y</p><p>m</p><p>k</p><p>x y</p><p>k</p><p>m</p><p>m k k</p><p>k</p><p>m</p><p>m k k</p><p>0 0</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>� �� �</p><p>k</p><p>m</p><p>m k k</p><p>k</p><p>m</p><p>m k km</p><p>k</p><p>x y</p><p>m</p><p>k</p><p>x y</p><p>0</p><p>1</p><p>0</p><p>1</p><p>A primeira soma pode ser escrita como:</p><p>k</p><p>m</p><p>m k k m</p><p>k</p><p>m</p><p>m k kx y x</p><p>m</p><p>k</p><p>x y</p><p>�</p><p>� � �</p><p>�</p><p>� �� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>0</p><p>1 1</p><p>1</p><p>1m</p><p>k</p><p>A segunda soma pode ser escrita como:</p><p>k</p><p>m</p><p>m k k m</p><p>k</p><p>m</p><p>m k km</p><p>k</p><p>x y y</p><p>m</p><p>k</p><p>x y</p><p>�</p><p>� � �</p><p>�</p><p>�</p><p>� �� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>0</p><p>1 1</p><p>0</p><p>1</p><p>1</p><p>�� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>��</p><p>�</p><p>� ��y</p><p>m</p><p>k</p><p>x ym</p><p>k</p><p>m</p><p>m k k1</p><p>1</p><p>1</p><p>1</p><p>Então, temos:</p><p>x y x</p><p>m</p><p>k</p><p>x y y</p><p>m</p><p>k</p><p>xm m</p><p>k</p><p>m</p><p>m k k m</p><p>k</p><p>m</p><p>m�� � � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>� � �</p><p>�</p><p>� �</p><p>1 1</p><p>1</p><p>1 1</p><p>1</p><p>1</p><p>�� �1 k ky</p><p>� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>� ��x y</p><p>m</p><p>k</p><p>m</p><p>k</p><p>x ym m</p><p>k</p><p>m</p><p>m k k1 1</p><p>1</p><p>1</p><p>1</p><p>108 Matemática Discreta</p><p>Mas</p><p>m</p><p>k</p><p>m</p><p>k</p><p>m</p><p>k�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�1</p><p>1</p><p>Então:</p><p>x y x y</p><p>m</p><p>k</p><p>x ym m m</p><p>k</p><p>m</p><p>m k k�� � � � �</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � �</p><p>�</p><p>� ��</p><p>1 1 1</p><p>1</p><p>11</p><p>� �</p><p>m</p><p>k</p><p>x y</p><p>k</p><p>m</p><p>m k k�</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>��</p><p>0</p><p>1 1</p><p>Assim, fica provado que o teorema é válido para todo n ∈ .</p><p>A fórmula binomial pode ser generalizada para mais de duas variáveis.</p><p>Definição</p><p>Para inteiros não negativos k</p><p>1</p><p>,</p><p>.</p><p>..., k</p><p>r</p><p>, com k</p><p>1</p><p>+</p><p>... + k</p><p>r</p><p>=</p><p>n, os coeficientes multinomiais</p><p>n</p><p>k , ..., k1 r</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� são</p><p>os coeficientes encontrados ao se expandir a n-ésima potência de uma soma de r variáveis. Em outras</p><p>palavras, definimos os coeficientes multinomiais</p><p>n</p><p>k , ..., k1 r</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� como os únicos números que satisfaçam</p><p>a seguinte identidade:</p><p>x x</p><p>n</p><p>k , ..., k</p><p>x xr</p><p>n</p><p>k kr n</p><p>k kr</p><p>1 r</p><p>1</p><p>k1</p><p>2</p><p>k2</p><p>1</p><p>1</p><p>1</p><p>���� � � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � �</p><p>�</p><p>...</p><p>,...,</p><p>....xr</p><p>kr</p><p>Vejamos um exemplo:</p><p>Σxemρlo 23</p><p>Utilize o polinômio (x1 + x2 + x3)</p><p>4</p><p>para encontrar</p><p>4</p><p>2 11</p><p>4</p><p>2 0 2</p><p>4</p><p>0 0 4,� ,�</p><p>,�</p><p>,� ,�</p><p>,�</p><p>,� ,�</p><p>.</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>Temos que:</p><p>x x x x x x1 2� �� � � � � �� �3</p><p>4</p><p>1</p><p>4</p><p>2</p><p>4</p><p>3</p><p>41</p><p>� � � � � � �� ��4 x x x x x x x x x x x x1</p><p>3</p><p>2 1</p><p>3</p><p>3 1 2</p><p>3</p><p>2</p><p>3</p><p>3 1 3</p><p>3</p><p>2 3</p><p>3</p><p>� � � �� ��6 x x x x x x1</p><p>2</p><p>2</p><p>2</p><p>1</p><p>2</p><p>3</p><p>2</p><p>2</p><p>2</p><p>3</p><p>2</p><p>� � � �� ��12 x x x x x x x x x1</p><p>2</p><p>2 3 1 2</p><p>2</p><p>3 1 2 3</p><p>2</p><p>Análise combinatória 109</p><p>O coeficiente de x x x1</p><p>2</p><p>2 3 é 12, o coeficiente de x x1</p><p>2</p><p>3</p><p>2 é 6 e o coeficiente de x3</p><p>4 é 1.</p><p>De acordo com a definição de coeficiente multinomial, temos que:</p><p>4</p><p>2 11</p><p>12</p><p>4</p><p>2 0 2</p><p>6</p><p>4</p><p>0 0 4</p><p>1</p><p>,� ,�</p><p>�,�</p><p>,� ,�</p><p>�,�</p><p>,� ,�</p><p>.</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>Note que, por exemplo,</p><p>n</p><p>k ,�...,�k1 r</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�� �</p><p>4</p><p>2 11</p><p>12</p><p>,� ,�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � → k1 = 2, k2 = 1 e k3 = 1</p><p>→ k1 + k2 + k3 = 4 = n.</p><p>Além disso, observe que em x x x1</p><p>2</p><p>2 3 temos que o expoente de x1 é k1 = 2, o ex-</p><p>poente de x2 é k2 = 1 e o expoente de x3 é k3 = 1, conforme a definição.</p><p>A seguir, apresentamos um teorema que nos ensina a calcular de modo prático</p><p>os coeficientes multinomiais de uma expansão polinomial da forma x � xr</p><p>n</p><p>1 ���� � .</p><p>Teorema</p><p>Para inteiros não negativos k1, …, kr, com k1 + … + kr = n, tem-se:</p><p>n</p><p>k ,�...,k</p><p>n</p><p>k</p><p>n k</p><p>k1 r 1 2</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�� �</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>���</p><p>��</p><p>�</p><p>��</p><p>�</p><p>�</p><p>��� ���</p><p>� �</p><p>��...�1 ��</p><p>� � � �... � !</p><p>! ! �... � !</p><p>n k k</p><p>k</p><p>n</p><p>k k k</p><p>r</p><p>r r</p><p>� � ��</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�� � � � �</p><p>�1 1</p><p>1 2</p><p>Demonstração</p><p>Pela definição de potenciação, temos que x � � � �xr</p><p>n</p><p>1 � �� �... pode ser escrito como:</p><p>x � � x x x xr</p><p>n</p><p>i</p><p>r</p><p>i</p><p>r</p><p>in</p><p>r</p><p>i i in</p><p>n�somas</p><p>1</p><p>1 1 2 1 1</p><p>1 2</p><p>� �� � �</p><p>� � �</p><p>� � �... ... ...</p><p>� ������ �����</p><p>Nessa demonstração, os monômios xi1</p><p>, xi2</p><p>, …, xin</p><p>são iguais a x ��xk</p><p>r</p><p>kr</p><p>1</p><p>1,��..., se os</p><p>índices i1, …, in são exatamente iguais a 1, 2 …, r. Contaremos o número de atribui-</p><p>ções de valores aos índices i1, …, in, satisfazendo isso.</p><p>• Escolhendo os índices k1 iguais a 1</p><p>Existem</p><p>n</p><p>k �1�</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�� maneiras de fazer isso.</p><p>• Escolhendo os índices k2 iguais a 2</p><p>Existem n-índices k1 restantes para escolher, então há</p><p>�n�-�k �</p><p>k �</p><p>1</p><p>2</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�� maneiras de es-</p><p>colher k2 deles.</p><p>• Escolhendo índices kJ iguais a j (j ∈ [r])</p><p>Há n - k1 - … - kj-1 índices restantes para escolher, então há</p><p>n� �k � � � �k �</p><p>k</p><p>j</p><p>j</p><p>� � ��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�1 1...</p><p>maneiras de escolher kj deles.</p><p>Logo, o coeficiente multinomial (ou seja, o coeficiente de x x xk k</p><p>r</p><p>kr</p><p>1</p><p>1</p><p>2</p><p>2 ... ) é:</p><p>n</p><p>k ,�...,k</p><p>n</p><p>k</p><p>n k</p><p>k</p><p>1 r</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>���</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>���</p><p>��</p><p>�</p><p>��</p><p>�</p><p>�</p><p>���� � �� � ...�</p><p>1</p><p>1</p><p>2</p><p>��</p><p>� ��</p><p>�</p><p>��</p><p>�</p><p>�</p><p>��</p><p>� �</p><p>�</p><p>�...� �� � �-��n k k k</p><p>k</p><p>r</p><p>r</p><p>1 2 1</p><p>110 Matemática Discreta</p><p>Assim, a primeira identidade é provada. Agora:</p><p>n</p><p>k</p><p>n k</p><p>k</p><p>n k k k</p><p>1</p><p>r�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�� �</p><p>��</p><p>�</p><p>��</p><p>�</p><p>�</p><p>��� �</p><p>� � � ��</p><p>�</p><p>��</p><p>��1</p><p>2</p><p>1 2 1��...��</p><p>...</p><p>kr ��</p><p>�� �</p><p>�</p><p>�� � �</p><p>�� �</p><p>� �� � � �</p><p>� � �� �n</p><p>k n k</p><p>n k</p><p>k n k k</p><p>n k kr!</p><p>! !</p><p>!</p><p>! !</p><p>...</p><p>...</p><p>1 1</p><p>1</p><p>2 1 2</p><p>1 1��</p><p>� � �� �</p><p>!</p><p>! ... !k n k kr r1</p><p>Convenientemente, muitos dos termos fatoriais se cancelam; desse modo</p><p>teremos:</p><p>n</p><p>k</p><p>n k</p><p>k</p><p>� ��</p><p>n k k k</p><p>k</p><p>r</p><p>r1</p><p>1</p><p>2</p><p>1 2 1�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�� �</p><p>��</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�� � �</p><p>� � � ��</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�...</p><p>...</p><p>��� � � � �</p><p>n</p><p>k k � � kr</p><p>!</p><p>! ! ... !1 2</p><p>Σxemρlo 24</p><p>Utilize o teorema anterior para calcular</p><p>5</p><p>1,�2,�2</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�.</p><p>Temos que 1 + 2 + 2 = 5. Então, pelo teorema anterior, obtemos:</p><p>5</p><p>1 2 2</p><p>5</p><p>1 2 2</p><p>5 4 3 2</p><p>1 2 2</p><p>5</p><p>,� ,�</p><p>!</p><p>!�� !�� !</p><p>�� �� �� !</p><p>�� �� !</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>� �</p><p>�</p><p>� � �</p><p>� �</p><p>�</p><p>��� ��4 3</p><p>2</p><p>5 2 3 30�</p><p>� � � �</p><p>CONSIDERAÇÕES FINAIS</p><p>Neste capítulo, vimos que a análise combinatória está fundamentada em alguns</p><p>princípios básicos da contagem, como o princípio multiplicativo, o princípio aditivo e o</p><p>princípio da casa dos pombos.</p><p>Além disso, você aprendeu que podemos utilizar funções para contar o número</p><p>de elementos de subconjuntos especiais de um conjunto finito dado. Essas funções</p><p>são utilizadas para definir novas fórmulas de contagem, que são importantíssimas em</p><p>vários problemas de matemática, como no desenvolvimento polinomial.</p><p>ATIVIDADES</p><p>1. Uma pequena comunidade tem 10 mulheres, cada uma delas com 3 filhos. Se,</p><p>em um festival, uma mulher e uma criança forem selecionadas como “mãe e</p><p>filho do ano” (independentemente de serem mãe e filho de fato), quantas são as</p><p>possibilidades diferentes de escolhermos uma dupla vencedora?</p><p>2. Suponha que queremos colocar 10 livros na estante. Desses, 4 são de Matemática,</p><p>3 são de Química, 2 são de História e 1 é de Literatura. Os livros de mesmo assunto</p><p>devem ser colocados juntos. Quantos arranjos diferentes são possíveis?</p><p>Análise combinatória 111</p><p>3. Ao pendurar 9 bandeiras em uma linha, das quais 4 são brancas, 3 são vermelhas</p><p>e 2 são azuis, quantas formas diferentes são possíveis?</p><p>4. Se em um grupo de 12 pessoas 3 delas são escolhidas para ganhar uma viajem, de</p><p>quantas maneiras diferentes pode ocorrer a escolha?</p><p>REFERÊNCIAS</p><p>GERSTING, J. L. Fundamentos matemáticos para ciência da computação. 4. ed. São Paulo: LTC, 2001.</p><p>GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5. ed. Boston:</p><p>Addison-Wesley, 2004.</p><p>HAZZAN, S. Fundamentos da matemática elementar: combinatória, probabilidade. São Paulo: Atual, 2013.</p><p>v. 5.</p><p>ROSEN, K. H. Matemática discreta e suas aplicações. 6. ed. São Paulo: McGraw-Hill, 2009.</p><p>SANTOS, J. P. O.; MELLO, M. P.; MURARI, I. T. C. Introdução à análise combinatória. Rio de Janeiro: Ciência</p><p>Moderna, 2008.</p><p>112 Matemática Discreta</p><p>7</p><p>Funções geradoras e</p><p>partição de um inteiro</p><p>Funções geradoras são uma das invenções mais surpreendentes,</p><p>úteis e inteligentes da matemática discreta. De modo geral, funções ge-</p><p>radoras transformam problemas sobre sequências numéricas em pro-</p><p>blemas de funções de valor real. Isso é ótimo porque já conhecemos</p><p>várias propriedades e técnicas matemáticas para manipular funções de</p><p>valor real.</p><p>Graças às funções geradoras, podemos aplicar todo o nosso conhe-</p><p>cimento sobre funções aos problemas de sequências numéricas. Dessa</p><p>forma, podemos utilizar funções geradoras para resolver todos os tipos</p><p>de problemas de contagem. Há um grande espaço da matemática de-</p><p>dicada ao estudo de funções geradoras, portanto, neste capítulo, apre-</p><p>sentaremos apenas uma pequena abordagem do assunto.</p><p>Você irá aprender a calcular a função geradora ordinária</p><p>e a fun-</p><p>ção geradora exponencial de uma sequência numérica, a realizar ope-</p><p>rações em funções geradoras e utilizá-las para resolver problemas de</p><p>contagem. Por fim, aprenderá o conceito e a como representar a parti-</p><p>ção de um número inteiro positivo.</p><p>7.1 Funções geradoras</p><p>Vídeo Iniciaremos com a definição formal de função geradora ordinária de uma se-</p><p>quência numérica.</p><p>Definição</p><p>A função geradora ordinária (FGO) para a sequência numérica infinita (g</p><p>0</p><p>, g</p><p>1</p><p>, g</p><p>2</p><p>, ...) é a série de potência</p><p>formal</p><p>G x g g x g x g x g x</p><p>i</p><p>i</p><p>i� �� � � � ���</p><p>�</p><p>�</p><p>�0 1 2</p><p>2</p><p>3</p><p>3</p><p>0</p><p>Indicaremos a correspondência entre uma sequência e sua função de geração</p><p>com uma seta dupla-face (↔), da seguinte forma:</p><p>(g 0, g1, g3, ...) ↔ g0 + g1 x + g2 x</p><p>2 + g3 x</p><p>3 + …</p><p>Funções geradoras e partição de um inteiro 113</p><p>Por exemplo, aqui estão algumas sequências e suas funções geradoras:</p><p>(0, 0, 0, 0, ...) ↔ 0 + 0x + 0x² + 0x³ + ... = 0</p><p>(1, 0, 0, 0, ...) ↔ 1 + 0x + 0x² + 0x³ + ... = 1</p><p>(3, 2, 1, 0, ...) ↔ 3 + 2x + 1x² + 0x³ + ... = 3 + 2x + x²</p><p>Observamos que o padrão para fazermos correspondência entre uma sequên-</p><p>cia numérica e sua função geradora ordinária é: o i-ésimo termo na sequência (in-</p><p>dexação de 0) é o coeficiente de xi na função geradora.</p><p>Também podemos relacionar função geradora e sequências numéricas defini-</p><p>das por recorrência. Vejamos um exemplo.</p><p>Σxemρlo 1</p><p>Considere a sequência numérica (gk), onde gk = (k</p><p>2 + 1) para k = 0, 1, 2, 3. Descreva</p><p>(gk) e sua função geradora.</p><p>Temos que (gk) = (g0, g1, g2, …) = ((02 + 1), (12 + 1), (22 + 1), …) = (1, 2, 5, ...).</p><p>Sendo assim, a função geradora de (gk) é</p><p>G x x x � k x</p><p>i</p><p>i� � � � � � �� �� �</p><p>�</p><p>�1 2 5 12</p><p>0</p><p>2</p><p>�</p><p>De maneira análoga, podemos definir a função geradora ordinária de uma se-</p><p>quência numérica infinita.</p><p>Definição</p><p>A função geradora ordinária (FGO) para a sequência numérica finita (g</p><p>0</p><p>, g</p><p>1</p><p>, g</p><p>3</p><p>,</p><p>.</p><p>.., g</p><p>n</p><p>) é o polinômio</p><p>G x g g x g x g x g x g xn</p><p>n</p><p>i</p><p>n</p><p>i</p><p>i� �� � � � ��� �</p><p>�</p><p>�0 1 2</p><p>2</p><p>3</p><p>3</p><p>0</p><p>Observe que a função geradora ordinária para uma sequência numérica finita</p><p>(g0, g1, g3, ..., gn) também pode ser vista como uma série infinita</p><p>i=0</p><p>i</p><p>ig x</p><p>�</p><p>� , onde gi = 0</p><p>para todo i > n.</p><p>Acompanhe um exemplo de FGO para uma sequência numérica finita.</p><p>Σxemρlo 2</p><p>Qual a função geradora da sequência numérica (2, 3, 5, 7, 11, 13)?</p><p>Tem-se, por definição, que</p><p>114 Matemática Discreta</p><p>G x g x x x x x x</p><p>i</p><p>i</p><p>i� � � � � � � � �</p><p>�</p><p>�</p><p>0</p><p>5</p><p>2 3 4 52 3 5 7 11 13</p><p>Lembre-se de que a soma de uma série geométrica infinita</p><p>i</p><p>iz</p><p>�</p><p>�</p><p>0</p><p>�</p><p>, para |z|</p><p>1 4 9 16</p><p>1</p><p>1</p><p>1</p><p>,� ,� ,� ,�...</p><p>� ² � ³</p><p>� � �</p><p>�� � �</p><p>�</p><p>�� �</p><p>d</p><p>dx</p><p>x</p><p>x</p><p>x</p><p>x</p><p>0 1 4 9 1</p><p>1</p><p>1</p><p>1</p><p>,� ,� ,� ,�...</p><p>� ³ � ³</p><p>� � � �</p><p>�</p><p>�� � �</p><p>�� �</p><p>�� �x x</p><p>x</p><p>x x</p><p>x</p><p>Assim, a função geradora da sequência numérica dos quadrados é:</p><p>x � �x</p><p>� �x</p><p>1</p><p>1</p><p>�� �</p><p>�� � ³ .</p><p>Funções geradoras são particularmente úteis para resolver problemas de contagem.</p><p>Especificamente, problemas envolvendo a escolha de itens de um conjunto geralmen-</p><p>te levam a funções de geração interessantes. Quando funções geradoras são usadas</p><p>dessa forma, o coeficiente de xn é o número de maneiras de escolher n itens.</p><p>Antes de apresentarmos aplicações de funções geradoras, iremos enunciar uma</p><p>versão estendida do teorema binomial.</p><p>Definição</p><p>Considere m um número real e k um número inteiro não negativo. Então, o coeficiente binomial esten-</p><p>dido</p><p>m</p><p>k</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� é dado por:</p><p>m</p><p>k</p><p>m m m k</p><p>k</p><p>se k</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>��</p><p>� �� ���� � �� �</p><p>�</p><p>1 1</p><p>0</p><p>!</p><p>, e</p><p>m</p><p>k</p><p>se k</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�� �1 0,</p><p>118 Matemática Discreta</p><p>Vejamos um exemplo:</p><p>Σxemρlo 8</p><p>Encontre os valores binomiais estendidos de</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>3</p><p>2</p><p>e</p><p>1</p><p>2</p><p>3</p><p>�</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�</p><p>��</p><p>.</p><p>Temos, por definição, que</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�� � �� �</p><p>�</p><p>�� � �� �</p><p>�</p><p>3</p><p>2</p><p>3 4</p><p>2</p><p>3 4</p><p>2</p><p>6</p><p>!</p><p>e</p><p>1</p><p>2</p><p>3</p><p>1</p><p>2</p><p>1</p><p>2</p><p>1 1</p><p>2</p><p>2</p><p>3</p><p>1</p><p>2</p><p>1</p><p>2�</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>!</p><p>��</p><p>�</p><p>�</p><p>� �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>3</p><p>2</p><p>6</p><p>1</p><p>16</p><p>Se m = -n ∈ ℤ, com n ∈ ℕ, temos que</p><p>m</p><p>k</p><p>n</p><p>k</p><p>n k</p><p>k</p><p>k�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>��</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�� �� �</p><p>� ��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�1</p><p>1</p><p>Segundo a observação, se m é um número inteiro negativo, o coeficiente bino-</p><p>mial estendido pode ser escrito em termos do coeficiente binomial clássico. Agora,</p><p>vamos enunciar o teorema binomial estendido.</p><p>Teorema</p><p>Considerando x um número real com |x|</p><p>de modo que cada unidade receba ao mínimo um novo</p><p>funcionário.</p><p>Esse tipo de solução pode ser resumido no seguinte teorema.</p><p>Teorema</p><p>O número de modos distintos que podemos distribuir n objetos diferentes em k</p><p>compartimentos diferentes sem que nenhum fique vazio é dado por:</p><p>D n k</p><p>k</p><p>i</p><p>k i</p><p>i</p><p>k</p><p>i n,� � � �� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �� �</p><p>�</p><p>�</p><p>0</p><p>1</p><p>Aplicando esse teorema ao Exemplo 14, temos que</p><p>D</p><p>i</p><p>i ���������������������������</p><p>i</p><p>i6 3 1</p><p>3</p><p>3</p><p>0</p><p>3</p><p>6,� � � �� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �� �</p><p>�</p><p>� ����������������������������������������������������������������������������</p><p>�� �� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �� � � �� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �� � � �� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �� 1</p><p>3</p><p>0</p><p>3 0 1</p><p>3</p><p>1</p><p>3 1 1</p><p>3</p><p>2</p><p>30 6 1 6 2 22 06� � �</p><p>= 36 – 3 · 26 + 3</p><p>= 540</p><p>Na dissertação Resolução</p><p>de problemas combinatórios</p><p>utilizando funções gerado-</p><p>ras, defendida em 2013 por</p><p>Domingos Boaes Garcia,</p><p>ele apresenta a aplicação</p><p>de funções geradoras e</p><p>relações de recorrência</p><p>no cálculo do tamanho de</p><p>uma população de coelhos.</p><p>Vale a pena conferir!</p><p>Disponível em: https://sca.profmat-sbm.</p><p>org.br/sca_v2/get_tcc3.php?id=37752.</p><p>Acesso em: 5 mar. 2021.</p><p>Leitura</p><p>https://sca.profmat-sbm.org.br/sca_v2/get_tcc3.php?id=37752</p><p>https://sca.profmat-sbm.org.br/sca_v2/get_tcc3.php?id=37752</p><p>https://sca.profmat-sbm.org.br/sca_v2/get_tcc3.php?id=37752</p><p>Funções geradoras e partição de um inteiro 123</p><p>7.4 Sequência de Fibonacci</p><p>Vídeo Às vezes podemos encontrar funções geradoras interessantes, e relativamente</p><p>simples, para sequências mais complicadas. Por exemplo, aqui está uma função</p><p>geradora para os números de Fibonacci:</p><p>0 1 1 2 3 5 8 13 21</p><p>1</p><p>, , , , , , , , , ...</p><p>²</p><p>� � � � � � � � � x</p><p>� �x� �x</p><p>� � �</p><p>� �</p><p>É sabido que a função de recorrência que define os números de Fibonacci é bas-</p><p>tante complicada, mas sua função geradora ordinária é bem simples!</p><p>Vamos demonstrar, no teorema a seguir, a função geradora para a sequência</p><p>de Fibonacci.</p><p>Teorema</p><p>A sequência de Fibonacci, definida por: f0 = 0, f1 = 1 e fn = fn-1 + fn-2 (para n ≥ 2),</p><p>possui função geradora ordinária dada por</p><p>G x x</p><p>� �x� �x</p><p>� � �</p><p>� �1 ²</p><p>Demonstração</p><p>Vamos utilizar a sequência F(x) = f0 + f1x + f2x</p><p>2 + f3x</p><p>3 + f4x</p><p>4 + ... para encontrar G(x),</p><p>função geradora da sequência (0, 1, f1 + f0, f2 + f1, f2 + f3, ...). Observamos que</p><p>(0, 1, f1 + f0, f2 + f1, f2 + f3, …) = (0, 1, 0, 0, 0, …)</p><p>+ (0, f0, f1, f2, f3, …)</p><p>+ (0, 0, f0, f1, f2, ...)</p><p>e que</p><p>(0,1, 0, 0, 0, ...) ↔ x</p><p>(0, f0, f1, f2, f3, ...) ↔ xF(x)</p><p>(0, 0, f0, f1, f2, ...) ↔ x²F(x)</p><p>Portanto,</p><p>(0, 1 + f0, f1 + f0, f2 + f1, f3 + f2, ...) ↔ x + xF(x) + x²F(x)</p><p>Essa sequência é quase idêntica aos lados direitos das equações de Fibonacci.</p><p>O único defeito é que o segundo termo é 1 + f0, em vez de simplesmente 1. No</p><p>entanto, isso não é um problema, já que f0 = 0. Agora, se igualarmos F(x) com a</p><p>nova função x + xF(x) + x²F(x), calcularemos implicitamente todas as equações que</p><p>definem os números de Fibonacci de uma só vez, pois</p><p>x + xF(x) + x2F(x) = 0 + (1 + f0)x + (f1 + f0)x</p><p>2 + (f2 + f1)x</p><p>3 + (f3 + f2)x</p><p>4 + ...</p><p>Resolvendo para F(x), teremos a função geradora para a sequência de Fibonacci:</p><p>F x x xF x x F x� � � � � � � � �²</p><p>�� � � �</p><p>� �</p><p>F x x</p><p>� �x� �x1 2</p><p>124 Matemática Discreta</p><p>7.5 Partição de um inteiro</p><p>Vídeo Não é difícil perceber que quanto mais restrições possui um problema de con-</p><p>tagem, mais difícil é para encontrar sua solução. Vimos que uma ferramenta da</p><p>análise combinatória que facilita a resolução desses problemas é a função geradora</p><p>ordinária. Essa ferramenta é importante para resolver problemas que podem ser</p><p>traduzidos em equação do tipo x1 + x2 + ... + xn = r de números inteiros não negativos.</p><p>Consideremos agora o seguinte problema: de quantas maneiras diferentes po-</p><p>demos colocar quatro bolas idênticas em duas caixas idênticas de modo que ne-</p><p>nhuma caixa fique vazia?</p><p>Podemos resolver esse problema de um modo mais simples, sem precisar re-</p><p>correr a uma equação do tipo x1 + x2 + ... + xn = r. Note que o número 4 pode ser</p><p>escrito como:</p><p>• 4.</p><p>• 3 + 1.</p><p>• 2 + 2.</p><p>• 2 + 1 + 1.</p><p>• 1 + 1 + 1 + 1.</p><p>As diferentes maneiras de escrever o número 4 são chamadas de partições do</p><p>número 4.</p><p>Considerando cada parcela como uma caixa, temos que existem apenas duas</p><p>opções diferentes de colocar quatro bolas idênticas em duas caixas idênticas. A</p><p>saber, {3, 1} e {2, 2}.</p><p>Esse método, a princípio, é bem simples. Mas, ao considerarmos números maio-</p><p>res, notamos que o número de partições aumenta de maneira considerável. Por</p><p>exemplo, o número 200 possui 3.972.999.029.388 partições. Vamos estudar em</p><p>mais detalhes as partições de um número.</p><p>Definição</p><p>Dado um número inteiro positivo n, uma partição de n é uma coleção de números inteiros positivos</p><p>cuja soma é n. O número de partições de n será denotado por p(n).</p><p>Já vimos, como exemplo, que p(4) = 5 e p(200) = 3.972.999.029.388. Vamos es-</p><p>crever pk(n) para indicar o número de partições com k parcelas de um número</p><p>inteiro positivo n. Por exemplo, p2(4) = 2 e p3(4) = 1.</p><p>É fácil ver que</p><p>k</p><p>n</p><p>kp n p n</p><p>�</p><p>� � � � � �</p><p>0</p><p>Funções geradoras e partição de um inteiro 125</p><p>Observamos que uma partição de um número inteiro define uma sequência nu-</p><p>mérica. A partição p = {3, 2, 2, 1} do número n = 8, por exemplo, define a sequência</p><p>numérica (3, 2, 2, 1). Vamos então relacionar partições de um inteiro e a função</p><p>geradora de uma sequência numérica.</p><p>Teorema</p><p>Seja n um número inteiro positivo e p(n) o número de partições de n, a função</p><p>geradora para p(n) é:</p><p>n</p><p>n</p><p>k</p><p>k</p><p>p x x</p><p>x� �</p><p>� �� � �</p><p>�1 1</p><p>1</p><p>1</p><p>� �</p><p>Onde p(0) = 1.</p><p>Demonstração</p><p>Sabemos que</p><p>1</p><p>1</p><p>1 2 3</p><p>�</p><p>� � � � ��</p><p>x</p><p>x x x ,</p><p>1</p><p>1</p><p>1</p><p>2</p><p>2 4 6</p><p>�</p><p>� � � � ��</p><p>x</p><p>x x x ,</p><p></p><p>1</p><p>1</p><p>1 2 3</p><p>�</p><p>� � � � ��</p><p>x</p><p>x x x</p><p>m</p><p>m m m</p><p>Portanto,</p><p>k</p><p>kx</p><p>x x x x x x �</p><p>�</p><p>� �</p><p>� � � � ��� � � � � � �� ��</p><p>1</p><p>2 3 2 4 61</p><p>1</p><p>1 1</p><p>�</p><p>Assim, notamos que os coeficientes do termo xn derivam de um termo xb1 da</p><p>primeira série, de x b2 2 da segunda, e assim por diante, com bi ≥ 0 para todo i. Pela</p><p>regra da potenciação, temos que</p><p>b1 + 2b2 + 3b3 +… + mbm = m</p><p>Cada bi deve ser visto como o número de i’s que aparecem na partição de n, ou</p><p>seja, podemos escrever n como</p><p>N = (1 + 1 + ... + 1) + (2 + 2 + ... + 2) + ... + (m + m + ... + m)</p><p>onde temos b1 1’s no primeiro parêntese, b2 2’s no segundo e bm m’s no m-ésimo</p><p>parêntese. Assim, cada partição de um n contribui em uma unidade para o coefi-</p><p>ciente de xn. Portanto,</p><p>k</p><p>kx</p><p>x x x � � x x x �</p><p>�</p><p>� � � � � �� �</p><p>� � � � � �� � � � � � �� ��</p><p>1</p><p>1 1 1 1 1 2 2 2 2 2 21</p><p>1</p><p>1 1</p><p>�</p><p>Ou seja, a função geradora para as partições de n, em que nenhuma parte su-</p><p>pera m, é dado por</p><p>k</p><p>m</p><p>kx�</p><p>� �1</p><p>1</p><p>1</p><p>126 Matemática Discreta</p><p>7.6 Gráfico de uma partição</p><p>Vídeo Seja n um número inteiro positivo, o gráfico de uma partição de n é representado</p><p>por meio de um conjunto de n pontos no plano, onde em cada linha inserimos em or-</p><p>dem decrescente o número de pontos correspondentes a cada uma de suas partes.</p><p>Σxemρlo 15</p><p>Construa o gráfico para a partição {3, 2, 1, 1} do número 7.</p><p>Por definição, temos que a primeira linha do gráfico possui três pontos, a se-</p><p>gunda linha possui dois pontos e as duas últimas linhas possuem um ponto cada.</p><p>Portanto, o gráfico da partição {3, 2, 1, 1} é dado por:</p><p>Note que ao invertemos as linhas e as colunas do gráfico de uma partição de</p><p>um número inteiro n, obtemos o gráfico de outra partição de n. Isso nos leva à</p><p>seguinte definição:</p><p>Definição</p><p>Dado um número inteiro positivo n e uma partição p de n, a partição conjugada de p é a partição p de n,</p><p>obtida pela inversão das linhas e colunas do gráfico de p.</p><p>Vejamos um exemplo:</p><p>Σxemρlo 16</p><p>Determine a partição conjugada da partição p = {4, 2, 1} do número 7.</p><p>Temos, por definição, que o gráfico da partição {4, 2, 1} é dado por</p><p>Funções geradoras e partição de um inteiro 127</p><p>Se invertemos as linhas e colunas, vamos obter o seguinte gráfico:</p><p>que corresponde à partição {3, 2, 1, 1}, ou seja, p = {3, 2, 1, 1}.</p><p>Definição</p><p>Dado um número inteiro positivo n e uma partição p de</p><p>n, a partição conjugada de p é chamada de</p><p>autoconjugada se p = p.</p><p>Se considerarmos, por exemplo, a partição p = {3, 2, 1} de n = 6:</p><p>temos que p = p .</p><p>CONSIDERAÇÕES FINAIS</p><p>Neste capítulo você aprendeu a relacionar sequências numéricas com funções</p><p>geradoras, a função geradora polinomial e a função geradora exponencial, além de</p><p>conceitos fundamentais de teoria de conjuntos, as diferentes formas de descrevê-</p><p>-los e como relacioná-los com objetos da vida real.</p><p>Aprendeu a realizar várias operações básicas entre as funções geradoras e</p><p>como essas operações são traduzidas em termos de sequências numéricas, além</p><p>de construir partições de um número inteiro não negativo e relacionar partições de</p><p>um inteiro e funções geradoras.</p><p>Por fim, aprendeu como podemos resolver problemas de contagem por meio</p><p>de funções geradoras.</p><p>ATIVIDADES</p><p>1. Mostre que a função geradora da sequência (1, -1, 1, -1, ...) é</p><p>G x � �x x � �x �</p><p>x</p><p>� � � � � � � �</p><p>�</p><p>1 1</p><p>1</p><p>² ³ ...</p><p>2. Encontre o coeficiente de x³ no desenvolvimento binomial de 1</p><p>1</p><p>2�� �x .</p><p>3. Encontre a sequência gerada pela função geradora ordinária</p><p>f x x</p><p>x</p><p>� � �</p><p>�� �</p><p>2</p><p>1 2</p><p>2</p><p>128 Matemática Discreta</p><p>REFERÊNCIAS</p><p>GERSTING, J. L. Fundamentos Matemáticos para Ciência da Computação 4 ed. São Paulo: LTC, 2001.</p><p>GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5 ed. Boston: Addison-</p><p>Wesley, 2004.</p><p>ROSEN, K. H. Matemática discreta e suas aplicações. 6 ed. São Paulo: McGraw-Hill, 2009.</p><p>Gabarito 129</p><p>GABARITO</p><p>1 Fundamentos de lógica matemática e métodos de</p><p>demonstração</p><p>1.</p><p>a) Teorema</p><p>Se a é um número inteiro par e b é um número inteiro ímpar, então a soma a + b é</p><p>um número inteiro ímpar.</p><p>Demonstração</p><p>Seja a um número inteiro par e b um número inteiro ímpar, pela definição de</p><p>número inteiro par, sabemos que a = 2k e, pela definição de número inteiro ímpar,</p><p>b = 2t + 1. Logo, a soma a + b é</p><p>a + b = 2k + (2t + 1) = 2(k + t) + 1 = 2t1 + 1, ou seja, a + b = 2t1 + 1, onde t1 = k + t.</p><p>Isso mostra que a + b tem a forma de um número inteiro ímpar. Podemos, assim,</p><p>concluir que a + b é um número inteiro ímpar.</p><p>b) Teorema</p><p>Se a é um número inteiro par e b um número inteiro ímpar, então o produto ab é</p><p>um número par.</p><p>Demonstração</p><p>Seja a um número inteiro par e b um número inteiro ímpar, pela definição de</p><p>número inteiro par, sabemos que a = 2k e, pela definição de número inteiro ímpar,</p><p>b = 2t + 1. Logo, o produto ab é</p><p>ab = (2k)(2t + 1) = 2k2t + 2k = 2(2kt + k), ou seja, ab = 2k1, onde k1 = 2kt + k.</p><p>Isso mostra que ab tem a forma de um número inteiro par. Podemos, assim,</p><p>concluir que ab é um número inteiro par.</p><p>2. Teorema</p><p>Se a é um número natural e a² é ímpar, então a é um número ímpar.</p><p>Demonstração</p><p>Nossa proposição é “p: a² é ímpar → q: a é ímpar”. Vamos demonstrar que a</p><p>proposição equivalente “~q: a é par → ~p: a² é par” é verdadeira. Com efeito, se a é</p><p>par existe k natural tal que a = 2k.</p><p>Logo, a² = (2k)² = 4k² = 2(2k²) = 2k2, onde k2 = 2k², ou seja, a² é um número par,</p><p>provando que a contrapositiva do teorema é verdadeira. Podemos, então, concluir</p><p>que o teorema é verdadeiro.</p><p>3.</p><p>Teorema</p><p>Se a é um número inteiro par e b é um número inteiro ímpar, então a soma a + b é</p><p>um número inteiro ímpar.</p><p>130 Matemática Discreta</p><p>Demonstração</p><p>Nossa hipótese é “p: a é um número inteiro par e b é um número inteiro ímpar”</p><p>e nossa tese é “q: a + b é um número inteiro ímpar”. Vamos então negar q, isto é,</p><p>“∼q: a + b é um número par”.</p><p>Suponha, então, que a = 2k1, b = 2t + 1 e a + b é um número par. Digamos que</p><p>a + b = 2k2, onde, por um lado, a + b = 2k1 + (2t + 1) e, por outro lado, a + b = 2k2.</p><p>Daí, 2k1 + (2t + 1) = 2k2 ⇒ 2(-k1 - t + k2) = 1. Isso nos diz que 1 é um número par,</p><p>obviamente uma contradição, de onde devemos ter que a + b é um número ímpar.</p><p>4.</p><p>Teorema</p><p>Se n é um número natural, 1² + 3² + 5² + ... + (2n - 1)² =</p><p>n 2n�-�1 2n�+�1</p><p>3</p><p>� �� �</p><p>.</p><p>Demonstração</p><p>Vamos, inicialmente, mostrar que o resultado é válido para n = 1. Se n = 1 temos</p><p>que 1² =</p><p>1 2(1) -1) 2(1)�+�1</p><p>3</p><p>=1(1)(3)</p><p>3</p><p>= 3</p><p>3</p><p>� � � �</p><p>= 1, provando que o teorema é válido no</p><p>caso n = 1.</p><p>Assumindo que o teorema é válido para n = k, ou seja, assumindo que</p><p>1² + 3² + 5² + ... + (2k - 1)² =</p><p>k 2k�-�1 2k�+�1</p><p>3</p><p>� �� � ,</p><p>Vamos mostrar que o teorema é válido para n = k + 1, ou seja, mostraremos que</p><p>1² + 3² + 5² + ... + (2k + 1)² = k�+�1 2k�+�1 2k�+�3</p><p>3</p><p>� �� �� � .</p><p>De fato,</p><p>1² + 3² + 5² + ... + (2k - 1)² + (2k + 1)² =</p><p>k 2k�-�1 2k�+�1</p><p>3</p><p>� �� � + (2k + 1)²</p><p>����������������������������������������������������������������������=</p><p>2k+1 k 2k-1 +3 2k+1</p><p>3</p><p>� � � � � ��� ��</p><p>�=</p><p>3</p><p>(2k +1)(2k +5k +3)2</p><p>�=</p><p>k+1 2k+1 2k+3</p><p>.</p><p>6</p><p>� �� �� �</p><p>Provando, assim, que 1² + 2² + 3² + ... + (k + 1)² �=</p><p>k+1 2k+1 2k+3</p><p>.</p><p>6</p><p>� �� �� �</p><p>Desse modo, podemos concluir que o teorema é válido.</p><p>2 Teoria de conjuntos</p><p>1.</p><p>Demonstração</p><p>Seja x ∈ A∩B, significa que (x ∈ A e x ∈ B), que pode ser lido como (x ∈ B e x ∈ A). Isso</p><p>significa que x ∈ B∩A, ou seja, A∩B ⊂ B∩A. De modo análogo, temos que B∩A ⊂ A∩B</p><p>e podemos concluir que A∩B = B∩A.</p><p>Gabarito 131</p><p>2.</p><p>Demonstração</p><p>Para provar essa propriedade, utilizaremos as leis distributivas da lógica matemática.</p><p>Seja:</p><p>x ∈ A∪(B∩C) ↔ x ∈ A ou x ∈ B∩C ↔ x ∈ A ou (x ∈ B e x ∈ C)</p><p>↔ (x ∈ A ou x ∈ B) e (x ∈ A ou x ∈ C) ↔ x ∈ A∪B e x ∈ A∪C</p><p>↔ x ∈ (A∪B)∩(A∪C)</p><p>Provando que A∪(B∩C) = (A∪B)∩(A∪C).</p><p>3.</p><p>Demonstração</p><p>Seja:</p><p>x ∈ (A∪B)C ↔ x ∉ A∪B ↔ ~(x ∈ A∪B) ↔ ~(x ∈ A ou x ∈ B)</p><p>↔ ~(x ∈ A) e ~(x ∈ B) ↔ x ∉ A e x ∉ B</p><p>↔ x ∈ AC e x ∈ BC ↔ x ∈ AC∩BC.</p><p>Provando que (A∪B)C = AC∩BC.</p><p>4.</p><p>Demonstração</p><p>Temos que:</p><p>x ∈ A\B ↔ x ∈ A e x ∉ B ↔ x ∉ AC e x ∈ BC</p><p>↔ x ∈ BC e x ∉ AC ↔ x ∈ BC\AC.</p><p>Provando que A\B = BC\AC.</p><p>3 Conjuntos numéricos</p><p>1.</p><p>Demonstração</p><p>Suponha que a, b > 0 e a | b, ou seja, b = ak com k ∈  . Como a e b são positivos,</p><p>temos que k ≥ 1. Multiplicando por a > 0, temos que ak ≥ a, ou seja, a ≤ b.</p><p>2.</p><p>Demonstração</p><p>Note que:</p><p>p</p><p>q</p><p>+ r</p><p>s</p><p>+ c</p><p>d</p><p>=</p><p>sp+qr</p><p>qs</p><p>+ c</p><p>d</p><p>=</p><p>d sp+qr +qsc</p><p>qsd</p><p>=</p><p>dsp+dqr+qsc</p><p>qsd</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� �</p><p>Por outro lado,</p><p>p</p><p>q</p><p>+ r</p><p>s</p><p>+ c</p><p>d</p><p>= p</p><p>q</p><p>+ dr�+�sc</p><p>sd</p><p>=</p><p>sdp�+�q dr�+�sc</p><p>qsd</p><p>= dsp��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � ++�dqr�+�qsc</p><p>qsd</p><p>Ou seja, p</p><p>q</p><p>+ r</p><p>s</p><p>+ c</p><p>d</p><p>= p</p><p>q</p><p>+ r</p><p>s</p><p>+ c</p><p>d</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� .</p><p>132 Matemática Discreta</p><p>3.</p><p>Demonstração</p><p>Se a ≡ b mod m e c ≡ d mod m, então, por definição, existem k1, k2 ∈  , tais que</p><p>a - b = mk1 e c - d = mk2, em que a - b + c - d = mk1 + mk2, ou seja, (a + c) - (b + d) = m(k1 + k2).</p><p>Isso significa que a + c ≡ b + d mod m.</p><p>4.</p><p>Demonstração</p><p>Temos que a é par se, e somente se, existe k ∈  , tal que a = 2k, e isso ocorre se,</p><p>e somente se, a - 0 = 2k, ou seja, se, e somente se, a ≡ 0 mod 2.</p><p>Analogamente, temos que a é ímpar se, e somente se, existe k ∈  , tal que a = 2k + 1,</p><p>e isso ocorre se, e somente se, a - 1 = 2k, ou seja, se, e somente se, a ≡ 1 mod 2.</p><p>4 Relações</p><p>1. Demonstração</p><p>Sabendo que A ⊂ B, queremos provar que A x C ⊂ B x C. Para isso, precisamos</p><p>mostrar que se (x, y) ∈ A x C, então (x, y) ∈ B x C. Seja então (x, y) ∈ A x C, pela</p><p>definição de produto cartesiano, temos x ∈ A e y ∈ C. Como A ⊂ B, temos que x ∈ B,</p><p>ou seja, x ∈ B e y ∈ C, provando que (x, y) ∈ B x C. Portanto, A x C ⊂ B x C.</p><p>2. Demonstração</p><p>Temos que:</p><p>(x, y) ∈ (A∩B) x C ↔ x ∈ (A∩B) e y ∈ C</p><p>↔ (x ∈ A e x ∈ B) e y ∈ C</p><p>↔ (x ∈ A e y ∈ C) e (x ∈ B e y ∈ C)</p><p>↔ (x, y) ∈ A x C e (x, y) ∈ B x C</p><p>↔ (x, y) ∈ (A x C)∩(B x C)</p><p>Portanto, (A∩B) x C = (A x C)∩(B x C).</p><p>3. Demonstração</p><p>Pela definição de A, temos que A = {1, 2, 3, 4, 5, 6, 7}. Sendo assim:</p><p> � � �� � � � � � � � � � � � �{ , | }x �y A A �x y 9 2,�7 ,� 3,�6 ,� 4,�5 ,� 5,�4 ,� 6,�3�� � � �� �,� 7,�2</p><p>Onde, Dom 2,�3,�4,�5,�6,�7� � � � � e Im = 2,�3,�4,�5,�6,�7� � � � .</p><p>Observamos também que  � �1 . Sendo assim, Dom Dom �� � � � �1 e</p><p>Im Im �� � � � �1 .</p><p>4. Demonstração</p><p>Para verificar que  � � � �{ x �y |x y�mod�m, } é uma relação de equivalência, vamos</p><p>demonstrar que essa relação é reflexiva, simétrica e transitiva.</p><p>É reflexiva: note que, para todo x ∈ ℤ, temos x – x =</p><p>0 · m, ou seja, x ≡ x mod m.</p><p>É simétrica: suponha que x ≡ y mod m. Então, existe k ∈ ℤ, tal que x – y = km.</p><p>→ y – x = (-k) m → y ≡ x mod m.</p><p>Gabarito 133</p><p>É transitiva: suponha que x ≡ y mod m e y ≡ z mod m. Assim, existem k1, k2 ∈ ℤ, tal</p><p>que x – y = k1m e y – z = k2m. Então, temos que:</p><p>→ (x – y) + (y – z) = k1m + k2m</p><p>→ x – z = (k1 + k2)m</p><p>Com k1 + k2 ∈ ℤ. Assim, x ≡ z mod m.</p><p>5 Funções discretas</p><p>1.</p><p>Demonstração</p><p>Seja y ∈ f(A∩B), existe x ∈ A∩B tal que f(x) = y. Então, x ∈ A e, portanto, y ∈ f(A). Também,</p><p>x ∈ B e, portanto, y ∈ f(B). Logo, y ∈ f(A)∩f(B). Provando que f(A∩B) ⊂ f(A)∩f(B).</p><p>2.</p><p>Demonstração</p><p>Temos que:</p><p>x ∈ f–1(A∪B) ↔ f(x) ∈ A∪B</p><p>↔ f(x) ∈ A ou f(x) ∈ B</p><p>↔ x ∈ f–1(A) ou x ∈ f–1(B)</p><p>↔ x ∈ f–1(A)∪f–1(B)</p><p>Provando que f–1(A∪B) = f–1(A)∪f–1(B).</p><p>3.</p><p>Demonstração</p><p>Suponhamos que existem x1, x2 ∈ ℕ tais que f(x1) = f(x2). Vamos mostrar que x1 = x2.</p><p>De fato, se f(x1) = f(x2), então 4x1 + 7 = 4x2 + 7, onde 4x1 = 4x2 e, assim, x1 = x2, onde</p><p>f é injetora.</p><p>4.</p><p>Demonstração</p><p>Basta escolhermos x1 = 1 e x2 = -1 e teremos f(x1) = f(x2) com x1 ≠ x2, ou seja, f não</p><p>é injetora.</p><p>5.</p><p>Demonstração</p><p>Para todo y ∈ ℕ, temos que, se x y�-�7</p><p>4</p><p>= , então:</p><p>f x = f y�-�7</p><p>4</p><p>= 4 y�-�7</p><p>4</p><p>+ 7 = y - 7 + 7 = y� � �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � �</p><p>Onde f é sobrejetora.</p><p>Se o domínio fosse o conjunto dos números naturais, então f não seria sobrejetora.</p><p>134 Matemática Discreta</p><p>6 Análise combinatória</p><p>1. Considerando M = {M1, M2, …, M10} o conjunto das mulheres e Fi = {Fi1, Fi2, Fi3} o</p><p>conjunto dos filhos da mulher i, como não importa o laço de maternidade entre</p><p>eles, temos que existem 10 possibilidades para escolher a mulher e 3 possibilidades</p><p>para escolher o filho. Sendo assim, no total temos T = |M| · |F| = 10 · 30 = 300</p><p>maneiras diferentes para realizar nossa escolha.</p><p>2. Considerando M = {Livros de Matemática}, Q = {Livros que Química}, H = {Livros de</p><p>História}, L = {Livro de Literatura}, temos que existem 4! maneiras de organizar os</p><p>livros de Matemática, 3! maneiras de organizar os livros de Química, 2! maneiras</p><p>de organizar os livros de História e 1! maneira de organizar os livros de Literatura.</p><p>Sendo assim, existem 4! · 3! · 2! · 1! = 288 modos de organizar os livros na seguinte</p><p>ordem: MQHL. No entanto, a ordem em que os livros estão organizados pode ser</p><p>diferente (por exemplo, QMHL), e sabemos que existem 4! maneiras diferentes de</p><p>escolher a ordem de organização dos livros por tema. Sendo assim, o número total</p><p>de arranjos em que podemos organizar os livros é 288 · 4! = 6.912.</p><p>3. Fazendo n1 = 4, n2 = 2, n3 = 3 e n = 9, temos que n1 + n2 + n3 = n, pois 4 + 2 + 3 = 9,</p><p>e estamos interessados em encontrar</p><p>n</p><p>n ,�n ,�n</p><p>�=�</p><p>9</p><p>4,�2,�3</p><p>�=� 9!</p><p>4!�·�3!�·�2!</p><p>�=�1.</p><p>1 2 3</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� 2260</p><p>pelo teorema multinomial. Portanto, existem 1.260 formas possíveis nessas</p><p>configurações.</p><p>4. Basta escolhermos 3 pessoas entre as 12 disponíveis. Não estamos preocupados</p><p>com a ordem da escolha, mas sim com quais pessoas serão escolhidas. O número de</p><p>maneiras de fazer isso é:</p><p>C =</p><p>12</p><p>3</p><p>= 12!</p><p>3! 12-3 !</p><p>=12�·�11�·�10�·�9!</p><p>3!�·�9!</p><p>=12�·�</p><p>12</p><p>3 �</p><p>�</p><p>�</p><p>�</p><p>�</p><p>� � �</p><p>111�·�10</p><p>3</p><p>=220</p><p>Portanto, existem 220 modos diferentes para escolher as 3 pessoas.</p><p>7 Funções geradoras e partição de um inteiro</p><p>1. Sabemos que</p><p>(1, 1, 1, 1, ...) ↔ 1+�x+x +�x +�...= 1</p><p>1�-�x</p><p>2 3</p><p>Substituindo x por -x nos dois lados da igualdade, temos que</p><p>1+ -x + -x +� -x +�...= 1</p><p>1- -x</p><p>2 3� � � � � � � �</p><p>Ou seja,</p><p>1-�x+x -x +�...= 1</p><p>1+x</p><p>2 3</p><p>Provando que a função geradora de (1, -1, 1, -1, ...) é</p><p>G x = 1</p><p>1+x</p><p>� �</p><p>2. Utilizando o teorema binomial, temos:</p><p>1+x =</p><p>1</p><p>2</p><p>p</p><p>x =</p><p>1</p><p>2</p><p>· 1</p><p>2</p><p>-1 ·&�· 1</p><p>2</p><p>-p+11</p><p>2</p><p>p=0</p><p>¥</p><p>p</p><p>p=0</p><p>¥</p><p>å å� �</p><p>�</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>��</p><p>�</p><p>�</p><p>�</p><p>�</p><p>p!</p><p>x ,p</p><p>Gabarito 135</p><p>Logo, o coeficiente de x3 é</p><p>1</p><p>2</p><p>1</p><p>2</p><p>-1 1</p><p>2</p><p>-3+1</p><p>3!</p><p>= 1</p><p>16</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>�</p><p>3. Sabemos que</p><p>1</p><p>1-x</p><p>=1+�x+x +�x +&�2 3</p><p>Substituindo x por 2x nos dois lados da igualdade, temos que</p><p>1</p><p>1-2x</p><p>=1+�2x+4x +�8x +16x +�...2 3 4</p><p>Multiplicando os dois lados por 2x², tem-se</p><p>2x</p><p>1-2x</p><p>=2x +�4x +8x +�16x +32x +�&</p><p>2</p><p>2 3 4 5 6</p><p>Logo, f(x) é a função geradora da sequência (0, 0, 2, 4, 8, 16, 32, …).</p><p>WELINGTON SANTOS</p><p>MATEMÁTICA DISCRETA</p><p>Código Logístico</p><p>59915</p><p>ISBN 978-65-5821-012-2</p><p>9 7 8 6 5 5 8 2 1 0 1 2 2</p><p>da Nova Zelândia e s: π</p><p>2</p><p>”.</p><p>Fundamentos de lógica matemática e métodos de demonstração 19</p><p>As proposições matemáticas recebem nomes especiais conforme seu grau de</p><p>importância.</p><p>Como vimos, os axiomas são proposições presumidamente assumidas como verdadeiras, ou seja,</p><p>que não requerem provas.</p><p>Observe os seguintes exemplos de axiomas da adição de números reais:</p><p>• Associatividade: sejam a, b, c ∈ ℝ, tem-se (a + b) + c = a + (b + c).</p><p>• Comutatividade: sejam a, b ∈ ℝ, tem-se a + b = b + a.</p><p>Um teorema é uma sentença matemática que pode ser provada como verdadeira.</p><p>Podemos citar como exemplo o famoso Teorema de Pitágoras: em qualquer</p><p>triângulo retângulo, o quadrado do comprimento da hipotenusa é igual à soma dos</p><p>quadrados dos comprimentos dos catetos.</p><p>Um lema é um teorema de menor importância que pode ser utilizado para demonstrar teoremas</p><p>mais importantes.</p><p>Nesse sentido, ao nos depararmos com um teorema complicado, para realizar-</p><p>mos a sua demonstração de modo simples, o dividimos em vários lemas. Como</p><p>exemplo, vamos considerar o importantíssimo lema que é utilizado para demons-</p><p>trar o algoritmo da divisão de números inteiros.</p><p>Lema – Método de divisão de Euclides</p><p>Sejam a e b inteiros, tais que a ≥ 0 e b > 0, então existem q e r, quociente e resto</p><p>respectivamente, tais que a = bq + r e 0 ≤ r</p><p>proposição é “p: a³ é múltiplo de 3 → q: a é múltiplo de 3”. Vamos de-</p><p>monstrar que a proposição equivalente “~q: a não é múltiplo de 3 → ∼p: a³ não é</p><p>múltiplo de 3” é verdadeira. Com efeito, note que se a não é múltiplo de 3, então</p><p>a = 3k1 + 1 ou a = 3k2 + 2. Analisando ambos os casos:</p><p>• Se a = 3k1 + 1, temos:</p><p>a³ = (3k1 + 1)³</p><p>= (3k1 + 1)² (3k1 + 1)</p><p>= 27k1³ + 9k1² + 9k1 + 1</p><p>= 3(9k1³ + 3k1² + 3k1) + 1</p><p>= 3k3 + 1</p><p>Onde k3 = 9k1³ + 3k1² + 3k1.</p><p>Existe mais de uma</p><p>maneira de se demons-</p><p>trar um teorema! Um dos</p><p>teoremas mais impor-</p><p>tantes que estudamos e</p><p>ensinamos para os alunos</p><p>da educação básica é o</p><p>Teorema de Pitágoras.</p><p>Na página Decifrando a</p><p>Matemática, da Unicamp,</p><p>você vai encontrar vários</p><p>caminhos diferentes para a</p><p>demonstração do Teorema</p><p>de Pitágoras, além de</p><p>encontrar boas aborda-</p><p>gens para o ensino desse</p><p>teorema.</p><p>Disponível em: www.ime.unicamp.</p><p>br/~apmat/teorema-de-pitagoras/.</p><p>Acesso em: 5 mar. 2021.</p><p>Saiba mais</p><p>http://www.ime.unicamp.br/~apmat/teorema-de-pitagoras/</p><p>http://www.ime.unicamp.br/~apmat/teorema-de-pitagoras/</p><p>24 Matemática Discreta</p><p>• Se a = 3k2 + 2, temos:</p><p>a³ = (3k2 + 2)³</p><p>= (3k2 + 2)²(3k2 + 2)</p><p>= 27k2³ + 18k2² + 36k2 + 6 + 2</p><p>= 3(9k2³ + 6k2² + 12k2 + 2) + 2</p><p>= 3k4 + 2</p><p>Onde k4 = 9k2³ + 6k2² + 12k2.</p><p>Sendo assim, a³ = 3k3 + 2 ou a³ = 3k4+2, provando que a³ não é múltiplo de três,</p><p>ou seja, a contrapositiva do teorema é verdadeira. Podemos concluir, portanto, que</p><p>o teorema é verdadeiro.</p><p>1.3 Demonstração por contradição</p><p>Vídeo</p><p>Esse método consiste em utilizar uma contradição para mostrar que uma pro-</p><p>posição é verdadeira e tem como inspiração a seguinte tabela-verdade:</p><p>p q ~p ∼p → q</p><p>V V F V</p><p>V F F V</p><p>F V V V</p><p>F F V F</p><p>Observando as duas primeiras linhas da tabela-verdade, temos que p é verda-</p><p>deira sempre que ~p → q é verdadeira. Isso significa que para mostrarmos que</p><p>uma proposição p é verdadeira, basta encontrarmos q, tal que ~p → q é verdadeira.</p><p>Resumidamente, o método de demonstração por contradição consiste em</p><p>afirmar a hipótese, negar a tese e chegar a uma contradição. Vejamos alguns</p><p>exemplos de aplicação do método de demonstração por contradição.</p><p>Σxemρlo 14</p><p>Utilize o método de demonstração por contradição para provar que o único</p><p>número que, quando somado com ele mesmo, resulta no próprio número é o zero.</p><p>Queremos demonstrar o seguinte teorema: Se a + a = a, então a = 0. Para isso,</p><p>vamos utilizar o método da demonstração por contradição. Nossa hipótese p é</p><p>“a + a = a” e nossa tese q é “a = 0”. Vamos então negar q, ou seja, ~q: a ≠ 0.</p><p>Suponha então que a + a = a e a ≠ 0. Temos que 2a = a, e como a ≠ 0, podemos</p><p>realizar a divisão por a (se a = 0, a divisão não pode ser realizada, afinal, não existe</p><p>divisão por zero).</p><p>Fundamentos de lógica matemática e métodos de demonstração 25</p><p>Finalmente, 2a</p><p>a</p><p>a</p><p>a</p><p>= . Concluímos que 2 = 1. Isso é uma contradição; logo, não</p><p>podemos ter a ≠ 0, então a = 0.</p><p>Agora, vamos utilizar o método de demonstração por contradição para demons-</p><p>trar o seguinte teorema, que já foi demonstrado pelo método de demonstração direta.</p><p>Σxemρlo 15</p><p>Utilize o método de demonstração por contradição para provar o seguinte teo-</p><p>rema: Se a e b são dois números inteiros pares, então a soma a + b é um número</p><p>inteiro par.</p><p>Nossa hipótese é “p: a e b são números inteiros pares” e nossa tese é “q: a + b é</p><p>um número inteiro par”. Vamos então negar q, isto é, ∼q: a + b é um número ímpar.</p><p>Considere que:</p><p>• a = 2k1</p><p>• b = 2k2</p><p>• a + b é um número ímpar</p><p>Logo, a + b = 2k3 + 1, onde, por um lado, a + b = 2k1 + 2k2 e, por outro lado, a + b = 2k3 + 1.</p><p>Daí, 2k1 + 2k2 = 2k3 + 1 ⇒ 2(k1 + k2 - k3) = 1. Isso nos diz que 1 é um número par, obvia-</p><p>mente uma contradição, da qual obtemos que a + b é um número par.</p><p>1.4 Demonstração por absurdo</p><p>Vídeo Esse método consiste em assumir que a hipótese e a negação da tese são</p><p>verdadeiras, para construir uma linha de raciocínio que nos leve a um absur-</p><p>do. A demonstração por absurdo tem como inspiração a seguinte tautologia</p><p>P: (p → q) ↔ (p ∧ ∼q) → c, onde c é uma contradição. Essa tautologia pode ser veri-</p><p>ficada pela tabela-verdade a seguir.</p><p>p q c ∼q p ∧ ∼q p → q p ∧ ∼q → c P</p><p>V V F F F V V V</p><p>V F F V V F F V</p><p>F V F F F V V V</p><p>F F F V F V V V</p><p>Sendo assim, para demonstrar que um teorema é verdadeiro pelo método de</p><p>demonstração por absurdo:</p><p>1. Assumimos que a hipótese e a negação da tese são verdadeiras.</p><p>2. Construímos uma linha de raciocínio de modo a encontrarmos um absurdo.</p><p>26 Matemática Discreta</p><p>Considere o seguinte exemplo de aplicação do método de demonstração por</p><p>absurdo.</p><p>Σxemρlo 16</p><p>Demonstre o seguinte teorema pelo método de demonstração por absurdo: Se</p><p>a é um número natural e a² é par, então a é um número par.</p><p>Para demonstrarmos por absurdo o teorema, temos que nossa hipótese é “p: a²</p><p>é par” e nossa tese “q: a é par”. Suponha que p e ∼q, “a é ímpar”, sejam verdadeiras.</p><p>Se a é ímpar, a = 2k1 + 1, de onde</p><p>a² = (2k1 + 1)²</p><p>= 4k1² + 4k1 + 1</p><p>= 2(2k1² + 2k1) + 1</p><p>= 2k2 + 1</p><p>Onde k2 = 2k1² + 2k1. Isto é, a² é par e ímpar ao mesmo tempo. Um absurdo!</p><p>Portanto, o teorema é válido.</p><p>1.5 Demonstração por indução finita</p><p>Vídeo Em matemática discreta os principais problemas de estudo são problemas de</p><p>contagem em espaços discretos, por exemplo: o espaço formado por todas as ida-</p><p>des dos cidadãos brasileiros. Desse modo, o principal método de demonstração</p><p>que utilizamos é o método da indução finita. Esse método é utilizado para de-</p><p>monstrar teoremas como os seguintes.</p><p>Teorema</p><p>A soma dos n primeiros números naturais é n n� ��� �1</p><p>2</p><p>.</p><p>Note que o teorema diz que se somarmos, por exemplo, 1 + 2 + 3 + 4 o resultado</p><p>será 4 4 1</p><p>2</p><p>4 5</p><p>2</p><p>20</p><p>2</p><p>10</p><p>�� �</p><p>�</p><p>� �</p><p>� � .</p><p>Teorema</p><p>A soma dos quadrados dos n primeiros números naturais é n n n� � � ��� � �� �1 2 1</p><p>6</p><p>.</p><p>Utilizando o teorema podemos concluir, por exemplo, que a soma 1² + 2² + 3² é</p><p>igual a</p><p>3 3 1 2 3 1</p><p>6</p><p>3 4 7</p><p>6</p><p>14</p><p>�� � � � �� �</p><p>�</p><p>� �� �</p><p>� .</p><p>Mas como podemos demonstrar que esses teoremas são válidos para qualquer</p><p>número? O método da indução finita consiste nos seguintes passos:</p><p>Fundamentos de lógica matemática e métodos de demonstração 27</p><p>Mostrar que o teorema é válido</p><p>para o menor n possível que</p><p>satisfaz a hipótese.</p><p>Assumir que o teorema é válido</p><p>para n = k.</p><p>1</p><p>2</p><p>Utilizar o fato de o teorema ser</p><p>válido para n = k para demonstrar</p><p>que o teorema é verdadeiro para</p><p>n = k + 1.</p><p>3</p><p>Podemos observar pelo passo 3 que a principal ideia da demonstração por</p><p>indução finita é mostrar que o teorema é sempre válido para o próximo núme-</p><p>ro. Vamos utilizar o método de indução para demonstrar os teoremas utilizados</p><p>como exemplos.</p><p>Teorema</p><p>A soma dos n primeiros números naturais é n n� ��� �1</p><p>2</p><p>.</p><p>Demonstração</p><p>Vamos inicialmente mostrar que o resultado é válido para n = 1. Se n = 1, temos</p><p>que 1 =</p><p>1 1� ��� �</p><p>�</p><p>1</p><p>2</p><p>2</p><p>2</p><p>= 1, provando que o teorema é válido para n = 1.</p><p>Assumindo que o teorema é válido para n = k, ou seja, assumindo que</p><p>1 + 2 + 3 + ... + k =</p><p>k k� ��� �1</p><p>2</p><p>Vamos mostrar que o teorema é válido para n = k + 1, ou seja, mostraremos que</p><p>1 + 2 + 3 + ... + k + (k + 1) = �</p><p>k� � k� ��� � �� �1 2</p><p>2</p><p>De fato,</p><p>� � � �k� �(k + 1) �</p><p>k k� �</p><p>� � k� �1 2 3</p><p>1</p><p>2</p><p>1� � � � � �</p><p>�� �</p><p>� �� �...</p><p>=�</p><p>k k� �</p><p>�</p><p>�� � � �1 2 1</p><p>2</p><p>( )k</p><p>=�</p><p>k� �</p><p>�</p><p>�� � �1 2</p><p>2</p><p>( )k</p><p>Provando assim que 1 + 2 + 3 + ... + k + (k + 1) =</p><p>k� � k� ��� � �� �1 2</p><p>2</p><p>.</p><p>Desse modo, podemos concluir que o teorema é válido.</p><p>Finalizaremos esta seção com o seguinte teorema:</p><p>28 Matemática Discreta</p><p>Teorema</p><p>A soma dos quadrados dos n primeiros números naturais é</p><p>n n� � n� ��� � �� �1 2 1</p><p>6</p><p>.</p><p>Demonstração</p><p>Inicialmente, vamos mostrar que o resultado é válido para n = 1. Se n = 1, temos que</p><p>1² =</p><p>1 1� � (1)� ��� � �� �</p><p>� �</p><p>1 2 1</p><p>6</p><p>12 3</p><p>6</p><p>6</p><p>6</p><p>( )( ) = 1, provando que o teorema é válido no caso n = 1.</p><p>Assumindo que o teorema é válido para n = k, ou seja, assumindo que</p><p>1² + 2² + 3² + ... + k² = k k� � k� ��� � �� �1 2 1</p><p>6</p><p>Mostraremos que o teorema é válido para n = k + 1, ou seja, que</p><p>1² + 2² + 3² + ... + k² + (k + 1)² =</p><p>k� � k� �</p><p>k� ��� � �� � �� �1 2 2 3</p><p>6</p><p>De fato,</p><p>1² + 2² + 3² + ... + k² + (k + 1)² = k k� � k� ��� � �� �1 2 1</p><p>6</p><p>+ (k + 1)²</p><p>�</p><p>�� � �� � � �k� � k� �1 2 1 6 1</p><p>6</p><p>[ ( )]k k</p><p>�</p><p>�� � � �� �k k k1 2 7 6</p><p>6</p><p>2</p><p>�</p><p>�� � �� � �� �k k k1 2 2 3</p><p>6</p><p>Provando, assim, que 1² + 2² + 3² + ... + k² + (k + 1)² =</p><p>k� k� � k� ��� � �� � �� �1 2 2 3</p><p>6</p><p>.</p><p>Desse modo, podemos concluir que o teorema é válido.</p><p>CONSIDERAÇÕES FINAIS</p><p>Neste capítulo, aprendemos que, para afirmarmos que um teorema ou uma fórmu-</p><p>la é verdadeira ou não, precisamos realizar um procedimento matemático chamado</p><p>de demonstração matemática, a qual consiste em provar que o teorema ou a fórmula é</p><p>verdadeira para qualquer elemento que satisfaça suas hipóteses.</p><p>Estudamos que é importante conhecermos os diferentes métodos de demonstra-</p><p>ção, pois podemos utilizar qualquer um deles para mostrar que um teorema ou uma</p><p>fórmula é verdadeira. Contudo, o ato de construir um raciocínio lógico para demons-</p><p>trar uma proposição torna-se mais fácil (ou mais difícil) conforme o método escolhido.</p><p>ATIVIDADES</p><p>1. Utilize a técnica de demonstração direta para provar os seguintes teoremas:</p><p>a) Se a é um número inteiro par e b é um número inteiro ímpar, então a soma</p><p>a + b é um número inteiro ímpar.</p><p>b) Se a é um número inteiro par e b um número inteiro ímpar, então o produto</p><p>ab é um número par.</p><p>O filme O homem que viu</p><p>o infinito conta a história</p><p>do matemático indiano</p><p>Srinivasa Ramanujan (1887-</p><p>1920). No filme, podemos</p><p>perceber a importância de</p><p>uma boa escrita matemá-</p><p>tica, ou seja, saber fazer</p><p>boas demonstrações.</p><p>Apesar de ter boas ideias,</p><p>Ramanujan sofreu muito</p><p>em sua história como</p><p>matemático pelo fato de</p><p>não ter a capacidade de</p><p>escrever boas demons-</p><p>trações.</p><p>Direção Matt Brown. Londres: Animus</p><p>Films, 2016.</p><p>Filme</p><p>Fundamentos de lógica matemática e métodos de demonstração 29</p><p>2. Utilize a técnica de demonstração por contraposição para o seguinte teorema: Se a</p><p>é um número natural e a² é ímpar, então a é um número ímpar.</p><p>3. Utilize a técnica de demonstração por contradição para provar o seguinte teorema:</p><p>Se a é um número inteiro par e b é um número inteiro ímpar, então a soma a + b é</p><p>um número inteiro ímpar.</p><p>4. Utilize a técnica de demonstração por indução para provar o seguinte teorema: Se</p><p>n é um número natural, 1² + 3² + 5² + ... + (2n - 1)² = n 2n�-�1 2n�+�1</p><p>3</p><p>� �� � .</p><p>REFERÊNCIAS</p><p>FILHO, E. A. Iniciação à lógica matemática. São Paulo: Nobel, 2002.</p><p>GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5. ed. Boston: Addison-</p><p>Wesley, 2004.</p><p>ROSEN, K. H. Matemática discreta e suas aplicações. 6. ed. São Paulo: McGraw-Hill, 2009.</p><p>30 Matemática Discreta</p><p>2</p><p>Teoria de conjuntos</p><p>As ideias fundamentais da teoria dos conjuntos e da álgebra dos con-</p><p>juntos são provavelmente os conceitos mais importantes em todas as</p><p>áreas da matemática, e isso não é diferente na matemática discreta.</p><p>Este capítulo apresenta a teoria dos conjuntos. O material é principal-</p><p>mente elementar. Lembre-se de que, em matemática, elementar não significa</p><p>simples, mas sim que não requer vários conhecimentos prévios para ser com-</p><p>preendido. O material elementar pode ser bastante desafiador, e parte deste</p><p>capítulo talvez exija que você ajuste seu ponto de vista para compreendê-lo.</p><p>Um ponto em especial no qual este capítulo pode divergir da sua ex-</p><p>periência anterior com teoria de conjuntos é o fato de realizarmos a de-</p><p>monstração das propriedades elementares dos conjuntos.</p><p>Neste capítulo você aprenderá a noção intuitiva de conjuntos, como</p><p>descrever um conjunto e seus subconjuntos e, por fim, como realizar ope-</p><p>rações entre conjuntos e as principais propriedades dessas operações.</p><p>2.1 Noção intuitiva de conjuntos</p><p>Vídeo Uma matilha, um cacho de uvas ou um bando de pombos são exemplos de con-</p><p>juntos. O conceito matemático de um conjunto pode ser expresso por meio desses</p><p>exemplos. Porém, como definir um conjunto matemático?</p><p>Um conjunto matemático pode ser definido simplesmente como uma coleção</p><p>de objetos diferentes, mais precisamente:</p><p>Definição</p><p>Um conjunto A é uma coleção de objetos distintos.</p><p>Vejamos o exemplo a seguir:</p><p>Σxemρlo 1</p><p>São exemplos de conjuntos:</p><p>• A = {1, 2, 3, 4, 5}.</p><p>• B = {quadrado, triângulo, circunferência}.</p><p>• C = {Pedro, Maria, Welington}.</p><p>• Os conjuntos são denotados por</p><p>letras maiúsculas A, B, C, … do</p><p>nosso alfabeto.</p><p>• Os objetos de um conjunto A</p><p>são chamados de elementos do</p><p>conjunto.</p><p>• Se A é um conjunto formado</p><p>pelos objetos a, b, c, d, escreve-</p><p>mos A = {a, b, c, d}.</p><p>Importante</p><p>Teoria de conjuntos 31</p><p>Precisamos prestar atenção a um fato bem importante na definição de conjun-</p><p>tos: em um conjunto não é permitida a repetição de elementos.</p><p>Σxemρlo 2</p><p>Não são conjuntos:</p><p>• A = {1, 1, 2, 3, 4, 5}.</p><p>• B = {quadrado, triângulo, triângulo, circunferência}.</p><p>• C = {Pedro, Maria, Welington, Welington}.</p><p>Note que, no Exemplo 2, A, B e C não são conjuntos pelo fato de existirem repe-</p><p>tições entre seus elementos. Quando existem repetições de elementos, chamamos</p><p>A, B e C de multiconjuntos.</p><p>Um conjunto A = {a, b, c, d, …} com infinitos elementos é chamado de conjunto</p><p>infinito.</p><p>• Se a é um elemento do conjunto</p><p>A, escrevemos a ∈ A e dizemos</p><p>que a pertence a A.</p><p>• Se A é um conjunto e b não é</p><p>um elemento de A, escrevemos</p><p>b ∉ A e dizemos que b não</p><p>pertence a A.</p><p>Importante</p><p>2.2 Descrição e igualdade de conjuntos</p><p>Vídeo A maneira mais básica de se definir um conjunto é listar seus elementos entre</p><p>chaves, por exemplo: A = {2, 4, 6, 8, 10}, como feito na seção anterior. Também</p><p>podemos definir um conjunto fornecendo uma regra chamada lei de formação do</p><p>conjunto, que determina com segurança se um objeto é um membro ou não, por</p><p>exemplo: B = {x | 0 0}.</p><p>• E = {x | x tem 20 anos de idade e x nasceu em 1820}.</p><p>Na definição de conjuntos não se está exigindo nada com relação à ordem em</p><p>que seus elementos aparecem, ou seja, a ordem não importa. Isso significa, por</p><p>exemplo, que os conjuntos A = {1, 3, 4, 7} e B = {3, 1, 4, 7} são iguais. Em geral, po-</p><p>demos definir a igualdade de dois conjuntos como:</p><p>Definição</p><p>Dois conjuntos A e B são iguais se possuem exatamente os mesmos elementos.</p><p>Em símbolos, escrevemos:</p><p>A = B ↔ ∀ x, x ∈ A ↔ x ∈ B</p><p>E lemos:</p><p>A é igual a B se, e somente se, para todo x, x pertence a A se, e somente se, x pertence a B.</p><p>Definição</p><p>Dois conjuntos A e B são diferentes se existe um elemento a ∈ A tal que a ∉ B, ou existe um elemento</p><p>b ∈ B tal que b ∉ A. Em símbolos,</p><p>escrevemos:</p><p>A ≠ B ↔ ∃ a | a ∈ A e a ∉ B, ou ∃ b | b ∈ B e b ∉ A</p><p>E lemos:</p><p>A é diferente de B se, e somente se, existe a tal que a pertence a A e a não pertence a B, ou existe b tal que</p><p>b pertence a B e b não pertence a A</p><p>A definição de igualdade de conjuntos estabelece que, para provarmos que dois</p><p>conjuntos A e B são iguais, devemos provar que:</p><p>1. Todo elemento de A também é um elemento de B.</p><p>2. Todo elemento de B também é um elemento de A.</p><p>Teoria de conjuntos 33</p><p>Vejamos um exemplo.</p><p>Σxemρlo 5</p><p>Prove que os conjuntos A = {x | 2x + 4 = 10} e B = {3} são iguais.</p><p>Devemos mostrar que todo elemento de A é um elemento de B e que todo ele-</p><p>mento de B é um elemento de A. Seja a ∈ A, pela definição do conjunto A, a é tal que</p><p>2a + 4 = 10. Resolvendo essa equação linear, temos que a = 3, ou seja, a ∈ B, uma</p><p>vez que 3 ∈ B. Note que 2(3) + 4 = 10, ou seja, 3 satisfaz a definição do conjunto A e,</p><p>assim, 3 ∈ A, provando que A = B.</p><p>Definição</p><p>Para um conjunto finito, a cardinalidade é o número de elementos que ele contém. Em notação simbóli-</p><p>ca, a cardinalidade de um conjunto A é descrita como |A| ou n(A).</p><p>Se A é um conjunto com infinitos elementos, dizemos que a cardinalidade de A é infinita e escrevemos</p><p>|A| = ∞ ou n(A) = ∞.</p><p>Vejamos o exemplo a seguir:</p><p>Σxemρlo 6</p><p>A cardinalidade do conjunto A = {1, 3, 10, 40, 400} é n(A) = 5, e a cardinalidade do</p><p>conjunto B = {x | x é um número par} é n(B) = ∞.</p><p>Chamaremos de conjunto unitário todo conjunto que possui apenas um elemen-</p><p>to. O conjunto A = {27}, por exemplo, é um conjunto unitário.</p><p>Quando vamos descrever um conjunto, por exemplo, o conjunto A = {todos os</p><p>homens que possuem 27 anos de idade}, admitimos a existência de um conjunto</p><p>maior ao qual pertencem todos os elementos que compõem o conjunto que esta-</p><p>mos definindo. Esse conjunto maior é chamado de conjunto universo e é denota-</p><p>do pela letra U. No nosso exemplo, U = {todos os homens}.</p><p>Σxemρlo 7</p><p>Se A = {x ∈ N | x = 2k, onde k é um número natural} é o conjunto dos números</p><p>naturais pares, o universo U é o conjunto de todos os números naturais.</p><p>Utilizando a definição de conjunto universo, podemos introduzir um novo con-</p><p>junto com base em um conjunto dado A.</p><p>34 Matemática Discreta</p><p>Definição</p><p>Dado um conjunto A e seja U seu conjunto universo, o conjunto dos elementos que pertencem a U</p><p>e não pertencem a A é chamado de conjunto complementar de A. Denotamos o complementar de A</p><p>por AC ou C(A).</p><p>Vejamos no exemplo a seguir:</p><p>Σxemρlo 8</p><p>Se A = {x ∈ ℕ | x = 2k, onde k é um número natural} é o conjunto dos números</p><p>naturais pares, sabemos que seu universo U é o conjunto de todos os números</p><p>naturais. Desse modo, pela definição de complementar, temos:</p><p>AC = {x ∈ ℕ | x ≠ 2k, onde k é um número natural}</p><p>Ou seja, AC é o conjunto dos números naturais ímpares.</p><p>Nesta seção, você aprendeu a classificar vários objetos da vida real em termos</p><p>de conjuntos. Além disso, vimos diferentes maneiras de descrever um conjunto e</p><p>como podemos considerar um conjunto como parte menor de um conjunto maior</p><p>(chamado de conjunto universo). Introduzindo a noção de subconjunto, vamos, na</p><p>próxima seção, explorar o fato de podermos considerar um conjunto como uma</p><p>parte menor de outro conjunto.</p><p>2.3 Subconjuntos</p><p>Vídeo Consideremos os seguintes conjuntos: A = {capitais brasileiras} e B = {São Paulo,</p><p>Porto Alegre, Curitiba}. Observamos que todos os elementos do conjunto B também</p><p>são elementos do conjunto A, pois São Paulo, Porto Alegre e Curitiba são capitais</p><p>brasileiras. Nesse caso, dizemos que o conjunto B é um subconjunto do conjunto</p><p>A. O mesmo acontece com os conjuntos C = {0, 10, 7, 8, 79, 5} e D = {0, 7, 5}, onde D</p><p>é um subconjunto de C.</p><p>A definição matemática de subconjunto é apresentada a seguir:</p><p>Definição</p><p>Um conjunto B é subconjunto de um conjunto A se, e somente se, todo elemento de B for um elemento</p><p>de A.</p><p>Vejamos no exemplo a seguir:</p><p>• Escrevemos B ⊂ A se B é um</p><p>subconjunto de A. Nesse caso,</p><p>também dizemos que B está</p><p>contido em A.</p><p>• Em símbolos, temos:</p><p>B ⊂ A ↔ ∀ b ∈ B → b ∈ A</p><p>• Escrevemos B ⊄ A se B não</p><p>é subconjunto de A. Nesse</p><p>caso, dizemos que B não está</p><p>contido em A.</p><p>• Todo conjunto A é um subcon-</p><p>junto do seu universo U.</p><p>Importante</p><p>Teoria de conjuntos 35</p><p>Σxemρlo 9</p><p>a. {⊠, ⊝} ⊂ {⊠, ⨁, ⊟, ⊝}.</p><p>b. {a, b, c} ⊄ {b, c, d}.</p><p>c. {x | x é um número natural par} ⊂ {x | x é um número natural}.</p><p>Podemos representar a inclusão de conjuntos de modo gráfico por meio do Dia-</p><p>grama de Venn. Seja A um conjunto, U seu universo e B ⊂ A, graficamente temos:</p><p>A</p><p>B</p><p>U</p><p>Teorema</p><p>A inclusão de conjuntos satisfaz as seguintes propriedades:</p><p>a. ∅ ⊂ A para todo conjunto A.</p><p>b. A ⊂ A (reflexiva).</p><p>c. Se A ⊂ B e B ⊂ A, então A = B (antissimétrica).</p><p>d. Se A ⊂ B e B ⊂ C, então A ⊂ C (transitiva).</p><p>Demonstração</p><p>O item a pode ser descrito na seguinte proposição:</p><p>∀ x ∈ ∅ → x ∈ A</p><p>Onde temos p: ∀ x ∈ ∅ e q: x ∈ A. Como p é falsa, pois não há elementos em ∅, a</p><p>proposição é sempre verdadeira, pois p → q é sempre verdadeira. Provando, então,</p><p>que ∅ ⊂ A.</p><p>O item b segue do fato de que, se x ∈ A, então x ∈ A.</p><p>O item c segue da definição de igualdade de conjuntos.</p><p>Para o item d, temos: seja x ∈ A, então, como A ⊂ B, temos que x ∈ B, mas B ⊂ C,</p><p>onde x ∈ C, ou seja, A ⊂ C.</p><p>Pela definição de igualdade de</p><p>conjuntos, dois conjuntos A e B</p><p>são iguais se, e somente se, A ⊂ B</p><p>e B ⊂ A.</p><p>Importante</p><p>36 Matemática Discreta</p><p>Σxemρlo 10</p><p>Considere os conjuntos A = {números naturais}, B = {números naturais pares} e</p><p>C = {números naturais que dividem 4}. Temos que:</p><p>a. B ⊂ A e n(B) = n(A) = ∞.</p><p>b. C ⊂ A e n(C) = 3 n(A). Na verdade, é possível</p><p>provar que n(℘(A)) = 2n(A). Obviamente, n(℘(A)) = ∞ se n(A) = ∞.</p><p>2.4 Operações com conjuntos</p><p>Vídeo Em teoria de conjuntos, assim como em todos os tópicos estudados em mate-</p><p>mática, estamos interessados em definir e compreender operações matemáticas</p><p>que podem ser realizadas entres seus objetos. Nesta seção vamos definir as princi-</p><p>pais operações entre conjuntos.</p><p>Observamos a seguinte proprie-</p><p>dade elementar da inclusão de</p><p>conjuntos:</p><p>Se A ⊂ B, então n(A) ≤ n(B)</p><p>Importante</p><p>Teoria de conjuntos 37</p><p>Começaremos com a interseção.</p><p>Definição</p><p>A interseção entre os conjuntos A e B é o conjunto A∩B formado pelos elementos que estão simultanea-</p><p>mente em A e B. Em símbolos:</p><p>A∩B = {x | x ∈ A e x ∈ B}</p><p>O Diagrama de Venn da interseção de dois conjuntos é dado por:</p><p>A B</p><p>A∩B</p><p>Vejamos um exemplo a seguir:</p><p>Σxemρlo 12</p><p>Sejam A = {1, ∆, ∇} e B = {1, a, ∇, Θ}, então A∩B = {1, ∇}.</p><p>A definição de interseção de conjuntos pode ser generalizada para uma quanti-</p><p>dade finita de conjuntos, conforme segue:</p><p>Definição</p><p>A interseção entre os conjuntos A</p><p>1</p><p>, A</p><p>2</p><p>, …, A</p><p>n</p><p>é o conjunto A</p><p>1</p><p>∩A</p><p>2</p><p>∩…∩A</p><p>n</p><p>, formado pelos elementos</p><p>que estão simultaneamente em A</p><p>1</p><p>, A</p><p>2</p><p>, …, A</p><p>n</p><p>. Em símbolos:</p><p></p><p>i =1</p><p>n</p><p>iA = A</p><p>1</p><p>∩A</p><p>2</p><p>∩...∩A</p><p>n</p><p>= {x | x ∈ A</p><p>1</p><p>e x ∈ A</p><p>i</p><p>, ∀ i = 2, 3, ..., n}</p><p>Vejamos um exemplo:</p><p>Σxemρlo 13</p><p>Vamos representar as diversas interseções que podem ser estudadas com rela-</p><p>ção aos conjuntos:</p><p>A</p><p>= {01,11, 001, 10, 00, 010}, B = {01, 11, 001, 101, 011, 111} e</p><p>C = {01,11, 011, 101, 10, 000, 110}</p><p>38 Matemática Discreta</p><p>A B</p><p>C</p><p>00100,010 111</p><p>01,11</p><p>000,110</p><p>10 101,011</p><p>Temos que:</p><p>A∩B∩C = {01, 11}</p><p>A∩B = {01, 11, 001}</p><p>A∩C = {01, 11, 10}</p><p>B∩C = {01, 11, 101, 011}</p><p>Definição</p><p>Dois conjuntos A e B são ditos conjuntos disjuntos se A∩B = ∅, ou seja, se A e B não possuem elementos</p><p>em comum.</p><p>Σxemρlo 14</p><p>Sejam A = {101, 111} e B = {010, 100}, então A∩B = ∅.</p><p>Apresentaremos a seguir algumas das principais propriedades da interseção</p><p>entre conjuntos. As propriedades são apresentadas considerando, em geral, a in-</p><p>terseção entre dois ou três conjuntos, mas podem ser facilmente generalizadas</p><p>para a interseção de n conjuntos.</p><p>Teorema</p><p>Sejam A e B dois conjuntos tais que A ⊂ B, então A∩B = A.</p><p>Demonstração</p><p>Vamos mostrar que A∩B ⊂ A e A ⊂ A∩B. De fato, seja x ∈ A∩B, isso significa que</p><p>x ∈ A e x ∈ B e, como x ∈ A, prova que A∩B ⊂ A. Seja agora y ∈ A, como A ⊂ B, temos</p><p>que y ∈ B, isto é, y ∈ A∩B, provando que A ⊂ A∩B. Concluímos, então, que A∩B = A.</p><p>Σxemρlo 15</p><p>Sejam A = {1010, 0101} e B = {1010, 1001, 1111, 0101}, então, como A ⊂ B:</p><p>A∩B = A = {1010, 0101}</p><p>Teoria de conjuntos 39</p><p>Teorema</p><p>Sejam A e B dois conjuntos quaisquer, então:</p><p>A∩B ⊂ B e A∩B ⊂ A</p><p>Demonstração</p><p>Vamos mostrar apenas a primeira inclusão, já que a segunda é análoga. Seja</p><p>x ∈ A∩B, então x ∈ A e x ∈ B, onde x ∈ B, provando que A∩B ⊂ B.</p><p>Σxemρlo 16</p><p>Sejam A = {11010, 10110} e B = {11010, 11111, 00000}, então:</p><p>A∩B = {11010} ⊂ {11010, 11111, 00000}</p><p>Teorema</p><p>Sejam A, B e C conjuntos quaisquer, se A ⊂ B, então:</p><p>C∩A ⊂ C∩B</p><p>Demonstração</p><p>Seja x ∈ C∩A → x ∈ C e x ∈ A ⊂ B → x ∈ C e x ∈ B → x ∈ C∩B, onde C∩A ⊂ C∩B.</p><p>Σxemρlo 17</p><p>Sejam A = {101, 111}, B = {101, 111, 110, 001} e C = {001, 111}, então:</p><p>A ⊂ B e A∩C = {111} ⊂ {111, 001} = B∩C</p><p>Teorema (propriedades fundamentais da interseção de conjuntos)</p><p>Sejam A, B e C conjuntos quaisquer e U o conjunto universo, a interseção de</p><p>conjuntos satisfaz as seguintes propriedades:</p><p>a. A∩∅ = ∅.</p><p>b. A∩AC = ∅.</p><p>c. A∩A = A (idempotente).</p><p>d. A∩U = A (elemento neutro).</p><p>e. A∩B = B∩A (comutativa).</p><p>f. A∩(B∩C) = (A∩B)∩C (associativa).</p><p>Demonstração</p><p>Provaremos apenas a propriedade associativa: seja x ∈ A∩(B∩C) ↔ x ∈ A e</p><p>x ∈ (B∩C) ↔ x ∈ A e (x ∈ B e x ∈ C) ↔ (x ∈ A e x ∈ B) e x ∈ C ↔ x ∈ (A∩B) e x ∈ C ↔</p><p>x ∈ (A∩B)∩C, então temos que A∩(B∩C) = (A∩B)∩C.</p><p>Outra operação importante entre dois ou mais conjuntos é a operação de</p><p>união, que consiste em reunir elementos para formar um novo conjunto. Mais pre-</p><p>cisamente, a união de conjuntos é definida como segue:</p><p>40 Matemática Discreta</p><p>Definição</p><p>A união entre os conjuntos A e B é o conjunto A∪B, formado pela reunião dos elementos de A e B. Em</p><p>símbolos:</p><p>A∪B = {x | x ∈ A ou x ∈ B}</p><p>Vejamos o exemplo a seguir:</p><p>Σxemρlo 18</p><p>Sejam A = {∆, 11, ∇} e B = {1, ∆, 11, α, β}, então:</p><p>A∪B = {1, ∆, 11, ∇, α, β}</p><p>A definição de união de conjuntos pode ser generalizada para uma quantidade</p><p>finita de conjuntos, conforme segue:</p><p>Definição</p><p>A união entre os conjuntos A</p><p>1</p><p>, A</p><p>2</p><p>, …, A</p><p>n</p><p>é o conjunto A</p><p>1</p><p>∪A</p><p>2</p><p>∪…∪A</p><p>n</p><p>, formado por todos os elementos</p><p>de A</p><p>1</p><p>, A</p><p>2</p><p>, …, A</p><p>n</p><p>. Em símbolos:</p><p></p><p>i =1</p><p>n</p><p>iA = A</p><p>1</p><p>∪A</p><p>2</p><p>∪...∪A</p><p>n</p><p>= {x | x ∈ A</p><p>1</p><p>ou x ∈ A</p><p>i</p><p>, ∀ i = 2, 3, ..., n}</p><p>Vejamos o exemplo a seguir:</p><p>Σxemρlo 19</p><p>Vamos representar a união dos conjuntos.</p><p>A = {01, 11, 001, 10, 00, 010}, B = {01, 11, 001, 101, 001, 111} e</p><p>C = {01, 11, 011, 101, 10, 000, 110}</p><p>Um ponto importante que devemos notar ao escrever a união de conjuntos é</p><p>que nunca repetiremos elementos, ou seja, cada elemento deverá aparecer uma</p><p>única vez no conjunto união. Sendo assim, temos:</p><p>A∪B∪C = {01, 11, 001, 00, 010, 101, 001, 111, 011, 10, 000, 110}</p><p>A seguir, apresentaremos algumas das principais propriedades da união de con-</p><p>juntos. As propriedades são apresentadas considerando, em geral, a união entre</p><p>dois ou três conjuntos, porém podem ser facilmente generalizadas para a união de</p><p>n conjuntos.</p><p>Teoria de conjuntos 41</p><p>Teorema</p><p>Sejam A e B dois conjuntos, então A ⊂ A∪B e B ⊂ A∪B.</p><p>Demonstração</p><p>Vamos mostrar que A ⊂ A∪B. De fato, seja x ∈ A, isso significa que x ∈ A ou x ∈ B,</p><p>isto é, x ∈ A∪B, provando que A ⊂ A∪B.</p><p>Σxemρlo 20</p><p>Sejam A = {∆, ⊗, ⊠} e B = {111, 101}, então A∪B = {∆, ⊗, ⊠, 111, 101} e, claramente,</p><p>A ⊂ A∪B, assim como B ⊂ A∪B.</p><p>Teorema</p><p>Sejam A e B dois conjuntos, então A∪B = B ↔ A ⊂ B.</p><p>Demonstração</p><p>De fato, já sabemos que A ⊂ A∪B. Como A∪B = B, temos que A ⊂ B. Agora,</p><p>sabendo que A ⊂ B, vamos mostrar que A∪B = B. De fato, já sabemos que B</p><p>⊂ A∪B, isso significa que basta provarmos que A∪B ⊂ B para termos a igual-</p><p>dade A∪B = B. Então, se x ∈ A∪B, isso significa que x ∈ A ou x ∈ B, mas A ⊂ B.</p><p>Em qualquer caso, teremos que x ∈ B; se x ∈ A∪B, temos que x ∈ B, provando</p><p>que A∪B = B.</p><p>Σxemρlo 21</p><p>Sejam A = {4, 7} e B = {4, 7, 8, 9}, então:</p><p>A∪B = {4, 7, 8, 9} = B</p><p>Teorema</p><p>Sejam A, B e C conjuntos tais que A ⊂ C e B ⊂ C, então A∪B ⊂ C.</p><p>Demonstração</p><p>De fato, seja x ∈ A∪B, então, por definição, x ∈ A ou x ∈ B. Como A ⊂ C e B ⊂ C,</p><p>segue que x ∈ A ⊂ C ou x ∈ B ⊂ C, ou seja, x ∈ C. Provando que A∪B ⊂ C.</p><p>Teorema (propriedades fundamentais da união de conjuntos)</p><p>Sejam A, B e C conjuntos quaisquer e U o conjunto universo, a união de conjun-</p><p>tos satisfaz as seguintes propriedades:</p><p>a. A∪∅ = A (elemento neutro).</p><p>b. A∪U = U.</p><p>c. A∪AC = U.</p><p>d. A∪A = A (idempotente).</p><p>e. A∪B = B∪A (comutativa).</p><p>f. A∪(B∪C) = (A∪B)∪C (associativa).</p><p>Agora é com você: faça a demons-</p><p>tração de que B ⊂ A∪B</p><p>Desafio</p><p>42 Matemática Discreta</p><p>Σxemρlo 22</p><p>Sejam A = {α, θ} e B = {101, 111, 110}, então:</p><p>A∪B = {α, θ, 101, 111, 110} = B∪A</p><p>Podemos também combinar as operações de união e interseção de conjun-</p><p>tos para obter um novo conjunto. A combinação das operações de interseção e</p><p>união de conjuntos satisfaz as seguintes propriedades, que são chamadas de leis</p><p>de absorção:</p><p>Teorema</p><p>Sejam A e B conjuntos, então:</p><p>A∩(A∪B) = A e A∪(A∩B) = A</p><p>Demonstração</p><p>Sabemos que A ⊂ A∪B e, assim, segue do teorema ilustrado no Exemplo 15 que</p><p>A∩(A∪B) = A. De maneira análoga, temos que A∪(A∩B) = A.</p><p>Duas propriedades importantes na combinação entre união e interseção de</p><p>conjuntos são as propriedades de distributividade, que são equivalentes às pro-</p><p>priedades de distributividade com relação à soma e multiplicação de números</p><p>reais. A seguir, vamos enunciar e provar as propriedades de distributividade da</p><p>interseção e união de conjuntos.</p><p>Teorema</p><p>Sejam A, B e C conjuntos, então valem as seguintes distributivas:</p><p>a. A∩(B∪C) = (A∩B)∪(A∩C).</p><p>b. A∪(B∩C) = (A∪B)∩(A∪C).</p><p>Demonstração</p><p>Para provar essas propriedades, utilizaremos as leis distributivas da lógica ma-</p><p>temática. Vamos provar o item a.</p><p>Seja x ∈ A∩(B∪C) ↔ x ∈ A e x ∈ B∪C ↔ x ∈ A e (x ∈ B ou x ∈ C)</p><p>↔ (x ∈ A e x ∈ B) ou (x ∈ A e x ∈ C) ↔ x ∈ A∩B ou x ∈ A∩C</p><p>↔ x ∈ (A∩B)∪(A∩C)</p><p>Provando que A∩(B∪C) = (A∩B)∪(A∩C).</p><p>Agora é com você: faça a demons-</p><p>tração do item b.</p><p>Desafio</p><p>Teoria de conjuntos 43</p><p>Σxemρlo 23</p><p>Considere A = {1, 2}, B = {0, 1, 3, 4} e C = {1, 4, 5}.</p><p>Note inicialmente que B∩C = {1, 4}, onde A∪(B∩C) = {1, 2, 4}.</p><p>Por outro lado, temos que A∪B = {0, 1, 2, 3, 4} e A∪C = {1, 2, 4, 5}, onde</p><p>(A∪B)∩(A∪C) = {1, 2, 4}.</p><p>Sendo assim, A∪(B∩C) = (A∪B)∩(A∪C).</p><p>Vamos agora demonstrar um teorema muito importante, conhecido como Leis</p><p>de De Morgan para conjuntos. Essas leis recebem esse nome porque sua demonstra-</p><p>ção é feita com base nas Leis de De Morgan da lógica matemática.</p><p>Teorema (Leis de De Morgan)</p><p>Sejam A e B conjuntos, então valem as seguintes leis de De Morgan:</p><p>a. (A∩B)C = AC∪BC.</p><p>b. (A∪B)C = AC∩BC.</p><p>Demonstração</p><p>Vamos provar o item a.</p><p>Seja x ∈ (A∩B)C ↔ x ∉ A∩B ↔ ~(x ∈ A∩B)</p><p>↔ ~(x ∈ A e x ∈ B) ↔ ~(x ∈ A) ou ~(x ∈ B)</p><p>↔ x ∉ A ou x ∉ B ↔ x ∈ AC ou x ∈ BC ↔ x ∈ AC∪BC</p><p>Uma terceira operação importante entre conjuntos é a diferença entre conjun-</p><p>tos, a qual está definida a seguir.</p><p>Definição</p><p>A diferença entre os conjuntos A e B é o conjunto A\B 2 , formado pelos elementos de A que não estão</p><p>em B. Em símbolos:</p><p>A\B</p><p>= {x | x ∈ A e x ∉ B}</p><p>A diferença entre conjuntos pode</p><p>ser denotada também por A – B.</p><p>2</p><p>Vejamos o exemplo a seguir:</p><p>Σxemρlo 24</p><p>Sejam A = {0, 3, 7} e B = {3, 5, 7} dois conjuntos, então:</p><p>A\B = {0} e B\A = {5}</p><p>Agora é com você: faça a demons-</p><p>tração do item b.</p><p>Desafio</p><p>A diferença entre dois conjuntos</p><p>A e B não é comutativa, ou seja,</p><p>A\B ≠ B\A.</p><p>Importante</p><p>44 Matemática Discreta</p><p>Teorema</p><p>Sejam A, B e C conjuntos em um universo U, então valem as seguintes proprie-</p><p>dades relacionadas com a diferença entre conjuntos:</p><p>a. A\∅ = A.</p><p>b. U\A = AC.</p><p>c. A\A = ∅.</p><p>d. A\AC = A.</p><p>e. (A\B)C = AC\B.</p><p>f. A\B = BC\AC.</p><p>g. (A\B)\C = A\(B∪C).</p><p>h. A\(B\C) = (A\B)∪(A∩C).</p><p>Demonstração</p><p>Vamos provar apenas o item g. Seja x ∈ (A\B)\C, temos por definição da opera-</p><p>ção de diferença de conjuntos que:</p><p>x ∈ (A\B)\C ↔ x ∈ A\B e x ∉ C ↔ (x ∈ A e x ∉ B) e x ∉ C</p><p>↔ x ∈ A e (x ∉ B e x ∉ C) ↔ x ∈ A e (~(x ∈ B) e ~(x ∈ C))</p><p>↔ x ∈ A e ~(x ∈ B ou x ∈ C) ↔ x ∈ A e ~(x ∈ B∪C)</p><p>↔ x ∈ A\(B∪C)</p><p>Ou seja, (A\B)\C = A\(B∪C).</p><p>Para finalizar este capítulo, iremos apresentar alguns exemplos de como pode-</p><p>mos utilizar operações entre conjuntos para analisar afirmações ou um conjunto</p><p>de afirmações.</p><p>Σxemρlo 25</p><p>Dado que Pedro é um homem e que todos os homens são mortais, mostre que</p><p>Welington é mortal.</p><p>Vamos utilizar a propriedade de que se A ⊂ B e B ⊂ C, então A ⊂ C. Sejam:</p><p>U: Conjunto de todos os seres vivos.</p><p>B: Conjunto de todos os seres humanos.</p><p>C: Conjunto de todos os mortais.</p><p>A: Conjunto unitário cujo único elemento é Pedro.</p><p>Temos que A ⊂ B, B ⊂ C. Logo, A ⊂ C, onde Pedro é mortal.</p><p>Teoria de conjuntos 45</p><p>Σxemρlo 26</p><p>Em uma escola de 1.000 alunos, 800 gostam de sorvete de chocolate, 700 gos-</p><p>tam de sorvete de morango e 600 gostam dos dois sabores. Quantos alunos não</p><p>gostam de nenhum dos dois sabores?</p><p>Seja U = {Alunos da escola}, A = {Alunos que gostam de sorvete de chocolate} e</p><p>B = {Alunos que gostam de sorvete de morango}. Vamos construir o Diagrama de</p><p>Venn após analisar os dados.</p><p>Temos que n(A∩B) = 600, ou seja, 600 alunos gostam dos sabores chocolate e</p><p>morango.</p><p>Para sabermos quantos alunos gostam apenas do sabor chocolate, fazemos a</p><p>subtração da quantidade de alunos que gostam desse sabor pela quantidade de</p><p>alunos que gostam de ambos os sabores. Assim:</p><p>n(A)\n(A∩B) = 800 – 600 = 200</p><p>Agora, para determinarmos a quantidade de alunos que gostam apenas do</p><p>sabor morango, o processo é análogo ao anterior, fazemos:</p><p>n(B)\n(A∩B) = 700 – 600 = 100</p><p>Sabemos que n(U) = 1.000, que é composto pela quantidade de alunos que gos-</p><p>tam apenas do sabor chocolate, de ambos os sabores, apenas do sabor de moran-</p><p>go e alunos que não gostam de nenhum dos dois sabores, logo:</p><p>n(U) = n(A\(A∩B)) + n(A∩B) + n(B\(A∩B)) + n(U\(AUB))</p><p>= 200 + 600 + 100 + n(U\(AUB))</p><p>Sendo assim, n(U\(AUB)) = 1.000 – 900 = 100, ou seja, 100 alunos não gostam de</p><p>nenhum dos sabores. O Diagrama de Venn ficará da seguinte forma:</p><p>Alunos da escola</p><p>Chocolate</p><p>e</p><p>morango</p><p>600</p><p>Chocolate Morango</p><p>100</p><p>200 100</p><p>Podemos definir outras</p><p>operações entre conjuntos.</p><p>Uma operação bem conhe-</p><p>cida é a diferença simétrica</p><p>entre conjuntos. Saiba</p><p>mais sobre essa operação</p><p>na página Matemática</p><p>Essencial, da UEL.</p><p>Disponível em: http://www.uel.br/</p><p>projetos/matessencial/basico/medio/</p><p>conjuntos.html#sec11. Acesso em: 5</p><p>mar. 2021.</p><p>Saiba mais</p><p>Sempre que você for resolver um</p><p>exercício com interseções e uniões</p><p>de conjuntos, inicie anotando a</p><p>cardinalidade das interseções e</p><p>lembre-se de que as subtrações</p><p>da cardinalidade de cada conjunto</p><p>com a interseção são realizadas</p><p>para que não façamos a soma</p><p>de cada interseção mais de uma</p><p>vez, ou seja, para determinar a</p><p>cardinalidade apenas de cada</p><p>conjunto, sem a interseção.</p><p>Importante</p><p>http://www.uel.br/projetos/matessencial/basico/medio/conjuntos.html#sec11</p><p>http://www.uel.br/projetos/matessencial/basico/medio/conjuntos.html#sec11</p><p>http://www.uel.br/projetos/matessencial/basico/medio/conjuntos.html#sec11</p><p>46 Matemática Discreta</p><p>CONSIDERAÇÕES FINAIS</p><p>Neste capítulo você aprendeu os conceitos fundamentais de teoria de conjuntos,</p><p>as diferentes formas de descrevê-los e como relacioná-los com objetos da vida real.</p><p>Pôde entender, ainda, como realizar várias operações básicas entre conjuntos, que</p><p>estão diretamente relacionadas com fatos e temas de estudos da matemática discreta.</p><p>Por fim, compreendeu como podemos utilizar a teoria de conjuntos para demons-</p><p>trar afirmações matemáticas.</p><p>ATIVIDADES</p><p>1. Demonstre a propriedade comutativa da interseção de conjuntos. Mais</p><p>precisamente, demonstre que dados dois conjuntos A e B, então A∩B = B∩A.</p><p>2. Prove que, se A, B e C são conjuntos, então:</p><p>A∪(B∩C) = (A∪B)∩(B∪C)</p><p>3. Verifique a validade da seguinte lei de De Morgan: se A e B são conjuntos, então</p><p>(A∪B)C = AC∩BC.</p><p>4. Prove que, se A e B são conjuntos, então A\B = BC\AC.</p><p>REFERÊNCIAS</p><p>IEZZI, G.; MURAKAMI, C. Fundamentos da matemática elementar. São Paulo: Atual, 2013.</p><p>FILHO, E. A. Teoria elementar dos conjuntos. São Paulo: Nobel, 1980.</p><p>ROSEN, K. H. Matemática discreta e suas aplicações. São Paulo: McGraw-Hill, 2009.</p><p>GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5. ed. Boston: Addison-</p><p>-Wesley, 2004.</p><p>Conjuntos numéricos 47</p><p>3</p><p>Conjuntos numéricos</p><p>Você deve concordar que o conceito fundamental em matemática é a ideia</p><p>de número. Mais ainda, é provável que a primeira palavra que surge na sua</p><p>cabeça ao pensar em matemática seja números.</p><p>A ideia de número se desenvolveu com a capacidade de contar e vem evo-</p><p>luindo conforme a evolução da matemática como ciência. Da necessidade de</p><p>contar objetos surgiram os números naturais, que já foram representados por</p><p>diversas notações até chegar à notação que utilizamos hoje. Com o desenvolvi-</p><p>mento de novos problemas matemáticos, fez-se necessária a criação de novos</p><p>conjuntos numéricos: inteiros, racionais, reais e imaginários.</p><p>Neste capítulo, você vai aprender os principais conjuntos numéricos, suas</p><p>principais operações e propriedades. Além disso, vai aprender a trabalhar com</p><p>aritmética modular, uma ferramenta fundamental para que nossos computa-</p><p>dores realizem tarefas, como executar um vídeo da internet de modo pratica-</p><p>mente instantâneo.</p><p>3.1 Conjunto dos números naturais</p><p>Vídeo “Deus criou os números naturais, todo o resto é obra do homem”. Essa frase</p><p>foi dita pelo famoso matemático alemão Leopold Kronecker (1823-1891) para dar</p><p>ênfase à importância dos números naturais.</p><p>Na verdade, toda a sistemática dos conjuntos numéricos conhecidos na ma-</p><p>temática pode ser feita por meio dos números que utilizamos para contar. Esses</p><p>números são conhecidos como números naturais.</p><p>Definição</p><p>Chamamos de conjunto dos números naturais, denotando por  , o conjunto formado pelos números</p><p>1, 2, 3, ….</p><p> = {1, 2, 3, …}</p><p>Assumiremos que já é sabido que podemos realizar duas operações fundamen-</p><p>tais com números naturais: adição e multiplicação. Essas operações satisfazem al-</p><p>gumas propriedades bem interessantes, que serão anunciadas em seguida.</p><p>Teorema</p><p>A operação da adição de números naturais satisfaz as propriedades a seguir:</p><p>48 Matemática Discreta</p><p>a. Associativa da adição:</p><p>(a + b) + c = a + (b + c), para todo a, b, c ∈  .</p><p>b. Comutativa da adição:</p><p>a + b = b + a, para todo a, b ∈  .</p><p>Observamos que na definição apresentada o número zero não pertence ao</p><p>conjunto dos números naturais, já que a criação dos números naturais se dá</p><p>com o objetivo de contagem, por exemplo, para um pastor contar suas ovelhas.</p><p>Sendo assim, não incluímos o zero como número natural; afinal, ninguém conta</p><p>zero ovelhas.</p><p>Em algumas oportunidades é conveniente trabalhar com o número zero. Sendo</p><p>assim, vamos denotar por 0 o conjunto dos números naturais unido ao elemento</p><p>zero, ou seja, 0 = ∪{0}. Nesse caso, chamaremos o zero de elemento neutro da</p><p>adição em 0, pois para todo a ∈  , temos que a + 0 = a.</p><p>A multiplicação de números naturais também possui propriedades bem defini-</p><p>das, a saber:</p><p>Teorema</p><p>A operação de multiplicação de números</p>