Inducción estructural - Structural induction

La inducción estructural es un método de prueba que se utiliza en lógica matemática (por ejemplo, en la prueba del teorema de Łoś ' ), informática , teoría de grafos y algunos otros campos matemáticos. Es una generalización de la inducción matemática sobre números naturales y se puede generalizar aún más a la inducción noetheriana arbitraria . La recursividad estructural es un método de recursividad que guarda la misma relación con la inducción estructural que la recursividad ordinaria con la inducción matemática ordinaria .

La inducción estructural se usa para demostrar que alguna proposición P ( x ) es válida para todo x de algún tipo de estructura definida recursivamente , como fórmulas , listas o árboles . Se define un orden parcial bien fundado en las estructuras ("subfórmula" para fórmulas, "sublista" para listas y "subárbol" para árboles). La prueba de inducción estructural es una prueba de que la proposición es válida para todas las estructuras mínimas y que si es válida para las subestructuras inmediatas de una determinada estructura S , entonces debe ser válida también para S. (Hablando formalmente, esto entonces satisface las premisas de un axioma de inducción bien fundada , que afirma que estas dos condiciones son suficientes para que la proposición sea válida para todo x ).

Una función estructuralmente recursiva usa la misma idea para definir una función recursiva: los "casos base" manejan cada estructura mínima y una regla para la recursividad. La recursividad estructural suele demostrarse correcta mediante inducción estructural; en casos particularmente fáciles, el paso inductivo a menudo se omite. Las funciones length y ++ en el ejemplo siguiente son estructuralmente recursivas.

Por ejemplo, si las estructuras son listas, por lo general se introduce la orden parcial "<", en la que L < M cada vez que la lista L es la cola de la lista M . Bajo este orden, la lista vacía [] es el único elemento mínimo. Una prueba de inducción estructural de alguna proposición P ( L ) consta de dos partes: una prueba de que P ([]) es verdadera y una prueba de que si P ( L ) es verdadera para alguna lista L , y si L es la cola de lista M , entonces P ( M ) también debe ser verdadera.

Eventualmente, puede existir más de un caso base y / o más de un caso inductivo, dependiendo de cómo se construyó la función o estructura. En esos casos, una prueba de inducción estructural de alguna proposición P ( l ) consiste entonces en:

  1. una prueba de que P ( BC ) es verdadera para cada caso base BC ,
  2. una prueba de que si P ( I ) es verdadero para algún caso I , y M se puede obtener de I aplicando una sola regla recursiva una vez, entonces P ( M ) también debe ser verdadero.

Ejemplos

Árbol ancestral antiguo, que muestra 31 personas en 5 generaciones

Un árbol de antepasados es una estructura de datos comúnmente conocida, que muestra a los padres, abuelos, etc. de una persona hasta donde se conoce (ver imagen para un ejemplo). Se define de forma recursiva:

  • en el caso más simple, un árbol ancestro muestra solo una persona (si no se sabe nada sobre sus padres);
  • alternativamente, un árbol ancestro muestra a una persona y, conectados por ramas, los dos subárboles ancestros de sus padres (usando para abreviar la prueba la suposición simplificadora de que si uno de ellos es conocido, ambos lo son).

Como ejemplo, la propiedad "Un árbol ancestro que se extiende a lo largo de g generaciones muestra como máximo 2 g  - 1 personas" se puede probar mediante inducción estructural de la siguiente manera:

  • En el caso más simple, el árbol muestra solo una persona y, por lo tanto, una generación; la propiedad es verdadera para tal árbol, ya que 1 ≤ 2 1  - 1 .
  • Alternativamente, el árbol muestra a una persona y los árboles de sus padres. Dado que cada uno de estos últimos es una subestructura de todo el árbol, se puede suponer que satisface la propiedad a probar (también conocida como hipótesis de inducción ). Es decir, p ≤ 2 g  - 1 y q ≤ 2 h  - 1 se puede suponer, en donde g y h indica el número de generaciones el subárbol de la madre del padre y se extiende sobre, respectivamente, y p y q denotan el número de personas que show.
    • En el caso de g  ≤  h , todo el árbol se extiende sobre 1 +  h generaciones y muestra p  +  q  + 1 personas, y p  +  q  + 1 ≤ (2 g  - 1) + (2 h  - 1) + 1 ≤ 2 h  + 2 h  - 1 = 2 1+ h  - 1 , es decir, todo el árbol satisface la propiedad.
    • En el caso h  ≤  g , el árbol completo se extiende sobre 1 +  g generaciones y muestra p  +  q  + 1 ≤ 2 1 +  g  - 1 personas con un razonamiento similar, es decir, todo el árbol satisface la propiedad también en este caso.

Por tanto, por inducción estructural, cada árbol ancestro satisface la propiedad.

Como otro ejemplo más formal, considere la siguiente propiedad de las listas: 

    length (L ++ M) = length L + length M          [EQ]

Aquí ++ denota la operación de concatenación de listas, y L y M son listas.

Para probar esto, necesitamos definiciones de longitud y para la operación de concatenación. Sea (h: t) una lista cuyo encabezado (primer elemento) es hy cuya cola (lista de elementos restantes) es t , y sea [] la lista vacía. Las definiciones de longitud y la operación de concatenación son: 

    length []     = 0                  [LEN1]
    length (h:t)  = 1 + length t       [LEN2]

    []    ++ list = list               [APP1]
    (h:t) ++ list = h : (t ++ list)    [APP2]

Nuestra proposición P ( l ) es que EQ es verdadera para todas las listas M cuando L es l . Queremos mostrar que P ( l ) es verdadero para todas las listas l . Demostraremos esto por inducción estructural en listas.

Primero probaremos que P ([]) es verdadero; es decir, EQ es verdadero para todas las listas M cuando L resulta ser la lista vacía []. Considere EQ: 

      length (L ++ M)  = length ([] ++ M)
                       = length M                     (by APP1)
                       = 0 + length M
                       = length [] + length M         (by LEN1)
                       = length L  + length M

De modo que se demuestra esta parte del teorema; EQ es verdadero para todo M , cuando L es [], porque el lado izquierdo y el lado derecho son iguales.

A continuación, considere la posibilidad de cualquier lista no vacía Me . Como I no está vacío, tiene un elemento principal, x, y una lista final, xs, por lo que podemos expresarlo como (x: xs). La hipótesis de inducción es que EQ es verdadera para todos los valores de M cuando L es xs : 

    length (xs ++ M) = length xs + length M    (hypothesis)

Nos gustaría mostrar que si este es el caso, entonces EQ también es cierto para todos los valores de M cuando L = I = (x: xs). Procedemos como antes: 

    length L  + length M      = length (x:xs) + length M
                              = 1 + length xs + length M     (by LEN2)
                              = 1 + length (xs ++ M)         (by hypothesis)
                              = length (x: (xs ++ M))        (by LEN2)
                              = length ((x:xs) ++ M)         (by APP2)
                              = length (L ++ M)

Así, de la inducción estructural, obtenemos que P (L) es verdadero para todas las listas L.

Bien ordenado

Así como la inducción matemática estándar es equivalente al principio de buen ordenamiento , la inducción estructural también es equivalente a un principio de buen ordenamiento. Si el conjunto de todas las estructuras de cierto tipo admite un orden parcial bien fundado, entonces cada subconjunto no vacío debe tener un elemento mínimo. (Ésta es la definición de " bien fundado ".) El significado del lema en este contexto es que nos permite deducir que si hay algunos contraejemplos del teorema que queremos demostrar, entonces debe haber un contraejemplo mínimo. Si podemos mostrar que la existencia del contraejemplo mínimo implica un contraejemplo aún más pequeño, tenemos una contradicción (ya que el contraejemplo mínimo no es mínimo) y por lo tanto el conjunto de contraejemplos debe estar vacío.

Como ejemplo de este tipo de argumento, considere el conjunto de todos los árboles binarios . Mostraremos que el número de hojas en un árbol binario completo es uno más que el número de nodos interiores. Supongamos que hay un contraejemplo; entonces debe existir uno con el mínimo número posible de nodos interiores. Este contraejemplo, C , tiene n nodos interiores y l hojas, donde n  + 1 ≠  l . Además, C debe ser no trivial, porque el árbol trivial tiene n  = 0 y l  = 1 y, por lo tanto, no es un contraejemplo. Por tanto, C tiene al menos una hoja cuyo nodo padre es un nodo interior. Elimine esta hoja y su padre del árbol, promoviendo el nodo hermano de la hoja a la posición que antes ocupaba su padre. Esto reduce tanto n como l en 1, por lo que el nuevo árbol también tiene n  + 1 ≠  l y, por lo tanto, es un contraejemplo más pequeño. Pero por hipótesis, C ya era el contraejemplo más pequeño; por lo tanto, la suposición de que había contraejemplos para empezar debe haber sido falsa. La ordenación parcial que implica 'más pequeño' aquí es la que dice que S < T cuando S tiene un menor número de nodos que T .

Ver también

Referencias

  • Hopcroft, John E .; Rajeev Motwani; Jeffrey D. Ullman (2001). Introducción a la teoría, los lenguajes y la computación de los autómatas (2ª ed.). Misa de lectura: Addison-Wesley. ISBN   978-0-201-44124-6 .

Las primeras publicaciones sobre inducción estructural incluyen: