[obm-l] Re: [obm-l] Re: [obm-l] Indução forte vs fraca
Entendi Ralph, sua explicação respondeu minhas dúvidas! Abraço. Em 17 de junho de 2017 11:34, Israel Meireles Chrisostomo < israelmchrisost...@gmail.com> escreveu: > Muito obrigado gente!Vcs me ajudaram muito! > Abraços > > Em 17 de junho de 2017 11:07, Ralph Teixeira escreveu: > >> Sim, isso eh uma demonstracao valida por inducao finita! Na minha >> opiniao, nem precisa formalizar muito mais -- a IDEIA da inducao como voce >> propos eh bastante comum, entao dah para escrever direto algo como voce >> disse, assim: >> >> a) Provo P(1) e P(2); >> b) Provo que P(k-1) e P(k) implicam P(k+1) para k=2,3,4,... >> c) Por inducao, P(n) estah demonstrado para n=1,2,3,... >> >> Agora, se voce realmente quiser encaixar num dos moldes formais (repito, >> acho que nao precisa, eu nao escreveria como abaixo), voce pode pensar de >> dois jeitos: >> >> i) Eh uma inducao fraca, cuja proposicao eh Q(n) = "P(n) e P(n+1)". >> >> De fato, para provar que vale Q(n) para todo n natural positivo, voce tem >> que: >> -- Mostrar Q(1) -- isto eh, mostrar P(1) e P(2); >> -- Mostrar que, para todo k>=2, Q(k-1) implica Q(k) -- isto eh, mostrar >> que (P(k-1) e P(k)) implica (P(k) e P(k+1))... Mas eh obvio que P(k) >> implica P(k), entao fica faltando apenas mostrar P(k+1), que eh o que voce >> fez. >> >> ii) Eh uma inducao forte, cuja proposicao eh P(n) mesmo. >> >> -- Mostre P(1); >> -- No passo de inducao, voce quer mostrar que "P(1) e P(2) e ... e P(k)" >> implica P(k+1) onde k=1,2,3, Vamos dividir em dois casos: >> k=1: para mostrar que P(1) implica P(2), podemos mostrar direto que >> P(2) vale. Ok, isso mostra a implicacao! >> k>=2: Claramente, "P(1) e P(2) e... e P(k)" implica "P(k-1) e >> P(k)"... Como voce mostrou que "P(k-1) e P(k)" implica P(k+1), voce >> completou o passo de inducao! Em suma, o fato de terem "sobrado hipoteses" >> no passo de inducao nao eh obstaculo! >> >> Abraco, Ralph. >> >> 2017-06-16 20:49 GMT-03:00 Israel Meireles Chrisostomo < >> israelmchrisost...@gmail.com>: >> >>> Eu estava tentando provar uma coisa aqui por indução.E gostaria de saber >>> uma coisa, fazendo o caso base de indução para k=1 e k=2, e, se como >>> hipótese de indução eu admitir que P(k) e P(k-1) é verdadeiro e conseguir, >>> a partir dessas duas hipóteses, provar que P(k+1) é verdadeiro, então isso >>> é uma prova válida?Se sim, esse seria um caso de indução forte?Ou indução >>> forte tem que ser necessariamente P(k) , P(k-1),...,P(1)? >>> >>> -- >>> Esta mensagem foi verificada pelo sistema de antivírus e >>> acredita-se estar livre de perigo. >> >> >> >> -- >> Esta mensagem foi verificada pelo sistema de antivírus e >> acredita-se estar livre de perigo. >> > > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Indução forte vs fraca
Muito obrigado gente!Vcs me ajudaram muito! Abraços Em 17 de junho de 2017 11:07, Ralph Teixeira escreveu: > Sim, isso eh uma demonstracao valida por inducao finita! Na minha opiniao, > nem precisa formalizar muito mais -- a IDEIA da inducao como voce propos eh > bastante comum, entao dah para escrever direto algo como voce disse, assim: > > a) Provo P(1) e P(2); > b) Provo que P(k-1) e P(k) implicam P(k+1) para k=2,3,4,... > c) Por inducao, P(n) estah demonstrado para n=1,2,3,... > > Agora, se voce realmente quiser encaixar num dos moldes formais (repito, > acho que nao precisa, eu nao escreveria como abaixo), voce pode pensar de > dois jeitos: > > i) Eh uma inducao fraca, cuja proposicao eh Q(n) = "P(n) e P(n+1)". > > De fato, para provar que vale Q(n) para todo n natural positivo, voce tem > que: > -- Mostrar Q(1) -- isto eh, mostrar P(1) e P(2); > -- Mostrar que, para todo k>=2, Q(k-1) implica Q(k) -- isto eh, mostrar > que (P(k-1) e P(k)) implica (P(k) e P(k+1))... Mas eh obvio que P(k) > implica P(k), entao fica faltando apenas mostrar P(k+1), que eh o que voce > fez. > > ii) Eh uma inducao forte, cuja proposicao eh P(n) mesmo. > > -- Mostre P(1); > -- No passo de inducao, voce quer mostrar que "P(1) e P(2) e ... e P(k)" > implica P(k+1) onde k=1,2,3, Vamos dividir em dois casos: > k=1: para mostrar que P(1) implica P(2), podemos mostrar direto que > P(2) vale. Ok, isso mostra a implicacao! > k>=2: Claramente, "P(1) e P(2) e... e P(k)" implica "P(k-1) e > P(k)"... Como voce mostrou que "P(k-1) e P(k)" implica P(k+1), voce > completou o passo de inducao! Em suma, o fato de terem "sobrado hipoteses" > no passo de inducao nao eh obstaculo! > > Abraco, Ralph. > > 2017-06-16 20:49 GMT-03:00 Israel Meireles Chrisostomo < > israelmchrisost...@gmail.com>: > >> Eu estava tentando provar uma coisa aqui por indução.E gostaria de saber >> uma coisa, fazendo o caso base de indução para k=1 e k=2, e, se como >> hipótese de indução eu admitir que P(k) e P(k-1) é verdadeiro e conseguir, >> a partir dessas duas hipóteses, provar que P(k+1) é verdadeiro, então isso >> é uma prova válida?Se sim, esse seria um caso de indução forte?Ou indução >> forte tem que ser necessariamente P(k) , P(k-1),...,P(1)? >> >> -- >> Esta mensagem foi verificada pelo sistema de antivírus e >> acredita-se estar livre de perigo. > > > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Indução forte vs fraca
Sim, isso eh uma demonstracao valida por inducao finita! Na minha opiniao, nem precisa formalizar muito mais -- a IDEIA da inducao como voce propos eh bastante comum, entao dah para escrever direto algo como voce disse, assim: a) Provo P(1) e P(2); b) Provo que P(k-1) e P(k) implicam P(k+1) para k=2,3,4,... c) Por inducao, P(n) estah demonstrado para n=1,2,3,... Agora, se voce realmente quiser encaixar num dos moldes formais (repito, acho que nao precisa, eu nao escreveria como abaixo), voce pode pensar de dois jeitos: i) Eh uma inducao fraca, cuja proposicao eh Q(n) = "P(n) e P(n+1)". De fato, para provar que vale Q(n) para todo n natural positivo, voce tem que: -- Mostrar Q(1) -- isto eh, mostrar P(1) e P(2); -- Mostrar que, para todo k>=2, Q(k-1) implica Q(k) -- isto eh, mostrar que (P(k-1) e P(k)) implica (P(k) e P(k+1))... Mas eh obvio que P(k) implica P(k), entao fica faltando apenas mostrar P(k+1), que eh o que voce fez. ii) Eh uma inducao forte, cuja proposicao eh P(n) mesmo. -- Mostre P(1); -- No passo de inducao, voce quer mostrar que "P(1) e P(2) e ... e P(k)" implica P(k+1) onde k=1,2,3, Vamos dividir em dois casos: k=1: para mostrar que P(1) implica P(2), podemos mostrar direto que P(2) vale. Ok, isso mostra a implicacao! k>=2: Claramente, "P(1) e P(2) e... e P(k)" implica "P(k-1) e P(k)"... Como voce mostrou que "P(k-1) e P(k)" implica P(k+1), voce completou o passo de inducao! Em suma, o fato de terem "sobrado hipoteses" no passo de inducao nao eh obstaculo! Abraco, Ralph. 2017-06-16 20:49 GMT-03:00 Israel Meireles Chrisostomo < israelmchrisost...@gmail.com>: > Eu estava tentando provar uma coisa aqui por indução.E gostaria de saber > uma coisa, fazendo o caso base de indução para k=1 e k=2, e, se como > hipótese de indução eu admitir que P(k) e P(k-1) é verdadeiro e conseguir, > a partir dessas duas hipóteses, provar que P(k+1) é verdadeiro, então isso > é uma prova válida?Se sim, esse seria um caso de indução forte?Ou indução > forte tem que ser necessariamente P(k) , P(k-1),...,P(1)? > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.