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

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

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

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.

Referências

• Teoremas - provas de teoremas relacionados com a Teoria de Grafos