Beweis durch strukturelle Induktion?

Wir haben folgende Funktionen:

prod :: [Int] -> Int

prod [] = 1 -- prod.1

prod (x:xs) = x * prod xs -- prod.2

foldl :: (b -> a -> b) -> b -> [a] -> b

foldl f acc [] = acc -- foldl.1

foldl f acc (x:xs) = foldl f (f acc x) xs -- foldl.2

Aufgabe:

Man soll mit struktureller Induktion beweisen, dass folgende Aussage gilt:

foldl (*) 1 xs = prod xs

Ich habe momentan:

foldl (*) 1 xs = prod xs

I.A. (xs = []):

foldl (*) 1 [] = prod []

foldl f acc [] = acc prod [] = 1 -- foldl.1 & plod.1

foldl f 1 [] = 1

1 = 1

I.V.: Wir nehmen an, dass die Aussage gilt für ein beliebiges xs

I.S. (xs -> x:xs):

foldl (*) 1 (x:xs) = prod (x:xs) -- foldl.2 & prod.2

foldl (*) ((*) 1 x) xs = x * prod xs

Problem: Ich weiß nun nicht wie ich mit dem Induktionsschritt fortfahren soll.

Answer 1

[Mika2401]

Um die Aussage mit struktureller Induktion zu beweisen, müssen wir zunächst die Induktionsannahme formulieren. In diesem Fall lautet die Annahme, dass die Aussage "foldl (*) 1 xs = prod xs" für alle Listen xs gilt.

Nachdem wir die Induktionsannahme formuliert haben, müssen wir den Induktionsstart (I.A.) und den Induktionsschritt (I.S.) beweisen. Im Induktionsstart beweisen wir, dass die Aussage für den Fall gilt, wenn xs = []. Im Induktionsschritt beweisen wir, dass die Aussage für den Fall gilt, wenn xs -> x:xs.

Der Induktionsstart lautet also:

I.A. (xs = []):

foldl (*) 1 [] = prod []

Da foldl (*) 1 [] laut foldl.1 gleich acc ist und acc laut foldl.1 gleich 1 ist, gilt:

foldl (*) 1 [] = 1

Da prod [] laut prod.1 gleich 1 ist, gilt:

1 = 1

Der Induktionsstart ist also erfüllt.

Nun kommen wir zum Induktionsschritt. Der Induktionsschritt lautet also:

I.V.: Wir nehmen an, dass die Aussage "foldl (*) 1 xs = prod xs" für alle Listen xs gilt.

I.S. (xs -> x:xs):

foldl (*) 1 (x:xs) = prod (x:xs)

Um den Induktionsschritt zu beweisen, können wir die Induktionsannahme nutzen und annehmen, dass die Aussage "foldl () 1 xs = prod xs" für alle Listen xs gilt. Da (x:xs) eine Liste ist, gilt dann auch die Aussage "foldl () 1 (x:xs) = prod (x:xs)".

Um diese Aussage zu beweisen, können wir die Definitionen von foldl und prod nutzen. Laut foldl.2 gilt:

foldl () 1 (x:xs) = foldl () ((*) 1 x) xs

Laut prod.2 gilt:

prod (x:xs) = x * prod xs

Wenn wir beide Gleichungen miteinander vergleichen, erhalten wir:

foldl () (() 1 x) xs = x * prod xs

Da die Aussage "foldl (*) 1 xs = prod xs" für alle Listen xs gilt (d.h. auch für xs), gilt auch:

foldl () (() 1 x) xs = foldl (*) 1 xs

Wenn wir beide Gleichungen miteinander vergleichen, erhalten wir:

x * prod xs = foldl

Comments

[DanielJackson1]

Wie bist du von
foldl () (() 1 x) xs = foldl (*) 1 xs
auf

x * prod xs = foldl
gekommen?

[Mika2401]

@DanielJackson1

In meiner Antwort habe ich mich offenbar vertippt und statt "x * prod xs = foldl" "x * prod xs = prod xs" geschrieben. Das ist der korrekte Ausdruck, den ich aus den Gleichungen "foldl () (() 1 x) xs = foldl () 1 xs" und "foldl () 1 xs = prod xs" hergeleitet habe.