1.2 cuantificatori
reamintim că o formulă este o afirmație a cărei valoare de adevărpoate depinde de valorile unor variabile. De exemplu,
” $x \ le 5 \ land x> 3$”
este adevărat pentru $x = 4$ și fals pentru $ x = 6$. Comparați acest lucru cu declarația
” pentru fiecare $x$, $x \ le 5 \ land x>3$,”
ceea ce este cu siguranță fals și afirmația
„există un $X $ astfel încât $ x \ le 5 \ land x>3$,”
ceea ce este cu siguranță adevărat. Expresia”pentru fiecare $x$”(uneori” pentru toți $X$”) este numităun cuantificator universal și este notat cu $\forall x$. Expresia „există un $X $ astfel încât” se numește un cuantificator existențialși este denotatde $ \ există x$. O formulă care conține variabile nu este pur și simpluadevărat sau fals, cu excepția cazului în care fiecare dintre aceste variabile este legată de un cuantificator. Dacă o variabilă nu este legată, adevărul formulei este condiționat de valoarea atribuită variabilei din universul discursului.
am fost atenți în secțiunea 1.1 Să definim cu exactitate valorile adevărului enunțurilor compuse. Facem același lucru pentru$\forall x\,P(x)$ și $\există x\,P(x)$, deși semnificația intenționată a acestora este clară.
Cuantificatorul Universal
o propoziție $\forall x\,P(x)$ este adevărat dacă și numai dacă $P(x)$ este adevărat nomatter ce valoare (din universul discursului) este înlocuită cu $x$.
exemplul 1.2.1
$\bullet$ $\forall x (x^2\ge 0)$,adică „pătratul oricărui număr nu este negativ.”
$\bullet$ $\forall x\,\forall y (x+Y=y+x)$, adică legea comutativă a adăugării.
$\bullet$ $\forall x\,\forall y\,\forall z ((X+y)+z=x+(y+z))$,adică legea asociativă a Adunării.
$\pătrat$
forma” toate”.Cuantificatorul universal este frecvent întâlnit în următorul context:$$\forall x (P(X)\implică Q(x)),$$care poate fi citit, „toate $x$ satisfăcătoare $P(x)$ satisfac și$Q(x)$.”Parantezele sunt cruciale aici; asigurați-vă că înțelegeți diferența dintre forma „all” și $\forall x\,P(x)\implică\forall x\,Q(x)$ și $(\forall x\,P(X))\implică Q(x)$.
ultima formulă ar putea fi scrisă și ca $\forall x\,P(x)\implicăq(x)$, ceea ce înseamnă că cuantificatorul universal are o precedență mai mare decât condiționalul; pentru a evita neînțelegerile,cel mai bine este să includeți parantezele. Semnificația acestei formularepoate să nu fie clar la început. $X $ în $ P(x)$ este legat de cuantificatorul universal, dar $x$ În $Q (x)$ nu este. Formula$(\forall x\, P(X)) \implică Q (x)$ are același înțeles ca $(\forallx\, P(x))\implică Q (y)$, iar adevărul său depinde de valoarea alocată variabilei în $Q (\cdot)$.
exemplul 1.2.2
$\bullet$ $\forall x$ ($x$ este un pătrat $\implică$ $x$ este un dreptunghi),adică „toate pătratele sunt dreptunghiuri.”
$\bullet$ $\forall x$ ($x$ locuiește în Walla Walla $\implică$ $x$ locuiește în Washington), adică „fiecare persoană care locuiește în Walla Walla locuiește în Washington.”
$\pătrat$
această construcție este uneori folosită pentru a exprima o propoziție matematică a formei” dacă aceasta, atunci aceea”, cu un cuantificator” înțeles”.
exemplul 1.2.3
$\bullet$ dacă spunem „dacă $x$ este negativ, la fel este și cubul său”, noi înțelegem de obicei „fiecare $X$ negativ are un cub negativ.”Acest lucru ar trebui să fie scris simbolic ca$ \ forall x ((x
$\bullet$ „dacă două numere au același pătrat, atunci au aceeași valoare absolută” ar trebui să fie scris ca$\forall x\,\forall y ((x^2=y^2)\implică (\vert x\vert = \vert y\vert))$.
$\bullet$ „dacă $x=Y$, atunci $X+z=y+z$” ar trebui să fie scris ca $\forall x\,\forally\,\forall z ((x=y)\implică (X+z=y+z))$.
$\pătrat$
dacă $s$ este un set, propoziția” fiecare $x$ în $s$ satisface $P(x)$ ” este scrisă formal ca$$\forall x ((x\în s)\implică P(x))$$ pentru claritate și concizie, aceasta este de obicei scrisă $\forall x\,{\in}\,S\,(P(x))$. Pentru a înțelege și manipula corect formula $ \ forallx\, {\in}\, S\, (P(x))$, uneori va trebui să o”dezabreviați”, rescriind-o ca $\forall x ((x\in s)\implicăp(x))$.
exemplu 1.2.4
$\bullet$ $\forall x\in (\sqrt x\ge x)$reprezintă $\forall x (x\in \implică \sqrt x\ge x).$
$ \ bullet $ $ \ forall x
$\pătrat$
Cuantificatorul existențial
o propoziție $\există x\,P(x)$ este adevărat dacă și numai dacă există cel puțino valoare de $x$ (din universul discursului) care face $P(x)$ adevărat.
exemplu 1.2.5
$\bullet$ $\există x (x \ge x^2)$este adevărat, deoarece $x=0$ este o soluție. Există multe altele.
$\bullet$ $\există x\,\există y (x^2+y^2=2XY)$ este adevărat deoarece$x=y=1$ este una dintre multele soluții.
$\pătrat$
forma” unora”. Existențialquantifier este frecvent întâlnit în următorul context: $$\exists x\(P(x)\land Q(x)),$$ care poate fi citit, „unele $x$ satisfacatoare $P(x)$ de asemenea, satisfies $Q(x)$.”
exemplul 1.2.6
$\bullet$ $\exists x\, \hbox{($X$ este profesor $\land$ $x$ este republican)}$, adică „un profesor este republican.”
$\bullet$ $\exists x\, \hbox{($X$ este un număr prim $\land$ $x$ este par)}$, adică”un număr prim este par.”
$\pătrat$
la început poate părea că ” unele $ x $ satisfying $ P(x)$satisfies $Q (x)$” ar trebui traduse ca$$\exists x(P(x)\implică Q (x)),$$ca cuantificatorul universal. Pentru a vedea de ce acest lucru nu funcționează,Să presupunem $P(x)=\hbox{„$X$ este un măr”}$ și $Q(x)=\hbox{„$X$ este anorange.”} $ Propoziția „unele mere sunt portocale” este sigurfalsă, dar$$\există x (P(x)\implică Q(x))$$este adevărat. Pentru a vedea acest lucru să presupunem că $x_0$ este un anumit portocaliu. Apoi$p(x_0)\implică Q (x_0)$ evaluează la $\hbox{F}\implică \hbox{t}$,care este T, iar cuantificatorul existențial este satisfăcut.
folosim abrevieri ale formei „unele” la fel ca cele pentru forma”toate”.
exemplu 1.2.7
$ \ bullet $ $ \ exists x
$\bullet$ $ \exists x\in (2x^2+x =1)$ reprezintă $ \exists x ((x\in )\land (2x^2 + x = 1)) $ $ \ square$
dacă $ \ forall $ corespunde cu ” all „și $\exists$ corespunde cu”some „avem nevoie de un al treilea cuantificator pentru a corespunde cu”none”? După cum arată următoarele, acest lucru nu este necesar:
exemplul 1.2.8
$\bullet$ „nu Democrații sunt republicani,” poate fi scris $\forall X$ ($x$ este un democrat $\implică$ $x$ nu este un republican).
$\bullet$ „nu triunghiuri sunt dreptunghiuri,” poate fi scris $\forall x$ ($x$ este un triunghi $\implică$ $x$ nu este un dreptunghi).
$\pătrat$
în general, afirmația” nu $x$ satisfăcător $p(x)$ satisface $Q(x) $ ” poate fi scrisă $ $ \pentrutoate x (P(X)\implică \LNU Q(x)).$$(Poate vă întrebați de ce nu folosim $\LNU \există x\,(P(x)\teren Q(x))$. De fapt, am putea—este echivalent cu $\forall x (P(X)\implică \LNU Q(x))$.)
exerciții 1.2
în aceste probleme, să presupunem că universul discursului este numere reale.
Ex 1.2.1 exprimă următoarele formule care implică cuantificatori:
a) orice număr ridicat la a patra putere nu este negativ.
b) un număr ridicat la a treia putere este negativ.
c) sinusul unui unghi este întotdeauna între $+1$ și $-1$.
d) secanta unui unghi nu este niciodată strict între $+1$ și $-1$.
Ex 1.2.2 să presupunem că $X$ și $Y$ sunt seturi. Exprimați următoarele ca formule care implică cuantificatori.
a) fiecare element de $X$ este un element de $Y$.
b) un element de $X$ este un element de $Y$.
c) un element de $X$ nu este un element de $Y$.
d) niciun element de $X$ nu este un element de $Y$.
Ex 1.2.3 reamintim (din calcul) că o funcție $f$ crește dacă$$ \forall a \forall b (a
a) $f$ scade.
b) $f$ este constantă.
c) $f$ are un zero.
Ex 1.2.4 exprimă simbolic următoarele legi:
a) Legea comutativă a înmulțirii
b) legea asociativă a înmulțirii
c) legea distributivă
Ex 1.2.5 sunt următoarele propoziții adevărate sau false?
a) $\forall x \forall y (x
b) $\forall x \forall y \forall z\ne 0 (XZ=YZ\implică x=y)$
c) $\există x
d) $\există x \există y \există z (x^2+y^2+z^2=2XY-2+2z)$
Ex 1.2.6 să presupunem că $P(x)$ și $Q (y)$ sunt formule.
a) este $\forall x \forall y (P(x)\implică Q(y))$echivalent cu $\forall x(P(X)) \implică \forall y(Q(y))$?
b) este $\există x \există y (P(x)\teren Q(y))$echivalent cu $\există x(P(x)) \teren \există y(Q(y))$?