Revisão Matemática Discreta: Demonstrações por Contradição e Subconjuntos

Matemática Discreta Turma 02 Revisão do conteúdo para a avaliação da terceira unidade Resolução de exercícios da Lista de exercícios nº 11 Exercício 22 Demonstre por contradição que para todo conjunto X Y X Y sse X Yc Demonstração Suponha que o enunciado é falso isto é existem os conjuntos A B tal que A B e A Bc ou A B e A Bc Caso A B e A Bc Por A Bc podemos deduzir que existe k U tal que k A Bc Disto segue pela def de interseção que k A e k Bc Por k Bc e pela def de complemento podemos concluir que k B Objetivo obter uma contradição Podemos obter uma contradição de duas formas diferentes Alternativa 1 Por k A e A B e pela def de subconjunto podemos afirmar que k B isto contradiz k B Alternativa 2 Por k B e A B e pela def de subconjunto podemos deduzir que k A isto contradiz k A Caso A B e A Bc Por A B e pela def de não subconjunto podemos concluir que existe l U tal que l A e l B Por l B e pela def de complemento temos que l Bc De l A e l Bc e pela def de interseção segue que l A Bc isto significa que A Bc Por A Bc e A Bc temos uma contradição Portanto a suposição é falsa e o enunciado é verdadeiro QED Exercício 19 Demonstre por contradição que para todo conjunto X Y X Y X Demonstração Suponha que o enunciado é falso isto é existem os conjuntos A B tal que A B A Logo podemos afirmar que existe k U tal que k A B A Disto segue pela def de interseção que k A e k B A Por k B A e pela def de diferença sabemos que k B e k A Por k A e k A temos uma contradição Portanto a suposição é falsa e o enunciado é verdadeiro QED Exercício 15 Demonstre por demonstração direta e por casos que para todo conjunto X Y se X Y então X Y Y Demonstração Sejam A e B dois conjuntos particulares e arbitrários tal que A B Seja k U um elemento particular e arbitrário tal que k A B Logo pela def de união temos que k A ou k B Caso k A Logo por A B e pela def de subconjunto temos que k B Caso k B Não há mais nada que demonstrar neste caso Portanto para todo z U se z A B então z B Logo pela def de subconjunto temos que A B B Portanto para todo conjunto X Y se X Y então X Y Y QED