Induzione strutturale - Structural induction

L'induzione strutturale è un metodo di dimostrazione utilizzato nella logica matematica (ad esempio, nella dimostrazione del teorema di Łoś ), nell'informatica , nella teoria dei grafi e in alcuni altri campi matematici. È una generalizzazione dell'induzione matematica sui numeri naturali e può essere ulteriormente generalizzata all'induzione noetheriana arbitraria . La ricorsione strutturale è un metodo di ricorsione che ha la stessa relazione con l'induzione strutturale come la ricorsione ordinaria ha con l'induzione matematica ordinaria .

L'induzione strutturale viene utilizzata per dimostrare che una certa proposizione P ( x ) vale per tutte le x di una sorta di struttura definita ricorsivamente , come formule , elenchi o alberi . Un ordine parziale ben fondato è definito sulle strutture ("subformula" per le formule, "sublist" per le liste e "sottoalbero" per gli alberi). La dimostrazione di induzione strutturale è una prova che la proposizione vale per tutte le minimali strutture e che se vale per le sottostrutture immediati di una certa struttura S , allora deve valere per S anche. (Formalmente parlando, questo soddisfa quindi le premesse di un assioma di induzione ben fondata , che afferma che queste due condizioni sono sufficienti affinché la proposizione valga per tutti gli x .)

Una funzione strutturalmente ricorsiva usa la stessa idea per definire una funzione ricorsiva: i "casi base" gestiscono ogni struttura minima e una regola per la ricorsione. La ricorsione strutturale è generalmente dimostrata corretta dall'induzione strutturale; in casi particolarmente facili, il passo induttivo viene spesso tralasciato. Le funzioni length e ++ nell'esempio seguente sono strutturalmente ricorsive.

Ad esempio, se le strutture sono liste, di solito si introduce l'ordine parziale "<", in cui L < M ogniqualvolta lista L è la coda della lista M . In questo ordine, l'elenco vuoto [] è l'elemento minimo unico. Una dimostrazione di induzione strutturale di qualche proposizione P ( L ) consiste quindi di due parti: una prova che P ([]) è vero e una prova che se P ( L ) è vero per qualche lista L , e se L è la coda di list M , quindi anche P ( M ) deve essere vero.

Alla fine, possono esistere più di un caso base e / o più di un caso induttivo, a seconda di come è stata costruita la funzione o la struttura. In quei casi, una dimostrazione di induzione strutturale di una proposizione P ( l ) consiste quindi in:

  1. una prova che P ( BC ) è vero per ogni caso base BC ,
  2. una prova che se P ( I ) è vero per qualche istanza I , e M può essere ottenuto da I applicando una qualsiasi regola ricorsiva una volta, allora anche P ( M ) deve essere vero.

Esempi

Image
Antico albero degli antenati, che mostra 31 persone in 5 generazioni

