Informatik Forsch. Entw. (1996) 11: 53–60

c© Springer-Verlag 1996

Theorembeweisen in hierarchischen bedingten Spezifikationen?

J. Avenhaus, K. Madlener

Fachbereich Informatik, Universitat Kaiserslautern, Erwin-Schrodinger-Strasse, D-67663 Kaiserslautern

Eingegangen am 19. Juli 1994 / Angenommen am 7. November 1995

Zusammenfassung.In der Arbeit werden klausale Spezifi-kationen zur Beschreibung von Programmen auf der Ebenedes funktionalen Entwurfs betrachtet. Die Axiome solch ei-ner Spezifikationspec bestehen aus positiv/negativ beding-ten Gleichungen, die neue Operatorenuber einer fest einge-bauten AlgebraA definieren. Wir definieren als Semantikvon spec eine AlgebraAspec, die initial in der Klasse allerModelle ist. Es wird ein Inferenzsystem angegeben, mit demman die Gultigkeit von positiv/negativ bedingten Gleichun-gen inAspec beweisen kann. Dieses Inferenzsystem erlaubtes auch, die Gultigkeit von Behauptungen zu widerlegen.

Schlusselworter: Klausale Spezifikation, partiell definierteOperatoren, hierarchische Termersetzungssysteme, indukti-ves Beweisen

Abstract. Clausal specifications for the description of sy-stems on the functional design level are studied. The axiomsof such a specificationspec are positive/negative conditionalequations which define new operators over a built-in algebraA. We define the semantics ofspec by an algebraAspec

which is initial in the class of all models which preserveA. An inference system for proving validity of clauses inAspec is provided which also allows to refute non validclauses.

Key words: Clausal specification, partially defined opera-tors, hierarchical term rewriting, inductive theorem proving.

CR Subject Classification:F.3.1, F.3.2, F.4.1.

1 Einleitung

Bei der Entwicklung großer Softwareprodukte ist es wun-schenswert, die Produkte auf jeder Ebene der Entwicklungzu beschreiben. Wir benutzen die Methode der algebraischenSpezifikation zur Beschreibung der Produkte auf der Ebenedes funktionalen Entwurfs. Dies soll es ermoglichen, uberdas Produkt auf Grund der Beschreibung ein Reasoning zubetreiben, also Aussagen zu beweisen.

? Diese Arbeit wurde durch die Deutsche Forschungsgemeinschaftgefordert. Sie entstand im SFB 314, Projekt D4.

Um dies zu erreichen, sollte eine Spezifikationsspracheverwendet werden, die genugend ausdrucksstark ist, einewohldefinierte Semantik hat und es erlaubt, Beweise zufuhren.

Wir verwenden dazu die Sprache der ”klausalen Spe-zifikation”. Eine klausale Spezifikation ist eine Menge vonbedingten Gleichungen der FormB ⇒ l = r, wobei Beine Konjunktion von Gleichungen und negierten Gleichun-gen ist. Jede bedingte Gleichung ist implizit all-quantifiziert,sie ist logisch gesehen also eine Klausel. Um die Gleichungoperational anwendbar zu machen, verlangen wir, daß dieLiterale inB in einem wohldefinierten Sinn bezuglich einerNoetherschen Partialordnung kleiner sind als die Konklusionl = r. Dies erlaubt es, jeder Spezifikation ein eindeutigesModell zuzuordnen.

Es ist klar, daß das Erlauben von negativen Bedingungen(negierten Gleichungen) die Ausdruckskraft gegenuber nurpositiven Bedingungen in Spezifikationen schon erheblichvergroßert. Dies reicht fur praktische Zwecke aber nicht aus.Wunschenswert waren folgende Gesichtspunkte:

(1) Man kann feste Strukturen einbauen, etwa die ganzenZahlenZ, die rationalen ZahlenQ, Listen uberZ undanderes mehr (Built-in-Algebra).

(2) Die Spezifikation definiert Operatorenuber der einge-bauten Algebra nur partiell.

(3) Die Spezifikation ist monoton erweiterbar, d.h., Satzebleiben nach der Erweiterung gultig. (Dies ist nicht tri-vial, wie das folgende Beispiel 2 zeigt.)

Wir gehen also von folgendem Szenario aus: Gegebenist eine feste (eingebaute) AlgebraA und eine Spezifika-tion spec, dieuberA neue Operatoren (partiell) spezifiziert.Festzulegen sind dann

a) eine denotationale Semantik vonspec in Form einer ka-nonischen AlgebraAspec. Dies kann auf verschiedeneWeise geschehen, entweder mit einer Noetherschen Ord-nung� und dem perfekten Modell vonspec bezuglich� oder durch ”konstruktive Absicherung der negativenBedingungen inA”. Wir beschreiben hier den zweitenAnsatz, fur den ersten Ansatz siehe [6] und [5].

b) die operationale Semantik. Dies geschieht mit Technikender Termersetzung. Beide Semantiken stimmenuberein.

54

c) ein Inferenzsystem zum Beweis von Aussagen der Form”Formel A gilt in Aspec”.

d) ein praktisch einsetzbarer Theorembeweiser auf der Ba-sis des Inferenzsystems.

Wir verdeutlichen dies an Beispielen. Dabei werden dieneuen OperatorenuberA stets durch ein Gleichungssystembeschrieben.

Beispiel 1.1ggT aufN: eingebaute TheorieSeiA = (N; +,−,≥) die Algebra der naturlichen Zahlen.

E : g(x, 0) = xg(0, y) = yg(x, y) = g(x− y, y) if x ≥ y = true, y 6= 0g(x, y) = g(x, y − x) if y ≥ x = true, x 6= 0

Dann spezifiziertE den Operatorg als g(x, y) =großter ge-meinsamer Teiler vonx und y. Beweisaufgabe:g(x, y) =g(y, x) gilt in Aspec.

Beispiel 1.2Partiell spezifizierter Operator ”− ”: Spezifi-kationserweiterungSeiA das initiale Modell zuE0,

E0 : x + 0 = x x + s(y) = s(x + y)

und seiE leer. Dann gilt0 +x = x in Aspec.Es werdeE erweitert zuE′ um die (partielle) Spezifikationfur den Operator−:

E′ : x− 0 = x s(x)− s(y) = x− y

Hier ist zu klaren, welche Werte die Variablen in Gleichun-gen annehmen durfen. Darf x jeden Term als Wert anneh-men, so gilt0 +x = x in Aspec′ nicht. Es gilt namlich z.B.nicht 0 + (0− s(0)) = 0− s(0) in Aspec′ , da 0− s(0) einnicht definierter (oder Junk-) Term ist. Bei dieser Festlegungist also das Prinzip (3) der monotonen Erweiterbarkeit vonSpezifikationen verletzt. Wir legen daher fest, daßx nur Kon-struktorterme (also Terme in0, s und +) als Wert annehmendarf. Dann gilt0 +x = x in Aspec′ , und das Prinzip (3) isterfullt. Man beachte, daß man den Operator− unterschied-lich total spezifizieren kann, etwa durch die zusatzliche Glei-chung0− s(y) = 0 (dann wird− als ”Minus aufN” spezifi-ziert) oder durch0− s(y) = s(y) (dann wird− spezifiziert zux− y =| x− y |). Es gilt (x+ y)− y = x in Aspec′ , und diesbleibt (wie auch0 + x = x) in beiden Erweiterungenspec′′gultig.

