Indução e Recursão Matemática

From Tools for Logic Wiki
Jump to navigation Jump to search

Este projeto descreve o uso da linguagem Maple para desenvolvimento da Indução Matemática e Recursão na disciplina de Fundamentos da Matemática para Computação II. Com uso da tradução livre do documento que foi disponibilizado do livro Matemática Discreta do Keneth H. Rosen, descreveremos como a Indução pode ser facilmente entendida e utilizada com Maple .


Introdução

Neste capítulo descreveremos como o maple pode ser usado para ajudar na compreensão e construção de provas matemáticas. Capacidades computacionais podem não parecer particularmente relevantes para o estudo das provas, embora na realidade essas capacidades possam ser úteis em provas de várias maneiras. Neste capítulo, descrevemos como o maple pode ser útil para trabalhar com regras formais de inferência, descrevemos como pode ajudar a compreender provas construtivas e não construtivas. Além disso, mostramos como usar o maple para ajudar a desenvolver provas usando indução matemática, até mesmo mostrando sua utilidade para ambos o passo base e passo indutivo, na prova da fórmula de somatório. Ademais, mostraremos como o maple pode ser usado para computar termos de sequencias definidas recursivamente. Vamos também comparar a eficiência da geração de termos dessa sequencia via técnicas indutivas versus técnicas recursivas.

Método de prova

Embora o maple não possa receber teoremas e resultados de provas para esses teoremas, pode receber expressões lógicas e simplificadas ou determinar características tais como: se uma expressão booleana pode ser satisfeita ou se é uma tautologia. Para trabalhar com expressões lógicas no maple, precisamos usar alguns dos recursos oferecidos pelo pacote de logic (um assunto abordado de maneira mais aprofundada no capítulo 9). Primeiramente examinaríamos os operadores lógicos: conjunção, disjunção, negação e implicação. Não existe (no Maple). Para estudar as condicionais, devemos trabalhar com os operadores booleanos inativos oferecidos pelo pacote logic. Todos esses são iniciados com o caracter mexpr , por exemplo: usamos invés de e invés de . Em seguida, vão alguns exemplos do uso de operadores booleanos inativos:

Imagem1.png

Nos preocupamos agora em determinar como o maple simplifica expressões booleanas caso estejam combinadas. Começamos com um simples exemplo de dupla negação:

Capeta.png

Isto pode ser simplificado através do uso da função bsimp do maple.

Imagem3.png

Agora, seguimos para um exemplo mais complexo, no qual o leitor pode confirmar a corretude da simplificação, construindo uma tabela verdade.

Imagem4.png

O próximo exemplo ilustra a simplificação do Modus Ponens. Primeiro afirmamos que p implica q e p é verdadeiro.

Imagem5.png

Então simplificamos a expressão booleana,

Imagem6.png

Determinando que q e p são verdadeiros, como nós já sabíamos que p era verdadeiro, nós concluímos que q é verdadeiro.

A função bsimp é um simplificador geral para expressões booleanas construídas usando os operadores booleanos inativos. A função computa uma expressão booleana simplificada equivalente ao seu argumento. Podemos também usar o maple para determinar se uma expressão é uma tautologia através do uso da função tautology oferecida pelo pacote logic.

Imagem7.png

Agora mostramos como usar o maple para compreender algumas provas construtivas. Especificamente, vamos examinar como explorar a construção de uma lista sequencial de números compostos.

Imagem8.png

Enquanto o maple pode ser usado para gerar uma lista de n inteiros compostos consecutivos, gerados por prova, não é possível derivar a prova em si usando o maple. Devemos observar que este argumento não fornece o menor conjunto de n inteiros compostos consecutivos. Embora dado um inteiro positivo n, é possível usar o maple para encontrar a menor sequencia de n inteiros compostos consecutivos. Através do maple abordaremos a prova não construtiva da existência de um número infinito de números primos. Por ser uma prova não construtiva, não podemos simplesmente criar um algoritmo para gerar um número primo maior, assumindo a existência de um número primo máximo. Embora a ideia chave da prova seja considerar a primalidade do inteiro , é possível que seja por si só um número primo, porém mesmo que não seja seu maior fator primo deve ser maior que n. É possível encontrar o menor fator primo fatorando diretamente, usando a rotina ifactor da biblioteca maple.

