Wie funktionieren Quantoren in der Prädikatenlogik?

Quantoren in Verbindung mit AND und OR

In den gebräuchlichsten Formen der Prädikatenlogik wirken ∀ und ∃ wie eine Art logische Konjunktion (AND) über alle Objekte bzw. logische Disjunktion (OR) über alle Objekte hinweg .

Verbindung zwischen ∀ und 'UND'

Betrachten Sie ein Argument, bei dem die einzigen 'Objekte' Schotten sind, und lassen Sie EPP( x ) = " x isst ihren Haferbrei einfach". Dann

∀x : EPP(x)

übersetzt (mit etwas weniger sozialer Anmut, als man es in der täglichen Sprache verwenden könnte) als

Für jeden [Schotten] x: x isst seinen Haferbrei einfach

was wir besser als darstellen könnten

Jeder Schotte isst seinen Haferbrei einfach .

Wenn wir davon ausgehen, dass jemand nur dann ein „Schotte“ ist, wenn er entweder in Schottland geboren wurde oder mindestens 90 % seines Lebens ein britischer Staatsbürger ist, dann gibt es nur endlich viele Schotten; wir könnten uns also auch vorstellen, eine Liste aller Schotten ("Angus", "Maeve", "Bruce", "Caroline", ...) zu erstellen, in diesem Fall ist es äquivalent zu

(Angus isst seinen Haferbrei pur) UND (Maeve isst ihren Haferbrei pur) UND ...

Das ist keine sehr bequeme Art, dasselbe auszudrücken, aber es ist immer noch äquivalent, solange wir alle Schotten auflisten und keine Person (oder Sache), die kein Schotte ist. Das Symbol ∀ ist auf diese Weise mächtiger – es erlaubt uns, einen Begriff auszudrücken

• ohne auf jedes Objekt verweisen zu müssen, das ein bestimmtes Kriterium erfüllt;
• ohne sich auf eine endgültige Liste aller Objekte im Universum des Diskurses festlegen zu müssen; und
• in anderen Kontexten, etwa wenn das Universum des Diskurses mathematische Objekte wie Zahlen sind, ohne auch nur zu kommentieren, ob es überhaupt eine endliche Liste von betrachteten Objekten gibt.

Besonders im letzten Fall erlaubt uns ∀, möglicherweise etwas auszudrücken, das über eine unendliche Menge oder deren Umfang wir noch nicht wissen, wahr ist. Aber trotzdem ist die Art und Weise, wie es sich verhält, sehr ähnlich wie ein logisches "UND" derselben Eigenschaft über alle Objekte im "Bereich des Diskurses".

Verbindung zwischen ∃ und 'ODER'

So wie ∀ so etwas wie ein „UND“ über alle betrachteten Objekte ausdrückt, drückt ∃ so etwas wie ein „ODER“ aus. Angenommen, der Bereich des Diskurses sind Menschen in einem bestimmten Raum (den ich als „diesen“ Raum bezeichnen werde; Sie können sich vorstellen, dass der Sprecher selbst im Raum ist) und M( x ) = „ x ist ein Mörder“. Dann

∃x : M(x)

übersetzt als

Es gibt eine [Person in diesem Raum] x: x ist ein Mörder

was wir besser als darstellen könnten

Jemand in diesem Raum ist ein Mörder .

Wir sagen stattdessen manchmal so etwas wie „Da ist ein Mörder in diesem Raum“, ohne damit definitiv behaupten zu wollen, dass es genau einen solchen gibt. Wenn wir wiederum annehmen, dass sich nur endlich viele Personen im Raum befinden ("Colonel Mustard", "Mrs. Peacock", "Professor Plum", ...), dann ist diese Aussage äquivalent zu

Entweder (Colonel Mustard ist ein Mörder) ODER (Mrs. Peacock ist ein Mörder) ODER ...

was wiederum unbequem, aber im Prinzip äquivalent zur Aussage mit ∃ ist, solange die Liste alle Personen im Raum und nur Personen im Raum enthält.

Eingeschränkte Quantifizierung

Es wäre schön, stattdessen über alle Schotten sprechen zu können, die Whiskey trinken , aber ohne das Universum des Diskurses zu verändern; oder tatsächlich die ganze Zeit über mehr als nur Schotten zu sprechen. Wir tun dies, indem wir Wege einführen, um die Quantifizierung einzuschränken.

Für den Existenzquantor ist dies einfach und offensichtlich. Angenommen, wir lassen das Universum des Diskurses alles auf der Erde sein, einschließlich Schotten, Chinesen, Honig, Melasse, Ameisen und so weiter. Wir können Aussagen über Schotten mit einem Prädikat S( x ) = " x ist eine schottische Person"; damit wir rendern können

Es gibt einen Schotten, der seinen Brei einfach isst

als "es gibt [etwas], das sowohl eine schottische Person ist als auch ihren Brei einfach isst"; oder

∃x: S(x) & EPP(x) .

Wir können etwas Ähnliches für die universelle Quantifizierung tun. Wenn wir zum Beispiel über Dinge sprechen wollen, die für alle Schotten gelten, können wir dies tun, indem wir eine Aussage machen, die für jedes Objekt x gilt, wenn x ein Schotte ist. Zum Beispiel,

Alle Schotten essen ihren Haferbrei einfach

kann beschrieben werden als "jedes [Ding], das ein Schotte ist, isst seinen Brei einfach" oder "für jedes [Ding] x: Wenn x ein Schotte ist, dann isst x seinen Brei einfach", was wir so wiedergeben können

∀x: S(x) ⇒ EPP(x) .

Dies ist in der Regel eine so nützliche Art, Dinge zu beschreiben, dass wir eine Notation dafür definieren, vielleicht in der folgenden Richtung:

∃x∈S: P   ≡   ∃x: [ S(x) & P ]

∀x∈S: P   ≡   ∀x: [ S(x) ⇒ P ]

wobei das, was ich links geschrieben habe, S im Grunde genommen als Beschreibung einer Menge behandelt – zum Beispiel die Menge aller Schotten. (Die Notationen variieren in verschiedenen Gemeinschaften.) Diese beiden „begrenzten“ Quantifizierungen verhalten sich genau so, als ob sie normale ∀- und ∃-Quantoren wären, außer dass sie sich über die Objekte x erstrecken, die S( x ) erfüllen .

Verbindung zwischen ∀ und ∃ unter Verwendung der Gesetze von de Morgan

Sie fragen sich vielleicht, warum wir bei der eingeschränkten Quantifizierung über S S(x) & Pfür die existentielle Quantifizierung über S und S(x) ⇒ Pfür die universelle Quantifizierung über S verwenden. Die Antwort verbirgt sich in der Verbindung zwischen den Quantoren und den UND- und ODER-Verknüpfungen: Es gibt eine Verbindung zwischen ∀ und ∃ durch die Gesetze von de Morgan in der klassischen Logik. Dies gilt unabhängig davon, ob wir eingeschränkte Quantifizierer oder uneingeschränkte Quantifizierer verwenden.

Betrachten Sie zum Beispiel den Fall, in dem die Schotten wieder das Universum des Diskurses sind. Angenommen, wir interpretieren ¬EPP(x) so, dass „ x ihrem Brei etwas hinzufügt, wenn sie ihn essen“. Dann sind die folgenden Aussagen äquivalent:

∀x: EPP(x) — Jeder Schotte isst sein Porridge einfach
¬∃x: [¬EPP(x)] — Kein Schotte fügt seinem Porridge etwas hinzu

(Warum ändern wir im obigen Satz das Wort „something“ in „anything“? Im Grunde genommen, weil das Gegenteil von „some“ im Englischen „not any“ ist.) Wir können dies anhand der Beschreibung in Form von UND und ODER sehen:

¬ ∃x: [¬EPP(x)] — Kein Schotte fügt seinem Brei etwas hinzu, wenn er ihn isst

kann unter Verwendung unserer Liste der Schotten interpretiert werden als

¬[ (Angus isst seinen Haferbrei mit etwas Beigefügtem) ODER (Maeve isst ihren Haferbrei mit etwas Beigefügtem) ODER ... ]

was äquivalent ist

¬(Angus isst seinen Haferbrei mit etwas Beigefügtem) UND ¬(Maeve isst ihren Haferbrei mit etwas Beigegebenem) UND ...

≡ (Angus isst seinen Haferbrei pur) UND (Maeve isst ihren Haferbrei pur) UND ...

das ist das gleiche ∀x: EPP(x)wie vorher. Umgekehrt, wenn es einen Schotten gibt, der seinen Brei mit etwas zugesetztem isst, haben wir es getan

∃x: [¬EPP(x)] — Einige Schotten fügen ihrem Brei etwas hinzu, wenn sie ihn essen

was mit unserer Liste von Schotten wird

(Angus isst seinen Haferbrei mit etwas Beigefügtem) ODER (Maeve isst ihren Haferbrei pur) ODER ...

≡ ¬(Angus isst seinen Haferbrei pur) ODER ¬(Maeve isst ihren Porridge pur) ODER ...

was uns unter Verwendung des Gesetzes von de Morgan gibt

¬[ (Angus isst seinen Haferbrei pur) UND (Maeve isst ihren Haferbrei pur) UND ... ]

das ist nur ¬∀x:EPP(x), oder

Nicht alle Schotten essen ihren Haferbrei pur .

Zusammenfassend haben wir für jede Eigenschaft P die folgenden Äquivalenzen:

Kein Objekt x ist P — Alle Objekte x sind nicht-P ; oder
¬∃x: P(x)   ≡   ∀x: ¬P(x) .

Irgendein Objekt x ist nicht-P — Nicht alle Objekte x sind P ; oder
∃x: ¬P(x)   ≡   ¬∀x: P(x) .

Dasselbe gilt, wenn wir eine eingeschränkte Quantifizierung verwenden. Für jede Eigenschaft S und jede Proposition P haben wir die folgenden Äquivalenzen:

¬∀x∈S: P
≡ ¬∀x: [ S(x) ⇒ P ]
≡ ¬∀x: [ ¬S(x) ∨ P ]
≡ ∃x: ¬[ ¬S(x) ∨ P ]
≡ ∃ x: [ S(x) & ¬P ]
≡   ∃x∈S: ¬P

und auch

¬∃x∈S: P
≡ ¬∃x: [ S(x) & P ]
≡ ∀x: ¬[ S(x) & P ]
≡ ∀x: [ ¬S(x) ∨ ¬P ]
≡ ∀x : [ S(x) ⇒ ¬P ]
≡   ∀x∈S: ¬P .

Der Grund für die unterschiedlichen Konnektoren bei der Definition der eingeschränkten Quantifizierungen liegt im Wesentlichen darin, dass dies erforderlich ist, damit sich die eingeschränkten Quantifizierungen so verhalten, als wären sie „normale“ Quantifizierungen auf dem kleineren Bereich.

∀ und ∃ im Klartext verstehen

Mit all dem können wir verstehen, wie Sätze in der Alltagssprache in Bezug auf die Quantoren beschrieben werden können. Am Ende läuft es darauf hinaus, die Dinge in Begriffen von „einigen“ oder „alle“ zu verstehen und sie dann formal zu übersetzen.

• „Kein X“ oder „Keines von X“ sind universelle Aussagen.
  
  Wieso den? Denn „none“ ist die Negation von „some“. Wenn wir also sagen "No X is P", sagen wir wirklich

  Es gibt kein X, das P ist

  oder gleichwertig

  ¬∃x∈X: P(x)
  ≡   ∀x∈X: ¬P(x)

  was eine universelle Aussage ist.

• „Einige X“-Aussagen sind existentielle Aussagen.
  
  Dies gilt unabhängig davon, ob wir über ein X sprechen , das eine Eigenschaft hat, oder über ein X , dem eine Eigenschaft fehlt . Wieso den? In diesem Fall ist es genau dort in der Sprache. Wenn wir sagen "einige X sind P", sagen wir

  Es gibt ein X, das P ist

  oder gleichwertig

  ∃x∈X: P(x) .

  Ähnlich sagen wir, wenn wir sagen "manche X sind nicht P".

  Es gibt ein X, das nicht-P ist

  oder gleichwertig

  ∃x∈X: ¬P(x) .

  Beides ist also offensichtlich existentiell.

• „Alle X“- und „Alle X“-Aussagen sind universelle Aussagen.
  
  Dies gilt wiederum unabhängig davon, ob wir über ein X mit einer Eigenschaft oder ein X ohne Eigenschaft sprechen, und wie im Fall von „einigen“ Aussagen ist es genau dort in der Sprache: Eine „alle“-Aussage wird kochen bis zu etwas von der Form

  ∀x∈X: P(x)   oder   ∀x∈X: ¬P(x) ,

  je nachdem, ob es darum geht, ob jedes Objekt P oder jedes Objekt Nicht-P ist.

