Fundamentos Matemáticos para Computação - Técnicas de Demonstração (Libras)

[Música] Olá alunas e alunos do curso de fundamentos de matemáticas para computação nesta videoaula eu vou falar de técnicas de demonstração começando pelas demonstrações informais seguido pelas técnicas de demonstração direta contraposição e absurdo bom para falar a respeito de demonstrações sejam elas informais nós precisamos ter a ideia de teoremas Teorema ele é 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 inferindo resultados válidos até chegar determinada conclusão também válida para um certo domínio bom então

basicamente dado T implica em que se P for verdadeiro e provarmos que que também o será Então essa implicação se torna verdadeira E aí temos um teorema então o teorema são provados só que agora né 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 predicados ou seja nós vamos ver qual é uma maneira mais mais informal de estar apresentando essas essas demonstrações mas sem fugir né de um 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 um argumento nós derrubamos eles uma das maneiras mais fáceis de Se derrubar ele é através de um contra exemplo tá para mostrar que aquela conjectura que aquele argumento ele é falso então por exemplo se alguém que todos os animais que vivem no oceano são peixes basta você apontar Que baleia é um mamífero então e não é logo não é peixe isso é um contra 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 contra exemplo 2 é menor que 10 e 2 não é maior que 5 né apesar de existir em outros contra exemplos possíveis então basta um contra exemplo para mostrar que uma conjectura é falsa tá então para todo inteiro por exemplo considerando aqui para todo inteiro positivo n n fatorial é menor ou igual que n² bom você pode tentar verificar isso considerando todo inteiro positivo para n = 1 você ver vai verificar que é verdadeiro para n = 2 é verdadeiro n = 3 também só que quando chega em N =

4 temos um contra exemplo o problema aí é que se N = 4 continuasse válida e você fosse tentar fazer isso até quando né Então essa situação é de você provar com contra exemplo é legal é interessante quando não é muito complicado você definir isso como por exemplo temos também a situação da demonstração informal que seria demonstração por exaustão então por exemplo para qualquer inteiro positivo menor ou igual a 5 quadrado do inteiro é menor ou igual a soma de 10 com 5 vezes inteiro então representando isso matematicamente temos n ao quadrado menor que 10

+ 5 x n considerando para qualquer inteiro positivo o que que 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 se aquela conjectura é válida verificamos aqui para n = 1 é válida para n = 2 para n = 3 que também é válida para N = 4 e n = 5 ou seja essa conjectura é válida para qualquer inteiro positivo menor

ou igual assim que é o que estava que 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 cinco vezes o inteiro isso já complica se eu for tentar agora continuar na linha da demonstração por exaustão primeiro que não dá porque é para qualquer inteiro positivo estamos falando aqui de uma coleção ilimitada de valores mas nesse caso felizmente a gente encontra um contra exemplo em n = 7 em n = 8 Então logo logo nos deparamos com contra exemplo

que mostra o que para qualquer inteiro positivo essa conjectura se torna falsa mas se eu tivesse que provar isso né e não fosse tão trivial assim por exaustão a encontrar um contra exemplo eu tenho técnicas que me permitem provar para qualquer valor se aquela conjectura vai ser válido ou não tá nesse caso felizmente para ele igual a 7 nós já encontramos um contra exemplo Então a primeira técnica para provar para uma situação em que você não tá 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á vimos fazendo nas aulas anteriores Então porque porque nós estabelecemos uma sequência de demonstração de demonstração partindo de uma hipótese chegando numa confusã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 né como vimos na lógica proporcional e te prejudicar suponha então que X é um inteiro para Y inteiro pá então o produto de X Y é um inteiro par como é que nós vamos

demonstrar isso primeiro passo identificar a hipótese a tese X é um inteiro par Y inteiro par é a minha tese Então eu tenho duas proposições combinadas com conectivo e só que eu não preciso escrever isso que eu posso por exemplo Deixar dessa forma e x y é um inteiro par essa seria a minha tese bom mas nesse caso para facilitar meu raciocínio é interessante representar matematicamente então eu tenho que X é um múltiplo de 2 duas vezes a um diário inteiro para representar que é par mesma coisa para o y vai ser um múltiplo duas

vezes B múltiplo de 2 onde B é um inteiro e o x vezes Y também é par ou seja múltiplo de dois considerando ser aqui um valor inteiro bom agora para demonstrar usando a demonstração direta eu parto da hipótese que é essa combinação x inteiro parir para chegar na testa só que eu já vou fazer isso usando a linguagem a representação matemática então substitui o x vezes Y por dois a esses dois b que é nada mais nada menos do que pensar isso aqui considerando dois multiplicando O que vem depois a vezes dois vezes B

