100
edits
Changes
no edit summary
O próximo exemplo ilustra a simplificação do Modus Ponens. Primeiro afirmamos que p implica q e p é verdadeiro.
Então simplificamos a expressão booleana,
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 {\bf '''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.\begin{figure}[H]\centering\includegraphics[width=1.0\textwidth]{File:imagem7.png}\end{figure}]]
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.
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 $N! +1$, é possível que $N!+1$ 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 $N!+1$ diretamente, usando a rotina {\bf '''ifactor} ''' da biblioteca maple.\begin{figure}[H]\centering\includegraphics[width=1.0\textwidth]{File:imagem9.png}\end{figure}]]
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:
Ela usa o procedimento {\bf factorset} do pacote {\bf numtheory} para computar o conjunto de fatores do inteiro de entrada, e então simplesmente seleciona seu menor membro.
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.
Agora, criamos um procedimento para examinar o Goldbach a conjectura mais automaticamente.
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 $1+2+3+...+n = n(n+1)/2$,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.
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 $n^2$ é 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:
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:
Precisamos de três equações para serem solucionadas em busca dos três coeficientes:
Agora, instruímos o maple para resolver essas equações e encontrar os três coeficientes.
A nossa fórmula original torna-se:
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 é:
Enquanto o lado direito da fórmula é:
Podemos usar o procedimento {\bf '''subs} ''' para verificar o passo base da indução; neste caso o passo base é $n=1$ \begin{figure}[H]\centering\includegraphics[width=1.0\textwidth]{File:imagem22.png}\end{figure}]]
Os resultados coincidem (concordam), então o passo base é estabelecido. Para o passo indutivo, usamos que a fórmula seja válida para n=k.
Para somar k+1 termos, computamos:
Por fim, a fórmula para n=k+1 é:
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.
É bem menos óbvio que o exemplo anterior. Para descobri-lo, iniciaremos gerando alguns dados numéricos.
Se um padrão não é imediatamente óbvio,podemos auxiliar nossa intuição gerando uma sequencia paralela.
Observando isto um pouco, fica óbvio que estamos no caminho certo, vamos apenas fazer alguns pequeno ajustes.
Desta evidencia, devemos inferir a conjectura que a fórmula para nosso somatório é: $S=(n+1)!-1$
A prova indutiva pode ser conduzida assim como foi feito no primeiro exemplo.
O passo base é:
O passo indutivo é:
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.
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 $A(n)= 3n^3 + 41n^2- 3n + 101$ nós usaríamos o seguinte comando:
Agora, se quiséssemos definir uma função recursivamente, digamos:
$b(n) =b(n-1)^2 + 2b(n-1) +6$, com a condição inicial $b(0) =2$, então informaríamos(inserir):
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.
Agora, criaremos uma função similar a {\bf b}, chamada {\bf f1}, que encontrará os números Fibonacci.
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 {\bf proc}. Para forçar o maple a calcular esses valores de forma eficiente, usamos a opção {\bf remember} para definições de procedimentos afetados pelo uso do {\bf 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.
Esse método processual engloba ambos os casos, o caso base (quando n <=2) e os casos indutivos (como na condição {\bf 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.
Agora, para ilustrar a diferença em complexidade computacional, compararemos os métodos processual e “->” usando a função {\bf time} do maple.
Então , fica claro que a função {\bf 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 {\bf for} ou {\bf while}) que computará valores começando do menor para o maior. Este método de programação é chamado de {\bf bottom up}: onde os menores valores de uma sequencia são computadose então usados para valores maiores.
Faça um contraste entre esse procedimento e o procedimento recursivo {\bf f2} que foi definido anteriormente.
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:
Que é comparável às vezes obtidas para {\bf '''f2}'''. Note que a implementação puramente recursiva {\bf '''f1} ''' não possibilita o uso para f2(100). De fato, um bom exercício é mostrar que para fazê-lo, {\bf '''f2} ''' precisaria de aproximadamente
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.
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 {\bf '''nextprime}''', {\bf '''prevprime} ''' e {\bf '''ithprime}''' \begin{figure}[H]\centering\includegraphics[width=1.0\textwidth]{File:imagem41.png}\end{figure}]]
Agora, após formada uma lista de primos, queremos extrair quaisquer pares de primos que ocorram nessa lista.
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 {\bf i}’s que formarem pares.
Parece não haver um padrão óbvio ocorrendo.
Primeiro vamos gerar dados para trabalhá-los (manipulá-los).
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 {\bf verdadeiro}.