Ich habe inzwischen mehrfach die Frage per Mail erhalten, ob denn zur Lösung von Aufgabe 9.1 wirklich strukturelle Induktion erforderlich sei, das ginge doch auch direkt mit den gegebenen Axiomen aus PAP.

Die Antwort darauf ist ein klares Jein.

In der Tat kann man x||y = y||x aufgrund der gegebenen Axiome aus PAP direkt äquivalent umformen.  Allerdings benötigt man dabei die Annahme, dass auch x|y = y|x gilt.  Und letzteres muss auch bewiesen werden.  Das lässt sich nach meinem Kenntnisstand nicht ohne strukturelle Induktion bewerkstelligen.  Die Aufgabenstellung verlangt daher, beides zu beweisen.

Zu der Aufgabe:

Gilt eigentlich nach CM9 auch sowas wie (a+b)|(c+d) = a|(c+d) + b|(c+d) oder kann für z nur ein atomarer Prozess eingesetzt sein? Ich fühl mich mit diesen ganzen Ersetzungsgeschichten noch immer nicht so ganz wohl…

Nachtrag: Vergesst die Frage, das Beispiel 4.20 aus S. 179 ist erst mal aufschlussreich genug für mich. :)

Habe einen Fehler auf der Übersicht der Axiome gefunden(S.200):

Anstatt LM2 x LL y = v* x muss es LM2 x LL y = v*y
heißen! (siehe Seite 177)

Hab gerade eine Schwierigkeiten mit der strukturellen Induktion für Paare, also die Behauptung, die bewiesen werden muss, gilt ja für ein Paar von Prozesstermen x,y.

Der Induktionsanfang über die atomaren Aktionen ist klar.
Aber wie sieht dann meine Annahme aus ? Soll die so aussehen: Ich nehme an, die Behauptung, gilt für den Term x=(u|v) und y=(w|z), und zu zeigen ist nun, dass die Behauptung auch für x,y gilt?
Aber dann hätte ich ja eine Masse an Kombinationen, weil ich kann ja auch x=(uLLv) und y=(w|z) und soweiter wählen.
Kann mir einer weiterhelfen?

Ich habe die möglichen Kombinationen von Termen zu sinnvollen Gruppen zusammengefasst.

Beispiel: Du hast x = (t1 + t2 + … tm) und y = (t1' + t2' + … tn'). Dann lässt x|y sich mit Hilfe der Axiome so umformen, dass nur noch Paare wie ta|tb' übrig bleiben, wobei ja dann ta und tb' eine andere Gestalt haben (müssen) als jeweils x und y. Für diese jeweiligen Gestalten muss es dann noch andere Fälle geben.

1. Beachte den Hinweis auf dem Aufgabenblatt. (Man muss sich für x und y nicht im Einzelnen mit allen denkbaren Termen auseinandersetzen.)

2. Die Fälle können sich aufeinander zurückführen lassen. Das kann man machen, weil die Terme jeweils nur eine endliche Länge haben und deshalb die Bestandteile, die man betrachtet, früher oder später nur noch atomare Symbole sind. Genau dies macht die strukturelle Induktion überhaupt erst möglich.