Portas logicas

Disponível somente no TrabalhosFeitos
  • Páginas : 30 (7372 palavras )
  • Download(s) : 0
  • Publicado : 11 de novembro de 2012
Ler documento completo
Amostra do texto
Fundamentos Matemáticos a Ciência da Computação
UM TRATAMENTO MODERNO DE MATEMÁTICA DISCRETA

Judith L. Gersting
Quinta Edição

LTC

DEMONSTRAÇÕES, RECORRÊNCIA E ANÁLISE DE ALGORITMOS

97

SEÇÃO 2.4 R E C U R S I V I D A D E E RELAÇÕES D E RECORRÊNCIA
DEFINIÇÕES RECORRENTES
Uma definição onde o item sendo definido aparece como parte da definição é chamada de uma definiçãorecorrente ou definição por recorrência ou ainda definição por indução. A princípio isso não parece fazer sentido — como podemos definir algo em termos de si mesmo? Isso funciona porque uma definição recorrente tem duas partes: 1. Uma base, ou condição básica, onde alguns casos simples do item sendo definido são dados explicitamente. 2. Um passo de indução ou recorrência, onde novos casos do item sendodefinido são dados em função de casos anteriores. A parte 1 nos dá um lugar para começar, fornecendo alguns casos simples e concretos; a parte 2 nos permite construir novos casos, a partir desses simples, e depois construir ainda outros casos a partir desses novos, e assim por diante. (O nome "definição por indução" é devido à analogia com demonstrações por indução matemática. Em uma demonstração porindução existe uma base da indução, a saber, mostrar que P(l) — ou P em algum outro valor inicial — é verdadeira, e existe um passo indutivo, onde a veracidade de P(k + 1) é estabelecida a partir da veracidade de P em valores anteriores.) Recorrência é uma ideia importante que pode ser usada para definir sequências de objetos, coleções mais gerais de objetos e operações com objetos. (O predicadoProlog na-cadeia-alimentar da Seção 1.5 foi definido de forma recorrente.) Até algoritmos podem ser recorrentes.

Sequências Definidas por Recorrência
Uma sequência 5 é uma lista de objetos que são numerados em determinada ordem; existe um primeiro objeto, um segundo, e assim por diante. S(k) denota o &-ésimo objeto na sequência. Uma sequência é definida por recorrência nomeando-se,explicitamente, o primeiro valor (ou alguns poucos primeiros valores) na sequência e depois definindo valores subsequentes na sequência em termos de valores anteriores. • EXEMPLO 29 A sequência 5 é definida por recorrência por 1. S(J) = 2 2. 5(n) = 2S(n - 1) para n > 2 Pela proposição 1, 5(1), o primeiro objeto em S, é 2. Depois, pela proposição 2, o segundo objeto em 5 é 5(2) = 25(1) = 2(2) = 4. Novamentepela proposição 2, 5(3) = 25(2) = 2(4) = 8. Continuando desse modo, vemos que a sequência 5 é 2,4,8,16,32,... *

Uma regra como a da proposição 2 no Exemplo 29, que define um valor de uma sequência em termos de um ou mais valores anteriores, é chamada uma relação de recorrência. PROBLEMA PRÁTICO 11 A sequência Té definida por recorrência por j
m = l

2. T(n) = T(n - 1) + 3 para n > 2 Escrevaos cinco primeiros valores da sequência T. •

• EXEMPLO 30

A famosa sequência de Fibonacci, introduzida no século XIII por um comerciante e matemático italiano, é uma sequência de números definida por recorrência por F(\) = 1 F{2) = 1 F(n) = F(n - 2) + F(n - 1) para n > 2 Aqui são dados os dois primeiros valores da sequência e a relação de recorrência define o n-ésimo valor em termos dos doisvalores precedentes. É melhor pensar na relação de recorrência em sua forma mais

98

CAPÍTULO DOIS

geral, que diz que F em qualquer valor — exceto em 1 e 2 — é a soma de F em seus dois valores anteriores. • Escreva os oito primeiros valores da sequência de Fibonacci. Prove que, na sequência de Fibonacci, F(n + 4) = 3F(n + 2) - F(n) para todo n > 1 Como queremos provar que alguma coisa éverdadeira para todo n > 1, é natural pensar em uma demonstração por indução. E como o valor de F(n) depende de F(n — 1) e de F(n — 2), deve-se usar o segundo princípio de indução. Para a base da indução, vamos provar dois casos, n = 1 e n = 2. Para n = 1, obtemos F(5) = 3F(3) - F ( l ) ou (usando os valores calculados no Problema Prático 12) 5 = 3(2) - 1 que é verdade. Para n = 2, F(6) = 3F(4) -...
tracking img