Atividade Matemática Discreta

5 Exercícios do Grupo 5 Exercício 51 33 pontos Demonstre por demonstração direta que para todo conjunto XY X Yc X Y Exercício 52 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto XYZ Z Y X X Y Z Y X Exercício 53 33 pontos Demonstre por contradição e por casos que para todo conjunto XY Y Yc Yc Xc 5 Exercícios do Grupo 5 Exercício 51 34 pontos Demonstre que para todo x 1 3 6 9 3x 3xx 12 Exercício 52 33 pontos Demonstre que para todo x 1 i1x i6i 5 xx 14x 72 Exercício 53 33 pontos Seja p1 p2 p3 uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo x 2 p x p x1 6x 1 Condição inicial p1 7 Use o método da iteração para achar uma fórmula explícita para esta sequência Demonstre que a fórmula explícita encontrada está correta Pode ser que seja necessário utilizar uma das seguintes duas asserções para resolver o terceiro exercício Para todo x 1 1 2 3 x xx12 Para todo x R 1 para todo y 0 1 x x2 xy xy1 1x 1 Exercícios de Teoria dos Conjuntos Exercício 51 Para provar que um conjunto está contido em outro devemos mostrar que qualquer elemento do primeiro conjunto também pertence ao segundo Seja a um elemento particular e arbitrário tal que a X Yᶜ 1 Pela definição de interseção de conjuntos se a X Y então temos que ᶜ a X e a Yᶜ 2 Pela definição de conjunto complementar se a Yᶜ isso significa que a Y 3 Combinando as duas condições temos que a X e a Y 4 Pela definição de diferença de conjuntos se um elemento pertence a X e não pertence a Y então ele pertence à diferença X Y Logo a X Y Portanto para qualquer elemento a se a X Y então ᶜ a X Y Pela definição de subconjunto podemos concluir que X Yc X Y QED Exercício 52 Utilizaremos uma demonstração direta por elemento dividida em casos Seja a um elemento particular e arbitrário tal que a Z Y X X Y 1 Pela definição de interseção temos que a Z e também que a Y X X Y 2 Pela definição de união se a Y X X Y então temos duas possibilidades casos o Caso 1 a Y X o Caso 2 a X Y Analisemos cada caso para provar que o elemento a pertence a Z Y X Caso 1 a Y X 1 Pela definição de diferença temos que a Y e a X 2 Da nossa premissa inicial já sabemos que a Z 3 Reunindo as informações temos que a Z e a Y 4 Pela definição de interseção isso implica que a Z Y 5 Pela definição de união se um elemento pertence a Z Y ele certamente pertencerá a qualquer união que inclua esse conjunto Portanto a Z Y X Caso 2 a X Y 1 Pela definição de diferença temos que a X e a Y 2 Pela definição de união se a X então ele certamente pertencerá a qualquer união que inclua o conjunto X Portanto a Z Y X Em ambos os casos demonstramos que se o elemento a pertence ao conjunto da esquerda ele também deve pertencer ao conjunto da direita Logo pela definição de subconjunto Z Y X X Y Z Y X QED Exercício 53 Faremos uma prova por contradição 1 Suposição Vamos supor por contradição que a proposição é falsa Ou seja supomos que Y Y ᶜ Y X ᶜ ᶜ 2 Consequência da Suposição Se Y não está contido no outro conjunto então existe pelo menos um elemento a tal que a Y e ao mesmo tempo a Y ᶜ Y X ᶜ ᶜ 3 Análise da Suposição o Pela definição de conjunto complementar se a Z então ᶜ a Z o Aplicando isso à nossa suposição se a Y ᶜ Y X então ᶜ ᶜ a Yᶜ Y X ᶜ 4 Busca pela Contradição Análise por Casos o Neste ponto temos duas informações sobre a a Y da premissa e a Y ᶜ Y X ᶜ da consequência o Pela definição de união se a Y ᶜ Y X então temos dois casos ᶜ possíveis Caso 1 a Yᶜ o Pela definição de complemento se a Y então ᶜ a Y o Isso cria uma contradição pois nossa premissa afirma que a Y Caso 2 a Y X ᶜ o Pela definição de diferença se a Y X então ᶜ a Yᶜ e a X o A condição a Yᶜ significa que a Y o Isso novamente cria uma contradição pois nossa premissa afirma que a Y Em ambos os casos possíveis chegamos a uma contradição lógica Portanto a suposição inicial de que a proposição era falsa deve ser ela mesma falsa Logo a proposição original é verdadeira Y Yc Yc X c QED Exercícios de Sequências Somatórios e Produtórios Exercício 51 Seja Px a proposição i1x3i3xx12i1x3i23xx1 PB Passo Base Temos que demonstrar que P1 é verdadeira Lado Esquerdo sumi11 3i 31 3 Lado Direito frac31112 frac3 cdot 22 3 Como os dois lados são iguais P1 é verdadeira PI Passo Indutivo Temos que demonstrar que para todo k 1 se Pk é verdadeira então Pk1 também é verdadeira Hipótese de Indução HI Seja k 1 um elemento particular e arbitrário tal que Pk é verdadeira i1k3i3kk12i1k3i23kk1 Objetivo Demonstrar que Pk1 é verdadeira i1k13i3k1k1123k1k22i1k13i23k1k1123k1 k2 Demonstração Começamos com o lado esquerdo da equação do objetivo e o expandimos i1k13ii1k3i3k1Pela definicao recursiva de somato rio ˊ i1k1 3ii1k3i3k1Pela definicao recursiva de somato rio ˊ Agora aplicamos a Hipótese de Indução HI 3kk123k1Pela HI23kk13k1Pela HI Para somar os termos encontramos um denominador comum 3kk123k1223kk123k1 Fatoramos o termo comum 3k1 3k1k2223k1k2 A expressão final é idêntica ao nosso objetivo Portanto para todo x 1 a proposição Px é verdadeira QED Exercício 52 33 pontos Demonstre que para todo x 1 i1xi6i5xx14x72i1xi6i52xx14x7 Demonstração por Indução Matemática Seja Px a proposição i1xi6i5xx14x72i1xi6i52xx14x7 PB Passo Base Temos que demonstrar que P1 é verdadeira Lado Esquerdo sumi11 i6i5 16 cdot 1 5 111 11 Lado Direito frac1114 cdot 1 72 frac1 cdot 2 cdot 112 11 Como os dois lados são iguais P1 é verdadeira PI Passo Indutivo Temos que demonstrar que para todo k 1 se Pk é verdadeira então Pk1 também é verdadeira Hipótese de Indução HI Seja k 1 um elemento particular e arbitrário tal que Pk é verdadeira i1ki6i5kk14k72i1ki6i52kk14k7 Objetivo Demonstrar que Pk1 é verdadeira i1k1i6i5k1k114k172k1k24k112i1k1 i6i52k1k114k172k1k24k11 Demonstração i1k1i6i5i1ki6i5k16k15Definicao recursiva de somato rio ˊ i1k1i6i5i1ki6i5k16k15Definicao recursiva de somato rio ˊ kk14k72k16k11Pela HI2kk14k7k16k11Pela HI kk14k72k16k112Denominador comum2kk14k72k16k11 Denominador comum k1k4k726k112Fatorando k12k1k4k726k11Fatorando k 1 k14k27k12k222Expandindo a expressao interna2k14k27k12k22 Expandindo a expressao interna k14k219k2222k14k219k22 k1k24k112Fatorando o polinoˆmio quadra tico2 ˊ k1k24k11 Fatorando o polinoˆmio quadra tico ˊ A expressão final é idêntica ao nosso objetivo Portanto para todo x 1 a proposição Px é verdadeira QED Exercício 53 33 pontos Seja p p p uma sequência definida recursivamente da seguinte forma ₁ ₂ ₃ Relação de recorrência Para todo x 2 pxpx16x1pxpx16x1 Condição inicial p17p17 Use o método da iteração para achar uma fórmula explícita para esta sequência Demonstre que a fórmula explícita encontrada está correta 1 Encontrando a Fórmula Explícita Método da Iteração Vamos expandir a recorrência para encontrar um padrão px px1 6x 1 px px2 6x1 1 6x 1 px2 6x 6x1 2 px px3 6x2 1 6x 6x1 2 px3 6x 6x1 6x2 3 O padrão geral ao expandir até p1p1 é pxp1i2x6i1pxp1i2x6i1 Podemos reescrever a soma para começar em i1 pxp1i1x6i1611pxp1i1x6i1611 Substituindo p17p17 px7i1x6ii1x15px7i1x6ii1x15 px26i1xii1x1px26i1xii1x1 Usando a fórmula da soma dos primeiros x inteiros sum i fracxx12 e sabendo que sum 1 x px26xx12xpx262xx1x px23xx1xpx23xx1x px23x23xxpx23x23xx px3x22x2px3x22x2 Esta é a nossa fórmula explícita candidata 2 Demonstração da Correção da Fórmula por Indução Matemática Seja Px a proposição px 3x2 2x 2 PB Passo Base Para x 1 a fórmula nos dá p1 312 21 2 3 2 2 7 Issocorrespondea condiccaoinicialdada ˋ Issocorrespondeaˋcondiccaoinicialdada p1 7 P1 é verdadeira PI Passo Indutivo Temos que demonstrar que para todo k 1 se Pk é verdadeira então Pk1 também é verdadeira Hipótese de Indução HI Seja k 1 um elemento particular e arbitrário tal que pk 3k2 2k 2 Objetivo Demonstrar que pk1 3k12 2k1 2 Expandindo o objetivo para simplificar pk1 3k2 2k 1 2k 2 2 3k2 6k 3 2k 4 3k2 8k 7 Demonstração Usamos a definição da recorrência para pk1pk1 pk1pk6k11pk1pk6k11 Substituímos pkpk usando nossa Hipótese de Indução pk13k22k26k11pk13k22k26k11 pk13k22k26k61pk13k22k26k61 pk13k22k6k261pk13k22k6k261 pk13k28k7pk13k28k7 Este resultado é idêntico ao nosso objetivo Portanto a fórmula explícita px 3x2 2x 2 está correta para todo x 1 QED