Matemática Discreta - Welington Santos

WELINGTON SANTOS MATEMÁTICA DISCRE TA Código Logístico 59915 Fundação Biblioteca Nacional ISBN 9786558210122 9 7 8 6 5 5 8 2 1 0 1 2 2 Matemática Discreta Welington Santos IESDE BRASIL 2021 2021 IESDE BRASIL SA É proibida a reprodução mesmo parcial por qualquer processo sem autorização por escrito do autor e do detentor dos direitos autorais Projeto de capa IESDE BRASIL SA Imagem da capa devotchkahaslowikenvatoelements Todos os direitos reservados IESDE BRASIL SA Al Dr Carlos de Carvalho 1482 CEP 80730200 Batel Curitiba PR 0800 708 88 88 wwwiesdecombr CIPBRASIL CATALOGAÇÃO NA PUBLICAÇÃO SINDICATO NACIONAL DOS EDITORES DE LIVROS RJ S239m Santos Welington Matemática discreta Welington Santos 1 ed Curitiba PR Iesde 2021 136 p il Inclui bibliografia ISBN 9786558210122 1 Matemática 2 Lógica simbólica e matemática 3 Teoria dos conjun tos 4 Análise combinatória 5 Funções Matemática I Título 2169713 CDD 510 CDU 51 Welington Santos Doutor e Mestre em Matemática pela Universidade Federal do Paraná UFPR Graduado em Licenciatura em Matemática pela Universidade Estadual de Ponta Grossa UEPG Participou de programa de doutoramento sanduíche na Universidade de Maryland EUA Tem experiência na área de Matemática com ênfase em Teoria algébrica dos códigos corretores de erros Teoria de invariantes Selfdual codes Decodificação fracionária e Teoria de matróides Tem experiência em ensino superior ministrando aulas no formato presencial e a distância SUMÁRIO 1 Fundamentos de lógica matemática e métodos de demonstração 9 11 Fundamentos de lógica matemática 9 12 Demonstração direta e demonstração por contraposição 20 13 Demonstração por contradição 24 14 Demonstração por absurdo 25 15 Demonstração por indução finita 26 2 Teoria de conjuntos 30 21 Noção intuitiva de conjuntos 30 22 Descrição e igualdade de conjuntos 31 23 Subconjuntos 34 24 Operações com conjuntos 36 3 Conjuntos numéricos 47 31 Conjunto dos números naturais 47 32 Conjunto dos números inteiros 51 33 Conjunto dos números racionais 54 34 Números reais e cardinalidade 56 35 Aritmética modular 58 4 Relações 61 41 Produto cartesiano e par ordenado 61 42 Conceito de relação 64 43 Relação inversa 68 44 Propriedades das relações 69 45 Operações e fecho de relações 72 46 Relação de ordem e de equivalência 74 5 Funções discretas 80 51 Conceito e classificação 80 52 Função composta e função inversa 85 53 Funções recursivas 89 6 Análise combinatória 92 61 Princípios de contagem 92 62 Arranjos 97 63 Permutações 99 64 Combinações 102 65 Binômio de Newton 106 6 Matemática Discreta 7 Funções geradoras e partição de um inteiro 112 71 Funções geradoras 112 72 Operações com funções geradoras 114 73 Funções geradoras exponenciais 120 74 Sequência de Fibonacci 123 75 Partição de um inteiro 124 76 Gráfico de uma partição 126 Gabarito 129 APRESENTAÇÃO Esta obra oferece uma abordagem introdutória à matemática discreta área da matemática dedicada ao estudo de objetos que são formados por elementos desconexos entre si chamados de elementos discretos Apresentamos com detalhes conceitos fundamentais de teoria de conjuntos conjuntos numéricos e aritmética modular diferentes problemas de combinatória e funções úteis para a resolução de problemas de contagem Para tanto no primeiro capítulo discorremos sobre os fundamentos básicos da lógica matemática apresentando operações entre proposições lógicas e suas implicações nas técnicas de demonstração para resultados matemáticos A matemática é fundamentada por axiomas lemas corolários e teoremas que são validados por meio das demonstrações Nesse sentido ao longo de toda a obra apresentamos e aplicamos as principais técnicas de demonstração direta contraposição contradição absurdo e indução para provar fatos bem conhecidos da matemática No segundo capítulo abordamos a teoria fundamental de conjuntos que embasa toda a matemática discreta apresentando as técnicas básicas de contagem do número de elementos dos conjuntos e as principais operações entre eles como a intersecção a união e a diferença O terceiro capítulo propõe um estudo aprofundado dos principais conjuntos numéricos explorando as diferentes propriedades e operações que cada um desses conjuntos possui Além disso classificamos os conjuntos numéricos em termos de sua cardinalidade descrevendo o conceito de conjunto enumerável e não enumerável Diante da importância da aritmética modular em problemas que envolvem contagem discorremos detalhadamente sobre essa matéria que é observada na leitura de um CD e na validação do número do Cadastro de Pessoa Física CPF No quarto capítulo com objetivo de introduzir o conceito de relações entre conjuntos nos debruçamos sobre a operação de produto cartesiano entre conjuntos Além disso apresentamos as principais propriedades das relações entre conjuntos e dois tipos especiais de relação relação de ordem e de equivalência que são utilizadas na alocação de frota de empresas aéreas por exemplo No quinto capítulo utilizamos o conceito de relações entre conjuntos para definir funções discretas apresentando os principais elementos que compõem uma função domínio contradomínio e imagem Exploramos também as principais propriedades operatórias entre funções Por fim apresentamos os fundamentos básicos de funções recursivas apontando sua aplicação para a criação de sequências numéricas como a famosa sequência de Fibonacci Vídeo 8 Matemática Discreta No sexto capítulo nos debruçamos sobre os princípios fundamentais de contagem princípio da adição da subtração da multiplicação e o princípio da casa dos pombos exibindo exemplos de aplicações para cada um deles Além disso o capítulo define classifica e ilustra diferentes problemas de contagem Por fim são exploradas as principais propriedades do binômio de Newton e do teorema multinomial No capítulo final abordamos a função geradora ordinária de uma sequência numérica identificando as relações entre operação com sequências numéricas e funções geradoras Exibimos por meio de exemplos como podemos utilizar funções geradoras para solucionar problemas de contagem Por fim as ideias básicas de partição de um número inteiro são apresentadas O livro também apresenta ao final de cada capítulo exercícios cuidadosamente selecionados para que você exercite e explore na prática os temas apresentados Bons estudos Fundamentos de lógica matemática e métodos de demonstração 9 1 Fundamentos de lógica matemática e métodos de demonstração Você já se perguntou como surgiram as diversas fórmulas da ma temática como as famosas fórmulas de Bhaskara e de Pitágoras Já imaginou o porquê de elas sempre funcionarem Isso se deve ao fato de que essas e muitas outras fórmulas foram demonstradas isto é alguém utilizando um método lógico dedutivo provou que elas são sempre válidas Neste capítulo você irá aprender os principais fundamentos da lógica matemática por exemplo qual é o principal objetivo de se estudála o que é um paradoxo o que é uma proposição e como podemos operar com proposições Além disso aprenderá os principais métodos de de monstrações isto é as principais técnicas utilizadas para demonstrar que alguma fórmula ou propriedade é verdadeira Por fim você realizará suas primeiras demonstrações matemáticas 11 Fundamentos de lógica matemática Vídeo A lógica matemática teve origem no século IV antes de Cristo na Grécia Antiga com os trabalhos de Parmênides 530460 aC e Zenão 510470 aC mas ganhou status de ciência apenas após os trabalhos do filósofo Aristóteles 384322 aC em especial na obra Organum na qual ele estabelece os princípios dela e por esse motivo é chamado de pai da lógica matemática O norte da lógica matemática é a busca pela verdade sendo assim possui como objeto de estudo as leis de formação do pensamento e as regras para se aplicar essas leis para investigar a verdade Outro grande objetivo dessa ciência é entender como podemos utilizar noções previamente estabelecidas como verdadeiras para deduzir novos conhecimentos Com o objetivo de estudar a verdade precisamos definir o principal objeto de estudo da lógica matemática as proposições 10 Matemática Discreta Definição Uma proposição é uma declaração que pode ser verdadeira ou falsa De modo mais preciso poderíamos dizer que uma proposição é um conjunto de símbolos e palavras que exprimem um pensamento o qual pode ser verdadeiro ou falso Observe os seguintes exemplos de proposições Σxemρlo 1 São proposições p Tóquio é a capital da China q Wellington é a capital da Nova Zelândia r 1 5 6 s π 3 Cada uma das proposições do exemplo anterior exprime um pensamento al guns verdadeiros como os pensamentos expressos nas proposições q e r e alguns falsos como nas proposições p e s Assim dizemos que as proposições q e r pos suem valor lógico verdadeiro V e a as proposições p e s possuem valor lógico falso F É possível escrevermos sentenças que não possuem nem valor lógico verdadei ro nem valor lógico falso Essas sentenças não são proposições e são conhecidas como paradoxos Existem alguns exemplos bem conhecidos os quais são muito utilizados na música e na literatura Vejamos O amor é ferida que dói e não se sente Luís Vaz de Camões Estou cego e vejo Carlos Drummond de Andrade Já estou cheio de me sentir vazio Renato Russo Note que não podemos atribuir um valor lógico verdadeiro ou falso para a frase de Carlos Drummond de Andrade pois estar cego e ver é um paradoxo A seguir vamos analisar o paradoxo conhecido como paradoxo do mentiroso Σxemρlo 2 Considere a seguinte sentença Esta frase não é verdadeira Agora faça a análise desse paradoxo Fundamentos de lógica matemática e métodos de demonstração 11 Note que se a sentença é verdadeira então pelo seu significado a sentença é falsa e isso é uma contradição Semelhantemente se a sentença for falsa então o que ela diz não é fato e assim a sentença é verdadeira ou seja temos novamente uma contradição e portanto um paradoxo A lógica matemática adota alguns axiomas que são proposições presumida mente assumidas como verdadeiras porque se acredita que são de alguma forma razoáveis por exemplo o seguinte axioma de Euclides podese traçar uma única reta ligando dois pontos quaisquer Os dois princípios fundamentais da lógica matemática são Princípio da não contradição Princípio do terceiro excluído Uma proposição não pode ter valor lógico verdadeiro e falso ao mesmo tempo Por definição excluise a possibilidade de um paradoxo ser uma proposição Toda proposição ou é verdadeira ou é falsa não havendo possibilidade de assumir outro valor lógico Esse princípio diz que toda proposição não abre espaço para interpretação isto é ou a proposição é verdadeira ou é falsa não existe a possibilidade de talvez e depende Assim como fazemos com pensamentos podemos combinar mais de uma proposição para formar uma nova chamada de proposição composta Mais preci samente dadas proposições simples p q r s t podemos construir uma nova proposição Pp q r s t ou simplesmente P formada pelas proposições simples que foram dadas Considere os seguintes exemplos de proposições simples p Welington é professor de matemática q Você é estudante de matemática r Você será professor de matemática s Você será engenheiro Com essas proposições podemos formar novas proposições compostas como Pp q Welington é professor de matemática e você é estudante de matemática Qs r Você será engenheiro ou você será professor de matemática Rq r Se você é estudante de matemática então você será professor de matemática Sp r Welington é professor de matemática e você será professor de matemática Utilizamos algumas palavras para conectar as proposições simples p q r s e produzirmos as proposições compostas P Q R S Essas palavras são chamadas de conectivos Na lógica matemática existem cinco conectivos e ou não se então e se e somente se O ato de combinar proposições é chamado de operação lógica e os conectivos de operadores Para cada conector daremos um nome e um símbolo especial 12 Matemática Discreta O quadro a seguir apresenta as cinco operações lógicas seus conectivos e res pectivos símbolos Quadro 1 Conectivos lógicos e seus símbolos Conectivo Símbolo do conectivo Operação do conectivo e Conjunção ou Disjunção não ou Negação se então Condicional se e somente se Bicondicional Fonte Elaborado pelo autor Dada uma proposição lógica composta iremos utilizar o valor lógico das pro posições simples que a compõem para determinar o seu valor lógico Isso só será possível se as operações estiverem bem definidas Para cada conjunto de proposi ções simples com seus respectivos valores lógicos obtemos um único valor lógico possível para a proposição composta Os valores lógicos das cinco operações lógicas são definidos como segue 1 Negação A negação da proposição p é a proposição p não p cujo valor lógico é definido da seguinte forma O valor lógico de p é verdadeiro se o valor lógico de p for falso O valor lógico de p é falso se o valor lógico de p for verdadeiro Podemos organizar essa informação em uma tabela a qual é chamada de tabelaverdade da proposição p p p V F F V Vejamos no exemplo a seguir como aplicar a tabelaverdade da negação para encontrar o valor lógico de uma proposição composta formada pela negação de uma proposição dada Σxemρlo 3 Considere a proposição p Tóquio é a capital da China Encontre o valor lógico da negação da proposição dada Fundamentos de lógica matemática e métodos de demonstração 13 Sabemos que p tem valor lógico falso F sendo assim o valor lógico da proposi ção p Não é verdade que Tóquio é a capital da China tem valor lógico verdadeiro V 2 Conjunção A conjunção das proposições p e q é a proposição p q p e q cujo valor lógico é definido da seguinte maneira O valor lógico de p q é verdadeiro se os valores lógicos de p e q são verdadeiros O valor lógico de p q é falso se o valor lógico de p ou de q é falso A tabelaverdade da proposição p q é apresentada a seguir p q p q V V V V F F F V F F F F Vejamos no exemplo a seguir como aplicar a tabelaverdade da conjunção para encontrar o valor lógico de uma proposição composta formada pela conjunção de duas proposições simples dadas Σxemρlo 4 Considere as proposições p Welington é professor de matemática q Wellington é capital da Nova Zelândia e s π 3 Encontre o valor lógico de p q p s e q s Sabemos que p tem valor lógico V q tem valor lógico V e s tem valor lógico F Sendo assim p q tem valor lógico V p s tem valor lógico F q s tem valor lógico F 3 Disjunção A disjunção das proposições p e q é a proposição p q p ou q cujo valor lógico é definido do seguinte modo O valor lógico de p q é verdadeiro se o valor lógico de p é verdadeiro ou o valor lógico de q é verdadeiro O valor lógico de p q é falso se o valor lógico de p é falso e o valor lógico de q é falso A tabelaverdade da proposição p q é apresentada a seguir 14 Matemática Discreta p q p q V V V V F V F V V F F F Vejamos no exemplo a seguir como aplicar a tabelaverdade da disjunção para encontrar o valor lógico de uma proposição composta formada pela disjunção de duas proposições simples dadas Σxemρlo 5 Considere as proposições p Welington é professor de matemática q Wellington é capital da Nova Zelândia e s π 3 Encontre o valor lógico de p q p s e q s Sabemos que p tem valor lógico V q tem valor lógico V e s tem valor lógico F Sendo assim p q tem valor lógico V p s tem valor lógico V q s tem valor lógico V 4 Condicional A condicional das proposições p e q é a proposição p q se p então q cujo valor lógico é definido da seguinte forma O valor lógico de p q é verdadeiro se p e q são verdadeiros O valor lógico de p q é verdadeiro sempre que p é falso O valor lógico de p q é falso se p é verdadeiro e q é falso A seguir representamos a tabelaverdade da proposição p q p q p q V V V V F F F V V F F V Vejamos no exemplo a seguir como aplicar a tabelaverdade da condicional para encontrar o valor lógico de uma proposição composta formada pela condicional p q de duas proposições simples Σxemρlo 6 Considere as proposições p Welington é professor de matemática q Wellington é capital da Nova Zelândia e s π 3 Encontre o valor lógico de p q p s e s q Fundamentos de lógica matemática e métodos de demonstração 15 Sabemos que p tem valor lógico V q tem valor lógico V e s tem valor lógico F Sendo assim p q tem valor lógico V p s tem valor lógico F s q tem valor lógico V 5 Bicondicional A bicondicional de duas proposições p e q é a proposição p q p se e somente se q cujo valor lógico é definido da seguinte maneira O valor lógico de p q é verdadeiro se p e q são verdadeiros O valor lógico de p q é verdadeiro se p e q são falsos O valor lógico de p q é falso se p é verdadeiro e q é falso O valor lógico de p q é falso se p é falso e q é verdadeiro A seguir representamos a tabelaverdade da proposição p q p q p q V V V V F F F V F F F V Vejamos no exemplo a seguir como aplicar a tabelaverdade da bicondicional para encontrar o valor lógico de uma proposição composta formada pela bicondi cional p q de duas proposições simples Σxemρlo 7 Considere as proposições p Welington é professor de matemática q Welling ton é capital da Nova Zelândia e s π 3 Encontre o valor lógico de p q p s e s q Sabemos que p tem valor lógico V q tem valor lógico V e s tem valor lógico F Sendo assim p q tem valor lógico V p s tem valor lógico F s q tem valor lógico F Podemos construir tabelasverdade de proposições compostas forma das por mais de duas proposições simples Nesse caso o número de linhas da tabelaverdade vai depender do número de proposições simples mais especifica mente o número de linhas da tabelaverdade da proposição composta P será 2n onde n é o número de proposições simples que a compõem Vejamos um exemplo 16 Matemática Discreta Σxemρlo 8 Sejam p q e r três proposições simples vamos construir a tabelaverdade da proposição composta Pp q r p r q r Primeiro note que o número de linhas da tabelaverdade será 2³ Além disso teremos as colunas p q r q p r q r e P p r q r Mais precisamente a tabelaverdade de Pp q r é p q r q p r q r P V V V F V V V V V F F F F V V F V V V V V V F F V F V V F V V F F V V F V F F F F V F F V V F V V F F F V F V V Observamos que a última coluna da tabelaverdade de Pp q r p r q r possui apenas valor lógico verdadeiro Nesse caso dizemos que P é uma tautologia Por outro lado chamaremos de contradição toda proposição composta P que pos sui apenas valor lógico falso na última coluna de sua tabelaverdade Podemos então utilizar a tabelaverdade para verificarmos se uma proposição composta é verdadeira ou não Para tanto basta considerarmos o valor lógico da última coluna da linha referente aos valores lógicos das proposições simples que a compõem Por exemplo se considerarmos p Welington é professor de matemática V q Wellington é capital da Nova Zelândia V e s π 3 F teremos que o valor lógico de Pp q r p r q r será V Basta olharmos para a segun da linha de sua tabelaverdade Durante a construção da tabelaverdade do exemplo anterior você deve ter se perguntado como saberei qual operação lógica irei realizar primeiro Assim como acontece nas operações com números reais as operações lógicas possuem uma ordem de preferência para serem realizadas A ordem de preferência para operações lógicas é a seguinte negação conjunção disjunção condicional bicon dicional sempre dando preferência para as operações entre parênteses Fundamentos de lógica matemática e métodos de demonstração 17 Definição Duas proposições compostas P e Q são chamadas de logicamente equivalentes se a tabelaverdade de P Q é uma tautologia Nesse caso escrevemos que P Q são logicamente equivalentes A seguir apresentamos dois exemplos de proposições equivalentes Esses dois exemplos são conhecidos como Leis de De Morgan e são superimportantes Cons truiremos a tabelaverdade de uma delas para comprovar que realmente temos uma equivalência lógica Σxemρlo 9 As seguintes equivalências lógicas são conhecidas como Leis de De Morgan p q p q p q p q Vamos verificar que o segundo item é realmente uma equivalência lógica Por definição devemos construir a tabelaverdade de P p q p q e verificar que temos uma tautologia p q p q p q p q p q P V V F F V F F V V F F V F V V V F V V F F V V V F F V V F V V V Observamos que P é uma tautologia sendo assim temos a seguinte equivalên cia p q p q Como já foi comentado podemos utilizar a tabelaverdade para analisar o valor lógico de uma proposição composta A seguir apresentamos um exemplo de como isso funciona para proposições matemáticas Σxemρlo 10 Sejam p π 3 e q 1 2 4 duas proposições matemáticas vamos analisar o valor lógico de Pp q p q q p Agora é com você construa a tabelaverdade para provar que a primeira Lei de De Morgan apre sentada no exemplo realmente é uma equivalência lógica Desafio Inicialmente vamos traduzir Pp q em uma sentença matemática traduzindo os conectivos para a linguagem formal Temos que p π 3 q 1 2 4 p q π 3 e 1 2 4 q p 1 2 4 e π 3 Então Pp q π 3 e 1 2 4 se e somente se 1 2 4 π 3 Vamos agora construir a tabelaverdade de Pp q p q p p q q q p Pp q V V F F F F V V F F F V F F F V V F V F V V F V F V F V V F V F F F V F V F V F V F Para analisarmos o valor lógico da proposição composta Pp q basta olharmos para os valores lógicos das proposições simples p e q Sabemos que ambas p e q são falsas Sendo assim o valor lógico de Pp q está na quarta linha de sua tabelaverdade a linha onde os valores lógicos de p e q são falsos ou seja Pp q tem valor lógico verdadeiro Você deve estar se perguntando sempre terei que construir a tabelaverdade para provar que uma proposição matemática é verdadeira A resposta para essa questão é não Nas próximas seções deste capítulo iremos aprender métodos e linhas de raciocínio lógico que são utilizados para provar que uma proposição matemática é verdadeira Esses métodos são conhecidos como métodos de demonstração Antes de iniciarmos o estudo sobre os métodos de demonstração precisamos estabelecer a estrutura de uma proposição matemática e algumas nomenclaturas Toda proposição matemática tem sua estrutura formada por uma hipótese a qual é a premissa que assumimos como verdadeira e por uma tese uma afirmação que queremos provar utilizando nossa hipótese Observe a seguinte proposição que estabelece a fórmula de Bhaskara Seja ax² bx c 0 com a 0 uma equação do segundo grau então x b b² 4ac 2a Nessa proposição nossa hipótese é p ax² bx c 0 com a 0 é uma equação do segundo grau e nossa tese q x b b² 4ac 2a Fundamentos de lógica matemática e métodos de demonstração 19 As proposições matemáticas recebem nomes especiais conforme seu grau de importância Como vimos os axiomas são proposições presumidamente assumidas como verdadeiras ou seja que não requerem provas Observe os seguintes exemplos de axiomas da adição de números reais Associatividade sejam a b c ℝ temse a b c a b c Comutatividade sejam a b ℝ temse a b b a Um teorema é uma sentença matemática que pode ser provada como verdadeira Podemos citar como exemplo o famoso Teorema de Pitágoras em qualquer triângulo retângulo o quadrado do comprimento da hipotenusa é igual à soma dos quadrados dos comprimentos dos catetos Um lema é um teorema de menor importância que pode ser utilizado para demonstrar teoremas mais importantes Nesse sentido ao nos depararmos com um teorema complicado para realizar mos a sua demonstração de modo simples o dividimos em vários lemas Como exemplo vamos considerar o importantíssimo lema que é utilizado para demons trar o algoritmo da divisão de números inteiros Lema Método de divisão de Euclides Sejam a e b inteiros tais que a 0 e b 0 então existem q e r quociente e resto respectivamente tais que a bq r e 0 r b Um corolário é uma proposição que pode ser provada diretamente de um teorema mais importante já demonstrado Tomemos como exemplo o seguinte corolário do Teorema de Pitágoras seja d a diagonal de um quadrado de lado l então d l2 Estabelecida a estrutura de uma proposição matemática e sua nomenclatura iremos estudar a seguir os métodos de demonstração Podemos representar a fórmula de Bhaskara pela proposição composta p q onde p ax² bx c 0 com a 0 e q x b b² 4ac2a Demonstrar a fórmula de Bhaskara é portanto assumir que p é verdadeira e provar que q também é verdadeira Utilizar uma sequência lógica de pensamentos para com base na hipótese provar que a conclusão é verdadeira é conhecido como método de demonstração direta Esse tipo de demonstração consiste em utilizar as particularidades da hipótese para provar a tese Vamos apresentar alguns exemplos de demonstrações diretas inclusive uma demonstração para a famosa fórmula de Bhaskara Demonstre os seguintes teoremas sobre a soma de números inteiros a Se a e b são dois números inteiros ímpares então a soma a b é um número inteiro par b Se a e b são dois números inteiros pares então a soma a b é um número inteiro par a Demonstração Considere a e b dois números inteiros ímpares Pela definição de número inteiro ímpar sabemos que a 2t₁ 1 e b 2t₂ 1 Logo a soma a b é a b 2t₁ 12t₂ 1 2t₁t₂ 2t₁ 2t₂ 2 22t₁t₂ t₁ t₂ 1 ou seja a b 2k₃ onde k₃ 2t₁t₂ t₁ t₂ Isso mostra que ab tem a forma de um número inteiro ímpar Podemos assim concluir que ab é um número inteiro ímpar b Demonstração Sejam a e b dois números inteiros pares pela definição de número inteiro par sabemos que a 2k₁ e b 2k₂ Logo o produto ab é ab 2k₁2k₂ 2k₁k₂ ou seja ab 2k₃ onde k₃ k₁k₂ Isso mostra que ab tem a forma de um número inteiro par Podemos portanto concluir que a b é um número inteiro par Vamos agora demonstrar a famosa fórmula de Bhaskara Teorema Fórmula de Bhaskara Seja ax² bx c 0 com a 0 uma equação do segundo grau então x b b² 4ac2a Demonstração Consideremos a equação ax² bx c 0 com a 0 Vamos aplicar várias operações nessa equação para chegarmos a nossa tese ax² bx c 0 a 0 0 0 ba ba b²4a² cb²4a² 0 Sendo assim utilizamos nossa hipótese para provar que nossa tese é verdadeira ou seja a fórmula de Bhaskara é verdadeira Durante a demonstração da fórmula de Bhaskara você deve ter percebido que há casos em que demonstrar um teorema pelo método direto pode não ser algo simples Podemos contornar esse fato utilizando o método de demonstração por contraproposição Esse método consiste na seguinte tautologia P p q q p Vamos verificar por meio de sua tabelaverdade que P é realmente uma tautologia p q p q p q q p p V V F F V V V V F F F V V F V V V F V V F V V V F V Como todos os valores lógicos da última coluna da tabelaverdade de P são verdadeiros concluímos que P é realmente uma tautologia Vejamos um exemplo simples de como aplicar o método de demonstração por contraproposição Fundamentos de lógica matemática e métodos de demonstração 23 A proposição composta P pode ser traduzida como P Se João é curitibano en tão João é brasileiro Essa proposição é equivalente à proposição Q q p que traduzida é Q Se João não é brasileiro então João não é curitibano Claramente P é verdadeira sempre que Q é verdadeira e viceversa Vamos agora aplicar o método de demonstração por contraposição para provar o seguinte teorema Teorema Se a é um número natural e a² é par então a é um número par Demonstração Nossa proposição é p a² é par q a é par Vamos demonstrar que a propo sição equivalente q a é ímpar p a² é ímpar é verdadeira Com efeito se a é ímpar existe k natural tal que a 2k 1 Logo a² 2k 1² 4k² 4k 1 22k² 2k 1 2k2 1 onde k2 2k² 2k ou seja a² é um número ímpar provando que a contrapositiva do teorema é verdadeira Podemos então concluir que o teorema é verdadeiro Definição Dizemos que um número a não é múltiplo de b se a divisão de a por b tem resto diferente de zero Um núme ro a não é múltiplo de b se a kb r onde 0 r b Por exemplo 7 não é múltiplo de 3 pois 7 23 1 Vamos demonstrar o seguinte teorema pelo método da contrapositiva Teorema Se a é um número natural e a³ é múltiplo de três então a é um múltiplo de três Demonstração Nossa proposição é p a³ é múltiplo de 3 q a é múltiplo de 3 Vamos de monstrar que a proposição equivalente q a não é múltiplo de 3 p a³ não é múltiplo de 3 é verdadeira Com efeito note que se a não é múltiplo de 3 então a 3k1 1 ou a 3k2 2 Analisando ambos os casos Se a 3k1 1 temos a³ 3k1 1³ 3k1 1² 3k1 1 27k1³ 9k1² 9k1 1 39k1³ 3k1² 3k1 1 3k3 1 Onde k3 9k1³ 3k1² 3k1 Existe mais de uma maneira de se demons trar um teorema Um dos teoremas mais impor tantes que estudamos e ensinamos para os alunos da educação básica é o Teorema de Pitágoras Na página Decifrando a Matemática da Unicamp você vai encontrar vários caminhos diferentes para a demonstração do Teorema de Pitágoras além de encontrar boas aborda gens para o ensino desse teorema Disponível em wwwimeunicamp brapmatteoremadepitagoras Acesso em 5 mar 2021 Saiba mais 24 Matemática Discreta Se a 3k2 2 temos a³ 3k2 2³ 3k2 2²3k2 2 27k2³ 18k2² 36k2 6 2 39k2³ 6k2² 12k2 2 2 3k4 2 Onde k4 9k2³ 6k2² 12k2 Sendo assim a³ 3k3 2 ou a³ 3k42 provando que a³ não é múltiplo de três ou seja a contrapositiva do teorema é verdadeira Podemos concluir portanto que o teorema é verdadeiro 13 Demonstração por contradição Vídeo Esse método consiste em utilizar uma contradição para mostrar que uma pro posição é verdadeira e tem como inspiração a seguinte tabelaverdade p q p p q V V F V V F F V F V V V F F V F Observando as duas primeiras linhas da tabelaverdade temos que p é verda deira sempre que p q é verdadeira Isso significa que para mostrarmos que uma proposição p é verdadeira basta encontrarmos q tal que p q é verdadeira Resumidamente o método de demonstração por contradição consiste em afirmar a hipótese negar a tese e chegar a uma contradição Vejamos alguns exemplos de aplicação do método de demonstração por contradição Σxemρlo 14 Utilize o método de demonstração por contradição para provar que o único número que quando somado com ele mesmo resulta no próprio número é o zero Queremos demonstrar o seguinte teorema Se a a a então a 0 Para isso vamos utilizar o método da demonstração por contradição Nossa hipótese p é a a a e nossa tese q é a 0 Vamos então negar q ou seja q a 0 Suponha então que a a a e a 0 Temos que 2a a e como a 0 podemos realizar a divisão por a se a 0 a divisão não pode ser realizada afinal não existe divisão por zero Fundamentos de lógica matemática e métodos de demonstração 25 Finalmente 2a a a a Concluímos que 2 1 Isso é uma contradição logo não podemos ter a 0 então a 0 Agora vamos utilizar o método de demonstração por contradição para demons trar o seguinte teorema que já foi demonstrado pelo método de demonstração direta Σxemρlo 15 Utilize o método de demonstração por contradição para provar o seguinte teo rema Se a e b são dois números inteiros pares então a soma a b é um número inteiro par Nossa hipótese é p a e b são números inteiros pares e nossa tese é q a b é um número inteiro par Vamos então negar q isto é q a b é um número ímpar Considere que a 2k1 b 2k2 a b é um número ímpar Logo a b 2k3 1 onde por um lado a b 2k1 2k2 e por outro lado a b 2k3 1 Daí 2k1 2k2 2k3 1 2k1 k2 k3 1 Isso nos diz que 1 é um número par obvia mente uma contradição da qual obtemos que a b é um número par 14 Demonstração por absurdo Vídeo Esse método consiste em assumir que a hipótese e a negação da tese são verdadeiras para construir uma linha de raciocínio que nos leve a um absur do A demonstração por absurdo tem como inspiração a seguinte tautologia P p q p q c onde c é uma contradição Essa tautologia pode ser veri ficada pela tabelaverdade a seguir p q c q p q p q p q c P V V F F F V V V V F F V V F F V F V F F F V V V F F F V F V V V Sendo assim para demonstrar que um teorema é verdadeiro pelo método de demonstração por absurdo 1 Assumimos que a hipótese e a negação da tese são verdadeiras 2 Construímos uma linha de raciocínio de modo a encontrarmos um absurdo Teorema A soma dos n primeiros números naturais é nn 1 2 Demonstração Vamos inicialmente mostrar que o resultado é válido para n 1 Se n 1 temos que 1 11 1 2 1 provando que o teorema é válido para n 1 Assumindo que o teorema é válido para n k ou seja assumindo que 1 2 3 k kk 1 2 Vamos mostrar que o teorema é válido para n k 1 ou seja mostraremos que 1 2 3 k k 1 k 1k 2 2 De fato 1 2 3 k k 1 kk 1 2 k 1 kk 1 2 k 1 k 1k 2 2 Provando assim que 1 2 3 k k 1 k 1k 2 2 Desse modo podemos concluir que o teorema é válido Teorema A soma dos quadrados dos n primeiros números naturais é nn 12n 1 6 Demonstração Inicialmente vamos mostrar que o resultado é válido para n 1 Se n 1 temos que 1² 11 121 1 6 1 provando que o teorema é válido no caso n 1 Assumindo que o teorema é válido para n k ou seja assumindo que 1² 2² 3² k² kk 12k 1 6 Mostramos que o teorema é válido para n k 1 ou seja que 1² 2² 3² k² k 1² k 1k 22k 1 1 6 De fato 1² 2² 3² k² k 1² kk 12k 1 k 1² 6 kk 12k 1 k 1k 1 6 k 1k 22k 3 6 Provando assim que 1² 2² 3² k² k 1² k 1k 22k 3 6 Desse modo podemos concluir que o teorema é válido CONSIDERAÇÕES FINAIS Neste capítulo aprendemos que para afirmarmos que um teorema ou uma fórmula é verdadeira ou não precisamos realizar um procedimento matemático chamado de demonstração matemática a qual consiste em provar que o teorema ou a fórmula é verdadeira para qualquer elemento que satisfaça suas hipóteses Estudamos que é importante conhecermos os diferentes métodos de demonstração pois podemos utilizar qualquer um deles para mostrar que um teorema ou uma fórmula é verdadeira Contudo o ato de construir um raciocínio lógico para demonstrar uma proposta tornase mais fácil ou mais difícil conforme o método escolhido 2 Utilize a técnica de demonstração por contraposição para o seguinte teorema Se a é um número natural e a² é ímpar então a é um número ímpar 3 Utilize a técnica de demonstração por contradição para provar o seguinte teorema Se a é um número inteiro par e b é um número inteiro ímpar então a b é um número inteiro ímpar 4 Utilize a técnica de demonstração por indução para provar o seguinte teorema Se n é um número natural 12 32 52 2n 1² n2n 12n 1 3 REFERÊNCIAS FILHO E A Iniciação à lógica matemática São Paulo Nobel 2002 GRIMALDI R P Discrete and combinatorial mathematics an applied introduction 5 ed Boston AddisonWesley 2004 ROSEN K H Matemática discreta e suas aplicações 6 ed São Paulo McGrawHill 2009 30 Matemática Discreta 2 Teoria de conjuntos As ideias fundamentais da teoria dos conjuntos e da álgebra dos con juntos são provavelmente os conceitos mais importantes em todas as áreas da matemática e isso não é diferente na matemática discreta Este capítulo apresenta a teoria dos conjuntos O material é principal mente elementar Lembrese de que em matemática elementar não significa simples mas sim que não requer vários conhecimentos prévios para ser com preendido O material elementar pode ser bastante desafiador e parte deste capítulo talvez exija que você ajuste seu ponto de vista para compreendêlo Um ponto em especial no qual este capítulo pode divergir da sua ex periência anterior com teoria de conjuntos é o fato de realizarmos a de monstração das propriedades elementares dos conjuntos Neste capítulo você aprenderá a noção intuitiva de conjuntos como descrever um conjunto e seus subconjuntos e por fim como realizar ope rações entre conjuntos e as principais propriedades dessas operações 21 Noção intuitiva de conjuntos Vídeo Uma matilha um cacho de uvas ou um bando de pombos são exemplos de con juntos O conceito matemático de um conjunto pode ser expresso por meio desses exemplos Porém como definir um conjunto matemático Um conjunto matemático pode ser definido simplesmente como uma coleção de objetos diferentes mais precisamente Definição Um conjunto A é uma coleção de objetos distintos Vejamos o exemplo a seguir Σxemρlo 1 São exemplos de conjuntos A 1 2 3 4 5 B quadrado triângulo circunferência C Pedro Maria Welington Os conjuntos são denotados por letras maiúsculas A B C do nosso alfabeto Os objetos de um conjunto A são chamados de elementos do conjunto Se A é um conjunto formado pelos objetos a b c d escreve mos A a b c d Importante Teoria de conjuntos 31 Precisamos prestar atenção a um fato bem importante na definição de conjun tos em um conjunto não é permitida a repetição de elementos Σxemρlo 2 Não são conjuntos A 1 1 2 3 4 5 B quadrado triângulo triângulo circunferência C Pedro Maria Welington Welington Note que no Exemplo 2 A B e C não são conjuntos pelo fato de existirem repe tições entre seus elementos Quando existem repetições de elementos chamamos A B e C de multiconjuntos Um conjunto A a b c d com infinitos elementos é chamado de conjunto infinito Se a é um elemento do conjunto A escrevemos a A e dizemos que a pertence a A Se A é um conjunto e b não é um elemento de A escrevemos b A e dizemos que b não pertence a A Importante 22 Descrição e igualdade de conjuntos Vídeo A maneira mais básica de se definir um conjunto é listar seus elementos entre chaves por exemplo A 2 4 6 8 10 como feito na seção anterior Também podemos definir um conjunto fornecendo uma regra chamada lei de formação do conjunto que determina com segurança se um objeto é um membro ou não por exemplo B x 0 x 1 1 lido como B é o conjunto dos números x tal que x é maior que zero e menor que um Se A é um conjunto descrito por uma regra dizemos que um elemento b perten ce a A se b satisfaz a regra que define A Σxemρlo 3 Considere os seguintes conjuntos e suas leis de formação A x ℕ x 2t onde t é um número natural B x ℕ x 2t onde t é um número natural e 1 t 10 Descrevendo os elementos de A temos que A 2 4 6 ou seja A é o conjun to dos números pares Descrevendo os elementos de B temos que B 4 6 8 10 12 14 16 18 ou seja B é o conjunto dos números pares entre 3 e 19 Observamos que A é um conjunto infinito e B é um conjunto finito com oito elementos Note que algumas vezes a regra que define um conjunto não é satisfeita por nenhum elemento Por exemplo A a ℕ a 2t onde t é um número natural e 1 t 2 O símbolo é lido como tal que alguns autores usam 1 32 Matemática Discreta Nesse caso não existe nenhum elemento que satisfaça a regra de formação do conjunto A Quando isso acontece dizemos que o conjunto A é um conjunto vazio Mais precisamente temos a seguinte definição de conjunto vazio Definição Um conjunto que não possui nenhum elemento é chamado de conjunto vazio Escrevemos ou para representar o conjunto vazio Σxemρlo 4 São exemplos de conjuntos vazios A x x x B x x é ímpar e múltiplo de dois C x x é um triângulo e possui quatro lados D x x 0 e x 0 E x x tem 20 anos de idade e x nasceu em 1820 Na definição de conjuntos não se está exigindo nada com relação à ordem em que seus elementos aparecem ou seja a ordem não importa Isso significa por exemplo que os conjuntos A 1 3 4 7 e B 3 1 4 7 são iguais Em geral po demos definir a igualdade de dois conjuntos como Definição Dois conjuntos A e B são iguais se possuem exatamente os mesmos elementos Em símbolos escrevemos A B x x A x B E lemos A é igual a B se e somente se para todo x x pertence a A se e somente se x pertence a B Definição Dois conjuntos A e B são diferentes se existe um elemento a A tal que a B ou existe um elemento b B tal que b A Em símbolos escrevemos A B a a A e a B ou b b B e b A E lemos 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 b pertence a B e b não pertence a A A definição de igualdade de conjuntos estabelece que para provarmos que dois conjuntos A e B são iguais devemos provar que 1 Todo elemento de A também é um elemento de B 2 Todo elemento de B também é um elemento de A Teoria de conjuntos 33 Vejamos um exemplo Σxemρlo 5 Prove que os conjuntos A x 2x 4 10 e B 3 são iguais Devemos mostrar que todo elemento de A é um elemento de B e que todo ele mento de B é um elemento de A Seja a A pela definição do conjunto A a é tal que 2a 4 10 Resolvendo essa equação linear temos que a 3 ou seja a B uma vez que 3 B Note que 23 4 10 ou seja 3 satisfaz a definição do conjunto A e assim 3 A provando que A B Definição Para um conjunto finito a cardinalidade é o número de elementos que ele contém Em notação simbóli ca a cardinalidade de um conjunto A é descrita como A ou nA Se A é um conjunto com infinitos elementos dizemos que a cardinalidade de A é infinita e escrevemos A ou nA Vejamos o exemplo a seguir Σxemρlo 6 A cardinalidade do conjunto A 1 3 10 40 400 é nA 5 e a cardinalidade do conjunto B x x é um número par é nB Chamaremos de conjunto unitário todo conjunto que possui apenas um elemen to O conjunto A 27 por exemplo é um conjunto unitário Quando vamos descrever um conjunto por exemplo o conjunto A todos os homens que possuem 27 anos de idade admitimos a existência de um conjunto maior ao qual pertencem todos os elementos que compõem o conjunto que esta mos definindo Esse conjunto maior é chamado de conjunto universo e é denota do pela letra U No nosso exemplo U todos os homens Σxemρlo 7 Se A x N x 2k onde k é um número natural é o conjunto dos números naturais pares o universo U é o conjunto de todos os números naturais Utilizando a definição de conjunto universo podemos introduzir um novo con junto com base em um conjunto dado A 34 Matemática Discreta Definição Dado um conjunto A e seja U seu conjunto universo o conjunto dos elementos que pertencem a U e não pertencem a A é chamado de conjunto complementar de A Denotamos o complementar de A por AC ou CA Vejamos no exemplo a seguir Σxemρlo 8 Se A x ℕ x 2k onde k é um número natural é o conjunto dos números naturais pares sabemos que seu universo U é o conjunto de todos os números naturais Desse modo pela definição de complementar temos AC x ℕ x 2k onde k é um número natural Ou seja AC é o conjunto dos números naturais ímpares Nesta seção você aprendeu a classificar vários objetos da vida real em termos de conjuntos Além disso vimos diferentes maneiras de descrever um conjunto e como podemos considerar um conjunto como parte menor de um conjunto maior chamado de conjunto universo Introduzindo a noção de subconjunto vamos na próxima seção explorar o fato de podermos considerar um conjunto como uma parte menor de outro conjunto 23 Subconjuntos Vídeo Consideremos os seguintes conjuntos A capitais brasileiras e B São Paulo Porto Alegre Curitiba Observamos que todos os elementos do conjunto B também são elementos do conjunto A pois São Paulo Porto Alegre e Curitiba são capitais brasileiras Nesse caso dizemos que o conjunto B é um subconjunto do conjunto A O mesmo acontece com os conjuntos C 0 10 7 8 79 5 e D 0 7 5 onde D é um subconjunto de C A definição matemática de subconjunto é apresentada a seguir Definição Um conjunto B é subconjunto de um conjunto A se e somente se todo elemento de B for um elemento de A Vejamos no exemplo a seguir Escrevemos B A se B é um subconjunto de A Nesse caso também dizemos que B está contido em A Em símbolos temos B A b B b A Escrevemos B A se B não é subconjunto de A Nesse caso dizemos que B não está contido em A Todo conjunto A é um subcon junto do seu universo U Importante Teoria de conjuntos 35 Σxemρlo 9 a b a b c b c d c x x é um número natural par x x é um número natural Podemos representar a inclusão de conjuntos de modo gráfico por meio do Dia grama de Venn Seja A um conjunto U seu universo e B A graficamente temos A B U Teorema A inclusão de conjuntos satisfaz as seguintes propriedades a A para todo conjunto A b A A reflexiva c Se A B e B A então A B antissimétrica d Se A B e B C então A C transitiva Demonstração O item a pode ser descrito na seguinte proposição x x A Onde temos p x e q x A Como p é falsa pois não há elementos em a proposição é sempre verdadeira pois p q é sempre verdadeira Provando então que A O item b segue do fato de que se x A então x A O item c segue da definição de igualdade de conjuntos Para o item d temos seja x A então como A B temos que x B mas B C onde x C ou seja A C Pela definição de igualdade de conjuntos dois conjuntos A e B são iguais se e somente se A B e B A Importante 36 Matemática Discreta Σxemρlo 10 Considere os conjuntos A números naturais B números naturais pares e C números naturais que dividem 4 Temos que a B A e nB nA b C A e nC 3 nA A inclusão de conjuntos e seus complementares está relacionada ao seguinte teorema Teorema Sejam A e B dois conjuntos e AC e BC seus complementares se A B então BC AC Demonstração Seja x BC então pela definição de conjunto complementar temos que x B Como A B temse que x A ou seja x AC Provando assim que BC AC Definição Para qualquer conjunto A definimos o conjunto das partes de A denotado por A como sendo o conjunto formado por todos os subconjuntos de A Em símbolos A B B A Observamos que pela definição de conjunto das partes A e A A para todo conjunto A Vejamos um exemplo de como encontrar o conjunto das partes de um conjunto A Σxemρlo 11 Seja A 1 11 0 então o conjunto das partes de A é A 0 1 11 111 10 110 1110 No exemplo é possível notar que se nA então a cardinalidade de A também será finita além disso teremos que nA nA Na verdade é possível provar que nA 2nA Obviamente nA se nA 24 Operações com conjuntos Vídeo Em teoria de conjuntos assim como em todos os tópicos estudados em mate mática estamos interessados em definir e compreender operações matemáticas que podem ser realizadas entres seus objetos Nesta seção vamos definir as princi pais operações entre conjuntos Observamos a seguinte proprie dade elementar da inclusão de conjuntos Se A B então nA nB Importante Teoria de conjuntos 37 Começaremos com a interseção Definição A interseção entre os conjuntos A e B é o conjunto AB formado pelos elementos que estão simultanea mente em A e B Em símbolos AB x x A e x B O Diagrama de Venn da interseção de dois conjuntos é dado por A B AB Vejamos um exemplo a seguir Σxemρlo 12 Sejam A 1 e B 1 a Θ então AB 1 A definição de interseção de conjuntos pode ser generalizada para uma quanti dade finita de conjuntos conforme segue Definição A interseção entre os conjuntos A1 A2 An é o conjunto A1A2An formado pelos elementos que estão simultaneamente em A1 A2 An Em símbolos i 1 n iA A1A2An x x A1 e x Ai i 2 3 n Vejamos um exemplo Σxemρlo 13 Vamos representar as diversas interseções que podem ser estudadas com rela ção aos conjuntos A 0111 001 10 00 010 B 01 11 001 101 011 111 e C 0111 011 101 10 000 110 38 Matemática Discreta A B C 001 00010 111 0111 000110 10 101011 Temos que ABC 01 11 AB 01 11 001 AC 01 11 10 BC 01 11 101 011 Definição Dois conjuntos A e B são ditos conjuntos disjuntos se AB ou seja se A e B não possuem elementos em comum Σxemρlo 14 Sejam A 101 111 e B 010 100 então AB Apresentaremos a seguir algumas das principais propriedades da interseção entre conjuntos As propriedades são apresentadas considerando em geral a in terseção entre dois ou três conjuntos mas podem ser facilmente generalizadas para a interseção de n conjuntos Teorema Sejam A e B dois conjuntos tais que A B então AB A Demonstração Vamos mostrar que AB A e A AB De fato seja x AB isso significa que x A e x B e como x A prova que AB A Seja agora y A como A B temos que y B isto é y AB provando que A AB Concluímos então que AB A Σxemρlo 15 Sejam A 1010 0101 e B 1010 1001 1111 0101 então como A B AB A 1010 0101 Teoria de conjuntos 39 Teorema Sejam A e B dois conjuntos quaisquer então AB B e AB A Demonstração Vamos mostrar apenas a primeira inclusão já que a segunda é análoga Seja x AB então x A e x B onde x B provando que AB B Σxemρlo 16 Sejam A 11010 10110 e B 11010 11111 00000 então AB 11010 11010 11111 00000 Teorema Sejam A B e C conjuntos quaisquer se A B então CA CB Demonstração Seja x CA x C e x A B x C e x B x CB onde CA CB Σxemρlo 17 Sejam A 101 111 B 101 111 110 001 e C 001 111 então A B e AC 111 111 001 BC Teorema propriedades fundamentais da interseção de conjuntos Sejam A B e C conjuntos quaisquer e U o conjunto universo a interseção de conjuntos satisfaz as seguintes propriedades a A b AAC c AA A idempotente d AU A elemento neutro e AB BA comutativa f ABC ABC associativa Demonstração Provaremos apenas a propriedade associativa seja x ABC x A e x BC x A e x B e x C x A e x B e x C x AB e x C x ABC então temos que ABC ABC Outra operação importante entre dois ou mais conjuntos é a operação de união que consiste em reunir elementos para formar um novo conjunto Mais pre cisamente a união de conjuntos é definida como segue 40 Matemática Discreta Definição A união entre os conjuntos A e B é o conjunto AB formado pela reunião dos elementos de A e B Em símbolos AB x x A ou x B Vejamos o exemplo a seguir Σxemρlo 18 Sejam A 11 e B 1 11 α β então AB 1 11 α β A definição de união de conjuntos pode ser generalizada para uma quantidade finita de conjuntos conforme segue Definição A união entre os conjuntos A1 A2 An é o conjunto A1A2An formado por todos os elementos de A1 A2 An Em símbolos i 1 n iA A1A2An x x A1 ou x Ai i 2 3 n Vejamos o exemplo a seguir Σxemρlo 19 Vamos representar a união dos conjuntos A 01 11 001 10 00 010 B 01 11 001 101 001 111 e C 01 11 011 101 10 000 110 Um ponto importante que devemos notar ao escrever a união de conjuntos é que nunca repetiremos elementos ou seja cada elemento deverá aparecer uma única vez no conjunto união Sendo assim temos ABC 01 11 001 00 010 101 001 111 011 10 000 110 A seguir apresentaremos algumas das principais propriedades da união de con juntos As propriedades são apresentadas considerando em geral a união entre dois ou três conjuntos porém podem ser facilmente generalizadas para a união de n conjuntos Teoria de conjuntos 41 Teorema Sejam A e B dois conjuntos então A AB e B AB Demonstração Vamos mostrar que A AB De fato seja x A isso significa que x A ou x B isto é x AB provando que A AB Σxemρlo 20 Sejam A e B 111 101 então AB 111 101 e claramente A AB assim como B AB Teorema Sejam A e B dois conjuntos então AB B A B Demonstração De fato já sabemos que A AB Como AB B temos que A B Agora sabendo que A B vamos mostrar que AB B De fato já sabemos que B AB isso significa que basta provarmos que AB B para termos a igual dade AB B Então se x AB isso significa que x A ou x B mas A B Em qualquer caso teremos que x B se x AB temos que x B provando que AB B Σxemρlo 21 Sejam A 4 7 e B 4 7 8 9 então AB 4 7 8 9 B Teorema Sejam A B e C conjuntos tais que A C e B C então AB C Demonstração De fato seja x AB então por definição x A ou x B Como A C e B C segue que x A C ou x B C ou seja x C Provando que AB C Teorema propriedades fundamentais da união de conjuntos Sejam A B e C conjuntos quaisquer e U o conjunto universo a união de conjun tos satisfaz as seguintes propriedades a A A elemento neutro b AU U c AAC U d AA A idempotente e AB BA comutativa f ABC ABC associativa Agora é com você faça a demons tração de que B AB Desafio 42 Matemática Discreta Σxemρlo 22 Sejam A α θ e B 101 111 110 então AB α θ 101 111 110 BA Podemos também combinar as operações de união e interseção de conjun tos para obter um novo conjunto A combinação das operações de interseção e união de conjuntos satisfaz as seguintes propriedades que são chamadas de leis de absorção Teorema Sejam A e B conjuntos então AAB A e AAB A Demonstração Sabemos que A AB e assim segue do teorema ilustrado no Exemplo 15 que AAB A De maneira análoga temos que AAB A Duas propriedades importantes na combinação entre união e interseção de conjuntos são as propriedades de distributividade que são equivalentes às pro priedades de distributividade com relação à soma e multiplicação de números reais A seguir vamos enunciar e provar as propriedades de distributividade da interseção e união de conjuntos Teorema Sejam A B e C conjuntos então valem as seguintes distributivas a ABC ABAC b ABC ABAC Demonstração Para provar essas propriedades utilizaremos as leis distributivas da lógica ma temática Vamos provar o item a Seja x ABC x A e x BC x A e x B ou x C x A e x B ou x A e x C x AB ou x AC x ABAC Provando que ABC ABAC Agora é com você faça a demons tração do item b Desafio Teoria de conjuntos 43 Σxemρlo 23 Considere A 1 2 B 0 1 3 4 e C 1 4 5 Note inicialmente que BC 1 4 onde ABC 1 2 4 Por outro lado temos que AB 0 1 2 3 4 e AC 1 2 4 5 onde ABAC 1 2 4 Sendo assim ABC ABAC Vamos agora demonstrar um teorema muito importante conhecido como Leis de De Morgan para conjuntos Essas leis recebem esse nome porque sua demonstra ção é feita com base nas Leis de De Morgan da lógica matemática Teorema Leis de De Morgan Sejam A e B conjuntos então valem as seguintes leis de De Morgan a ABC ACBC b ABC ACBC Demonstração Vamos provar o item a Seja x ABC x AB x AB x A e x B x A ou x B x A ou x B x AC ou x BC x ACBC Uma terceira operação importante entre conjuntos é a diferença entre conjun tos a qual está definida a seguir Definição A diferença entre os conjuntos A e B é o conjunto AB 2 formado pelos elementos de A que não estão em B Em símbolos AB x x A e x B A diferença entre conjuntos pode ser denotada também por A B 2 Vejamos o exemplo a seguir Σxemρlo 24 Sejam A 0 3 7 e B 3 5 7 dois conjuntos então AB 0 e BA 5 Agora é com você faça a demons tração do item b Desafio A diferença entre dois conjuntos A e B não é comutativa ou seja AB BA Importante 44 Matemática Discreta Teorema Sejam A B e C conjuntos em um universo U então valem as seguintes proprie dades relacionadas com a diferença entre conjuntos a A A b UA AC c AA d AAC A e ABC ACB f AB BCAC g ABC ABC h ABC ABAC Demonstração Vamos provar apenas o item g Seja x ABC temos por definição da opera ção de diferença de conjuntos que x ABC x AB e x C x A e x B e x C x A e x B e x C x A e x B e x C x A e x B ou x C x A e x BC x ABC Ou seja ABC ABC Para finalizar este capítulo iremos apresentar alguns exemplos de como pode mos utilizar operações entre conjuntos para analisar afirmações ou um conjunto de afirmações Σxemρlo 25 Dado que Pedro é um homem e que todos os homens são mortais mostre que Welington é mortal Vamos utilizar a propriedade de que se A B e B C então A C Sejam U Conjunto de todos os seres vivos B Conjunto de todos os seres humanos C Conjunto de todos os mortais A Conjunto unitário cujo único elemento é Pedro Temos que A B B C Logo A C onde Pedro é mortal Teoria de conjuntos 45 Σxemρlo 26 Em uma escola de 1000 alunos 800 gostam de sorvete de chocolate 700 gos tam de sorvete de morango e 600 gostam dos dois sabores Quantos alunos não gostam de nenhum dos dois sabores Seja U Alunos da escola A Alunos que gostam de sorvete de chocolate e B Alunos que gostam de sorvete de morango Vamos construir o Diagrama de Venn após analisar os dados Temos que nAB 600 ou seja 600 alunos gostam dos sabores chocolate e morango Para sabermos quantos alunos gostam apenas do sabor chocolate fazemos a subtração da quantidade de alunos que gostam desse sabor pela quantidade de alunos que gostam de ambos os sabores Assim nA AB 800 600 200 Agora para determinarmos a quantidade de alunos que gostam apenas do sabor morango o processo é análogo ao anterior fazemos nB AB 700 600 100 Sabemos que nU 1000 que é composto pela quantidade de alunos que gos tam apenas do sabor chocolate de ambos os sabores apenas do sabor de moran go e alunos que não gostam de nenhum dos dois sabores logo nU nAAB nAB nBAB nUAUB 200 600 100 nUAUB Sendo assim nUAUB 1000 900 100 ou seja 100 alunos não gostam de nenhum dos sabores O Diagrama de Venn ficará da seguinte forma Alunos da escola Chocolate e morango 600 Chocolate Morango 100 200 100 Podemos definir outras operações entre conjuntos Uma operação bem conhe cida é a diferença simétrica entre conjuntos Saiba mais sobre essa operação na página Matemática Essencial da UEL Disponível em httpwwwuelbr projetosmatessencialbasicomedio conjuntoshtmlsec11 Acesso em 5 mar 2021 Saiba mais Sempre que você for resolver um exercício com interseções e uniões de conjuntos inicie anotando a cardinalidade das interseções e lembrese de que as subtrações da cardinalidade de cada conjunto com a interseção são realizadas para que não façamos a soma de cada interseção mais de uma vez ou seja para determinar a cardinalidade apenas de cada conjunto sem a interseção Importante 46 Matemática Discreta CONSIDERAÇÕES FINAIS Neste capítulo você aprendeu os conceitos fundamentais de teoria de conjuntos as diferentes formas de descrevêlos e como relacionálos com objetos da vida real Pôde entender ainda como realizar várias operações básicas entre conjuntos que estão diretamente relacionadas com fatos e temas de estudos da matemática discreta Por fim compreendeu como podemos utilizar a teoria de conjuntos para demons trar afirmações matemáticas ATIVIDADES 1 Demonstre a propriedade comutativa da interseção de conjuntos Mais precisamente demonstre que dados dois conjuntos A e B então AB BA 2 Prove que se A B e C são conjuntos então ABC ABBC 3 Verifique a validade da seguinte lei de De Morgan se A e B são conjuntos então ABC ACBC 4 Prove que se A e B são conjuntos então AB BCAC REFERÊNCIAS IEZZI G MURAKAMI C Fundamentos da matemática elementar São Paulo Atual 2013 FILHO E A Teoria elementar dos conjuntos São Paulo Nobel 1980 ROSEN K H Matemática discreta e suas aplicações São Paulo McGrawHill 2009 GRIMALDI R P Discrete and combinatorial mathematics an applied introduction 5 ed Boston Addison Wesley 2004 Conjuntos numéricos 47 3 Conjuntos numéricos Você deve concordar que o conceito fundamental em matemática é a ideia de número Mais ainda é provável que a primeira palavra que surge na sua cabeça ao pensar em matemática seja números A ideia de número se desenvolveu com a capacidade de contar e vem evo luindo conforme a evolução da matemática como ciência Da necessidade de contar objetos surgiram os números naturais que já foram representados por diversas notações até chegar à notação que utilizamos hoje Com o desenvolvi mento de novos problemas matemáticos fezse necessária a criação de novos conjuntos numéricos inteiros racionais reais e imaginários Neste capítulo você vai aprender os principais conjuntos numéricos suas principais operações e propriedades Além disso vai aprender a trabalhar com aritmética modular uma ferramenta fundamental para que nossos computa dores realizem tarefas como executar um vídeo da internet de modo pratica mente instantâneo 31 Conjunto dos números naturais Vídeo Deus criou os números naturais todo o resto é obra do homem Essa frase foi dita pelo famoso matemático alemão Leopold Kronecker 18231891 para dar ênfase à importância dos números naturais Na verdade toda a sistemática dos conjuntos numéricos conhecidos na ma temática pode ser feita por meio dos números que utilizamos para contar Esses números são conhecidos como números naturais Definição Chamamos de conjunto dos números naturais denotando por o conjunto formado pelos números 1 2 3 1 2 3 Assumiremos que já é sabido que podemos realizar duas operações fundamen tais com números naturais adição e multiplicação Essas operações satisfazem al gumas propriedades bem interessantes que serão anunciadas em seguida Teorema A operação da adição de números naturais satisfaz as propriedades a seguir 48 Matemática Discreta a Associativa da adição a b c a b c para todo a b c b Comutativa da adição a b b a para todo a b Observamos que na definição apresentada o número zero não pertence ao conjunto dos números naturais já que a criação dos números naturais se dá com o objetivo de contagem por exemplo para um pastor contar suas ovelhas Sendo assim não incluímos o zero como número natural afinal ninguém conta zero ovelhas Em algumas oportunidades é conveniente trabalhar com o número zero Sendo assim vamos denotar por 0 o conjunto dos números naturais unido ao elemento zero ou seja 0 0 Nesse caso chamaremos o zero de elemento neutro da adição em 0 pois para todo a temos que a 0 a A multiplicação de números naturais também possui propriedades bem defini das a saber Teorema A operação de multiplicação de números naturais satisfaz as propriedades a seguir a Associativa da multiplicação abc abc para todo a b c b Comutativa da multiplicação ab ba para todo a b c Elemento neutro da multiplicação a 1 a para todo a d Distributiva da multiplicação relativamente à adição ab c ab ac para todo a b c Outra propriedade importante que os números naturais satisfazem é a proprie dade conhecida como tricotomiaI enunciada a seguir Dados a b pode ocorrer exatamente uma das três alternativas seguintes a b Existe p tal que a b p Existe q com b a q Além das suas propriedades operatórias e da propriedade da tricotomia o con junto dos números naturais possui outra propriedade muito importante a orde nação dos números naturais que diz que dados dois números naturais diferentes existe sempre um maior que o outro A ordenação dos números naturais é chamada de relação de ordem A relação de ordem no conjunto dos números naturais é definida da seguinte forma Conjuntos numéricos 49 Definição Dados a b dizemos que a é menor que b e escrevemos a b se existe p tal que b a p Nessas condições dizemos que b é maior que a Também podemos utilizar a notação a b para dizer que um número a é menor ou igual a um número b ou seja quando a b p com p 0 Teorema A relação de ordem dos números naturais satisfaz as propriedades a seguir a Transitividade se a b e b c então a c b Tricotomia dados a e b pode ocorrer exatamente uma das alternativas a b ou a b ou b a c Monotonicidade da adição se a b então para todo p temse a p b p Demonstração Vamos demonstrar apenas os itens a e c Para o item a suponhamos que a b e b c Isso significa que existem p q tais que b a p e c b q em que c a p q a p q ou seja a c Para o item c temos que a b em que existe q tal que a q b Sendo assim a p q b p ou seja a p b p As propriedades do teorema apresentado continuam verdadeiras quando con sideramos Além disso podemos descrever uma propriedade de monotonicidade para multiplicação mais precisamente Teorema A relação de ordem dos números naturais satisfaz a seguinte propriedade de monotonicidade da multiplicação Se a b e p então ap bp A demonstração desse fato segue diretamente da propriedade distributiva da multiplicação com relação à soma de números naturais Outra propriedade importante é a propriedade do corte ou propriedade do cancelamento a qual é utilizada com frequência quando estamos fazendo cálculos e comparações de números naturais A lei do corte para números naturais é dada pelo seguinte teorema Teorema lei do corte Sejam a b e c números naturais tais que c 0 e ac bc Então a b Demonstração Suponhamos por contraposição que a b Por tricotomia a b ou b a Se a b existe m tal que b a m em que bc a mc ac mc Logo ac bc Se a b existe n tal que a b n em que ac b nc bc nc Logo ac bc Sendo assim se ac bc então a b Agora é com você prove o item b Desafio 50 Matemática Discreta Existem infinitos números naturais ou seja a cardinalidade do conjunto dos números naturais é infinita Esse fato é enunciado e demonstrado no teorema a seguir Teorema O conjunto dos números naturais tem cardinalidade infinita isto é n Demonstração Suponhamos que é um conjunto finito Então utilizando a tricotomia para comparar todos os elementos de dois a dois obtemos um natural b maior que todos os elementos de Mas b 1 também é natural e é maior que b uma con tradição provando que tem cardinalidade infinita Para encerrar esta seção demonstraremos um teorema muito importante pois possui várias aplicações em especial na computação Esse teorema é conhecido como teorema fundamental da aritmética e indica que todo número natural pode ser escrito como a multiplicação de números primos Lembramos que a definição de número primo é dada por Definição Um número natural p é chamado de número primo quando p 1 e não existem a b tais que p ab Entre os cem primeiros números naturais temos os seguintes números primos 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 Teorema teorema fundamental da aritmética Se b então b pode ser escrito de maneira única como o produto de nú meros primos Demonstração Vamos utilizar um método de demonstração conhecido como segundo princípio da indução Seja b e suponha que todo número natural menor que b pode ser escrito como o produto de fatores primos então b é primo nesse caso b é trivial mente um produto de fatores primos ou b cd com c b e d b Pela hipótese de indução c e d podem ser escritos como o produto de fatores primos Sendo assim o teorema é válido Conjuntos numéricos 51 32 Conjunto dos números inteiros Vídeo Ao longo do tempo com o desenvolvimento de novos problemas matemáti cos fezse necessária a ampliação do conjunto dos números naturais de modo que fosse possível por exemplo obter a solução de uma equação do tipo x 3 1 Ou seja foi preciso estender o conjunto dos números naturais para um conjunto que apresentasse entre seus elementos números negativos Esse conjunto é chamado de conjunto dos números inteiros e é definido da seguinte maneira Definição Chamamos de conjunto dos números inteiros denotado por o conjunto formado pelos números 3 2 1 0 1 2 3 3 2 1 0 1 2 3 O conjunto dos números inteiros possui alguns subconjuntos notáveis a saber 0 1 2 3 0 chamado de conjunto dos números inteiros não negativos 3 2 1 0 chamado de conjunto dos números inteiros não positivos 3 2 1 1 2 3 chamado de conjunto dos inteiros não nulos Assim como no caso do conjunto dos números naturais o conjunto dos nú meros inteiros também apresenta um número infinito de elementos Esse fato é sintetizado no seguinte teorema Teorema O conjunto dos números inteiros possui cardinalidade infinita isto é n Demonstração Segue desse fato que n e A grande importância dos números inteiros se dá pelo fato de que podemos realizar três das quatro operações fundamentais adição subtração e multiplica ção Vamos assumir que essas operações já nos são conhecidas Sendo assim ire mos rever apenas algumas notações e propriedades Existem algumas diferenças básicas nas propriedades operatórias da multiplica ção e da soma quando consideramos o conjunto dos números inteiros em relação ao conjunto dos números naturais Podemos citar por exemplo a existência de um elemento simétrico da adição ou seja dado a existe um elemento b tal que a b 0 Nesse caso denotamos b a A operação de subtração de números inteiros não é simétrica pois é claro que por exemplo 1 3 3 1 A seguir elencamos algumas propriedades operatórias Teorema As operações de adição e subtração de números inteiros satisfazem as proprie dades a seguir a Associativa da adição e subtração a b c a b c para todo a b c 52 Matemática Discreta b Comutativa da adição a b b a para todo a b c Elemento neutro da adição e subtração a 0 a para todo a Além disso existem propriedades análogas para a operação de multiplicação de números inteiros Teorema A operação de multiplicação de números inteiros satisfaz as propriedades a seguir a Associativa da multiplicação abc abc para todo a b c b Comutativa da multiplicação ab ba para todo a b c Elemento neutro da multiplicação a 1 a para todo a d Distributiva da multiplicação relativamente à adição e à subtração ab c ab ac para todo a b c O elemento 0 é chamado de elemento absorvente da multiplicação pois 0 b b 0 0 para todo b Além disso a multiplicação de números inteiros satisfaz a chamada regra de sinais Vejamos dados a b então a multiplicação de a e b é tal que ab ab ab ab ab 0 se e somente se a 0 ou b 0 A lei do corte pode ser estendida para números inteiros da seguinte forma Teorema lei do corte para números inteiros Se 0 a então ab ac b c para todo b c Outra operação fundamental entre números inteiros é a operação de divisão inteira Essa operação é esquematizada pelo algoritmo da divisão de Euclides sejam a b com b 0 podemos escrever a da seguinte forma a bq r em que q r são únicos para 0 r b Nesse caso dizemos que q é o quociente da divisão e r é o resto da divisão Σxemρlo 1 Considerando os números inteiros 2 15 e 10 temos a 2 15 0 2 b 10 25 0 c 15 27 1 Note que no item b do exemplo temos que o resto é zero Nesse caso temos que a 10 é um múltiplo de b 2 Isso nos leva à definição de divisor de um nú mero inteiro Definição Seja a b Z dizemos que b divide a ou que b é divisor de a ou ainda que a é divisível por b se existe q Z tal que a bq Se não existe q Z dizemos que b não divide a Observamos então que b divide a se e somente se o resto da divisão de a por b é zero Vamos escrever b a para representar que b divide a Se b não divide a vamos escrever b a Vejamos um exemplo Exemplo 2 Considerando os números inteiros 2 10 e 13 temos que 2 10 e 2 13 A noção de divisibilidade possui propriedades importantes as quais nos ajudam a operar e encontrar os divisores de um número Essas propriedades estão elencadas no seguinte teorema Teorema Sejam a b c Z temos que a Se a b e b c então a c b Se a b e b a então a b c Se a b 0 e a b então a b Demonstração Vamos demonstrar apenas o item a Se a b e b c então existem m n Z tais que b na e c mb em que c mna e isso significa que a c Lembramos que módulo ou valor absoluto de um número a Z é definido por a a se a 0 a se a 0 54 Matemática Discreta 33 Conjunto dos números racionais Vídeo A fim de definir a divisão de dois números iremos estender o conjunto dos números inteiros para um conjunto maior chamado de conjunto dos números racio nais Note que a divisão de dois números inteiros nem sempre tem como resultado um número inteiro por exemplo 3 e 2 porém 3 2 ou seja não é um número inteiro O conjunto dos números racionais é definido da seguinte maneira Definição Chamamos de conjunto dos números racionais denotado por o conjunto formado pelas frações p q em que p q e q 0 Para b p q chamamos p de numerador e q de denominador de b Dizemos que dois números racionais p q e r s são iguais se ps rq Note por exemplo que os números racionais 9 4 e 18 8 são iguais As operações de adição subtração multiplicação e divisão de números racio nais são definidas da seguinte forma Definição operações fundamentais de números racionais Sejam p q e r s então as operações de adição subtração multiplicação e divisão são definidas como a p q r s ps rq qs b p q r s pr qs c p q p q r s s r ps qr O conjunto dos números racionais possui alguns subconjuntos notáveis a saber chamado de conjunto dos números racionais não negativos chamado de conjunto dos números racionais não positivos chamado de conjunto dos números racionais não nulos Teorema As operações de adição e subtração de números racionais satisfazem as pro priedades a seguir Note que se a ou a então a Importante a Associativa da adição e da subtração p q r s c p q r s d para todo p r c s d Q b Comutativa da adição p q r s r s p q para todo p q r s Q c Elemento neutro da adição e da subtração p q 0 p q para todo p q Q d Elemento oposto da adição p q p q 0 para todo p q Q Demonstração Vamos demonstrar apenas o item b Temos por um lado que p q r s ps rq qs sp qr sq Por outro lado r s p q rq sp sq sp qr sq Sendo assim p q r s r s p q Teorema A operação de multiplicação de números racionais satisfaz as propriedades a seguir a Associativa da multiplicação p q r s c p q r s d para todo p q r s c Q b Comutativa da multiplicação p q r s r s p q para todo p q r s Q c Elemento neutro da multiplicação p 1 p q para todo p q Q d Elemento inverso da multiplicação p q p 1 para todo p q Q e Distributiva da multiplicação relativamente à adição e à subtração p q r s p q c d p q r s c d para todo p q r s Q Demonstração Vamos demonstrar apenas o item b Pela definição de igualdade de números racionais verificamos que o produto pr sq qs rp isso é claro pelas propriedades de números inteiros 56 Matemática Discreta I O número decimal é exato ou seja o número de algoritmos é finito Por exemplo a 1 2 05 b 6 2 30 II O número decimal é uma dízima periódica ou seja tem infinitos algoritmos que se repetem periodicamente Por exemplo a 1 3 0333 b 2 7 0285714285714 O caminho inverso nem sempre é verdadeiro ou seja dado um número escrito em sua forma decimal nem sempre é possível escrevêlo na forma de fração Esses números são chamados de números irracionais 34 Números reais e cardinalidade Vídeo Para finalizar nosso estudo sobre conjuntos numéricos vamos definir um con junto numérico maior que abrange todos os conjuntos já estudados Esse conjunto recebe o nome de conjunto dos números reais Definição Chamamos de conjunto dos números reais denotado por o conjunto formado pelos números com representação decimal finita ou periódica chamados de números racionais e pelos decimais infinitos não periódicos chamados de números irracionais Observamos que pela definição de números reais As operações de adição subtração multiplicação e divisão de números reais satisfazem todas as propriedades operatórias já enunciadas para os demais conjuntos numéricos O conjunto dos números reais possui alguns subconjuntos notáveis A saber chamado de conjunto dos números reais não negativos chamado de conjunto dos números reais não positivos chamado de conjunto dos números reais não nulos Ao estudarmos conjuntos definimos a cardinalidade de um conjunto finito como seu número de elementos Desse modo dizemos que dois conjuntos pos suem a mesma cardinalidade se apresentam o mesmo número de elementos Vamos estender a ideia de igualdade entre cardinalidade para conjuntos com in finitos elementos O número irracional mais fa moso que existe é o número 3141592653589 o qual possui infinitas casas deci mais e é conhecido como π No vídeo Para que serve o Pi e por que esse número causa tanto fascínio produzido pela BBC News Brasil você vai encontrar uma pequena descrição e várias curiosida des sobre o número π Disponível em httpswwwyoutube comwatchvvY6965UdcLI Acesso em 5 mar 2021 Vídeo Definição Dois conjuntos A e B possuem a mesma cardinalidade se e somente se existe uma bijeção f A B Uma bijeção f A B é uma função que associa cada elemento de A a um único elemento de B e viceversa a cada elemento de B um único elemento de A Também chamamos esse tipo de associação de associação biunívoca ou um para um Utilizaremos a definição anterior para classificar os conjuntos de cardinalidade infinita em dois grupos diferentes o grupo dos conjuntos que possuem a mesma cardinalidade do conjunto dos números naturais e o grupo dos conjuntos que possuem cardinalidade diferente Definição Um conjunto que é finito ou tem a mesma cardinalidade do conjunto dos números naturais é chamado de conjunto enumerável ou conjunto contável Quando um conjunto infinito A é enumerável indicamos a cardinalidade de A por nA ℵ₀ ℵ é alef a primeira letra do alfabeto hebraico e dizemos que A tem cardinalidade alef zero Definição Um conjunto que não é contável é chamado de incontável ou não enumerável Vejamos um exemplo Exemplo 3 Vamos mostrar que o conjunto dos números inteiros é enumerável Demonstração Basta considerarmos f N Z dada por fn n2 se n é par n 12 se n é ímpar É fácil perceber que f é uma bijeção 58 Matemática Discreta 35 Aritmética modular Vídeo Para finalizar este capítulo iremos introduzir a ideia de congruência modular A teoria de congruência modular é muito rica e extensa Além disso possui várias aplicações por exemplo na leitura de um CD Durante esta seção iremos estudar os conceitos básicos de congruência modular Definição Seja m um número natural dizemos que a b são congruentes módulo m e escrevemos a b mod m se m divide a b ou seja se b a km para um certo k Vejamos um exemplo Σxemρlo 4 a Se m 10 temos 32 2 mod 10 já que 32 2 310 b Se m 2 temos 27 5 mod 2 já que 27 5 162 Consideremos as seguintes congruências 28 7 mod 3 26 4 mod 3 Note que 28 26 7 4 mod 3 pois 28 26 7 4 51 173 Esse fato nos indica que podemos somar congruências Podemos resumir essa propriedade no seguinte teorema Teorema Sejam m e a b c d tais que a b mod m c d mod m Então a c b d mod m Além disso podemos multiplicar congruências conforme enunciado no próxi mo teorema Teorema Sejam m e a b c d tais que a b mod m c d mod m Então ac bd mod m Vejamos um exemplo Σxemρlo 5 Sejam 2 5 mod 7 e 5 16 mod 7 Então pelo teorema da multiplicação de congruências temos que 25 516 mod 7 A aritmética modular está presente em vários campos da nossa vida No site Campus Code você irá en tender como funciona a validação de documentos como o CPF Disponível em httpswww campuscodecombrconteudoso calculododigitoverificador docpfedocnpj Acesso em 5 mar 2021 Saiba mais Conjuntos numéricos 59 Uma outra propriedade da congruência é que para qualquer a e m a 0 mod m se e somente se a é múltiplo de m Além disso dado um número natural m fixo qualquer número inteiro pode ser descrito por uma con gruência com m Teorema Sejam m e a então existe um único r 0 1 m 1 tal que a r mod m Demonstração Dividindo a por m utilizando o algoritmo da divisão de Euclides temos a qm r com r 0 1 m 1 Logo a r qm e isso significa que a r mod m A unicidade de r é clara pois o resto da divisão é único Σxemρlo 6 Se m 6 temos 40 4 mod 6 já que 40 4 66 Nesse caso temos a 40 e r 4 0 1 2 3 4 5 A operação de congruência módulo m é uma relação de equivalência ou seja satisfaz as propriedades a seguir Teorema Sejam m e a b c a Reflexiva a a mod m b Simétrica se a b mod m então b a mod m c Transitiva se a b mod m e b c mod m então a c mod m Demonstração Vamos provar apenas o item c Como m a b e m b c existem inteiros s e t tais que b a sm c b tm em que c a s tm e isso significa que a c mod m Σxemρlo 7 Se m 6 temos 40 4 mod 6 e 4 22 mod 6 Sendo assim pelo item c do teo rema apresentado temos que 40 22 mod 6 Agora é com você prove os itens a e b Desafio No livro Códigos correto res de erros você pode aprofundar seus conheci mentos sobre aritmética modular por meio de reflexões valiosas sobre as propriedades operatórias das classes residuais e apli cações do tema na teoria de informação HEFEZ A VILLELA M L T Rio de Janeiro IMPA 2017 Livro CONSIDERAÇÕES FINAIS Neste capítulo você aprendeu conceitos fundamentais dos principais conjuntos numéricos as operações essenciais e suas propriedades operatórias Compreendeu o conceito de divisibilidade e como podemos aplicálo para resolver problemas matemáticos Por fim você aprendeu a trabalhar com aritmética modular presente em várias aplicações de tecnologia e de segurança como na criação de um código de barras ou de um número de CPF ATIVIDADES 1 Mostre que se a b Z com a b 0 e a b então a b 2 Sejam pq rs Q mostre que pq rs cd pq rs cd 3 Demonstre o seguinte teorema sejam m N e a b c d Z tais que a b mod m c d mod m então a c b d mod m 4 Mostre que a Z é par se e somente se a 0 mod 2 e que a é ímpar se e somente se a 1 mod 2 REFERÊNCIAS GRIMALDI R P Discrete and combinatorial mathematics an applied introduction 5 ed Boston AddisonWesley 2004 IEZUI G MURAKAMI C Fundamentos da matemática elementar 1 conjuntos funções São Paulo Atual 2013 LIPSCHUTZ S LIPSON M Matemática discreta 2 ed Porto Alegre Bookman 2004 ROSEN K H Matemática discreta e suas aplicações 6 ed São Paulo McGrawHill 2009 Relações 61 4 Relações Ao estudarmos a teoria elementar de conjuntos aprendemos a realizar diversas operações e comparações entre conjuntos Porém quando apro fundamos nossos estudos em matemática geralmente também estamos interessados em comparar os elementos dos conjuntos e não apenas os conjuntos Por exemplo é mais comum comparar números em relação à ordem e divisibilidade do que conjuntos numéricos Em matemática a comparação entre elementos de um ou mais conjuntos é chamada de relação entre os conjuntos No nosso dia a dia estamos frequentemente utilizando o conceito de relações como quando comparamos objetos maior menor igual Relações podem ser usadas para resolver problemas tais como determi nar quais pares de cidades são ligadas por linhas aéreas em uma rede Neste capítulo serão apresentadas as principais propriedades opera tórias entre relações com destaque para dois tipos muito especiais rela ção de ordem e relação de equivalência 41 Produto cartesiano e par ordenado Vídeo O principal objetivo deste capítulo é estudar relações entre elementos que per tencem a um ou mais conjuntos Para isso precisamos definir uma maneira espe cial de organizar elementos Definição Dados dois objetos quaisquer a e b chamamos de par ordenado um terceiro objeto a b Nesse caso dizemos que a e a primeira coordenada e b e a segunda coordenada de a b Observe alguns fatos importantes que decorrem da definição a A ordem dos elementos importa Ou seja o par ordenado a b é diferente do par ordenado b a b Não devemos confundir um par ordenado a b com um conjunto a b c Dois pares ordenados a b e c d são iguais se e somente se a c e b d São exemplos triviais de pares ordenados 1 4 4 1 100 0 carro motocicleta Maria José futebol vôlei Durante seus estudos no ensino médio você provavelmente aprendeu geometria analítica e conheceu uma forma de representar pontos ordenados em um plano chamado cartesiano Para construirmos um plano cartesiano basta que fixemos uma origem e dois eixos perpendiculares O plano cartesiano que conhecemos é então um conjunto de todos os pares ordenados de números reais Esse conjunto é chamado de produto cartesiano e pode ser generalizado para o produto de conjuntos quaisquer conforme a definição Definição Dados dois conjuntos A e B o conjunto de todos os pares ordenados a b com a A e b B é chamado de produto cartesiano de A e B e é denotado por A B Em linguagem de conjuntos A B a b a A e b B Vejamos um exemplo Exemplo 1 Sejam A A X e B 0 1 2 então A B A 0 A 1 A 2 X 0 X 1 X 2 B A 0 A 0 X 1 A 1 X 2 A 2 X Observamos no exemplo que em geral A B B A Além disso podemos provar que se nA e nB são finitos então nA B nB A nAnB A ideia de produto cartesiano de dois conjuntos pode ser estendida para o produto cartesiano de um número finito de conjuntos Definição Dados n conjuntos A₁ A₂ Aₙ O conjunto de todas as nuplas ordenadas a₁ a₂ aₙ com aᵢ Aᵢ é chamado de produto cartesiano de A₁ A₂ Aₙ e é denotado por A₁ A₂ Aₙ Em linguagem de conjuntos A₁ A₂ Aₙ a₁ a₂ aₙ aᵢ Aᵢ Observamos novamente que a ordem dos elementos de uma nupla importa ou seja a₁ aᵢ aₙ aᵢ a₁ aₙ se aᵢ a₁ Além disso se todos os conjuntos Aᵢ são finitos vale que nA₁ A₂ Aₙ nA₁ nA₂ nAₙ Exemplo 2 Sejam A A B 0 1 2 e C 0 1 então A x B x C A00A01A10A11A20A21 000110112021 E observamos que A 0 11 e A x B x C 0 A 11 e B x A x C A 11 0 e A x C x B A operação de produto cartesiano possui algumas propriedades operatórias Observe algumas no teorema a seguir Teorema Sejam A e B e C conjuntos então são válidas as seguintes propriedades a A x B A ou B b Se A e B então A x B B x A A B c Se A c B então A x C C x B e C x A C x B d Se A então A x B c A x C B c C Demonstração Vamos provar apenas o item d Note que se B então o resultado é trivial Vamos supor que B Seja b B um elemento qualquer Como A existe no mínimo um elemento em A Vamos considerar que esse elemento seja a então a A Assim se A x B c A x C temos a e A e b B a b A x B a b A x C a e A e b C Onde B c C Suponha agora que B c C Seja a b A x B então pela definição de produto cartesiano a e A e b C Como B c C temos que b C ou seja a b A x C Provando que A x B c A x C A operação de produto cartesiano também pode ser combinada com as demais operações entre conjuntos interseção união e diferença satisfazendo as seguintes propriedades distributivas Teorema Sejam A e B e C conjuntos então são válidas as seguintes propriedades distributivas a A x B n C A x B n A x C b A n B x C A x C n B x C c A x B C A x B A x C d A B x C A x C B x C e A B x C A x C B x C 64 Matemática Discreta Demonstração Vamos provar apenas os itens c e e Para o item c temos que a b A x BC a A e b BC a A e b B ou b C a A e b B ou a A e b C a b A x B ou a b A x C a b A x B U A x C Provando que A x BC A x BA x C Para o item e temos que a b A x BC a A e b BC a A e b B e b C a A e a A e b B e b C a A e b B e a A e b C a A e b B e a A e b C a b A x B e a b A x C a b A x BA x C Provando que A x BC A x BA x C O produto cartesiano A x A é chamado de quadrado cartesiano de A o qual é denotado por A2 ou seja A2 x y x y A Denotamos por Da o conjunto cha mado de diagonal de A2 o qual é formado pelos pares ordenados x x A2 ou seja Da x x x A Por exemplo considerando o conjunto A 1 2 temos A2 1 1 1 2 2 1 2 2 e Da 1 1 2 2 Observamos também que se A é um conjunto com cardinalidade finita digamos nA m então nA2 m2 e nDa m 42 Conceito de relação Vídeo Uma relação é uma ferramenta matemática que considera o vínculo de certo elemento de um conjunto com elementos de um ou mais conjuntos As relações são amplamente utilizadas na ciência da computação especialmente em bancos de dados e códigos corretores de erros No artigo Modelagem do problema de alocação de frota de uma empresa aérea brasileira dos auto res Daniel J Caetano e Nicolau D F Gualda publicado em 2008 no congresso anual da Associação Nacional de Pesquisa e Ensino em Transportes ANPET você pode conhecer mais a respeito de resolução de problemas com relações entre conjuntos Acesso em 5 mar 2021 httpswwwcaetanoengbrtrabalhosgetfilephpfn2008XXIIANPETAnaispdf Artigo Agora e com você prove os itens a b d e f Desafio Notemos as seguintes relações matemáticas Menor que 1 π o número real 1 está relacionado com o número π por essa relação Contido em 1 2 N o conjunto 1 2 está relacionado com o conjunto N por essa relação Observamos então que uma relação é uma regra para fazer uma afirmação sobre dois elementos que podem ou não pertencer ao mesmo conjunto Em outros termos para descrevermos uma relação de um conjunto A em B precisamos escolher ou definir uma regra de como escolher pares a b A x B Em termos de teoria de conjuntos podemos definir uma relação como segue Definição Dados dois conjuntos A e B uma relação binária R de A em B é um subconjunto do produto cartesiano A x B Se A B chamaremos a relação R de relação binária em A Vejamos um exemplo Exemplo 3 Dados A 4 5 6 e B a b c podemos definir relações de A e B escolhendo pares ordenados aleatoriamente em A x B por exemplo R1 4 a R2 4 a 6 c e R3 4 a 5 b 6 c6b Observe também que no exemplo anterior R1 c R2 e R1 c R3 porém R2 R3 Dado dois conjuntos A e B e uma relação R de A em B existem alguns subconjuntos especiais de R que são utilizados para descrever a relação Definição Seja R A x B uma relação de A em B o domínio de R denotado por DomR é o conjunto de todos os elementos em A que estão relacionados com algum elemento em B 43 Relação inversa Nesta seção aprenderemos a definir uma relação do conjunto B no conjunto A com base em uma relação de A em B Definição Dada uma relação binária R de A em B chamamos de relação inversa de R o conjunto R1 y x y B x y R Notamos que se R é uma relação binária de A em B então R1 é subconjunto de B x A ou seja R1 é uma relação binária de B em A Além disso temos que y x R1 x y R Segue sa definição que R1 é o conjunto dos pares ordenados obtidos a partir dos pares ordenados de R invertendose a ordem dos termos em cada par Vejamos um exemplo Exemplo 9 Dados A 0 1 2 3 e B 1 3 5 7 com relação R entre esses conjuntos dada por R x y A x B x 1 y determine os elementos de R e de R1 usando a notação de conjunto Pela definição de R temos que R 0 3 0 5 0 7 1 3 1 5 1 7 2 5 2 7 3 5 3 7 E pela definição de relação inversa temos R1 3 0 5 0 7 0 3 1 5 1 7 1 5 2 7 2 5 3 7 3 Teorema Sejam A e B conjuntos R uma relação de A em B e R1 sua relação inversa então são válidas as seguintes propriedades DomR1 ImR ImR1 DomR R11 R 44 Propriedades das relações Ao definirmos relações de A em B como subconjuntos do produto cartesiano A x B adquirimos a grande vantagem de colocar à nossa disposição todo o nosso conhecimento sobre teoria de conjuntos para descrever propriedades a respeito de relações Entretanto é comum encontrarmos na literatura a descrição de relação entre dois elementos por meio de um símbolo entre eles Por exemplo x y e x y expressam duas relações matemáticas a relação de soma e a relação de maior que Em geral para uma dada relação R de A em B escrevemos aRb a b R para representar que a está relacionado com b Ao considerarmos um conjunto A não vazio e uma relação R de A em A podemos explorar algumas propriedades importantes São elas o objeto de estudo desta seção Definição Dado um conjunto A não vazio uma relação binária R em A é reflexiva se para todo a A temos que a está relacionado com a Em símbolos R é reflexiva se a A aRa A relação de igualdade é reflexiva em qualquer conjunto numérico uma vez que escrever por exemplo 2 2 é equivalente a escrever 2 2 invertendo a ordem dos números dois Nem toda relação em um conjunto é reflexiva como podemos observar no seguinte exemplo Exemplo 11 Dado o conjunto A 1 2 3 considere a relação R1 em A dada por R1 11 22 12 21 Verifique que R1 não é reflexiva Claramente R1 não é reflexiva pois 3 A e 3 3 R1 Claramente R2 não é assimétrica pois a d A a d R2 e d a R2 Definição Sejam R A B duas relações de A em B então a relação interseção entre R e S é a relação R S de A em B dada por aR S aRb e aSb Definição Sejam R A B duas relações de A em B então a relação união entre R e S é a relação R S de A em B dada por aR S aRb ou aSb Definição De fato notamos que 1 α S R pois 1 x R e x α S Teorema Considerase relações R A B S B C e T C D então Observe que existe uma pequena diferença entre relação de ordem e relação de equivalência Toda relação de ordem é antissimétrica e toda relação de equivalência é simétrica Vejamos mais um exemplo de relação de equivalência Exemplo 25 Verifique que se a b Z a relação a b mod 2 é uma relação de equivalência em Z Para verificarmos que é relação de equivalência vamos mostrar que é uma relação reflexiva simétrica e transitiva De fato É reflexiva Para cada a Z temos a a 0 2 0 a a mod 2 É simétrica Se a b Z tais que a b mod 2 então existe k Z tal que a b 2k b a 2k b a mod 2 É transitiva Se a b c Z tais que a b mod 2 e b c mod 2 então existe k1 k2 Z tais que b a 2k1 e c b 2k2 Adicionando essas duas igualdades temos c b b a 2k1 2k2 c a 2k1 k2 c a 2k com k k1 k2 Z Portanto a c mod 2 Logo a relação a b mod 2 é de equivalência T S R T S R Veja um exemplo Exemplo 27 Considere o conjunto A a b c d e Vamos encontrar uma partição de A Existe mais de uma partição possível para A Podemos considerar por exemplo a partição formada pelos conjuntos A1 a c A2 b e A3 d Existe uma correspondência entre relações de equivalência em A e partições de A Podemos simplificar essa correspondência no seguinte teorema Teorema As classes de equivalência de uma relação de equivalência em um conjunto A formam uma partição de A Veja um exemplo do teorema Exemplo 28 Considere o conjunto dos números inteiros Z e a relação de congruência módulo 5 mod 5 Determine a quantidade e quais são as classes de equivalência dessa relação S R R1 S1 Veja um exemplo Exemplo 26 Seja A Z R x y mod 5 uma relação de A Determine a classe de equivalência 7 e a compare com as classes 12 e 17 Nesse caso temos que 7 é o conjunto de todos os elementos em Z que estão relacionados a 7 por R x y mod 5 assim 7 3 2 7 12 17 22 Ao comparar 7 com as classes 12 e 17 observamos que 7 12 17 Definição Uma partição de um conjunto A é uma coleção de subconjuntos disjuntos e não vazios A1 A2 An cuja união é A Demonstração Essa relação particiona o conjunto dos números inteiros em cinco classes de equivalência a saber 0 5 0 5 10 15 20 1 4 1 6 11 16 21 2 3 2 7 12 17 22 3 2 3 8 13 18 23 4 1 4 9 14 19 24 CONSIDERAÇÕES FINAIS Neste capítulo você aprendeu a realizar o produto cartesiano entre conjuntos e viu que essa operação pode ser utilizada para definir relações entre conjuntos que por sua vez podem ser empregadas para solucionar problemas práticos como na malha aérea de uma empresa Além disso estudamos que é possível realizar operações entre relações e como definir a relação inversa de uma dada relação E por fim nos debruçamos sobre dois tipos especiais de relações as de ordem que podem ser encontradas em aplicações de teoria da informação e as de equivalência aprendendo a relacionálas com partição de um conjunto 80 Matemática Discreta 5 Funções discretas O objetivo primordial de estudar matemática é aprender técnicas para conseguir descrever objetos da natureza por meio de ferramentas mate máticas a fim de solucionar problemas e desenvolver novas tecnologias A principal ferramenta é o conceito de função o qual nos ajuda a agrupar e descrever elementos por meio de uma regra Neste capítulo vamos apresentar as principais propriedades de fun ções Você aprenderá a definir uma função entre dois conjuntos A e B por meio de uma relação entre esses conjuntos e a classificála em inje tora sobrejetora e bijetora Além disso aprenderá a realizar uma opera ção muito importante entre funções a composição Iremos ainda utilizar funções para contar o número de elementos em um conjunto e por fim definiremos funções de maneira recursiva 51 Conceito e classificação Vídeo Funções como fx x2 x 1 e gx x tg1x são certamente bastante fami liares nas disciplinas de cálculo Em matemática discreta usaremos funções para contagem mas de uma forma que pode não ser familiar Em vez de utilizarmos fun ções que mapeiam um número real para outro usaremos funções que relacionam elementos de conjuntos finitos Para contar com precisão precisamos definir cuidadosamente a noção de função Definição Uma função f entre os conjuntos X e Y é uma regra que associa a cada elemento x X um único ele mento de Y denotado por fx Y É comum representarmos uma função de um conjunto X em um conjunto Y por f X Y x y fx Uma função f X Y também pode ser considerada uma relação entre dois con juntos X e Y que relaciona cada elemento de X a um elemento de Y O conjunto X é chamado de domínio da função f e Y é chamado de contradomínio Provaremos apenas o item a Funções discretas 81 Aqui está um exemplo ilustrativo de uma função Domínio Contradomínio a b c d e X f Y 1 2 3 4 5 Notamos que f X Y onde o conjunto X a b c d e é o domínio e o contra domínio é o conjunto Y 1 2 3 4 5 Os elementos relacionados são unidos por uma seta e indicam que f mapeia a para 1 b para 3 c para 4 d para 3 e para 5 De modo equivalente fa 1 fb 3 fc 4 fd 3 e fe 5 É importante lembrarmos que para uma relação de um conjunto X em um con junto Y definir uma função de X em Y é necessário que cada elemento de X esteja relacionado com um e apenas um elemento de Y Observe por exemplo as rela ções a seguir a b c d e X Y 1 2 3 4 5 a b c d e X Y 1 2 3 4 5 As relações apresentadas não são funções a primeira porque a está relaciona do com dois elementos do contradomínio 1 e 2 e a segunda porque b e d não estão relacionados com nenhum elemento do contradomínio Definição Sejam X e Y conjuntos A X e f X Y uma função a imagem direta de A é o conjunto fA fx Y x A Observe que dada uma função f X Y a imagem direta de um conjunto A X é formada pelos elementos y do contradomínio Y tais que existe um x A que está relacionado com y Além disso a imagem direta de A é um subconjunto do contradomínio Claramente T S R é também relações de A e D 82 Matemática Discreta Σxemρlo 1 Seja uma função f com domínio X a b c d e e contradomínio Y 1 2 3 4 5 onde fa 1 fb 3 fc 4 fd 3 e fe 5 Determine a imagem direta dos sub conjuntos A1 a b e A2 c d e Se A1 a b temos que fA1 1 3 Analogamente se A2 c d e temos que fA2 3 4 5 Teorema Sejam A B X e f X Y uma função a imagem direta é tal que a fAB fAfB b fAB fAfB Demonstração Vamos provar apenas o item a Se y fAB então existe x AB tal que fx y Se x A temos que y fA Se porém x B temos que y fB Em qual quer caso y fAfB Logo fAB fAfB Reciprocamente seja z fAfB então z fA ou z fB No primeiro caso existe x A tal que z fx No segundo existe y B tal que z fy De qualquer modo existe w AB tal que z fw Assim z fAB isto é fAfB fAB Essas duas inclusões mostram que fAB fAfB Definição Sejam X Y conjuntos B Y e f X Y uma função a imagem inversa de B é o conjunto f1B x X fx B X Observe que dada uma função f X Y a imagem inversa de um conjunto B Y é formada pelos elementos x do domínio X tais que existe um y B que está rela cionado com x Além disso a imagem inversa de B é um subconjunto do domínio Σxemρlo 2 Seja uma função f com domínio X a b c d e e contradomínio Y 7 8 9 10 11 onde fa 7 fb 8 fc 10 fd 9 e fe 11 Determine a imagem inversa dos conjuntos B1 7 8 e B2 7 9 10 11 Se B1 7 8 temos que f1B1 a b Analogamente se B2 7 9 10 11 temos que f1B2 a c d e Agora é com você prove o item b Desafio Seja a d A B um elemento qualquer se a d T S R pela definição de composição existe um elemento c C tal que a c S R e c d T Funções discretas 83 Teorema Sejam A B Y e f X Y uma função a imagem inversa é tal que a f1AB f1Af1B b f1AB f1Af1B Demonstração Vamos provar apenas o item b Temos que x f1AB fx AB fx A e fx B x f1A e x f1B x f1Af1B Portanto f1AB f1Af1B Definição Seja f X Y uma função dizemos que f é injetora se fx1 fx2 sempre que x1 x2 para x1 x2 X Note que dizer que uma função f X Y é injetora equivale a dizer que se fx1 fx2 então x1 x2 Vejamos um exemplo Σxemρlo 3 Sejam f ℕ ℕ dada por fx 2x e g ℤ ℕ dada por gx x2 verifique que f é injetora e que g não é injetora Suponhamos que existem x1 x2 ℕ tais que fx1 fx2 Vamos mostrar que x1 x2 De fato se fx1 fx2 então 2x1 2x2 onde x1 x2 e assim f é injetora É fácil ver que g não é injetora pela contrapositiva se x1 x2 então fx1 fx2 mas se x1 2 e x2 2 ℤ temos que g2 g2 4 Funções injetoras são especiais pois transformam fAB fAfB em uma igualdade Mais precisamente temos o seguinte teorema Teorema Seja A B X e f X Y uma função injetora então fAB fAfB Demonstração Dado y fAfB temos y fA e y fB Logo existem x1 A e x2 B com y fx1 e y fx2 Como f é injetora deve ser x1 x2 e portanto x1 AB Seguese que y fx1 pertence a fAB o que mostra fAfB fAB Como a inclusão oposta é sempre verdadeira concluímos que fAB fAfB Como a c S R podemos usar novamente a definição de composição e obter um elemento b B tal que a b R e b c S Agora sabemos que b c S e c d T e podemos concluir que b d T S Relacionamos funções e o conjunto n pelo seguinte teorema Teorema Considere os conjuntos n e m com n m Seja também f n m uma função então Se n m f não é sobrejetora Se n m f não é injetora Podemos utilizar o teorema anterior para demonstrar o seguinte resultado que relaciona conjuntos de cardinalidade finita e funções Teorema Sejam A e B conjuntos de cardinalidade finita Se existe uma bijeição f A B então A B Demonstração Sejam A n e B m podemos então corresponder cada elemento de ai A com i n e cada elemento bj B com o elemento j m Como f é injetora temos que n m e como f é sobrejetora temos que n m onde n m ou seja A B Um exemplo simples de aplicação do teorema é apresentado a seguir Da mesma forma a b R e b d T S seguese que a d T S R Sejam A e B conjuntos de cardinalidade finita Se existe uma bijeção f A B então A B 86 Matemática Discreta Observe que a função g f está bem definida pois fx Y e Y é o domínio de g Porém a composição pela outra ordem f g não está definida Além disso f g só estaria definida se gy X para todo y Y ou seja se gy X Σxemρlo 7 Sejam f ℕ ℝ a função definida por fx log x e g ℝ ℝ dada por gx x² 1 Determine g fx Note que g f ℕ ℝ é dada por g fx gfx log x² 1 Além disso observe que a função f g não está definida pois 125 Img ℝ e 125 Domf ℕ Veja mais um exemplo sobre composição de funções Σxemρlo 8 Sejam f ℕ ℕ a função definida por fx x 1 e g ℕ ℕ dada por gx x² x 1 Determine g fx e f gx Note que ambas g fx e f gx estão bem definidas Inicialmente vamos calcular g fx g fx gfx fx2 fx 1 x 12 x 1 1 x2 2x 1 x 2 x2 3x 3 Portanto g fx x2 3x 3 Agora f gx f gx fgx gx 1 x2 x 1 1 x2 x 2 Portanto f gx x2 x 2 No exemplo observamos que g fx f gx Esse fato nos diz que a com posição de funções não é em geral comutativa Por outro lado o teorema a seguir enuncia que a composição de funções é associativa Teorema Quaisquer que sejam f X Y g Y Z e h Z W temse que h g f h g f Isso prova que T S R T S R Funções discretas 87 Demonstração Considerando um elemento qualquer x de X e considerando fx y gy z e hz w temos h g fx h gfx h gy hgy hz w Notamos que g fx gfx gy z Portanto h g fx hg fx hz w Então para todo x de A h g fx h g fx Teorema Se duas funções f X Y e g Y Z são sobrejetoras então a função composta g f A C é sobrejetora Demonstração Sendo g sobrejetora então para todo z Z existe y Y tal que gy z e como a função f é sobrejetora isto é dado y Y existe x X tal que fx y Logo para todo z Z existe x X tal que z gy gfx g fx Provando que g f é sobrejetora O teorema anterior afirma que a composição de funções conserva a sobreti vidade ou seja informa que a composta de funções sobrejetoras é uma função sobrejetora O mesmo ocorre com funções injetoras como podemos observar no teorema a seguir Teorema Se duas funções f X Y e g Y Z são injetoras então a função composta g f A C é injetora Demonstração Consideremos x1 e x2 dois elementos quaisquer de X e suponhamos que g fx1 g fx2 isto é gfx1 gfx2 Como g é injetora da última igual dade resulta que fx1 fx2 como f é também injetora temos que x1 x2 Portanto g f é injetora A operação de composição de funções é utilizada para definir a função inversa de uma função Definição Seja f X Y uma função se existe g Y X tal que f gx x x Y e g fx x x A então uma função g é chamada de função inversa de f e é denotada por f1 46 Relação de ordem e de equivalência 88 Matemática Discreta Vejamos um exemplo Σxemρlo 9 Considere as funções f ℝ ℝ definida por fx x 2 e g ℝ ℝ dada por gx x 2 Calcule e mostre que g é a função inversa de f De fato notase que f gx fgx fx 2 x 2 2 x e g fx gfx gx 2 x 2 2 x Portanto g é a inversa de f ou seja g f1 Já sabemos que podemos considerar uma função f X Y como uma relação de X em Y isto é f x y X Y y fx x fx x X Desse modo você pode ser levado ao erro de relacionar função inversa com relação inversa Mas não faça isso Relação inversa e função inversa são dois conceitos totalmente diferentes Ade mais possuem algumas propriedades que as diferenciam por exemplo a relação inversa sempre existe o que não acontece com a função inversa A existência ou não da inversa de uma função está relacionada com sua sobre jetividade como estabelece o seguinte teorema Teorema Seja f X Y uma função a inversa f1 Y X existe se e somente se f for bijetora Podemos concluir com as funções do Exemplo 9 fx x 2 e gx x 2 que devido ao fato de g ser a inversa de f ou seja a inversa de f existir temos que fx x 2 é bijetora Analogamente por fx x 2 ser bijetora concluímos que f possui inversa g dada por gx x 2 Outra propriedade interessante da função inversa relaciona a inversa de uma função composta com a composta de suas inversas Teorema Sejam f X Y e g Y Z duas funções bijetoras então g f1 f1 g1 Nesta seção iremos estudar duas classes muito especiais de relações entre conjuntos as relações de ordem e de equivalência Funções discretas 89 Demonstração Se as funções f e g são bijetoras então a função composta g f de X em Z é bije tora logo existe a função inversa g f1 de X em Z Para provar que g f1 f1 g1 basta provar que f1 g1 g fx x e g f f1 g1x x De fato f1 g1 g fx f1 g1 g fx f1 g1 g fx f1 g1 g fx f1 fx x e g f f1 g1x g f f1 g1x g f f1 g1x g f f1 g1x g g1x x Provamos assim que f1 g1 é a inversa da função composta g f 53 Funções recursivas Vídeo Recursividade é um método utilizado para definir funções f ℕ0 Y onde Y é um conjunto numérico qualquer Esse método consiste em duas etapas a Definir um valor para a função f em zero b Fornecer uma regra para encontrar o valor de fx 1 a partir dos valores de f0 f1 fx Σxemρlo 10 Seja f ℕ0 ℕ a função definida recursivamente por f0 7 e fx 1 3fx 1 Determine os valores de f1 f2 e f3 Por definição temos que f1 f0 1 3f0 1 3 7 1 22 f2 f1 1 3f1 1 3 22 1 67 f3 f2 1 3f2 1 3 67 1 202 Essas duas classes de relações são as mais estudas em toda a matemática 90 Matemática Discreta Várias operações podem ser estudadas por meio de funções recursivas Lem bramos por exemplo que a operação fatorial de um número natural x é definida como x 1 2 3 x A operação fatorial pode ser definida por meio da seguinte função recursiva f ℕ0 ℕ dada por f0 1 fx 1 x 1fx Por exemplo temos que f1 f0 1 0 1f0 1 1 1 f2 f1 1 1 1f1 2 1 2 1 2 Para finalizar este capítulo apresentaremos uma função que é definida de ma neira recursiva e gera uma sequência de números conhecidos como números de Fibonacci Esses números foram introduzidos pelo matemático italiano Leonardo de Pisa 11701250 mais conhecido por Fibonacci e possuem várias aplicações em ciência da computação e teoria de jogos Além disso essa sequência de números está intrinsecamente ligada à natureza descrevendo perfeitamente por exemplo a reprodução das abelhas Σxemρlo 11 Os números de Fibonacci f0 f1 f2 são dados pela função f ℕ0 ℕ definida recursivamente por f0 0 f1 1 fx fx 1 fx 2 Calcule os valores de f2 f3 f4 e f5 Temos por definição que f2 f2 1 f2 2 f1 f0 1 0 1 f3 f3 1 f3 2 f2 f1 1 1 2 f4 f4 1 f4 2 f3 f2 2 1 3 f5 f5 1 f5 2 f4 f3 3 2 5 CONSIDERAÇÕES FINAIS Neste capítulo vimos que uma função entre dois conjuntos X e Y pode ser vis ta como uma relação e que toda função é classificada conforme sua injetividade sobrejetividade e bijetividade Além disso você aprendeu que dadas duas funções f X Y e g Y Z podemos produzir uma nova função g f X Z chamada de função composta Vimos a importância das funções para contar o número de ele mentos de um conjunto finito e como podemos utilizar funções recursivas para produzir uma sequência de números No filme O código da Vinci o simbologista Robert Langdon e a criptóloga Sophie Neveu encontram números na cena de um crime ocorrido no Museu do Louvre em Paris Os números pintados a sangue postos em ordem aleatória revelamse mais tarde um código a série de Fibonacci que os pro tagonistas usam para abrir um cofre e dar sequência à resolução do mistério Direção Ron Howard EUA Sony Pictures 2006 Filme Definição Funções discretas 91 ATIVIDADES 1 Sejam A B X e f X Y uma função mostre que a imagem direta de f é tal que fAB fAfB 2 Sejam A B Y e f X Y uma função mostre que imagem inversa de f é tal que f1AB f1Af1B 3 Mostre que a função f ℕ ℕ dada por fx 4x 7 é injetora 4 Mostre que a função f ℤ ℕ dada por fx 2x2 não é injetora 5 Mostre que a função f ℝ ℕ dada por fx 4x 7 é sobrejetora Se o domínio de f fosse o conjunto dos números naturais f ainda seria sobrejetora REFERÊNCIAS GERSTING J L Fundamentos Matemáticos para Ciência da Computação 4 ed São Paulo LTC 2001 GRIMALDI R P Discrete and combinatorial mathematics an applied introduction 5 ed Boston Addison Wesley 2004 ROSEN K H Matemática discreta e suas aplicações 6 ed São Paulo McGrawHill 2009 Dado um conjunto A não vazio uma relação binária R em A é dita relação de ordem parcial em A se for reflexiva antissimétrica e transitiva 92 Matemática Discreta 6 Análise combinatória A análise combinatória é a área da matemática que se dedica a desen volver técnicas de contagem preocupandose em como e não com o que vamos contar Muitos dos problemas de contagem tiveram sua origem ligada a jogos e loterias As principais publicações da análise combinatória foram feitas pelos matemáticos Blaise Pascal e Pierre de Fermat Neste capítulo vamos apresentar as principais técnicas de contagem como combinações arranjos e permutações e demonstrar como utilizálas em diferentes situações 61 Princípios de contagem Vídeo A análise combinatória é baseada em alguns princípios de contagem muito sim ples e intuitivos Você pode pensar que eles são tão fáceis que nem mesmo mere cem um nome Mas para levarmos a contagem a sério devemos estar cientes de fatos simples que usamos implicitamente o tempo todo Definição princípio da adição Dizemos que um conjunto finito A é particionado nas partes A1 Ak se as partes são disjuntas e sua união é A Em outras palavras temos AiAj para i j e A1A2Ak A Nesse caso A A1 A2 Ak O princípio da adição mostra que se existem A1 maneiras de tomar a decisão A1 A2 maneiras de tomar a decisão A2 Ak maneiras de tomar a decisão Ak então o número de maneiras de se tomar a decisão A1 ou a decisão A2 ou a de cisão Ak é A1 A2 Ak Vejamos um exemplo Σxemρlo 1 Seja A o conjunto de alunos que assistem à aula de combinatória Esse conjunto pode ser particionado nas partes A1 e A2 tais que A1 Alunos que gostam de exemplos fáceis A2 Alunos que não gostam de exemplos fáceis Vejamos um exemplo Análise combinatória 93 Se A1 22 e A2 8 de quantas maneiras distintas podemos escolher um aluno que assiste à aula de combinatória Como A A1A2 com A1A2 então podemos concluir pelo princípio da adi ção que existem A A1 A2 30 maneiras diferentes de escolher um aluno que assiste à aula de combinatória Acompanhe outro exemplo Σxemρlo 2 Você vai a um restaurante e ao observar o cardápio encontra 4 diferentes pra tos italianos e 3 diferentes pratos portugueses De quantas maneiras você pode escolher um único prato para fazer sua refeição Considere os seguintes conjuntos A Pratos do restaurante A1 Pratos italianos A2 Pratos portugueses Observamos que A A1A2 com A1A2 e A A1 A2 7 Logo existem sete maneiras diferentes de se escolher um prato para realizar uma refeição Definição princípio da subtração Seja A um subconjunto de um conjunto finito X definimos A XS como o complemento de A em X Então A X A Σxemρlo 3 Considere X o conjunto de alunos que estudam análise combinatória e A o con junto de alunos que não são do curso de Matemática nem do curso de Ciência da Computação Considerando que o total de alunos é 23905 se 20178 não fazem parte do curso de Matemática e nem do curso de Ciência da Computação quantos alunos estão cursando Matemática ou Ciência da Computação Sabemos que X 23905 e A 20178 Além disso Exemplo 21 94 Matemática Discreta A Alunos que cursam Matemática ou Ciência da Computação A X A 23905 20178 3727 Ou seja existem 3727 alunos que cursam Matemática ou Ciência da Computação A seguir apresentaremos dois outros princípios que são igualmente intuitivos e naturais e que ocorrerão com frequência na resolução de exercícios e nas demons trações de teoremas Definição princípio da multiplicação Se A é um conjunto finito definido pelo produto cartesiano de A1 Ak ou seja A A1 x A2 x x Ak então A A1 x A2 x x Ak O princípio da multiplicação mostra que se existem A1maneiras de tomar a decisão A1 A2 maneiras de tomar a decisão A2 Ak maneiras de tomar a de cisão Ak então o número de maneiras de se tomar sucessivamente as decisões A1 A2 Ak é A1 x A2 x x Ak Vejamos um exemplo Σxemρlo 4 Você vai a um restaurante e ao observar o cardápio encontra 4 opções de pra tos principais e 3 opções de sobremesa De quantas maneiras você pode fazer uma refeição formada por um prato principal e uma sobremesa Considere os seguintes conjuntos A Refeições com um prato principal e uma sobremesa A1 Pratos principais A2 Sobremesa Observamos que A A1 A2 e A A1 A2 12 Logo existem 12 maneiras diferentes de realizar uma refeição formada por um prato principal e uma sobremesa Acompanhe mais um exemplo do princípio da multiplicação Σxemρlo 5 Quantos números de três dígitos podemos formar com os algarismos 2 3 4 e 6 Verifique que a relação divide nos números naturais é uma relação de ordem parcial Para verificar que a relação divide é de ordem parcial analisamos suas propriedades Lembramos que n m é a função denominada de maior inteiro ou seja n m menor a ℕ tal que a nm Se por exemplo n 10 e m 3 então 10 3 3333 4 Já a função n m é denominada de menor inteiro ou seja n m maior a ℕ tal que a nm Temos por exemplo que se n 10 e m 3 então 10 3 3333 3 Vejamos um exemplo Exemplo 7 Suponha que haja 5 buracos na parede nos quais 17 pombos se aninham Utilizando o princípio da casa dos pombos o que podemos dizer sobre a distribuição dos pombos nesses buracos Pelo princípio da casa dos pombos temos que m 5 e n 17 Então podemos concluir que Existe algum buraco com pelo menos 17 5 4 pombos Existe algum buraco com no máximo 17 5 3 pombos Vejamos mais um exemplo Exemplo 8 Se as notas da disciplina de Matemática Discreta são graduadas por A B C e D quantos alunos devem ter na sala de aula para garantirmos que no mínimo 4 alunos tirem a mesma nota Vamos aplicar o princípio da casa dos pombos Note que temos 4 possibilidades de notas A B C e D Logo m 4 Queremos que alguma das notas seja atingida por no mínimo 3 alunos ou seja queremos que n 4 4 em que n é o número de alunos na turma Sendo assim devemos ter n 13 pois nesse caso 13 4 4 É reflexiva porque x x Note que se n 12 então 12 4 3 4 Portanto o número mínimo de alunos que a sala de aula deve ter para garantirmos que no mínimo 3 alunos tirem a mesma nota é 13 É antissimétrica porque x y e y x implica x y Definição princípio da contagem dupla Se contarmos a mesma quantidade de duas maneiras diferentes o processo pode fornecer uma identidade não trivial Vamos aplicar esse princípio no famoso lema do aperto de mão handshaking lemma Exemplo 9 Suponha que n pessoas estejam em uma festa e que todos irão apertar a mão um do outro Quantos apertos de mão irão ocorrer Vamos fazer a contagem do número de apertos de mão utilizando duas estratégias diferentes Primeira estratégia Cada pessoa aperta a mão total de n 1 mãos Contudo duas pessoas estão envolvidas em um aperto de mão então se apenas multiplicarmos nn 1 cada aperto de mão será contado duas vezes Logo devemos dividir por dois Portanto o número total de apertos de mão é nn 1 2 Segunda estratégia Numeramos as pessoas de 1 a n Para evitar a contagem de um aperto de mão duas vezes contamos para a pessoa i apenas os apertos de mão com pessoas de números menores Então o número total de apertos de mão é n Σ i1 i1 n1 Σ i0 n1 Σ i1 Ou seja utilizando as duas estratégias para contar o número de apertos de mão obtemos a seguinte identidade não trivial n1 Σ i0 i nn1 2 62 Arranjos Denotamos o conjunto dos n primeiros números naturais por n Ou seja n 1 2 n Definição princípio da contagem dupla Seja A um conjunto finito um arranjo ordenado de A é uma função s n A É transitiva porque x y e y z implica x z Os arranjos ordenados mais importantes são aqueles em que a função é injetiva ou seja si sj para i j Esse tipo de arranjo será chamado de permutação como definido a seguir Definição Seja A um conjunto finito uma permutação de A é uma função bijetiva π n A Quando A n denominamos o conjunto de todas as permutações de n por Sn Geralmente escrevemos permutações como sequências numéricas se n 10 Vejamos um exemplo Exemplo 11 Seja A 7 vamos descrever a permutação π 7 7 dada por π 2713546 Ao denominarmos π 2713546 estamos escrevendo que π é a função dada por i 1 2 3 4 5 6 7 πi 2 7 1 3 5 4 6 Ou seja π1 2 π2 7 π3 1 π4 3 π5 5 π6 4 e π7 6 Definição Para 0 k A uma kpermutação de A é um arranjo ordenado de k elementos distintos de A ou seja uma função injetiva π k A Se A n vamos denotar o conjunto de todas as kpermutacoes de A por Pn k Em particular temos Sn Pn n Portanto é uma relação de ordem parcial Arranjos ordenados são tão comuns que ocorrem em muitas situações e são conhecidos por nomes diferentes Aprendemos que BANANA é uma palavra e que 0815422372 é uma sequência de números embora ambos sejam arranjos ordenados de elementos BANANA é um arranjo ordenado dos elementos do conjunto A A B N e 0815422372 é um arranjo ordenado dos elementos do conjunto B 0 1 2 3 4 5 7 8 A seguir apresentamos as perspectivas mais comuns sobre o que é um arranjo ordenado e os nomes e notações que os acompanham Definição Seja s n A um arranjo ordenado do conjunto finito A temos que n é o domínio de s A imagem de s é s com i n e pode ser denotada pelo conjunto x A si x para algum i n Vejamos um exemplo Exemplo 10 Seja A A e o arranjo ordenado s 7 A À dada pela tabela a seguir i 1 2 3 4 5 6 7 si A Encontre o domínio de s a imagem de 3 e a imagem de s Por definição o domínio de s é 7 1 2 3 4 5 6 7 a imagem de 3 é e a imagem de s é si A Observe que o elemento A não está na imagem de s Definição Seja s n A um arranjo ordenado do conjunto finito A chamamos de s uma Astring ou apenas string de comprimento n e escrevemos s s1s2s3sn A iésima posição ou caractere em s é denotada por si si O conjunto A é chamado de alfabeto e seus elementos são chamados de letras Frequentemente uma string s é chamada de palavra No Exemplo 10 escrevemos que s A é uma string ou palavra de comprimento n sobre o alfabeto A de cinco letras O quarto caractere de s é s₄ A Podemos ver s n A como um elemento do produto cartesiano A₁ An em que Ai A para i n Chamamos s de tupla e a escrevemos como s s₁ s₂ sn O elemento si i n é chamado de iésima coordenada Ver os arranjos como elementos de produtos torna mais fácil restringir o número de valores permitidos para uma determinada coordenada basta escolher Ai A Outra relação de ordem parcial clássica que podemos citar é a relação menor ou igual nos números naturais Exemplo 12 Seja A 7 vamos descrever a 3permutação π 3 7 dada por π 312 Ao denominarmos π 312 estamos escrevendo que π é a função dada por i 1 2 3 πi 3 1 2 Ou seja π1 3 π2 1 e π3 2 Essa relação de equivalência divide Pn k em classes de equivalência e cada classe de equivalência é chamada de kpermutação circular O conjunto de todas as kpermutações circulares é denotado por Pcn k Acompanhe um exemplo de kpermutação circular Exemplo 13 Sejam π₁ 76123 π₂ 12376 e π₃ 32167 verifique que π₁ e π₂ são circulares equivalentes e que π₃ não é circular equivalente a π₁ e π₂ Observe o seguinte desenho representando cada permutação 1 6 2 3 7 1 π₁ π₂ π₃ Nesse desenho indica a seta circular de um número ao outro fechando a circunferência Observamos que conseguimos sair da permutação π₁ para a permutação π₂ realizando três giros da direita para a esquerda ou seja existem s 3 e 5 tal que se i 3 mod 5 π₁i π₂i Para conseguir chegar da permutação π₁ ou da permutação π₃ à permutação π₂ precisaríamos inverter os elementos 6 e 7 e isso não é permitido na definição de permutação circular equivalente em que π₃ não é equivalente a π₁ e π₂ No próximo teorema contaremos o número de kpermutacoes ciculares Para isso recordamos a notação e a definição de fatoriais n n n 1 n 2 n k 1 n n k Pcn k n k n k Porém note que a relação menor que não é uma ordem parcial porque não é reflexiva Para provar a uma kpermutação é uma função injetiva π k n Vamos contar as várias maneiras de escolher essa função escolhendo as imagens uma após a outra Existem n maneiras de escolher π1 Dado um valor para π1 existem n 1 maneiras de escolher π2 pois não podemos escolher π1 novamente Continuando desse modo existem n i 1 maneiras de escolher πi e o último valor que escolhemos é πk com n k 1 possibilidades Cada kpermutação pode ser construída exatamente de uma maneira O número total de kpermutacoes é portanto dado como o produto 𝑃n k n n 1 n k 1 𝑛n k Para provar b contamos duplamente Pn k A primeira estratégia é Pn k 𝑛n k que provamos em a A segunda estratégia é Pn k Pn k k pois cada classe de equivalência em Pn k contém k permutações de Pn k uma vez que existem k maneiras para gerar uma permutacao k Então utilizando o princípio da contagem dupla obtemos 𝑛n k Pcn k k Pcn k 𝑛kn k Observe que pelo teorema anterior temos que Pn n n ou seja o número total de permutações de n elementos é n Podemos utilizar permutações para resolver alguns problemas de contagem Vejamos um exemplo Exemplos 14 Quantos anagramas podemos formar com as letras da palavra LETO Queremos encontrar o número de maneiras diferentes que podemos ordenar utilizando as letras da palavra LETO ou seja estamos interessados em saber qual é o número total de permutações que podemos fazer com os elementos do conjunto A L E T O Como A 4 utilizando o fato de que o número total de permutações de n elementos é dado por Pn n n temos que P4 4 4 4 3 2 1 24 Portanto existem 24 anagramas diferentes com as letras da palavra LETO Acompanhe mais um exemplo de permutação Frequentemente uma relação de ordem parcial é denotada com o símbolo em vez de uma letra como R Queremos encontrar o número de maneiras diferentes em que podemos classificar os atletas em primeiro segundo terceiro quarto quinto e sexto colocado Considerando A 1 2 3 4 5 6 como o conjunto das possíveis classificações temos que A 6 portanto queremos encontrar P6 6 com n 6 Logo existem P6 6 6 6 5 4 3 2 1 720 possíveis resultados Observamos que em geral o número de permutações de n elementos sem nenhuma repetição de elementos é dado por Pn Pn n n Nem sempre os elementos que serão ordenados são distintos Nesse caso denotaremos por p o número de permutações de n elementos dos quais um é repetido 𝑎 vezes outro é repetido 𝑏 vezes outro é repetido 𝑐 vezes e assim por diante O número total dessa permutação é p n𝑎 𝑏 𝑐 Vejamos um exemplo Exemplos 16 Quantos anagramas diferentes podemos formar com as letras da palavra MATEMÁTICA desconsiderando o acento agudo Considerando o multiconjunto B A A A M T T E I C temos que B 10 e que A se repete 3 vezes M 2 vezes e T 2 vezes Portanto o número de anagramas diferentes que podemos fazer com as letras da palavra MATEMÁTICA é dado por p32210 10322 151200 Ou seja podemos formar 151200 anagramas com as letras da palavra MATEMÁTICA sem considerarmos o acento agudo Isso faz sentido uma vez que evoca o símbolo que é uma das ordens parciais mais comuns Existem algumas situações em combinação nas quais a escolha dos elementos para formar um determinado agrupamento não depende do ordem em que esses elementos são escolhidos ou dispostos Esse fato nos leva à definição a seguir Definição Seja A um conjunto finito e k ℕ um arranjo não ordenado de k elementos de A é um multiconjunto S de cardinalidade k com elementos distintos de A Podemos considerar por exemplo A Ana Pedro Maria Tiago descreva duas 3combinações de A e uma 1combinação de A Uma 3combinação de A é um subconjunto de cardinalidade três Então podemos tomar por exemplo as 3combinações S1 Ana Pedro Maria e S2 Pedro Maria Tiago Uma 1combinação de A é um subconjunto de cardinalidade um Podemos tomar por exemplo a 1combinação S3 Maria O conjunto de todos os ksubconjuntos de A é denotado por n k e se A n denominamos n k AA k Definição Teorema Para 0 k n temos Pn k n k k Demonstração Para construir um elemento de Pn k primeiro escolhemos k elementos de n Pela definição de n k existem exatamente n k maneiras de fazer isso Então escolhemos uma ordem para esses k elementos Existem Pk k k maneiras de fazer isso Cada elemento de Pn k pode ser construído assim de exatamente uma maneira em que Pn k n kk o que prova a afirmação Note que o teorema anterior nos diz que o número de kcombinações de um conjunto finito A com A n é dado por n k A k Pn k k n kn k Vejamos um exemplo Exemplo 18 Um grupo de 5 pessoas está organizando um evento científico sendo que 2 dessas 5 pessoas ficarão encarregadas de organizar a festa de encerramento De quantas maneiras diferentes podemos escolher essas duas pessoas Queremos contar o número total de 2combinações do conjunto A p₁ p₂ p₃ p₄ p₅ em que p representa a pessoa i do conjunto Como A 5 queremos encontrar C²₅ 5 25 2 5 23 20 2 10 Ou seja existem 10 maneiras possíveis de escolher duas pessoas para organizar a festa de encerramento Acompanhe outro exemplo de combinação Exemplo 19 Considere um sistema de comunicação composto de quatro antenas Quantas possibilidades existem de exatamente três antenas estarem com defeito Queremos contar o número total de 3combinações do conjunto A A₁ A₂ A₃ A₄ em que A representa a antena i do conjunto Como A 4 queremos encontrar C³₄ 4 34 3 4 31 4 Portanto existem 4 maneiras possíveis de exatamente três antenas estarem com defeito Vejamos mais um exemplo Exemplo 20 Em um campeonato de futebol cada um dos 16 times joga uma única vez contra todos os demais Quantas partidas serão realizadas Como cada partida é formada por dois times queremos contar o número total de 2combinações do conjunto A T₁ T₂ T₁₆ em que Tₙ representa o time i Como A 16 queremos encontrar C²₁₆ 16 216 2 16 214 16 15 14 214 16 15 2 8 15 120 Ou seja ocorrerão 120 partidas no campeonato A seguir observe outro exemplo no qual usamos a combinatória Exemplo 21 De 5 mulheres e 7 homens quantos comitês diferentes de 2 mulheres e 3 homens podem ser formados Vamos considerar A M₁ M₂ M₃ M₄ M₅ em que M₁ denota a mulher i e B H₁ H₂ H₃ H₄ H₅ H₆ H₇ sendo que H₁ denota o homem j Em cada comitê teremos um conjunto de 2 mulheres Como A 5 precisamos calcular C²₅ 5 25 2 5 23 10 Analagmente em cada comitê teremos um conjunto de 3 homens Como B 7 precisamos calcular C³₇ 7 37 3 7 34 35 Dado um conjunto A e uma ordem parcial no conjunto A o par P A é chamado de conjunto parcialmente ordenado ou poset Como cada comitê é formado por 2 mulheres e 3 homens precisamos utilizar o princípio multiplicativo para obter o número total de comitês diferentes que podem formar Ou seja o número total T será T C²₅ C³₇ 10 35 350 Portanto podemos formar 350 comitês diferentes 65 Binômio de Newton Os números n k para 0 k n são chamados também de coeficientes binomiais pois são os coeficientes encontrados ao se expandir a enésima potência de uma soma de duas variáveis x yⁿ Coeficientes binomiais são utilizados no método conhecido como binômio de Newton Para demonstrar o binômio de Newton utilizaremos o teorema a seguir Teorema Sejam m n ℕ então m k 1 m k m 1 k Vejamos um exemplo Exemplo 22 Verifique que 4 2 4 3 5 3 Temos que 4 2 4 24 2 12 2 6 4 3 4 34 3 4 1 4 5 3 5 35 3 20 2 10 Portanto O binômio de Newton é descrito e demonstrado a seguir Teorema Sejam x y variáveis e n ℕ então x yⁿ ₖ₀ⁿ n k xⁿᵏ yᵏ A representação gráfica dos posets quando A é finito é dada pelo Diagrama de Hasse Dado um poset finito A os elementos de A são representados por vértices e as relações dos elementos por arestas convencionando que um elemento a é está abaixo de b e A se e somente se a b Vamos demonstrar por indução que o binômio de Newton é válido para qualquer n 1 Para n 1 temos x y1 x y e k01 1 k xnkyk 1 0x1y0 1 1x0y1 x y Ou seja x y1 k01 1 kxnkyk Logo o binômio de Newton é válido para n 1 Agora suponha que o resultado é verdadeiro para n m ou seja vale x ym k0m m kxmkyk Vamos demonstrar que o resultado é válido para n m 1 De fato x ym1 x yx ym x y k0m m kxmkyk xsumk0m m kxmkyk yk0m m kxmkyk k0m m kxm1kyk k0m m kxmkyk1 A primeira soma pode ser escrita como k0m m kxm1k xm1kyk A segunda soma pode ser escrita como k0m m kxm1kyk1 ym1k0m1 m kxmk Então temos x ym1 xm1 ym1 k1m m kxm1k yk k0m1 m1 kxm1kyk Assim fica provado que o teorema é válido para todo n ℕ A fórmula binomial pode ser generalizada para mais de duas variáveis Vejamos um exemplo Definição Para inteiros não negativos k1 kr com k1 kr n os coeficientes multinomiais binomnk1 kr são os coeficientes encontrados ao se expandir na nésima potência de uma soma de r variáveis Em outras palavras definimos os coeficientes multinomiais binomnk1 kr como os únicos números que satisfazem a seguinte identidade x1 xrn k1 kr n binomnk1 kr k1k2krkr Vejamos um exemplo Exemplo 23 Utilize o polinômio x1 x2 x34 para encontrar binom4211 cdot binom4202 cdot binom4004 Temos que x1 x2 x34 1x14 x24 x34 4x22x3 x32x2 x23 x1x3x23 x13x2 x2x32 6x12x22 x32x22 12x12x2x3 x2x32 x1x22x32 Exemplo 22 Considere P A o poset definido sobre o conjunto A 1 2 3 4 e com ordem parcial Assim a primeira identidade é provada Agora left beginarrayc n k1 endarray right left beginarrayc nk1 k2 endarray right cdots left beginarrayc nk1k2cdotskr1 kr endarray right fracnk1nk1k2nk1k2 cdots krnk1k2cdotskr Análise combinatória 111 3 Ao pendurar 9 bandeiras em uma linha das quais 4 são brancas 3 são vermelhas e 2 são azuis quantas formas diferentes são possíveis 4 Se em um grupo de 12 pessoas 3 delas são escolhidas para ganhar uma viajem de quantas maneiras diferentes pode ocorrer a escolha REFERÊNCIAS GERSTING J L Fundamentos matemáticos para ciência da computação 4 ed São Paulo LTC 2001 GRIMALDI R P Discrete and combinatorial mathematics an applied introduction 5 ed Boston AddisonWesley 2004 HAZZAN S Fundamentos da matemática elementar combinatória probabilidade São Paulo Atual 2013 v 5 ROSEN K H Matemática discreta e suas aplicações 6 ed São Paulo McGrawHill 2009 SANTOS J P O MELLO M P MURARI I T C Introdução à análise combinatória Rio de Janeiro Ciência Moderna 2008 1 1 2 2 3 3 4 4 1 3 2 3 2 4 Descreva o Diagrama de Hasse de P Funcões geradoras são uma das invenções mais surpreendentes úteis e inteligentes da matemática discreta De modo geral funções geradoras transformam problemas sobre sequências numéricas em problemas de funções de valor real Isso é ótimo porque já conhecemos várias propriedades e técnicas matemáticas para manipular funções de valor real O Diagrama de Hasse de P A é Você irá aprender a calcular a função geradora ordinária e a função geradora exponencial de uma sequência numérica a realizar operações com funções geradoras e utilizálas para resolver problemas de contagem Por fim aprenderá o conceito e como representar a partição de um número inteiro positivo Lembrese de que a soma de uma série geométrica infinita para z 1 é frac11z Note que frac101x 10 cdot frac11x onde Fx frac11x é a função geradora associada à sequência numérica infinita 1 1 1 1 Qual é função geradora ordinária da sequência numérica 0 0 0 10 10 10 10 Encontre uma função geradora fechada para a sequência de quadrados perfeitos 0 1 4 9 16 Encontre os valores binomiais estendidos de 3 atop 2 e left frac12 atop 3 right Quantas são as soluções inteiras de x1 x2 x3 7 sabendo que y1 y2 in 1 2 3 e x3 in 3 4 Acompanhe mais um exemplo Exemplo 12 De quantas maneiras podemos escolher 10 calças de 4 marcas diferentes A função geradora que determina o número de calças de uma marca é 1 x x² x¹⁰ Como são quatro marcas diferentes a solução será o coeficiente de x¹⁰ em 1 x x² x¹⁰⁴ Sabemos que 1 x x² x¹⁰ 1 x¹¹ 1 x Logo 1xx²x¹⁰⁴ 1x¹¹1x⁴ 1x¹¹⁴1x⁴ Como 1 x⁴ 1 4x¹¹ 6x²² 4x³³ x⁴⁴ temos que o coeficiente de x¹⁰ em 1 x x² x¹⁰ é o coeficiente de x¹⁰ em 1 x⁴ Como 1 x⁴ ₖ₀ 1ᵏ4 k 1 k xᵏ o coeficiente de x¹⁰ é 1¹⁰4 10 1 10 286 Portanto existem 286 modos de se escolher 10 calças de 4 marcas diferentes 73 Funções geradoras exponenciais Na seção anterior vimos alguns exemplos de como utilizar a função geradora ordinária para resolver problemas de contagem cuja ordem em que os objetos aparecem é irrelevante Agora vamos estudar as funções geradoras exponenciais utilizadas para solucionar problemas de contagem em que a ordem dos objetos retirados é importante Definição A função geradora exponencial FGE para a sequência numérica interna g₀ g₁ g₂ é a série de potência formal Gx g₀ g₁x g₂x²1 g₃x³2 ₐ₀ gₐxᵏi Não é difícil perceber que quanto mais restrições possui um problema de contagem mais difícil é para encontrar sua solução Vimos que uma ferramenta da análise combinatória que facilita a resolução desses problemas é a função geradora ordinária Essa ferramenta é importante para resolver problemas que podem ser traduzidos em equação do tipo x₁ x₂ xₖ r de números inteiros não negativos Consideremos agora o seguinte problema de quantas maneiras diferentes podemos colocar quatro bolas idênticas em duas caixas idênticas de modo que nenhuma caixa fique vazia Podemos resolver esse problema de um modo mais simples sem precisar recorrer a uma equação do tipo x₁ x₂ xₖ r Note que o número 4 pode ser escrito como 4 3 1 2 2 2 1 1 1 1 1 1 As diferentes maneiras de escrever o número 4 são chamadas de partições do número 4 Considerando cada parcela como uma caixa temos que existem apenas duas opções diferentes de colocar quatro bolas idênticas em duas caixas idênticas A saber 3 1 e 2 2 Esse método a princípio é bem simples Mas ao considerarmos números maiores notamos que o número de partições aumenta de maneira considerável Por exemplo o número 200 possui 3972999029388 partições Vamos estudar em mais detalhes as partições de um número Observamos que uma partição de um número inteiro define uma sequência numérica A partição p 3 2 2 1 do número n 8 por exemplo define a sequência numérica 3 2 2 1 Vamos então relacionar partições de um inteiro e a função geradora de uma sequência numérica Teorema Seja n um número inteiro positivo e pn o número de partições de n a função geradora para pn é pxn 11 xk Onde p0 1 Demonstração Sabemos que 11 x 1 x x² x³ 11 x² 1 x² x⁴ x⁶ 11 xm 1 xm x²m x³m Portanto 11 xk 1 x x² x³ 1 x² x⁴ x⁶ Assim notamos que os coeficientes do termo xⁿ derivam de um termo x¹ da primeira série de x²b da segunda e assim por diante com b₁ 0 para todo i Pela regra da potenciação temos que b₁ 2b₂ 3b₃ mbₘ m Cada bₑ deve ser visto como o número de is que aparecem na partição de n ou seja podemos escrever n como N 1 1 1 2 2 2 m m m onde temos b₁s no primeiro parêntese b₂s no segundo e bₘs no mésimo parêntese Assim cada partição de um n contribui em uma unidade para o coeficiente de xⁿ Portanto 11 x 1 x x¹ x¹¹ 1 x² x²² x²²² 126 Matemática Discreta 76 Gráfico de uma partição Vídeo Seja n um número inteiro positivo o gráfico de uma partição de n é representado por meio de um conjunto de n pontos no plano onde em cada linha inserimos em or dem decrescente o número de pontos correspondentes a cada uma de suas partes Σxemρlo 15 Construa o gráfico para a partição 3 2 1 1 do número 7 Por definição temos que a primeira linha do gráfico possui três pontos a se gunda linha possui dois pontos e as duas últimas linhas possuem um ponto cada Portanto o gráfico da partição 3 2 1 1 é dado por Note que ao invertemos as linhas e as colunas do gráfico de uma partição de um número inteiro n obtemos o gráfico de outra partição de n Isso nos leva à seguinte definição Definição 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 obtida pela inversão das linhas e colunas do gráfico de p Vejamos um exemplo Σxemρlo 16 Determine a partição conjugada da partição p 4 2 1 do número 7 Temos por definição que o gráfico da partição 4 2 1 é dado por Se invertirmos as linhas e colunas vamos obter o seguinte gráfico que corresponde à partição 3 2 1 1 ou seja p 3 2 1 1 Definição Dado um número inteiro positivo n e uma partição p de n a partição conjugada de p é chamada de autoconjugada se p p Se considerarmos por exemplo a partição p 3 2 1 de n 6 temos que p p 128 Matemática Discreta REFERÊNCIAS GERSTING J L Fundamentos Matemáticos para Ciência da Computação 4 ed São Paulo LTC 2001 GRIMALDI R P Discrete and combinatorial mathematics an applied introduction 5 ed Boston Addison Wesley 2004 ROSEN K H Matemática discreta e suas aplicações 6 ed São Paulo McGrawHill 2009 Gabarito 129 GABARITO 1 Fundamentos de lógica matemática e métodos de demonstração 1 a Teorema Se a é um número inteiro par e b é um número inteiro ímpar então a soma a b é um número inteiro ímpar Demonstração Seja a um número inteiro par e b um número inteiro ímpar pela definição de número inteiro par sabemos que a 2k e pela definição de número inteiro ímpar b 2t 1 Logo a soma a b é a b 2k 2t 1 2k t 1 2t1 1 ou seja a b 2t1 1 onde t1 k t Isso mostra que a b tem a forma de um número inteiro ímpar Podemos assim concluir que a b é um número inteiro ímpar b Teorema Se a é um número inteiro par e b um número inteiro ímpar então o produto ab é um número par Demonstração Seja a um número inteiro par e b um número inteiro ímpar pela definição de número inteiro par sabemos que a 2k e pela definição de número inteiro ímpar b 2t 1 Logo o produto ab é ab 2k2t 1 2k2t 2k 22kt k ou seja ab 2k1 onde k1 2kt k Isso mostra que ab tem a forma de um número inteiro par Podemos assim concluir que ab é um número inteiro par 2 Teorema Se a é um número natural e a² é ímpar então a é um número ímpar Demonstração Nossa proposição é p a² é ímpar q a é ímpar Vamos demonstrar que a proposição equivalente q a é par p a² é par é verdadeira Com efeito se a é par existe k natural tal que a 2k Logo a² 2k² 4k² 22k² 2k2 onde k2 2k² ou seja a² é um número par provando que a contrapositiva do teorema é verdadeira Podemos então concluir que o teorema é verdadeiro 3 Teorema Se a é um número inteiro par e b é um número inteiro ímpar então a soma a b é um número inteiro ímpar Nossa hipótese é p a é um número inteiro par e b é um número inteiro ímpar e nossa tese é q a b é um número inteiro ímpar Vamos então negar isso isto é q a b é um número par Suponha então que a 2k b 2t 1 e a b é um número par Digamos que a b 2k onde por um lado a b 2k 2t 1 e por outro lado a b 2k Daí k 2t 1 2k t k 1 Isso nos diz que 1 é um número ímpar obviamente uma contradição de onde devemos ter que a b é um número ímpar Teorema Se n é um número natural 12 32 52 2n 12 nn 12n 1 3 x A Bc x A B x A ou x B x A x B x Ac e x Bc x Ac Bc Provando que A Bc Ac Bc x A B x A e x B x Ac e x Bc x Bc e x Ac x A Bc Provando que A B B Ac Seja y e fAnB existe x e A e B tal que fxy Então x e A e portanto y e fA Também x e B e portanto y e fB Logo y e fAnB Provando que fAnB fAfB 1 1 1 1 1xx²x³ 11x Logo o coeficiente de x³ é frac12leftfrac12cdotfrac12cdot33right frac116 3 Sabemos que frac11x 1 x x² x³ Substituindo x por 2x nos dois lados da igualdade temos que frac112x 2x 4x² 8x³ 16x⁴ Multiplicando os dois lados por 2x² temse 2x² 2x² 4x³ 8x⁴ 16x⁵ 32x⁶ Logo fx é a função geradora da sequência 0 0 2 4 8 16 32 WELINGTON SANTOS MATEMÁTICA DISCRE TA Código Logístico 59915 Fundação Biblioteca Nacional ISBN 9786558210122 9 7 8 6 5 5 8 2 1 0 1 2 2