Seite parallel anzeigen





Du befindest dich hier: Aussagenlogik / Syntax

Der Formelbaum

(Aussagenlogik Kapitel 3.7)

Diese Seite nimmt Bezug auf

(Seite parallel anzeigen)
Liste überspringen
Zum Seitenanfang

Ein Graph ist eine Menge von Knoten und Kanten, durch die die Knoten verbunden sind.
Die Knoten bezeichnen Objekte - die Kanten die Relationen zwischen den Objekten.

Ein Formelbaum ist die Repräsentation einer Formel γ als Graph:
  • Der 1. Knoten des Formelbaumes repräsentiert γ und wird Wurzel genannt.
  • Repräsentiert ein Knoten eine Aussage der Form γ°δ (für einen beliebigen 2-stelligen Junktor °), so ist dieser mit ° markiert und ist mit 2 weiteren Knoten (die sog. "Nachfolger" oder auch "Kinder") verbunden: das linke Kind repräsentiert γ, und das rechte δ
  • Repräsentiert ein Knoten eine Aussage der Form °γ (für einen beliebigen 1-stelligen Junktor °), so ist dieser mit ° markiert und das Kind repräsentiert γ.
  • Repräsentiert ein Knoten eine Elementaraussage γ, ist dieser ein sog. Blatt des Baumes und mit γ markiert

Das linke bzw. rechte Kind eines Knotens, der eine Formel γ repräsentiert, repräsentiert also genau die linke bzw. rechte unmittelbare Teilformel von γ.
Die Wurzel des Formelbaumes, der γ repräsentiert, ist genau mit dem Hauptjunktor von γ markiert.

Im Folgenden stellen wir die Formel, die der Knoten repräsentiert ausgegraut und zwischen eckigen Klammern dar.

Beispiel - Eine Formel als Baum darstellen

Betrachten wir die Formel
  • γ = !p&q->r|s
und den Knoten der die Formel repräsentiert:
  • K1 ~ γ
 [~!p&q->r|s]
Der Hauptjunktor ist die Implikation.
Wir markieren den Knoten mit dem Symbold für den Junktor und fügen dem Knoten einen linken und einen rechten Nachfolger hinzu, der jeweils die linke bzw. rechte unmittelbare Teilformel repräsentiert:
  • K2 ~ !p&q
  • K3 ~ r|s
->[~!p&q->r|s]
[~!p&q] [~r|s]
Nun arbeiten wir mit dem linken Nachfolgerknoten - K2 weiter.
Die Konjunktion ist der Hauptjunktor.
Wir markieren den Knoten mit dem Symbold für den Junktor und fügen dem Knoten einen linken und einen rechten Nachfolger hinzu, der jeweils die linke bzw. rechte unmittelbare Teilformel repräsentiert:
  • K4 ~ !p
  • K5 ~ q
->[~!p&q->r|s]
&[~!p&q]
[~!p] q
[~r|s]
Wieder arbeiten wir wieder mit dem linken Nachfolgerknoten - K4 weiter.
Die Negation ist der Hauptjunktor.
Wir markieren also den Knoten mit dem Symbold für den Junktor und fügen einen Nachfolgerknoten für die unmittelbare Teilformel hinzu:
  • K6 ~ p
->[~!p&q->r|s]
&[~!p&q]
![~!p]

p		 q
[~r|s]
Sowohl K5, als auch K6 repräsentieren Atome.
Hier ist also nichts mehr zu tun.
Der nächste, unbearbeitete Knoten ist K3.
Die Disjunktion ist der Hauptjunktor.
Wir markieren also den Knoten und fügen einen Nachfolgerknoten für die linke bzw. rechte unmittelbare Teilformel hinzu:
  • K7 ~ r
  • K8 ~ s
->[~!p&q->r|s]
&[~!p&q]
![~!p]

p		 q
|[~r|s]
r s
Da sowohl K7, als auch K8 Atome repräsentieren, sind wir fertig.
->
&
!

p		 q
|
r s
Aus der Definition des Formelbaumes folgt, dass folgendes gilt:
Betrachten wir den Formelbaum, dessen Wurzel γ repräsentiert, so repräsentiert die Menge all seiner Knoten genau die Menge der Teilformeln von γ.

Beispiel - Formelbaum und Teilformeln

Betrachten wir den Formelbaum der Formel
  • γ = !p&q->r|s

->[~!p&q->r|s]
&[~!p&q]
![~!p]

p		 q
|[~r|s]
r s
und die Menge der Teilformeln von γ
  • p
  • !p
  • q
  • !p&q
  • r
  • s
  • r|s
  • !p&q->r|s
sehen wir, dass die Menge der Formeln, die durch einen Knoten des Baumes repräsentiert werden, genau die Menge der Teilformeln darstellt.