Indução estrutural
A indução estrutural é um método de demonstração que é usado na lógica matemática (por exemplo, para provar teoremas), em ciência da computação, em teoria dos grafos, e alguns outros campos da matemática. Podemos dizer que é uma generalização do método de indução matemática. A recursão estrutural é um método de recursão que está para a indução estrutural assim como a recursão ordinária está para a indução matemática usual.
Em geral, a ideia é que se deseja demonstrar alguma proposição P(x), onde x é alguma instância de algum tipo de estrutura recursivamente definida, tais como listas ou árvores. Uma ordem parcial bem-fundada (Well-founded) é definida sobre as estruturas. Indução estrutural é um método de demonstração em que a proposição vale para todas as estruturas minimais, e que se valer para as subestruturas de uma determinada estrutura S, então deverá valer para S também.
Uma função estruturalmente recursiva usa a mesma ideia de modo a definir uma função recursiva: "os casos base" dão conta de cada estrutura minimal e se há regras para o caso recursivo. A recursão estrutural é geralmente demonstrada correta através da indução estrutural; em casos mais triviais, a etapa indutiva é deixada frequentemente de fora da prova. A função comprimento (length) e a função concatenação são estruturalmente recursivas e mostradas no exemplo abaixo.
Por exemplo, imagine que as estruturas que vamos utilizar sejam listas, agora introduza uma ordem parcial ‘<’ na qual L < M. Essa ordem parcial indica que a lista L é a cauda da lista M. Segundo esta ordem parcial, o único elemento minimal é quando temos a lista vazia [ ]. Uma demonstração por indução estrutural de alguma proposição P(L) consiste então em duas partes: Uma demonstração de que P([ ]) é verdadeiro, e uma demonstração que se P(L) for verdadeiro para alguma lista L, e se L < M (L for a cauda de uma lista M), então P(M) também deve ser verdadeiro.
Exemplo com listas
[editar | editar código-fonte]Considere a seguinte propriedade das listas:
comprimento (L ++ M) = comprimento L + comprimento M [IG]
Aqui ++ denota a função concatenação de listas.
A fim de demonstrar isto, nós necessitamos definir a operação para o comprimento e a operação para a adição. Aqui (h:t) denota que dada uma lista cuja cabeça é h e a cauda é t.
comprimento [] = 0 [COMP1]
comprimento (h:t) = 1 + comprimento t [COMP2]
[] ++ lista = lista [CONC1]
(h:t) ++ lista = h: (t ++ lista) [CONC2]
Nossa proposição P(l) é que IG é verdadeiro para todas as listas M quando L é l. Nós queremos mostrar que P(l) é verdadeiro para todas as listas l. Demonstraremos isto por indução estrutural sobre as listas.
Primeiramente nós demontraremos que P([ ]) é verdadeiro, isto é, IG é verdadeiro para todas as listas M quando L for a lista vazia [ ]. Com efeito:
comprimento (L ++ M) = comprimento L + comprimento M
comprimento ([]++ M) = comprimento [] + comprimento M
comprimento M = comprimento [] + comprimento M (por CONC1)
comprimento M = 0 + comprimento M (por COMP1)
Isto demonstra que o teorema IG é verdadeiro para todo M, quando L é [ ], uma vez que o lado esquerdo é igual ao lado direito.
Agora nós provaremos P(l) quando l é uma lista não vazia. Já que l não é vazia, ela tem uma cabeça, x, e uma cauda, xs, logo nós podemos denotá-la como (x:xs). A hipótese da indução é que IG é verdadeiro para todos os valores de M quando L é xs:
comprimento (xs ++ M) = comprimento xs + comprimento M (hipótese de indução)
Nós gostaríamos de mostrar que se este for o caso, então IG é também verdadeiro para todos os valores de M quando L é uma lista (x:xs) cuja cauda for xs. Prosseguiremos como antes: IG é verdadeiro para todos os valores de M quando L é xs:
comprimento (L ++ M) = comprimento L + comprimento M
comprimento ((x:xs)++ M) = comprimento (x:xs) + comprimento M
comprimento (x:(xs ++ M)) = comprimento (x:xs) + comprimento M (por CONC2)
1 + comprimento (xs ++ M) = comprimento (x:xs) + comprimento M (por COMP2)
1 + comprimento (xs ++ M) = 1 + comprimento xs + comprimento M (por COMP2)
comprimento (xs ++ M) = comprimento xs + comprimento M
Acabamos de observar que na última linha chegamos justamente na hipótese de indução, logo a demonstração está completa.
Exemplo com grafos
[editar | editar código-fonte]Teorema.Seja G(V,A) um grafo não orientado e conexo com n vértices. Então G contém pelo menos n-1 arestas.
Segue a demonstração por indução estrutural.
Assuma que G(V,A) é um grafo não orientado e conexo com n vértices. Seja P a propriedade de que G tenha pelo menos n-1 arestas. Base: G(1,0) tem um vértice e nenhuma aresta. Logo, a propriedade P é verdadeira.
Passo de indução: Seja G(V,A) um grafo não orientado e conexo com a propriedade P acima, e G' um grafo obtido a partir de G por uma das operações que se seguem:
1.Inserção de vértice: Para que o grafo G ' permaneça conexo, ao se inserir um novo vértice em G ' faz-se necessário inserir uma nova aresta que o conecte a algum outro vértice de G '. Logo a propriedade P é mantida em G '.
2.Inserção de aresta: A inserção de uma nova aresta não altera a propriedade P. Portanto, G contém pelo menos n-1 arestas.
Princípio da boa-ordenação
[editar | editar código-fonte]Assim como a indução matemática é equivalente ao princípio da boa-ordenação, a indução estrutural é também equivalente ao princípio da boa-ordenação. Se o conjunto de todas as estruturas de um determinado tipo admitir uma ordem parcial bem-fundada, então cada subconjunto não vazio deve ter um elemento minimal. (Esta é a definição para "bem-fundada"). A relevância do lema neste contexto é que ele nos permite deduzir que se houver algum contra-exemplo ao teorema que nós queremos provar, deve haver um contra-exemplo mínimo. Se nós pudermos mostrar que a existência do contra-exemplo minimal implica um contra-exemplo ainda menor, nós temos uma contradição (uma vez que o contra-exemplo minimal não seria minimal) e portanto o conjunto dos contra-exemplos deve ser vazio.
Como um exemplo deste tipo de argumento, considere o conjunto de todas as árvores binárias. Nós mostraremos que o número das folhas em uma árvore estritamente binária é um número a mais do que o número de nós interiores. Suponha que há um contra-exemplo; então deve existir uma árvore minimal com o menor número possível de nós interiores. Este contra-exemplo, C, tem n nós interiores e l folhas, aonde n+1 ≠ l. Além disso, C não deve ser trivial, porque a árvore trivial tem n = 0 e l = 1 e não é consequentemente um contra-exemplo. C tem portanto ao menos uma folha cujo nó pai é um nó interior. Remova esta folha e seu pai da árvore, promovendo o nó da folha irmã à posição ocupada anteriormente por seu pai. Isto reduz n e l por 1, assim a árvore nova terá também n+1 ≠ l e é conseqüentemente um contra-exemplo ainda menor. Mas, por hipótese, C já era o menor contra-exemplo; portanto, a própria suposição de que haveria contra-exemplos tem que ser falsa. Perceba que aqui a ordem parcial por trás dessa noção "de menor que" é aquela que diz que S < T sempre que S tem menos nós do que T.