Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Das Thema, das uns im Moment beschäftigt, sind Term-Ersetzungssysteme. Letzte Woche schon angefangen.

Ich erinnere nochmal an die Grundbegriffe, die da eingeführt wurden.

Wir reden zum einen über Terme, die man knapp über eine Grammatik definieren kann.

Das Prinzip der Definition von syntaktischen Kategorien über Grammatiken, das haben wir ja letztes Semester hinreichend kennengelernt.

Auch das kennen wir vom letzten Semester. Ein Term ist entweder eine Variable aus einer vorgegebenen Menge V von Variablen,

die manchmal variieren wird und die wir deswegen in die Notation ausdrücklich mit aufnehmen.

Oder ein Term ist die Anwendung eines endstelligen Funktionssymbols f auf schon konstruierte Terme t1 bis tn.

Wenn f in unserer Signatur groß Sigma ist, ist der Vorrat an Symbolen, die wir benutzen,

im aktuellen Fall sind es nur Funktionssymbole und sie kommen jeweils daher mit einer gegebenen Arität.

Das schreiben wir über diesen Schrägstrich, das heißt also in diesem Falle ist die Arität des Funktionssymbols f n.

Das reflektiert sich daran, dass wir hier tatsächlich genau n Argumente angeben in der Funktionsanwendung.

Neu war, dass wir auch über Kontexte reden. Kontexte sind Terme mit Löchern.

Auch die konnte man über eine Grammatik definieren, die den Begriff des Terms, den wir jetzt schon haben, weiter verwendet.

Und zwar ist ein Kontext entweder nur die Freistelle selbst oder ein Ausdruck der folgenden Form, eine Anwendung eines Funktionssymbols auf einen Haufen Terme,

ich schreibe mal die restlichen auch schon hin, an allen Argumentstellen von f bis auf eine sagen wir die Ithe und an dieser Ithenstelle steht wieder ein Kontext.

Das ist jetzt eine Definition, die sicherstellt, dass eben diese Freistelle wirklich nur an einem einzigen Punkt im Term vorkommt.

Dann gibt es eben eine offensichtliche Definition davon, was passiert, wenn man einen Term in einen Kontext einsetzt.

Er nimmt dann eben genau den Platz der Freistelle ein. Das wiederhole ich jetzt von der rekursiven Definition hier nicht.

Dann mache ich die Tür zu.

Und dann gab es eben die Definition davon, was ein Termersetzungssystem nun eigentlich ist. Und die Definition war sehr einfach.

Ein Termersetzungssystem ist schlicht und einfach eine Relation auf Termen. Die schreiben wir Pfeilindex 0.

Und dass es eine Relation auf Termen ist, das heißt formal, dass es eine Teilmenge ist des kathesischen Quadrats der Menge der Terme, die wir so schreiben.

Also nochmal, ich hatte ausdrücklich gesagt, die Menge der Terme hängt von Sigma ab und von Vorrat groß v an Variablen.

Und beides machen wir in der Notation für diese Termmenge explizit. Das heißt T Sigma von v ist die Menge aller Terme,

die ich gemäß dieser Grammatik aus dem Vorrat Sigma an Funktionssymbolen und dem Vorrat v an Variablen bilden kann.

Gut. Ja, das war jetzt glaube ich nur so als Definition letztes Mal der Schluss gewesen.

Ja, also das ist das, was ein Termersetzungssystem ist. Das war ein kurzes Beispiel da gewesen.

So, wir beschäftigen uns heute jetzt zunächst damit, was ein Termersetzungssystem denn so tut.

So, dazu beschäftigen wir uns jetzt mit allen möglichen Eigenschaften, die Relation auf Termen so haben können.

Das sammeln wir in einer großen Definition. Ich stapel das jetzt erstmal als Haufen Definitionen und dann kommen hinterher Beispiele.

So, alle diese Definitionen betreffen eine Relation auf Termen. Die schreibe ich jetzt mal nicht als Pfeil 0, sondern als gemeint allgemeiner.

Natürlich gibt es an Pfeilen 0 gar keine Restriktion, insofern kann von allgemeiner keine Rede sein.

Aber ich verwende jetzt absichtlich einen anderen Buchstaben, nämlich Groß R, um anzudeuten, dass wir diese Begriffe zum Teil auf andere Relationen als nur direkt auf die Grundrelation des Termersetzungssystems anwenden werden.

Wir reden jetzt also über irgendeine Definition R auf Termen und wir definieren eine Liste von Eigenschaften, die so ein Ding haben kann oder auch nicht.

Eine Eigenschaft, die so ein Ding haben kann, ist, es kann Kontext abgeschlossen sein. Ich definiere jetzt, was das heißt.

Abgeschlossen heißt eigentlich immer irgendwas der folgenden Form, so wie es jetzt kommt.

Sprich, wenn irgendwelche Dinge drin sind, dann sind andere Dinge auch drin. Also hier setze ich voraus, dass also irgendein Paar von Termen in Relation steht.

Also T steht in Relation R zu S und ich verlange dann, dass irgendwas anderes ebenfalls in Relation steht.

In diesem Falle hat dieses andere etwas mit Kontexten zu tun und es ist dann das Offensichtliche.

Nämlich, dass wenn ich irgendeinen Kontext C habe und T da einsetze, dass dann auch der so entstehende Term, also C von T, entsteht, indem ich in den Freilplatz von diesem Kontext C den Term T rein packe,

dass das dann auch in Relation R zu C von S steht. So, wie gesagt, Beispiele sehen wir gleich.

Erstmal steht man da und guckt sich diese Definition an. Gut, kann man definieren, klar.

Als Intuition für das Ganze denke man kurz an einfach Termumformungen, denn darum geht es ja, wie wir sie letztlich aus der Schule kennen.

Denken Sie daran, wie es war, als Sie in der 8. Klasse Algebra gelernt haben.

Da haben Sie also das erste Mal gelernt, dass man also diese ganzen Gesetze, Kommutativität, Assoziativität und so weiter, die man in der Grundschule lernt, dass man die auch auf Formeln mit Buchstaben anwenden kann.

Und wenn ich jetzt gelernt habe, dass zum Beispiel das Kommutativgesetz gilt, also x plus y gleich y plus x, dann habe ich sogar von alleine die Neigung, und man braucht es mir gar nicht zu sagen,

das auch dann zu machen, wenn ich diesen Term irgendwo tief in einer komplizierten Umgebung finde.

Wenn ich sowas habe wie sowas hier zum Beispiel, also x plus y und dann ganz viel komplizierter Kram außen rum,

dann müsste man mich geradezu systematisch davon abhalten, hier x und y zu vertauschen, wenn ich das Kommutativgesetz schon kenne.