Noethersche Induktion

163

Motivation: noethersche Relationen

Noethersche Relationen sind direkt verknüpft mit Terminierung:

• Wie kann man formal ausdrücken, dass die Schleifewhile test do prog anhält?

• Betrachte Folge der Zustände zu Beginn der Schleife: s0, s1, s2, . . ..

• Terminierung gilt genau dann, wenn für jedes s0 die Folge endlich ist.

• Definiere also: s′ ≪ s⇔ s erfüllt test und s′ entsteht aus s durchAbarbeitung von prog

• Analog für eine rekursive Definition einer Funktion/Methode f:s′ ≪ s⇔ Wenn man f mit s aufruft, findet ein rek. Aufruf mit s′ statt(man erhält jetzt evtl. mehrere s′, i.e. einen Aufrufsbaum)

• Kriterium für Terminierung ist: Die Relation ≪ enthält keine unendlichenabsteigenden Folgen . . .≪ s2 ≪ s1 ≪ s0.

164

Noethersche Relationen

Definition (Noethersche Relationen)Sei ≪ ⊆ A×A. Die Relation ≪ heißt noethersch (oder wohlfundiert, engl.well-founded) wenn es keine unendlichen ≪-Ketten gibt:

. . .≪ a3 ≪ a2 ≪ a1 ≪ a0

Beispiele:

• < auf natürlichen Zahlen ist noethersch, aber nicht >

• < auf ganzen Zahlen ist nicht noethersch

• m ≪ n ⇔ n = m + 1 ist noethersch (nicht transitiv)

• ⊂ (echte Teilmenge) ist noethersch auf endlichen Mengen(Warum nicht auf unendlichen?)

165

Eigenschaften noetherscher Relationen

• ≪ ist immer irreflexiv

• Die Relation muss nicht transitiv sein, ihre transitive Hülle ist aber auchnoethersch (und transitiv)deshalb häufig o.B.d.A nur noethersche Ordnungen betrachtet

• Die Relation muss kein eindeutiges kleinstes Element besitzen.Beispiel: echte Teilmenge auf nichtleeren Mengen

• kleinstes Element existiert 6⇒ noethersch.Beispiel: < auf rationalen Zahlen, die ≥ 0 sind.

• Wenn < noethersch und ≪ stärker, i.e. x≪ y → x < y,dann erst Recht ≪ noethersch

166

Bedeutung noetherscher Relationen

Bedeutung:

• betrachte Folge der Zustände, die ein Programm durchläuft.Definiere s′ ≪ s :⇔ s′ ist Nachfolgezustand von s

Dann gilt: ≪ noethersch ⇔ Programm terminiert immer

• stärkeres Induktionsprinzip als strukturelle Induktion:noethersche Induktion

• Nicht behandelt: Zu noetherscher Induktion gehörenwohlfundiert rekursive Definitionen.(Analog zu: strukturelle Induktion vs. rekursive Definition)

167

Beispiele für noethersche Prädikate

Ordnungsprädikate: Ordnungsprädikate < von Datendefinitionen sindnoethersch.

Zur Erinnerung: x < y ⇔ „x (als Konstr.term) ist echter Unterterm von y“.Z. Bsp. bei Listen : x < a + x, x < a + (b + x), x 6= [] → [] < xkeine Grössenordnung, nicht: a + x < a + b + x (ausser wenn a = b)

Größenordnung:Sei size : s→ nat. Dann ist ≪ noethersch mit

x≪ y :↔ size(x) < size(y).

Lexikalische Ordnung:Betrachte Spezifikation Pair2 von vorher. Seien <1 : elem× elem und <2 :elem× elem noethersch. Dann auch ≪ mit

mkpair(a, b) ≪ mkpair(a′, b′) :⇔ a <1 a′ ∨ (a = a′ ∧ b <2 b

′).

168

Noethersche Induktion

Satz (Noethersche Induktion)Genau für noethersche Relationen ≪ gilt:Wenn für jedes a aus E(a′) für alle Elemente a′ ≪ a die Aussage E(a)gefolgert werden kann, so gilt E für alle Elemente:

