Conexões entre Conjuntos e Álgebra Booleana

Coleções 85 A conexão entre operações com conjuntos e a álgebra booleana 1121 Prove que a diferença simétrica é uma operação comutativa ou seja para conjuntos A e B verificase A A B B A A 1122 Prove que a diferença simétrica é uma operação associativa isto é para quaisquer conjuntos A B e C temos A A B A C A A B A C 1123 Ilustre A A B A C A A B A C com um diagrama de Venn 1124 Prove a Proposição 1115 1125 Sejam os conjuntos A B e C Prove a A x BJ C A x Bl A x C b A x 5 n C A x B n A x Q c A x B Q A x B A x Q d A x B A Q A x B A A x Q 12 Prova combinatória dois exemplos Na Seção 11 apresentamos o conceito de prova combinatória de equações Essa técnica funciona mostrando que os lados de uma equação são respostas para uma pergunta comum Esse método foi utilizado para provar a Proposição 114 para os conjuntos finitos A e B temos vá 5 U5 n5 Consulte o Esquema de prova 9 Nesta seção fornecemos dois exemplos que ilustram ainda mais essa técnica Um deles baseiase no problema de contagem de conjuntos e o outro no problema de contagem de listas Proposição 121 Seja n um inteiro positivo Então 2o 21 2 2 1 Por exemplo 2o 21 22 23 24 1 2 4 8 16 31 25 l Buscamos uma pergunta para a qual ambos os lados da equação forneçam uma resposta correta O lado direito é mais simples portanto vamos começar daí O termo 2 responde à pergunta Quantos subconjuntos um conjunto de n elementos tem Entretanto o termo é 2 1 e não 2 Podemos modificar a pergunta para excluir todos exceto um dos subconjuntos Qual subconjunto deveria ser ignorado Uma escolha natural é omitir o conjunto vazio A per gunta reformulada é Quantos subconjuntos não vazios um conjunto de n elementos tem Agora é evidente que o lado direito da equação 2 1 é a resposta correta Mas e quanto ao lado esquerdo O lado esquerdo é uma soma longa com cada termo da forma 2J Isso é uma pista de que estamos considerando vários problemas de contagem de subconjuntos De algum modo a pergunta sobre quantos subconjuntos não vazios um conjunto de n elementos tem deve ser 86 Matemática Discreta dividida em casos desconexos cada problema de contagem de subconjuntos para si próprio e em seguida combinada para fornecer a resposta completa Sabemos que estamos contando conjuntos não vazios de um conjunto de n elementos Para fins de especificidade suponha que o conjunto seja 12 n Comecemos escreven do os subconjuntos não vazios deste conjunto É natural iniciar com 1 Em seguida escre vemos 12 e 2 estes são os conjuntos cujo maior elemento é 2 Após isso escrevemos os conjuntos cujo maior elemento seja 3 Vamos organizar isso em um quadro Maior elemento Subconjuntos de 12 ri 1 0 2 2 1 2 3 3 1 323 1 2 3 4 4 1424 124 1234 n n 1 ri 2 nl2 12 3 Deixamos de escrever todos os subconjuntos na linha 4 do quadro Quantos há Os conjuntos nesta linha devem conter 4 desde que este seja o maior elemento Os outros elementos desses conjuntos são escolhidos entre 1 2 e 3 Como há 23 8 formas possíveis de constituir um subconjunto de 1 2 3 deve haver 8 conjuntos nessa linha Reserve um momento para averiguar isso sozinho completando a linha 4 do quadro Agora vá para a última linha do quadro Quantos subconjuntos de 12n têm o maior elemento n Devemos incluir n juntamente com qualquer subconjunto de 1 2 1 para um total de 2 escolhas Observe que cada conjunto não vazio de 12 ri deve aparecer exatamente uma vez no quadro A totalização das dimensões da linha fornece 12 4 8 2 Aha Este é precisamente o lado esquerdo da equação que buscamos provar Valendose dessas percepções estamos prontos para escrever a prova Prova da Proposição 121 Seja n um inteiro positivo e seja N 12 n Quantos subconjuntos não vazios N tem Resposta 1 Como N tem 2 subconjuntos ao desconsiderarmos o conjunto vazio constatamos que N tem 21 subconjuntos não vazios Resposta 2 Consideramos o número de subconjuntos de N cujo maior elemento seja j em que 1 jn Esses subconjuntos devem ser da forma em que os outros elementos são escolhidos a partir de 1 j 1 Como esse último conjunto tem 2H subconjuntos N tem 2H subconjuntos cujo maior elemento é j A soma dessas respostas sobre todos os j fornece 2o 2 22 21 subconjuntos não vazios de N Coleções 87 Como as respostas 1 e 2 são soluções corretas para o mesmo problema de contagem temos 2o 2 1 22 2 2 Agora vamos para um segundo exemplo Proposição 122 Seja n um inteiro positivo Então 1 1 2 2 Por exemplo com n 4 observe que 1 1 2 2 3 3 4 4 1 1 2 2 3 6 424 1 418 96 1191201 511 O segredo para provar a Proposição 122 é encontrar a pergunta para a qual ambos os lados da equação forneçam a resposta correta Assim como no primeiro exemplo o lado direito é mais simples portanto começaremos aí O termo 11 nos lembra das listas de contagem sem substituição Especificamente ele responde à pergunta Quantas listas podemos formar utilizando os elementos de 12 n 1 em que cada elemento é utilizado exatamente uma vez Como o lado direito também inclui um termo 1 precisamos descartar uma dessas listas Qual Uma escolha natural é omitir a lista 1 2 3 n 1 esta é a única lista em que cada elemento j não está nayésima posição na lista Por outro lado a lista descartada é a única em que os elementos aparecem em ordem crescente Portanto consideramos a pergunta Quantas listas podemos formar utilizando os elemen tos de 1 2 n 1 em que cada elemento aparece exatamente uma vez e em que os ele mentos não aparecem em ordem crescente Evidentemente n 1 1 é uma solução para este problema precisamos demonstrar que o lado esquerdo também é uma resposta correta Se os elementos na lista não estão em ordem crescente então algum elemento digamos k não estará na posição k Podemos organizar este problema de contagem considerando onde ele acontece pela primeira vez Consideremos o caso n 4 Podemos formar um quadro contendo todas as listas sem repetição de comprimento 5 que pudermos formar a partir dos elementos de 1234 5 que não estejam em ordem crescente Organizamos o quadro considerando a primeira vez que a posição A não é o elemento k Por exemplo quando k 3 as listas são 1243512453 12534 e 12543 desde que os valores nas posições 1 e 2 sejam os elementos 1 e 2 respectivamente mas o valor 3 não seja 3 Omitimos as vírgulas e parênteses para fins de clareza Ver o quadro para n 4 a seguir 88 Matemática Discreta k primeiro elemento fora do lugar na posição k 1 21345 21354 21435 21453 21534 21534 23145 23154 23415 23514 23514 23541 24135 24153 24315 24351 24513 24531 25134 25143 25314 25341 25413 25431 31245 31254 31425 31452 31524 31542 32145 32154 32415 32451 32514 32541 34125 34152 34215 34251 34512 34521 35124 35142 35214 35241 35412 35421 41235 41253 41325 41352 41523 41532 42135 42153 42315 42351 42513 42531 43125 43152 43215 43251 43512 43521 45123 45132 45213 45231 45312 45321 51234 51243 51324 51342 51423 51432 52134 52143 52314 52341 52413 52431 53124 53142 53214 53241 53412 53421 54123 54132 54213 54231 54312 54321 2 13245 13254 13425 13452 13524 13542 14235 14253 14325 14352 14523 14532 15234 15243 15324 15342 15423 15432 3 12435 12453 12534 12543 4 12354 5 Observe que a linha 5 do quadro está vazia Por quê Essa linha deveria conter todas as listas sem repetições em que a primeira posição k que não contenha o elemento k seja k 5 Essa lista deve ser da forma 1 2 3 4 mas nesse caso não há uma maneira válida de preencher a última posição Em seguida conte o número de listas em cada posição do quadro Trabalhando a partir da parte inferior há 1 4 18 96 119 listas todas 5 120 com exceção da lista 1 23 4 5 A soma de 1 4 18 96 deve ser familiar é precisamente 1 1 2 2 3 3 441 Obviamente isso não é nenhuma coincidência Considere a primeira linha do quadro As listas nessa linha não devem iniciar com 1 mas podem iniciar com qualquer elemento de 2 34 5 há quatro escolhas para o primeiro elemento Assim que o primeiro elemento for escolhido os quatro elementos restantes na lista podem ser escolhidos de qualquer maneira que nos for conveniente Desde que haja 4 elementos restantes após a seleção do primeiro esses 4 elementos podem ser dispostos de 4 maneiras Com isso por meio do Princípio da Multiplicação há 4 4 Listas em que o primeiro elemento não é 1 A mesma análise se aplica à segunda linha As listas nesta linha devem começar com 1 desse modo o segundo elemento não pode ser 2 Há 3 opções para o segundo elemento porque devemos escolhêlo de 34 5 Uma vez que o segundo elemento é selecionado os três elementos restantes podem ser dispostos de qualquer maneira que desejarmos e há 3 maneiras de fazer isso Com isso a segunda linha do quadro contém 331 18 listas Estamos prontos para completar a prova Prova da Proposição 122 Seja n um inteiro positivo Perguntamonos Quantas listas sem repetição podemos formar utilizando todos os elementos em 1 2 n 1 em que os elementos não apareçam na ordem crescente Coleções 89 Resposta 1 Há n 1 listas sem repetição e apenas em uma dessas listas os elementos aparecem em ordem a saber 1 2 n n 1 Desse modo a resposta para a pergunta é n 1 1 Resposta 2 Seja j um inteiro entre 1 e n de forma inclusiva Consideremos aquelas listas em que os primeiros elementos j 1 são 1 2 j 1 respectivamente mas para as quais o yésimo elemento não é y Quantas listas desse tipo existem Para o elemento j há n 1 y escolhas porque os elementos de 1 ay 1 já foram escolhidos e não podemos utilizar o elemento j Os elementos n 1 y restantes podem preencher as posições restantes na lista em qualquer ordem fornecendo 1 y possibilidades Pelo Princípio da Multiplicação há 1 y 1 y listas desse tipo Somandoy 12 n fornece w n w 1 1 3 3 2 2 1 1 Como as respostas 1 e 2 são soluções corretas para o mesmo problema de contagem temos 1 1 2 2 Recapitulando Nesta seção ilustramos o conceito de prova combinatória por meio da aplicação da técnica para demonstração das duas identidades 12 Exercícios 121 Forneça uma prova alternativa da Proposição 121 em que utilize a contagem de lista em vez da contagem de subconjuntos 122 Seja n um inteiro positivo Utilize a álgebra para simplificar a seguinte expressão x 11 x x2 11 Utilize isso para fornecer outra prova da Proposição 121 123 A substituição de x 3 em sua expressão no problema anterior resulta em 2 3o 2 31 2 32 2 31 3 1 Prove essa equação combinatoriamente Em seguida substitua x 10 e ilustre o resultado utilizando números de base 10 comuns 124 Sejam a e b inteiros positivos com a b Forneça uma prova combinatória da identidade a 6a b á2 b 2 125 Seja n um inteiro positivo Forneça a prova combinatória de que n2 nn 1 n i 90 Matemática Discreta Autoteste 1 O indicativo de chamada para uma estação de rádio nos Estados Unidos é uma lista de três ou quatro letras como WJHU ou WJZ A primeira letra deve ser W ou K e não há restrições quanto às outras letras De quantas maneiras o indicativo de chamada de uma estação de rádio pode ser formado 2 De quantas maneiras podemos fazer uma lista de três números inteiros a b c em que 0a b c9 e a b c é par 3 De quantas maneiras podemos fazer uma lista de três números inteiros a b c em que 0 a b c 9 e abc é par 4 Sem o uso de qualquer auxílio computacional simplifique a seguinte expressão 20 173 5 De quantas maneiras podemos organizar um conjuntopadrão de 52 cartas de forma que todas as cartas em determinado naipe apareçam contiguamente por exemplo primeiro aparecem todas as espadas a seguir todos os ouros então todas as copas e em seguida todos os naipes de paus 6 Dez casais estão esperando em uma fila para entrar em um restaurante Os maridos e as esposas ficam próximos uns dos outros mas qualquer um deles pode estar à frente do outro Quantas disposições desse tipo são possíveis 7 Avalie o seguinte n k2 k i 8 Seja A x Z x 10 Avalie A 9 Seja A 12 34 Quais das seguintes alternativas são verdadeiras e quais são falsas Não é necessária nenhuma prova a 1 6 A b 1 e A c 3 A d 3 e A e 3 CA 10 Sejam A e B conjuntos finitos Determine se os seguintes enunciados são verdadeiros ou falsos Justifique sua resposta com uma prova e um contraexemplo conforme apropriado a 2AnB 2An2B b 2AUB 2AU2B c 2AbB 2AA2B 11 Seja A um conjunto Quais das seguintes alternativas são verdadeiras e quais são falsas a x A sse x e 2A b T Ç A sse T 2a c x e A sse x 2a d x e A sse x e 2a Coleções 91 12 Quais dos seguintes enunciados sobre inteiros são verdadeiros e quais são falsos Não é necessária nenhuma prova a Vjc Vy x y b 3bc V y x y c Vjc 3 y x y d 3x 3 y x y 13 Seja px y uma sentença sobre dois inteiros xey Por exemplo px y poderia significar r y é um quadrado perfeito Suponha que o enunciado Vjc 3ypx y seja verdadeiro Qual dos seguintes enunciados sobre inteiros também deve ser verdadeiro a Vx 3y px y b 3x Vy pxy c 3x 3y pxy 14 Sejam A e B conjuntos e suponha que A X 5 12 13 22 23 Encontre AU B A D B e A B 15 Que A B e C denotem conjuntos Prove que A u B C A C U BQ e forneça uma ilustração do diagrama de Venn 16 Suponha que A e B sejam conjuntos finitos Dado que A 10 I U fi 15e fl 5 1 3 determine B 17 Sejam A e B conjuntos Crie uma expressão que seja estimada para A fl B e utilize apenas a união de operações e diferença de conjuntos Ou seja encontre a fórmula que utilize apenas os símbolos A B U e parênteses essa fórmula deve ser igual aA I1B para todos os conjuntos AeB 18 Seja n um inteiro positivo Forneça uma prova combinatória da identidade 3 nn 1 2 3 nn 1 n 116 Matemática Discreta 1511 De quantas maneiras podemos dividir vinte pessoas em dois times com dez jogadores cada 1512 De quantas maneiras podemos dividir cem pessoas em dez grupos de discussão com dez pessoas em cada grupo 1513 Quantas partições diferentes com exatamente duas partes podemos fazer no conjunto 1234 Responda à mesma pergunta para o conjunto 1 2 3 1 0 0 1514 Duas moedas diferentes são colocadas em casas de um tabuleiro padrão de xadrez 8 x 8 elas podem ser colocadas ambas na mesma casa SL y y í i Chamemos equivalentes dois arranjos dessas moedas no tabuleiro se pudermos mo ver as moedas diagonalmente para passar de um arranjo para outro Por exemplo as duas posições mostradas nos dois tabuleiros na figura anterior são equivalentes De quantas maneiras diferentes não equivalentes as moedas podem ser colocadas no tabuleiro 1515 Refaça o problema anterior admitindo que as moedas sejam idênticas 1516 Seja A um conjunto e seja V uma partição de A É possível termos A V í 16 Coeficientes binomiais Terminamos a seção anterior com o Exemplo 157 em que contamos o número de classes de equivalência da relação tem o mesmo tamanho que no conjunto de subconjuntos de 1 23 4 Encontramos cinco classes de equivalência diferentes correspondentes aos cinco inteiros de 0 a 4 e essas classes de equivalência têm diversos tamanhos Seus tamanhos são pela or dem 14 64 e 1 Esses números já devem ser conhecidos do leitor Observe x y4 lx4 y óx2 y2 4xy ly4 Esses números são os coeficientes de x y4 após desenvolvimento O leitor pode também reconhecer esses números como a quarta linha do triângulo de Pascal Nesta seção vamos explorar minuciosamente esses números A notação j se lê n k a k Outra forma dessa notação ainda em uso em algumas calculadoras é Ck Ocasionalmente escrevese C n k Como forma alternativa de expressar j é como o número de combinações de n objetos tomados k de cada vez A palavra com bin atória um termo que se refere a problemas de contagem em matemática discreta provém de combinações Não aprecio Contagem e Relação 117 o uso da palavra combinações e creio ser mais claro dizer que j representa o número de sub conjuntos de k elementos de um conjunto de n elementos O problema central que vamos considerar nesta seção é o seguinte Quantos subconjuntos de tamanho k tem um conjunto de n elementos Há uma notação especial para a resposta a essa questão Definição 161 Coeficiente binomial Sejam n k e N O símbolo l denota o número de subconjuntos de k elementos de um conjunto de n elementos O número é chamado coeficiente binomial A razão dessa designação é que os números são os coeficientes do desenvolvimento de x yn Esse ponto será explicado adiante com mais detalhe Exemplo 162 Calcule q Solução Devemos contar o número de subconjuntos de zero elementos de um conjunto de cinco elementos O único conjunto possível é 0 de modo que a resposta é Q 1 É claro que não há nada de especial quanto ao número 5 nesse exemplo O número de subconjuntos com zero elementos em qualquer conjunto é sempre 1 Temos pois para todo n e N Exemplo 163 Calcule j Solução O problema pede o número de subconjuntos de um elemento de um conjunto de cinco elementos Consideremos por exemplo o conjunto de cinco elementos 1 2 3 4 5 Os subconjuntos de um elemento são 1 2 3 4 e 5 assim j 5 O número de subconjuntos de um elemento de um conjunto de n elementos é exatamente n Exemplo 164 Calcule j Solução O símbolo j representa o número de subconjuntos de dois elementos de um conjunto de cinco elementos O mais simples a fazer é listar todas as possibilidades 118 Matemática Discreta 12 13 14 15 23 24 25 34 35 45 Há portanto dez subconjuntos de dois elementos em um conjunto de cinco elementos de forma que 2 4 3 2 1 10 Há um padrão interessante no Exemplo 164 Procuremos generalizálo Suponha que queiramos saber o número de subconjuntos de dois elementos de um conjunto de elementos Seja 1 2 3 o conjunto de n elementos Podemos fazer um quadro como no exemplo A primeira linha do quadro relaciona os subconjuntos de dois elementos cujo menor elemento é 1 A segunda linha relaciona os subconjuntos de dois elementos cujo menor elemento é 2 e assim por diante e a última linha da tabela relaciona o único subconjunto de dois elementos cujo menor elemento é n 1 isto é 1 Note que nosso quadro esgota todas as possibilidades 0 menor elemento deve ser um dos números de 1 a n 1 não ocorrendo nenhuma duplicação os subconjuntos em linhas diferentes da tabela têm menores elementos diferentes O número de conjuntos na primeira linha dessa tabela hipotética é n 1 porque uma vez que decidamos que o menor elemento é 1 0 subconjunto se apresenta assim 1 O segundo elemento deve ser maior que 1 sendo pois escolhido em 2 há 1 maneiras de completar 0 conjunto 1 O número de conjuntos da segunda linha dessa tabela é 2 Todos os subconjuntos nessa linha se apresentam assim 2 O segundo elemento deve ser escolhido entre os números 3 a n de modo que há 2 maneiras de completar esse conjunto De modo geral o número de conjuntos na linha k dessa tabela hipotética é n k Os subconjuntos nessa linha se apresentam assim k e o segundo elemento do conjunto deve ser um inteiro de k 1 a n havendo n k possibilidades Essa discussão constitui a prova do seguinte resultado Proposição 165 Seja n um inteiro com n 2 Então n1 l 2 3 n l lfc kl Até agora calculamos jj e Q Prossigamos com essa exploração Exemplo 166 Calcule 3 Contagem e Relação 119 Solução Simplesmente listamos os subconjuntos de três elementos de 1 2 3 4 5 123 124 125 134 135 145 234 235 245 345 Há dez desses conjuntos assim 3 10 Note que Q 10 Essa igualdade não é uma coincidência Vejamos por que esses números são iguais A ideia é achar uma maneira natural de emparelhar os dois subconjuntos de 1 2 3 4 5 com os subconjuntos de três elementos Queremos uma correspondência biunívoca entre esses dois tipos de conjunto Naturalmente poderíamos apenas listálos em duas colunas de uma tabela mas isso não é necessariamente natural A ideia é tomar o com plemento consulte o Exemplo 1117 de um subconjunto de dois elementos para formar um subconjunto de três elementos ou viceversa É 0 que vamos fazer aqui A A A A 12 345 24 13 5 13 245 25 134 14 235 34 125 15 234 35 0 24 23 145 45 123 Este é um exemplo de prova bijetíva O conceito de complemento de um conjunto é desenvolvido no Exemplo 1117 Cada subconjunto de dois elementos A é emparelhado com 12 34 5 A que denotamos por A pois 1 234 5 é o universo que estamos considerando no momento Esse mparelhamento A A é uma correspondência biunívoca entre os subconjuntos de dois e de três elementos de 12 34 5 Se A x e A2 são dois subconjuntos diferentes de dois elementos então A e A2 são dois subconjuntos diferentes de três elementos Todo subconjunto de dois elementos é emparelhado com exatamente um subconjunto de três elementos e nenhum conjunto fica fora do emparelhamento Isso explica de modo cabal por que ij 3 e nos abre o caminho para a generalização Poderíamos supor 3 mas isso não seria correto Apliquemos nossa análise do complemento a j e vejamos o que aprendemos Seja A um subconjunto de dois elementos de 1 2n Nesse contexto A significa 1 2n A O emparelhamento A não estabelece correspondência entre subconjuntos de dois e de três elementos O complemento de um conjunto de dois elementos seria um subconjunto de 2 elementos de 12 n Temos agora o resultado correto n2 Podemos avançar mais com essa análise Em lugar de formar o complemento dos subconjuntos de dois elementos de 12 n podemos formar os complementos de subconjuntos de outros tamanhos Quais são os complementos dos subconjuntos de k elementos de 12 São 120 Matemática Discreta precisamente os subconjuntos de n k elementos Além disso a correspondência AÃ dá um emparelhamento um a um dos subconjuntos de k e n k elementos de 1 2 n Isso implica que o número de subconjuntos de k e n k elementos de um conjunto de n elementos deve ser o mesmo O que acabamos de mostrar é o que segue Proposição 167 Sejam n k 6 N com 0 kn Então Eis outra maneira de cogitar sobre esse resultado Imagine uma turma com n crianças O professor tem k barras de chocolate idênticas para dar a exatamente k das crianças De quantas maneiras as barras de chocolate podem ser distribuídas A resposta é k porque estamos selecionando um conjunto de k crianças para ganhar a barra de chocolate Mas a visão pessimista também é interessante Podemos pensar em selecionar as crianças sem sorte que não receberão o chocolate H à n k crianças nessas condições e podemos selecionar esse subconjunto da classe de t maneiras Como os dois problemas de contagem obviamente coincidem devemos ter nk n J Calculamos até agora Q Q e 3 Prossigamos Podemos utilizar a Proposição 167 para calcular 4 a proposição afirma que e já sabemos que Q 5 Assim Q 5 Em seguida vem 5 Podemos utilizar a Proposição 167 e raciocinar 5 5Í 5 jj 1 ou podemos entender que só pode haver um subconjunto de cinco elementos em um conjunto de cinco elementos a saber o conjunto total Em seguida vem ij Podemos tentar usar a Proposição 167 mas nos deparamos com um empecilho Escrevemos s 5 H ò mas não sabemos o que é j Na realidade a situação é pior não tem sentido Não faz sentido pedir o número de subconjuntos de um conjunto de cinco elementos que tenham 1 elementos não tem sentido considerar conjuntos com um número negativo de elementos Esta é a razão pela incluímos a hipótese O úkúnw à formulação da Proposição 167 Entretanto um conjunto pode ter seis elementos de modo que jD não deixa de ter sentido é simplesmente zero Um conjunto de cinco elementos não pode ter nenhum subconjunto de seis elementos de forma que g 0 Analogamente 7 8 0 Resumamos o que aprendemos até agora Contagem e Relação 121 Calculamos 5k para todos os números naturais k Os valores são 1 510 10 5 1 0 0 para k 0 1 2 respectivamente Temos q 1 e n Temos f i 1 2 n 1 Temos Se k n Q 0 Cálcu lo de nk Até agora calculamos diversos valores de mas nosso trabalho tem sido específico Não temos um método geral para obter esses valores Constatamos que os valores não nulos de são 15 10 10 5 L Desenvolvendo x y5 obtemos x y2 lx3 5x4y IQxy1 Í0x2y3 5xy4 1 y x y 2 2 x2y3 í xy Isso sugere uma forma para calcular nk desenvolver x yn e k é o coeficiente de xnkyk Isso é realmente maravilhoso Vamos proválo Teorema 168 Binomial Seja n G N Então n x yy 2 k 0 nk Xk a y Esse resultado explica por que Q é chamado coeficiente binomial Os números nk são os coeficientes que aparecem no desenvolvimento de x yn Prova A chave para a prova do teorema binomial consiste em pensarmos como multiplicamos polinómios Quando multiplicamos x y2 fazemos o seguinte cálculo x y2 x y jcyxx xyjjcy e gmpamos os termos semelhantes obtendo x2 2xy y1 O processo para x y é precisamente o mesmo Escrevemos n fatores x x y x y x y x y Formamos então todos os termos possíveis tomando um x ou um y dos fatores 1 2 3 n Isso equivale a fazer listas ver Seção 7 Estamos formando todas as listas de n elementos possíveis onde cada elemento é umx ou um y Por exemplo 122 Matemática Discreta x y x y x y xxx xxy xyx xyy yxx yxy yyxyyy O próximo passo consiste em grupar os termos semelhantes No exemplo x y3 há um termo com três x e nenhum y três termos com dois x e um y três termos com um x e dois y e um termo com nenhum x e três y Isso nos dá x y3 lx3 3x2y 3 xy2 ly3 A questão tomase então quantos termos de x yn têm precisamente os k y e n k os x Encaremos esse problema como uma questão de contagem de lista Desejamos contar o número de listas de n elementos com precisamente w k x e os ky E sabemos qual deve ser a resposta nk Devemos justificar essa resposta Podemos especificar todas as listas com os k y e n kx fixando as posições dosy e os x ocuparão as posições restantes Por exemplo se n 10 e dizemos que o conjunto de posições de y é 2 3 7 então sabemos que estamos falando do termo lista xyyxxxyxxx Poderíamos fazer uma tabela à esquerda da tabela ficariam todas as listas com os k y e n k x e à direita escreveríamos o conjunto de posições de y para cada lista A coluna da direita da tabela consistiria simplesmente nos subconjuntos de k elemèntos de 1 2 n Mas o número de listas com os k y z n k x é exatamente o mesmo que o número de subconjuntos de k elementos de 12 Portanto o número xky de termos que agrupamos é E isso completa a prova Exemplo 169 Desenvolver x y5 e achar todos os termos com dois y e três x Emparelhar esses termos com os subconjuntos de dois elementos de 1234 5 Solução yyxxx 1 2 yxyxx 13 yxxyx 14 yxxxy 1 5 xyyxx 23 xyxyx 24 xyxxy 2 5 xxyyx 34 xxyxy 35 xxxyy 45 Temos agora um processo para calcular digamos Tudo quanto devemos fazer é desenvolver x y20 e achar o coeficiente de x10 y 10 Para tanto escrevemos todos os termos de xxx xx a yyy yy e grupamos os termos semelhantes Há apenas 220 1048576 termos Parece brincadeira Não O leitor tem razão Esta não é uma boa maneira de calcular jq Não é melhor do que escrever todos os subconjuntos de dez elementos possíveis de 1 2 20 E há um grande número deles Quantos não sabemos É o que estamos procurando determinar Necessitamos de outro método ver também o Exercício 1629 Contagem e Relação 123 O triângulo de Pascal O leitor deve estar lembrado do seu curso de álgebra que os coeficientes de x yn formam a Mésima linha do triângulo de Pascal Afigura a seguir mostra o triângulo de Pascal O valor registrado na linha n 4 e diagonal k 2 é Q 6 conforme mostrado contamos as linhas e as diagonais a partir de 0 Como é gerado o triângulo de Pascal Eis uma descrição completa A linha zero do triângulo de Pascal contém apenas o número 1 Cada linha sucessiva contém mais um número do que a anterior O primeiro e o último números em cada linha são 1 Um número intermediário em qualquer linha é formado pela adição dos dois números exatamente à sua direita e à sua esquerda na linha anterior Por exemplo o primeiro 10 na linha n 5 e diagonal k 2 é formado adicionandose o 4 à sua esquerda superior em n 4 l e o 6 à sua direita superior em n 4k 2 envolvido por um círculo na figura JS 0 f s 1 1V V 2 1 2 f é 3 1 3 31 l 4 4 l v 51 T l O 10 5 1 Como sabemos qué o triângulo de Pascal gera os coeficientes binomiais Como sabemos que o elemento na linha n e coluna k é Jfi Para vermos por que isso funciona devemos mostrar que os coeficientes binomiais seguem as mesmas quatro regras que acabamos de citar Em outras palavras formamos um triângulo contendo na linha zero Q na primeira linha 0 j 2 na segunda linha e assim por diante Devemos então provar que esse triân gulo de coeficientes binomiais é gerado exatamente pelas mesmas regras que o triângulo de Pascal Há nisso três quartos de facilidade e um quarto de estratagema Prossigamos A linha zero do triângulo de coeficientes binomiais contém o único número 1 Isso é fácil a linha zero do triângulo de coeficientes binomiais é 1 Cada linha sucessiva contém um número a mais que a linha antecedente Isso é fácil de ver a linha n do triângulo de coeficientes binomiais contém exatamente n 1 números O primeiro e o último números em cada linha é 1 O primeiro e o último número na linha n do triângulo de coeficientes binomiais é JJ O número intermediário em qualquer linha é formado pela adição dos dois números imediatamente à sua direita e imediatamente à sua esquerda na linha anterior Isso é ardiloso A primeira coisa a fazer é definir cuidadosamente o que precisamos provar sobre os coeficientes binomiais Precisamos de um número intermediário em qualquer linha Isso significa que não precisamos preocuparnos com ou IÉÉé i 124 Matemática Discreta 1 Já sabemos que ambos são 1 Um número intermediário em qualquer linha n seria com 0 k n Quais são os números logo acima de Para acharmos o vizinho superior esquerdo caminhamos para cima até a linha n 1 e até a diagonal k 1 Assim o número à esquerda superior é Para acharmos o vizinho superior direito caminhamos para cima até a linha n 1 mas permanecemos na diagonal k Assim o número à direita superior é k Devemos provar o seguinte Teorema 1610 Identidade de Pascal Sejam n e k inteiros com 0 k n Então GH0 v Como podemos provar isso Não dispomos de uma fórmula para A ideia é utilizar a prova combinatória ver Esquema de prova 9 Devemos formular uma pergunta e então provar que os membros esquerdo e direito da equação do Teorema 1610 dão ambos respostas corretas a essa pergunta Que pergunta admite tais respostas Há uma pergunta óbvia à qual o membro esquerdo dá uma resposta A pergunta é quantos subconjuntos de k elementos têm um conjunto de n elementos Prova Para provar que nk consideramos a pergunta Quantos subconjuntos de k elementos tem o conjunto 12 3 Resposta 1 por definição Mas precisamos de outra resposta O membro direito da equação nos dá algumas suges tões contém os números n k e k e nos diz que escolhamos ou k 1 ou A elementos de um conjunto de n 1 elementos Mas temos cogitado de um conjunto de n elementos e assim desprezemos um dos elementos digamos que o elemento n é um estranho O membro direito nos diz que escolhamos k 1 ou k elementos entre os elementos nor mais 1 2 n 1 Se escolhemos apenas k 1 elementos não perfazemos um conjunto completo de k elementos nesse caso podemos acrescentar o elemento estranho ao sub conjunto de k 1 elementos Ou então selecionamos elementos entre os elementos normais Temos agora um subconjunto completo de k elementos não havendo mais lugar para o elemento estranho Contagem e Relação 12 5 Temos agora todas as ideias em seus lugares expressemolas com clareza Seja n o elemento estranho de 12 n e chamemos normais os outros elementos Quando formamos um subconjunto de elementos de 12 há duas possibilidades Ou temos um subconjunto que inclui o elemento estranho ou temos um subconjunto que não o inclui essas possibilidades mutuamente excludentes abrangem todos os casos Se incluímos o elemento estranho no subconjunto então temos I J escolhas para completar o subconjunto porque devemos escolher k 1 elementos de 12 n 1 Se não colocamos o elemento estranho no subconjunto então temos n1 maneiras de formar o subconjunto porque devemos escolher todos os k elementos de 12 n 1 Temos assim outra resposta Resposta 2 l V Como as respostas 1 e 2 são ambas respostas corretas do mesmo problema elas devem ser iguais e estamos terminados Exemplo 1611 Mostraremos que 0 listando todos os subconjuntos de dois elementos de 12 34 5 6 Há j 5 subconjuntos de dois elementos que incluem o estranho 6 16 26 36 46 56 e há j 10 subconjuntos de dois elementos que não incluem 6 12 13 14 15 23 24 25 34 35 45 Desejamos agora calcular j0 A técnica que poderíamos seguir consiste em gerar o triângulo de Pascal até a 20a linha e procurar 0 valor na diagonal 10 Quanto trabalho exigiria isso A 20a linha do triângulo de Pascal contém 21 números A linha precedente contém 20 e a linha antes dela tem 19 Há apenas 12 3 21 231 números Obtemos a maior parte deles por simples adição necessitando de cerca de 200 adições Podemos ser mais eficientes ver o Exercício 1630 Se fôssemos implementar esse processo em um computador não precisaríamos salvar todos os 210 números Deveríamos salvar apenas 40 Uma vez calculada uma linha do triângulo de Pascal podemos ignorar a linha anterior Assim em qualquer instante basta conservarmos a linha anterior e a linha corrente E se o operador for arguto poderá até economizar mais memória Em qualquer caso seguindo esse procedimento o leitor verificará que jq 184756 126 Matemática Discreta Uma Fórmula para O procedimento de gerar um triângulo de Pascal para calcular coeficientes binomiais é uma boa técnica Podemos calcular jj resolvendo cerca de 200 problemas de adição em vez de peneirar um milhão de termos em um polinómio ver também Exercício 1629 Há algo não muito satisfatório nessa resposta Gostamos de fórmulas E desejamos uma maneira elegante de expressar nk em uma forma simples utilizando operações familiares Temos uma expressão para Q a Proposição 165 afirma que 2 1 2 3 n 1 Isso não é nada mau mas sugere que ainda precisamos fazer uma boa quantidade de adições para obtermos a resposta Há entretanto um interessante artifício para simplificar essa soma Escrevamos os inteiros de 1 a n 1 em ordem crescente e em ordem decrescente e somemos Q I 2 3 n 2 n l H 2 rz l t 2 n 3 2 1 2 Q n n n n nn 1 assim f n nn 1 W 2 Essa equação é um caso especial de um resultado mais geral Eis outra maneira de contar subconjuntos de k elementos de um conjunto com n elementos Comecemos contando todas as listas de k elementos sem repetição cujos elementos são extraídos de um conjunto de n elementos Tratase de um problema que já resolvemos ver Seção 7 O número de tais listas é nk Por exemplo há 53 5 4 3 60 listas de três elementos sem repetição que podemos formar com os elementos de 12 345 Eilas 123 132 213 231 312 321 124 142 214 241 412 421 125 152 215 251 512 521 e assim por diante até 345 354 435 453 534 543 Todos os valores de determinada linha dessa tabela expressam o mesmo subconjunto de três elementos de seis maneiras diferentes Como essa tabela tem 60 valores o número de subconjuntos de três elementos de 1 2345 é 60 6 10 Note como organizamos nossa tabela Todas as listas da mesma linha contêm precisamente os mesmos elementos apenas em ordens diferentes Definamos uma relação R sobre essas listas A relação é tem os mesmos elementos que duas listas estão relacionadas pela R quando seus elementos são precisamente os mesmos embora suas ordens possam ser diferentes Contagem e Relação 127 Obviamente R é uma relação de equivalência Cada linha da tabela representa uma classe de equivalência Interessanos contar as classes de equivalência Há 60 elementos do conjunto todos são listas de três elementos Cada classe de equivalência contém seis listas Portanto o número de classes de equivalência é 10 3 pelo Teorema 156 Refaçamos essa análise para o problema geral Desejamos contar 0 número de subconjuntos de k elementos de 1 2 n Em lugar disso consideramos as listas de k elementos sem repetição que podemos formar com 1 2 n Definimos duas dessas listas como equivalentes se elas contêm os mesmos elementos Por fim calculamos 0 número de classes de equivalência para calcular O número de listas de k elementos sem repetição que podemos formar a partir de 12 ri é um problema que já resolvemos Teorema 76 há nk dessas listas Portanto o número de classes de equivalência é nJk Podemos reescrever nk como nn k desde que k ne temos o resultado a seguir A razão por que cada lista é equivalente a kk c decorre também do Teorema 76 desejamos saber quantas listas de tamanho k sem repetição podemos formar utilizando k elementos Teorema 1612 Fórmula p ara Sejam n e k inteiros com 0 kn Então n n kn k Encontramos uma fórmula para Estamos satisfeitos Talvez Se desejamos calcular j o que é que esse teorema nos manda fazer Ele determina que calculemos 2 0 20 x 19 x 18 x x 3 x 2 x 1 1 0 1 0 x 9 x 8 x x 2 x l x l 0 x 9 x 8 x x 2 x l Isso exige cerca de 40 multiplicações e 1 divisão Os resultados intermediários o numerador e o denominador também são extremamente grandes mais algarismos que a maior parte das calculadoras comporta Naturalmente podemos cancelar alguns termos no numerador e no denominador a fim de abreviar os cálculos Os últimos dez termos do numerador são 10 x x 1 o que cancela um dos 10 do denominador Assim 0 problema se reduz a 20 20 x 19 x 18 x x 11 10y 10 x 9 x 8 x x 1 Podemos procurar mais cancelamentos mas isso nos leva a considerar os números envolvidos O cancelamento de um 10 no denominador foi trivial poderíamos têlo introduzido facilmente em um programa de computador Outros cancelamentos podem ser complicados para achar Se estamos trabalhando em um computador podemos perfeitamente fazer as multiplicações restantes e a divisão final o que seria Mais Provas 4 Até aqui temos utilizado principalmente uma técnica de prova conhecida como prova direta Nesse método trabalhamos da hipótese para a con clusão mostrando como cada afirmação decorre de afirmações prévias A ideia central é desenredar definições e preencher a lacuna entre o que temos e o que desejamos Estamos agora prontos para métodos mais sofisticados de prova e precisamos deles Neste capítulo vamos apresentar dois métodos po derosos a prova por contradição e a prova por indução e sua variante prova por contraexemplo mínimo 19 Contradição A maioria dos teoremas pode expressarse na forma seentão A maneira usual de provar Se A então B consiste em supor as condições relacionadas em A e procurar provar as condições em B ver Esquema de prova 1 Nesta seção vamos apresentar duas alternativas para esse método direto de prova Prova pela contrapositiva A afirmação Se A então B é logicamente equivalente à afirmação Se não B então não A A afirmação Se não B então não A é chamada contrapositiva de Se A então B Por que uma afirmação e sua contrapositiva são logicamente equivalentes Com efeito para que Se A então B seja verdadeira deve ocorrer que sempre que A for verdadeira B também deverá sêlo Se acontecer de B ser falsa A deveria ter sido falsa também Em outras palavras se B for falsa então A deverá ser falsa Temos assim Se não B então não A Eis outra explanação Sabemos que Se A então B é logicamente equivalente a não A ou B ver Exercício 33 Pelo mesmo raciocínio Se não B então não A é equivalente a não não B ou não A mas não não B é o mesmo que B e assim a expressão se reduz a B ou não A que é equivalente a não A ou B Em símbolos a b 1 a v b iò v a iò ia Se essas explanações são difíceis de acompanhar eis uma forma mecânica de proceder Construímos umatabelaverdadeparaa b eparaib a e observamos os mesmos resultados 156 Matemática Discreta a b ab i b ia 6 a V V V F F V V F F V F F F V V F V V F F V V V V A linha da base é para provar que Se A então B é aceitável provar Se não B então não A conforme esboçado no Esquema de prova 11 Esquema de prova 11 Prova pela contrapositiva Provar que Se A então B supor não E e tentar provar não A Vamos trabalhar com um exemplo Proposição 191 Seja R uma relação de equivalência em um conjunto A e sejam a b 6 A Se a b então a n è 0 Essencialmente isso já foi provado ver Proposição 1412 Nosso objetivo aqui é ilustrar a prova pela contrapositiva Nós o faremos utilizando o Esquema de prova 11 Seja R uma relação de equivalência em um conjunto A e sejam abA Vamos provar a contrapositiva da afirmação Suponhamos a n ó 0 Portanto a Rb O pontochave a observar é que supomos a oposta da conclusão não a D ó 0 e procuramos provar a oposta da hipótese não aflb isto éa R b Note que você foi alertado para o fato de que não estamos utilizando a prova direta anunciando que vamos provar a contrapositiva Para prosseguir a prova observamos que o fl i 0 significa que existe um elemento simultaneamente em a e em 6 Introduzamos esse fato na prova Seja R uma relação de equivalência em um conjunto A e sejam abA Vamos provar a contrapositiva da afirmação Suponhamos a fl 6 0 Então existe um jc 6 a n 6 isto é x G a e x e 6 Portanto a Rb Mais Provas 157 Para concluir vamos usar a definição de classe de equivalência Seja R uma relação de equivalência em um conjunto A e sejam a b A Vamos provar a contrapositiva da afirmação Suponhamos a fl è 0 Então existe um x e a fl isto é x e a e x G Logo x R a e x R b Por simetria a R xe como x R b por transitividade temos a Rb H Há alguma vantagem na prova pela contrapositiva Sim Tente provar a Proposição 191 diretamente Suporíamos a fl b e procuraríamos mostrar que a fl è 0 Como desenredaríamos a hipótese a ljtb l Como mostraríamos que dois conjuntos não têm qualquer elemento em comum Não temos uma forma razoável para levar a cabo essas tarefas uma prova direta aqui é bastante difícil Apelando para a contrapositiva temos condições mais fáceis de serem usadas Reductio ad absurdum A prova pela contrapositiva é a alternativa para o método direto Se não pudermos achar uma prova direta tentemos provar pela contrapositiva Não seria interessante se existisse uma téc nica de prova que combinasse a prova direta e a prova pela contrapositiva De fato ela existe E a chamada prova p o r contradição ou em latim reductio a d absurdum Eis como funciona A prova por contradição é também chamada prova indireta Um erro Eis outra maneira de encarara prova por contradição Supomos A e não B e prosseguimos com um raciocínio válido até chegarmos a uma situação impossível Isso significa que deve haver um erro Se todo nosso raciocínio é válido e como podemos supor A o erro deve ter sido em supor não B Como não S é o erro devemos ter B Pretendemos provar que Se A então B Para tanto mostramos que é impossível A ser verdadeiro enquanto B é falso Em outras palavras queremos mostrar que A e não B é impossível Como provamos que algo é impossível Admitimos que a coisa impossível seja verdadeira e provamos que essa suposição conduz a uma conclusão absurda Se uma afirmação implica algo claramente errado então a afirmação deve ser falsa Para provar Se A então B fazemos duas suposições Admitimos a hipótese A e supomos a oposta da conclusão isto é admitimos não B A partir dessas duas suposições procuramos chegar a uma afirmação claramente falsa O esboço geral é dado no Esquema de prova 12 158 Matemática Discreta Esquema de prova 12 Prova por contradição Provar que Se A então B Supomos as condições em A Por contradição supomos não B Argumentamos até chegar a uma contradição O símbolo é uma abreviatura do seguinte assim chegamos a uma contradição Portanto a suposição não B deve ser falsa Logo B é verdadeira Vamos apresentar uma descrição formal de uma prova por contradição e em seguida dar um exemplo Pretendemos provar uma afirmação da forma Se A então B Para isso admitimos A e não B e mostramos que isso implica algo falso Simbolicamente queremos mostrar que ab Paia tanto provamos que a Ah FALSO Essas duas proposições são logicamente equivalentes Proposição 192 As fórmulas booleanas a bea A h FALSO são logicamente equivalentes Prova Para confirmar que as duas expressões se equivalem logicamente construímos uma tabelaverdade a b a b a A ni FALSO V V V F V V F F V F F V V F V F F V F V Portanto a b a A b FALSO Apliquemos esse método para provar o seguinte Proposição 193 Nenhum inteiro é ao mesmo tempo par e ímpar Reexpressa na forma seentão a Proposição 193 é se x é um inteiro então x não pode ser simultaneamente par e ímpar Formulemos uma prova por contradição Mais Provas 159 Seja x um inteiro Suponhamos por contradição que x seja ao mesmo tempo par e ímpar Isto é impossível Chegamos assim a uma contradição e nossa suposição de que x seja ao mesmo tempo par e ímpar é falsa Portanto x não é simultaneamente par e ímpar e a proposição está provada n Cabem aqui vários comentários A primeira sentença dá a hipótese seja x um inteiro A segunda sentença atende a dois propósitos Primeiro anuncia a você que se trata de uma prova por contradição por meio da frase por contradição Segundo supõe o oposto da conclusão A suposição é que x seja simultaneamente par e ímpar A próxima sentença afirma Isto é impossível Não sabemos qual é o antecedente de Isto O que é impossível Ainda não sabemos A medida que a prova se desenvolve esperamos chegar a uma contradição Dado que chegamos a uma contradição eis como concluímos a prova Afirmamos que a suposição é impossível porque leva a uma afirmação absurda Portanto a suposição não B deve ser falsa Logo a conclusão B deve ser verdadeira As últimas poucas sentenças de uma prova por contradição são quase sempre as mesmas Os matemáticos usam um símbolo especial para abreviar um grupo de palavras O símbolo é A imagem é a de que duas implicações estão colidindo uma com a outra O símbolo é uma abreviatura para chegamos assim a uma contradição por conseguinte a suposição é falsa A suposição é aquilo que admitimos isto é não B Não sabemos ainda a qual contradição podemos chegar Vamos continuar trabalhando com o que temos Sabemos que x é ao mesmo tempo par e ímpar e dessa forma procuremos desenredar Seja x um inteiro Suponhamos por contradição que x seja ao mesmo tempo par e ímpar Como x é par sabemos que 2x isto é existe um inteiro a de modo que x 2a Como x é ímpar sabemos que existe um inteiro b de modo que x 2 b Portanto x não pode ser simultaneamente par e ímpar e a proposição está provada Até agora nenhuma contradição As definições estão completamente desenredadas Devemos trabalhar com x 2a 2b 1 em que a e b são inteiros De alguma forma devemos 160 Matemática Discreta manipular esses elementos a fim de chegar a algo falso Tentemos dividir a equação x 2a 2b 1 por 2 obtendo a b o que nos diz que um inteiro é apenas maior que o outro isto é a b Mas a b é um inteiro e não é Um número a b não pode ser ao mesmo tempo inteiro e não inteiro É uma contradição Hurra Vamos introduzila na prova Note que não utilizamos f na contradição o que nos permite simplificar bastante Seja x um inteiro Suponhamos por contradição que x seja par e ímpar Como x é par sabemos que 2x isto é existe um inteiro a de modo que x 2a Como x é ímpar sabemos que existe um inteiro b de modo que x 2b 1 Portanto 2a 2b 1 Dividindo ambos os membros por 2 obtemos a b 1 de forma que a b Note que a b é um inteiro pois a tb o são mas não é inteiro Logo x não é ao mesmo tempo par e ímpar e a proposição está provada Isso completa a prova Quando começamos essa prova não sabíamos que a contradição a que chegaríamos seria a de que 5 é um inteiro Isso é típico em uma prova por contradição começamos com A e não B e vemos aonde a implicação conduz A Proposição 193 também pode expressarse como segue Sejam X x 6 Z x é par e Y x Z x é ímpar Então X tlY 0 A prova por contradição é em geral a melhor técnica para mostrar que um conjunto é va zio Ela justifica a codificação em um esquema de prova Esquema de prova 13 1 Provar que um conjunto é vazio Para provar que um conjunto é vazio Suponha que o conjunto é não vazio e argumente de forma a chegar a uma contradição O Esquema de prova 13 é apropriado para provar afirmações da forma Não há objeto que satisfaça às condições A contradição é também a técnica de prova escolhida quando devemos provar afirmações de unicidade Tais afirmações asseguram que só pode haver um objeto que satisfaça às condições dadas Mais Provas 161 Linguagem matemática Você poderia esperar que acima de todas as pessoas os matemáticos empregassem a palavra dois corretamente Pode surpreender pois quando um matemático diz dois ele eventualmente quer dizer um ou dois Eis um exemplo Consideremos a seguinte afirmação Todo inteiro positivo par é a soma de dois inteiros positivos ímpares Os matemáticos consideram verdadeira essa afirmação a despeito do fato de só haver uma maneira de escrever 2 como soma de dois inteiros positivos ímpares a saber 2 1 1 Ocorre que apenas os dois números são o mesmo A frase Sejam x e y dois inteiros permite que os inteiros x e y sejam o mesmo Esta é a convenção embora um tanto perigosa Seria melhor escrever simplesmente Sejam x e y inteiros Ocasionalmente interessanos eliminar a possibilidade x y Nesse caso escrevemos Sejam x e y dois inteiros diferentes ou Sejam x e y dois inteiros distintos Esquema de prova 14 Prova da unicidade Para provar que há no máximo um objeto que satisfaz determinadas condições Suponhamos que haja dois objetos diferentes x e y que verificam as condições Argumente de modo a chegar a uma contradição Com frequência a contradição em uma prova de unicidade é que os dois objetos alegadamente diferentes são na verdade o mesmo Eis um exemplo simples Proposição 194 Sejam a e b números com aO Existe no máximo um número x com ax b 0 Prova Suponhamos que haja dois números diferentes x ey de modo que ax b 0 e q y b 0 Isso nos dá ax b ay b Subtraindo b de ambos os membros vem ax ay Como a 0 podemos dividir ambos os membros por a obtendo x jyx Uma questão de estilo A prova por contradição de Se A então B em geral é mais fácil do que a prova direta por que oferece mais condições Em vez de começarmos com a única condição A e procurarmos demonstrar a condição B comecemos com A e não B conjuntamente e procuramos uma contradição Isso nos dá mais material para trabalhar As vezes quando optamos por uma prova por contradição podemos descobrir que tal prova realmente não era exigida sendo possível um tipo mais simples de prova Uma prova é uma prova e você deve darse por feliz se conseguir chegar a uma prova correta Não obstante é sempre preferível uma forma mais simples de apresentar seu argumento Eis como dizer se é possível simplificar uma prova do tipo Se A então B 162 Matemática Discreta Você supôs A e não B Utilizou apenas a hipótese A e a contradição a que chegou foi B e não E Nesse caso temos realmente uma prova direta e podemos remover o aparato estranho da prova por contradição Supusemos A e não B Usamos apenas a suposição não B e a contradição a que chegamos foi A e não A Nesse caso temos realmente uma prova pela contrapositiva Reescrevaa nessa forma Recapitulando Introduzimos duas novas técnicas de prova para afirmações da forma Se A então B Em uma prova pela contrapositiva supomos não B e procuramos provar não A Em uma prova por contradição supomos A e não B e procuramos chegar a uma contradição 19 Exercícios 191 Formule a contrapositiva de cada uma das seguintes afirmações a Se x é ímpar então x2 é ímpar b Se p é primo então 2P 2 é divisível por p c Se x é diferente de zero então x1 é positivo d Se as diagonais de um paralelogramo são perpendiculares então o paralelogramo é um losango e Se a bateria está carregada o carro dará a partida f Se A ou B então C 192 Qual é a contrapositiva da contrapositiva de uma afirmação do tipo seentão 193 Uma afirmação da forma A se e somente se B costuma ser provada em duas partes em uma delas mostramos que A Be na outra que B A Explique por que também é aceitável a seguinte estrutura para uma prova Primeiro provamos que A B e em seguida provamos que A B 194 Para cada uma das afirmações seguintes escreva as primeiras sentenças de uma prova por contradição você não deve tentar completar as provas Utilize a frase por contradição a Se A Ç B e B Ç C então A C C b A soma de dois inteiros negativos é um inteiro negativo c Se o quadrado de um número racional é um inteiro então o número racional deve ser também um inteiro d Se a soma de dois primos é um primo então um dos primos deve ser 2 e Uma reta não pode interceptar os três lados de um triângulo f Círculos distintos interceptamse no máximo em dois pontos g Há um número infinito de números primos 195 Prove por contradição que inteiros consecutivos não podem ser ambos pares 196 Prove por contradição que inteiros consecutivos não podem ser ambos ímpares w Funções O conceito de Junção é central em matemática Intuitivamente uma função pode ser encarada como uma máquina Introduzse um número na máquina apertase um botão e sai uma resposta Uma propriedadechave do fato de ser uma função é a consistência Toda vez que introduzimos um número específico digamos 4 na máquina aparece sempre a mesma resposta A figura ao lado ilustra esse fato Ali a função recebe um inteiro x como entrada e devolve o valor 3x 1 Assim toda vez que o número 4 é introduzido na máquina surge a resposta 47 Note que a função da figura opera sobre números Não teria sentido introduzir um triângulo no alimentador dessa máquina Não obstante podemos criar uma função cujas entradas sejam triângulos e cujas saídas sejam números Por exemplo podemos definir como a função cujas entradas são triângulos e para cada triângulo introduzido na função a saída é a área do triângulo O mecanismo na máquina da função não precisa ser ditado por uma fórmula algébrica Tudo quanto se exige é que se especifiquem cuidadosamente as entradas permitidas e para cada entrada a saída cor respondente Em geral isso se faz por meio de uma expressão algébrica embora haja outros meios de especificar uma função Neste capítulo faremos um estudo cuidadoso das funções come çando com uma definição precisa 23 Funções Intuitivamente uma função é uma regra ou um mecanismo que transforma uma quantidade em outra Por exemplo a função X x2 4 toma um inteiro x e o transforma no inteiro x2 4 A função gx x toma o inteiro x e retoma x se x 0 e x se x 0 Nesta seção vamos desenvolver uma visão mais abstrata e rigorosa das funções As funções são tipos especiais de relações reveja a Seção 13 Recordese de que uma relação nada mais é que um conjunto de pares ordenados Assim como essa definição de relação foi em princípio contraintuitiva também a definição precisa de uma função pode parecer estranha inicialmente 222 Matemática Discreta Definição 231 Função Uma relação f é chamada função desde que a b G e a c G impliquem bc Enunciada de forma negativa uma relação não é uma função se existem a b c com a h G eo c e f e b f c Exemplo 232 Sejam 12 23 31 4 7 e g 12 13 4 7 A relação é uma função mas a relação g não o é porque 12 1 3 G g e 2 3 Linguagem matemática Os matemáticos costumam usar a palavra aplicação como sinônimo de função Além de dizer f de 1 é igual a 2 também se referem a f aplica 1 em 2 E há uma notação para isto escrevemos 1 2 A seta especial significal 2 Afunçãonão é explicitamente mencionada na notação 1 1 2 quando usamos a notação devemos ter a certeza de que o leitor sabe que função está sendo discutida Quando expressas como conjuntos de pares ordenados as funções não se parecem com regras para transformar um objeto em outro mas vamos observar melhor Os pares ordenados em associam valores de entrada os primeiros elementos nas listas em a valores de saída os segundos elementos nas listas No Exemplo 232 a função associa o valor de entrada 1 ao valor de saída 2 pois 12 G A razão por que g não é uma função é que para o valor de entrada 1 há dois valores de saída diferentes 2 e 3 O que toma f uma função é o fato de que para cada entrada só pode haver no máximo uma saída Os matemáticos raramente utilizam a notação 1 2 G embora isso seja formalmente correto Eles preferem a notação Definição 233 Notação de função Seja uma função e seja a um objeto A notação fa é definida desde que exista um objeto b de modo que a b e f Nesse casozz b Caso contrário não existe par ordenado da forma a G a notação fà não está definida O símbolo fq se lê de a Para a função do Exemplo 232 temos 1 2 2 3 3 l4 7 Funções 223 mas para qualquer outro objeto xfx permanece indefinida A razão por que não chamamos g uma função se toma mais clara Quanto é g 1 Uma vez que tanto 12 como 13 g a notação gl não especifica um valor único Exemplo 234 Problema Expresse a função fx x2 definida no conjunto dos inteiros como um con junto de pares ordenados Solução Poderíamos escrever isto utilizando reticências 3 9 24 1 1 0 0 1 1 24 3 9 mas é muito mais claro se empregarmos a notação de definição de conjuntos y x y e z y x2 Em geral é mais claro escrevermos Seja f a função definida para um inteiro x por fx jc2 do que escrevermos como um conjunto de pares ordenados como no exemplo A notação de conjunto de pares ordenados para uma função equivale a escrevermos uma função como uma tabela X Á x 3 9 2 4 1 1 0 0 1 1 2 4 3 9 Domínio e imagem O conjunto de entradas permitidas e de saídas possíveis de uma função têm nomes especiais Definição 235 Domínio imagem Seja uma função O conjunto de todos os primeiros elementos possíveis dos pares ordenados deé chamado domínio de f e se denota por dom f O conjunto de todos os segundos elementos possíveis dos pares ordenados de f se chama imagem dee se denota por im f 224 Matemática Discreta Em outra notação dom a 3b a b e j e im b 3a a b e j De forma alternativa podemos escrever dom a fa está definido e im f b b ja para algum a Exemplo 236 Seja 12 23 31 4 7 Esta é a função do Exemplo 232 Então dom 12 34 e im 12 3 7 Exemplo 237 Seja a função do Exemplo 234 isto é f x y x y e Z y x 2 O domínio de f é o conjunto de todos os inteiros e a imagem de é o conjunto de todos os quadrados perfeitos Introduzimos a seguir uma notação especial para funções Definição 238 f A B Seja uma função e sejam os conjuntos A eB Dizemos que f é uma junção de A para B se dom A e im Ç B Nesse caso escrevemos f A B Dizemos também que f é uma aplicação de A em B A notação f A B s e l ê f é uma função de A para B A notação f A B sugere três coisas primeiraé uma função segunda dom f A terceira im Ç B Linguagem matemática A notaçãoA B pode ser toda uma sentença uma cláusula independente ou uma frase Em um teorema poderíamos escrever Se fAB então Nesse caso devemos ler os símbolos como Se é uma função de A para B Não obstante podemos também escrever Seja A B Nesse caso deveríamos ler Sejauma função de A para B Exemplo 239 Consideremos a função seno Essa função é definida para todo número real e tem um valor real O domínio da função seno consiste em todos os números reais e a imagem é o conjunto 11 x e R 1 x 1 Podemos escrever sen R R porque dom sen R e im sen Ç R Seria correto também escrevermos sen R 11 Funções 225 1 Para provar que AB isto é para provarmos que é uma função de A para B usaremos o Esquema de prova 19 Esquema de prova 19 Mostrar que fAB Provar queé uma função de um conjunto A para um conjunto B Prove que é uma função Prove que dom f A Prove que im Ç B Gráficos de funções Os gráficos constituem uma forma excelente de visualizarmos funções cujas entradas e saídas são números reais Por exemplo a figura a seguir mostra o gráfico da função fx sen x cos 3x Para traçar o gráfico de uma função marcamos um ponto no plano das coordenadas x x para todo x e dom f Formalmente o gráfico de uma função é o conjunto x y y fifx O interessante é que esse conjunto é a função A função f é o conjunto de todos os pares ordenados pcy para os quais y fx Por isso falar a respeito do gráfico de uma função é redundante Isso não é ruim Ao utilizarmos a palavra gráfico nesse contexto estamos formulando uma visão geométrica da função Os gráficos são instrumentos poderosos para entender funções definidas nos reais Para verificar se uma ilustração representa uma função podemos aplicar o teste da reta vertical Qualquer reta vertical no plano só pode interceptar o gráfico de uma função no máximo em 1 um ponto Uma reta vertical não pode cortar o gráfico duas vezes porque então teríamos dois pontos diferentes xyt e xy2 ambos no gráfico da função Isso significaria que tanto x j como xy2 G f comj f y 2 E isso está em desacordo com a definição de função Na matemática discreta estamos especialmente interessados em funções para e de conjuntos finitos ou N ou Z Em tais casos os gráficos tradicionais de funções podem ou não ajudar ou mesmo não ter sentido Por exemplo sejaTIm conjunto finito Podemos considerar a função 2a y N definida porx x Alerta As barras verticais nesse contexto não significam valor absoluto A cada subconjunto x de A a função faz corresponder ao seu tamanho Não há maneira prática de representar este fato como um gráfico em eixos coordenados Temos uma forma alternativa para traçar gráficos de funções f A B em que A e B são conjuntos finitos Sejam A 1234 5 6 e B 1234 5 e consideremos a função AB definida por À 226 Matemática Discreta 12 2 1 32 44 5 5 62 Obtémse uma ilustração de traçandose dois conjuntos de pontos um para A à esquerda e um para B à direita Traçase uma seta de um ponto a A a um ponto b B precisamente quando a b isto é quando yer b Pela figura é fácil vermos que im 1245 Consideremos agora g definida por g 1 3 2 1 24 32 44 5 5 Temos que g é uma função de A 12 3 4 5 6 para B 1 2 3 4 5 Há duas razões pelas quais g A B è falsa Primeiro 6 e A mas 6 dom g Assim dom g yf como se pode ver na figura não há setas partindo do elemento 6 Segundo g não é uma função de um conjunto arbitrário para outro Note que 21 24 g o que viola a Definição 231 A figura também ilustra esse fato há duas setas partindo do elemento 2 S eé uma função de A para B fA B sua figura deve satisfazer o seguinte todo ponto à esquerda em A tem exatamente uma seta partindo dele e terminando à direita em B De maneira inversa podemos contar tabelas De quantas maneiras diferentes podemos substituir os pontos de interrogação na tabela seguinte com elementos de B X y w 1 9 2 a 7 A coluna da direita é uma lista de tamanho o de elementos escolhidos do conjunto de b elementos B Existem ba maneiras de completar a tabela Funções 227 Contagem de funções Sejam A e B conjuntos finitos Quantas funções há de A para B Sem perda de generalidade podemos escolherá como o conjunto 1 2 a e B como o conjunto 1 2 b Toda função f A B pode escreverse como Em que os pontos de interrogação são elementos de B De quantas maneiras podemos substituir os pontos de interrogação com elementos de 5 Há b escolhas para o elemento em 1 e para cada uma dessas escolhas há b escolhas para em 2 etc e por fim b escolhas para o elemento em cr consideradas todas as escolhas anteriores Assim ao todo há ba escolhas Acabamos de mostrar o seguinte Proposição 2310 Sejam A e B conjuntos finitos com A ae B b O número de funções de A para B é ba Exemplo 2311 Sejam 412 3eB4 5 Determine todas as funções f A B Solução A Proposição 2310 afirma que há 23 8 dessas funções São Na Seção 9 introduzimos a notação 2A para o conjunto de todos os subconjuntos de A Essa notação é um artifício mnemónico para lembrar que o número de subconjuntos de um conjunto de a elementos é 2a De forma análoga há uma notação especial para o conjunto de todas as fun ções de A para B A notação é BA Tratase também de um processo mnemónico para a Proposição 2310 pois podemos escrever Neste livro não empregamos essa notação Além disso as pessoas achamna confusa É tenta dor pronunciar o símbolo BA como B elevado a A quando na realidade a notação significa o conjunto de funções de A para B 2 3 a 14 24 34 14 2 4 35 14 2 5 3 4 14 2 5 3 5 15 24 34 15 24 3 5 15 2 5 34 1 5 2 5 3 5 BA BW A notação BA representa o conjunto de todas as funções A B 228 Matemática Discreta Funções inversas Uma função é um tipo especial de relação Recorde que na Seção 13 definimos a inversa de uma relação R denotada por R como a relação formada a partir de R mediante inversão de todos os seus pares ordenados Como uma função é uma relação podemos também considerar1 O problema que suscitamos aqui é se f é uma função de A para B f será uma função de B para A Exemplo 2312 Sejamí 012 34 e B 5 67 8 9 Seja f A B definida por 05 17 2 8 3 9 4 7 de forma que 5 0 7 1 82 93 74 será uma função de B para Al A resposta é não por duas razões Primeira1 não é uma função Note que tanto 7 1 como 7 4 estão em segunda dom 5 7 8 95 Veja a figura No exem plo1 não é uma função Vejamos por quê Consultando a Definição 231 no tamos que para q u e 1 seja uma função deve primeiro ser uma relação Isso não constitui problema comoé uma relação também o é Segundo sempre que a b a c e devemos ter b c Reformulando em termos de f sempre que b d c d e f devemos ter b c Isso é o que estava errado no Exemplo 2312 tínhamos 17 47 e f mas 14 Pictoricamente1 não é uma função porque há duas setas atingindo o elemento 7 à direita Vamos formalizar esta condição como uma definição Definição 2313 Um para um Uma função é chamada um para um se sempre que x b y b devemos ter xy Em outras palavras se x y entãofx fy Funções 229 1 Linguagem matemática A expressão um para um costuma também ser escrita como 11 Outra designação para uma função um para um é injeção ou função injetiva A função do Exemplo 2312 não é um para um porque1 4 mas 1 4 Compare detalhadamente as Definições 2313 um para um e 231 função As condições são bastante semelhantes Proposição 2314 Sejauma função A relação inversa f l é uma função se e somente se f é um para um Deixamos a prova como exercício Exercício 2310 Enquanto trabalha nela prove também o seguinte Proposição 2315 Sejauma função e suponhamos que também seja uma função Então dom im 1 e im d o m 1 Frequentemente queremos provar que uma função é um para um O Esquema de prova 20 dá a estratégia para provar que uma função é um para um Esquema de prova 20 Provar que uma função é um para um Mostrar que é um para um Método direto Suponhamos fxj fy Portanto x y e assimé um para umB Método pela contrapositiva Suponhamos x fy Portantox fy e assim f é um para um Método da contradição Suponhamos x fy mas x f y Portanto é um para um Exemplo 2316 Seja Z Z definida por x 3x 4 Prove que é um para um Prova Suponhamos fx fy Então 3x 4 3y 4 Subtraindo 4 de ambos os membros vem 3x 3y Dividindo ambos os membros por 3 obtemos xy Portantoé um para um Em contrapartida para provar que uma função não é um para um devemos tipicamente apresentar um contraexemplo isto é um par de objetos x e y comx f y mas fx fy I j 230 Matemática Discreta Exemplo 2317 Seja Z Z definida por fx x2 Prove que não é um para um Prova Note que3 3 9 mas 3 3 Portantonão é um para um Linguagem matemática Na linguagem usual a palavra sobre é uma preposição Na linguagem matemática empregase sobre como um adjetivo Outra designação para função sobre é sobrejeção Para que a inversa de uma função também seja uma função é necessário e suficiente que a função seja um para um Consideremos agora uma questão mais focalizada Seja AB Interessanos saber quando f é uma função de B parati Recordemonos de que tivemos duas dificuldades no Exemplo 2312 Superamos a primeira dificuldade deve ser uma função A segunda dificuldade era que havia um elemento em B que não tinha seta de chegada Consideremos a função A B exibida na figura Obviamente é um para um de modo que é uma função Entretanto não é uma função de B para A porque há um elemento b e B para o qual não é definida Para B A deve haver uma seta apontando para cada elemento de B Eis uma forma cuidadosa de enunciar este fato Definição 2318 Sobre SejafA B Dizemos que é sobreB desde que para todo b eB existaumoef de modoa b Em outras palavras im B A sentença f A B é sobre é uma garantia da validade do seguinte primeiroé uma função segundo dom A e terceiro imf B ver o Exercício 237 B Exemplo 2319 Sejam 4 1234 56 e B 78910 e sejam 1 7 2 7 3 8 4 9 5 9 6 10 e g 17 27 3 7 49 59 610 Funções 231 Note que A B é sobre porque para cada elemento b de B podemos achar um ou mais elementos a G A de modoa b É fácil ver também que im B Entretanto g A B não é sobre Note que 8 6 5 mas não há a G A com g a 8 Tam bém im g 79 10 B A condição d e f A B ser sobre se expressa com auxílio dos quantificadores 3 e V como b G B 3a G A fà b A condição de f não ser sobre se expressa como 3b GBWa G A fa b Essas maneiras de encarar as funções sobre são formalizadas no Esquema de prova 21 Esquema de Prova 21 Provar que uma função é sobre Mostrar que f A Bé sobre Método direto Seja b um elemento arbitrário de B Explique como acharconstruir um elemento a GA de modo que a b Portanto é sobre Método dos conjuntos Mostre que os conjuntos B e im são iguais Exemplo 2320 Seja Q Q dada por fx 3x 4 Prove que é sobre Q Prova Seja b Q arbitrário Procuramos um a Q de modoúr b Seja a 5 b4 Como b é um número racional também o é a Note que fa 3 g fi 4 4 ô 4 4 6 Portanto Q Q é sobre Tenha em mente que Q representa o conjunto dos números racionais Como conseguimos adivinhar que deveríamos tomar a b 4 Na realidade não supusemos Trabalhamos em sentido contrário Seja f A B Para que 1 seja uma função é necessário e suficiente que seja um a um Dado isso para que B A é necessário queseja sobre B Caso contrário se não é sobre B podemos achar um b G B de modo f l b não esteja definida Teorema 2321 Sejam os conjuntos A e B e f A B A relação inversaf x é uma função de B para A se e somente se f é um para um e sobre B 232 Matemática Discreta Prova Seja A B Suponhamos que seja um para um e sobre B Devemos provar que f B A Vamos utilizar o Esquema de prova 19 Como f é um para um sabemos pela Proposição 2314 que fx é uma função Como é sobre B im B pela Proposição 2315 dom f l B Como o domínio deé A pela Proposição 2315 im 1 A Portanto1 B A Suponhamos fA B ef B A Como fx é uma funçãoé um para um Propo sição 2314 Como im dom B vemos que é sobre B Uma função que é ao mesmo tempo um para um e sobre tem um nome especial Uma função A 8 que é ao mesmo tempo uma injeção e uma sobrejeção é chamada bijeção Definição 2322 Bijeção Seja A B f é chamada uma bijeção se é ao mesmo tempo um para um e sobre Exemplo 2323 Sejam A o conjunto dos inteiros pares e B o conjunto dos inteiros ímpares A função A B definida por fx x 1 é uma bijeção Prova Devemos provar que é um para um e sobre Para vermos que é um para um suponhamos fx y em quexy são inteiros pares Assim fxfyx 1 y 1 xy Logoé um para um Para vermos que é sobre B seja b e B isto é b é um inteiro ímpar para algum inteiro k Seja a 2kr obviamente a é par Então fa a 1 é sobre Como é um para um e sobreé uma bijeção Por definição b2k1 2k 1 6 de forma que Novamente contagem de funções Sejam A e B conjuntos finitos com A a e S b Quantas funções f A B são um para um Quantas são sobre Consideremos dois casos especiais fáceis Se A 5 então não pode ser um a um Por quê Consideremos a função f A B que esperamos seja um para um Como fé um para um para elementos distintos xy G A fx e fy são elementos distintos de B Assim os primeiros b elementos de A são levados pela em b elementos diferentes de B Após isso não há outros elementos em B aos quais podemos aplicar elementos de 4 Funções 243 247 Ache uma sequência de nove inteiros distintos que não contenha uma subsequência monótona de comprimento quatro Generalize sua construção mostrando como construir para todo inteiro positivo uma sequência de ri2 inteiros distintos que não contenha uma subsequência monótona de comprimento n 1 248 Escreva um programa de computador que tenha como entrada uma sequência de inteiros distintos e como saída o comprimento da mais longa subsequência monótona 249 Seja N Z dada por Prove que é uma bijeção 2410 Denote por E o conjunto dos inteiros pares Ache uma bijeção entre E e Z 25 Composição Assim como há operações por exemplo e x para combinar inteiros e operações para combinar conjuntos por exemplo U e n há uma operação natural para combinar funções Definição 251 Composição de funções Sejam os conjuntos A B e Ce sejam A B e g B C Então a função g o fé uma função de A para C definida por Exemplo 252 Sejam A 1234 5 B 67 89 e C 10111213 14 Sejam f A B e gB C definidas por se n se é par e se n se é impar Sofa gfa em que a e A A função g ofé chamada composição de g ef f 1 6 2 6 3 9 4 7 5 7 g 610 7 11 812 9 13 e Então goféa função 110 2 10 3 13 4 11 5 11 244 Matemática Discreta Por exemplo 2 g 2 g 6 10 Exemplo 253 Seja Z Z dada por 1 e g Z Z dada por gx 2c 3 Quanto é go 4 Calculamosgo4 g4 g 4 2 1g17 2 1 7 3 31 Verafigura De modo geral Funções 245 Alguns comentários Anotação g o significa que primeiro aplicamos e em seguida g Pode parecer estranho que embora calculemos primeiro escrevamos seu símbolo g depois Por quê Quando aplicamos a função gof a um elemento a como em gfà a letra está mais próxima de a e atinge a primeiro g fd g O domínio de g ofé o mesmo que o de domg of dom Para que g o f tenha sentido toda saída de deve ser uma entrada aceitável para g Propriamente dito devemos ter im Ç dom g As exigências f A B e g B C asseguram que as funções se adaptam quando formamos g of Para as funções do Exemplo 252ognão é definida porque g6 10 mas 10 dom f É possível que g e o g tenham ambas sentido sejam definidas Em tal situação pode ocorrer quef o g f g o sejam funções diferentes Exemplo 254 g o fffo g Seja A 12 34 5 6 e sejamA AegAA definidas por 11 21 31 41 51 e g 15 24 33 42 51 Então g o f e f o g são g o f 15 2 5 3 5 4 5 5 5 e f o g 11 21 31 41 51 Assim g o f f f o g Exemplo 255 Recordemos as fiinçõese g do Exemplo 253 fx r2 le gx 2x 3 Para essas funções temos go4 g4g17 31 e fogX4 fg 4 5 26 246 Matemática Discreta Portanto g o f f o g Mais geralmente igfx gfx gx2l 2x2 1 3 2x2 1 e ifogx g x 2 x 3 2x32 1 4jc2 12x 10 Portanto g o o g Assim a composição de funções não satisfaz a propriedade comutativa Verificase entretanto a propriedade associativa Proposição 256 Sejam os conjuntos ABC e e sejam A 5 g B C e h C D Então hogoj h o g o f Essa proposição afirma que duas funções h o g 0J e h o g o f são a mesma função Antes de começarmos a prova façamos tuna pausa Como provamos que duas funções são a mesma função Podemos voltar aos fundamentos e recordar que funções são relações e por sua vez relações são conjuntos de pares ordenados Podemos então seguir o Esquema de prova 5 para mostrar que os conjuntos são iguais Entretanto é mais simples mostrarmos que as duas funções têm o mesmo domínio e que para cada elemento em seu domínio comum geram o mesmo valor Isso implica que os dois conjuntos são o mesmo ver Exercício 252 Esses fatos estão resumidos no Esquema de prova 22 Esquema de prova 22 Provar que duas funções são iguais Sejam as funçõese g Para provar que g devemos fazer o seguinte Provar que dom dom g Provar que para todo x em seu domínio comumyfr gx Passamos agora à prova da Proposição 256 Prova Sejam A y B g B C e h C D Pretendemos provar que hogofhogof Em primeiro lugar verificamos que os domínios de h o g of e de h o g o f coincidem Já havíamos notado que dom g of domf Aplicando esse fato à situação em curso temos Funções 247 domi ogo domg o f dom A e domj o g o f dom A assim ambas as funções têm o mesmo domínio A Em segundo lugar verificamos que para qualquer a 6 A as duas funções geram o mesmo Seja a A arbitrário Calculamos hgfa hg ofa hgfa e hogofà hogfa h g f a l Logo h o g o f h o g o f A função identidade O inteiro 1 é o elemento identidade para a multiplicação e 0 é o elemento identidade para a união Qual é o elemento identidade para a composição Não existe um elemento único ao contrário há diversos Definição 257 Função identidade Seja A um conjunto A Junção identidade emAé a função id cujo domínio éA e para todo a GA idA a a Em outras palavras idA a d a e A A razão por que chamamos id função identidade é a seguinte Proposição 258 Sejam os conjuntos A q B e consideremos a função fA B Então foidA idBo f f ProvaDevemos mostrar que as funções o idx idfl o esão todas a mesma função Recorre mos ao Esquema de prova 22 Consideremos o id e f Temos domd id dom idA A dom assim elas têm o mesmo domínio Seja a 6 A Calculamos 248 Matemática Discreta f ida ida já de forma que foidAe f dão o mesmo valor qualquer que seja a 6 A Portanto o id O argumento que iàB offé praticamente o mesmo ver Exercício 255 Tal como a multiplicação de um número racional por seu inverso dá 1 a composição de uma função com sua inversa dá uma função identidade Proposição 259 Sejam os conjuntos AeB e suponhamos que f A B seja um para um e sobre Então o l ids e l o id Prove essa proposição Exercício 256 Recapitulando Nesta seção vamos estudar a composição de funções e as funções identidade 25 Exercícios 251 Listamos a seguir vários pares de funções feg Para cada par Determine qual das duas é definida gofoufog Se uma ou ambas forem definidas ache as funçãoões resultantes Se ambas forem definidas determine se g offo g ou não a 12 23 34 eg 21 31 41 b 1 2 2 3 34 e g 2 1 3 2 4 3 c 1 2 2 3 34 e g 12 2 0 3 5 4 3 d 14 24 3 3 4 1 eg 1 1 2 1 3 4 44 e 1 2 2 3 34 4 5 5 1 e g 1 3 24 3 5 41 52 f fx x2 1 e gx x2 1 ambos para todo x e Z g x x 3 egxx7 ambos para todo x Z h x 1 x e gx 2 x ambos para todo x e Q fxx paraxG Q exceto x 0 e gx x 1 para todo x e Q j idAeg id5quandoA C B masAB 252 Considere as funções feg Prove que g como conjuntos se e somente se dom dom g e para todo x em seu domínio comumxgx Isso justifica o Esquema de prova 22 253 Dados os conjuntos AeB prove que A B se e somente se id idfl 254 Qual é a diferença entre a função identidade definida em um conjunto A ea relação é igual a definida em A 255 Complete a prova da Proposição 258 Funções 249 256 Prove a Proposição 259 257 Sejam A e B conjuntos e e g funções com f A B o g B A Prove Se g o f id e o g idB então é invertível e g Nota Esse resultado é uma recíproca da Proposição 259 258 Seja f A B uma bijeção Explique por que as seguintes igualdades são incorretas id e f o idfi 259 Sejam os conjuntos A B e C ef A B e g B C Prove a See g são um para um também oégof b See g são sobre g o f também é sobre c See g são bijeções também oégof 2510 Determine um par de funçõeseg do conjunto A para si mesmo de modo f g g f Qualquer um dos casos a seguir serve Escolhaf e g como a mesma função Escolhaou g como idr Escolha g 1 Estes são muito fáceis Ache outro exemplo 2511 Sejam A um conjunto e uma função com f A A a Suponha que seja um para um Deve ser sobre b Suponha que seja sobre Deve ser um para um Justifique sua resposta 2512 Suponha que f A A e g A A sejam ambas bijeções Prove ou refute a g o f ê uma bijeção de A para si mesmo b g of gof c g o f f o g 2513 Sejam A um conjunto e f A A Entãoof é também uma função de A para si mesmo também o éfo fo f Representemos porn a composição de ordem n deconsigo mesma isto é n o o o n vezes Naturalmente1 Note que11 não significa fx Por exemplo sex 1 então21x ffx x 1 l i L 2 2 1 4X SS0 n 0 mesmo 9ue lMl2 Í2X 2 X2 X 1 a Estabeleça um significado aceitável para0 b S e f g A A devemos ter g o ff g2 o2 Prove ou refute c Seé invertível deve ser ffi fwf rl Prove ou refute A melhor maneira de responder às questões a seguir é com o auxílio de um computador d Seja R K definida por fx 28xl x Considere a sequência de valores f C22 32 4