1.2 Kwantificeerders
herinneren eraan dat een formule een statement is waarvan de waarheidswaarde kan afhangen van de waarden van sommige variabelen. Bijvoorbeeld,
” $x \ le 5 \ land x> 3$”
is waar voor $x = 4$ en onwaar voor$x = 6$. Vergelijk dit met de verklaring
” voor elke $x$, $x \ le 5 \ land x>3$,”
dat is zeker onwaar en de verklaring
” er bestaat een $x$ zodanig dat $x \ le 5 \ land x>3$,”
wat zeker waar is. De zinsnede ” voor elke $x$”(soms” voor alle $x$”) is calleda universal quantifier en wordt aangegeven door $\forall x$. De zinsnede “er bestaat een $x$ zodanig dat” een existentialquantifier wordt genoemd en wordt aangeduid door $\exists x$. Een formule die variabelen bevat is niet simplytrue of false tenzij elk van deze variabelen is gebonden door een kwantificeerder. Als een variabele niet gebonden is, is de waarheid van de formule afhankelijk van de waarde die is toegewezen aan variabel uit het universum van discours.
in Paragraaf 1.1 hebben we zorgvuldig de waarheidswaarden van samengestelde verklaringen nauwkeurig gedefinieerd. We doen hetzelfde voor$ \ forall x\, P (x)$ en $ \ bestaat x\, P (x)$, hoewel de bedoelde betekenissen hiervan duidelijk zijn.
de Universele waardegever
een zin $\forall x\, P (x)$ is dan en slechts dan waar als $P (x)$ waar is nomatter welke waarde (uit het universum van discours) wordt vervangen door $x$.
voorbeeld 1.2.1
$ \ bullet$ $ \ forall x (x^2\ge 0)$,d.w.z. “het kwadraat van een willekeurig getal is niet negatief.”
$ \ bullet$ $ \ forall x\, \ forall y (x+y=y+x)$, d.w.z. de commutatieve wet van optellen.
$ \ bullet$ $ \ forall x\, \ forall y\,\forall z ((x+y)+z=x+(y+z))$,d.w.z. de associatieve wet van optellen.
$ \ vierkant$
het “alle” formulier.De universele kwantificeerder wordt vaak aangetroffen in de volgende context:$$ \ forall x(P(x)\impliceert Q(x)),$$die kan worden gelezen, “Alle $x$ tevredenstellend $P(x)$ voldoen ook$Q (x)$.”Haakjes zijn hier cruciaal; zorg ervoor dat je het verschil begrijpt tussen de” all ” vorm en $\forall x\, P(x)\impliceert\forall x\, Q (x)$ en $(\forall x\, P(x))\impliceert Q (x)$.
deze laatste formule kan ook worden geschreven als $\forall x\, P (x) \ impliesQ(x)$, dat wil zeggen dat de universele kwantificeerder een hogere precisie heeft dan de voorwaardelijke; om misverstanden te voorkomen,is het het beste om de haakjes op te nemen. De Betekenis van deze formulericht in het begin niet duidelijk. De $x$ in $P (x)$ is gebonden door de Universal quantifier, maar de $x$ in $Q(x)$ is dat niet. De formule$(\forall x\, P(x))\impliceert Q (x)$ heeft dezelfde betekenis Als $(\forallx\,P(x))\impliceert Q (y)$, en de waarheid ervan hangt af van de waarde toegewezen aan de variabele in $Q (\cdot)$.
voorbeeld 1.2.2
$ \ bullet$ $ \ forall x$ ($x$ is een vierkant $\impliceert$ $x$ is een rechthoek), d.w.z., “alle vierkanten zijn rechthoeken.”
$\bullet$ $ \ forall x$ ($x$ woont in Walla Walla $\impliceert$ $x$ woont in Washington), dat wil zeggen: “iedere persoon die in Walla Walla woont, woont in Washington.”
$ \ vierkant$
deze constructie wordt soms gebruikt om amathetische zin van de vorm uit te drukken “als dit, dan dat,” met een”begrepen” kwantificeerder.
voorbeeld 1.2.3
$\bullet$ als we zeggen: “als $x$ negatief is, zo is zijn kubus,” bedoelen we meestal ” elke negatieve $x$ heeft een negatieve kubus.”Dit zou symbolisch moeten worden geschreven als$\forall x ((x
$ \ bullet$ “als twee getallen hetzelfde vierkant hebben, dan hebben ze dezelfde absolute waarde” zou moeten worden geschreven als$\forall x\,\forall y ((x^2=y^2)\implies(\vert X\vert = \vert y\vert))$.
$ \ bullet$ “als $x = y$, dan $x + z = y+z$” moet worden geschreven als $\forall x\,\forally\,\forall z ((x=y)\implies (x+z=y+z))$.
$ \ vierkant$
als $s$ een verzameling is, wordt de zin “elke $x$ in $s$ voldoet aan $P(x)$” formeel geschreven als$$ \ forall x ((x\in s)\impliceert P(x))$$ voor duidelijkheid en beknoptheid, wordt dit meestal geschreven $\forall x\,{\in}\,S\, (P (x))$. Om de formule $\forallx\,{\in}\,S\, (P(x))$ goed te begrijpen en te manipuleren, moet je het soms”unabbreviate” maken en herschrijven als $\forall x ((x\in s)\impliesP(x))$.
voorbeeld 1.2.4
$ \ bullet$ $ \ forall x \ in (\sqrt x\ge x)$staat voor $\forall x (x\in \impliceert \sqrt x \ ge x).$
$ \ bullet$ $ \ forall x
$ \ square$
de existentiële Kwantificeerder
een zin $ \ bestaat x\, P (x)$ is dan en alleen waar als er tenminste een waarde is van $x$ (uit het universum van discours) die $P (x)$ waar maakt.
voorbeeld 1.2.5
$ \ bullet$ $ \ bestaat x (x \ ge x^2)$is waar omdat $x=0$ een oplossing is. Er zijn vele anderen.
$ \ bullet$ $ \ exists x\, \ exists y (x^2+y^2=2xy)$ is waar omdat$x=y=1$ een van de vele oplossingen is.
$ \ vierkant$
de “sommige” vorm. De existentialquantifier wordt vaak aangetroffen in de volgende context: $$ \ exists x\(P(x)\land Q(x)),$$ die gelezen kan worden, “Some $x$ satisfying $P(x)$ alsosatisfies $Q (x)$.”
voorbeeld 1.2.6
$ \ bullet$ $\ exists x\, \hbox{($x$ is een professor $ \ land$ $x$ is een Republikein)}$, dat wil zeggen: “sommige professor is een Republikein.”
$ \ bullet$ $ \ exists x\,\hbox {($x$ is een priemgetal $ \ land$ $x$ is even)}$, dat wil zeggen,”een priemgetal is even.”
$ \ vierkant$
het kan op het eerste gezicht lijken dat ” sommige$ x $ tevredenstellend $P(x)$tevredenstellend $Q (x)$” vertaald moet worden als$$\exists x(P(x)\implies Q (x)),$$zoals de universele kwantificeerder. Om te zien waarom dit niet werkt,stel dat $P(x)=\hbox{“$x$ is een apple”}$ en $Q (x)=\hbox{“$x$ is anorange.”} $ De zin “sommige appels zijn sinaasappels” is zeker verkeerd, maar$$\bestaat x (P(x)\impliceert Q(x))$$is waar. Om dit te zien veronderstel $x_0$ is een bepaalde oranje. Dan$ P(x_0)\implies Q(x_0) $evalueert naar$\hbox{F}\implies \hbox{T}$, wat T is, en de existentiële waardegever is tevreden.
we gebruiken afkortingen van de “sommige” vorm zoals die voor de” alle ” vorm.
voorbeeld 1.2.7
$ \ bullet$ $ \ exists x
$ \ bullet$ $ \exists x \ in (2x^2+x =1)$ staat voor $ \exists x ((x\in )\land (2x^2 + x = 1))$$ \ square$
als $ \ forall$ correspondeert met ” all “en $ \ exists $ correspondeert met “some” hebben we dan een derde kwantificeerder nodig om te corresponderen met “none”? Zoals het volgende laat zien, is dit niet nodig:
voorbeeld 1.2.8
$\bullet$ “geen Democraten zijn Republikeinen,” kan worden geschreven $\forall x$ ($x$ is een democraat $\impliceert$ $x$ is geen Republikein).
$ \ bullet$ “geen driehoeken zijn rechthoeken,” kan worden geschreven $ \ forall x$ ($x$ is een driehoek $\impliceert$ $x$ is geen rechthoek).
$ \ vierkant$
in het algemeen kan het statement “no $x$ satisfying $P(x)$ satisfying $Q(x)$” geschreven worden $$\forall x(P(x)\implies \lnot Q (x)).$$(Je vraagt je misschien af waarom we geen $\lnot \exists x\, (P(x)\land Q (x))$gebruiken. In feite kunnen we-het is gelijk aan $ \ forall x(P(x)\impliceert \lnot Q (x))$.)
oefeningen 1.2
in deze problemen, neem aan dat het universum van het discours bestaat uit getallen.
Ex 1.2.1 drukt het volgende uit als formules met kwantificeerders:
a) elk getal verhoogd tot de vierde macht is niet-negatief.
b) een getal dat is verhoogd tot de derde macht is negatief.
c) de sinus van een hoek ligt altijd tussen $+1$ en $-1$.
d) de secant van een hoek ligt nooit strikt tussen $+1$ en $-1$.
Ex 1.2.2 stel dat $X$ en $Y$ Verzamelingen zijn. Druk het volgende uit als formules met kwantificeerders.
a) elk element van $X$ is een element van $Y$.
b) een element van $X$ is een element van $Y$.
c) een element van $X$ is geen element van $Y$.
d) geen element van $X$ is een element van $Y$.
Ex 1.2.3 Recall (uit calculus) dat een functie $f$ toeneemt als$$ \forall a \forall b (a
a) $f$ afneemt.
b) $f$ is constant.
c) $f$ heeft een nul.
Ex 1.2.4 drukken de volgende wetten symbolisch uit:
A) de commutatieve wet van de vermenigvuldiging
b) de associatieve wet van de vermenigvuldiging
c) de distributieve wet
Ex 1.2.5 zijn de volgende zinnen waar of onwaar?
a) $\forall x \forall y (x
b) $ \ forall x \forall y \forall z \ ne 0 (xz=yz\impliceert x=y)$
c) $\bestaat x
d) $\bestaat X \bestaat y \bestaat z (x^2+y^2 + z^2=2xy-2+2z)$
Ex 1.2.6 stel dat $P (x)$ en $Q(y)$ formules zijn.
a) is $\forall x \forall y (P(x)\impliceert Q(y))$equivalent aan $\forall x(P(x)) \impliceert \forall y(Q(y))$?
b) is $\exists x \exists y (P(x)\land Q(y))$equivalent aan $\exists x(P(x)) \land \exists y(Q(y))$?