1.2 Quantifizierer
Denken Sie daran, dass eine Formel eine Aussage ist, deren Wahrheitswertkann von den Werten einiger Variablen abhängen. Beispiel:
„$x\le 5 \land x> 3$“
ist wahr für $ x = 4 $ und falsch für $ x = 6 $. Vergleichen Sie dies mit der Aussage
„Für jedes $ x $, $ x \ le 5 \ land x>3$,“
was definitiv falsch ist und die Aussage
„Es gibt ein $x$, so dass $ x\le 5 \land x>3$,“
was definitiv stimmt. Der Ausdruck „für jedes $ x $“(manchmal „für alle $ x $“) wird aufgerufenein universeller Quantifizierer und wird mit $ \ forall x $ bezeichnet. Der Ausdruck „es existiert ein $ x $, so dass“ als existentialquantifier bezeichnet wird und durch $ \ exists x $ bezeichnet wird. Eine Formel, die Variablen enthält, ist nicht einfachwahr oder falsch, es sei denn, jede dieser Variablen ist durch einen Quantifizierer gebunden. Wenn eine Variable nicht definiert ist, hängt die Wahrheit der Formel von dem Wert ab, der der Variablen aus dem Universum des Diskurses zugewiesen ist.
Wir haben in Abschnitt 1.1 darauf geachtet, die Wahrheitswerte zusammengesetzter Aussagen genau zu definieren. Wir machen dasselbe für $ \forall x \,P(x) $ und $\exists x\,P(x) $ , obwohl die beabsichtigten Bedeutungen davon klar sind.
Der universelle Quantifizierer
Ein Satz $ \ forall x \,P(x) $ ist genau dann wahr, wenn $ P(x) $ wahr ist, unabhängig davon, welcher Wert (aus dem Universum des Diskurses) $ x $ ersetzt.
Beispiel 1.2.1
$ \bullet$ $ \forall x (x ^ 2 \ge 0) $, dh „Das Quadrat einer beliebigen Zahl ist nicht negativ.“
$\bullet$ $\forall x\,\forall y (x+y=y+x)$, d.h. das kommutative Gesetz der Addition.
$\bullet$ $\forall x\,\forall y\,\forall z ((x+y)+z=x+(y+z))$, d. H. das assoziative Additionsgesetz.
$\Quadrat$
Die „alle“ Form.Der universelle Quantifizierer wird häufig im folgenden Kontext angetroffen: $$ \ forall x (P(x) \impliziert Q(x)), $$ was gelesen werden kann: „Alle $ x $, die $ P (x) $ erfüllen, erfüllen auch $ Q (x) $.“ Klammern sind hier entscheidend; Stellen Sie sicher, dass Sie den Unterschied zwischen der „all“ -Form und $\forall x\,P(x)\impliziert\forall x \,Q(x) $ und $(\forall x\,P(x))\impliziert Q(x) $ .
Die letztere Formel könnte auch als $\forall x \,P(x) \impliesQ(x) $ geschrieben werden, was bedeutet, dass der universelle Quantifizierer eine höhere Präzedenz hat als die Bedingung; Um Missverständnisse zu vermeiden, ist es am besten, die Klammern einzuschließen. Die Bedeutung dieser Formelkann zunächst nicht klar sein. Das $ x $ in $ P (x) $ ist durch den universellen Quantifizierer gebunden, das $ x $ in $ Q (x) $ jedoch nicht. Die Formel$(\forall x\,P(x)) \impliziert Q(x) $ hat die gleiche Bedeutung wie $(\forallx\,P(x)) \impliziert Q(y) $, und ihre Wahrheit hängt von dem Wert ab, der der Variablen in $ Q (\ cdot) $ zugewiesen wurde.
Beispiel 1.2.2
$ \ bullet $ $ \forall x $ ($ x $ ist ein Quadrat $ \impliziert $ $ x $ ist ein Rechteck), dh „Alle Quadrate sind Rechtecke.“
$ \bullet$ $\forall x $ ($ x $ lebt in Walla Walla $ \ impliziert $ $ x$ lebt in Washington), dh „Jede Person, die in Walla Walla lebt, lebt in Washington.“
$\Quadrat$
Diese Konstruktion wird manchmal verwendet, um ein auszudrückenmathematischer Satz der Form „wenn dies, dann das“ mit einem“verstandenen“ Quantifizierer.
Beispiel 1.2.3
$ \ bullet $ Wenn wir sagen: „Wenn $ x $ negativ ist, ist auch sein Würfel“, meinen wir normalerweise „Jedes negative $ x $ hat einen negativen Würfel.“ Dies sollte symbolisch geschrieben werden als$\forall x ((x
$\bullet$ „Wenn zwei Zahlen das gleiche Quadrat haben, dann haben sie den gleichen absoluten Wert“ sollte geschrieben werden als$\forall x\,\forall y ((x^2=y^2)\,(\vert x\vert = \vert y\vert)) $.
$\bullet$ „Wenn $x=y$, dann sollte $x+z=y+z$“ als $\forall x\,\forally\,\forall z ((x=y)\, (x+z=y+z)) $ geschrieben werden.
$\Quadrat$
Wenn $S $ eine Menge ist, wird der Satz „every $x$ in $S$ satisfies $P(x)$“ formal als$$\forall x ((x\in S)\implies P(x))$$ Für Klarheit und Kürze wird dies normalerweise geschrieben $\forall x\,{\in}\,S\,(P(x)) $. Um die Formel $\forallx\,{\in}\,S\, (P(x))$ richtig zu verstehen und zu manipulieren, müssen Sie sie manchmal „unknacken“ und als $\forall x ((x\in S)\impliesP(x))$ .
Beispiel 1.2.4
$\bullet$$\forall x\in (\sqrt x\ge x)$steht für $\forall x (x\in \bullet \sqrt x\ge x).$
$ \ Kugel $ $ \ für alle x
$ \ Quadrat$
Der existentielle Quantifizierer
Ein Satz $\exists x\,P(x) $ ist genau dann wahr, wenn es mindestens einen Wert von $ x $ (aus dem Universum des Diskurses) gibt, der $ P (x) $ wahr macht.
Beispiel 1.2.5
$\bullet$ $\exists x (x \ge x^2)$ist wahr, da $x=0 $ eine Lösung ist. Es gibt viele andere.
$\bullet$ $\exists x\,\exists y (x^2+y^2=2xy)$ ist wahr, da $x=y= 1 $ eine von vielen Lösungen ist.
$\Quadrat$
Die „einige“ Form. Der existentialquantifier wird häufig im folgenden Kontext angetroffen: $$\exists x\(P(x) \land Q(x)),$$ was gelesen werden kann: „Einige $ x $, die $ P (x) $ befriedigen, befriedigen auch $ Q (x) $.“
Beispiel 1.2.6
$\bullet$ $\exists x\, \hbox{($ x $ ist ein Professor $ \ land $ $ x$ ist ein Republikaner)}$, dh „Ein Professor ist ein Republikaner.“
$\bullet$ $\exists x\, \hbox{($x $ ist eine Primzahl $\land $ $x$ ist gerade)} $, dh“eine Primzahl ist gerade.“
$\Quadrat$
Es mag auf den ersten Blick scheinen, dass „Einige $ x $, die $ P (x) $ befriedigen, $ Q (x) $ befriedigen“, als $$ \ exists x (P (x) \exists Q(x)) übersetzt werden sollten), $$ wie der universelle Quantifizierer. Um zu sehen, warum dies nicht funktioniert, nehmen wir an, $P(x)=\hbox{„$x $ ist ein Apfel“} $ und $ Q(x) =\hbox{„$ x $ ist ein Apfel“.“}$ Der Satz „einige Äpfel sind Orangen“ ist sicherfalsch, aber $$\exists x (P(x)\implies Q(x))$$ist wahr. Um dies zu sehen, nehmen wir an, $ x_0 $ ist eine bestimmte Orange. Dann ergibt $P(x_0) \implies Q(x_0) $ $ \hbox{F} \implies \hbox{T} $ , was T ist, und der existentielle Quantifizierer ist erfüllt.
Wir verwenden Abkürzungen der „einige“ Form ähnlich wie die für die“alle“ Form.
Beispiel 1.2.7
$\bullet$ $\existiert x
$\bullet$ $ \existiert x\in (2x^2+x =1)$ steht für $ \existiert x ((x\in )\land (2x^2+x=1))$$\square$
Wenn $ \ forall $ „all“ entspricht und $ \ exists $ „some“ entspricht, benötigen wir einen dritten Quantifizierer, der „none“ entspricht? Wie das Folgende zeigt, ist dies nicht erforderlich:
Beispiel 1.2.8
$ \ bullet $ „Keine Demokraten sind Republikaner“ kann geschrieben werden $\ forall x $ ($ x $ ist ein Demokrat $ \ impliziert $ $ x $ ist kein Republikaner).
$\bullet$ „Keine Dreiecke sind Rechtecke“, kann geschrieben werden $\forall x $ ($ x $ ist ein Dreieck $\impliziert $ $ x $ ist kein Rechteck).
$\Quadrat$
Im Allgemeinen kann die Aussage „no $x$ satisfying $P(x)$ satisfies $Q(x)$“ geschrieben werden $$\forall x (P(x)\implies \lnot Q(x)).$$(Sie fragen sich vielleicht, warum wir nicht $\lnot \exists x\,(P(x)\land Q(x))$ . In der Tat könnten wir-es ist äquivalent zu $ \forall x (P(x) \ impliziert \lnot Q(x)) $.)
Übungen 1.2
Nehmen wir in diesen Problemen an, dass das Universum des Diskurses thereale Zahlen ist.
Ex 1.2.1Geben Sie Folgendes als Formeln mit Quantifizierern an:
a) Jede Zahl, die auf die vierte Potenz angehoben wird, ist nicht negativ.
b) Eine auf die dritte Potenz erhobene Zahl ist negativ.
c) Der Sinus eines Winkels liegt immer zwischen $+1$ und $-1$.
d) Die Sekante eines Winkels liegt niemals streng zwischen $+ 1 $ und $-1 $.
Ex 1.2.2Angenommen, $ X $ und $Y $ sind Mengen. Drücken Sie Folgendes als Formeln mit Quantifizierern aus.
a) Jedes Element von $X$ ist ein Element von $Y $.
b) Ein Element von $X $ ist ein Element von $Y $.
c) Ein Element von $ X $ ist kein Element von $Y $.
d) Kein Element von $X$ ist ein Element von $Y $.
Ex 1.2.3Erinnern Sie sich (aus der Infinitesimalrechnung) daran, dass eine Funktion $f $ zunimmt, wenn $$ \forall a \forall b (a
a) $f $ abnimmt.
b) $f$ ist konstant.
c) $f$ hat eine Null.
Ex 1.2.4Drücken Sie die folgenden Gesetze symbolisch aus:
a) das kommutative Multiplikationsgesetz
b) das assoziative Multiplikationsgesetz
c) das Verteilungsgesetz
Ex 1.2.5Sind die folgenden Sätze wahr oder falsch?
a) $ \ füralle x \ füralle y (x
b) $ \ füralle x \ füralle y \ füralle z \ne 0 (xz = yz \ impliziert x = y) $
c) $ \ existiert x
d) $ \ existiert x \ existiert y \existiert z (x ^ 2 + y ^ 2 + z ^ 2 = 2xy-2 + 2z)$
Ex 1.2.6Angenommen, $ P(x) $ und $Q(y) $ sind Formeln.
a) Ist $\forall x \forall y (P(x) \impliziert Q(y)) $äquivalent zu $\forall x(P(x)) \impliziert \forall y(Q(y))$?
b) Ist $\exists x \exists y (P(x)\land Q(y))$äquivalent zu $\exists x(P(x)) \land \exists y(Q(y))$?