Die bislang hier verwendete lineare Darstellung von Formeln hat sich für Logiker zur Handhabung ihrer Untersuchungen bewährt. Beiläufig bemerkt, weicht sie weit ab von der ursprünglich von Frege verwendeten 2-dimensionalen Darstellung. Man kann nicht von vorneherein erwarten, daß für Computeranwendungen eine dieser beiden Darstellungen in gleicher Weise geeignet wäre, hatten doch weder Frege noch die Logiker nach ihm Gelegenheit, sich mit Computern zu beschäftigen. Für Implementierungen sind daher verschiedene Datenstrukturen zur Darstellung von Formeln verwendet worden, die wir hier nicht alle besprechen können.
Aus der Sicht der Wissensrepräsentation ist die Wahl einer geeigneten Repräsentation der Logik von großer Bedeutung, wie wir in den folgenden Abschnitten im Vergleich mit anderen Formalismen noch sehen werden. Viele Mißverständnisse über die Rolle der Logik beruhen tatsächlich auf der mangelnden Beachtung der Möglichkeit solcher verschiedenartigen Logikrepräsentationen.
Entscheidend für die Auswahl einer bestimmten Repräsentation können ontologische Gesichtspunkte im Hinblick auf die zu modellierende Wirklichkeit sein; vor allem sind es aber die vorherrschenden Operationen und die Kosten, die bei der gewählten Darstellung zur Durchführung der Operationen anfallen. Als wichtiges Beispiel illustrieren wir hier nur die sogenannte gaG-Darstellung als gerichteter azyklischer Graph (engl. dag), von dem wir in der Regel zusätzlich annehmen, daß er geordnet sei.
Die erste und letzte der drei obigen Beispielformeln sind in den Abbildungen 2.1 und 2.2 als ein solcher gaG dargestellt. Dabei ist jede Unterformel als Knoten des Graphen repräsentiert. Ein solcher Knoten hat eine geordnete Menge von Nachfolgern. Der erste darunter ist jeweils ein markierte Knoten, der die Art seines Vaterknotens bestimmt, die entweder durch eine logische Operation oder ein (möglicherweise negiertes) Prädikatszeichen charakterisiert ist. Die weiteren Nachfolger bilden die Operanden oder Argumente. Konstanten oder Variablen als Argumente sind wiederum markierte Knoten. Komplexere Terme als Argumente können ebenfalls als gaG oder auch einfach als markierter Knoten dargestellt werden, je nach den Erfordernissen.
Wir nennen einen gaG, der eine Formel darstellt, zeichenminimal, wenn jedes Prädikats-, Funktions-, Konstanten- oder Variablenzeichen höchstens einmal auftritt, und minimal, wenn es keinen gaG mit einer geringeren Knotenzahl für die gleiche Formel gibt. Minimale gaGs sind notwendig auch zeichenminimal. Umgekehrt gibt es zeichenminimale gaGs, die nicht minimal sind, da ja Teil-gaGs mehrfach auftreten können. Die gaGs in den Abbildungen 2.1 und 2.2 sind minimal.
Abbildung 2.1: Der gaG der Formel 
Abbildung 2.2: Der gaG der Formel 
Hinter der Eigenschaft der Zeichenminimalität verbirgt sich der
wesentliche Vorteil der gaG-Darstellung für Operationen, deren
Ausgangspunkt ein Name ist. Zum Beispiel ist eine Operation ``Finde alle
Aussagen über Objekt a'' bei dieser Darstellung besonders bevorzugt, weil
man nur von 
aus alle eingehenden Verweise rückverfolgen muß.
In dieser Weise sind um jedes Objekt alle zugehörigen Aussagen
assoziiert. In diesem Sinne ist diese Darstellung einer
Formel objektorientiert (vgl.
Abschnitt 2.8.2).
Man beachte, daß selbst mit der Wahl eines gaG als Darstellungsform Einzelheiten der Implementierung noch völlig offen sind. Beispielsweise würde man zur Ausführung der ebengenannten Operation tunlichst jede gerichtete Kante des Graphen auch mit einem Rückverweis zur raschen Auffindung des Vorgängers versehen. Auf die in Abschnitt 1.5.3 genannten Operationen gehen wir im Zusammenhang mit gaGs im einzelnen in den Abschnitten 2.4 und 2.6 ein.
Die gaGs sind nur eine Variante von möglichen syntaktischen Darstellungen logischer Formeln. Zunächst erwähnen wir weiter, daß zur Vereinfachung der Formelstruktur meist auf Normalformen zurückgegriffen wird. So enthält die Skolemnormalform nur eine Sorte von Quantoren, die alle am Beginn der Formel stehen. Für jede auftretende Variable ist dann im wesentlichen eindeutig bestimmt, durch welchen Quantor sie gebunden ist und wo dieser steht, so daß sich die Nennung der Quantoren überhaupt erübrigt. Der restliche Formelteil wird dann auch Matrix genannt.
Die logische Struktur der Matrix einer solchen Formel ist bestimmt durch aussagenlogische Operatoren, so daß wir uns im Moment mit rein aussagenlogischen Matrizen befassen, ohne dem allgemeinen Fall Abbruch zu tun. Insbesondere ist die Transformation solcher Matrizen in (aussagenlogische) Normalform wohlbekannt. Solche Normalform-Formeln werden dann auch oft als Matrizen in der Form von Mengen von Klauseln, dh. von Mengen von Literalen, repräsentiert. Dabei wird von einer positiven und negativen Repräsentation gesprochen, je nachdem ob die Formel selbst oder deren Negation (im Hinblick auf ``Beweis durch Widerspruch'') repräsentiert wird. So repräsentiert die Matrix
positiv die Formel
In der von der linearen Algebra gewohnten zweidimensionalen Matrixform stellt sich diese Formel wie folgt dar.
Sie ist die Negation der vorangegangenen Formel. In Matrixform lautet sie wie folgt.
Drehung gegen den Uhrzeigersinn sowie durch eine Vertauschung aller Vorzeichen
übergeht. Wegen dieses einfachen Zusammenhangs ist es leicht, von der
einen in die andere Darstellung überzuwechseln. Im folgenden bevorzugen
wir in der Regel die positive Darstellung.
Wegen des einfachen Zusammenhangs von Formeln und
Matrizen verwenden wir die beiden Begriffe synonym. Sehr oft
haben wir es mit
Hornformeln zu tun,
deren Klauseln in positiver Repräsentation höchstens ein negiertes Atom
enthalten. Die obige Matrix ist nicht Horn, da sie die Klausel 
mit zwei negierten Atomen enthält. Die Matrix
ist dagegen Horn. In Matrixform lautet sie
| R. | ||
| Q |  | R. |
| P | | Q. |
| | P? | |
Christoph Quix, Thomas List, René Soiron