• "Beliebige X"-Aussagen sind universelle Aussagen.
  
  Sie müssen sorgfältig darüber nachdenken, wie das Wort „beliebig“ verwendet wird. Wir fragen oft auf Englisch: are there any of [some object] ? Bei dieser Frage könnte es um existenzielle Quantifizierung gehen, aber es ist sicherlich keine existenzielle Aussage – noch eine Aussage irgendeiner Art.

  Wenn Sie an irgendeine Aussage (im Gegensatz zu der Frage) der Form "irgendein X" denken , sollte es ziemlich klar sein, dass es sich um etwas handelt, das für alle Objekte gilt. „Jeder, der in Schottland geboren ist, ist Schotte“ ist eine Aussage über alle Menschen, die in Schottland geboren sind; „Das Quadrat einer ganzen Zahl ist eine andere ganze Zahl“ ist eine Aussage über etwas, das für jede ganze Zahl gilt. Eine "Any X is P"-Aussage wird also übersetzt als

  ∀x∈X: P .

  Dies gilt auch für „es gibt keine X“-Aussagen, wie sie mit der Frage „gibt es welche?“ verbunden sind. Wenn wir sagen, dass es keine gibt, behaupten wir, dass es keine von X gibt ; Wie wir oben bemerkt haben, behaupten wir also

  ¬∃x∈X: P   ≡   ∀x∈X: ¬P .

Auf diese Weise können wir, indem wir das Gesagte sorgfältig prüfen, es in eine Aussage über Existenz, Nicht-Existenz oder etwas, das für alle Objekte gilt, umwandeln und es dann in etwas verwandeln, das offensichtlich existentiell (∃) oder offensichtlich ist universell (∀).

In der Ordnung der Quantoren

Es ist wichtig, sich daran zu erinnern, dass die Reihenfolge der Quantifizierer wichtig ist – Sie können sie oft nicht neu ordnen, ohne die Bedeutung zu ändern.

• Sie können die Reihenfolge zweier benachbarter Existenzquantoren ändern, im Wesentlichen weil OR kommutativ und assoziativ ist: Denken Sie daran, dass dies a v b v cdasselbe ist wie c v a v bund so weiter. Wenn also c = „Käse essen“ und A( x,t,a ) bedeutet, dass „ x ein Ort und t eine Zeit ist, wenn a angemessen ist“, dann

  ∃x ∃t: A(x,t,c)   und   ∃t ∃x: A(x,t,c)

  beide bedeuten im Wesentlichen , dass es eine Zeit und einen Ort gibt, um Käse zu essen ; der Unterschied besteht darin, ob die Disjunktion zuerst durch mögliche Orte iteriert und dann (für jeden Ort) mögliche Zeiten berücksichtigt, um herauszufinden, ob es an diesem Ort eine geeignete Zeit gibt; oder ob die Disjunktion stattdessen zuerst durch mögliche Zeiten iteriert und dann für jede Zeit mögliche Orte berücksichtigt, um herauszufinden, ob es zu dieser Zeit einen geeigneten Ort gibt.

• Ebenso können Sie die Reihenfolge benachbarter universeller Quantifizierer ändern . Wenn Sie ein extremer Käse-Enthusiast sind, möchten Sie vielleicht Folgendes behaupten (beide sind gleichwertig):

  ∀x ∀t: A(x,t,c)   und   ∀t ∀x: A(x,t,c)

  beides bedeutet, dass jede Zeit und jeder Ort eine gute Zeit und ein guter Ort ist, um Käse zu essen – egal zu welcher Zeit, jeder Ort ist gut; und egal wo du bist, jederzeit ist gut.