(∀ a. (∀ a′. a′ ≪ a⇒ E(a′)) ⇒ E(a)) ⇒ ∀ b. E(b)

Definition (Noethersche Induktionsregel)Sei y := free(Γ ⊢ ∆) \ {x} und ≪ noethersch. Induktion über x:

IND(≪)

∀ y.∀ x′. x′ ≪ x→ (∧Γ →

∨∆)x

′

x ,Γ ⊢ ∆

Γ ⊢ ∆

speziell für Formel:

∀ y.∀ x′. x′ ≪ x→ ϕx′

x ⊢ ϕ

⊢ ϕ

169

Noethersche Induktion (Beispiele)

Beispiel: Natürliche Zahlen

∀ n0. n0 < n→ ϕ(n0) ⊢ ϕ(n)

⊢ ∀ n. ϕ(n)

Beispiel: Listen

∀ l0. (l0 ≪ l) → ϕ(l0) ⊢ ϕ(l)

⊢ ∀ l. ϕ(l)

170

Noethersche Induktion in KIV

• In KIV ist die Regel induction für noethersche Induktion vorhanden

• Für Variablen x eines freien Datentyps wird angeboten⋆ Ind. über vordefiniertes Ordnungsprädikat

(pro Sorte eines; Induktion über x wird angeboten)⋆ Ind. über vordedefinierte Grössenfunktion

