Quantoren + Kommutativgesetz der Logik

ez22
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 28. Mär 2011 14:52

Quantoren + Kommutativgesetz der Logik

Beitrag von ez22 » 14. Aug 2011 14:57

Hallo,

möchte mich vergewissern, dass die Reihenfolge der Quantoren bei einer Formel unterschiedlich sein kann.
Beispiel:

A - allquator
E - existenzquator
"-" - negation
Formel:
(Ew P(f(a),w) und Ax -P(x,y) und Ez-Qz) *P und Q - Relationen; f - eine einstellige Funktion

ich könnte sofort die Quantoren vor die Klammer ziehen oder ich könnte die Terme wegen des Kommutativgesetzes vertauschen (somit könnte ich die Stellung der Quantoren beeinflüssen) und dann die Quantoren vor die Klammer ziehen.
Zweite Variante wäre auch nicht falsch... oder?

Danke für die Antworten!

Benutzeravatar
Domac
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 160
Registriert: 4. Okt 2010 16:11

Re: Quantoren + Kommutativgesetz der Logik

Beitrag von Domac » 15. Aug 2011 09:49

\(\exists w P(f(a),w)\) und
\(\forall x \neg Pxy\) und
\(\exists b \neg Qb\) ... das soll jetzt eine Formel (aneinander gereiht) darstellen, nehme ich an, sonst würde deine Frage keinen Sinn machen. ^^

Durch vertauschen der Terme und durch "Quantoren vor die Klammer ziehen" veränderst du (nicht genau genommen) nichts. Die Quantoren binden deine Variablen, also belegen im allgemeinem Sinne deine Variablen.

Übersetze man dein "und" zwischen den Termen im logischem Sinne, dann erhält man \(\exists w P(f(a),w) \wedge \forall x \neg Pxy \wedge \exists b \neg Qb \equiv \exists w \forall x \exists b ( P(f(a),w) \wedge \neg Pxy \wedge \neg Qb ) \not \equiv \exists w \exists b \forall x ( P(f(a),w) \wedge \neg Pxy \wedge \neg Qb )\).

Dort jetzt die Quantoren untereinander zu vertauschen (vor der Klammer) würde ich nicht machen... bin mir nicht mehr sicher, aber doch der Meinung das man das u.a. wegen Prädikatenlogik und/oder Quantorenrang nicht darf. Jedenfalls ändert das Vertauschen der Quantoren vor der Klammer den Sinn deiner Formel und ist deswegen nicht zulässig.

Gruß domac

EDIT: Habe die 'z' mal durch 'b' ersetzt, weil man 'z' so schlecht erkennen konnte.

Nachtrag: Sorry, habe dich glaube ich falsch verstanden. Du meintest, dass du Formel1 \(\wedge\) Formel2 \(\wedge\) Formel 3 da stehen hast und die Formeln kommutieren lässt und dann die Quantoren vorziehst. Da bin ich mir nicht ganz so sicher... wäre mal ne Frage bei der Feriensprechstunden wert.
Extend my dropbox space (here).
Thanks!

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: Quantoren + Kommutativgesetz der Logik

Beitrag von dschneid » 18. Aug 2011 20:00

Ja, du kannst grundsätzlich die Quantoren ganz nach außen/vorne ziehen (also die Pränex-Normalform bilden), solange du darauf achtest, dass dabei keine freien Variablen gebunden werden; das kann aber nur passieren, wenn die Variable des Quantors gleich heißt wie eine freie Variable, was ja hier nicht der Fall ist. Du kannst auch vorher die drei Formeln beliebig vertauschen. Die Reihenfolge der Quantoren in der Pränex-Normalform hängt aber gar nicht von der Reihenfolge der Formeln ab, sondern wenn du so willst nur von der Reihenfolge, in der du die Quantoren nach vorne ziehst, und das kannst du ohnehin in einer beliebigen Reihenfolge machen. Deswegen können bei deiner Formel in der PNF die Quantoren in einer beliebigen Reihenfolge stehen. Im Allgemeinen kannst du aber nicht bei mehreren Quantoren, die schon direkt hintereinander stehen, die Reihenfolge vertauschen; wenn man ein Beispiel über die ganzen Zahlen mit der üblichen Addition und Konstante \(0\) nimmt, dann ist beispielsweise \(\forall x \exists y \; x + y = 0\) sicherlich nicht äquivalent zu \(\exists y \forall x \; x + y = 0\), denn die erste Formel ist wahr, aber die zweite ist falsch. Dass du in deiner speziellen Formel die Quantoren beliebig vertauschen könntest, liegt daran, dass in jeder Teilformel nur genau eine der quantifizierten Variablen vorkommt (vorausgesetzt, \(y\) ist bei dir eine Konstante), es also keine Abhängigkeiten gibt, die durch eine Umordnung verändert werden könnten.

Antworten

Zurück zu „Archiv“