Schreibweise in der Prädikatenlogik

[freakC++]

Hallo

Ich habe folgende Aufgabe, dir mir eigentlich nicht so schwierigk erscheint, doch ich habe Schwierigkeiten im Aufschreiben:

Die Aussage Exy bedeutet, dass die beiden Knoten x y eines Graphens direkt mit einander verbunden sind. Px hingegen bedeutet, dass der Knoten aktiv ist.

Nun möchte ich mit Quantorenschreibweise folgendes aufschreiben:

Jeder aktive Knoten ist mit jedem anderen aktiven Knoten direkt verbunden.

In Umgangssprache bedeutet das: Für alle Knoten x, die aktiv sind, gilt: Für alle alle aktiven Knoten y muss Exy true sein.

Schreibe ich das jetzt so auf:

$\forall Px(\forall Py (Exy))$

Eine öffnene Klammer bedeutet für mich "für die gilt". Ich habe aber auch schon einen Doppelpunkt gesehen und kann man die Klammern sogar weglassen?

Danke für die Hilfe
LG, freakC++

[Bashar]

Ich würde auf keinen Fall $\forall Px$ schreiben. Da gehört eine Variable hin, eigentlich also $\forall x$. Standard ist auch die Abkürzung $\forall x\in M$, die nur über die Elemente der angegebenen Menge quantifiziert. Mit einem beliebigen Prädikat hab ich das noch nicht gesehen.

Ob man den Quantor von der Formel durch . oder : oder sonstwie abtrennt ist Geschmackssache, Hauptsache man erkennt, was gemeint ist. Ich würde die Formel übrigens so schreiben: $\forall x \forall y: Px \wedge Py \Rightarrow Exy$.

[knivil]

Jeder aktive Knoten ist mit jedem anderen aktiven Knoten direkt verbunden.

In Umgangssprache bedeutet das: Für alle Knoten x, die aktiv sind, gilt: Für alle alle aktiven Knoten y muss Exy true sein.

Also du hast eine Menge an Knoten V und eine Menge an Kanten E, die zusammen einen Graph G = (V,E) bilden: $\forall x, y \in V: active(x) \land active(y) => (x,y) \in E$. Man kann auch gleich die Menge aktiver Knoten spezifizieren, dann entfaellt das Praedikat active . Beispielsweise: Sei $A = \{ v \in V | active(v)\}$, dann gilt $\forall x,y \in A \land (x,y) \in E$. Das kann auf vielfaeltige Weise ausgedrueckt werden: $\forall x,y\in A \exists(w,z)\in V: x = w \land y = z$. Ob das jetzt die korrekte Syntax ist, weiss ich nicht genau, aber es kommt schon sehr nah dran.

Allgemein: Variablen werden quantisiert, nicht praedikate. D.h. wenn du eine Variable einfuehrst, dann muss sie durch einen Quantor $\forall$ oder $\exists$ eingefuehrt werden. Ist genauso wie bei reinen Funktionen in der Mathematik: $f(x) = x^2$. Das x auf der rechten Seite kann nur benutzt werden, weil es durch die linken Seite eingefuehrt wurde. Es gibt viele weitere Analogien, beispielsweise mittels Lamda-Ausdruecken oder einfachen Funktionsdeklarationen in Programmiersprachen.

[Michael E.]

Was du eventuell noch einbauen müsstest, ist die Bedingung x != y.

[freakC++]

Vielen Dank für eure Hilfe. Das hat mir schon sehr geholfen. Kann es sein, dass manchmal anstatt eines Doppelpunktes für "für die gilt" ein Klammerausdruck benutzt wird?

Vielen Dank
LG, freakC++

[Christoph]

freakC++ schrieb:

Vielen Dank für eure Hilfe. Das hat mir schon sehr geholfen. Kann es sein, dass manchmal anstatt eines Doppelpunktes für "für die gilt" ein Klammerausdruck benutzt wird?

Ja. Oft sieht man auch einen Punkt: $\forall x.\varphi(x)$

Letztendlich ist nur wichtig, dass man sich an eine gängige Schreibweise hält und nicht verschiedene mischt.