Un albero degli antenati è una struttura dati comunemente nota, che mostra i genitori, i nonni, ecc. Di una persona per quanto noti (vedere l'immagine per un esempio). È definito ricorsivamente:

  • nel caso più semplice, un albero degli antenati mostra solo una persona (se non si sa nulla dei loro genitori);
  • in alternativa, un albero degli antenati mostra una persona e, collegati da rami, i due sottoalberi degli antenati dei loro genitori (usando per brevità di prova l'assunto semplificativo che se uno di loro è noto, entrambi lo sono).

Ad esempio, la proprietà "Un albero antenato che si estende su g generazioni mostra al massimo 2 g  - 1 persona" può essere dimostrata mediante induzione strutturale come segue:

  • Nel caso più semplice, l'albero mostra una sola persona e quindi una generazione; la proprietà è vera per un tale albero, poiché 1 ≤ 2 1  - 1 .
  • In alternativa, l'albero mostra una persona e gli alberi dei suoi genitori. Poiché ciascuno di questi ultimi è una sottostruttura dell'intero albero, si può presumere che soddisfi la proprietà da dimostrare (ovvero l' ipotesi di induzione ). Cioè, p ≤ 2 g  - 1 e q ≤ 2 h  - 1 assumibili, dove g ed h denota il numero di generazioni sottostruttura della madre del padre e si estende oltre, rispettivamente, e p e q denotano il numero di persone che spettacolo.
    • Nel caso g  ≤  h , l'intero albero si estende per 1 +  h generazioni e mostra p  +  q  + 1 persone, ep  +  q  + 1 ≤ (2 g  - 1) + (2 h  - 1) + 1 ≤ 2 h  + 2 h  - 1 = 2 1+ h  - 1 , cioè l'intero albero soddisfa la proprietà.
    • Nel caso h  ≤  g , l'intero albero si estende su 1 +  g generazioni e mostra p  +  q  + 1 ≤ 2 1 +  g  - 1 persone con un ragionamento simile, cioè l'intero albero soddisfa la proprietà anche in questo caso.

Quindi, per induzione strutturale, ogni albero antenato soddisfa la proprietà.

Come altro esempio più formale, considera la seguente proprietà degli elenchi: 

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

Qui ++ denota l'operazione di concatenazione di elenchi e L e M sono elenchi.

Per dimostrarlo, abbiamo bisogno di definizioni per la lunghezza e per l'operazione di concatenazione. Sia (h: t) una lista la cui testa (primo elemento) è he la cui coda (lista degli elementi rimanenti) è t , e [] denoti la lista vuota. Le definizioni per la lunghezza e l'operazione di concatenazione sono: 

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

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

La nostra proposizione P ( l ) è che EQ è vera per tutte le liste M quando L è l . Vogliamo mostrare che P ( l ) è vero per tutte le liste l . Lo dimostreremo per induzione strutturale su liste.

Per prima cosa dimostreremo che P ([]) è vero; cioè, EQ è vero per tutte le liste M quando L sembra essere la lista vuota []. Considera l'EQ: 

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

Quindi questa parte del teorema è dimostrata; L'EQ è vero per tutte le M , quando L è [], perché il lato sinistro e il lato destro sono uguali.

Quindi, considerare ogni lista non vuota io . Poiché I non è vuoto, ha un elemento principale, x, e un elenco di coda, xs, quindi possiamo esprimerlo come (x: xs). L'ipotesi di induzione è che l'EQ sia vero per tutti i valori di M quando L è xs : 

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

Vorremmo mostrare che se questo è il caso, allora l'EQ è vero anche per tutti i valori di M quando L = I = (x: xs). Procediamo come prima: 

    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)

Quindi, dall'induzione strutturale, otteniamo che P (L) è vero per tutte le liste L.

Ben ordinato

Proprio come l' induzione matematica standard è equivalente al principio di buon ordinamento , anche l'induzione strutturale è equivalente a un principio di buon ordinamento. Se l'insieme di tutte le strutture di un certo tipo ammette un ordine parziale ben fondato, allora ogni sottoinsieme non vuoto deve avere un elemento minimo. (Questa è la definizione di " fondato ".) Il significato del lemma in questo contesto è che ci permette di dedurre che se ci sono dei controesempi del teorema che vogliamo dimostrare, allora ci deve essere un controesempio minimo. Se possiamo dimostrare che l'esistenza del controesempio minimo implica un controesempio ancora più piccolo, abbiamo una contraddizione (poiché il controesempio minimo non è minimo) e quindi l'insieme dei controesempi deve essere vuoto.

Come esempio di questo tipo di argomento, considera l'insieme di tutti gli alberi binari . Mostreremo che il numero di foglie in un albero binario completo è uno in più del numero di nodi interni. Supponiamo che ci sia un controesempio; allora ne deve esistere uno con il minor numero possibile di nodi interni. Questo controesempio, C , ha n nodi interni e l foglie, dove n  + 1 ≠  l . Inoltre, C deve essere non banale, perché l'albero banale ha n  = 0 e l  = 1 e quindi non è un controesempio. C quindi ha almeno una foglia il cui nodo padre è un nodo interno. Elimina questa foglia e il suo genitore dall'albero, promuovendo il nodo di pari livello della foglia nella posizione precedentemente occupata dal suo genitore. Questo riduce sia n che l di 1, quindi anche il nuovo albero ha n  + 1 ≠  l ed è quindi un controesempio più piccolo. Ma per ipotesi, C era già il più piccolo controesempio; quindi, la supposizione che ci fossero dei controesempi con cui cominciare doveva essere falsa. L'ordinamento parziale implicita 'minore' qui è quella che dice che S < T quando S ha meno nodi di T .

Guarda anche

Riferimenti

  • Hopcroft, John E .; Rajeev Motwani; Jeffrey D. Ullman (2001). Introduzione alla teoria, ai linguaggi e al calcolo degli automi (2a ed.). Messa di lettura: Addison-Wesley. ISBN   978-0-201-44124-6 .

Le prime pubblicazioni sull'induzione strutturale includono: