3 - AULA 11

Prévia do material em texto

AULA Nº11
LÓGICA E MATEMÁTICA DISCRETA 
P.I.F e Boa Ordenação
Profa. Deborah M. Raphael
Princípio = Axioma
Princípio é o mesmo que axioma. Designam uma afirmação que é admitida como verdadeira e não será demonstrada.
O Princípio da Boa Ordenação é equivalente ao Princípio da Indução Finita. Admitindo um deles como verdadeiro, podemos provar o outro.
Princípio da Boa Ordenação
O Princípio da Boa Ordenação é equivalente ao Princípio da Indução Finita. Admitindo um deles como verdadeiro, podemos provar o outro.
Princípio da Boa Ordenação
Seja um subconjunto não vazio de . Então, existe um elemento tal que .
Ou seja, o Princípio da Boa Ordenação garante que todo subconjunto não vazio de tem mínimo.
Jogo de Nim
Jogo de Nim (uma versão). São dadas duas pilhas com o mesmo número de moedas. Uma jogada consiste em retirar moedas (pelo menos uma) de uma das pilhas. Os jogadores alternam suas jogadas. Vence quem retirar a última moeda.
Jogo de Nim
Vamos entender melhor a situação.
Dadas duas pilhas com uma moeda em cada, o primeiro jogador só pode retirar uma moeda de uma pilha e o segundo jogador ganha.
O que acontece com duas pilhas com duas moedas em cada?
Jogo de Nim
Representamos por 2-2 duas pilhas com duas moedas em cada. Depois do primeiro jogador fazer sua jogada, teremos uma das situações:
1-2 ou 0-2 (2-1 e 2-0 descrevem a mesma situação).
Caso 0-2: o segundo jogador joga 0-0 e vence.
Caso 1-2: o segundo jogador joga 1-1 e vence na próxima.
Jogo de Nim
Sequência de jogadas que garante a vitória do segundo jogador.
2-2
1-2
1-1
0-2
0-0
0-1
0-0
Jogo de Nim
Vamos chamar de o jogo que se inicia com duas pilhas com moedas cada. Acabamos de ver que, para e , o segundo jogador sempre consegue vencer.
Jogo de Nim
No jogo de Nim com duas pilhas com o mesmo número de moedas, o segundo jogador sempre consegue ganhar.
Prova. Vamos usar o Princípio da Boa Ordenação.
Jogo de Nim
Temos que provar que, para todo , o segundo jogador sempre consegue garantir sua vitória em . Consideramos o subconjunto dos , tais que o segundo jogador não consegue garantir sua vitória em . Queremos mostrar que . A prova será por contradição. Suponhamos que . Pelo Princípio da Boa Ordenação, existe . 
Jogo de Nim
Sabemos que . No jogo há duas jogadas possíveis para o primeiro jogador: retirar algumas ou todas as moedas de uma das pilhas. 
Se o jogador 1 retira uma pilha inteira, o jogador 2 retira a outra pilha e vence.
Jogo de Nim
Se o jogador 1 retira algumas moedas de uma das pilhas, o jogador 2 retira o mesmo número de moedas da outra pilha e restarão duas pilhas iguais, com moedas em cada. Ou seja, será como um jogo , com . 
Como é o mínimo elemento de , para , temos que . Logo, o segundo jogador consegue garantir sua vitória em . 
Jogo de Nim
Sequência de jogadas que garante a vitória do segundo jogador para o jogo 
m-m
k-m
k-k
0-m
0-0
Jogo de Nim
Conseguimos garantir a vitória do segundo jogador, mesmo iniciando com duas pilhas com moedas cada. Isso é uma contradição que vem do fato de termos suposto . Logo, e provamos que o segundo jogador sempre consegue ganhar.
Jogo de Nim
Algumas observações.
Repare que a demonstração fornece o modo como o segundo jogador pode ganhar. Basta “imitar” a jogada do primeiro.
Usando P.I.F (versão forte) você pode fazer essa prova de maneira bem parecida.
Exemplo
Prove que , para todo .
Prova por indução sobre . 
Caso inicial. Se , a igualdade vale pois
 e .
Exemplo
Passo de Indução.
Dado , devemos mostrar que se
 , então a fórmula também vale para . Ou seja, devemos mostrar que
.
 
 , 
o que mostra o passo de indução.
Cuidados
Nas provas usando indução, a passagem mais delicada costuma ser o passo de indução.
Lembre-se, você deve mostrar uma implicação.
Para uma prova direta da implicação , suponha que seja verdade e deduza que também deve ser. Outra alternativa é provar a contrapositiva: nãonão.
Resumo
Foi enunciado o Princípio da Boa Ordenação e discutida sua relação com o P.I.F. 
O Jogo de Nim foi apresentado e analisada uma configuração específica. Também fizemos um exemplo usando o P.I.F.