Logik: Rechnen mit Existenz- und Allquantoren.

05.07.2011, 00:15

CalebR

Logik: Rechnen mit Existenz- und Allquantoren.

Meine Frage:
Ich soll sagen ob die Formel:
$\begin{eqnarray*} \forall x: \exists x:\exists y:\forall y: x=y \end{eqnarray*}$
wahr ist, und das Ergebnis begründen.

Meine Ideen:
Ich habe zwei Strategien wobei ich bei der einen nicht so sicher bin:

1. Ich negiere die Formel zweimal, was wieder zwei mal gemacht wird und sorge dafür dass ich gleiche Ausdrücke doppelt stehen habe. Ich ersetze also nach folgendem Schema
$\begin{eqnarray*} \forall x: \forall x: F \equiv \forall x: F \end{eqnarray*}$

Damit komme ich bei der o.g. Formel zu dem Ergebnis
$\begin{eqnarray*} \forall x: \forall y: x=y \end{eqnarray*}$
Dann sage ich, dass die Formel nur unter einelementigen Trägermengen wahr ist, sonst aber absurd.

MfG

2. Ich sorge dafür, dass ich nur einen Ausdruckstyp habe und gehe davon aus, dass das oben nicht funktioniert.
Dann erhalte ich nach dem Umformen:
$\begin{eqnarray*} \forall x: \neg\forall x: \forall y: \neg\forall y: x=y \end{eqnarray*}$

Und sage jetzt, dass diese Aussage absurd ist, damit also nie wahr.

3. Ich verfahre wie in (2.), versuche mich aber weiter kirre zu machen indem ich sage, dass (1.) nicht funktioniert weil die Variablen verschieden voneinander sind. Dann wäre aber
$\begin{eqnarray*} \forall x: \neg\forall x: F \end{eqnarray*}$ nicht absurd.

Ich kann mich leider für keine der Varianten entscheiden, da ich keine Möglichkeit der Überprüfung wüsste und im 3. Fall auch nicht wüsste wie ich weiter verfahren müsste.

05.07.2011, 02:12

pseudo-nym

Auf diesen Beitrag antworten »

RE: Logik: Rechnen mit Existenz- und Allquantoren.
Ich halte die Fragestellung für etwas seltsam. Der Begriff "wahr" ist für Formeln keine gute Wahl, denn es gibt Formeln (unter anderem die gegebene) deren Wahrheitsgehalt interpretationsabhängig ist. Der Begriff der Tautologie, also der einer Aussage die wahr ist egal unter welcher Interpretation man sie betrachtet scheint mir passender.

Desweiteren wundert mich auch deine Verwendung des Begriffs "absurd" ein wenig. Benutzt du ihn synonym zu "falsch"?

Nun zu deinen Strategien:
1)Das kann schon stimmen und ich teile deine Schlussfolgerung am Ende, ohne die einzelnen Schritte ist das allerdings schwer zu sagen, ob dein Weg korrekt ist.

2.Damit hast du aber nichts gezeigt, sondern lediglich eine Antwort erfunden. Sich weiter "kirre machen" wäre dringend notwendig.

3.Tatsächlich ist die Negation von $\begin{eqnarray*} \forall x \neg \forall x : F \end{eqnarray*}$ keine Tautologie, das heißt es gibt F für die $\begin{eqnarray*} \forall x \neg \forall x : F \end{eqnarray*}$ unter einer geeigneten Interpretation wahr ist.

05.07.2011, 09:35

CalebR

Auf diesen Beitrag antworten »

Es geht in dieser Aufgabe um das arbeiten und verstehen der Prädikatenlogik. „Wahr“ würde ich in diesem Fall als synonym zu Tautologie interpretieren. Es ist bei der Aufgabe also alles Zulässig was zur Lösung findet und die Regeln und Definitionen kreativ (aber korrekt(!)) anwendet. Thema bisher ist aber noch keine Lösungsmethode sondern die Semantik der Prädikatenlogik.

„Absurd“ reden wir von etwas das „nicht Tautologie“, also bei jeder Belegung falsch ist. Während „Tautologie“ bei uns bedeutet, dass eine Formel unter jeder Belegung wahr ist. Beides ist also mehr als nur falsch oder wahr.