• JEDOCH – Sie können die Reihenfolge von universellen Quantoren und existenziellen Quantoren nicht ändern, ohne die Bedeutung zu ändern. Anstatt uns nur auf das Essen von Käse zu fixieren, sollten wir alle möglichen Arten von Aktivitäten in Betracht ziehen. Dann

  ∀ a ∃x ∃t: A(x,t,a)

  bedeutet, dass es für jede Aktivität eine Zeit und einen geeigneten Ort gibt; oft laut gesagt als "es gibt eine Zeit und einen Ort für alles". Dies ist jedoch nicht dasselbe wie

  ∃x ∃t ∀ a: A(x,t,a)

  was bedeutet, dass es eine Zeit und einen Ort gibt, wo alles gleichzeitig angemessen ist. (Man könnte dies auch als „ es gibt für alles eine Zeit und einen Ort “ beschreiben; dies zeigt nur, dass Alltagssprache mehrdeutig ist und dass man bei der Interpretation ein Urteilsvermögen ausüben muss.) Um a more zu verwenden ergreifendes Beispiel, wenn L( x,y,t ) bedeutet " x liebt y zur Zeit t ", dann ist die Proposition

  ∀x ∃y ∃t: L(x,y,t)

  könnte interpretiert werden als „ jeder liebt irgendwann jemanden “; wohingegen

  ∃y ∀x ∃t: L(x,y,t)

  bedeutet, dass es eine einzelne Person gibt, die jeder irgendwann in seinem Leben liebt;

  ∃t ∀x ∃y: L(x,y,t)

  bedeutet, dass es eine Zeit gibt, in der jeder in jemand anderen verliebt ist; und

  ∃y ∃t ∀x: L(x,y,t)

  bedeutet, dass es eine einzelne Person gibt, die zu mindestens einem Zeitpunkt von allen gleichzeitig geliebt wurde – was alles ganz unterschiedliche Dinge bedeutet.

Einzigartige Existenz

Schließlich können wir unter Verwendung der Theorie der eindeutigen Beschreibungen einzigartige Existenz charakterisieren, indem wir eine Kombination aus existentieller Quantifizierung, universeller Quantifizierung und Gleichheit verwenden. Wenn zum Beispiel E( x ) = " x ist Elvis Presley" und i = ich selbst, könnte ich I am the one and only Elvis Presley by ausgeben

E(i) & ∀y: [ (y ≠ i) ⇒ ¬E(y) ]

oder "Ich bin Elvis Presley, und jeder, der nicht ich ist, ist nicht Elvis Presley". Wir können dies logisch vereinfachen (allerdings auf Kosten einer leicht perversen Formulierung in normaler Sprache), indem wir im zweiten Teil das Kontrapositiv nehmen:

E(i) & ∀y: [ E(y) ⇒ (y = i) ]

oder "Ich bin Elvis Presley, und jeder, der Elvis Presley ist, ist niemand anderes als ich selbst". Wenn ich sagen wollte, dass es einen und nur einen Elvis Presley gibt, ohne zu behaupten, ich selbst sei Elvis, könnte ich stattdessen schreiben

∃x: [ E(x) & ∀y: [ E(y) ⇒ (x = y) ]]

was wir interpretieren könnten als "es gibt jemanden, der Elvis Presley ist, und [er ist einzigartig, dh] jeder, der Elvis Presley ist, ist kein anderer als der Elvis Presley". (Unter Verwendung der Definitionen der eingeschränkten Quantifizierungen könnten wir dies sogar schreiben als ∃x∈E ∀y∈E: (x=y): "es gibt einen Elvis Presley, und alle Elvis Presley sind dieselbe Person".)

Wenn wir sagen wollten, dass es mindestens zwei Elvis Presley gibt, könnten wir nur den Teil der obigen Aussage verneinen, wo wir die Einzigartigkeit beanspruchen:

∃x: [ E(x) & ¬∀y: [ E(y) ⇒ (x = y) ]]

oder gleichwertig

∃x: [ E(x) & ∃y: [ E(y) & (x ≠ y) ]]

(Die eingeschränkte Quantifizierungsversion würde geschrieben werden als ∃x∈E ∃y∈E: (x≠y), oder "There are two [different] Elvises Presley".) Wir können den inneren Quantifizierer nach vorne ausführen, wodurch die Formel in die Pränex-Normalform gebracht wird :

∃x ∃y: E(x) & E(y) & (x ≠ y) .

Wenn wir sagen wollten, dass es genau zwei Elvis Presley gibt , könnten wir dann behaupten, dass jeder, der Elvis Presley ist, einer der beiden sein muss, die wir identifiziert haben

∃x ∃y: E(x) & E(y) & (x ≠ y) & (∀z: [ E(z) ⇒ (z=x ∨ z=y) ]) .

oder wir können auch schreiben , indem wir den inneren Quantor nach außen bringen, um die Formel in die Pränex-Normalform zu bringen

∃x ∃y ∀z: E(x) & E(y) & (x ≠ y) & [ E(z) ⇒ (z=x ∨ z=y) ] .