6 Questões de Matematica Discreta

Matemática Discreta Teoria dos Conjuntos Primeiro exemplo de demonstração direta Demonstremos que para todo conjunto X Y X Y X Demonstração Sejam A e B dois conjuntos particulares e arbitrários Seja k U um elemento particular e arbitrário tal que k A B Logo pela def de interseção podemos conduzir que k A e k B Portanto para todo z U se z A B então z A k A e B z X Y z X e z Y para todo z U se z A B então z A Objetivo A B A Logo pela def de subconjunto podemos deduzir que A B A Portanto para todo conjunto X Y X Y X QED Matemática Discreta Avaliação da Segunda Unidade do semestre 20251 prof Claudio Callejas 1 Exercícios do Grupo 1 Exercício 11 34 pontos Demonstre que para todo x 0 1473x1 x13x22 Exercício 12 33 pontos Demonstre que para todo x 0 3i 3x1 12 i0 x Exercício 13 33 pontos Seja p1 p2 p3 uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo x 2 px px1 3x 1 Condição inicial p1 2 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 ℝ 1 para todo y 0 1 x x2 xy xy1 1x1 Exercícios do Grupo 2 Exercício 21 34 pontos Demonstre que para todo x 0 27125x2 x15x42 Exercício 22 33 pontos Demonstre que para todo x 1 i5i3 xx15x23 i1 x Exercício 23 33 pontos Seja p1 p2 p3 uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo x 2 px px1 3x 2 Condição inicial p1 1 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 123x xx12 Para todo x ℝ 1 para todo y 0 1 x x2 xy xy1 1x1 3 Exercícios do Grupo 3 Exercício 31 34 pontos Demonstre que para todo x 0 3 5 7 2x 3 x 12x 62 Exercício 32 33 pontos Demonstre que para todo x 1 i3i 4 xx 12x 52 i1 Exercício 33 33 pontos Seja p1 p2 p3 uma sequência definida recursi vamente da seguinte forma Relação de recorrência Para todo x 2 pₓ pₓ₁ 4x 2 Condição inicial p₁ 3 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 assertivas para resolver o terceiro exercício Para todo x 1 1 2 3 x xx12 Para todo x ℝ 1 para todo y 0 1 x x² xʸ xy1 1x1 4 Exercícios do Grupo 4 Exercício 41 34 pontos Demonstre que para todo x 0 7 11 15 4x 7 x 12x 7 Exercício 42 33 pontos Demonstre que para todo x 1 i1 to x i7i 2 xx 114x 136 Exercício 43 33 pontos Seja p₁ p₂ p₃ uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo x 2 pₓ pₓ₁ 4x 2 Condição inicial p₁ 3 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 assertivas para resolver o terceiro exercício Para todo x 1 1 2 3 x xx12 Para todo x ℝ 1 para todo y 0 1 x x² xʸ xy1 1x1 Relação de recorrência Para todo x 2 pₓ pₓ₁ 4x 5 Condição inicial p₁ 1 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 assertivas para resolver o terceiro exercício Para todo x 1 1 2 3 x xx12 Para todo x ℝ 1 para todo y 0 1 x x² xʸ xy1 1x1 4 Exercícios do Grupo 4 Exercício 41 34 pontos Demonstre que para todo x 0 7 11 15 4x 7 x 12x 7 Exercício 42 33 pontos Demonstre que para todo x 1 i1 to x i7i 2 xx 114x 136 Exercício 43 33 pontos Seja p₁ p₂ p₃ uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo x 2 pₓ pₓ₁ 4x 2 Condição inicial p₁ 3 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 assertivas para resolver o terceiro exercício Para todo x 1 1 2 3 x xx12 Para todo x ℝ 1 para todo y 0 1 x x² xʸ xy1 1x1 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 i1 to x i6i 5 xx 14x 72 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 pₓ pₓ₁ 6x 1 Condição inicial p₁ 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 assertivas para resolver o terceiro exercício Para todo x 1 1 2 3 x xx12 Para todo x ℝ 1 para todo y 0 1 x x² xʸ xy1 1x1 6 Exercícios do Grupo 6 Exercício 61 34 pontos Demonstre que para todo x 0 1 7 13 6x 1 x 13x 1 Exercício 62 33 pontos Demonstre que para todo x 0 i0 to x 7ⁱ 7x116 Exercício 63 33 pontos Seja p₁ p₂ p₃ uma sequência definida recursivamente da seguinte forma 8 Exercícios do Grupo 8 Exercício 81 34 pontos Demonstre que para todo x 0 4 11 18 7x 4 x17x82 Exercício 82 33 pontos Demonstre que para todo x 1 i1 to x i8i 5 xx116x 76 Exercício 83 33 pontos Seja p1 p2 p3 uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo x 2 px px1 2x 9 Condição inicial p1 4 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 ℝ 1 para todo y 0 1 x x2 xy xy1 1x 1 9 Exercícios do Grupo 9 Exercício 91 34 pontos Demonstre que para todo x 1 3 14 33 x4x 1 xx18x16 Exercício 92 33 pontos Demonstre que para todo x 0 i0 to x 3i 1 x13x22 Exercício 93 33 pontos Seja p1 p2 p3 uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo x 2 px px1 7x 1 Condição inicial p1 8 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 ℝ 1 para todo y 0 1 x x2 xy xy1 1x 1 10 Exercícios do Grupo 10 Exercício 101 34 pontos Demonstre que para todo x 0 5 13 21 8x 5 x14x5 Exercício 102 33 pontos Demonstre que para todo x 1 i1 to x i4i 1 xx18x16 Exercício 103 33 pontos Seja p1 p2 p3 uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo x 2 px px1 7x 3 Condição inicial p1 2 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 ℝ 1 para todo y 0 1 x x2 xy xy1 1x 1 11 Exercícios do Grupo 11 Exercício 111 34 pontos Demonstre que para todo x 1 2 14 36 x5x 3 xx15x 23 Exercício 112 33 pontos Demonstre que para todo x 0 i0 to x 4i 7 x 12x 7 Exercício 113 33 pontos Seja p1 p2 p3 uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo x 2 px px1 7x 3 Condição inicial p1 3 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 ℝ 1 para todo y 0 1 x x2 xy xy1 1x 1 12 Exercícios do Grupo 12 Exercício 121 34 pontos Demonstre que para todo x 0 1 7 72 7x 7x1 16 Exercício 122 33 pontos Demonstre que para todo x 1 i1 to x 3i 3xx 12 Exercício 123 33 pontos Seja p1 p2 p3 uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo x 2 pₓ pₓ₁ 10x 2 Condição inicial p₁ 1 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 x² xʸ xy1 1x1 13 Exercícios do Grupo 13 Exercício 131 34 pontos Demonstre que para todo x 1 7 20 39 x3x 4 xx 12x 52 Exercício 132 33 pontos Demonstre que para todo x 0 ₙᵢ₀ˣ7i 4 x 17x 82 Exercício 133 33 pontos Seja p₁ p₂ p₃ uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo x 2 pₓ pₓ₁ 10x 3 Condição inicial p₁ 6 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 x² xʸ xy1 1x1 14 Exercícios do Grupo 14 Exercício 141 34 pontos Demonstre que para todo x 1 9 32 69 x7x 2 xx 114x 136 Exercício 142 33 pontos Demonstre que para todo x 0 ₙᵢ₀ˣ6i 1 x 13x 1 Exercício 143 33 pontos Seja p₁ p₂ p₃ uma sequência definida recursivamente da seguinte forma Relação de recorrência Para todo x 2 pₓ pₓ₁ 5x 4 Condição inicial p₁ 10 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 x² xʸ xy1 1x1 15 Exercícios do Grupo 15 Exercício 151 34 pontos Demonstre que para todo x 0 1 3 3² 3ˣ 3x1 12 Exercício 152 33 pontos Demonstre que para todo x 0 ₙᵢ₀ˣ2i 3 x 12x 62 Exercício 153 33 pontos Seja p₁ p₂ p₃ uma sequência definida recur sivamente da seguinte forma Relacao de recorrˆencia Para todo x 2 px px1 4x 3 Condicao inicial p1 3 Use o metodo da iteracao para achar uma formula explıcita para esta sequˆencia Demonstre que a formula explıcita encontrada esta correta Pode ser que seja necessario utilizar uma das seguintes duas assercoes para resolver o terceiro exercıcio Para todo x 1 1 2 3 x xx1 2 Para todo x R 1 para todo y 0 1 x x2 xy xy11 x1 11 Matemática Discreta Teoria dos Conjuntos Exemplos de demonstração direta 1 Demonstremos que para todo conjunto X Y Z X Y U Z X Y X Z Demonstração Sejam A B e C três conjuntos particulares e arbitrários E seja x U um elemento particular e arbitrário tal que x A BC Logo pela definição de diferen ça de conjuntos sabemos que x A e x BC Logo pela definição de união de conjuntos dedu zimos que x B e x C Por x A e x B e x C e pela definição de diferença de conjuntos temos como consequência que x A B e x A C Disto segue pela definição de interseção de conjuntos que x A B A C Portanto para todo w U se w A B C então w A B A C Logo pela definição de subconjunto podemos concluir que A BC A B A C w X U Y w X e w Y w X Y w X e w Y w X Y w X e w Y A BC A B A C A BC A B A C x y w U w X w Y A B A C A B A C A BC A BC x y x y e y x A B A C A BC A B A C A BC x A B x A C k A B e k B k A C k A B A C k A B e k A C k A B A C para todo w U se w A BC então w A B A C A BC A B A C A B A C A BC Objetivo A B C A B A C 2 seja l U um elemento particular e arbitrário tal que l A B A C Logo pela definição de interseção de conjuntos sabemos que l A B e l A C De l A B e pela definição de diferença de conjuntos segue que l A e l B Por l A C e pela definição de diferença de conjuntos podemos concluir que l A e l C Por l B e l C e pela definição de união temos como consequência que l BC De l A e l BC e pela definição de diferença de conjuntos podemos derivar que l A BC Portanto para todo w U se w A B A C então w A BC Logo pela definição de subconjunto sabemos que A B A C A BC l B e l C l A e l B l A B C para todo w U se w A B A C então w A B C Objetivo Parcial A B A C A B C Por A B C A B A C e A B A C A B C e pela definição de igualdade de conjuntos se desprende que A BC A B A C Portanto para todo conjunto X Y Z X YZ X Y X Z QED Matemática Discreta Teoria dos Conjuntos Exemplos de demonstração direta 1 Demonstre que para todo conjunto X Y Z se XY e YZ então XZ Demonstração Sejam A B e C três conjuntos particulares e arbitrários tal que AB e BC Seja kU um elemento particular e arbitrário tal que kA Logo por AB e pela definição de subconjunto podemos concluir que kB Por kB e BC e pela definição de subconjunto deduzimos que kC Portanto para todo uU se uA então uC Logo pela definição de subconjunto podemos afirmar que AC Portanto para todo conjunto X Y Z se XY e YZ então XZ QED 2 Demonstremos que para todo conjunto W X Y Z se WX e YZ então WY XZ Demonstração Sejam A B C e D quatro conjuntos particulares e arbitrários tal que AB e CD Seja kU um elemento particular e arbitrário tal que kAC Logo pela definição de intersecção podemos concluir que kA e kC Por kA e AB e pela definição de subconjunto deduzimos que kB De kC e CD e pela definição de subconjunto segue que kD Por kB e kD e pela definição de intersecção se desprende que kBD Portanto para todo vU se vAC então vBD Logo pela definição de subconjunto podemos derivar que AC BD Portanto para todo conjunto W X Y Z se WX e YZ então WY XZ QED Matemática Discreta Sequências Somatórios e Produtos Fórmula fechada Demonstremos que para todo x1 1²2²3²x² xx12x16 Demonstração PB Temos que demonstrar que 1² 1112116 Temos que 1112116 1236 1 1² Portanto 1² 1112116 PI Temos que demonstrar que para todo y1 se 1²2²3²y² yy12y16 então 1²2²3²y1² y1y112y116 Seja kN₀ um elemento particular e arbitrário tal que 1²2²3²k² kk12k16 onde k1 Temos que 1²2²3²k1² 1²2²3²k²k1² Pela ordem dos naturais kk12k16 k1² Pela HI e por substituição k1k2k16k16 k12k²k6k66 k12k²3k4k66 k1k22k36 k1k112k116 Objetivo 1²2²3²k1² k1k112k116 Portanto para todo y1 se 1²2²3²y² yy12y16 então 1²2²3²y1² y1y112y116 Portanto para todo x1 1²2²3²x² xx12x16 QED Matemática Discreta Avaliação da Terceira Unidade do semestre 20251 prof Claudio Callejas 1 Exercícios do Grupo 1 Exercício 11 33 pontos Demonstre por demonstração direta que para todo conjunto X Y X Yc Xc Yc Exercício 12 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto X Y Z Z Y X Z Y X Exercício 13 33 pontos Demonstre por contradição que para todo conjunto X Y X Y X Y 2 Exercícios do Grupo 2 Exercício 21 33 pontos Demonstre por demonstração direta que para todo conjunto X Y X Y X Yc Exercício 22 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto X Y Z Z Y X Z Y Y Z X Exercício 23 33 pontos Demonstre por contradição e por casos que para todo conjunto X Y Xc Yc Xc X 3 Exercícios do Grupo 3 Exercício 31 33 pontos Demonstre por demonstração direta que para todo conjunto X Y X Y X X Y Exercício 32 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto X Y Z Z Y X Z Y X Exercício 33 33 pontos Demonstre por contradição e por casos que para todo conjunto X Y X Yc Xc Yc 4 Exercícios do Grupo 4 Exercício 41 33 pontos Demonstre por demonstração direta que para todo conjunto X Y Z X Y Z X Y Z Exercício 42 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto X Y Z X Y Z Y X X Y Z Exercício 43 33 pontos Demonstre por contradição e por casos que para todo conjunto X Y X Y X Yc 5 Exercícios do Grupo 5 Exercício 51 33 pontos Demonstre por demonstração direta que para todo conjunto X Y X Yc X Y Exercício 52 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto X Y Z Z Y X X Y Z Y X Exercício 53 33 pontos Demonstre por contradição e por casos que para todo conjunto X Y Y Yc Yc Xc 6 Exercícios do Grupo 6 Exercício 61 33 pontos Demonstre por demonstração direta que para todo conjunto X Y X Y X X Y Exercício 62 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto X Y Z Y X Z Y X Z Exercício 63 33 pontos Demonstre por contradição e por casos que para todo conjunto X Y Xc Yc X Yc 7 Exercícios do Grupo 7 Exercício 71 33 pontos Demonstre por demonstração direta que para todo conjunto X Y Z X Y Z X Y Z Exercício 72 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto X Y Z X Z Y X Z Z X Y Exercício 73 33 pontos Demonstre por contradição e por casos que para todo conjunto X Y X Yc Xc Yc 8 Exercícios do Grupo 8 Exercício 81 33 pontos Demonstre por demonstração direta que para todo conjunto XY Xc Yc X Yc Exercício 82 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto XYZ Y Z X Y Z Z Y X Exercício 83 33 pontos Demonstre por contradição e por casos que para todo conjunto XY X Xc Xc Yc 9 Exercícios do Grupo 9 Exercício 91 33 pontos Demonstre por demonstração direta que para todo conjunto XY Y Yc Yc Xc Exercício 92 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto XYZ X Y Z X Y Z Exercício 93 33 pontos Demonstre por contradição e por casos que para todo conjunto XY Xc Yc X Yc 10 Exercícios do Grupo 10 Exercício 101 33 pontos Demonstre por demonstração direta que para todo conjunto XY X Y X X Y Exercício 102 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto XYZ Y Z X Y Z X Exercício 103 33 pontos Demonstre por contradição e por casos que para todo conjunto XY X X X Y 11 Exercícios do Grupo 11 Exercício 111 33 pontos Demonstre por demonstração direta que para todo conjunto XYZ X Y Z X Y Z Exercício 112 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto XYZ Z X Y Z X Y Exercício 113 33 pontos Demonstre por contradição e por casos que para todo conjunto XY X Yc X Y 12 Exercícios do Grupo 12 Exercício 121 33 pontos Demonstre por demonstração direta que para todo conjunto XY X Xc Xc Yc Exercício 122 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto XYZ X Z Y X Z Y Exercício 123 33 pontos Demonstre por contradição e por casos que para todo conjunto XY X X Y X 13 Exercícios do Grupo 13 Exercício 131 33 pontos Demonstre por demonstração direta que para todo conjunto XYZ X Y X Y Y Z Exercício 132 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto XYZ Z X Y Z X X Z Y Exercício 133 33 pontos Demonstre por contradição e por casos que para todo conjunto XY X Y X X Y 14 Exercícios do Grupo 14 Exercício 141 33 pontos Demonstre por demonstração direta que para todo conjunto XYZ X Y Z X Y Z Exercício 142 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto XYZ Z X Y Y X Z X Y Exercício 143 33 pontos Demonstre por contradição e por casos que para todo conjunto XY X Y X X Y 15 Exercícios do Grupo 15 Exercício 151 33 pontos Demonstre por demonstração direta que para todo conjunto XY X Y X X Y Exercicio 152 34 pontos Demonstre por demonstração direta e por casos que para todo conjunto X Y Z Y X Z Y X X Y Z Exercicio 153 33 pontos Demonstre por contradição e por casos que para todo conjunto X Y X Y X Y X Matemática Discreta Teoria dos Conjuntos Exemplo de demonstração direta e por casos Demonstremos que para todo conjunto X Y X Yc Xc Yc Demonstração Sejam A e B dois conjuntos particulares e arbitrários 1 Seja k U um elemento particular e arbitrário tal que k A Bc Disto segue pela definição de complemento de conjunto que k A B Logo pela definição de interseção podemos concluir que k A ou k B Caso k A Logo pela definição de complemento deduzimos que k Ac Por k Ac e pela definição de união temos que k Ac Bc Caso k B De k B e pela definição de complemento segue que k Bc Logo pela definição de união sabemos que k Ac Bc Portanto para todo z U se z A Bc então z Ac Bc Logo pela definição de subconjunto podemos concluir que A Bc Ac Bc A Bc Ac Bc X Y X Y e Y X z X Y z X ou z Y z X Y z X e z Y z Xc z X z U z X ou z Y X Y z U z X z Y 2 Seja l U um elemento particular e arbitrário tal que l Ac Bc Logo pela definição de união sabemos que l Ac ou l Bc Caso l Ac Disto segue pela definição de complemento que l A Por l A e pela definição de interseção temos como consequência que l A B De l A B e pela definição de complemento segue que l A Bc Caso l Bc Logo pela definição de complemento temos que l B Consequentemente pela definição de interseção temos que l A B Por l A B e pela definição de complemento podemos afirmar que l A Bc Portanto para todo z U se z Ac Bc então z A Bc Logo pela definição de subconjunto podemos concluir que Ac Bc A Bc l A ou l B A B l A Bc para todo z U se z Ac Bc então z A Bc Objetivo parcial Ac Bc A Bc Por A Bc Ac Bc e Ac Bc A Bc e pela definição de igualdade de conjuntos podemos concluir que A Bc Ac Bc Portanto para todo conjunto X Y X Yc Xc Yc QED Matemática Discreta Teoria dos Conjuntos Exemplo de demonstração direta e por casos Demonstremos que para todo conjunto X Y XXY XY Demonstração Sejam A e B dois conjuntos particulares e arbitrários 1 Seja k U um elemento particular e arbitrário tal que k A A B Logo pela definição de diferença de conjuntos sabemos que k A e k A B Por k A B e pela definição de diferença podemos concluir que k A ou k B Caso k A Isto contradiz k A Caso k B Por k A e k B e pela definição de interseção podemos deduzir que k A B Portanto para todo z U se z A A B então z A B Logo pela definição de subconjunto podemos concluir que A A B A B z X Y z X ou z Y z X Y z X e z Y z X Y z X e z Y X Y z U z X z Y X Y X Y e Y X k A e k B para todo z U se z A A B então z A B A A B A B 2 Seja l U um elemento particular e arbitrário tal que l A B Disto podemos concluir pela definição de interseção que l A e l B Por l B e pela definição de diferença de conjuntos temos que l A B De l A e l A B e pela definição de diferença de conjuntos segue que l A A B Portanto para todo z U se z A B então z A A B Logo pela definição de subconjunto temos que A B A A B l A ou l B l A A B para todo z U se z A B então z A A B Objetivo parcial A B A A B Por A A B A B e A B A A B e pela definição de igualdade de conjuntos temos que A A B A B Portanto para todo conjunto X Y XXY X Y QED Matematica Discreta Teoria dos Conjuntos Exemplos de demonstração direta e por casos 1 Demonstremos que para todo conjunto XYZ se X C Z e Y C Z então XUY C Z Demonstração Sejam ABC três conjuntos particulares e arbitrários tal que A C C e B C C Seja k E U um elemento particular e arbitrário tal que k E AUB Logo pela def de união sabemos queou k E A ou k E B w E XUY w E X ou w E Y X C Y w E X w E Y X AUB Y C Caso k E A Logo por A C C e pela def de subconjunto podemos concluir que k E C Caso k E B Por k E B e B C C e pela def de subconjunto se desprende que k E C Portanto para todo w E U se w E AUB então w E C Logo pela def de subconjunto deduzimos que AUB C C Portanto para todo conjunto XYZ se X C Z e Y C Z então XUY C Z 2 Demonstremos que para todo conjunto WXYZ se W C X e Y C Z então WUY C XUZ Demonstração Sejam ABCD quatro conjuntos particulares e arbitrários tal que A C B e C C D Seja k E U um elemento particular e arbitrário tal que k E AUC Por k E AUC e pela def de união podemos concluir que k E A ou k E C w E XUY w E X ou w E Y X C Y w E X w E Y X AUC Y BUD Caso k E A De k E A e A C B e pela def de subconjunto se desprende que k E BUD Caso k E C Logo por C C D e pela def de subconjunto continuamos que k E D De k E D e pela def de união segue que k E BUD Portanto para todo v E U se v E AUC então v E BUD Logo pela def de subconjunto podemos deduzir que AUC BUD Portanto para todo conjunto WXYZ se W C X e Y C Z então WUY C XUZ QED 3 Demonstremos que para todo conjunto XYZ se XNY C Z e XCNY C Z então Y C Z Demonstração Sejam ABC três conjuntos particulares e arbitrários tal que ANB C c e ANB C c Seja k E U um elemento particular e arbitrário tal que k E B Caso k E A Por k E A e k E B e pella def de intersefção concluimos que k E ANB Logo por ANB C C e pela def de subconjunto temos que k E C Caso k ĂL Logo pela def de complemento sabemos que k E Ac De k E Ac e k E B e pela def de interseção segue que k E ANB Por k E A0NB e ANB C C e pela def de subconjunto deduzimos que k E C w E X w E Y w E X w E Y w E X w E Y X C Y w E X w E Y X C Y Portanto para todo w E U se w E B então w E C Logo pela def de subconjunto temos que B C C Portanto para todo conjunto XYZ se XNY C Z e XCNY C Z então Y C Z QED Matemática Discreta Teoria dos Conjuntos Demonstração por Contradição Com e Sem casos Exemplos de demonstração por contradição 1 Demonstremos que para todo conjunto XYZ se X Y e Y C Z c então XN Z 0 Demonstração Suponha que o enunciado é falso isto é existem os conjuntos ABC tal que ACB e AN 0 Por AN 0 podemos deduzir que existe k E 0 tal que k E ANC Disse segue pela def de interseção que k E A e k E C Por k E A B e pela def de subconjunto concluimos que k E B De k E B e B C e pela def de subconjunto se desprende que k E C Logo pela def de complemento sabemos que k Ç C isto antradi 2 k E C w E X w E X w E X w E Y w E Xc Y X Y Portanto a suposição é falsa e o enunciado é verdadeiro QED 2 Demonstremos que para todo conjunto XYZ se Z C Y então ZN Y X 0 Demonstração Suponha que o enunciado é falso isto é existem os conjuntos ABC tal que CB e CN BA 0 Por CN BA0 deduzimos que existe k E 0 tal que k E C N BA Logo pela def de interseção temos que k E C e k E BA De k E BA e pela def de diferença segue que k E Ac Por k E C e CBB e pela def de subconjunto concluimos que k E B Disto segue pela def de complemento que k E B Por k E B e k 6 B temos uma contradição Objetivo obter uma contradição Portanto a suposição é falsa e o enunciado é verdadeiro QED 3 Demonstremos que para todo conjunto XYZ se Y N Z C X então ZN N Y X 0 Demonstração Suponha que o enunciado é falso isto é existem os conjuntos ABC tal que BNCS A e CANBA 0 Por CA0 podemos deduzir que existe tal que k E CA N BA Logo pela def de interseção reduzimos que k E CA e k E BA Por k E CA e pela def de diferença temos que k E C De k E BA e pela def de diferença segue que k E B e k 4 A Por k E B e k E pela def de interseção sabemos que k BNC De k E BNC e BN C C A e pela def de subconjunto concluimos que k 16 A isto contradi 2 k 4 A Objetivo obter uma contradição Portanto a suposição é falsa e o enunciado é verdadeiro QED Exemplos de demonstração por contradição e por casos 1 Demonstre que para todo conjunto X Y Z se X Z e Y Z então X Y Z Demonstração Suponha que o enunciado é falso isto é existem os conjuntos A B C tal que A C e B C e A B C Fato 1 Fato 2 Fato 3 Pois A B C e pela def de nãosubconjunto sabemos que existe k T tal que k A B e k C Por k A B e pela def de união temos que k A ou k B k A B weXUY k X ou k Y A B C X Y weUx weX e weY Objetivo obter uma contradição Caso k A Logo por A C e pela def de subconjunto podemos concluir que k C Por k C e k C temos uma contradição Caso k B De k B e B C e pela def de subconjunto temos que k C isto contradiz k C Portanto a suposição é falsa e o enunciado é verdadeiro QED 2 Demonstre que para todo conjunto W X Y Z se W X e Y Z então W Y X Z Tarefa Matemática Discreta Relações Def de produto cartesiano Sejam A e B dois conjuntos O produto cartesiano entre A e B denotado por A x B é o conjunto formado por todos os pares ordenados xy tal que x A e y B isto é A x B x y x A e y B Exemplo A 5 ³ B 7 6³ A x B 7 6 5 5 57 56 7 6 7 6 5 x x x x x x x x x x Def de relação Sejam A e B dois conjuntos Uma relação R de A a B é um subconjunto do produto cartesiano entre A e B isto é R A x B Exemplo R 5 5 A x B 7 6 5 x x Tipos de relações em um conjunto 1 Def de relação reflexiva Seja A um conjunto Uma relação R sobre A isto é R A x A é reflexiva se satisfaz a seguinte condição x A x x R x R x 2 Def de relação simétrica Seja A um conjunto Uma relação R sobre A isto é R A x A é simétrica se satisfaz a seguinte condição xy A xy R yx R x R y y R x 3 Def de relação antissimétrica Seja A um conjunto Uma relação R sobre A isto é R A x A é antissimétrica se satisfaz a seguinte condição xy A xy R e yx R x y x R y y R x Note que uma relação antissimétrica pode ser simétrica 4 Def de relação transitiva Seja A um conjunto Uma relação R sobre A isto é R A x A é transitiva se satisfaz a seguinte condição xyz A xy R e yz R xz R x R y y R z x R z 5 Def de préordem ou quaseordem Seja A um conjunto Uma relação R sobre A isto é R A x A é uma préordem ou quaseordem se é reflexiva e transitiva Exemplos de préordens ou quaseordens ℤ x ℤ 5 5 2 20 220 5 20 20 100 5 100 25 100 100 400 25 400 804 804 ℕ x ℕ relação de divisibilidade 6 Def de ordem parcial Seja A um conjunto Uma relação R sobre A isto é R A x A é uma ordem parcial se é reflexiva transitiva e antissimétrica préordem ou quaseordem Exemplos de ordens parciais ℤ x ℤ x y e y x x y x y e y x x y 5 20 20 5 5 5 5 5 25 25 25 25 25 25 Exemplo de uma préordem que não é uma ordem parcial ℤ x ℤ x y e y x x y 6 6 6 6 6 6 A relação sobre ℤ não é antissimétrica 7 Def de relação de equivalência Seja A um conjunto Uma relação R sobre A isto é R A x A é uma relação de equivalência se é reflexiva transitiva e simétrica préordem ou quaseordem Exemplo de uma relação de equivalência ℤ x ℤ x R y e y R x x y Representação de relações sobre um conjunto Toda relação R sobre um conjunto A pode ser representada por um grafo dirigido seguindo os seguintes passos 1º Desenhe todos os elementos de A junto a um ponto 2º Para cada xy R desenhe uma seta de x até y Exemplos 1 A a b c d e R₁ aa ae bd ed ea a b e c d R₁ não é reflexiva pois b R₁ b R₁ não é simétrica pois b R₁ d mas d R₁ b R₁ não é transitiva pois e R₁ a e a R₁ e mas e R₁ e bb R₁ R₁ não é antissimétrica pois a R₁ e e R₁ a mas a e xy A x R y e y R x x y R1 não é uma préordem nem ordem parcial nem uma relação de equivalência pois R1 não é reflexiva 2 R2 R2 é reflexiva R2 não é simétrica pois a R2 d mas d R2 a R2 não é transitiva pois d R2 b e b R2 a mas d R2 c R2 não é antissimétrica pois a R2 b e b R2 a mas a b R2 não é uma préordem nem ordem parcial nem uma relação de equivalência pois R1 não é transitiva 3 R3 R3 é reflexiva R3 é antissimétrica R3 é transitiva R3 não é simétrica pois a R3 b mas b R3 a R3 é uma préordem e é uma ordem parcial R3 não é uma relação de equivalência pois não é simétrica 4 R4 R4 é reflexiva R4 é antissimétrica R4 é transitiva R4 é simétrica R4 é uma préordem é uma ordem parcial e é uma relação de equivalência 5 R5 R5 é reflexiva R5 não é antissimétrica pois a R5 b e b R5 a mas a b R5 é transitiva R5 é simétrica R5 é uma préordem e é uma relação de equivalência R5 não é uma ordem parcial pois não é antissimétrica Matemática Discreta Teoria dos Conjuntos Exercícios de revisão do conteúdo para a avaliação da terceira unidade 1 Demonstremos por demonstração direta que para todo conjunto XYZ se Z Y e Y X então Z X Y Z Sejam AB e C três conjuntos particulares e arbitrários tal que C B e B A Seja k U um elemento particular e arbitrário tal que k C Por k C e B e pela definição de subconjunto deduzimos que k B De k B e B A e pela definição de subconjunto concluímos que k A Por k C e pela definição de diferença de conjuntos se desprende que k B C De k A e k B C e pela definição de diferença de conjuntos segue que k A B C Portanto para todo w Y se w C então w A B C Logo pela definição de subconjunto podemos concluir que C A B C Portanto para todo conjunto XYZ se Z Y e Y X então Z X Y Z QED 2 Demonstremos por demonstração direta e por casos que para todo conjunto XYZ X Y Z X Y Z X Demonstração Sejam AB e C três conjuntos particulares e arbitrários Seja k U um elemento particular e arbitrário tal que k A B C Logo pela definição de subconjunto concluímos que k A ou k B C Caso k A Logo pela definição de união temos que k A B De k A e pela definição de diferença de conjuntos segue que k C A Por k A B e k C A e pela definição de diferença de conjuntos concluimos que k A B C A Caso k B C Por k B C e pela definição de diferença de conjuntos derivamos que k B e k C Por k B e pela definição de união concluímos que k A B De k C e pela definição de diferença de conjuntos segue que k C A Por k A B e k C A e pela definição de diferença temos como consequência que k A B C A Portanto para todo w J se w A B C então w A B C A Logo pela definição de subconjunto deduzimos que A B C A B C A Portanto para todo conjunto XYZ X Y Z X Y Z X QED 3 Demonstremos por contradição para todo conjunto XYZ se Z X Y X então Y Z X Demonstração Suponha que o enunciado é falso isto é existem os conjuntos AB C tal que C A B A e B C A De B C A e pela definição de nãosubconjunto segue que existe k B C tal que k B k A Por k B e pela definição de interseção sabemos que k B e k C Por k C e k A e pela definição de diferença concluímos que k C A De k B e k A e pela definição de diferença de conjuntos podemos deduzir que k B A Por k C A e k B A e pela definição de interseção temos que k C A B A Consequentemente temos que q C A B A isto contradir C A B A Portanto a suposição é falsa e o enunciado é verdadeiro QED w X Y w X e w Y w X Y w X e w Y X Y w J w X e w Y objetivo obter uma contradição Matemática Discreta Teoria dos Conjuntos Exemplos de demonstração direta 1 Demonstremos que para todo conjunto X Y X Y X Demonstração Sejam A e B dois conjuntos particulares e arbitrários Seja k U um elemento particular e arbitrário tal que k A B Logo pela definição de diferença de conjuntos concluímos que k A e k B Portanto para todo z U se z A B então z B Logo pela definição de subconjunto deduzimos que A B A Portanto para todo conjunto X Y X Y X QED 2 Demonstremos que para todo conjunto X Y X X Y Demonstração Sejam A e B dois conjuntos particulares e arbitrários Seja k U um elemento particular e arbitrário tal que k A Logo pela definição de união de conjuntos deduzimos que k A B Portanto para todo z U se z A então z A B Logo pela definição de subconjunto podemos concluir que A A B Portanto para todo conjunto X Y X X Y QED Resolução de exercícios para revisão da Unidade III 1 Demonstremos que para todo conjunto X Y Z X X Z Y c X Z X Y Demonstração Sejam A B C três conjuntos part e arb Temos que demonstrar que A A C B c A C A B C seja k U um elemento particular e arbitrário tq k A A C B c Temos que k A A C B c k A e k A C B c k A e k A C B k A e k A C ou k B k A e k A ou k C ou k B Contradição k B k A B k A C A B k A C A B k C k A C Portanto para todo z U se z A A C B c então z A C A B Logo por 415 temos que A A C B c A C A B 2 Seja ℓ U um elemento part e arb tq ℓ A C A B temos que ℓ A C A B ℓ A C ou ℓ A B ℓ A ℓ C ℓ A ou ℓ A B ℓ C ℓ A C ℓ A C B ℓ A C B ℓ A C B c ℓ A e ℓ A C B c Portanto para todo z U se z A C A B então z A A C B c Logo por 415 temos que A C A B A A C B c Logo por 418 temos que 1 Portanto 2 QED 2 Demonstremos algebricamente que para todo conjunto X Y Yc Yc X c Y Demonstração Sejam A B dois conjuntos part e arb Temos que demonstrar que Bc Bc A c B Temos que Bc Bc A c Bc Bc Ac c 612 Bc Bc Ac c 69a Bc Bc Ac c 695 Bc c 6105 B 66 Portanto 1 QED 3 Demonstremos por contradição que para todo conjunto X Y Z se X Y X Z e Xc Yc Xc Z então Y Z Demonstração Suponha que o enunciado é falso isto é existem os conjuntos A B C tq A B A C e Ac B Ac C e B C Não sabemos se B se C porque existe k U tq k B e k C ou k B e k C mas em qualquer um dos dois casos o raciocínio é idêntico por isso o escrevemos da seguinte forma Por B C suponha sem perda de generalidade que existe k U tq k B e k C Temos dois casos k A ou k A Caso k A Logo por k B e por 422 temos que k A B Por A B A C e por 418 temos que A B A C e A C A B Por k A B e A B A C e por 415 temos que k A C Logo por 422 temos que k A e k C Por k C e k C temos uma contradição Caso k A Logo por 426 temos que k Ac Logo por k B e 422 temos que k Ac B Por Ac B Ac C e por 418 temos que Ac B Ac C e Ac B e por AcNB AcNC e por 415 temos que kEAcNC Logo por 422 temos que kEAc e kEC Por kEC e kE c temos uma contradição Portanto a suposição é falsa e o enunciado é verdadeiro QED Pk1Pk3k12 Matemática Discreta 2 Demonstremos que para todo x 3 sumi3x yi 4 yx 163 Demonstração PB Temos que demonstrar que sumi33 yi 4 y3 163 Temos que 4y3 163 4 y3 y23 y3 y 13 y3 33 y3 sumi33 yi Portanto sumi33 yi 4 y3 163 para todo y 3 se Py então Py1 PI Temos que demonstrar que para todo y 3 se sumi3y yi 4 yk 163 então sumi3y1 yi 4 yy1 163 Seja k N0 um elemento particular e arbitrário tal que sumi3k yi 4 yk 163 onde k 3 Temos que sumi3k1 yi sumi3k yi yk1 Pela definição recursiva de somatório 4 yk 163 yk1 Pela HI e por substituição 4yk 163 3 4 yk1 4 yk 423 3 yk1 4 yk1 y3 34 yk1 4 yk1 y3 3 yk1 3 4 yk1 423 Portanto para todo y 3 se sumi3y yi 4 yk 163 então sumi3y1 yi 4 yy1 163 Portanto para todo x 3 sumi3x yi 4 yx 163 QED Matematica Discreta 11a Lista de Exercıcios Teoria dos Conjuntos prof Claudio Callejas 1 Exercıcios de demonstracao direta sem im plicacao Exercıcio 1 Demonstre por demonstracao direta que para todo conjunto X Xcc X Exercıcio 2 Demonstre por demonstracao direta que para todo conjunto X Y X X Y X Exercıcio 3 Demonstre por demonstracao direta que para todo conjunto X Y X Y X Y c Exercıcio 4 Demonstre por demonstracao direta que para todo conjunto X Y X Y c Xc Y c 2 Exercıcios de demonstracao direta com im plicacao Exercıcio 5 Demonstre por demonstracao direta que para todo conjunto X Y se X Y Y entao X Y Exercıcio 6 Demonstre por demonstracao direta que para todo conjunto X Y Z se X Y e X Z entao X Y Z Exercıcio 7 Demonstre por demonstracao direta que para todo conjunto X Y X Y sse X Y X Exercıcio 8 Demonstre por demonstracao direta que para todo conjunto W X Y Z se W X e Y Z entao W Z X Y Exercıcio 9 Demonstre por demonstracao direta que para todo conjunto X Y Z se Y Z entao X Z X Y Exercıcio 10 Demonstre por demonstracao direta que para todo conjunto X Y X Y sse Y c Xc 1 Exercıcio 11 Demonstre por demonstracao direta que para todo conjunto X Y X Y sse Y c Xc Y c 3 Exercıcios de demonstracao direta e por casos sem implicacao Exercıcio 12 Demonstre por demonstracao direta e por casos que para todo conjunto X Y Z X Y Z X Y X Z Exercıcio 13 Demonstre por demonstracao direta e por casos que para todo conjunto X Y Z X Y Z X Y X Z Exercıcio 14 Demonstre por demonstracao direta e por casos que para todo conjunto X Y Z X Y Z X Y X Z 4 Exercıcios de demonstracao direta e por casos com implicacao Exercıcio 15 Demonstre por demonstracao direta e por casos que para todo conjunto X Y se X Y entao X Y Y Exercıcio 16 Demonstre por demonstracao direta e por casos que para todo conjunto X Y se X Y entao X Y X Y 5 Exercıcios de demonstracao por contradicao Exercıcio 17 Demonstre por contradicao que para todo conjunto X X Xc Exercıcio 18 Demonstre por contradicao que para todo conjunto X X Xcc Exercıcio 19 Demonstre por contradicao que para todo conjunto X Y X Y X Exercıcio 20 Demonstre por contradicao que para todo conjunto X Y se X Y Y entao X Y Exercıcio 21 Demonstre por contradicao que para todo conjunto X Y X Y sse X Y Exercıcio 22 Demonstre por contradicao que para todo conjunto X Y X Y sse X Y c 2 Exercıcio 23 Demonstre por contradicao que para todo conjunto X Y Z se Z X e X Y entao Z Y Exercıcio 24 Demonstre por contradicao que para todo conjunto X Y se Xc Y U entao X Y 6 Exercıcios de demonstracao por contradicao e por casos Exercıcio 25 Demonstre por contradicao e por casos que para todo con junto X X Xc U Exercıcio 26 Demonstre por contradicao e por casos que para todo con junto X X Xcc U Exercıcio 27 Demonstre por contradicao e por casos que para todo conjunto X Y se X Y entao X Y Y Exercıcio 28 Demonstre por contradicao que para todo conjunto X Y se X Y entao Xc Y U 3 Matemática Discreta Sequências definidas recursivamente Parte 2 Exemplos de resolução por iteração de sequências definidas recursivamente 1 Seja a0 a1 a2 a sequência definida recursivamente da seguinte forma Relação de recorrência para todo x 1 ax r ax1 onde r N Condição inicial a0 a onde a N Use o método da iteração para achar uma fórmula explícita para essa sequência Demonstre que a fórmula explícita encontrada está correta Resolução a0 a a r0 a2 r r a a r2 a1 r a a r1 a3 r r r a a r3 Possível fórmula explícita para todo x 0 ax a rx Temos que demonstrar que a fórmula explícita está correta Demonstração PB Temos que demonstrar que a0 a r0 Temos que a r0 a 1 a a0 pela condição inicial Portanto a0 a r0 PI Temos que demonstrar que para todo y 0 se ay a ry então ay1 a ry1 Seja k N0 um elemento particular e arbitrário tal que ak a rk onde k 0 Temos que ak1 r ak pela relação de recorrência r a rk pela HI e por substituição a rk1 Portanto para todo y 0 se ay a ry então ay1 a ry1 Portanto a fórmula explícita está correta QED 2 Seja a0 a1 a2 a sequência definida recursivamente da seguinte forma Relação de recorrência para todo x 1 ax x ax1 Condição inicial a0 1 Use o método da iteração para achar uma fórmula explícita para essa sequência Demonstre que a fórmula explícita encontrada está correta Resolução a0 1 a1 1 1 1 a2 2 1 1 2 a3 3 2 1 1 3 Possível fórmula explícita para todo x 0 ax x Temos que demonstrar que a fórmula explícita está correta Demonstração PB Temos que demonstrar que a0 0 Temos que a0 1 pela condição inicial 0 Portanto a0 0 PI Temos que demonstrar que para todo y 0 se ay y então ay1 y1 Seja k N0 um elemento particular e arbitrário tal que ak k onde k 0 Temos que ak1 k1 ak pela relação de recorrência k1 k pela HI e por substituição k1 Portanto para todo y 0 se ay y então ay1 y1 Portanto a fórmula explícita está correta QED 3 Seja b0 b1 b2 a sequência definida recursivamente da seguinte forma Relação de recorrência para todo x 1 bx bx11 bx1 Condição inicial b0 1 Use o método da iteração para achar uma fórmula explícita para essa sequência Demonstre que a fórmula explícita encontrada está correta Resolução b0 1 11 01 b1 1 11 12 1 1 12 13 b2 1 1 1 1 11 12 1 12 13 1 21 b3 1 1 1 1 1 1 1 1 13 1 13 14 1 31 Possível fórmula explícita para todo x 0 bx 1 x1 Temos que demonstrar que a fórmula explícita está correta Demonstração PB Temos que demonstrar que b0 1 01 Temos que frac101 1 b0 Pela condição inicial Portanto b0 frac101 PI Temos que demonstrar que para todo y geq 0 se by frac1y1 então by1 frac1y11 Seja k in mathbbN um elemento particular e arbitrário tal que bk frac1k1 onde k geq 0 Temos que bk1 fracbk1bk Pela relação de recorrência fracfrac1k11frac1k1 Pela HI e por substituição frac1k11 frac1k11 Portanto para todo y geq 0 se by frac1y1 então by1 frac1y11 Portanto a fórmula explícita está correta QED Duas fórmulas que podem ser ocupadas neste tipo de exercícios a Para todo x geq 1 123 cdots x fracxx12 b Para todo x in mathbbR3 para todo y geq 0 1 x x2 x3 cdots xy1 fracxy1x1 4 Seja c1 c2 c3 ldots a sequência definida recursivamente da seguinte forma Relação de recorrência para todo x geq 2 cx 3 cx1 1 Condição inicial c1 1 Use o método da iteração para achar uma fórmula explícita para essa sequência Demonstre que a fórmula explícita encontrada está correta Resolução c1 1 1 c3 33 cdot 1 1 1 3231 cy 3 left33 cdot 1 1 1right 1 332311 33 32 3 1 c2 3 cdot 1 1 3 1 Rascunho antes de propor a possível fórmula explícita cx 1 3 32 33 ldots 3x1 frac3x 12 Possível fórmula explícita para todo x geq 1 cx frac3x 12 Temos que demonstrar que a fórmula explícita está correta Demonstração PB Temos que demonstrar que c1 frac31 12 Temos que frac31 12 1 c1 Pela condição inicial Portanto c1 frac31 12 PI Temos que demonstrar que para todo y geq 1 se cy frac3y 12 então cy1 frac3y1 12 Seja k in mathbbN0 um elemento particular e arbitrário tal que ck frac3k 12 onde k geq 1 Temos que ck1 3 ck 1 Pela relação de recorrência 3 leftfrac3k 12right 1 Pela HI e por substituição frac33k 12 1 frac3k1 32 frac22 frac3k1 12 objetivo ck1 frac3k1 12 Portanto para todo y geq 1 se cy frac3y 12 então cy1 frac3y1 12 Portanto a fórmula explícita está correta QED Matemática Discreta Teoria dos Conjuntos Exemplos de demonstração direta 1 Demonstremos que para todo conjunto X Y XY subseteq X Demonstração Sejam A e B dois conjuntos particulares e arbitrários Seja k in U um elemento particular e arbitrário tal que k in A B Logo pela definição de diferença de conjuntos concluímos que k in A e k otin B Portanto para todo z in U se z in A B então z in B Logo pela definição de subconjunto deduzimos que A B subseteq A Portanto para todo conjunto X Y XY subseteq X QED 2 Demonstremos que para todo conjunto X Y X subseteq X cup Y Demonstração Sejam A e B dois conjuntos particulares e arbitrários Seja k in U um elemento particular e arbitrário tal que k in A Logo pela definição de união de conjuntos deduzimos que k in A cup B Portanto para todo z in U se z in A então z in A cup B Logo pela definição de subconjunto podemos concluir que A subseteq A cup B Portanto para todo conjunto X Y X subseteq X cup Y QED Matematica Discreta Teoria dos Conjuntos Exemplos de demonstração direta 1 Demonstremos que para todo conjunto X Y X Y X Demonstração Sejam A e B dois conjuntos particulares e arbitrários Seja k U um elemento particular e arbitrário tal que k A B Logo pela definição de diferença de conjuntos concluímos que k A e k B Portanto para todo z U se z A B então z B Logo pela definição de subconjunto deduzimos que A B A Portanto para todo conjunto X Y X Y X QED K A B K A B z X Y z X e z Y para todo z U se z A B então z A Objetivo A B A 2 Demonstremos que para todo conjunto X Y X X Y Demonstração Sejam A e B dois conjuntos particulares e arbitrários Seja k U um elemento particular e arbitrário tal que k A Logo pela definição de união de conjuntos deduzimos que k A B Portanto para todo z U se z A então z A B Logo pela definição de subconjunto podemos concluir que A A B Portanto para todo conjunto X Y X X Y QED K A B K A B z X Y z X ou z Y para todo z U se z A então z A B Objetivo A A B Matematica Discreta 1a Lista de Exercícios Teoria dos Conjuntos Resolução do Exercício 4 na Seção 1 Exercício 4 Demonstre por demonstração direta que para todo conjunto X Y X Yc Xc Yc Demonstração Sejam A e B dois conjuntos particulares e arbitrários Seja k U um elemento particular e arbitrário tal que k A Bc Disto segue pela definição de complemento que k A B Por k A B e pela definição de união sabemos que k A e k B K A B K A B K A B z X Y z X e z Y k A e k B k A e k B k A B para todo z U se z A Bc então z A c B c Objetivo A Bc A c B c A Bc A c B c A Bc A c B c X Y A Bc A Bc X Y A c B c A Bc X Y A Bc A Bc A c B c De k A e k B e pela definição de complemento deduzimos que k A c e k B c Disto temos como consequência pela definição de interseção que k A c B c Portanto para todo z U se z A Bc então z A c B c Logo pela definição de subconjunto podemos deduzir que A Bc A c B c Seja l U um elemento particular e arbitrário tal que l A c B c Logo pela definição de interseção sabemos que l A c e l B c Por l A c e l B c e pela definição de complemento podemos concluir que l A e l B Consequentemente pela definição de união temos que l A B De l A B e pela definição de complemento segue que l A Bc Portanto para todo z U se z A c B c então z A Bc Logo pela definição de subconjunto concluímos que A c B c A Bc Por A Bc A c B c e A c B c A Bc e pela definição de igualdade temos como consequência que A Bc A c B c Portanto para todo conjunto X Y X Yc Xc Yc QED Matematica Discreta Sequências Somatórios e Produtórios Exemplos de demonstração por indução matemática 1 Demonstremos que para todo x 0 1 2 22 2x 2x1 1 Demonstração PB Temos que demonstrar que 20 201 1 Temos que 201 1 21 1 2 1 1 20 Portanto 20 201 1 PI Temos que demonstrar que para todo y 0 se 1 2 22 2y 2y1 1 então 1 2 22 2y 2y1 2y11 1 Seja k N0 um elemento particular e arbitrário tal que 1 2 22 2k 2k1 1 onde k 0 Temos que 1 2 22 2k 2k1 1 2 22 2k 2k1 Pela ordem dos naturais 2k1 1 2k1 Pela HI e por substituição 2 2k1 1 2k1 1 1 1 2k2 1 Portanto para todo x 0 se 1 2 22 2y 2y1 1 então 1 2 22 2y1 2y11 1 Portanto para todo x 0 1 2 22 2x 2x1 1 QED 2 Demonstremos que para todo x 1 13 23 x3 x x122 Demonstração PB Temos que demonstrar que 13 11122 Temos que 11122 1222 12 13 Portanto 13 11122 PI Temos que demonstrar que para todo y 1 se 13 23 y3 yy122 então 13 23 y13 y1y1122 Seja k N0 um elemento particular e arbitrário tal que 13 23 k3 kk122 onde k 1 Temos que 13 23 k13 13 23 k3 k13 Pela ordem dos naturais kk122 k13 Pela HI e por substituição kk122 k13 Objetivo 13 23 k13 k1k1122 kk12 22 k13 22 k2 k12 22 22 k13 22 k12 k2 22 k1 22 k12 k2 4k1 22 k12 k2 4k 4 22 k12 k22 22 k12 k112 22 k1k112 22 k1k1122 Portanto para todo y 1 se 13 23 y3 yy122 então 13 23 y13 y1y1122 Portanto para todo x 1 13 23 x3 xx122 QED