Zu meiner erste Lösung hier einmal der Rechenweg:
$\begin{eqnarray*} \forall x:\exists x:\exists y:\forall y: x=y \end{eqnarray*}$
$\begin{eqnarray*} \equiv \neg\neg\forall x:\exists x:\exists y:\forall y: x=y \end{eqnarray*}$
$\begin{eqnarray*} \equiv \neg\exists x:\neg\exists x:\exists y:\forall y: x=y \end{eqnarray*}$
$\begin{eqnarray*} \equiv \neg\exists x:\exists y:\forall y: x=y \end{eqnarray*}$
$\begin{eqnarray*} \equiv \forall x:\neg\exists y:\forall y: x=y \end{eqnarray*}$
$\begin{eqnarray*} \equiv \neg\neg\forall x:\neg\exists y:\forall y: x=y \end{eqnarray*}$
$\begin{eqnarray*} \equiv \neg\exists x:\neg\forall y:\neg\forall y: x=y \end{eqnarray*}$
$\begin{eqnarray*} \equiv \neg\exists x:\neg\forall y:\neg\forall y: x=y \end{eqnarray*}$
$\begin{eqnarray*} \equiv \neg\exists x:\neg\forall y: x=y \end{eqnarray*}$
$\begin{eqnarray*} \equiv \forall x:\neg\neg\forall y: x=y \end{eqnarray*}$
$\begin{eqnarray*} \equiv \forall x:\forall y: x=y \end{eqnarray*}$

Das kann natürlich nur stimmen, wenn die Zusammenfassung nach dem Schema $\begin{eqnarray*} \forall x:\forall x: F \equiv \forall x: F \end{eqnarray*}$ stimmt und zulässig ist und dabei die gebundenen Variablen (das erste und das zweite x) nicht voneinander unterschiedlich sind. Dazu also meine Frage: Ist diese Form der Zusammenfassung überhaupt zulässig?

Zu 3. hast du wahrscheinlich mit mehr gearbeitet als mir derzeit zur Verfügung steht. Ich kann noch keine Vorhersagen über Tautologien usw. machen. Ich stecke noch voll in der Semantik.

Das bedeutet dann also, dass ich bei 2./3. keine wirklichen Ergebnisse erziehlt habe oder bin ich irgendwo einfach falsch rangegangen?

MfG (und danke für die Hilfe Wink

)

05.07.2011, 13:41

Huggy

Auf diesen Beitrag antworten »

Die Aufgabe finde ich irritierend und deswegen interessant. Irritierend ist sie für mich wegen der doppelten Quantifizierungen der Variablen x und y. Trotz heftigen Nachdenkens ist mir keine Regel der Prädikatenlogik eingefallen, die solche doppelte Quantifzierungen verbietet. Und wenn sie verboten wären, hättet ihr wohl kaum diese Aufgabe bekommen.

Deinen Ansatz, durch doppelte Negation des Ausdrucks gleiche aufeinanderfolgende Quantoren zu erzeugen, kann ich nicht nachvollziehen. Da bleiben meiner Meinung nach immer ungleiche Quantoren:

$\begin{eqnarray*} F = \forall x : \exists x: A(x) \end{eqnarray*}$

Einmal negiert ergibt sich:

$\begin{eqnarray*} \neg F = \exists x: \neg (\exists x: A(x)) =\exists x: \forall x: \neg A(x) \end{eqnarray*}$

Und wenn man das noch mal negiert, erhält man den ursprünglichen Ausdruck zurück.

Es bleibt also die Frage, wie doppelte Quantifizierungen zu handhaben sind? Kam da nichts in eurer Vorlesung?

Wenn man die Formeln auf einen endlichen Individuenbereich anwendet, können die Quantoren durch Konjunktionen und Disjunktionen ersetzt werden. Man kommt dann zu dem Schluss, dass man die inneren Quantoren einer doppelten Quantifizierung einfach weglassen kann. Allerdings bin ich mit der formalen Logik nicht genügend vertraut, um sagen zu können, dass das allgemein gilt. Jedenfalls müsste eine allgemeine Regel mit der Regel für endliche Individuenbereiche konsistent sein.

Wenn man das generell machen darf, reduziert sich die Formel der Aufgabe zu:

$\begin{eqnarray*} \forall x: \exists y : x = y \end{eqnarray*}$

Und das ist eine allgemeingültige Formel, eine Tautologie, also wahr.

05.07.2011, 19:08

pseudo-nym

Auf diesen Beitrag antworten »

@CalebR:
Also ich weiß nicht welche Methoden ihr zur Auswertung von Ausdrücken besprochen habt, aber ich würde Ausrechnen empfehlen. Dann kommt nämlich ziemlich schnell heraus, dass für jede Interpretation I gilt:
$\begin{eqnarray*} (\forall x : \exists x A)^I = (\exists x A)^I \end{eqnarray*}$
$\begin{eqnarray*} (\exists x : \forall x A)^I = (\forall x A)^I \end{eqnarray*}$

Nun zu deinen Ideen:
$\begin{eqnarray*} \forall x:\forall x: F \equiv \forall x: F \end{eqnarray*}$ ist richtig (muss aber erst gezeigt werden), allerdings ist das nicht die Umformung, die zu benutzt hast. Du verwendest
$\begin{eqnarray*} \neg \exists x: \neg \exists x: F \equiv \neg \exists x: F \end{eqnarray*}$ und das ist keine regelkonforme Umformung.

@Huggy

Zitat:

