Das Verfahren, Formeln oder Terme in eine kanonische Repräsentationsform zu überführen, die bis auf logische Äquivalenz eindeutig ist, zur Vergleichs-, Indexierungs- und Gleichheitsprüfung.

Prinzip

Definiere eine deterministische Normalisierungsfunktion und die gewählte Äquivalenzrelation; wende geordnete Umschreibungen, Umbenennung gebundener Variablen, Beseitigung syntaktischer Mehrdeutigkeiten und Standardoperandensortierung an, um für jede Äquivalenzklasse einen eindeutigen Repräsentanten zu erzeugen.

Demonstration

Konvertiere propositionale Formeln in eine kanonische KNF durch Distribution, Entfernen von Tautologien, lexikographisches Sortieren von Literalen und Klauseln sowie konsistentes Umbenennen von Variablen, so dass logisch äquivalente Formeln dieselbe Zeichenkettenrepräsentation für das Indexieren erhalten.

Fehlanwendung

Annehmen, Canonicalisierung sei kostenfrei oder immer möglich; eine heuristische ‚Normalisierung‘ anwenden, die nicht deterministisch ist oder von willkürlichen Symbolnamen abhängt und damit keine Eindeutigkeit für äquivalente Formeln gewährleistet.

Konsequenz

Kanonische Formen ermöglichen effiziente syntaktische Gleichheitsprüfungen für semantische Äquivalenz, unterstützen Caching, Indexierung und Duplikatelimination in automatischen Schlusssystemen.

Umkehrung

Die Verwendung mehrerer gleichermaßen gültiger Normalformen oder das Belassen von Formeln in ungebundenen vereinfachten Formen führt zu nicht-deterministischen Repräsentationen, die direkte Äquivalenzprüfungen erschweren.

Abgrenzung

Hängt von der Logik und der gewählten Äquivalenz ab (semantische Äquivalenz, strukturelle Kongruenz, Alpha-Äquivalenz); einige Logiken erlauben keine berechenbare vollständige Canonicalisierung oder machen sie prohibitv teuer.

Semantische Spannung

Canonicalisierung steht in Spannung zu Vereinfachung und Minimierung: Sie priorisiert Eindeutigkeit und Reproduzierbarkeit der Repräsentation, möglicherweise zulasten minimaler syntaktischer Größe oder Lesbarkeit.

Synthese

Canonicalisierung ist die deterministische Abbildung äquivalenter Formeln auf einen einzigen gewählten Repräsentanten durch geordnete Umschreibungen und Standardkonventionen, sodass Äquivalenzfragen auf syntaktische Gleichheit reduziert werden.