Beispiel 1.3Klausale SpezifikationSeiA das initiale Modell zuE0 = ∅

und E : even(0) = trueeven(s(x)) = false if even(x) = trueeven(s(x)) = true if even(x) 6= trueodd(s(0)) = trueodd(s(s(x)) = odd(x)

Beweisaufgabe: Es gilteven(x) = true ∨ odd(x) = true inAspec

Wir vergleichen hier kurz unseren Spezifikationsansatz mitAnsatzen aus der Literatur. Es gibt kaum Arbeitenuber dieklausale Spezifikation von abstrakten Datentypen. In der Re-gel werden nur positiv bedingte Gleichungen als Axiome inE zugelassen. Definiert außerdemE die neuen Operatorentotal, so ist die Erweiterung vonA hinreichend vollstandig

und es gibt keine Junk-Terme. In diesem Fall ist die Seman-tik von spec leicht zu definieren. Es ist die Quotientenalge-bra T (F ) /=E ein ausgezeichnetes Modell vonspec, es istinitial in der Klasse aller Modelle.

Enthalt E auch negativ bedingte Gleichungen, so gibt esi.a. kein initiales Modell vonspec. Definiert E die neuenOperatoren nicht total, so werden haufig partielle Algebrenals Modelle betrachtet [9], [14]. Hier tritt das Problem auf,die Gleichheit angemessen zu definieren: zwei Termet1, t2ohne Variablen heißenstark gleich (t1 =s t2) in einerAlgebra B , wenn sie entweder beide definiert und gleichoder beide undefiniert sind. Sie heißenexistentiell gleich(t1 =e t2), wenn sie beide definiert und gleich sind. Imersten Fall sind also je zwei Junk-Terme gleich, im zwei-ten Fall sind je zwei Junk-Terme verschieden. Dies ent-spricht sicher nicht der Intuition. Die Problematik verscharftsich bei der Definition der Gultigkeit einer bedingten Glei-chung u = v =⇒ t1 = t2. In [9] wird dies erklart durchu =e v =⇒ t1 =s t2.

Wir definieren die operationale E-Gleichheit auf allenTermen durch reines Gleichungsschließen. Dabei tritt dasProblem auf, wie negative Bedingungen ausgewertet werdensollen. Wir tun dies durch eine konstruktive Absicherung derUngleichheit in der BasisalgebraA. Die positiven Bedin-gungen werden wieublich durch reines Gleichheitsschließenausgewertet. Diese Festlegung garantiert, daß Spezifikatio-nen (wie oben beschrieben) monoton erweiterbar sind. Wirgehen in dieser Arbeit auf Semantikfragen nicht detailliertein. Dazu sei auf [1] verwiesen.

Bedingte Gleichungen, die inAspec gelten, heißen in-duktive Theoreme. Allerdings herrscht hier einige Begriffs-verwirrung, da manchmal auch Gleichungen, die in allen ter-merzeugten Modellen vonspec gelten, als induktive Theo-reme bezeichnet werden. Die Begriffsbildungen werden nochverwirrender, wenn man erlaubt, daß Operatoren durchEnur partiell spezifiziert werden. Fur eine Klarung dieser Be-griffsbildungen sei auf [18] verwiesen.

Ist E ein unbedingtes Gleichungssystem, so ist die Me-thode ”Konsistenztest” ein Beweisverfahren fur induktiveTheoreme, siehe [13],[12], [3]. Dieses Verfahren ist wider-legungsvollstandig in dem Sinn, daß es nach endlicher Zeitmeldet, wenn eine Gleichung kein induktives Theorem ist.Unser Ansatz ist eine Fortentwicklung dieser Methode. Sieberuht auf der Idee, daß man systematisch mogliche Inkonsi-stenzen zwischenE und der Behauptung solange bezuglicheiner Noetherschen Ordnung verkleinert, bis feststeht, daß(a) keine Inkonsistenz existiert oder daß (b) eine Inkonsi-stenz offensichtlich ist. Im Fall (a) ist die Behauptung bewie-sen. Das Kriterium, das Fall (a) nachweist, ist zwar haufiganwendbar, aber leider im allgemeinen nicht entscheidbar.

Fur positiv bedingte Gleichungssysteme sind Verfahrensehr erfolgreich, die mitUberdeckungsmengen arbeiten, z.B.cover sets [19] oder test sets [8]. Hier versucht man, alleGrundterme durch eine endliche Menge von Termen zuuberdecken und so einen Induktionsbeweis nach einer ge-eigneten Reduktionsordnung zu fuhren (Noethersche Induk-tion). Schließlich gibt es noch das Verfahren der explizitenInduktion [7], [15]. Hier extrahiert man ausE ein geeigne-tes Induktionsschema und fuhrt so Induktionsbeweise. In [6]wird allgemeines Theorembeweisen mit eingebauten Theo-

55

rien betrachtet. Es wird ein Resolutionsverfahren beschrie-ben, das widerspruchsvollstandig ist.

Wir beschreiben hier die entwickelte Theorie in verein-fachter Form und verzichten aus Platzgrunden auf alle Be-weise. Eine ausfuhrlichere Version, die auch auf Fragen derSemantik genauer eingeht, ist in Vorbereitung [1]. Die vor-liegende Arbeit beschreibt einen Teil der Resultate, die imSFB-314, ProjektDeduktion in gleichungsdefinierten Struk-turen entstanden sind. Fur speziellere und tieferliegendereResultate sei auf die Arbeiten von K. Becker, B. Gramlichund C.-P. Wirth verwiesen, wie sie im Literaturverzeichnisangegeben sind.

2 Hierarchische Spezifikationen

Wir gehen im folgenden davon aus, daß die eingebaute Al-gebra das initiale Modell einer Basisspezifikationspec0 istund daßspec eine hierarchische Spezifikationuber spec0ist. (Siehe [2] fur den allgemeinen Fall.) Wir legen in die-sem Paragraphen die syntaktischen Einheiten einer solchenhierarchischen Spezifikation fest.

Definition 2.1. Eine Signatursig = (S, F, τ ) besteht aus ei-ner MengeS von Sorten, einer MengeF von Operatorenund einer Funktionτ : F → S+, die jedemf ∈ F seineStelligkeit zuordnet. Giltτ (f ) = s1, . . . , sn, s, so schreibenwir auchf : s1, . . . , sn → s.

Sei sig = (S, F, τ ) gegeben, und sei (Vs)s∈S ein sor-tiertes System von Variablen mitVs ∩ Vs′ = ∅ furs 6= s′. Dann ist V =

⋃s∈S Vs, und T (F, V ) bezeich-

net die Menge der wohlgeformten (sortierten) Terme. SeiTs(F, V ) die Menge der Terme der Sortes ∈ S. Wir ver-langenTs(F0) 6= ∅ fur alle s ∈ S. Es istV ar(t) die Mengeder Variablen in t. EinGleichheitsatomhat die Formt1 = t2mit t1, t2 ∈ Ts(F, V ) fur ein s ∈ S, und ein Definiert-heitsatomhat die Formdef (t) mit t ∈ T (F, V ). (Hierbeiist def ein Metasymbol.) EinLiteral L ist ein Atom oderein negiertes Atom und eineKlausel ist eine Disjunktionvon Literalen. Wir schreiben KlauselnG auch in der FormG ≡ A1 ∧ A2 ∧ ... ∧ Ak =⇒ B1 ∨ B2 ∨ ... ∨ Bl

oder Γ =⇒ ∆ mit Γ = {A1, . . . , Ak}, ∆ = {B1, . . . , Bl}und k, l ≥ 0. Dabei sind dieAi und Bj Atome. Haufigzeichnen wir unter denBj ein Gleichheitsatom aus, etwaB1 ≡ s = t und schreiben dannG auch in der FormA1, . . . , Ak,¬B2, . . . ,¬Bl =⇒ s = t oderΓ =⇒ s = t,∆′mit ∆′ = {B2, . . . , Bl}. Eine bedingte Gleichunghat dieForm Γ ;∆ =⇒ s = t sie ist logischaquivalent zur KlauselΓ =⇒ s = t,∆. Die Elemente ausΓ heißen positive, dieaus∆ heißen negative Bedingungen. Ist∆ = ∅, so schrei-ben wir auchΓ =⇒ s = t und sprechen von einer positivbedingten Gleichung. Ist auchΓ = ∅, so heißt =⇒ s = t eineunbedingte Gleichung.

Wir kommen nun zu hierarchischen Signaturen und Spe-zifikationen. Es bezeichne + die disjunkte Vereinigung vonMengen.

Definition 2.2. Eine hierarchische Signaturuber der Basis-signatursig0 = (S, F0, τ0) hat die Formsig = (S, F0+F1, τ0+τ1) mit τ1 : F1 → S+. SeiF = F0 ∪ F1. Die f ∈ F0 heißenKonstruktoren, die f ∈ F1 heißendefinierte Operatoren.

Man beachte, daßsig die gleiche Sortenmenge hat wiedie Basissignatursig0. Dies ist konzeptionell keine wesent-liche Einschrankung, erlaubt aber spater eine einheitlicheFormulierung der Ergebnisse und vermeidet Fallunterschei-dungen.

Definition 2.3. Eine Basisspezifikationspec0 = (sig0, E0)besteht aus einer Signatursig0 und einer MengeE0 von po-sitiv bedingtensig0-Gleichungen. Einehierarchische Spezifi-kation uber der Basisspezifikationspec0 = (sig0, E0) hat dieFormspec = (sig, E). Dabei istsig = (S, F0+F1, τ0+τ1) einehierarchische Signaturubersig0 = (S, F0, τ0), E = E0 +E1undE1 eine Menge von bedingten GleichungenΓ ;∆ =⇒ s =t, wobei (i) s und t nicht beideF1-frei sind (d.h.,s oder tenthalt einen definierten Operator) und (ii)∆ kein Definiert-heitsatom enthalt.

Wir nennen eine hierarchische Spezifikation auch eineKlauselspezifikation. Eine Klauselspezifikation besteht alsoaus einer positiv bedingten Basisspezifikation und einer po-sitiv/negativ bedingten Erweiterungsspezifikation.

Die Semantik einer hierarchischen Spezifikationspec =(sig, E) uber der Basisspezifikationspec0 = (sig0, E0) kannnun durch zwei Algebren festgelegt werden: DaE0 eineMenge positiv bedingtersig0-Gleichungen ist, ist dieE0-Gleichheit =E0 auf densig0-GrundtermenT (F0) wie ublichdefiniert. Es ist dannA = T (F0) / =E0 die initiale Alge-bra zuspec0. Wir definieren dann die E-Gleichheit =E aufallen Grundtermen, also aufT (F ), und setzenAspec =T (F ) / =E . Dabei sind drei Punkte zu beachten: (1)specspezifiziert dief ∈ F1 i.a. nur partiell. (2) Inspec tretenpositiv und negativ bedingte Gleichungen auf. Wir wertendie positiven Bedingungen durch reines Gleichheitsschließenund negative Bedingungen durch eine ”konstruktive Absi-cherung inA” aus. Insbesondere giltdef (t) in Aspec ge-nau dann, wennt =E t0 fur einen Termt0 in T (F0). (3)Es ist zu klaren, welche Werte die Variablen in GleichungausE−E0 annehmen durfen. Wir legen fest, daß die Varia-blen nur Werte aus der BasisalgebraA annehmen durfen.Technisch heißt dies, daß fur jede Substitutionσ und jedeVariablex der Termσ(x) in T (F0, V ) liegt, also ein Basi-sterm ist.

Wir gehen hier nicht naher auf Semantikfragen ein,erwahnen aber, daß man Modelle vonspec alssig-Algebrenuber Sortenhierarchien definieren kann. Dann istAspec in-itial in der Klasse aller Modelle vonspec. Siehe [1], [2],[17].

Wegen der konstruktiven Auswertung von negativen Be-dingungen verlangen wir, daß die Terme in diesen Bedingun-gen durch def-Atome abgesichert sind. (D.h., fur jede be-dingte GleichungΓ ;∆ =⇒ s = t und jedes Gleichheitsatomu = v in ∆ gilt def (u), def (v) ∈ Γ .) Solche Spezifikationennennen wirdef-moderiert. Diese syntaktische Einschrankungfur bedingte Gleichungen mit negierten Bedingungen erlaubtes, die Semantik auch durch eine auf Termersetzung basie-rende operationale Semantik beim Vorliegen von Konfluenzzu erfassen. Viele der Standardkriterien fur Terminierungund Konfluenz von Termersetzungssystemen lassen sich aufdiese allgemeinere Form von bedingten Regelnubertragen[17]. Damit kann man auch den Nachweis fuhren, daßspeceine konsistente Erweiterung vonspec0 ist.

56

3 Ein Beweiser fur induktive Theoreme

Wir geben in diesem Abschnitt ein Inferenzsystem an, mitdem man induktive Theoreme zu hierarchischen Spezifika-tionen beweisen kann. Dieses System kann auch fur Wider-legungen verwendet werden, d.h., fur Eingabeformeln, diekein induktives Theorem sind, kann es die Ausgabe NEINliefern. Der Nachweis der Gultigkeit einer Klausel in einerspeziellen Algebra erfordert Induktionsbeweise. Hierbei un-terscheiden sich verschiedene Ansatze in der Art, wie starkman beim Induktionsschritt von InduktionsvoraussetzungenGebrauch machen kann. Die hier vorgestellte Beweisme-thode ist sehr flexibel und geht weituber strukturelle Induk-tion hinaus. Sie ermoglicht Induktionsbeweise mit beliebigenReduktionsordnungen.

Wir wollen zunachst die wesentlichen Eigenschaften desBeweisers etwas abstrakter formulieren und spater geeignetinstantiieren. (Siehe auch [5] fur diesen Ansatz.) Wir deutendie spatere Instantiierung mit dem Zusatz ”in unserem Fall”an und versuchen so, die richtige Intuition zu wecken.

Wir arbeiten mitsyntaktischen EinheitenG,H, . . . , inunserem Fall sind das Klauseln der FormΦ =⇒ Ψ . Es be-zeichnenG und H Mengen solcher syntaktischen Einhei-ten. Jede syntaktische EinheitG beschreibt vielesemantischeEinheiten(G, τ ), in unserem Fall durchlauft τ die Mengealler Grundsubstitutionen. IstG ∈ G , so heißt (G, τ ) aucheine G -Instanz. Weiter seiP ein Pradikat, die ”zu bewei-sende Eigenschaft” auf semantischen Einheiten. In unseremFall gilt P (G, τ ) genau dann, wennτ (G) in Aspec gilt.Wir schreibenP (G), wennP (G, τ ) fur alle τ gilt, und wirschreibenP (G ), wennP (G) fur alleG ∈ G gilt. Um Be-hauptungen zu widerlegen, benotigen wir ein FehlerpradikatFail auf den syntaktischen Einheiten. In unserem Fall giltFail(G), wennG ”offensichtlich” kein induktives Theoremist. Wir prazisieren dies spater. Prinzipiell wird verlangt, daßFail mit P kompatibelist: Gilt Fail(G), so gilt nichtP (G).Wir sagen, es giltFail(G ), falls Fail(G) fur ein G∈ Ggilt. Ist alsoFail mit P kompatibel und giltFail(G ), sogilt P (G ) nicht.

Das zu entwickelnde InferenzsystemI arbeitet aufZustandender Form (H ; G ), dabei istG die Menge derzu beweisenden Formeln (Klauseln) undH die Menge derInduktionshypothesen. Es bestehtI aus Inferenzregeln derForm (wir schreibenG , G stattG ∪ {G} und G ,G ′ stattG ∪G ′):

I:(H ; G , G)(H , G; G ,G ′)

Die InferenzregelI ersetzt also das ZielG durch neue ZieleG ′ und schiebtG in die Menge der Induktionshypothe-sen. Wir schreiben (H ; G ) `I (H ′; G ′), wenn man(H ′; G ′) aus (H ; G ) durch Anwendung einer Inferenz-regel ausI erhalten kann.

Es soll nunI so konstruiert werden, daß (I), (II) und(III) gilt:

(I) Gibt es eineI -Ableitung (∅,G ) `I . . . `I (H ′; ∅),so gilt P (G ).

(II) Gibt es eineI -Ableitung (∅,G ) `I . . . `I (H ′; G ′)und gilt Fail(G ′), so gilt P (G ) nicht.

(III) Gilt P (G ) nicht, so gibt es eineI -Ableitung (∅; G )`I . . . `I (H ′,G ′), so daßFail(G ′) gilt.

Wegen (I) kann man also mitI Beweise fuhren, und we-gen (II) kann man mitI Behauptungen widerlegen. Wegen(III) kann man immer eine Widerlegung finden, wennP (G )nicht gilt. Diese Eigenschaft ist zwar wunschenswert, abernicht immer einfach effektiv zu sichern. Gilt (I), so heißtIinduktiv korrekt, gilt (II), so heißt I widerspruchskorrektund gilt (III), so heißtI widerlegungsvollstandig.

Will man fur ein konkretes Inferenzsystem diese Eigen-schaften sicherstellen, so benotigt man Quasiordnungen aufden semantischen Einheiten, deren strikter Anteil wohlfun-diert ist. Eine solche Ordnung�i heißt eineInduktionsord-nung. Eine semantische Einheit (G, τ ) fur G ∈ G heißtein G -Gegenbeispiel(fur P ), falls P (G, τ ) nicht gilt. EinZustand (H ; G ) heißt korrekt falls gilt: Zu jedem G -Gegenbeispiel (G, τ ) gibt es einH -Gegenbeispiel (H, τ ′)mit (G, τ ) �i (H, τ ′). Insbesondere sind Zustande derForm (H ; ∅) stets korrekt und ein Zustand der Form (∅; G )ist genau dann korrekt, wennP (G ) gilt. Ist (H ; G ) nichtkorrekt, so gibt es eininduktives Gegenbeispiel(G, τ ) zu(H ; G ), d.h., es gilt nichtP (G, τ ), aber es giltP (H,π)fur alle H -Instanzen mit (G, τ ) �i (H,π).

Man beachte, daß die Korrektheit eines Zustandes vonder gewahlten Induktionsordnung und von der EigenschaftP abhangt. Ein Zustand (H ; G ) ist korrekt, fallsP (G )gilt, oder jedes�i minimale Gegenbeispiel eineH -Instanzist. Will man nun fur ein InferenzsystemI die Eigen-schaft (I) sicherstellen, so genugt es, die Inferenzregeln so zuwahlen, daß keine inkorrekten Zustande in korrekte Zustandeuberfuhrt werden konnen, d.h., man verliert keine indukti-ven Gegenbeispiele. Eigenschaft (II) ist gegeben, falls fur je-den Inferenzschritt (H ; G ) ` (H ′; G ′) ausP (G ) stetsP (G ′) folgt, d.h., es werden keine Gegenbeispiele neu ein-gefuhrt. (Dies gilt fur alle P -kompatiblenFail-Pradikate.)Eigenschaft (III) hangt wesentlich von der Existenz einesgeeignetenFail-Pradikats in Verbindung mit einer fairenI -Ableitung ab. (In der hier betrachteten Allgemeinheitwird ein Fail-Pradikat benotigt, welches neben syntakti-schen Eigenschaften auch die Anwendbarkeit von Inferenz-regeln berucksichtigt. Ein solches Pradikat kann dann unent-scheidbar sein). In der Regel wird man sich mit entscheid-baren Naherungen einesFail- Pradikats begnugen.

Zur Konkretisierung des InferenzsystemsI gibt es meh-rere Moglichkeiten zur Wahl der Inferenzregeln, sie nutzendie Induktionshypothesen unterschiedlich stark aus.

Seispec = (sig,R) eine konsistente hierarchische Spezi-fikation uber der Basisspezifikationspec0 = (sig0, R0). Wirsetzen voraus, daßR bezuglich einer festen Simplifikati-onsordnung� verkleinernd und daßR konfluent ist (siehe[10]).

Wir kl aren zunachst, welche Eingaben der konkrete Be-weiser zulaßt, und wann eine Eingabe ein induktives Theo-rem heißt. (Man beachte, daß fur eine Substitutionτ stetsτ (x) ∈ T (F0, V ) gilt, also τ (x) ein sig0-Term ist.)

Definition 3.1. Eine KlauselA1∧. . .∧An =⇒ B1∨. . .∨Bm

heißt eininduktives Theoremzu spec, wenn sie inAspec

gultig ist, genauer, wenn fur jede Grundsubstitutionτ einτ (Ai) in Aspec nicht gilt oder einτ (Bj) in Aspec gilt.

Wir instantiieren also die Grundkonzepte des abstraktenBeweisers so: Die syntaktischen EinheitenG sind Klauseln

57

der FormΦ =⇒ Ψ , wobei die Atome inΦ und Ψ entwederGleichheitsatome der Formt1 = t2 oder Definiertheitsatomeder Formdef (t) uber sig sind. Eine semantische Einheit(G, τ ) besteht aus einer Klausel und einer Grundsubstitution.Das Pradikat P trifft auf (G, τ ) zu, wennτ (G) in Aspec

gilt. Es gilt alsoP (G) genau dann, wennG ein induktivesTheorem ist. Das FehlerpradikatFail wird spater festgelegt.

Als nachstes ist die Induktionsordnung�i auf Klauselnfestzulegen. Sie basiert auf der gegebenen Reduktionsord-nung�. Dazu definieren wir zunachst die Komplexitat c(A)eines Atoms durchc(u = v) = {u, v} und c(def (u)) = {u}.Dann ist die Komplexitat c(G) mit G ≡ Φ =⇒ Ψ definiertals die Multimengec(G) = {c(A) | A ∈ Φ ∪ Ψ}. Schließlichist die Induktionsordnung�i gegeben durchG �i G′, fallsc(G) �dm c(G′′) oderc(G) = c(G′). Dabei ist�dm die dop-pelte Multimengenerweiterung von�. Siehe [11] zur Defini-tion der Multimengenerweiterung einer gegebenen Ordnung.

Wir geben nun das InferenzsystemI an. Es hat als Pa-rameter (i) das RegelsystemR, (ii) die Reduktionsordnung� und (iii) eine MengeL von Lemmata. Dabei ist jedesG ∈ L eine Klausel, die ein induktives Theorem ist. Wirsetzen voraus, daßL alle Regeln inR und alle Klauselnder Form =⇒ t = t mit t ∈ T (F, V ) und =⇒ def(t) mitt ∈ T (F0, V ) undA =⇒ A, A ein Atom, enthalt.

Jede InferenzregelI in I hat die Form

I :(H ; G , G)(H , G; G ,G ′)

Wir sagen, daßI auf G angewendet wird und dabeiG ′ ∈I(H ; G , G) produziert. Dabei kannG ′ = ∅ sein. SindHund G aus dem Kontext bekannt, so schreiben wir einfachI(G) stattI(H ; G , G) fur die moglichen Mengen von Fol-gezielen.

Es gibt funf Inferenzregeln, die unten durch Regel 0 bisRegel 4 beschrieben sind: (0) Triviale Transformation, (1)Uberdeckung des Sukzedens, (2) Uberlappung in den Ante-zedens, (3) Simplifikation und (4) Subsumption. Wir gebenfur diese funf Regeln an, wie I auf ein aktuelles Ziel G wirkt.Wir erlautern die Inferenzregeln an dem festen Regelsystem

R0 : ρ1 ≡ =⇒ x− 0→ x

ρ2 ≡ =⇒ s(x)− s(y)→ x− y

Es sei� die rekursive Pfadordnung zur Prazedenz− � s, 0[10].

Regel 0 hat die Aufgabe, triviale Transformationen aufeinem ZielG durchzufuhren.

Regel 0:Triviale TransformationIst G ≡ Φ =⇒ A,Ψ (Φ,A =⇒ Ψ ) und hatA die Gestaltu = u oderdef (t) mit t ∈ Term(F0, V ), dann ist∅ ∈ I0(G)({Φ =⇒ Ψ} ∈ I0(G)). Ist G ≡ Φ,A =⇒ A,Ψ , dann ist∅ ∈ I0(G).

Zur Angabe der restlichen Regeln werden weitere Notatio-nen benotigt. Wir sagen, daß eine Grundsubstitutionτ irre-duzibel (inR) ist, falls τ (x) irreduzibel ist fur allex ∈ V .

Die Regel 1 hat zum Ziel, auf einem aktuellen G eineFallunterscheidung durchzufuhren und gleichzeitig jedes soentstehende Teilziel mit dem Regelsystem zu reduzieren (zuverkleinern). Dabei reicht es, nur solche Klauseln G zu be-trachten, die einen leeren AntezedensΦ haben.

Definition 3.2. Sei Ψ eine Menge von Atomen. EinUber-deckungselementzuΨ (undR) ist ein 4-Tupel(σ,A, p, ρ), sodaßσ eine Substitution,A ∈ Ψ, p ∈ O(A) undρ ≡ Γ ;∆ =⇒l = r Instanz einer Regel inR ist undσ(A/p) ≡ l gilt. DannheißtA′ ≡ σ(A)[r]p dasReduktvon(σ,A, p, ρ). Eine MengeCov(Ψ ) vonUberdeckungselementen heißt einevollstandigeUberdeckungvonΨ , falls fur jede irreduzible Grundsubsti-tution τ esτ ′ undσ gibt, so daßτ = τ ′ ◦σ gilt und entwederexistiert ein(σ,A, p, ρ) in Cov(Ψ ) mit ρ ≡ Γ ;∆ =⇒ l = rund→R erfullt τ ′(Γ ); τ ′(∆) (d.h.,τ ′(ρ) ist anwendbar) oderes existiert ein Atoms = t in Ψ und es istσ = mgu(s, t).

Gibt es eine vollstandigeUberdeckungCov(Ψ ) fur G ≡=⇒ Ψ , so gilt fur jede Grundsubstitutionτ : Es gibt ein Atoms = t in Ψ mit τ (s) ≡ τ (t) oderτ (G) ist mit R reduzierbar.Im ersten Fall istτ (G) ein induktives Theorem und mußdaher nicht weiter betrachtet werden, im zweiten Fall wirdin Regel 1 die reduzierte Form vonτ (G) eine G ′-Instanzund somit ein neues Ziel.

Regel 1:Uberdeckung des SukzedensSeiG ≡ =⇒ Ψ undCov(Ψ ) eine vollstandigeUberdeckungvon Ψ . Dann bestehtG ′ ∈ I1(G) aus allen Klauseln derForm Γ =⇒ σ(Ψ − {A}), A′, ∆, so daß(σ,A, p, ρ ≡Γ ;∆ =⇒ l = r) in Cov(Ψ ) undA′ das Redukt von(σ,A, p, ρ)ist.

Wir illustrieren Regel 1 mit dem RegelsystemR0 und demZiel G ≡=⇒ x = 0, x − x = 0. Es istCov(G) = {({x ←s(x)}, x− x = 0, p, ρ2)} eine vollstandigeUberdeckung vonG. Fur eine Grundsubstitutionτ gilt namlich τ (x) ≡ si(0).Ist i = 0, so lost τ das Teilzielx = 0. Ist i > 0, so istτ (x − x) ≡ s(x) − s(x) mit ρ2 reduzierbar. Es bestehtG ′nur aus =⇒ s(x) = 0, x− x = 0.

Die Regel 2 hat das Ziel, den AntezedensΦ von G ≡Φ =⇒ Ψ zu entfernen. Dies geschieht mit Narrowing-Techniken.

Definition 3.3. Sei A ein Atom. Ein Narrowing-Tripel(σ, p, ρ) zuA (undR) besteht aus einer Substitutionσ, ei-ner Stellep ∈ O(A) und einer Regelρ ≡ Γ ;∆ =⇒ l = r inR, so daßA/p keine Variable undσ = mgu(A/p, l) ist. DannheißtA′ ≡ σ(A[r]p) das ReduktvonA und (σ, p, ρ). EineMengeNar(A) von Narrowing-Tripeln heißtvollstandigeNarrowing-Uberdeckungvon A, falls fur jede irreduzible Grundsubstitutionτ gilt:Gilt τ (A) in Tspec, so gibt esτ ′ undσ, so daßτ = τ ′ ◦σ giltund es existiert ein(σ, p, ρ) ∈ Nar(A) oder es istA ≡ s = tundσ = mgu(s, t).

Man kann eine vollstandige Narrowing-UberdeckungNar(A) stets berechnen. Dazu bilde man alle Narrowing-Tripel zuA und nehme sie inNar(A) auf.

Regel 2:Uberlappung in den AntezedensSei G ≡ Φ,A =⇒ Ψ und seiNar(A) eine vollstandigeNarrowing-Uberdeckung zuA. Dann bestehtG ′ ∈ I2(G)aus allen Klauseln der Formσ(Φ), A′, σ(Γ ) =⇒ σ(Ψ ), σ(∆),so daß(σ, p, ρ) ∈ Nar(A), ρ ≡ Γ ;∆ =⇒ l = r und A′das Redukt vonA und (σ, p, ρ) ist. Ist A ≡ s = t undσ = mgu(s, t), so ist auchσ(Φ) =⇒ σ(Ψ ) in G ′.

58

Wir illustrieren Regel 2 mitR0 und dem ZielG ≡ x− y =0 =⇒ x = y. Es istA ≡ x − y = 0 undNar(A) = {({y ←0}, p, ρ1), ({x ← s(x), y ← s(y)}, p, ρ2)} eine vollstandigeNarrowinguberdeckung vonA, undG ′ ∈ I2(G) besteht ausden neuen Zielenx = 0 =⇒ x = 0 und x − y = 0 =⇒s(x) = s(y). Das erste neue Ziel ist eine Tautologie und kannsofort geloscht werden. Die folgende Regel 4 subsumiert daszweite neue Ziel mit der neuen HypotheseG und loscht es(siehe unten).

Die Inferenzregeln gemaß Regel 3 und 4 beschreiben dieSimplifikation und die (partielle) Subsumption eines ZielsG ∈ G mit einer InduktionshypotheseH ∈H oder einemLemmaH ∈ L . Dabei konnen fur die Anwendbarkeit derRegel neue Beweisverpflichtungen auftreten. Sie werden vorder Anwendung rekursiv mit dem gleichen Beweiser gelost.Um zu garantieren, daß dieser rekursive Aufruf des Bewei-sers wohl-fundiert ist und daß die Regeln Gegenbeispieleverkleinern, werden nur gerichtete bzw. aufgespaltene Klau-selnH zugelassen.

Definition 3.4.a) Eine KlauselΦ =⇒ u = v, Ψ heißt (bezuglich�) gerichtet,falls u � v undu �st w fur alle w inΦ =⇒ Ψ gilt.b) Eine KlauselΦ0, Φ1 =⇒ Ψ0, Ψ1 heißt (bezuglich�) aufge-spaltenfalls Φ0 =⇒ Ψ0 �i Φ1 =⇒ Ψ1 gilt.