que é um inteiro porque o produto de três inteiros já resultam inteiro k e dessa forma eu tenho que x vezes Y Vai resultar sempre no número par porque eu considerei dois valores pagos quaisquer dessa forma se o produto é par eu provei A Minha tese certo usando a demonstração direta Porque a partir da hipótese para chegar na tese um outro exemplo se um inteiro for 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 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 E aí como é que eu vou provar isso é eu parto da hipótese que X é um múltiplo de é divisível por 6 certo multiplico por 2 esse x verifico que eu obtenho 12 do outro lado mas o que que é o 12 4 x 3 ou seja eu tenho que duas vezes x é igual a 4 vezes

um valor k que é inteiro que é esse três vezes a logo eu tenho que para um X múltiplo de 6 quaisquer 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 contraposição eu faço o que eu assumo que se Temple que eu posso provar que quer negado implica em ter negado porque muitas vezes é mais fácil esse caminho então saindo de uma hipótese para chegar na tese chega 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 ta autológica por favor montanha a tabela verdade verifiquem essa equivalência tal tal lógica Vamos a um exemplo se o quadrado de um inteiro for ímpar então inteiro terá que ser ímpar observem que a minha hipótese é o quadrado de um inteiro é ímpar e a Minha tese é que esse inteiro é ímpar sair daqui e chegar até aqui com demonstração direta pode ser complicado porque eu vou calcular uma raiz eu vou ter que decompor o X então é mais fácil

pensar essa demonstração negando Eu nego 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 é ímpar ele vai ser pai dessa maneira agora eu posso chegar a partir da Minha tese negada e chegar na minha hipótese negada por contraposição então demonstrando por contraposição eu tenho aqui dado que x = 2B que A negação da Minha tese seu elevai só ao quadrado eu tenho quatro B ao quadrado que nada mais é do que duas vezes dois B ao quadrado

ou seja duas vezes k x ao quadrado 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 demonstração por contraposição vamos agora analisar o caso que temos um seis somente C como um exemplo também de como podemos usar contraposição Então nesse caso lembrando sei somente se significa o bico condicional ou seja bem amplique em que e quem implica em P Isso significa que temos que provar sentenças onde aparece seis somente ser considerado ainda e a volta do bico condicional para fazer isso nesse exemplo

aqui nós temos que considerar por exemplo que eu vou ter um p que pode ser o meu x vezes y o produto né é um número ímpar e considerando que X é ímpar e y é ímpar nesse caso para bem sem terço para fazer a ida eu Suponho então que eu tenho dado que o produto é ímpar eu quero chegar à conclusão porque é ímpar e y é ímpar porque se o produto de x y será ímpar então desmembrando aqui o seis somente seis x e y tanto x quanto Y são ímpares é um e

bom para eu provar isso fica mais fácil por contraposição porque a contraposição que negado vai tornar isso aqui um ou com x pare Y par e a minha hipótese se torna chegar no produto x y = ímpar eu tenho que chegar nessa hipótese negada então XY agora tem que ser par então o que que eu vou fazer eu parto que x vezes Y eu tenho como hipótese que é o que negado que X é par ou Y é par considerando x par eu vou ter aqui facilmente que vezes Y é o meu k Então eu

tenho que o meu produto é par Ah mas eu podia ter suposto y = c tudo bem igual a 2c tudo bem Eu como trocando agora considerando nesse outro que eu tivesse assumido que o y era par a mesma coisa Eu ainda continuo obtendo x y tá então eu provei usando contraposição que dado que esse produto tem limpa então cada termo tem que ser ímpar certo bom agora eu fiz a ida eu tenho que fazer a volta no caso da volta fica mais fácil porque aí se torna X em y e ímpar implicando em x

y ímpar aí nesse caso eu parto da hipótese que x e y são ímpares multiplico eles e verifico que o resultado desse produto é ímpar basta colocar o dois em evidência aqui já tinha um sobrando e eu chego que o produto é ímpar provei nesse caso por demonstração nesses volta eu demonstrei usando a demonstração direta partindo da hipótese 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 se a hipótese é verdadeira essa conclusão aqui é furada ela é falsa se isso acontece e isso aqui que eu tô dizendo for verdade esses hipótese tem que me levar em algo falso porque P implica em quê se eu tô dizendo que P ocorre que não ocorre isso aqui teria que ser falso Então tem que obter uma conclusão uma uma algo que é contraditório que é uma inverdade 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 então