(pro Sorte eine Fkt. #; Induktion über # x)

• Grössenfunktionen für nichtfreie Datentypen kann man mit„Unit-Add HeuristicInfo“ addieren

• es ist auch möglich einen Term anzugeben, über dessen Grösseinduziert wird (z.Bsp. # x−# y)

• Die Induktionshypothese wird in KIV mit Ind-Hyp abgekürzt.

• „Goal-Again with Ind-Hyp“ zeigt die Induktionshypothese an.

• Anwendung der Induktionshypothese mit apply induction (statt all left )

171

Sequentielle Programme,Hoare-Logik und

Dynamische Logik

172

Was ist ein SW-System mathematisch?

1. Sicht: operational

Ein SW-System ist ein Automat

• mit Zustand,

• Zustandsübergängen und

• mit Abläufen.

2. Sicht: algebraisch

Ein SW-System ist eine Algebra, d. h. ein System von Daten undOperationen.

173

Grundidee für Programme

Hilfsmittel: Begriffe von Signatur, Algebra und Belegung aus derPrädikatenlogik

• Datentypen in den Programmen sind beliebigealgebraisch spezifizierte Datentypen(daher heißen die Programme abstrakte Programme)

• Programmvariablen sind Variablen der Prädikatenlogik

• Ein Zustand eines Programms ist eine Belegung der Prädikatenlogik

• Kopiersemantik, d.h. Änderung an einer Variablen ändert keine andere(eine Variable ist kein Zeiger auf ein Objekt)

• Variablen haben keine Adressen(kein &x wie in C)

174

Programme: Syntax

Programme Prog(Σ,X) (Notation: α, β, γ)

• parallele Zuweisung: x1 := t1, x2 := t2, . . . , xn := tnVariablen aus X, Terme aus T (Σ, X), kurz: x := t

• { α; β } (geschachtelte { } weglassen)

• Schleife (ε ist quantorenfreie Formel): while ε do α

• Fallunterscheidung: if ε then α else β

• lokale Variablen: let x1 = t1, x2 = t2, . . . , xn = tn in α

• das Programm, das nichts tut: skip(Abkürzung: if ε then α ≡ if ε then α else skip )

• das Programm, das nie terminiert: abort(kann als Abkürzung definiert werden: while true do skip )

• Prozeduren später

175

Programme: Semantik (1)

Für eine Σ-Algebra A betrachtet man die MengeST:={v | v :

⋃s∈S Xs → As}

der Variablenbelegungen.

Für sequentielle Programme sind nicht alle Zwischenzustände interessant,es genügt, Anfangs- und Endzustände zu betrachten.

Erster Versuch: Ein Programm überführt einen Anfangszustand in einenEndzustand:

[[α]] : ST → ST

176

Programme: Semantik (1)

Für eine Σ-Algebra A betrachtet man die MengeST:={v | v :

⋃s∈S Xs → As}

der Variablenbelegungen.

Für sequentielle Programme sind nicht alle Zwischenzustände interessant,es genügt, Anfangs- und Endzustände zu betrachten.

Erster Versuch: Ein Programm überführt einen Anfangszustand in einenEndzustand:

[[α]] : ST → ST

Probleme mit dieser Semantik:

• Was ist die Semantik von abort ?

• Wie auf indeterministische Programme erweitern?176

Programme: Semantik (2)

Deshalb: relationale Semantik:

[[α]] ⊆ ST × ST

• (v, v′) ∈ [[α]] bedeutet: Zustand v wird von α in v′ überführt

• Wenn zu v kein v′ mit (v, v′) ∈ [[α]] vorhanden ist:α terminiert nicht, wenn in v gestartet

• Wenn {(v, v′), (v, v′′)} ⊆ [[α]], so ist das Programm mit v gestartetindeterministisch mit 2 möglichen Endzuständen: v′ und v′′

• derzeit betrachtete Programme sind deterministisch:Zu jedem v höchstens ein v′

177

Programme: Semantik (3)

Man definiert die relationale Semantik eines Programmes bzgl. der AlgebraA rekursiv wie folgt:

[[abort ]] := ∅

[[skip ]] := {(v, v) | v ∈ ST}

[[x := t]] := {(v, w) | w = v[[t]]

A,v

x }

[[α; β]] := {(u,w) | es gibt v : (u, v) ∈ [[α]] und (v, w) ∈ [[β]]}

[[if ε then α else β]] := {(v, w) | A, v |= ε und (v, w) ∈ [[α]] oder

A, v |= ¬ε und (v, w) ∈ [[β]]}

[[let x = t in α]] := {(v, wv(x)x ) | (v

[[t]]A,v

x , w) ∈ [[α]]}

[[while ε do α]] :=⋃

i∈N

[[(if ε then α)i; if ε then abort ]]

wobei α0 := skip , αi+1 := α; αi

178

Korrektheitsbegriffe für Programme

Partielle Korrektheit: ϕ {α} ψ

Falls zu Beginn ϕ gilt und α terminiert, dann gilt anschließend ψ

Semantik: A |= ϕ {α} ψ ⇔ für jedes v mit A, v |= ϕ und jedes w mit(v, w) ∈ [[α]] gilt A, w |= ψ

Totale Korrektheit: ϕ 〈α〉 ψ

Falls zu Beginn ϕ gilt, dann terminiert α und anschließend gilt ψ

Semantik: A |= ϕ 〈α〉 ψ ⇔ für jedes v mit A, v |= ϕ gibt es w mit (v, w) ∈ [[α]]es gilt A, w |= ψ

In der Literatur findet man auch die Notation {ϕ}α{ψ}(für sowohl partielle als auch totale Korrektheit).

179

Beispiele zur Korrekheit

Partielle Korrektheit:

|= true { x:= 2 } x = 2

|= x = 2 { x:= x+1 } x = 3

|= x = y { x:= x +1} x−1 = y

|= x = a ∧ y = b { x:= y, y := x} x = b ∧ y = a

|= x = 2 { abort } x > 2

Unterschied partielle und totale Korrektheit:

|= true { if y=0 then abort else x:=1 } x = 1

6|= true 〈if y=0 then abort else x:=1 〉 x = 1

|= y 6= 0 〈if y=0 then abort else x:=1 〉 x = 1

180

Der Hoare-Kalkül

Floyd, C. A. R. Hoare, Oxford 1969

SP ⊢HC ϕ{α}ψ

HC: Besteht aus Regeln zur Behandlung von Programmen und den Regelndes Sequenzenkalküls

181

Regeln des Hoare-Kalküls (1)

skip-Regel:

ϕ {skip } ϕ

abort-Regel:

ϕ {abort } ψZuweisungs-Regel:

ϕtx {x := t} ϕ

compound-Regel:

ϕ {α} χ χ {β} ψ

ϕ {α; β} ψ

wobei die Zwischenbedingung χ selbst gesucht werden muss.

182

Regeln des Hoare-Kalküls (2)

conditional-Regel:

ϕ ∧ ε {α} ψ ϕ ∧ ¬ ε {β} ψ

ϕ {if ε then α else β} ψ

while-Regel:

⊢ ϕ→ INV INV ∧ ε {α} INV ⊢ INV ∧ ¬ ε→ ψ

ϕ {while ε do α od} ψ

wobei die Schleifeninvariante INV selbst gesucht werden muss

183

Hoare-Kalkül für totale Korrektheit

Frage: Wie ändert sich der Kalkül, wenn man totale Korrektheit betrachtet?

Antwort: Genau da, wo Nichtterminierung auftreten kann: abort und while .

Ersetze also die geschweiften Klammern durch spitze und ändere dieabort - und while -Regel ab, um Nichtterminierung zu verhindern.

Dies ergibt den totalen Hoare-Kalkül (THC):

SP ⊢THC ϕ〈α〉 ψ

abort-Regel:⊢ ¬ϕ

ϕ 〈abort 〉 ψ

abort ist nur dann total korrekt, wenn die Vorbedingung nie auftritt.

184

Hoare-Kalkül: while-Regel für Totale Korr.

Bedingung bei while -Regel: Schleife darf nur endlich oft durchlaufenwerden!

Benutze dazu noethersche Ordnung ≪ und einen Term t (z.B. Länge einerListe), der bzgl. ≪ kleiner wird, sowie eine Variable v 6∈ V ar(α).

while-Regel:

⊢ ϕ→ INV INV ∧ ε ∧ v = t 〈α〉 INV ∧ t≪ v ⊢ INV ∧ ¬ ε→ ψ

ϕ 〈while ε do α od〉 ψ

wobei die Schleifeninvariante INV und der Term t selbst gesucht werdenmuss

Intuition: v merkt sich den alten Wert von t. t muss nach der Schleifenoethersch kleiner geworden sein ⇒ sie wird nur endlich oft durchlaufen.

185

Dynamische Logik

A. Salwicki 1970 (“algorithmische Logik”),V.R. Pratt 1976, D. Harel 1977

Idee: Erfinde nicht einfach einen komplett neuen Kalkül für neue Objekte(hier: Hoare-Tripel) sondern bilde Programmformeln und erweitere Kalkülum diese neuen Formeln.

186

Dynamische Logik: Syntax

Die Menge DLFor(Σ,X) der DL-Formeln über der Signatur Σ und derVariablenmenge X enthält

• Alle prädikatenlogischen Formeln von For(Σ,X)

• Für α ∈ DLProg(Σ,X) und ϕ ∈ DLFor(Σ,X) auch⋆ [α]ϕ („box alpha phi“)

Informelle Bedeutung: „Wenn α terminiert, gilt nachher ϕ“⋆ 〈α〉ϕ („diamond alpha phi“)

Informelle Bedeutung: „α hält, und nachher gilt ϕ“

Klassifikation:

• Dynamische Logik ist eine (Multi-)Modallogik.

• Modallogik mit Formeln ⋄ ϕ (und 2 ϕ) stammen aus der Philosophie:“ich weiss ϕ” “ich glaube ϕ”, “ϕ ist möglich”

• Temporallogik: “irgendwann wird ϕ wahr sein”187

Bemerkungen zur Syntax

• Boxen und Diamonds binden stärker als Aussagenlogik:[α]ψ ∧ χ bedeutet ([α]ψ) ∧ χ

• Schachtelung möglich:〈α〉〈β〉ψ bedeutet 〈α〉 ( 〈β〉ψ )

• Auch gemischte Schachtelung ist erlaubt: [α] ∀ x. ϕ ∧ 〈β〉ψ

• Auch in DL betrachtet man Sequenzen, z.B. 〈α〉ψ,Γ ⊢ ∆.

• Wenn x in α vorkommt, x0 aber nicht, so besagt〈α〉 x = x0 : “Am Ende von α hat x den Wert, den x0 jetzt hat”

• 〈α〉 x = x0 → 〈β〉 x = x0 bedeutet:“Wann immer α in x einen Wert x0 ausrechnet so tut das auch β”Man kann in DL also über Programmähnlichkeit reden

• Es gilt: [α]ψ ↔ ¬ 〈α〉¬ ψ

Man könnte also Box mit Hilfe von Diamond definieren

188

Semantik der Dynamischen Logik

Die Semantik von Formeln der Prädikatenlogik wird erweitert durch

A, v |= [α]ψ :⇔ für alle w : (v, w) ∈ [[α]] ⇒ A, w |= ψ.A, v |= 〈α〉ψ :⇔ es gibt w : (v, w) ∈ [[α]] und A, w |= ψ.

Damit gilt

A, v |= ϕ{α}ψ ⇔ A, v |= ϕ→ [α]ψ

A, v |= ϕ〈α〉 ψ ⇔ A, v |= ϕ→ 〈α〉ψ,

Hoare-Tripel sind also spezielle Formeln der Dynamischen Logik.

189

Dynamische Logik: Beispiele

|= [x := 1] x = 1

|= x = x0 → [x := x + 1] x = x0 + 1

|= x = x0 → 〈x := x + 1〉 x = x0 + 1

Unterschied Box/Diamond:|= x = 5 → [abort ] x = 5

6|= x = 5 → 〈abort 〉 x = 5

Sequenzen mit Programmen, Programme auch im Antezedent:|= x = x0 ⊢ [x := x + 1] x = x0 + 1

|= x > 0 ⊢ 〈while x > 1 do x := x -1〉 x = 1

|= 〈if x > 0 then y := 1 else abort 〉 y = y0 ⊢ y0 = 1 ∧ x > 0|= [if x > 0 then y := 1 else abort ] y = y0 ⊢ y0 = 1 ∧ x > 0 ∨ x = 0

190

Kalkül für Dynamische Logik

Grundidee: Symbolische Ausführung von Programmen

Betrachte Ausführung des Programms

α1; α2; . . . ; αn (αi ohne ; (compound) auf top-level)

• Annahme: Initialer Zustand erfüllt Vorbedingung ϕ0

• Berechne ϕ1, die stärkste Formel, die nach α1 gilt

• Berechne ϕ2, die stärkste Formel, die nach α1; α2 gilt

• . . . solange bis das Programm verschwunden ist

• Zum Schluss: Teste ob ϕn die Nachbedingung impliziert (nur noch PL)

• Gegenüber Hoare-Kalkül: kein Raten von Zwischenformeln bei seq.Ausführung, Zuweisung vorwärts ausführen!

• Symb. Ausführung geht sowohl im Antezedent als auch im Sukzedent!

191

DL-Kalkül: Normalisierung

normalize right

Γ ⊢ 〈α〉〈β〉ψ,∆

Γ ⊢ 〈α; β〉ψ,∆

Γ ⊢ [α][β]ψ,∆

Γ ⊢ [α; β]ψ,∆

normalize left

〈α〉〈β〉ψ,Γ ⊢ ∆

〈α; β〉ψ,Γ ⊢ ∆

[α][β]ψ,Γ ⊢ ∆

[α; β]ψ,Γ ⊢ ∆

In KIV: Nie explizit angewandt, die erste Anweisung wird bei jederRegelanwendung (in allen Programmformeln) immer automatischabgespalten. KIV rotiert immer die Programmformeln nach vorne.

192

DL-Kalkül: Zuweisungen (1)

assign right (Hoare-Regel in DL)

Γ ⊢ ψτx,∆

Γ ⊢ [x := τ ]ψ,∆

assign right (Dynamische Logik)

Γ, x′ = τ ⊢ [αx′

x ]ψx′

x ,∆

Γ ⊢ [x := τ ][α]ψ,∆

wobei x′ eine neue Variable ist (bezeichnet den neuen Wert von x)

Beachte: Programmvariablen werden umbenannt!

193

DL-Kalkül: Zuweisungen (2)

• In KIV: assign right kombiniert beide Regeln:⋆ Original-Hoare-Regel, falls nach der Zuweisung ψ kein Programm

mehr enthält⋆ Sonst die DL Regel

• Die Regel gilt genau gleich auch für Diamonds statt Boxen

• Die Regel für Zuweisung auf der linken Seite sieht genauso aus:

assign left

x′ = τ, [αx′

x ]ψx′

x ,Γ ⊢ ∆

[x := τ ][α]ψ,Γ ⊢ ∆

wobei x′ eine neue Variable ist

194

DL-Kalkül: Regeln für if

Der Kalkül der dynamischen Logik besteht u. a. aus den Regeln desHoare-Kalküls, wie z. B.

if right

Γ, ε ⊢ [α]ψ,∆ Γ,¬ ε ⊢ [β]ψ,∆

Γ ⊢ [if ε then α else β]ψ,∆

if positive right

Γ, ε ⊢ [α]ψ,∆ Γ ⊢ ε,∆

Γ ⊢ [if ε then α else β]ψ,∆

Analog: if negative right , if left etc.. KIV versucht immer die Tests zuentscheiden (per Simplifier), damit nur eine Prämisse entsteht.

195

DL-Kalkül: while-Regel

invariant right

Γ ⊢ INV ,∆ INV , ε ⊢ [α]INV INV ,¬ ε ⊢ ψ

Γ ⊢ [while ε do α]ψ,∆

invariant right

Γ ⊢ INV ,∆ INV , ε, v = t ⊢ 〈α〉(INV ∧ t≪ v) INV ,¬ ε ⊢ ψ

Γ ⊢ 〈while ε do α〉ψ,∆

KIV: Die Schleifeninvariante INV und im zweiten Fall auch die Schranke tmuss von Hand eingegeben werden (v ist neue Variable)

196

DL-Kalkül: Regeln für skip und abort

skip rightΓ ⊢ ψ,∆

Γ ⊢ 〈skip 〉ψ,∆

Γ ⊢ ψ,∆

Γ ⊢ [skip ]ψ,∆

skip leftψ,Γ ⊢ ∆

〈skip 〉ψ,Γ ⊢ ∆

ψ,Γ ⊢ ∆

[skip ]ψ,Γ ⊢ ∆

abort rightΓ ⊢ ∆

Γ ⊢ 〈abort 〉ψ,∆ Γ ⊢ [abort ]ψ,∆

abort left

〈abort 〉ψ,Γ ⊢ ∆Γ ⊢ ∆

[abort ]ψ,Γ ⊢ ∆

197

DL-Kalkül: lokale Variablen

vardecls right

x′ = τ ,Γ ⊢ 〈αx′

x 〉ϕ

Γ ⊢ 〈let x = τ in α〉ϕ

vardecls left

〈αx′

x 〉ϕ, x′ = τ ,Γ ⊢ ∆

〈let x = τ in α〉ϕ,Γ ⊢ ∆

x′ sind neue Variablen (bezeichnen die lokalen Variablen).Dieselben Regeln gelten auch für Boxen.

198

Beispiel zur Korrekheit

Liste nat. Zahlen x:

m := x.first, x0 := x.rest;while x0 6= [] do

{if x0.first > m then m := x0.first ;x0 := x0.rest

}

199

Beispiel zur Korrekheit

Maximum einer nichtleeren Liste nat. Zahlen x:

x 6= []⊢ 〈m := x.first, x0 := x.rest;while x0 6= [] do

{if x0.first > m then m := x0.first ;x0 := x0.rest

}〉m = maxl(x)

wobei maxl([]) = 0, maxl(n+ x) = max(n,maxl(x))

199

Zur nächsten Aufgabe

Invarianten vorher überlegen!!!

200