Bisher haben wir nur Substitutionenσ verwendet, d.h.,es ist σ(x) ∈ T (F0, V ) ein Basisterm. Dies fuhrt zuSimplifikations- und Subsumptionsregeln, die zu schwachsind. Wir lassen daher jetzt zu, daßσ(x) ∈ Ts(F, V ) ist furalle x ∈ Vs. Dann heißtσ : Vs → Ts(F, V ) eine Quasi-Substitution. Um die fruher entwickelte Semantik nicht zuverletzen, fordern wir in den Regeln 3 und 4, daßdef (σ(x))im aktuellen Kontext gilt. Dann ist alsoσ ”im wesentlichen”eine Substitution. SeiV ar(G) die Menge der inG auftre-tenden Variablen.

Regel 3:SimplifikationSei G ≡ Φ,A =⇒ Ψ (bzw.G ≡ Φ =⇒ A,Ψ ). Sei wei-ter H ≡ Γ =⇒ u = v,∆ in H ∪L , sei σ eine Quasi-Substitution, so daßA ≡ A[σ(u)]p gilt und σ(H) gerich-tet ist. Sei weiterG = {Φ, σ(B) =⇒ Ψ | B ∈ ∆} ∪{Φ =⇒ σ(B), Ψ | B ∈ Γ} ∪ {Φ =⇒ def (σ(x)), Ψ | x ∈V ar(G), σ(x) 6∈ T (F0, V )} und sei(H ; G ) ein korrek-ter Zustand. Dann istG ′ = {Φ,A[σ(v)]p =⇒ Ψ} (bzw.G ′ = {Φ =⇒ A[σ(v)]p, Ψ}) in I3(G) = I3(H ; G , G).

