Demonstração é o ato de mostrar que uma afirmação é verdadeira a partir de afirmações já estabelecidas como verdade. Na prática, podemos distinguir entre demonstrações formais, que seguem regras lógicas estritas, e demonstrações informais, que acabam sendo rigorosas o suficiente para a matemática, mas com uma apresentação menos mecânica.
Observação importante: quando uma inferência não é válida, apresentamos um contraexemplo para mostrar a falsidade da hipótese. Um contraexemplo é um caso específico que quebra a conjectura. Exemplos comuns:
Um contraexemplo típico é:
Demonstração por exaustão: verifica-se o enunciado caso a caso em um domínio finito. Ex.: provar que para N ∈ {1,2,3,4,5}, N² ≤ 10 + 5N. Se a conjectura falhar para algum N, a demonstração por exaustão não é válida para todos os inteiros positivos.
A demonstração direta parte de hipóteses (premissas) e, por meio de regras de inferência, chega a uma conclusão. Exemplo:
Se x e y são inteiros pares, então xy é par. Escrevemos x = 2a e y = 2b, logo xy = 4ab, que é múltiplo de 2, ou seja, par.
Demonstração por contraposição: provar P ⇒ Q por meio da negação de Q, levando à negação de P, ou seja, mostrar que ¬Q ⇒ ¬P. Ex.: se x² é ímpar, então x é ímpar. Para provar por contraposição, assume-se que x é par (¬Q) e deduz-se que x² é par (¬P), e depois volta-se à conclusão de Q.
Demonstração por absurdo (ou por contradição): assume-se que a afirmação é falsa e mostra-se que isso leva a uma contradição. Ex.: se sqrt(2) fosse racional, então poderia ser expresso como p/q com gcd(p,q)=1; chegaríamos à contradição de que 2 divides ambos, impossibilitando gcd(p,q)=1.
Demonstração por implicação (condicional) com p ⇒ q: as regras (inclui contraposição, etc.) são usadas para estruturar a prova da implicação.
Demonstração por exaustão em domínio infinito não é possível na prática, pois não é viável verificar todos os casos. Contudo, técnicas como inspeção de padrões, invariantes, ou divisões em casos estratégicos ajudam a vencer esse obstáculo.
Exemplos práticos ajudam a entender cada técnica. Abaixo, apresentamos uma sequência breve para fixar as ideias:
Resposta correta: A) Demonstração direta
Explicação: a demonstração direta parte da hipótese e utiliza regras de inferência para obter a conclusão, sem recorrer à negação da conclusão ou a contradições.
Resposta correta: C) ¬Q ⇒ ¬P
Explicação: P ⇒ Q é logicamente equivalente a ¬Q ⇒ ¬P (lei da contraposição).
Resposta correta: B) Contraposição
Explicação: para provar “se x² é ímpar, então x é ímpar”, costuma-se usar contraposição: se x é par, então x² é par. A demonstração direta seria menos direta nesse caso, mas a contraposição facilita o caminho.
Resposta correta: A) Demonstração direta usando cadeia de inferência
Explicação: a passagem de P ⇒ Q e Q ⇒ R leva a P ⇒ R por transitividade da implicação; uma demonstração direta pode encadear as implicações para obter a conclusão.
Olá, alunas e alunos do curso de Fundamentos Matemáticos para Computação.
Nesta video aula, eu vou falar de técnicas de demonstração, começando pelas demonstrações informais, seguido pelas técnicas de demonstração direta, com a oposição e a pessoa.
Para falar de demonstração, seja um éo informais, precisamos ter a ideia de teoremas.
Teorema é uma afirmação que pode ser provada como verdadeira por meio de afirmações já demonstradas.
De certa forma, nas aulas anteriores, nós já vimos provando teoremas.
Nós vimos partindo de hipóteses, cheguei inferindo resultados válidos até chegar determinada conclusão, também válida para um certo domínio.
Então, basicamente, dá do T, impliquem que esse perforver da deiro e provarmos que que também o será, então essa implicação se torna a verdadeira.
E aí temos um teoreno.
Então, o teoreno é um santo provado, só que agora, nós vamos ver que teoremas podem ser provados de modo menos formal do que o que estavam fazendo antes usando a lógica proposicional e a lógica de criticados.
Ou seja, nós vamos ver uma maneira mais informal de estar apresentando essas demonstrações, mas sem fugir de formalismo matemático, coerente.
Mas antes disso tudo, nós vamos começar pelo fato de quando não é válido.
Quando não é válido em um argumento, nós derrubamos eles uma das melhorias mais fáceis de se ver o barril e através de um ponto de exemplo.
Para mostrar que aquela congictura, que aquele argumento, ele é falso.
Então, por exemplo, se alguém afema que todos os animais que vivem no senão são peixes, basta você apontar que baléia é um mamífero, então, e não, logo não é peixe, isso é um encontre exemplo.
Mais do que suficiente.
Se alguém diz que todo inteiro, menor do que 10, é maior do que 5, você pode falar que 2 já é um encontre exemplo, 2 é menor que 10 e 2 não é maior que 5, apesar de desistir em outros encontre exemplos possíveis.
Então, basta um encontre exemplo para mostrar que uma congictura é falso.
Então, para todo inteiro, por exemplo, considerando aqui, para todo inteiro positivo, N, N factorial é menor, é igual que N², bom, você pode tentar verificar isso.
Considerando todo inteiro positivo para N igual a 1, você vai verificar que vem da deiro para N igual a 2, é verdadeiro, N igual a 3 também.
Só que quando chegar em N igual a 4, temos um encontre exemplo.
O problema aí é que se N igual a 4 continua a se vale, daí você fosse tentar fazer isso até quando.
Então, essa situação de você trovar quando encontre exemplo é legal, é interessante quando não é muito complicado, você definisse quando treze na época.
Tem também a situação da demonstração informal que seria a demonstração por exaustão.
Então, por exemplo, para qualquer inteiro positivo, N igual a 5, quadrado do inteiro, N igual a soma de 10 com 5 vezes 2.
Então, representando isso matemáticamente, temos N² menor que 10, mais 5 vezes N.
Considerando, para qualquer inteiro positivo, o que vai menor ou igual a 5? Observe que nós temos um domínio muito bem definido e um domínio formado por uma coleção de valores bem limitada.
Isso significa que podemos verificar caso a caso.
Esse é o escopo da demonstração por exaustão.
Mas, verificamos caso a caso se aquela conjectura é válida.
Verificamos aqui para N igual a 1 é válida, para N igual a 2, para N igual a 3, também é válida, para N igual a 4 e N igual a 5.
Ou seja, essa conjectura é válida para qualquer inteiro positivo menor ou igual a 5, que é o que estava aqui estabelecido.
Só que se alguém tenta generalizar e falar para qualquer inteiro positivo, o quadrado do inteiro é menor ou igual a soma de 10 vezes com 5 vezes o inteiro, isso já implica.
Se eu fotei agora, continuando a linha da demonstração por exaustão, primeiro que não dá, porque para qualquer inteiro positivo estamos falando aqui de uma coleção inimitada de valores.
Mas nesse caso, felizmente, a gente encontra o encontro exemplo em N igual a 7, então logo nos deparamos pelo encontro, que mostram que para qualquer inteiro positivo, essa conjectura se torna falsa.
Mas se eu tivesse que provar isso e não fosse tão trivial assim por exaustão encontrar o encontro exemplo, eu tenho técnico, eu acho que me permite provar para qualquer valor, se aquela conjectura vai ser válida ou não.
Nesse caso, felizmente, para N igual a 7, nós já encontramos um encontro exemplo.
Então, a primeira técnica para provar para uma situação em que você não está num domínio finito e que você pode exaustivamente verificar todos os casos, uma primeira técnica é a demonstração direta.
Então, nós temos uma hipótese e dela, vamos deduzir uma conclusão, uma tese.
É o tipo de demonstração que já vim nos fazendo das aulas anteriores.
Então, por quê? Porque nós estabelecemos uma sequência de demonstração, de demonstração, partindo de um noipotense e chegando numa conclusão através daquelas regras de inferência, regras de equivalência lógica que vimos.
Aqui nós vamos ver isso agora de uma forma menos formal, como vimos na lógica proposicional e de predicado.
Supõe, então, que se x é um inteiro par y, o inteiro par, então o produto de xy é um inteiro par.
Como é que nós vamos demonstrar isso? Primeiro passo, identificar a hipótese e a tese.
X é um inteiro par, y é um inteiro par, é uma tese.
Então, tem duas proposições combinadas com um conectivo e, só que eu preciso escrever isso, que eu posso, por exemplo, deixar dessa forma.
E xy é um inteiro par.
Essa seria uma tese.
Bom, mas nesse caso, para facilitar meu rassossino, é interessante representar matematicamente.
Então, eu tenho que x é um múltiplo de 2, duas vezes a, um dia a um inteiro, para representar que é par.
Mesmo a coisa pro y, vai ser um múltiplo de 2, o que é um inteiro, e o x vezes y também é par, ou seja, múltiplo de 2 considerando c aqui no valor inteiro.
Bom, agora para demonstrar usando a demonstração direta, eu parto da hipótese, que é essa combinação x é inteiro par, y é inteiro par, para chegar na tese.
Só que eu já vou fazer isso usando a linguagem a representação matemática.
Então, substituo x vezes y por 2 a vezes 2b, que é nada mais nada menos do que pensar isso aqui considerando o 2 multiplicando o que vem depois, a vezes 2 vezes b, que é um inteiro, porque o produto de 3 inteiro já resulta um inteiro, e dessa forma, eu tenho que x vezes y vai resultar sempre num número par, porque eu considerei dois valores pares com a esquerda.
Dessa forma, se o produto é par, eu provei a minha tese.
Certo, usando a demonstração direta, porque partida hipótese para chegar na tese.
Um outro exemplo, se o inteiro foi divisível por 6, então o dobro desse inteiro será divisível por 4.
Novamente, usando a demonstração direta, eu identifico a hipótese, que é x é divisível por 6, que significa o quê? Que x é um múltiplo de 6, ou seja, x é 6 vezes a a inteiro.
O dobro desse inteiro tem que ser divisível por 4, ou seja, duas vezes esse inteiro tem que ser um múltiplo do número 4.
E aí, como é que eu vou provar isso? Eu parto da hipótese que x é um múltiplo divisível por 6, certo? Multiplico por 2 e esse x verifica o que eu obtém 12 do outro lado, mas o que é o 12? 4 vezes 3, ou seja, eu tenho que 2 vezes x é igual a 4 vezes 1 valor k, que é inteiro, que é esse 3 vezes a.
Logo, eu tenho que prum x múltiplo de 6 quais quer, duas vezes x também vai ser, vai ser um múltiplo do número 4, vai ser divisível por 4.
Dessa forma, eu provei a minha tese, por demonstração direta.
Na demonstração por contracosição, eu faço o quê? Eu assume que se tem impliquem, que eu posso provar, que negava impliquem pernegado, porque muitas vezes é mais fácil esse caminho.
Então, saindo do múltiplo para chegar na tese, passa a ser, às vezes mais fácil negar a tese, chegar na hipótese.
Só que isso eu posso fazer, porque é uma equivalência autológica, por favor, monta em a tabela de verdade e verifique essa equivalência autológica.
Vamos ao exemplo, se o quadrado de um inteiro for impar, então o inteiro terá que ser impar.
Observe que a minha hipótese é o quadrado de um inteiro impar, e a minha tese é que esse inteiro é impar.
Saí daqui e chegar até que, quando a demonstração direta pode ser complicado, calcou uma raiz, eu vou ter que decompor o x, então é mais fácil pensar essa demonstração negando, eu nego o p, que seria, se o quadrado de um inteiro, ele não é impar, significa que ele vai ser par.
E se o inteiro não é par, não é impar, ele vai ser par.
Dessa maneira, agora eu posso chegar a partir da minha tese negada e chegar na hipótese negada por contraposição.
Então, demonstrando por contraposição, eu tenho que dado que x é igual a 2b, que é a negação da minha tese, se eu elevar só o quadrado, eu tenho 4b², que nada mais é do que 2 vezes 2b², ou seja, 2 vezes k, x² também é um número par.
Logo, eu provei negando agora, chegando à conclusão da minha hipótese negada.
Então, eu tenho aqui uma transação por contraposição.
Vamos agora analisar o caso em que temos um 6 somente c, como um exemplo também de como podemos usar a contraposição.
Então, nesse caso, lembrando, 6 somente c, significa b conditional, ou seja, tem pliqui em k e que impliqui em p.
Isso significa que temos que provar sentanças, onde aparece 6 somente c, considerando a ida e a volta do b conditional.
Para fazer isso, nesse exemplo aqui, nós temos que considerar, por exemplo, porque eu vou ter um p que pode ser o meu x vezes y, o produto, né, é um número impar, e considerando que x é impar e y é impar.
Bom, nesse caso, para fazer a ida, eu supo, então, que eu tenho, dado que o produto impar, eu quero chegar com a conclusão, que é impar e y é impar, porque se o produto de x e y será impar, então, desmembrando aqui o 6 somente c, x e y estão com x quanto y são impas, é o e.
Bom, para eu provar isso, fica mais fácil por contraposição, porque a contraposição que negada vai tornar isso aqui, no o, com x para y.
E a minha hipótese se torna chegar no produto x e y igual a impar.
Eu tenho que chegar nessa hipótese negada, então, x e y agora tem que ser par.
Então, o que eu vou fazer? Eu parto que x é impson, eu tenho como hipótese que é o que é negado, que x é par ou y é par.
Considerando x par, eu vou ter aqui facilmente que b vezes y é o meu car, então, eu tenho que o meu produto é par.
Ah, mas eu podia ter suposto y igual a c, tudo bem, igual a 2c, tudo bem.
Eu colontrocando agora considerando nesse ô, que eu tivesse assumido que o y era par, a mesma coisa, ainda continuo obtendo x e y par.
Então, eu provei usando contraposição que se dado que esse produto é impar, então, cada termo tem que ser impar.
Certo? Bom, agora, eu fiz a hídr, eu tenho que fazer a volta.
No caso da volta, fica mais fácil, porque aí se torna x é impar, e y é impar, implicando em x e y, impar.
Aí, nesse caso, eu parto da hipótese que x e y são impar, multiplico eles e verifica o que o resultado desse produto é impar, basta colocar o 2 em evidência aqui, já tinha um sobrando, e eu chego que o produto é impar.
Provei nesse caso, com demonstração, nesse sábol, eu demonstrei usando a demonstração direta, partindo da hipótese e chegando na tese.
Bom, na demonstração, por absurdo, o que eu vou fazer? Eu tenho que agora pensar no seguinte, que dado a minha hipótese e a minha conclusão, eu vou fazer o seguinte, eu mantenho a hipótese, e eu digo, não, sei hipótese é verdadeira, essa conclusão aqui é furada, ela é falsa.
Se isso acontece e isso aqui que eu estou dizendo, foi verdade, esse hipótese tem que me levar em algo falso, porque p implica em quê? Se eu estou dizendo que p ocorre, que não ocorre, isso aqui teria que ser falso, então eu tenho que ter uma conclusão, uma algo que é contraditória, que é uma invernidade, então essa é a demonstração por absurdo ou contradição.
Para provar que algo não é verdade, você geralmente lança muito mão da demonstração por absurdo.
Por exemplo, se um número somado é ele mesmo, for igual a ele mesmo, então esse número será zero, parece complicado, não é? Se um número somado a ele mesmo for igual a ele mesmo, então esse número é zero.
Bom, na verdade, olhando isso aqui, a gente vê que a demonstração matemática é bem simples e que o fato de ele ser zero é bem óbvio, mas justamente por ser muito óbvio provar que isso é verdade, venha de rica, provar que algo não é verdade, geralmente é mais fácil por absurdo, então por exemplo, nesse caso, aqui o que eu vou fazer? Eu vou ter que a minha tese é que esse número será zero, que o meu x é zero.
Então o que eu vou fazer para provar isso por absurdo? Eu vou assumir peike negado implicando em algo que é falso.
Mi potes e passa a cp que negado, ou seja, x mais x é igual a x, eu estou supondo que não, isso aqui acontece e o meu x é diferente de zero.
Eu vou ter uma contradição aí, vamos provar isso.
A minha tese representada por esse zero significa que eu vou chegar em algo falso, em algo contraditoro.
Então o que vai acontecer nesse caso? Eu vou partir da Mi potes e aí o que eu faço? Eu para chegar nessa tese, eu começo a fazer as contas, bom, escolhe uma hipótese, a estratégia em geral, você escolhe uma hipótese de modo que você tenha que, em algum momento, assumindo essa outra hipótese, você percebe que você é elevado a um absurdo, logo falso.
Então vamos assumir isso aqui como verdade, isso aqui foi verdadeiro, você já devem ter visto até na internet algumas demonstrações desse tipo.
Se eu somar, eu tenho que 2x igual a x, bom, aí eu divido por x, beleza? Posso dividir porque por hipótese x é diferente de zero.
Dividindo, eu chego na brilhante conclusão matemática de que 2 é igual a 1, o que é a absurdo é falso.
Eu cheguei nesse absurdo porque eu assumi essa hipótese aqui, que é errada.
Isso demonstra que isso aqui não pode acontecer.
Então essa minha demonstração aqui, ela caiu em algum falso que prova, então que só se vai ser válido para x igual a zero.
Um outro exemplo aqui provar que raiz de 2 não é um número racional.
Então vamos lá demonstrar por absurdo.
Supõe que raiz de 2 é racional.
O que significa um número ser racional? Significa que ele pode ser representado por uma fração cujo numerador e o denominador são inteiros indivisíveis.
Bom, óbvio para um denominador diferente de zero.
O que vai acontecer nesse caso? Se eu tenho repare que agora o que vai acontecer? Eu estou assumindo que na minha demonstração por absurdo, que eu quero provar que ele não é um número racional, então por absurdo eu assumo que ele seja racional.
Eu estou negando até negando o meu quê? Tu sou um assunto, isso.
Vamos ver onde que eu chego.
Eu tenho essa relação na temática.
Que se eu elevar o quadrado, eu acho que eu tenho o quadrado de um inteiro dividido pelo quadrado de outro inteiro.
O que me leva a essa relação aqui? Essa relação, nada mais é do que eu estar chevando o fato de que dois divide pi ao quadrado.
Se dois divide pi ao quadrado, dois vai ser um fator do número P.
Isso significa que P pode ser representado como um múltiplo de 2.
Eu estou usando aqui a letra X como um inteiro qualquer para representar que P é um múltiplo de 2, ou seja, 2 é um fator de P.
Se isso acontece quando eu elevo P ao quadrado, lembrando que o P ao quadrado é igual a 2, que é o quadrado, eu vou ter uma relação que é 4x ao quadrado igual a 2, que é o quadrado.
Que me remete a 2x igual a que ao quadrado? Opa, eu caí em algo muito parecido com que eu tinha aqui para o P ao quadrado.
Agora o meu que é o quadrado é par.
Não, é múltiplo de 2.
Isso significa que o 2 divide o que é o quadrado, logo 2 divide o quê? Se isso acontece, isso significa que 2 é um fator comum de quê e P.
Então se eu tenho dois como fator de quê e dois como fator de P, P que não podem ser indivisíveis.
E aí está o absurdo da minha hipótese de poder querer representar um número irracional com um número racional.
Então eu tenho que a raiz de 2 não pode ser racional, não é racional, certo? Prove pro absurdo que o produto de 2 inteiros em par não é par.
Então vamos a folks a um e pro absurdo que o produto de 2 inteiros em par é par, o que significa isso? Que eu tenho que x é um, é impar, y, impar, mas o produto deles é par.
Bom, então eu estou tentando fazer uma demonstração pro absurdo.
Quando eu sigo por esse caminho, eu pego, vou fazer o produto de 2 números que é par, certo? Que é uma das minhas hipótese e outra hipótese agora que eu use, eu fato de x e plenção impar, fazendo a conta, eu chego aqui a conclusão que o produto desses dois caras que era impar, que são ímpares, dá um número impar, ou seja ele não vai ser igual um número par é pAlso.
Então a minha demonstração também está falsa.
Uma pessoa, essa foi a aula de hoje, todos os conceitos vão retirados da sessão 2 contando nosso material base, fundamentos matemáticos para a ciência da computação, muitos dos exemplos foram tirados de aula, eu espero que vocês tenham entendido nos vemos na próxima aula.