Bereinigte Normalform

In der Prädikatenlogik heißt eine Formel bereinigt, wenn

  1. keine Variable sowohl frei als auch gebunden vorkommt,
  2. hinter jedem Quantor eine andere Variable steht.

Hinweis: Zu jeder Formel gibt es eine bereinigte äquivalente Formel. Jede Formel F lässt sich durch geeignete, gebundene Umbenennung in eine bereinigte Form überführen.

Beispiel:

F:=\forall x\exists y\left(P\left(x,y\right) \wedge Q\left(x,a\right)\right)
G:=\exists u\left(\forall v P\left(u,v\right)\vee Q\left(v,v\right)\right)

In der Formel F sind die Variablen x und y gebunden und a ist frei. F ist somit bereinigt. In der Formel G sind alle Vorkommen der Variable u gebunden, allerdings tritt v sowohl gebunden als auch frei auf. G ist daher nicht in bereinigter Form. Eine Überführung für G ist folgende Umbenennung (bei der Umbenennung müssen die gebundenen Variablen umbenannt werden):

G':=G\left[v/w\right]=\exists u\left(\forall w P\left(u,w\right)\vee Q\left(v,v\right)\right)

Siehe auch


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Normalform — Unter einer Normalform (auch kanonische Form) versteht man eine Darstellung mit bestimmten vorgegebenen Eigenschaften. Mitunter ist die Darstellung eindeutig. Formal ist eine Normalform ein letztes Element in einer Kette von einer wohlfundierten… …   Deutsch Wikipedia

  • Skolem-Normalform — Skolemform ist ein Begriff der Prädikatenlogik und bezeichnet eine prädikatenlogische Formel, die sich in einer Normalform nach Albert Thoralf Skolem befindet. Für Formeln in Skolemform existiert ein berechenbarer Test auf Erfüllbarkeit. Dies ist …   Deutsch Wikipedia

  • Pränex-Normalform — Die Pränexform ist eine mögliche Normalform, in der Aussagen der Prädikatenlogik dargestellt werden können. Sie wird unter anderem als Vorstufe zur Skolemform benötigt. Eine Aussage in der Prädikatenlogik erster Stufe befindet sich in Pränexform …   Deutsch Wikipedia

  • Verneinungstechnische Normalform — Die Pränexform ist eine mögliche Normalform, in der Aussagen der Prädikatenlogik dargestellt werden können. Sie wird unter anderem als Vorstufe zur Skolemform benötigt. Eine Aussage in der Prädikatenlogik erster Stufe befindet sich in Pränexform …   Deutsch Wikipedia

  • Kanonische Form — Unter einer Normalform versteht man eine Darstellung, die bestimmte vorgegebene Eigenschaften hat. Insbesondere bezeichnet Normalform in der Mathematik eine Darstellung eines Objektes, die bestimmte vorgegebene Eigenschaften hat und für alle… …   Deutsch Wikipedia

  • Skolemformel — Skolemform ist ein Begriff der Prädikatenlogik und bezeichnet eine prädikatenlogische Formel, die sich in einer Normalform nach Albert Thoralf Skolem befindet. Für Formeln in Skolemform existiert ein berechenbarer Test auf Erfüllbarkeit. Dies ist …   Deutsch Wikipedia

  • Skolemisierung — Skolemform ist ein Begriff der Prädikatenlogik und bezeichnet eine prädikatenlogische Formel, die sich in einer Normalform nach Albert Thoralf Skolem befindet. Für Formeln in Skolemform existiert ein berechenbarer Test auf Erfüllbarkeit. Dies ist …   Deutsch Wikipedia

  • Skolemnormalform — Skolemform ist ein Begriff der Prädikatenlogik und bezeichnet eine prädikatenlogische Formel, die sich in einer Normalform nach Albert Thoralf Skolem befindet. Für Formeln in Skolemform existiert ein berechenbarer Test auf Erfüllbarkeit. Dies ist …   Deutsch Wikipedia

  • Herbrand-Theorie — Der nach Jacques Herbrand, einem französischen Logiker, benannte Satz von Herbrand (engl. Herbrand s theorem, was gelegentlich nicht ganz korrekt als Herbrand Theorie übersetzt wird) in der Prädikatenlogik lautet: Sei F eine geschlossene Formel… …   Deutsch Wikipedia

  • Pränexnormalform — Die Pränexform ist eine mögliche Normalform, in der Aussagen der Prädikatenlogik dargestellt werden können. Sie wird unter anderem als Vorstufe zur Skolemform benötigt. Eine Aussage in der Prädikatenlogik erster Stufe befindet sich in Pränexform …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”