Wir illustrieren Regel 3 mitR0 und dem ZielG ≡ x −y = 0 =⇒ s(x) − s(y) = 0. SeiH die Regelρ2, also =⇒s(x) − s(y) → x − y. Sie wird mit der Substitutionσ ={x ← s(x), y ← s(y)} angewandt. Das liefertG = ∅, alsosimplifiziert H das ZielG zur Tautologiex − y = 0 =⇒x− y = 0.

Man beachte, daßG �i G fur alle G ∈ G gilt.Man kann also den Beweiser rekursiv mit dem Startzustand(H ; G ) aufrufen, um nachzuweisen, daß (H ; G ) ein kor-rekter Zustand ist. Es ist (H ; G ) sicher dann ein korrekterZustand, wenn jedesG ∈ G entweder inH liegt oder eininduktives Theorem ist. Ist anderweitig bekannt, daßP (G )gilt, so kann man die Voraussetzung in Regel 3, daßσ(H) ge-richtet ist, abschwachen zur Voraussetzung, daßσ(u) � σ(v)gilt.

Regel 4:SubsumptionSeiG ≡ Φ0, Φ1 =⇒ Ψ0, Ψ1. SeiH ≡ Γ0, Γ1 =⇒ ∆0, ∆1 inH ∪L und seiσ eine Quasi-Substitution, so daßσ(H) auf-gespalten ist undσ(Γ0) ⊆ Φ0 und σ(∆0) ⊆ Ψ0 gilt. Weitersei G = {Φ1 =⇒ σ(B), Ψ1 | B ∈ Γ1} ∪ {Φ1, σ(B) =⇒ Ψ1 |B ∈ ∆1} ∪ {Φ1 =⇒ def (σ(x)), Ψ1 | x ∈ V ar(G), σ(x) 6∈T (F0, V )} und (H ; G ) ein korrekter Zustand. Dann istG ′ = ∅ in I4(G) = I4(H ; G , G).

