Matematica Discreta - Tecnicas de Demonstracao - Provas de Generalizacao e Existencia

Introducao as Tecnicas de Demonstracao QXD0008 Matematica Discreta Prof Lucas Ismaily ismailybfufcbr Universidade Federal do Ceara 1º semestre2024 Topicos desta aula Enunciados de generalizacao e de existˆencia Provas de Generalizacao Provas de Existˆencia Tencicas de Provas de Condicionais 2 Referˆencias para esta aula Secao 17 do livro Kenneth H Rosen Matematica Discreta e suas Aplicacoes Sexta Edicao 3 Introdução Demonstracao de Teoremas Demonstrar um teorema geralmente envolve 1 analisar a estrutura da sua proposicao 2 identificar tecnicas adequadas para provar a afirmacao e escolher uma 3 levantar hipoteses de acordo com a tecnica escolhida 4 provar uma nova proposicao objetivo criada pela tecnica 5 concluir que a proposicaoobjetivo segue das hipoteses Os Items 3 a 5 serao a prova do teorema da proposicao original O no Item 4 aponta uma abertura na prova Esta parte e contextual dependente do assunto do teorema E nosso trabalho completala reaplicando o roteiro acima recursivamente 5 Tipos de Enunciados de Teoremas Ha principalmente dois tipos de enunciados Universais ou Generalizacoes Existenciais Algumas tecnicas sao orientadas ao tipo de enunciado Prova de Generalizacao Prova Existencial Prova por Contraexemplo Prova de Unicidade 6 Enunciados de Generalizacao Universais ou Generalizacoes xPx Qx Todos os elementos do domınio que satisfazem a propriedade Px devem satisfazer tambem a propriedade Qx E o formato mais comum que teoremas assumem A fim de provar um teorema da forma xPx Qx nosso objetivo e mostrar que Pc Qc e verdadeiro onde c e um elemento arbitrario do domınio Uma vez provado isso aplicamos a regra de inferˆencia generalizacao universal 7 Enunciados de Generalizacao Exemplo Universais ou Generalizacoes xPx Qx Px x e par e Qx x2 e par Variacoes Para todo numero se este e par entao seu quadrado e par Para todo numero par seu quadrado e par Se um numero e par seu quadrado e par Para qualquer numero par seu quadrado e par Dado um numero par seu quadrado sera par O quadrado de um inteiro par e par 8 Enunciados de Generalizacao Como interpretar O quadrado de um inteiro par e par Procure os seguintes elementos 1 Sempre ha um condicional ou um bicondicional 2 O restante do texto e composto por afirmacoes menores Que partes do enunciado caracterizam objetos Que tipos de objetos sao esses 3 Algumas afirmacoes sao condicoes a priori e outros sao conclusoes a posteriori Observacao E possıvel ter outros elementos no texto mas estes da lista acima sempre existirao 9 Enunciados de Generalizacao Como interpretar O quadrado de um inteiro par e par Procure os seguintes elementos 1 Sempre ha um condicional ou um bicondicional Se nao estiver explıcito assuma que e um condicional simples Quando tiver os outros elementos da lista reavalie este item Resposta Condicional 10 Enunciados de Generalizacao Como interpretar O quadrado de um inteiro par e par Procure os seguintes elementos 2 O restante do texto e composto por afirmacoes menores Que partes do enunciado caracterizam objetos Que tipos de objetos sao esses Resposta um inteiro par o quadrado desse inteiro e par 11 Enunciados de Generalizacao Como interpretar O quadrado de um inteiro par e par Procure os seguintes elementos 3 Algumas afirmacoes sao condicoes a priori e outros sao conclusoes a posteriori Resposta Neste enunciado a descricao um inteiro par condiciona a descricao o quadrado desse um inteiro e par Entao temos que SE um inteiro e par ENTAO o quadrado desse inteiro e par 12 Enunciados Existenciais Existenciais xPx Alguns elementos do domınio satisfazem a propriedade Px A propriedade Px pode ser tambem uma formula com conectivos O conectivo mais comum e a conjuncao Admitem excecoes 13 Enunciados Existenciais Existenciais xPx Qx Px x e primo e Qx x e par Variacoes Existe um numero primo par Algum numero primo e par Existe um numero que e primo e par Ao menos um numero e simultaneamente primo e par Ha numeros que sao primos e pares Alguns numeros que sao primos sao pares 14 Enunciados Existenciais Como interpretar Algum numero primo e par Procure os mesmos elementos de antes 1 Identifique partes do enunciado que descrevam objetos e que tipos de objetos sao 2 Quais deles sao condicoes Normalmente indicarao o domınio Procure tambem os seguintes elementos 3 Quantificadores para cada variavel Se o condicional do enunciado tiver excecoes ele se tornara verdadeiro ou falso Caso permaneca verdadeiro o enunciado e existencial caso falso e universal Observacao A palavra algum indica que basta um elemento do domınio satisfazer as propriedades Isso significa que o enunciado admite excecoes A unica variavel existente e existencial 15 Eu acho que o enunciado e falso ou verdadeiro Universal Verdadeiro Prova de Generalizacoes Universal Falso Prova por Contraexemplo Existencial Verdadeiro Prova de Existˆencia Construtiva ou NaoConstrutiva Existencial Falso Prova de Generalizacoes 16 Prova de Generalizações Eu acho que o enunciado e falso ou verdadeiro Exemplo Existe um numero par cujo quadrado e ımpar x x e par x2 e ımpar Parece falso nao e mesmo La atras vimos que Existencial Falso Prova de Generalizacoes Vamos negar esta frase Nao existe nenhum numero par cujo quadrado seja ımpar x x e par x2 e ımpar 18 Eu acho que o enunciado e falso ou verdadeiro Exemplo Existe um numero par cujo quadrado e ımpar x x e par x2 e ımpar Parece falso nao e mesmo La atras vimos que Existencial Falso Prova de Generalizacoes Vamos negar esta frase Nao existe nenhum numero par cujo quadrado seja ımpar x x e par x2 e ımpar 18 Eu acho que o enunciado e falso ou verdadeiro Exemplo Existe um numero par cujo quadrado e ımpar x x e par x2 e ımpar Parece falso nao e mesmo La atras vimos que Existencial Falso Prova de Generalizacoes Vamos negar esta frase Nao existe nenhum numero par cujo quadrado seja ımpar x x e par x2 e ımpar 18 Eu acho que o enunciado e falso ou verdadeiro Desenvolvimento completo a partir da negacao P Nao existe nenhum numero par cujo quadrado seja ımpar x x e par x2 e ımpar x x e par x2 e ımpar Lei da negacao do quantificador x x e par x2 e ımpar DeMorgan x x e par x2 e ımpar Lei do condicional x x e par x2 e par Negacao P Para todo numero par seu quadrado e par P Se um numero e par entao seu quadrado e par P O quadrado de um inteiro par e par 19 Eu acho que o enunciado e falso ou verdadeiro Desenvolvimento completo a partir da negacao P Nao existe nenhum numero par cujo quadrado seja ımpar x x e par x2 e ımpar x x e par x2 e ımpar Lei da negacao do quantificador x x e par x2 e ımpar DeMorgan x x e par x2 e ımpar Lei do condicional x x e par x2 e par Negacao P Para todo numero par seu quadrado e par P Se um numero e par entao seu quadrado e par P O quadrado de um inteiro par e par 19 Prova de generalizacoes Por exemplo no enunciado decodificado anteriormente O quadrado de um inteiro par e par x x e par x2 e par temos o quantificador universal Portanto para demonstrar que o enunciado e verdadeiro precisaremos da Prova de Generalizacoes 20 Prova de generalizacoes Demonstre que o quadrado de um inteiro par e par x x e par x2 e par 1 Instanciacao Universal Seja c um inteiro qualquer 2 Desenvolvimento Provaremos que c e par c2 e par Este item e deixado em aberto pela generalizacao Demanda a aplicacao de outra tecnica 3 Generalizacao Universal Como provamos a propriedade para um inteiro qualquer a propriedade vale para todos os inteiros 21 Prova de generalizacoes Demonstre que o quadrado de um inteiro par e par x x e par x2 e par 1 Instanciacao Universal Seja c um inteiro qualquer 2 Desenvolvimento Provaremos que c e par c2 e par Este item e deixado em aberto pela generalizacao Demanda a aplicacao de outra tecnica 3 Generalizacao Universal Como provamos a propriedade para um inteiro qualquer a propriedade vale para todos os inteiros 21 Prova de generalizacoes Demonstre que o quadrado de um inteiro par e par x x e par x2 e par 1 Instanciacao Universal Seja c um inteiro qualquer 2 Desenvolvimento Provaremos que c e par c2 e par Este item e deixado em aberto pela generalizacao Demanda a aplicacao de outra tecnica 3 Generalizacao Universal Como provamos a propriedade para um inteiro qualquer a propriedade vale para todos os inteiros 21 Prova de generalizacoes Demonstre que o quadrado de um inteiro par e par x x e par x2 e par 1 Instanciacao Universal Seja c um inteiro qualquer 2 Desenvolvimento Provaremos que c e par c2 e par Este item e deixado em aberto pela generalizacao Demanda a aplicacao de outra tecnica 3 Generalizacao Universal Como provamos a propriedade para um inteiro qualquer a propriedade vale para todos os inteiros 21 Recapitulando Eu acho que o enunciado e falso ou verdadeiro Universal Verdadeiro Prova de Generalizacoes Universal Falso Prova por Contraexemplo Existencial Verdadeiro Prova de Existˆencia Construtiva NaoConstrutiva Existencial Falso Prova de Generalizacoes 22 Prova de existˆencia Vimos anteriormente o seguinte enunciado Algum numero primo e par xx e primo x e par Neste enunciado temos um quantificador universal Portanto para demonstrar que o enunciado e verdadeiro precisaremos da Prova de Existˆencia Uma Prova de Existˆencia pode ser construtiva ou naoconstrutiva 23 Prova de existˆencia Construtiva Definicao Um inteiro n e par se existe um inteiro k tal que n 2k Definicao Um inteiro n e ımpar se existe um inteiro k tal que n 2k 1 Definicao Um inteiro p e primo se p 1 e se os unicos divisores positivos de p sao 1 e p Definicao Um inteiro positivo que e maior do que 1 e nao e primo e chamado de composto Teorema Algum numero primo e par xx e primo x e par Prova construtiva O numero 2 e primo e e par 24 Prova de existˆencia NaoConstrutiva Teorema Algum numero primo e par xx e primo x e par Prova naoconstrutiva Por contradicao suponha que nao existe nenhum numero primo par Isso significaria que todos os numeros primos sao ımpares Considere agora um numero par como por exemplo o numero 42 Pela nossa suposicao 42 nao e primo ou seja 42 e composto um produto de numeros primos Como todos os primos sao ımpares temos um produto de numeros ımpares que resulta em um numero par Absurdo Logo deve existir ao menos um numero primo par 25 Recapitulando Eu acho que o enunciado e falso ou verdadeiro Universal Verdadeiro Prova de Generalizacoes Universal Falso Prova por Contraexemplo Existencial Verdadeiro Prova de Existˆencia Construtiva NaoConstrutiva Existencial Falso Prova de Generalizacoes 26 Prova por contraexemplo Universal Falso Prova por Contraexemplo O formato mais comum de enunciado e o de generalizacao xPx Qx Sempre ha um condicional seentao numa generalizacao Dada uma afirmacao condicional como provar que ela e falsa A maneira tıpica de refutar um condicional e criar um contraexemplo Um contraexemplo de uma afirmacao se P entao Q seria uma instˆancia em que P e verdadeira mas Q e falsa xPx Qx xPx Qx Lei da negacao do quantificador xPx Qx Lei do condicional xPx Qx DeMorgan xPx Qx Negacao dupla 27 Definicoes Definicao Sejam a e b inteiros Dizemos que a e divisıvel por b se existir um inteiro c de modo que bc a Alternativamente podemos dizer que a e um multiplo de b b e um fator de a b e um divisor de a ou b divide a A notacao correspondente e ba e deve ser lida como b divide a Simbolicamente se a e b sao inteiros ba um inteiro k tal que a bk 28 Prova por contraexemplo Afirmacao falsa Sejam a e b inteiros Se ab e ba entao a b ab ab ba a b Parece que se ab entao a b e se ba entao b a entao a b Mas este raciocınio e incorreto Para refutar a afirmacao precisamos achar inteiros a e b tais que de uma lado verifiquem ab e ba mas de outro nao verifiquem a b Contraexemplo a 5 e b 5 29 Prova por contraexemplo Afirmacao falsa Sejam a e b inteiros Se ab e ba entao a b ab ab ba a b Parece que se ab entao a b e se ba entao b a entao a b Mas este raciocınio e incorreto Para refutar a afirmacao precisamos achar inteiros a e b tais que de uma lado verifiquem ab e ba mas de outro nao verifiquem a b Contraexemplo a 5 e b 5 29 Resumo Tipos de Enunciados Estas tecnicas sao as unicas associadas a quantificadores Prova de Generalizacoes Prova de Existenciais Prova por ContraExemplo Vimos que O enunciado mais comum e o de generalizacao xPx Qx Sempre ha um condicional numa generalizacao Conclusao Precisamos de tecnicas para provar condicionais 30 Prova de Condicionais Prova de Condicionais Tecnicas para provar Pc Qc Prova direta suponha PC alcanceconclua Qc Prova por Contraposicao suponha QC alcanceconclua Pc Prova por Contradicao ou Reducao ao Absurdo suponha pC Qc alcanceconclua 32 Prova de Condicionais Tecnicas para provar Pc Qc Prova direta suponha PC alcanceconclua Qc Prova por Contraposicao suponha QC alcanceconclua Pc Prova por Contradicao ou Reducao ao Absurdo suponha pC Qc alcanceconclua 32 Prova de Condicionais Tecnicas para provar Pc Qc Prova direta suponha PC alcanceconclua Qc Prova por Contraposicao suponha QC alcanceconclua Pc Prova por Contradicao ou Reducao ao Absurdo suponha pC Qc alcanceconclua 32 Prova de Condicionais Tecnicas para provar Pc Qc Prova direta suponha PC alcanceconclua Qc Prova por Contraposicao suponha QC alcanceconclua Pc Prova por Contradicao ou Reducao ao Absurdo suponha pC Qc alcanceconclua 32 Prova de Condicionais Prova Direta 33 Prova Direta Definicao Uma demonstracao direta de um condicional p q e construıda quando o primeiro passo e supor que p e verdadeira os passos subsequentes sao construıdos utilizandose axiomas definicoes e teoremas previamente comprovados junto com regras de inferˆencia com o passo final mostrando que q deve ser tambem verdadeira 34 Prova Direta Exemplo 1 Demonstre que o quadrado de um inteiro par e par x x e par x2 e par 1 Instanciacao Universal Seja c um inteiro qualquer 2 Desenvolvimento Provaremos que c e par c2 e par Este item e deixado em aberto pela generalizacao Demanda a aplicacao de outra tecnica 3 Generalizacao Universal Como provamos a propriedade para um inteiro qualquer a propriedade vale para todos os inteiros 35 Prova Direta Exemplo 1 Demonstre que o quadrado de um inteiro par e par x x e par x2 e par 1 Instanciacao Universal Seja c um inteiro qualquer 2 Desenvolvimento Provaremos que c e par c2 e par Este item e deixado em aberto pela generalizacao Demanda a aplicacao de outra tecnica 3 Generalizacao Universal Como provamos a propriedade para um inteiro qualquer a propriedade vale para todos os inteiros 35 Prova Direta Exemplo 1 Demonstre que o quadrado de um inteiro par e par x x e par x2 e par 1 Instanciacao Universal Seja c um inteiro qualquer 2 Desenvolvimento Provaremos que c e par c2 e par Este item e deixado em aberto pela generalizacao Demanda a aplicacao de outra tecnica 3 Generalizacao Universal Como provamos a propriedade para um inteiro qualquer a propriedade vale para todos os inteiros 35 Prova Direta Exemplo 1 Demonstre que o quadrado de um inteiro par e par x x e par x2 e par 1 Instanciacao Universal Seja c um inteiro qualquer 2 Desenvolvimento Provaremos que c e par c2 e par 21 Por PROVA DIRETA suponha que c e par 22 Entao existe k Z tal que c 2k definicao 23 Logo c2 4k2 2 2k2 e um numero par 3 Generalizacao Universal Como provamos a propriedade para um inteiro qualquer a propriedade vale para todos os inteiros 36 Prova Direta Exemplo 1 Demonstre que o quadrado de um inteiro par e par x x e par x2 e par 1 Instanciacao Universal Seja c um inteiro qualquer 2 Desenvolvimento Provaremos que c e par c2 e par 21 Por PROVA DIRETA suponha que c e par 22 Entao existe k Z tal que c 2k definicao 23 Logo c2 4k2 2 2k2 e um numero par 3 Generalizacao Universal Como provamos a propriedade para um inteiro qualquer a propriedade vale para todos os inteiros 36 Prova Direta Exemplo 2 Demonstre que se n e um inteiro ımpar entao n2 e ımpar x x e ımpar x2 e ımpar Demonstracao 1 Seja n um numero inteiro ımpar 2 Pela definicao de numero ımpar temos que n 2k 1 em que k e algum inteiro Queremos demonstrar que n2 e tambem ımpar 3 Vamos elevar ao quadrado ambos os membros da equacao n 2k 1 Para quˆe Qual a finalidade 4 Assim temos n2 2k 12 4k2 4k 1 22k2 2k 1 5 Pela definicao de inteiro ımpar concluımos que n2 e ımpar 6 Consequentemente provamos que se n e um inteiro ımpar entao n2 e ımpar 37 Prova Direta Exemplo 2 Demonstre que se n e um inteiro ımpar entao n2 e ımpar x x e ımpar x2 e ımpar Demonstracao 1 Seja n um numero inteiro ımpar 2 Pela definicao de numero ımpar temos que n 2k 1 em que k e algum inteiro Queremos demonstrar que n2 e tambem ımpar 3 Vamos elevar ao quadrado ambos os membros da equacao n 2k 1 Para quˆe Qual a finalidade 4 Assim temos n2 2k 12 4k2 4k 1 22k2 2k 1 5 Pela definicao de inteiro ımpar concluımos que n2 e ımpar 6 Consequentemente provamos que se n e um inteiro ımpar entao n2 e ımpar 37 Definicao Um inteiro a e um quadrado perfeito se existe um inteiro b tal que a b2 Exemplos 4 9 16 25 36 38 Prova Direta Exemplo 3 Demonstre que se m e n sao ambos quadrados perfeitos entao m n tambem e um quadrado perfeito U N mn QPm QPn QPmn Demonstracao 1 Sejam m e n dois inteiros quadrados perfeitos 2 Pela definicao de quadrado perfeito seguese que existem inteiros s e t tal que m s2 e n t2 3 Portanto temos que mn s2t2 sstt stst stst st2 usando comutatividade e associatividade da multiplicacao 4 Pela definicao de quadrado perfeito segue que mn tambem e um quadrado perfeito 39 Prova Direta Exemplo 3 Demonstre que se m e n sao ambos quadrados perfeitos entao m n tambem e um quadrado perfeito U N mn QPm QPn QPmn Demonstracao 1 Sejam m e n dois inteiros quadrados perfeitos 2 Pela definicao de quadrado perfeito seguese que existem inteiros s e t tal que m s2 e n t2 3 Portanto temos que mn s2t2 sstt stst stst st2 usando comutatividade e associatividade da multiplicacao 4 Pela definicao de quadrado perfeito segue que mn tambem e um quadrado perfeito 39 Prova Direta Transitividade da dividibilidade Teorema Para todos os inteiros a b e c se ab e bc entao ac U Z abc ab bc ac Demonstracao 1 Sejam a b e c inteiros arbitrarios tais que a divide b e b divide c 2 Vamos mostrar que a divide c 3 Pela definicao de dividibilidade b ar e c bs para inteiros r e s 4 Por substituicao e associatividade da multiplicacao temos que c bs ars ars 5 Seja k rs onde k e um numero inteiro 6 Logo c ak ou seja a divide c pela definicao de divisibilidade 40 Prova Direta Transitividade da dividibilidade Teorema Para todos os inteiros a b e c se ab e bc entao ac U Z abc ab bc ac Demonstracao 1 Sejam a b e c inteiros arbitrarios tais que a divide b e b divide c 2 Vamos mostrar que a divide c 3 Pela definicao de dividibilidade b ar e c bs para inteiros r e s 4 Por substituicao e associatividade da multiplicacao temos que c bs ars ars 5 Seja k rs onde k e um numero inteiro 6 Logo c ak ou seja a divide c pela definicao de divisibilidade 40 Definicao de racional e irracional O numero real r e racional se existem inteiros p e q com q 0 tal que r pq Todo numero racional pode ser escrito como uma fracao irredutıvel p e q nao tem divisor comum Um numero real que nao e racional e chamado de irracional 41 Definicao de racional e irracional Exemplos a 103 e racional Sim quociente de inteiros b 0 281 e racional Sim Numero na notacao decimal que representa 2811000 c 0 121212 e racional Sim Seja x 0 121212 e 100x 12 121212 100x x 12 121212 0 121212 99x 12 x 1299 42 Definicao de racional e irracional Exemplos a 103 e racional Sim quociente de inteiros b 0 281 e racional Sim Numero na notacao decimal que representa 2811000 c 0 121212 e racional Sim Seja x 0 121212 e 100x 12 121212 100x x 12 121212 0 121212 99x 12 x 1299 42 Definicao de racional e irracional Exemplos a 103 e racional Sim quociente de inteiros b 0 281 e racional Sim Numero na notacao decimal que representa 2811000 c 0 121212 e racional Sim Seja x 0 121212 e 100x 12 121212 100x x 12 121212 0 121212 99x 12 x 1299 42 Definicao de racional e irracional Exemplos a 103 e racional Sim quociente de inteiros b 0 281 e racional Sim Numero na notacao decimal que representa 2811000 c 0 121212 e racional Sim Seja x 0 121212 e 100x 12 121212 100x x 12 121212 0 121212 99x 12 x 1299 42 Definicao de racional e irracional Exemplos a 103 e racional Sim quociente de inteiros b 0 281 e racional Sim Numero na notacao decimal que representa 2811000 c 0 121212 e racional Sim Seja x 0 121212 e 100x 12 121212 100x x 12 121212 0 121212 99x 12 x 1299 42 Definicao de racional e irracional Exemplos a 103 e racional Sim quociente de inteiros b 0 281 e racional Sim Numero na notacao decimal que representa 2811000 c 0 121212 e racional Sim Seja x 0 121212 e 100x 12 121212 100x x 12 121212 0 121212 99x 12 x 1299 42 Prova Direta Exemplo 5 Teorema A soma de dois numeros racionais e um numero racional U Q rs r Q s Q r x Q Demonstracao 1 Sejam r e s dois numeros racionais 2 Pela definicao de numero racional existem inteiros p e q com q 0 tais que r pq e inteiros t e u com u 0 tais que s tu Podemos usar esta informacao para mostrar que r s e racional 3 Somando r e s nos obtemos o seguinte numero r s p q t u pu qt qu 4 Como q 0 e u 0 segue que qu 0 Assim r s pode ser expresso como a razao de dois inteiros pu qt e qu com qu 0 Isso implica que r s e racional 43 Prova Direta Exemplo 5 Teorema A soma de dois numeros racionais e um numero racional U Q rs r Q s Q r x Q Demonstracao 1 Sejam r e s dois numeros racionais 2 Pela definicao de numero racional existem inteiros p e q com q 0 tais que r pq e inteiros t e u com u 0 tais que s tu Podemos usar esta informacao para mostrar que r s e racional 3 Somando r e s nos obtemos o seguinte numero r s p q t u pu qt qu 4 Como q 0 e u 0 segue que qu 0 Assim r s pode ser expresso como a razao de dois inteiros pu qt e qu com qu 0 Isso implica que r s e racional 43 Prova de Condicionais Prova por Contraposicao 44 Prova por Contraposicao Princıpios 1 Expresse a afirmacao a ser provada na forma x U se Px entao Qx 2 Reescreva a afirmacao na forma contrapositiva x U se Qx entao Px 3 Prove a contrapositiva por uma prova direta a Suponha x um elemento escolhido arbitrariamente de U tal que Qx seja V b Tomando Qx como premissa e usando axiomas definicoes e teoremas previamente provados e regras de inferˆencia mostre que Px deve ser verdadeira 45 Prova por Contraposicao Exemplo 1 Teorema Dado qualquer inteiro n se n2 e par entao n e par Demonstracao por contraposicao 1 Instanciacao Seja n um inteiro qualquer 2 Desenvolvimento Provaremos que n2 e par n e par 21 Por CONTRAPOSIC AO suponha que n e ımpar 22 Devemos mostrar que n2 nao e par ou seja e ımpar 23 Por definicao de um numero ımpar sabese que n 2k 1 para algum inteiro k Entao n2 2k 12 4k2 4k 1 22k2 2k 1 24 Desta forma n2 e um numero ımpar 3 Generalizacao Como provamos a propriedade para um inteiro n qualquer a propriedade vale para todos os inteiros Como a negacao do consequente do enunciado condicional implica a negacao do antecedente do enunciado condicional temos que o enunciado condicional original e verdadeiro 46 Prova por Contraposicao Exemplo 1 Teorema Dado qualquer inteiro n se n2 e par entao n e par Demonstracao por contraposicao 1 Instanciacao Seja n um inteiro qualquer 2 Desenvolvimento Provaremos que n2 e par n e par 21 Por CONTRAPOSIC AO suponha que n e ımpar 22 Devemos mostrar que n2 nao e par ou seja e ımpar 23 Por definicao de um numero ımpar sabese que n 2k 1 para algum inteiro k Entao n2 2k 12 4k2 4k 1 22k2 2k 1 24 Desta forma n2 e um numero ımpar 3 Generalizacao Como provamos a propriedade para um inteiro n qualquer a propriedade vale para todos os inteiros Como a negacao do consequente do enunciado condicional implica a negacao do antecedente do enunciado condicional temos que o enunciado condicional original e verdadeiro 46 Prova por Contraposicao Exemplo 1 Teorema Dado qualquer inteiro n se n2 e par entao n e par Demonstracao Vamos provar a afirmacao por contraposicao Seja n um inteiro qualquer Suponha que n e ımpar Pela definicao de numero ımpar temos que n 2k 1 para algum inteiro k Isso implica que n2 2k 12 4k2 4k 1 22k2 2k 1 Isto e n2 2s 1 sendo s 2k2 2k e um inteiro Pela definicao de numero ımpar concluımos que n2 e ımpar Como a negacao do consequente do enunciado condicional implica a negacao do antecedente do enunciado condicional temos que o enunciado condicional original e verdadeiro 47 Prova por Contraposicao Exemplo 1 Teorema Dado qualquer inteiro n se n2 e par entao n e par Demonstracao Vamos provar a afirmacao por contraposicao Seja n um inteiro qualquer Suponha que n e ımpar Pela definicao de numero ımpar temos que n 2k 1 para algum inteiro k Isso implica que n2 2k 12 4k2 4k 1 22k2 2k 1 Isto e n2 2s 1 sendo s 2k2 2k e um inteiro Pela definicao de numero ımpar concluımos que n2 e ımpar Como a negacao do consequente do enunciado condicional implica a negacao do antecedente do enunciado condicional temos que o enunciado condicional original e verdadeiro 47 Prova por Contraposicao Exemplo 2 Teorema Dados dois inteiros positivos a e b se n ab entao a n ou b n Demonstracao 1 Vamos provar a contrapositiva Dados dois inteiros positivos a e b suponha que a n ou b n e falso 2 Usando o significado da disjuncao junto com a Lei de DeMorgan isto implica que a n e b n 3 Podemos multiplicar essas duas inequacoes juntas para obter ab n n n Aqui usamos o fato de que se 0 s t e 0 u v entao su tv 4 Assim concluımos que n ab 5 Como a negacao do consequente do enunciado condicional implica a negacao do antecedente do enunciado condicional temos que o enunciado condicional original e verdadeiro 48 Prova por Contraposicao Exemplo 2 Teorema Dados dois inteiros positivos a e b se n ab entao a n ou b n Demonstracao 1 Vamos provar a contrapositiva Dados dois inteiros positivos a e b suponha que a n ou b n e falso 2 Usando o significado da disjuncao junto com a Lei de DeMorgan isto implica que a n e b n 3 Podemos multiplicar essas duas inequacoes juntas para obter ab n n n Aqui usamos o fato de que se 0 s t e 0 u v entao su tv 4 Assim concluımos que n ab 5 Como a negacao do consequente do enunciado condicional implica a negacao do antecedente do enunciado condicional temos que o enunciado condicional original e verdadeiro 48 Prova de Condicionais Prova por Contradicao Reducao ao Absurdo 49 Prova por Contradicao Princıpios 1 Expresse a afirmacao a ser provada na forma x U se Px entao Qx 2 Primeiro suponha que Qx e verdadeira para x qualquer 3 Entao use a premissa Px e a negacao da conclusao Qx para chegar em uma contradicao A razao pela qual essas demonstracoes sao validas esta na equivalˆencia logica p q p q F 50 Prova por Contradicao Exemplo 1 Teorema O quadrado de um inteiro par e par 1 Instanciacao Universal Seja c um inteiro qualquer 2 Desenvolvimento Provaremos que c e par c2 e par Por CONTRADIC AO suponha que c e par mas c2 e ımpar Entao existem k Z tal que c 2k definicao de par e j Z tal que c2 2j 1 definicao de ımpar Temos que c2 c c 2k 2k 4k2 Logo 4k2 2j 1 Isolando j encontraremos que j 4k21 2 4k2 2 1 2 2k2 1 2 que nao e inteiro Absurdo pois j deveria ser inteiro 3 Generalizacao Universal Como provamos a propriedade para um inteiro qualquer a propriedade vale para todos os inteiros 51 Prova por Contradicao Exemplo 1 Teorema O quadrado de um inteiro par e par 1 Instanciacao Universal Seja c um inteiro qualquer 2 Desenvolvimento Provaremos que c e par c2 e par Por CONTRADIC AO suponha que c e par mas c2 e ımpar Entao existem k Z tal que c 2k definicao de par e j Z tal que c2 2j 1 definicao de ımpar Temos que c2 c c 2k 2k 4k2 Logo 4k2 2j 1 Isolando j encontraremos que j 4k21 2 4k2 2 1 2 2k2 1 2 que nao e inteiro Absurdo pois j deveria ser inteiro 3 Generalizacao Universal Como provamos a propriedade para um inteiro qualquer a propriedade vale para todos os inteiros 51 Prova por Contradicao Exemplo 2 Teorema A soma de dois inteiros ımpares e par 1 Instanciacao Universal Sejam p e q dois inteiros quaisquer 2 Desenvolvimento Provaremos que se p e q sao ımpares p q e par Por CONTRADIC AO suponha que p e q sao ımpares mas p q e ımpar Entao existem k j Z tais que p 2k 1 e q 2j 1 definicao de ımpar e m Z tal que p q 2m 1 definicao de ımpar Temos que p q 2k 1 2j 1 2m 1 Logo 2k j 1 2m 1 Isolando m encontraremos que m 2kj11 2 2kj1 2 1 2 que nao e inteiro Absurdo pois m deveria ser inteiro 52 Prova por Contradicao Exemplo 2 Teorema A soma de dois inteiros ımpares e par 1 Instanciacao Universal Sejam p e q dois inteiros quaisquer 2 Desenvolvimento Provaremos que se p e q sao ımpares p q e par Por CONTRADIC AO suponha que p e q sao ımpares mas p q e ımpar Entao existem k j Z tais que p 2k 1 e q 2j 1 definicao de ımpar e m Z tal que p q 2m 1 definicao de ımpar Temos que p q 2k 1 2j 1 2m 1 Logo 2k j 1 2m 1 Isolando m encontraremos que m 2kj11 2 2kj1 2 1 2 que nao e inteiro Absurdo pois m deveria ser inteiro 52 Relacao entre prova por contradicao e prova por contraposicao Na prova por contraposicao a afirmacao x U se Px entao Qx e provada apresentando uma prova direta da afirmacao equivalente x U se Qx entao Px Este tipo de prova segue os seguintes passos a Suponha que x e um elemento arbitrario de U tal que Qx b Atraves do raciocınio dedutivo isto leva a Px A prova por contradicao e baseada nos seguintes passos a Suponha que existe um elemento x U tal que Px Qx b Usando o mesmo raciocınio dedutivo isto leva a contradicao Px Px 53 Relacao entre prova por contradicao e prova por contraposicao Na prova por contraposicao a afirmacao x U se Px entao Qx e provada apresentando uma prova direta da afirmacao equivalente x U se Qx entao Px Este tipo de prova segue os seguintes passos a Suponha que x e um elemento arbitrario de U tal que Qx b Atraves do raciocınio dedutivo isto leva a Px A prova por contradicao e baseada nos seguintes passos a Suponha que existe um elemento x U tal que Px Qx b Usando o mesmo raciocınio dedutivo isto leva a contradicao Px Px 53 Relacao entre prova por contradicao e prova por contraposicao Na prova por contraposicao a afirmacao x U se Px entao Qx e provada apresentando uma prova direta da afirmacao equivalente x U se Qx entao Px Este tipo de prova segue os seguintes passos a Suponha que x e um elemento arbitrario de U tal que Qx b Atraves do raciocınio dedutivo isto leva a Px A prova por contradicao e baseada nos seguintes passos a Suponha que existe um elemento x U tal que Px Qx b Usando o mesmo raciocınio dedutivo isto leva a contradicao Px Px 53 Relacao entre prova por contradicao e prova por contraposicao Exemplo Teorema Para todo inteiro n se n2 e par entao n e par Demonstracao por contradicao Suponha por contradicao que exista um inteiro n tal que n2 e par e n e ımpar Devese chegar a uma contradicao Ja que n e ımpar n2 que e o produto n n e tambem ımpar Isto contradiz a suposicao que n2 e par Logo as proposicoes Pn n2 e par e Pn n2 e ımpar sao verdadeiras ao mesmo tempo o que e uma contradicao 54 Relação entre prova por contradição e prova por contraposição Exemplo Prova por contraposição É fácil saber que conclusão deve ser provada negação da hipótese Não é necessário obter a negação da afirmação Só pode ser usado para afirmações com quantificadores existencial ou universal Prova por contradição A prova termina assim que é achada uma contradição Esta técnica aplicase a declarações gerais sejam elas quantificadas ou nãoquantificadas A negação da afirmação é mais complexa Pode ser mais difícil achar o caminho da prova Provas de condicionais Estas tecnicas sao as mais comumente usadas para condicionais Prova Direta Prova por Contraposicao Prova por Contradicao 56 Sentencas NaoQuantificadas Prova por Contradicao Reducao ao Absurdo 57 Demonstracao de Proposicoes NaoQuantificadas por Contradicao Princıpios 1 Suponha que a afirmacao a ser provada e falsa 2 Mostre que essa suposicao leva logicamente a uma contradicao 3 Conclua que a afirmacao a ser provada e verdadeira A razao pela qual esta tecnica de demonstracao e valida devese a seguinte equivalˆencia P P F P F P F Suponha que podemos encontrar uma contradicao q tal que p q e verdadeira Como q e falsa mas p q e verdadeira podemos concluir que p e falsa o que significa que p e verdadeira A dificuldade nesta tecnica pode ser expressa nesta pergunta Como podemos encontrar uma contradicao q que possa nos ajudar a provar que p e verdadeira 58 Prova por Contradicao Teorema 2 e irracional Demonstracao Suponha por contradicao que 2 e um numero racional Pela definicao de numero racional 2 pode ser escrito como uma fracao de inteiros Entao sejam a e b inteiros tais que 2 ab onde b 0 e a e b nao tˆem fator comum a fracao ab e irredutıvel Aqui estamos usando o fato de que todo numero racional pode ser escrito em uma fracao irredutıvel Elevando ambos os membros da equacao ao quadrado seguese que 2 a2b2 Portanto 2b2 a2 Pela definicao de numero par a2 e par Podemos usar o fato de que se a2 e par entao a e par o qual segue do teorema anterior provado em aula 59 Prova por Contradicao Teorema 2 e irracional Demonstracao Suponha por contradicao que 2 e um numero racional Pela definicao de numero racional 2 pode ser escrito como uma fracao de inteiros Entao sejam a e b inteiros tais que 2 ab onde b 0 e a e b nao tˆem fator comum a fracao ab e irredutıvel Aqui estamos usando o fato de que todo numero racional pode ser escrito em uma fracao irredutıvel Elevando ambos os membros da equacao ao quadrado seguese que 2 a2b2 Portanto 2b2 a2 Pela definicao de numero par a2 e par Podemos usar o fato de que se a2 e par entao a e par o qual segue do teorema anterior provado em aula 59 Prova por Contradicao Continuacao da Demonstracao Mas se a e par pela definicao de numero par a 2c para algum inteiro c Entao 2b2 a2 implica que 2b2 4c2 Dividindo ambos os membros dessa equacao por 2 temos b2 2c2 Pela definicao de par isso significa que b2 e par Novamente usando o fato de que se o quadrado de um inteiro e par entao o inteiro tambem deve ser par concluımos que b deve ser par tambem Portanto ter assumido que 2 e racional nos levou a equacao 2 ab em que a e b nao tˆem fator comum mas a e b sao pares Isto e uma contradicao Como a afirmacao 2 e racional nos levou a uma contradicao entao ela deve ser falsa Ou seja a sentenca 2 e irracional e que e verdadeira Portanto provamos que 2 e irracional 60 Provas de Equivalência Provas de Equivalˆencia Como provar sentencas da forma p q Para demonstrar um teorema que e uma sentenca bicondicional mostramos que p q e q p sao ambas verdadeiras A validade desse metodo segue da seguinte equivalˆencia logica p q p q q p 62 Prova de Equivalˆencias Exemplo 1 Teorema Se n e um inteiro entao n e par se e somente se n2 e par 1 Instanciacao Universal Seja c um inteiro qualquer 2 Desenvolvimento Provaremos que c e par c2 e par A fim de provar esse bicondicional devemos provar que c e par c2 e par e que c2 e par c e par Ambas as implicacoes ja foram provadas em slides anteriores Portanto como provamos que ambas c e par c2 e par e c2 e par c e par sao verdadeiras mostramos que c e par c2 e par 3 Generalizacao Universal Como provamos a propriedade para um inteiro qualquer a propriedade vale para todos os inteiros 63 Prova de Equivalˆencias Exemplo 1 Teorema Se n e um inteiro entao n e par se e somente se n2 e par 1 Instanciacao Universal Seja c um inteiro qualquer 2 Desenvolvimento Provaremos que c e par c2 e par A fim de provar esse bicondicional devemos provar que c e par c2 e par e que c2 e par c e par Ambas as implicacoes ja foram provadas em slides anteriores Portanto como provamos que ambas c e par c2 e par e c2 e par c e par sao verdadeiras mostramos que c e par c2 e par 3 Generalizacao Universal Como provamos a propriedade para um inteiro qualquer a propriedade vale para todos os inteiros 63 Prova de Equivalˆencias Exemplo 2 Teorema As seguintes sentencas sobre o inteiro n sao equivalentes p1 n e par p2 n 1 e ımpar p3 n2 e par Demonstracao Note que basta mostrar que os condicionais p1 p2 p2 p3 e p3 p1 sao verdadeiros Para mostrar p1 p2 usamos demonstracao direta Suponha que n e par Entao n 2k para algum inteiro k Consequentemente n 1 2k 1 2k 1 1 1 2k 1 1 Isso significa que n 1 e ımpar pois e da forma 2m 1 em que m k 1 64 Prova de Equivalˆencias Exemplo 2 Teorema As seguintes sentencas sobre o inteiro n sao equivalentes p1 n e par p2 n 1 e ımpar p3 n2 e par Demonstracao Note que basta mostrar que os condicionais p1 p2 p2 p3 e p3 p1 sao verdadeiros Para mostrar p1 p2 usamos demonstracao direta Suponha que n e par Entao n 2k para algum inteiro k Consequentemente n 1 2k 1 2k 1 1 1 2k 1 1 Isso significa que n 1 e ımpar pois e da forma 2m 1 em que m k 1 64 Prova de Equivalˆencias Exemplo 2 Continuacao da Demonstracao Para mostrar p2 p3 usamos demonstracao direta Suponha que n 1 e ımpar Entao n 1 2k 1 para algum inteiro k Portanto n 2k 2 e isto implica que n2 2k 22 4k2 8k 4 22k2 4k 2 Logo n2 e par pois e da forma 2m sendo m 2k2 4k 2 Para mostrar p3 p1 usamos demonstracao por contraposicao Ou seja provamos que se n nao e par entao n2 nao e par Isso e o mesmo que demonstrar que se n e ımpar entao n2 e ımpar o que ja demonstramos em slides anteriores Isso completa a demonstracao 65 FIM