Original von Huggy
Die Aufgabe finde ich irritierend und deswegen interessant. Irritierend ist sie für mich wegen der doppelten Quantifizierungen der Variablen x und y. Trotz heftigen Nachdenkens ist mir keine Regel der Prädikatenlogik eingefallen, die solche doppelte Quantifzierungen verbietet. Und wenn sie verboten wären, hättet ihr wohl kaum diese Aufgabe bekommen.
[...]
Es bleibt also die Frage, wie doppelte Quantifizierungen zu handhaben sind?

In der Logik gibt es formale Regeln für quantifizierte Ausdrücke. Somit ist es nichts außergewöhnliches mehrmals über eine Variable zu quantifizieren.

Zitat:

Original von Huggy
Wenn man die Formeln auf einen endlichen Individuenbereich anwendet, können die Quantoren durch Konjunktionen und Disjunktionen ersetzt werden. Man kommt dann zu dem Schluss, dass man die inneren Quantoren einer doppelten Quantifizierung einfach weglassen kann. Allerdings bin ich mit der formalen Logik nicht genügend vertraut, um sagen zu können, dass das allgemein gilt. Jedenfalls müsste eine allgemeine Regel mit der Regel für endliche Individuenbereiche konsistent sein.

Das würde ich gerne sehen, denn wie ich schon sagte, erhalte ich durch Ausrechnen
$\begin{eqnarray*} \forall x : \exists x A \Leftrightarrow \exists x A \end{eqnarray*}$

05.07.2011, 21:39

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von pseudo-nym

Zitat:

Das würde ich gerne sehen, denn wie ich schon sagte, erhalte ich durch Ausrechnen
$\begin{eqnarray*} \forall x : \exists x A \Leftrightarrow \exists x A \end{eqnarray*}$

Wie schon gesagt, habe ich endliche Individuenbereiche betrachtet, z. b. einen Bereich mit 2 Individuen $\begin{eqnarray*} x_1 \end{eqnarray*}$ und $\begin{eqnarray*} x_2 \end{eqnarray*}$ . Es ist dann

$\begin{eqnarray*} (1) \quad \forall x : A(x) \equiv A(x_1) \land A(x_2) \end{eqnarray*}$

$\begin{eqnarray*} (2) \quad \exists x : A(x) \equiv A(x_1) \lor A(x_2) \end{eqnarray*}$

Wenn nun in (1) $\begin{eqnarray*} A(x) = \exists x : B(x) \end{eqnarray*}$ bekommt man

$\begin{eqnarray*} (1a) \quad \forall x : \exists x : B(x) \equiv (\exists x_1 : B(x_1)) \land (\exists x_2 : B(x_2)) \end{eqnarray*}$

Wenn $\begin{eqnarray*} x_1 \end{eqnarray*}$ und $\begin{eqnarray*} x_2 \end{eqnarray*}$ Individuenbezeichner sind, ist

$\begin{eqnarray*} \exists x_1 : B(x_1) \equiv B(x_1) \end{eqnarray*}$ und $\begin{eqnarray*} \exists x_2 : B(x_2) \equiv B(x_2) \end{eqnarray*}$

womit sich ergibt:

$\begin{eqnarray*} (1b) \quad \forall x : \exists x : B(x) \equiv B(x_1) \land B(x_2) \end{eqnarray*}$

Bei einem Bereich mit 2 Individuen ist

$\begin{eqnarray*} B(x_1) \land B(x_2) \equiv \forall x : B(x) \end{eqnarray*}$

womit man zu

$\begin{eqnarray*} (1c) \quad \forall x : \exists x : B(x) \equiv \forall x : B(x) \end{eqnarray*}$

gelangt. Die Umformungen aus (2) sind recht analog.

Wie schon gesagt, bin ich nnit formaler Logik nicht sehr vertraut. Also mag in obigem ein Fehler stecken. Aber welcher?

06.07.2011, 00:33

pseudo-nym

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
Wenn nun in (1) $\begin{eqnarray*} A(x) = \exists x : B(x) \end{eqnarray*}$ bekommt man

$\begin{eqnarray*} (1a) \quad \forall x : \exists x : B(x) \equiv (\exists x_1 : B(x_1)) \land (\exists x_2 : B(x_2)) \end{eqnarray*}$

$\begin{eqnarray*} A = \exists x : B(x) \end{eqnarray*}$ ist eine geschlossene Formel, also eine Formel, die von keiner Variablen abhängt. Das x wird nämlich vom Existenzquantor gebunden. Du darft quantifizierte Variablen nicht einfach so austauschen.

06.07.2011, 08:47

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von pseudo-nym
$\begin{eqnarray*} A = \exists x : B(x) \end{eqnarray*}$ ist eine geschlossene Formel, also eine Formel, die von keiner Variablen abhängt. Das x wird nämlich vom Existenzquantor gebunden. Du darft quantifizierte Variablen nicht einfach so austauschen.

Über Nacht war mir das auch aufgegangen.

Neue Frage »

Antworten »

Logik: Rechnen mit Existenz- und Allquantoren.

Verwandte Themen