Wir illustrieren Regel 4 mit dem ZielG ≡ x − y = 0 =⇒s(x) = s(y) und der HypotheseH ≡ x − y = 0 =⇒ x = y.Wir setzenΦ1 = Ψ0 = Γ1 = ∆0 = ∅. Dann istΦ0 =⇒ Ψ0 ≡x − y = 0 =⇒ und Φ1 =⇒ Ψ1 ≡=⇒ s(x) = s(y), alsogilt Γ0 =⇒ ∆0 �i Γ1 =⇒ ∆1 und H ist aufgespalten. Wirbenutzen die Substitutionσ = id, damit ergibt sichσ(Γ0) =Φ0 = {x − y = 0} und σ(∆0) = Ψ0 = ∅. Es bestehtG nurausx = y =⇒ s(x) = s(y). Offenbar ist (H ,G ) fur jedesH ein korrekter Zustand, also istG ′ = ∅ in I4(G).

Man beachte, daßG �i G fur alle G ∈ G gilt. Dieswird durch die Voraussetzung garantiert, daßσ(H) aufge-spalten ist. Man kann also die Anwendbarkeit von Regel 4wie bei Regel 3 verifizieren. Ist anderweitig bekannt, daßP (G ) gilt, so kann man die Voraussetzung fallen lassen,daßσ(H) aufgespalten ist.

