Portas logicas

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ção recorrente 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 sendo definido 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 por induçã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 predicado Prolog 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,