Prof. Dr. M. Kreuzer Abgabe: 15.12.2003, 12.15 Uhr Peter Ackermann

Logik für Informatiker

Übungsblatt 9

Aufgabe 20: Sei G eine Gruppe (Axiome siehe Vorlesung, wobei die Folgerung x∘i(x) = e dazugenommen werde). Weiter gebe es ẽ, a ∈ G mit ẽ ∘ a = a.

a) Formulieren Sie obige Situation als gleichungslogische Formeln.

b) Folgern Sie mit Hilfe von Termersetzungen, dass ẽ = e.

Aufgabe 21: Sei M Menge von Gleichungen. Zeigen Sie: Besitzt jeder Term eine eindeutige Normalform bzgl. →^{M}, so ist →^{M} konfluent.

Aufgabe 22: Sei M eine Menge mit assoziativer Verknüpfung ∘ : M × M → M, d. h. x ∘ (y ∘ z) = (x ∘ y) ∘ z.

a) Formulieren Sie die Situation als gleichungslogische Formel.

b) Zeigen Sie, dass das resultierende Termersetzungssystem noethersch und konfluent ist (Hinweis: Für die Konfluenz benutze man Aufgabe 21).