Wir kommentieren noch die Bedingung in Regel 3 undRegel 4, daß (H ; G ) ein korrekter Zustand ist. Sie drucktaus, daß die KlauselH wirklich anwendbar ist, daß alsodie Bedingungen (die Klauseln inG ) zumindest dann gel-ten, wenn man die Gultigkeit derH0 ∈H voraussetzt. Furdie Verifikation der Anwendbarkeit vonH zum Simplifi-zieren/Subsumieren vonG durfen also die aktuellen Induk-tionsvoraussetzungen inH benutzt werden. Es gibt auchandere Varianten der Simplifikation und Subsumption. Sietesten nicht direkt die Anwendbarkeit vonH, sondern neh-men die Bedingungen der Anwendbarkeit als Beweisziele inG ′ mit auf. Dabei ensteht aber i.a. ein Inferenzsystem, dasnicht widerspruchskorrekt ist.

Wir kommen nun zur Angabe einesFail-Pradikats. Esmuß mit P – also der induktiven Gultigkeit – kompatibelsein und ausdrucken, daß eine KlauselG ”offensichtlich”kein induktives Theorem ist.

Wir geben zunachst ein Fehlerpradikat Fail1 an, dasleicht anwendbar ist. Wir sagen, daßG und H variablen-disjunkt sind, wennV ar(G) ∩ V ar(H) = ∅ gilt.

