1.2 Quantifiers
Husk at en formel Er en uttalelse hvis sannhetsverdikan avhenge av verdiene til noen variabler. For eksempel
«$x\le 5 \land x> 3$»
er sant for $x = 4$ og falsk for $ x= 6$. Sammenlign dette med setningen
«for hver $x$, $x\le 5 \land x>3$,»
som er definitivt falsk og setningen
«det eksisterer en $x$ slik at $x\le 5 \ land x>3$,»
som er definitivt sant. Uttrykket » for hver $ x$»(noen ganger» for alle $x$») kallesen universell kvantifier og er betegnet med $\forall x$. Uttrykket «det eksisterer en $x $ slik det» kalles en eksistensiell quantifier og betegnesav $ \ eksisterer x$. En formel som inneholder variabler er ikke bare sann eller usann med mindre hver av disse variablene er bundet av en kvantifier. Hvis en variabel er notbound sannheten av formelen er betinget av verdien tildelt til variablefra universet av diskurs.
vi var forsiktige i avsnitt 1.1 for å definere sannhetsverdiene av sammensatte uttalelser nøyaktig. Vi gjør det samme for$\forall x\,P(x)$ og $\eksisterer x\,P(x)$, selv om de tiltenkte betydningene av disse er klare.
Universal Quantifier
en setning $\forall x\,P(x)$ er sant hvis og bare hvis $P(x)$ er sann nomatter hvilken verdi (fra diskursuniverset) er erstattet av $x$.
Eksempel 1.2.1
$\bullet$ $\forall x (x^2\ge 0)$,dvs. «kvadratet av et hvilket som helst tall er ikke negativt.»
$\bullet$ $ \ forall x\,\forall y (x + y=y + x)$, dvs. den kommutative loven om tillegg.
$ \ bullet$ $ \ forall x\,\forall y\,\forall z ((x + y) + z=x + (y+z))$,dvs.den assosiative loven om tillegg.
$ \ kvadrat$
» all » form.Den universelle kvantifiseringen oppstår ofte i følgende sammenheng:$$\forall x (P (x) \ innebærer Q (x)),$$som kan leses, » Alle $ x$ tilfredsstillende $P (x)$ tilfredsstiller også$Q (x)$.»Parenteser er avgjørende her; vær sikker på at du forstår forskjellen mellom» alle » skjemaet og $\forall x\, P (x) \ innebærer\forall x\, Q (x)$ og $(\forall x\, P(X)) \ innebærer Q (x)$.
sistnevnte formel kan også skrives som $ \ forall x\, P (x)\impliesQ (x)$, som er å si at den universelle kvantifisereren har høyerestående enn den betingede; for å unngå misforståelser er det best å inkludere parentesene. Betydningen av denne formelenmight ikke være klart først. $X$ i $ P (x)$ er bundet avuniversal quantifier, men $x$ i $ Q (x)$ er ikke. Formelen$(\forall x\,p (X))\impliserer Q (x)$ har samme betydning som $(\forallx\, P(X)) \ impliserer Q (y)$, og dens sannhet avhenger av verdien tilordnet variabelen i $ Q (\cdot)$.
Eksempel 1.2.2
$\bullet$ $\forall x$ ($x$ er en firkant $\innebærer$ $x$ er et rektangel),dvs. «alle firkanter er rektangler.»
$ \ bullet$ $ \ forall x $ ($x $ bor I Walla Walla $ \ innebærer$ $ x $ bor I Washington), dvs. «hver person som bor I Walla Walla bor I Washington.»
$ \ kvadrat$
denne konstruksjonen brukes noen ganger til å uttrykke amatematisk setning av skjemaet «hvis dette, da det» med en»forstått» kvantifier.
Eksempel 1.2.3
$\bullet$ hvis vi sier, «hvis $x$ er negativ, så er kuben,» betyr vi vanligvis » hver negativ $x$ har en negativ kube.»Dette bør skrives symbolsk som$ \ forall x ((x
$ \ bullet$» hvis to tall har samme firkant, så har de samme absolutte verdi » skal skrives som$\forall x\,\forall y ((x^2=y^2) \ impliserer (\vert x \vert = \vert y \ vert))$.
$\bullet$ «hvis $x=y$, så $x+z=y+z$» skal skrives som $\forall x\,\forally\,\forall z ((x=y)\innebærer (x+z=y+z))$.
$ \ kvadrat$
hvis $S$ er et sett, er setningen «hver $x$ i $s$ tilfredsstiller $P (x)$» skrevet formelt som$$ \ forall x ((x\i s)\innebærer P(x))$$ for klarhet og korthet, dette er vanligvis skrevet $\forall x\,{\in}\,S\, (p (x))$. For å forstå og manipulere formelen $\forallx\,{\in}\,S\, (p(x))$ riktig, må du noen ganger «unabbreviate» den, omskrive den som $ \ forall x ((x\I s)\impliesP (x))$.
Eksempel 1.2.4
$ \ bullet$ $ $ \ forall x \ in (\sqrt x \ ge x) $ står for $ \ forall x (x\in \ innebærer \sqrt x \ ge x).$
$ \ bullet $ $ \ forall x
$ \ kvadrat$
Den Eksistensielle Kvantifiseringen
en setning $\eksisterer x\, P(x)$ er sant hvis Og bare hvis det er minsten verdi på $x$ (fra diskursuniverset) som gjør $P(x)$ sant.
Eksempel 1.2.5
$\bullet$ $\eksisterer x (x \ge x^2)$er sant siden $x=0$ er en løsning. Det er mange andre.
$ \ bullet$ $ \ eksisterer x\, \ eksisterer y (x^2 + y^2=2xy) $ er sant siden$x = y = 1$ er en av mange løsninger.
$ \ kvadrat$
«noen» form. Eksistensialquantifier oppstår ofte i følgende sammenheng: $$\eksisterer x \ (P (x) \ land Q (x)),$$ som kan leses, » Noen $x$ tilfredsstillende $P (x)$ også tilfredsstiller $Q (x)$.»
Eksempel 1.2.6
$\bullet$ $\exists x\, \hbox{($x$ er professor $\land$ $x$ er republikansk)}$, dvs. «noen professor er republikaner.»
$\bullet$ $\eksisterer x\, \hbox {($x$ er et primtall $ \ land$ $ x $ er jevnt)}$, dvs.»noen primtall er jevnt.»
$ \ kvadrat$
Det kan først virke som «Noen $x $ tilfredsstillende $ P (x) $ tilfredsstiller $Q(x)$» skal oversettes som$ $ \ eksisterer x (P (x) \ innebærer Q (x)),$$som universell kvantifier. For å se hvorfor dette ikke virker,anta $P(x)=\hbox{«$x$ er et eple»}$ Og $Q (x)=\hbox{«$x$ er anorange.»} $ Setningen «noen epler er appelsiner» er sikkertfalsk, men$$\eksisterer x (P (x) \ innebærer Q (x))$$er sant. For å se dette antar $x_0$ er noe spesielt oransje. Da$P(x_0) \ impliserer Q (x_0) $ evaluerer til $\hbox{F} \ impliserer \hbox{T}$, Som Er T, og den eksistensielle kvantifiseringen er fornøyd.
vi bruker forkortelser av» noen «form mye som de for» alle » form.
Eksempel 1.2.7
$\bullet$ $\eksisterer x
$\bullet$ $ \eksisterer x\in (2x^2+x =1)$ står for $ \eksisterer x ((x\in )\land (2x^2+x=1))$ $ \ kvadrat$
Hvis $\forall$ tilsvarer «alle» og $\eksisterer$ tilsvarer «noen» trenger vi en tredje kvantifier for å svare til «ingen»? Som følgende viser, er dette ikke nødvendig:
Eksempel 1.2.8
$\bullet$ «ingen demokrater er republikanere,» kan skrives $\forall x$ ($x$ er en demokrat $ \ innebærer$ $ x$ er ikke en republikansk).
$\bullet$ «ingen trekanter er rektangler,» kan skrives $\forall x $ ($x$ er en trekant $\innebærer$ $x$ er ikke et rektangel).
$ \ kvadrat$
generelt kan setningen «nei $x $ tilfredsstillende $P (x) $ tilfredsstiller $Q (x)$» skrives $$ \ forall x (P (x) \ impliserer \ lnot Q(x)).$$(Du lurer kanskje på hvorfor vi ikke bruker $\likke \ eksisterer x\, (P(x)\land Q (x))$. Faktisk kunne vi-det tilsvarer $ \ forall x (P (x) \ innebærer \lnot Q (x))$.)
Øvelser 1.2
i disse problemene, antar universet av diskurs er thereal tall.
Ex 1.2.1 Uttrykke følgende som formler som involverer kvantifisere:
a) Et hvilket som helst tall hevet til fjerde kraft er ikke-negativt.
b) noen tall hevet til den tredje kraften er negativ.
c) sinus av en vinkel er alltid mellom $+1$ og $-1$.
d) sekanten av en vinkel er aldri strengt mellom $ + 1$ og $-1$.
Ex 1.2.2 Anta At $X$ og $ Y$ er sett. Uttrykk følgende som formler som involverer kvantifiserere.
a) Hvert element av $X$ er et element av $Y$.
b) noe element på $X$ er et element på $Y$.
c) noe element på $X$ er ikke et element på $Y$.
d) Ingen element av $X$ er et element av $Y$.
Ex 1.2.3 Tilbakekalling (fra kalkulator) at en funksjon $f$ øker hvis$$ \forall a \forall b (a
a) $f$ reduseres.
b) $f$ er konstant.
c) $f$ har null.
Ex 1.2.4 Uttrykke følgende lover symbolsk:
a) den kommutative loven om multiplikasjon
b) den assosiative loven om multiplikasjon
c) distribusjonsloven
Ex 1.2.5 er følgende setninger sanne eller usanne?
a) $\forall x \forall y (x
b) $\forall x \forall y \forall z\ne 0 (xz=yz\innebærer x=y)$
c) $\eksisterer x
d) $\eksisterer x \eksisterer y \eksisterer z (x^2+y^2+z^2=2xy-2+2z)$
Ex 1.2.6 Anta At $P(x)$ og $Q(y)$ Er formler.
a) er $\forall x \forall y (P(x)\impliserer Q(y))$tilsvarende $\forall x(P(x)) \impliserer \forall y(Q(y))$?
b) er $\eksisterer x \eksisterer y (P(x)\land Q(y))$tilsvarende $\eksisterer x(P(x)) \land \eksisterer y(Q(y))$?