Imagem9.png

Podemos observar pelo resultado que, enquanto alguns desses números são primos, outros não são, a partir disso, podemos fazer a leitura do menor fator primo. Para determinar o menor fator primo de cada um desses inteiros, podemos escrever a seguinte rotina:

Imagem10.png


Ela usa o procedimento factorset do pacote numtheory para computar o conjunto de fatores do inteiro de entrada, e então simplesmente seleciona seu menor membro.

Imagem11.png

Agora confrontamos nosso exemplo final do uso do maple explorando teoremas matemáticos. Neste caso vamos explorar a conjectura de Goldbach: que é, todo inteiro par maior que 4 pode ser expressado como a soma de dois primos.

Imagem12.png

Agora, criamos um procedimento para examinar o Goldbach a conjectura mais automaticamente.

Imagem13.png

Indução Matemática

O maple pode ser usado para auxiliar na elaboração de provas de várias afirmações matemáticas usando a indução matemática. De fato, com o maple como seu assistente, você pode conduzir inteiramente o processo de descoberta e averiguação de forma intuitiva. É provável que entre os primeiros exemplos de indução matemática, encontremos a verificação da fórmula ,a soma dos primeiros n inteiros positivos. O maple se adequa para provar fórmulas como essa porque os passos envolvidos numa prova indutiva incluem manipulação simbólica. É possível gerar uma grande quantidade de dados numéricos para serem examinado.

Imagem14.png

Através da geração de um grande conjunto de dados numéricos de pouca compreensão, eventualmente será possível determinar a fórmula acima. A saída mostra que é um pouco menos que o dobro da soma dos n primeiros inteiros para os valores de n testados. Partindo de um padrão, é possível perceber que a fórmula correta é uma função quadrática de n, resolva para encontrar os coeficientes e então teste se esse procedimento produz a fórmula correta. Uma técnica útil para experimentos semelhantes é gerar listas de pares que consista da sequencia que esteja interessado e de várias possibilidades que você elabore. Para investigar a hipótese de que a fórmula seja quadrática, devemos começar gerando uma lista de pares semelhantes ao seguinte:

Imagem15.png

Para explorar se a soma é uma função quadrática de n, podemos inserir um quadrático genérico em n e solucionar para encontrar os coeficientes a,b e c:

Imagem16.png

Precisamos de três equações para serem solucionadas em busca dos três coeficientes:

Imagem17.png

Agora, instruímos o maple para resolver essas equações e encontrar os três coeficientes.

Imagem18.png

A nossa fórmula original torna-se:

Imagem19.png

Neste ponto, as habilidades do maple permitem manipular expressões simbolicamente para ajudar a construir uma prova indutiva. Segue um exemplo de como a prova interativa da fórmula acima pode ser conduzido no maple por indução matemática. O termo geral da soma é:

Imagem20.png

Enquanto o lado direito da fórmula é:

Imagem21.png

Podemos usar o procedimento subs para verificar o passo base da indução; neste caso o passo base é

Imagem22.png

Os resultados coincidem (concordam), então o passo base é estabelecido. Para o passo indutivo, usamos que a fórmula seja válida para .

Imagem23.png

Para somar k+1 termos, computamos:

Imagem.png

Por fim, a fórmula para n=k+1 é:

Imagem24.png

Os resultados coincidem, então o passo indutivo é verificado. A fórmula agora segue por indução matemática. Assim, podemos concluir que enquanto o maple ainda não é capaz de construir provas inteiramente por conta própria, é uma ferramenta muito efetiva para ser usada na construção de provas interativas. Agora, vamos considerar um exemplo mais complicado. A fórmula do somatório. É bem menos óbvio que o exemplo anterior. Para descobri-lo, iniciaremos gerando alguns dados numéricos.

Imagem25.png