Definition 3.5. SeiG ≡ A1 ∧ . . .∧ An =⇒ B1 ∨ . . .∨Bm.Es giltFail1(G) genau dann, wenn es Lemmata=⇒ A′i undB′j =⇒ gibt, so daß gilt: (i) Die Lemmata undG sind paar-weise variablendisjunkt und (ii) Es gibt eine Substitutionσmit σ(Ai) ≡ σ(A′i) undσ(Bj) ≡ σ(B′j) fur alle i = 1, . . . , nund j = 1, . . . ,m.

Die Bedingung (ii) ist eine Unifikations-Bedingung. Istz.B. G ≡=⇒ def (g(0, x)) undH ≡ def (g(y, h(z))) =⇒ einLemma, so gibt es einσ mit σ(def (g(0, x))) ≡ σ(g(y, h(z))),also giltFail1(G). Man zeigt leicht, daßFail1 mit P kom-patibel ist.

Das InferenzsystemI bestehe aus den RegelI0 bis I4und dem FehlerpradikatFail1.

59

Satz 3.1. I ist induktiv korrekt, widerspruchskorrekt und esverkleinert induktive Gegenbeispiele.

Es bleibt noch die Widerspruchsvollstandigkeit zu disku-tieren. DaI induktive Gegenbeispiele verkleinert, kann eskeine unendlichenI -Ableitungen geben, die die induktivenGegenbeispiele echt verkleinern. Laßt man bei der Abarbei-tung der Ziele keine aus (Fairness), so benotigt man, um dieVollstandigkeit zu erreichen, ein starkeresFail-Pradikat. Einsolches ist z.B.Fail(G) genau dann, wennFail1(G) oderaufG ist keine der RegelnI0, I1, I2 anwendbar. Fur prakti-sche Zwecke ist diesesFail-Pradikat nicht immer sehr hilf-reich, da unklar ist, wie man testen soll, obFail(G) gilt. Soist z.B. RegelI1 auf G ≡ =⇒ Ψ nicht anwendbar, wenn eskeine vollstandigeUberdeckungCov(Ψ ) gibt. Dies ist abernur in Spezialfallen entscheidbar.

4 Ein Beispiel

Die Inferenzregeln vonI sind zwar sehr machtig, aber auchsehr abstrakt formuliert. Auch die Rolle der Lemmata bedarfnoch einer Erklarung. In diesem Paragraphen soll an einemeinfachen Beispiel verdeutlicht werden, wie die Inferenz-regeln und die Lemmata angewendet werden, wie man alsomit I Beweise fuhren kann. Es ist von Vorteil, einen großenVorrat an Lemmata zu haben. Sie konnen nicht nur fur dieInferenzregelnSubsumptionund Simplifikationbenutzt wer-den, sondern auch fur den Nachweis, daßFail1(G) gilt.

Die Anwendung eines LemmasH ≡ Γ =⇒ ∆ fur dieSubsumption und die Simplifikation erzeugt (fur die An-wendbarkeit) i.a. neue Beweisaufgaben. Das ist nicht derFall, wenn das ”ganze Lemma” benutzt wird, wenn etwa furdie Subsumption mitH ≡ Γ0, Γ1 =⇒ ∆0, ∆1 und σ dieMengenΓ1 und∆1 leer sind undσ eine Substitution (keineQuasi-Substitution) ist (vgl. Regeln 3,4).

Wir verdeutlichen die Arbeitsweise unseres Beweisers anfolgendem Beispiel.

Beispiel: Seienspec0 = (sig0, R0), spec = (sig,R) undR =R0 +R1 gegeben durch

R0: leerR1: =⇒ x + 0 = x =⇒ x− 0 = x

=⇒ x + s(y) = s(x + y) =⇒ s(x)− s(y) = x− y

Es ist alsospec0 eine Basisspezifikation mit freien Konstruk-toren 0 unds. Es reprasentiert der Termsi(0) die naturlicheZahl i, und R1 spezifiziert die Operatoren + (Addition)und− (Subtraktion). Sei� die rekursive Pfadordnung zurPrazedenz +> s. Dann istR verkleinernd bezuglich�, d.h.,l � r gilt f ur jede Regel =⇒ l = r. Weiter istR auch kon-fluent.

1. Aufgabe: Zeige, daßG ≡ def (x− y) =⇒ (x− y) + y = x

ein induktives Theorem ist. Regel 2 liefertI2(G) 3 {G1, G2}

G1 ≡ def (x) =⇒ (x− 0) + 0 =xG2 ≡ def (x− y) =⇒ (s(x)− s(y)) + s(y) = s(x)

