1.2 Kvantificatorer
Husk at en formel er en erklæring, hvis sandhedsværdikan afhænge af værdierne af nogle variabler. For eksempel
” $5 \ land> 3$”
er sandt for $ 4$ og falsk for $ 6$. Sammenlign dette med udsagnet
“for hver$$, $ $ \le 5 \ land>3$,”
hvilket er absolut falsk og udsagnet
” der findes en $ $ sådan at $5 \ land>3$,”
hvilket er helt sikkert sandt. Udtrykket”for hver $$”(nogle gange” for alle$$$”) kaldesen universel kvantificator og er betegnet med$\for alle$$. Udtrykket” der eksisterer en $$ sådan, at ” kaldes en eksistentiel kvantifier og er betegnet med $\eksisterer$. En formel, der indeholder variabler, er ikke simpelthensand eller falsk, medmindre hver af disse variabler er bundet af en kvantifier. Hvis en variabel ikke er bundet, er sandheden i formlen betinget af den værdi, der er tildelt variablenfra diskursens univers.
vi var forsigtige i afsnit 1.1 med at definere sandhedsværdierne for sammensatte udsagn præcist. Vi gør det samme for$\for alt\,P ($) $og$ \eksisterer\,P ( $ )$, selvom de tilsigtede betydninger af disse er klare.
den universelle Kvantificator
en sætning $\for alle\,P(S)$ er sand, hvis og kun hvis $P(S)$ er sand nomatter hvilken værdi (fra diskursuniverset) erstattes af $S$.
eksempel 1.2.1
$\bullet$ $\forall “(^2\ge 0)$,dvs. ” kvadratet af et hvilket som helst tal er ikke negativt.”
$\bullet$ $\forall\,\forall y (S+y=y+s)$, dvs.kommutativ lov om tilføjelse.
$ \ bullet$ $ \ forall\, \ forall y\, \ forall å ((s+y)+å=s+(y + å))$, dvs.den associative lov om tilføjelse.
$\firkant$
den” ALLE ” form.Den universelle kvantificeringsmaskine findes ofte i følgende sammenhæng:$$\for alle “betyder”,$$, som kan læses, ” alle$$, der opfylder$ P ( $ )$, tilfredsstiller også$ $ ($)$.”Parenteser er afgørende her; vær sikker på at du forstår forskellen mellem “alle” – formularen og $\for alle\,P(For)\indebærer\for alle\,K(for)$ og $(\for alle\,P(For))\indebærer K(for)$.
sidstnævnte formel kan også skrives som $\for alle\,p(s)\indebærer$, hvilket vil sige,at den universelle kvantificator har højere end den betingede; for at undgå misforståelse er det bedst at medtage parenteserne. Betydningen af denne formelmå ikke være klar i starten. $ $I$ P ($)$ er bundet af den universelle kvantifikator, men $$ i $ $ er ikke. $ Har samme betydning som$ (\forall\, P(S)) \betyder $(\forall\, P(S))\betyder$ (y)$, og dens sandhed afhænger af den værdi, der er tildelt variablen i$K (\cdot)$.
eksempel 1.2.2
$ \ bullet$ $ \ for alt $ ($$$er en firkant $ \indebærer$ $ $ er et rektangel), dvs. “alle firkanter er rektangler.”
$\bullet$ $\for alt$ ($$$$$$betyder $ $ $ $ bor i USA), dvs. ” enhver person, der bor i USA, bor i USA.”
$ \ firkant$
denne konstruktion bruges undertiden til at udtrykke enmatematisk sætning af formularen “hvis dette, så det” med en”forstået” kvantificator.
eksempel 1.2.3
$\bullet$ hvis vi siger, “hvis $$ er negativ, så er dens terning,” vi normalt mener “hver negativ $$ har en negativ terning.”Dette skal skrives symbolsk som$\forall ((
$ \ bullet$ “hvis to tal har samme firkant, så har de samme absolutte værdi” skal skrives som$\forall\,\forall y ((^^2=y ^ 2)\indebærer(\vert\vert = \vert y\vert))$.
$\bullet$ “hvis $H=y$, så $H=y+å$” skal skrives som $\forall h\,\forally\,\forall H ((H=y)\indebærer (h+å=y+å))$.
$\firkant$
hvis $S$ er et sæt, skrives sætningen “hver $$ i $S$ opfylder $P ($) $” formelt som$$\forall ((s\I S) \indebærer P(S))$$ for klarhed og kortfattethed skrives dette normalt $\forall\, {\in}\, S\, (P(S))$. For at forstå og manipulere formlen $\forall\,{\in}\,S\, (P(H))$ korrekt, skal du nogle gange”unabbreviate” det, omskrive det som $\forall\((h\in S) \ impliesP(h))$.
eksempel 1.2.4
$\bullet$ $\forall\in (\forall\ge)$står for $\forall * (\in \indebærer \forall*).$
$ \ bullet$ $ \foralle
$ \ firkant$
den eksistentielle Kvantificator
en sætning $\eksisterer\,P(H)$ er sand, hvis og kun hvis der er mindsten værdi på $$ (fra diskursuniverset), der gør $P(H)$ true.
eksempel 1.2.5
$\bullet$ $\eksisterer (2)$er sandt, da $=0$ er en løsning. Der er mange andre.
$ \ bullet$ $ \ eksisterer\, \ eksisterer y (2+y^2=2)$ er sandt, da$1$ er en af mange løsninger.
$\firkant$
den” nogle ” form. Den eksistentielle kvantifier opstår ofte i følgende sammenhæng: $ $ \ eksisterer \ \(p(s) \ land K(S)),$$ som kan læses, “nogle $$ opfylder $P (S)$ også tilfredsstiller $K (S)$.”
eksempel 1.2.6
$\bullet$ $\eksisterer\, \hboks {($$$er en professor$ \land $$$ er en republikaner)}$, dvs. “en professor er en republikaner.”
$\bullet$ $\eksisterer\, \ hboks {($$er et primtal $ \ land$ $ $ er lige)}$, dvs. ” nogle primtal er lige.”
$ \ firkant$
det kan i første omgang synes ,at “nogle$ $ tilfredsstillende $P ($) $ opfylder $ $ $” skal oversættes som$ $ \ eksisterer For at se,hvorfor dette ikke virker, skal du antage, at $P (S) = \ H boks {“$S $ er et æble”}$ og $S(S)=\H boks {“$S$ er anorange.”} $ Sætningen “nogle æbler er appelsiner”er helt sikkertfalsk, men$$\eksisterer. For at se dette antager $0$ er en bestemt orange. Derefter$ P(H_0)\indebærer K(H_0) $evalueres til$\hboks{F}\indebærer \hboks{T}$, som er T, og den eksistentielle kvantificator er opfyldt.
vi bruger forkortelser af “nogle” – formularen meget som dem for”alle” – formularen.
eksempel 1.2.7
$\bullet$ $\eksisterer
$\bullet$ $ \eksisterer\i (2 gange^2+gange =1)$ står for $ \eksisterer \ land (2 gange^2 + gange=1))$ $ \ firkant$
hvis $ \ forall$ svarer til” alle “og $\eksisterer$ svarer til”nogle “har vi brug for en tredje kvantificator for at svare til”ingen”? Som det følgende viser, er dette ikke nødvendigt:
eksempel 1.2.8
$\bullet$ “ingen Demokrater er republikanere,” kan skrives $\forall$ ($$er en demokrat $\indebærer$ $$ er ikke en republikaner).
$\bullet$ “ingen trekanter er rektangler,” kan skrives $\forall$ ($$er en trekant $\indebærer$ $$ er ikke et rektangel).
$\firkant$
generelt kan udsagnet “ingen $ $ tilfredsstillende $P ($) $ opfylder $K ($) $” skrives $$\for alle K (P(K) \ indebærer \ lnot K (K)).$$(Du kan undre dig over, hvorfor vi ikke bruger $\lnot \eksisterer\,(P(S)\land K(S))$. Faktisk kunne vi—det svarer til $\for alt (P(S)\indebærer \lnot spørgsmål(S))$.)
øvelser 1.2
i disse problemer antager universet af diskurs er derreelle tal.
eks 1.2.1 udtrykker følgende som formler, der involverer kvantificatorer:
a) ethvert tal hævet til den fjerde magt er ikke-negativt.
b) nogle tal hævet til den tredje magt er negativ.
c) sinus af en vinkel er altid mellem $+1$ og $-1$.
d) sekanten af en vinkel er aldrig strengt mellem $+1$ og $-1$.
eks 1.2.2 Antag $$ $og$ Y $ er sæt. Udtryk følgende som formler, der involverer kvantificatorer.
a) hvert element på $$ er et element på $Y$.
b) et element af $$ er et element af $Y$.
c) noget element på $$ er ikke et element på $Y$.
d) intet element på $$ er et element på $Y$.
eks 1.2.3 husk (Fra Beregning), at en funktion $f$ stiger, hvis$$ \forall a \forall b (a
a) $f$ falder.
b) $f$ er konstant.
c) $f$ har et nul.
eks 1.2.4 udtrykke følgende love symbolsk:
a) den kommutative lov om multiplikation
b) den associative lov om multiplikation
c) fordelingsloven
eks 1.2.5 Er følgende sætninger sande eller falske?
a) $\forall \forall y (
b) $\forall \forall y \forall y\ne 0 ($=y\indebærer=y) $
c) $\eksisterer
d) $ \eksisterer \eksisterer y \eksisterer å (
eks 1.2.6 Antag, at $P(S)$ og $P(y)$ er formler.
A) er $\forall \forall y (P(s)\indebærer s(y))$svarende til $\forall S(P(S)) \indebærer \forall y(S(y))$?
b) er $\eksisterer \eksisterer y (P(K)\land K(y))$svarende til $\eksisterer S(P(K)) \land \eksisterer y(k(y))$?