Se um padrão não é imediatamente óbvio,podemos auxiliar nossa intuição gerando uma sequencia paralela.

Imagem26.png

Observando isto um pouco, fica óbvio que estamos no caminho certo, vamos apenas fazer alguns pequeno ajustes.

Imagens.png

Desta evidencia, devemos inferir a conjectura que a fórmula para nosso somatório é:

A prova indutiva pode ser conduzida assim como foi feito no primeiro exemplo.

Imagem28.png

O passo base é:

Entrenseind.png

O passo indutivo é:

Imagem29.png

Usando um pouco de manipulação algébrica, vemos que as duas últimas fórmulas são iguais. Isso completa a prova via indução matemática. Concluímos que nosso palpite sobre a fórmula está correto.

Definições Recursiva e Interativa

As funções do maple podem ser definidas tanto processualmente (usando a função proc) como explicitamente (usando a notação ->), cada um desses métodos envolve meios interativos e recursivos de definição. Iniciamos nosso estudo, usando a função -> do maple. Se nós quiséssemos definir uma função polinomial nós usaríamos o seguinte comando:

Imagem30.png

Agora, se quiséssemos definir uma função recursivamente, digamos: , com a condição inicial , então informaríamos (inserir):

Imagem31.png

Se quiséssemos ver uma sequencia de valores para a função b, podemos usar a função seq, para exibir as saídas de um dado intervalo de entradas.

Imagem32.png

Agora, criaremos uma função similar a b, chamada f1, que encontrará os números Fibonacci.

Imagem33.png

Enquanto a notação para funções é conveniente e intuitiva, ela não oferece todas as facilidades para melhoria da eficiência que estão disponíveis no uso do comando proc. Para forçar o maple a calcular esses valores de forma eficiente, usamos a opção remember para definições de procedimentos afetados pelo uso do proc. Esta opção exige que o maple lembre de qualquer valor para procedimento que já tenha sido computado através do armazenamento destes em uma tabela Fibonacci.

Imagem34.png

Esse método processual engloba ambos os casos, o caso base (quando ) e os casos indutivos (como na condição else). Adicionalmente, o procedimento tem a indicação da função remember, forçando o maple a manter controle sobre quais valores da função já foram encontrados, para que estes sejam diretamente verificados ao invés de serem novamente computados.

Imagem35.png

Agora, para ilustrar a diferença em complexidade computacional, compararemos os métodos processual e “->” usando a função time do maple.

Imagem36.png

Então , fica claro que a função remember pode fazer uma enorme diferença em complexidade de tempo. Outra maneira de melhorar a eficiência de uma função definida recursivamente é reescrevê-la para evitar o uso de recursão. Ao invés disso, reestruturamos para que use um algoritmo iterativo. Na construção de um algoritmo iterativo, os componentes chave consistem em criar uma forma de loop (um for ou while) que computará valores começando do menor para o maior. Este método de programação é chamado de bottom up: onde os menores valores de uma sequencia são computadose então usados para valores maiores.

Imagem37.png

Faça um contraste entre esse procedimento e o procedimento recursivo f2 que foi definido anteriormente.

Imagem38.png

Ambos os casos base e passo recursivo são explicitamente definidos no corpo do procedimento. O algoritmo primeiro tenta computar diretamente o valor verdadeiro e pede valores de subcasos conforme é solicitado. Este método de programação é conhecido como top-down, pois os valores maiores são computados através da quebra da entrada em partes menores e da combinação dos resultados. Similar a atravessar uma árvore binária. Perceba que o procedimento recursivo com a opção remember e o procedimento iterativo tem praticamente a mesma performance. Para os primeiros vinte números Fibonacci, obtemos:

Imagem39.png

Que é comparável às vezes obtidas para f2. Note que a implementação puramente recursiva f1 não possibilita o uso para f2(100). De fato, um bom exercício é mostrar que para fazê-lo, f2 precisaria de aproximadamente

Imagem40.png

Chamadas para operar todos os subcasos que surgirem. Mesmo a um bilhão de subcasos por segundo, isso exigiria mais de seis mil anos para sua conclusão.