Also wird der Startzustand (∅; {G}) uberfuhrt in({G}; {G1, G2}). Es werdenG1 undG2 mit R simplifiziertzu

G′1 ≡ def (x) =⇒ x = x

G′2 ≡ def (x− y) =⇒ s((x− y) + y) = s(x)

undG′2 wird mit G simplifiziert zuG′′2 ≡ def (x− y) =⇒ s(x) = s(x)

Nun werdenG′1 und G′′2 mit der RegelI0 geloscht. Diesalles liefert den Zustand ({G,G1, G2, G

′1, G

′2, G

′′2}; ∅), also

ist G ein induktives Theorem.Wir betrachten die Simplifikation vonG2 etwas genauer.

Zunachst wirdG2 mit der Regel =⇒ s(x) − s(y) = x − yund der Substitutionσ = id simplifiziert zudef (x− y) =⇒(x − y) + s(y) = s(x). Diese Klausel wird anschließend mitder Regel =⇒ x+s(y) = s(x+y) und der Quasi-Substitutionσ = {x← x−y} simplifiziert zuG′2 ≡ def (x−y) =⇒ s((x−y) + y) = s(x). Dies ist erlaubt, weilG = {def (x − y) =⇒def (σ(x)), def (x−y) =⇒ def (σ(y))} aus zwei Klauseln be-steht, die induktive Theoreme sind. Schließlich wirdG′2 mitG undσ = id zuG′′2 ≡ def (x− y) =⇒ s(x) = s(x) simplifi-ziert. Dies ist moglich, weilG = {def (x−y) =⇒ def (x−y),def (x− y) =⇒ def (x), def (x− y) =⇒ def (y)} aus drei in-duktiven Theoremen besteht.

2. Aufgabe: Teste, obG ≡ =⇒ (x− y) + y = x

ein induktives Theorem ist. Offenbar ist Regel 2 nicht aufG anwendbar. Es ist auch Regel 1 nicht aufG anwend-bar, da z.B. mit der Grundsubstitutionτ = {x ← 0, y ←s(0)} τ (G) ≡=⇒ (0− s(0)) + s(0) = s(0) nicht mitR redu-zierbar ist. (Beachte, daßσ = {x← x−y} keine Substitutionist !) Also gilt Fail(G), und Satz 3.1 (mitFail stattFail1)liefert, daßG kein induktives Theorem ist.

References

1. Avenhaus, J., Madlener, K.: Theorem proving in hierarchic clausalspecifications. In preparation

2. Avenhaus, J., Becker, K.: Operational specifications with built-ins.Proc. 11th Annual Symposium on Theoretical Aspects of ComputerScience, LNCS 77, pp. 263–274. Berlin: Springer 1994

3. Bachmair, L.: Proof by consistency in equational theories. Proc. 3rdIEEE Symposium on Logic in Computer Science, pp. 228–233, 1988

4. Bachmair, L., Ganzinger, H.: Rewrite-based equational theorem pro-ving with selection and simplification. J. Logic Comput. 4 (3), 1–31(1994)

5. Becker, K.: Rewrite operationalization of clausal specifications withpredefined structures. Diss. Universitat Kaiserslautern, 1994

6. Bachmair, L., Ganzinger, H., Waldmann, U.: Refutational theorem pro-ving for hierarchic first order theories. Appl. Algebra in Eng., Commun.Comput. 5, 193–212, 1994

7. Boyer, R.S., Moore, J.S.: A Computational Logic. New York: Acade-mic Press 1979

8. Bouhoula, A., Rusinowitch, M.: Automatic case analysis in proof byinduction. Proc. of the 13th Int. Conf. on Artifical Intelligence, pp.88–94, Chambery, Savoie, France, April 1993

9. Broy, M., Wirsing, M., Pair, C.: A systematic study of models ofabstract data types. Theor. Comp. Science 33, 139–174, 1984

10. Dershowitz, N., Jouannaud, J.P.: Rewrite systems. In: van Leeuwen,J. (ed.). Handbook of Theoretical Computer Science, Vol. B, pp. 243–320. Amsterdam: Elsevier 1990

11. Dershowitz, N., Manna, Z.: Proving termination with multiset or-derings. Comm. ACM 22, 465–476 (1979)

12. Huet, G., Hullot, J.M.: Proofs by induction in equational theories withconstructors. J. Comput. Syst. Sci. 25, 239–266 (1982)

13. Kapur, D., Musser, D.R.: Proof by consistency. Art. Intell. 31, 125–157(1987)

60

14. Padawitz, P.: Deduction and declarative programming, Cambridge Uni-versity Press, 1992

15. Walther, C.: Mathematical induction. In: Gabbay, D.M., Hogger, J.C.,Robinson, C.A. (eds.). Handbook of Logic in Artificial Intelligence andLogic Programming, Vol. 2, pp. 127–235. Oxford: Oxford UniversityPress 1994

16. Wirth, C.-P., Becker, K.: Abstract notions and inference systems forproofs by mathematical induction. Proc. 4th Int. Workshop on Condi-tional Term Rewriting Systems, 1994, to appear

17. Wirth, C.-P., Gramlich, B.: A constructor-based approach to posi-tive/negative conditional equational specifications. J. Symb. Comput.17, 51–90 (1994)

18. Wirth, C.-P., Gramlich, B.: On notions of inductive validity for firstorder equational clauses. In: Bundy, A. (ed.) Proc. 12th Conf. on Au-tomated Deduction. Lect. Notes Aret. Intell. Vol. 814, pp. 162–176,1994

19. Zhang, H., Kapur, D., Krishnamoorthy, M.S.: A mechanizable induc-tion principle for equational specifications. In: Lusk, E., Overbeek, R.(eds.) Proc. of the 9th Int. Conf. on Automated Deduction. LNCS, Vol.310, pp. 162–181. Berlin: Springer 1988

Jurgen Avenhausstudierte von 1961bis 1967 Mathematik in Braunschweigund Karlsruhe. Er promovierte 1970 inKarlsruhe und habilitierte sich 1979 amFachbereich Informatik in Kaiserslau-tern. Dort ist er zur Zeit Professor furTheoretische Informatik. Seine Interes-sen liegen auf dem Gebiet der automa-tischen Deduktion mit Rewrite Techni-ken. Hierzu gehoren allgemeines Theo-rembeweisen (auch verteilt auf mehrereRechner), induktives Beweisen und hig-her order rewriting.

Klaus Madlenerstudierte von 1964 bis1968 Mathematik und Elektrotechnikin Bogota (Universidad de los An-des) and Mainz. Er promovierte 1970in Mainz und habilitierte sich 1978am Fachbereich Mathematik in Kai-serslautern. Seit 1979 ist er Professorfur Theoretische Informatik im Fach-bereich Informatik in Kaiserslautern.Seine Interessen liegen auf dem Ge-biet der Effizienten Anwendung vonReduktionsmethoden fur das Rech-nen und Schließen in algebraischenStrukturen. Hierzu gehoren Anwendun-gen in Gruppen (Wortersetzungs sy-steme) und Ringen (Grobner Basen)sowie induktives Beweisen.