por exemplo se um número somado a ele mesmo for igual a ele mesmo então esse número será zero parece complicado mas 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 dele ser zero é Bem óbvio mas justamente por ser muito Óbvio provar que vem a dica provar que algo não é verdade né geralmente é mais fácil por absurdo então por exemplo nesse caso aqui o que que

eu vou fazer eu vou ter que a minha tese é que esse número será 0 né que o meu X é 0 então o que que eu vou fazer para provar isso por absurdo né eu vou assumir tem que negado implicando em algo que é falso me hipótese passa a CPI negado ou seja x + x = x eu tô supondo que não ó isso aqui acontece e o meu X é diferente de zero eu vou ter uma contradição aí mas vamos provar isso A Minha tese representada por esse zero significa que eu vou chegar

em algo falso em algo contraditório então o que que vai acontecer nesse caso né eu vou partir da minha hipótese E aí o que eu faço eu para chegar nessa tese eu começo a fazer as contas bom escolha uma hipótese a estratégia em geral é você escolhe uma hipótese de modo que você tenha que em algum momento assumindo essa a outra hipótese você percebe que você é levado a um absurdo algo falso Então vamos assumir isso aqui como verdadeiro só que foi verdadeiro você já deve ter visto até na internet algumas demonstrações desse tipo se

eu somar eu tenho que dois x 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 dois é igual a um O que é um absurdo é falso eu cheguei nesse absurdo porque eu assumi essa hipótese aqui que é errada Isso demonstra o que isso aqui não pode acontecer então essa minha demonstração aqui ela caiu em algo falso que prova então que só vai ser válido para x = 0 um outro exemplo aqui provar que raiz de

2 não é um número racional Então vamos lá demonstrar por absurdo Suponha que raiz de 2 é racional O que 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 né bom Óbvio com denominador diferente de zero que que vai acontecer nesse caso se eu tenho repare que agora o que que vai acontecer eu tô assumindo né 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

tô negando a tese negando o meu que então se eu assumo isso vamos ver onde que eu chego eu tenho essa relação matemática que se eu levar ao quadrado faz com que eu tenho o quadrado de um inteiro dividido pelo quadrado de outro inteiro o que me leva é essa relação aqui essa relação nada mais é do que eu está chegando ao fato de que dois divide p² se dois divide o quadrado dois vai ser um fator do número p Isso significa que P pode ser representado como um múltiplo de dois eu tô usando aqui

a letra x como inteiro qualquer para representar que ter é um múltiplo de dois ou seja dois é um fator de p isso acontece quando eu elevo p² Lembrando que o p² é igual a 2 que é o quadrado eu vou ter uma relação que é 4x ao quadrado igual a 2 que é o quadrado quem me remete a 2x igual a que ao quadrado Opa eu caí em algo muito parecido com que eu tinha aqui para o p o quadrado agora o meu quadrado é par é múltiplo de 2 Isso significa que o dois

divide o que é o quadrado logo dois de vídeo que isso acontece isso significa que dois é um fator comum de que e p então se eu tenho dois como fator de q e 2 como fator de p p q não podem ser indivisíveis E aí tá o absurdo da minha hipótese de poder de querer representar um número irracional como um número racional então eu tenho que raiz de 2 não pode ser racional não é racional certo prove por absurdo que o produto de dois inteiros ímpares não é par Então vamos lá vamos assumir por

absurdo que o produto de dois inteiros ímpares é par que que significa isso que eu tenho que X é ímpar Y em ímpar mas o produto deles é par bom então eu tô tentando fazer uma demonstração por absurdo quando eu sigo por esse caminho eu pego vou fazer o produto de dois números que é par certo que é uma das minhas hipóteses e outra hipótese agora que eu uso é o fato de que x e y são ímpares fazendo a conta eu chego aqui a conclusão que o produto desses dois caras que era ímpar que

são ímpares dá um número ímpar ou seja ele não vai ser igual ao número par é falso então a minha demonstração também está falsa bom pessoal Essa foi a aula de hoje né eu todos os conceitos foram retirados da sessão 2.1 do nosso material básico fundamentos matemáticos para Ciência da Computação muitos dos exemplos foram tirados de lá desta aula eu espero que vocês tenham entendido nos vemos na próxima aula [Música]