Computações e Explorações

Nesta seção do material, exploraremos o modo como o maple pode ser usado para resolver as questões 4,5 e 8 da seção “computações e explorações” do livro.


1 - Quantos pares de números primos podem ser encontrados?


Para determinar quantos pares de números primos existem, usaremos o pacote “numtheory” do maple, que contém as funções nextprime, prevprime e ithprime

Imagem41.png

Agora, após formada uma lista de primos, queremos extrair quaisquer pares de primos que ocorram nessa lista.

Imagem42.png

Ao invés de dar como resultados os pares de números primos, o número de sequências de primos pode indicar um padrão, então construímos uma lista dos i’s que formarem pares.

Imagem43.png

Parece não haver um padrão óbvio ocorrendo.


2- Determine quais números Fibonacci são divisíveis por 5, quais são divisíveis por 7 e quais são divisíveis por 111. Prove que suas conjecturas estão corretas. Primeiro vamos gerar dados para trabalhá-los (manipulá-los).

Imagem44.png

Queremos determinar os índices n para os quais o enésimo número Fibonacci é divisível por 5. Uma maneira de fazer isso é construindo uma lista, através de testes com os dados acima e adicionando à lista somente os índices n para os quais o teste retorne verdadeiro.

Imagem45.png

Isso constrói uma lista indicando quais entre os primeiros 500 números Fibonacci são múltiplos de 5. Os dados indicam que o enésimo número Fibonacci é divisível por 5, somente se n é divisível por 5. Para obter evidências para a conversão, devemos testar se é divisível por 5, para tantos n quanto forem possíveis. Para que nosso teste seja conciso e ainda permita testar um grande intervalo(série) de valores, vamos implementá-lo de maneira que nenhum resultado seja produzido, a menos que seja encontrado um contra exemplo.

Imagem46.png

Assim, não há contra exemplo entre os primeiros 5000 números Fibonacci. Você pode testar com valores maiores que 1000, para obter novas evidências. Outra abordagem ligeiramente diferente pode ser usada para encontrar os números Fibonacci divisíveis por um dado inteiro, neste caso, o número 7. Nós simplesmente construímos o teste de divisibilidade no comando para gerar dados.

Imagem47.png

Podemos agora selecionar os índices dos pares cujo segundo membro seja igual a 0.

Imagem48.png

Podemos perceber um padrão nesses dados, como o seguinte:

Imagem49.png

Você pode tentar averiguar se esse padrão persiste, substituindo 500 na definição de fib_list por números muito maiores. (O teste da divisibilidade por 111, nós deixamos pra você).


2 – A notória conjectura (também conhecida como conjectura de Collatz e por vários outros nomes) afirma que: independente de qual inteiro x você escolha para iniciar, em iteração com a função f(x), onde f(x) = x/2, se x é par e f(x) = 3x+1 se x é ímpar, sempre produz o inteiro 1. Cheque essa conjectura para tantos inteiros positivos possíveis. Para inicar, precisamos definir a função, a qual examinaremos.

Imagem50.png

Agora escrevemos uma função que fará a iteração da função Collatz até que o valor obtido seja igual a 1, nós incluímos uma variável “count” por dois motivos: Primeiro, queremos ter uma idéia de quanto tempo leva para que as iterações estabilizem; Segundo, já que não sabemos ao certo se as iterações vão estabilizar para um dado valor de entrada “seed”, nos codificamos um limite superior para o número de iterações a serem computadas.

Imagem51.png

Para averiguar a conjectura para os 1000 primeiros inteiros, podemos usar a função IC como no exemplo a seguir:

Imagem52.png

Perceba que, o fato de a função ter eventualmente parado é a averiguação que buscamos.

Exercícios e Projetos

1.Use Maple para encontrar e provar a fórmula do soma do primeiros (K elevado a enésima potência) inteiros positivos para N = 4, 5, 6, 7, 8, 9 e 10.

2.Use Maple para estudar a função McCarthy 91.

Q1.jpg

3.Escreva um procedimento no Maple para encontrar a menr (isto é, a primeira) sequência consecutiva de N inteiros positivos compostos, para um inteiro N positivo arbitrário.

4.Use Maple para desenvolver um procedimento para gerar números Ulam. Faça e estude numericamente as conjecturas sobre a distribuição desses números.

5.Escreva um procedimento no Maple que receba um inteiro K como entrada e determine se é ou não o produto dos primeiros K primos mais 1, e se é primo ou não, através da fatoração deste número.

Q2.jpg

6.Outra maneira de mostrar que existem infinitos primos é assumir que existem apenas N primos . Mas isso é uma contradição já que tem ao menos um fator primo que não é divisível por , i = 1, 2, ..., N. Encontre o menor fator primo de para todos os inteiros positivos N que não excedam 200. Para os quais N é este número primo.

7.O número Lucas satisfaz a recorrência e as condições iniciais e . Use o Maple para obter evidências para as conjecturas sobre a divisibilidade dos números Lucas por outros divisores inteiros diferentes.

8.A sequência é chamada de periódica se existirem inteiros positivos N e p, para os quais , para todo . O menor inteiro p, para o qual isso é verdadeiro é chamado de período da sequência se diz que é o módulo periódico m, para um inteiro positivo M, se a sequência ,, , ... é periódica. Use maple para determinar se a sequência Fibonacci é modulo periódico m, para vários inteiros m e, se for, encontre o período.Você pode, através da inspeção de valores de m diferentes o suficiente, fazer alguma conjectura a respeito da relação entre m e o período? Faça o mesmo para sequências que julgar interessante.

Extra

Nesta sessão serão tratados algumas demonstrações sobre indução e recursão contidas na pagina 240, cujo Extra 1, 2, 3 e 4 são implentações na linguagem de C++ como forma de uma abordagem alternativa como sugestão do Professor Umberto Rivieccio da disciplina de FMC II.

  • Exemplo 1

Use o princípio da indução matemática para provar que para todo Seja p(n) a afirmação

Passo base: p(0) : , (perceba que a soma no lado esquerdo de p(0) inicia e termina com o primeiro termo 1, consequentemente é apenas o primeiro termo 1). é verdadeiro pois ambos os lados são iguais a 1.

Passo indutivo: : suponha para qualquer k, é verdadeiro, isto é, Precisamos mostrar que a próxima afirmação , é verdadeira: Para fazer isso, iniciamos com e adicionamos o próximo termo, , em ambos os lados, depois mostramos que essa é a afirmação .

    
     

                                   
                                   
                                   

Isto é, . Portanto uma afirmação verdadeira p(k, é seguida por outra afirmação verdadeira , por isso é verdadeira. Assim, pelo princípio da indução matemática , é verdadeiro para todo . Nota: Alternativamente, a prova de pode ser escrita dessa forma. Começamos escrevendo o lado esquerdo da equação que é . Então mostramos que pode ser reescrita para dar o lado direito de . Perceba que a suposição que é verdadeira está sendo usada em substituição do primeiro passo.

                          
                           
                           
                           
  • Exemplo 2

Prove que :

para todo

Seja

Passo base: afirma que , é verdadeiro, já que ambos os lados são iguais a 5.

Passo indutivo: : suponha que é verdadeiro, isto é: Adicionamos a ambos os lados e simplificamos :

                     
                                             
                                             

Que é , assim, é verdadeiro. Portanto, pelo princípio da indução matemática, é verdadeiro para todo .

  • Exemplo 3

Encontre uma fórmula para Para , use o princípio de indução matemática para provar que sua fórmula está correta. Primeiro precisamos de um palpite para a fórmula do produto. Usando obtemos:

=

=

=

Assim, os produtos são , ,,. Podemos reescrever essas frações como , , , . Isso sugere como a forma geral da soma.

Seja = Agora, tentamos mostrar que é verdadeiro para todo .

Passo base:

 é verdadeiro.  afirma que (1-1/2²) = , que é verdade pois, ambos os lados são iguais a .

Passo indutivo: : suponha que é verdadeiro para algum k. Portanto: =

Multiplica-se ambos os lados da equação por para obter

=

Que é . Portanto, pelo princípio da indução matemática,

 =  é verdadeiro para todo .
  • Exemplo 4

Use o princípio da indução matemática para provar que para todo .

Seja a afirmação .

Passo base: é verdadeiro, pois , ou .

Passo indutivo: suponha verdadeiro para algum inteiro não negativo k, isto é, .

Precisamos mostrar que é verdadeiro: , mas .Porém, através de , e , já que é par. Portanto , 2 é divisor da diferença, isto é, .

Assim, é verdadeiro. Pelo princípio da indução matemática , é verdadeiro para todo .

  • Exemplo 5

Use o princípio da indução matemática para provar que: , para todo . Seja p(n) a afirmação .

Passo base: O passo base é , afirma que , o que é verdade, pois .

Passo indutivo: , suponha que para algum inteiro . Precisamos mostrar que é verdadeiro. Mas . O termo é positivo por , e é positivo, pois é no mínimo , daí a soma é positiva e é verdadeiro. Portanto, pelo princípio da indução matemática, é verdadeiro para todo .

  • Exemplo 6

A) Escreva um algoritmo recursivo para encontrar a soma dos n primeiros inteiros positivos pares.

B) Use a indução matemática para provar que o algoritmo está correto.

Solução:

A)Seja evensum(n) a soma dos n primeiros inteiros positivos. O algoritmo recursivo é:

  Procedure evensum(n : integer >= 1)
      If n=1    then  evensum(n): = 2
  Else evensum(n):= evensum(n-1) +2n

B)Seja , evensum(n) (a soma dos n primeiros inteiros positivos pares).

‘’’Passo base:’’’ Quando , a ação then (então) do procedimento toma efeito e atribui evensum(1) = 2, que é a soma do primeiro inteiro par.

‘’’Passo indutivo:’’’ Assumimos verdadeiro para algum e devemos mostrar que é também verdadeiro. A proposição afirma que evensum(k) é a soma dos primeiros inteiros positivos pares. De acordo com o algoritmo, como , a condição else é usada (com em lugar de) para obter evensum(k+1) e retorna:

   evensum(k+1) = evensum(k)  soma dos primeiros k inteiros pares 

Que é a soma dos primeiros inteiros pares. Portanto, o passo de indução é seguido. O princípio da indução matemática prova que o algoritmo está correto.

  • Exemplo 5

Para a sequencia de números Fibonacci , prove que :

  

Seja a afirmação

Passo base: afirma que e

Passo Indutivo: , suponha que é verdadeiro para algum inteiro não negativo , isto é, devemos mostrar que

   

é verdadeiro, isto é,

   :
              

Portanto , pelo princípio da indução matemática , é verdadeiro para todo .

Implementações em C++(Exemplos 1, 2, 3 e 4)

Os códigos aqui inseridos podemos notar que foi uitlizado a biblioteca math.h para utilização da função POW, com a qual calculamos a potência de uma determinada base. Captura de tela de 2016-05-29 20-22-52.png Captura de tela de 2016-05-29 20-23-27.png Captura de tela de 2016-05-29 20-24-41.png Captura de tela de 2016-05-29 20-25-21.png Captura de tela de 2016-05-29 20-25-36.png

Conclusão

A elaboração deste trabalho nos proporcionou um novo conhecimento sobre a liguagem Maple e como podemos aplica-la no entendimento da Indução e Recursão na Matemática em Fundamentos da Matemática para a Computação II. Com isso podemos perceber o quanto é importante o aprendizado contínuo na área da Tecnologia da Informação para nos mantermos atualizados e em crescente aprimoração seja acadêmica ou profissional .

Referências

Discrete Mathematics and Its Applications. Disponível em: <http://www.mhhe.com/math/advmath/rosen/r5/student/ch03/maple.html> Acesso em: 12 de Maio de 2016. Discrete Mathematics and Its Applications, Disponivel em: <http://www.mhhe.com/math/advmath/rosen/r5/student/ch03/sec03.3/examples.html> Acesso em: 25 de Maio de 2016.