Indukcja strukturalna - Structural induction

Indukcja strukturalna jest metodą dowodową stosowaną w logice matematycznej (np. W dowodzie twierdzenia Łosia ), informatyce , teorii grafów i niektórych innych dziedzinach matematycznych. Jest to uogólnienie indukcji matematycznej na liczby naturalne i może być dalej uogólnione na dowolną indukcję Noetherian . Rekursja strukturalna to metoda rekursji mająca taki sam związek z indukcją strukturalną, jak zwykła rekursja ma związek ze zwykłą indukcją matematyczną .

Indukcja strukturalna służy do udowodnienia, że ​​pewne zdanie P ( x ) zachodzi dla wszystkich x jakiegoś rodzaju rekurencyjnie zdefiniowanej struktury, takiej jak formuły , listy lub drzewa . W strukturach zdefiniowano dobrze ugruntowany porządek częściowy („podformuła” dla formuł, „lista podrzędna” dla list i „poddrzewo” dla drzew). Dowód indukcji strukturalnej jest dowodem na to, że zdanie zachodzi dla wszystkich struktur minimalnych i że jeśli zachodzi dla bezpośrednich podstruktur pewnej konstrukcji S , to musi być zachowane również dla S. (Formalnie rzecz biorąc, spełnia to przesłanki aksjomatu dobrze ugruntowanej indukcji , który stwierdza, że ​​te dwa warunki są wystarczające, aby twierdzenie zachowało się dla wszystkich x .)

Strukturalnie rekurencyjna funkcja wykorzystuje tę samą koncepcję do definiowania funkcji rekurencyjnej: „przypadki podstawowe” obsługują każdą minimalną strukturę i regułę rekursji. Rekurencję strukturalną zwykle udowadnia się poprzez indukcję strukturalną; w szczególnie łatwych przypadkach często pomija się stopień indukcyjny. Funkcje length i ++ w poniższym przykładzie są strukturalnie rekurencyjne.

Na przykład, w przypadku struktury są listy, zwykle wprowadza się jeden częściowy rozkaz „<”, w którym L < M , gdy lista L jest ogon listy M . W tej kolejności pusta lista [] jest unikalnym minimalnym elementem. Strukturalny dowód indukcji jakiegoś zdania P ( L ) składa się zatem z dwóch części: dowodu, że P ([]) jest prawdziwe i dowodu, że jeśli P ( L ) jest prawdziwe dla jakiejś listy L , a L jest ogonem list M , to P ( M ) również musi być prawdziwe.

Ostatecznie może istnieć więcej niż jeden przypadek podstawowy i / lub więcej niż jeden przypadek indukcyjny, w zależności od tego, jak skonstruowano funkcję lub strukturę. W takich przypadkach strukturalny dowód indukcji pewnego twierdzenia P ( l ) składa się z:

  1. dowód, że P ( BC ) jest prawdziwe dla każdego przypadku bazowego BC ,
  2. dowód, że jeśli P ( I ) jest prawdziwe dla jakiegoś przykładu I , i M można uzyskać z I , stosując raz jedną regułę rekurencyjną, to P ( M ) również musi być prawdziwe.

Przykłady

Starożytne drzewo przodków, przedstawiające 31 osób w 5 pokoleniach

Drzewo przodków jest powszechnie znaną strukturą danych, przedstawiającą rodziców, dziadków itp. Osoby, o ile jest znana (patrz przykład na ilustracji). Jest zdefiniowany rekurencyjnie:

  • w najprostszym przypadku drzewo przodków przedstawia tylko jedną osobę (jeśli nic nie wiadomo o jej rodzicach);
  • alternatywnie drzewo przodków przedstawia jedną osobę i połączone gałęziami dwa poddrzewa przodków ich rodziców (używając dla zwięzłości dowodu uproszczonego założenia, że ​​jeśli jedna z nich jest znana, oboje są).

Na przykład właściwość „Drzewo przodków rozciągające się ponad g pokoleń wykazuje co najwyżej 2 g  - 1 osobę” można udowodnić za pomocą indukcji strukturalnej w następujący sposób:

  • W najprostszym przypadku drzewo przedstawia tylko jedną osobę, a więc jedno pokolenie; właściwość jest prawdziwa dla takiego drzewa, ponieważ 1 ≤ 2 1  - 1 .
  • Alternatywnie, drzewo przedstawia jedną osobę i drzewa jej rodziców. Ponieważ każda z tych ostatnich jest podstrukturą całego drzewa, można założyć, że spełnia sprawdzaną właściwość (czyli hipotezę indukcyjną ). Oznacza to, że można założyć p ≤ 2 g  - 1 i q ≤ 2 h  - 1 , gdzie g i h oznaczają liczbę pokoleń, nad którymi rozciąga się poddrzewo ojca i matki, a p i q oznaczają liczbę osób, które pokazać.
    • W przypadku g  ≤  h całe drzewo rozciąga się na 1 +  h pokoleń i pokazuje p  +  q  + 1 osób oraz p  +  q  + 1 ≤ (2 g  - 1) + (2 h  - 1) + 1 ≤ 2 h  + 2 h  - 1 = 2 1+ h  - 1 , czyli całe drzewo spełnia tę właściwość.
    • W przypadku, gdy h  ≤  g , całe drzewo rozciąga się na 1 +  g pokoleń i pokazuje p  +  q  + 1 ≤ 2 1 +  g  - 1 osób z podobnego rozumowania, tj. Całe drzewo spełnia tę własność również w tym przypadku.

Stąd, poprzez indukcję strukturalną, każde drzewo przodków spełnia tę właściwość.

Jako inny, bardziej formalny przykład rozważmy następującą właściwość list: 

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

Tutaj ++ oznacza operację konkatenacji list, a L i M to listy.

Aby to udowodnić, potrzebujemy definicji długości i operacji konkatenacji. Niech (h: t) oznacza listę, której głową (pierwszym elementem) jest h, a ogonem (listą pozostałych elementów) jest t , i niech [] oznacza pustą listę. Definicje długości i operacji łączenia są następujące: 

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

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

Nasza propozycja P ( l ) jest taka, że ​​EQ jest prawdziwe dla wszystkich list M, gdy L wynosi l . Chcemy pokazać, że P ( l ) jest prawdziwe dla wszystkich list l . Udowodnimy to poprzez wprowadzenie strukturalne na listach.

Najpierw udowodnimy, że P ([]) jest prawdziwe; to znaczy, EQ jest prawdziwe dla wszystkich list M, gdy L jest pustą listą []. Rozważ EQ: 

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

Więc ta część twierdzenia została udowodniona; EQ jest prawdziwe dla wszystkich M , gdy L wynosi [], ponieważ lewa i prawa strona są równe.

Następnie rozpatruje wszelkie listy niepusty I . Ponieważ I jest niepusty, ma element główny, x i listę końcową, xs, więc możemy to wyrazić jako (x: xs). Hipoteza indukcyjna jest taka, że ​​EQ jest prawdziwe dla wszystkich wartości M, gdy L wynosi xs : 

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

Chcielibyśmy pokazać, że jeśli tak jest, to EQ jest również prawdziwe dla wszystkich wartości M, gdy L = I = (x: xs). Postępujemy jak poprzednio: 

    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)

Zatem z indukcji strukturalnej otrzymujemy, że P (L) jest prawdziwe dla wszystkich list L.

Dobrze uporządkowane

Tak jak standardowa indukcja matematyczna jest równoważna zasadzie dobrego uporządkowania , tak indukcja strukturalna jest również odpowiednikiem zasady dobrego uporządkowania. Jeśli zbiór wszystkich struktur pewnego rodzaju dopuszcza dobrze ugruntowany porządek częściowy, to każdy niepusty podzbiór musi mieć element minimum. (To jest definicja „ uzasadnionego ”). Znaczenie lematu w tym kontekście polega na tym, że pozwala nam wywnioskować, że jeśli istnieją jakieś kontrprzykłady do twierdzenia, które chcemy udowodnić, to musi istnieć minimalny kontrprzykład. Jeśli możemy wykazać, że istnienie minimalnego kontrprzykładu implikuje jeszcze mniejszy kontrprzykład, mamy sprzeczność (ponieważ minimalny kontrprzykład nie jest minimalny), a zatem zbiór kontrprzykładów musi być pusty.

Jako przykład tego typu argumentu rozważ zbiór wszystkich drzew binarnych . Pokażemy, że liczba liści w pełnym drzewie binarnym jest o jeden większa niż liczba węzłów wewnętrznych. Załóżmy, że istnieje kontrprzykład; wtedy musi istnieć jeden z możliwie najmniejszą liczbą węzłów wewnętrznych. Ten kontrprzykład C ma n węzłów wewnętrznych i l liści, gdzie n  + 1 ≠  l . Ponadto C musi być nietrywialne, ponieważ drzewo trywialne ma n  = 0 i l  = 1, a zatem nie jest kontrprzykładem. C ma zatem co najmniej jeden liść, którego węzeł macierzysty jest węzłem wewnętrznym. Usuń ten liść i jego rodzica z drzewa, promując węzeł rodzeństwa liścia do pozycji zajmowanej wcześniej przez jego rodzica. Zmniejsza to zarówno n i L 1, a więc nowe drzewo również n  + 1 ≠  l , a zatem jest mniejsza kontrprzykładem. Ale zgodnie z hipotezą, C już było najmniejszym kontrprzykładem; dlatego też przypuszczenie, że na początku istniały jakieś kontrprzykłady, musiało być fałszywe. Częściowa zamawiania regulowane „mniejszy” jest tu taki, który stwierdza, że S < T , gdy S ma mniej węzłów niż T .

Zobacz też

Bibliografia

  • Hopcroft, John E .; Rajeev Motwani; Jeffrey D. Ullman (2001). Wprowadzenie do teorii automatów, języków i obliczeń (wyd. 2). Czytanie Mszy: Addison-Wesley. ISBN   978-0-201-44124-6 .

Wczesne publikacje na temat indukcji strukturalnej obejmują: