Kvantifikatori

Rečenica poput $x^2\ge 0$ nije iskaz dok promenljiva $x$ ne dobije određenu vrednost ili se ne veže kvantifikatorom. Kvantifikatori određuju koliko elemenata posmatranog skupa treba da zadovolji dati uslov. Skup iz kojeg biramo promenljivu naziva se domen i mora biti poznat jer isti zapis može imati različitu istinitosnu vrednost u različitim skupovima. U primerima ćemo koristiti $\mathbb{N}=\{1,2,3,\ldots\}$ .

Ako je $P(x)$ uslov koji zavisi od promenljive $x$ , koristimo sledeće zapise:

Naziv	Zapis	Čitanje
Univerzalni kvantifikator	$(\forall x\in A)P(x)$	Za svaki $x$ iz skupa $A$ važi $P(x)$
Egzistencijalni kvantifikator	$(\exists x\in A)P(x)$	Postoji bar jedan $x$ iz skupa $A$ za koji važi $P(x)$
Kvantifikator jedinstvenosti	$(\exists!x\in A)P(x)$	Postoji tačno jedan $x$ iz skupa $A$ za koji važi $P(x)$

Na primer,

(\forall x\in\mathbb{R})(x^2\ge 0)

čitamo: „Za svaki realan broj $x$ , njegov kvadrat je nenegativan.” Iskaz

(\exists!x\in\mathbb{R})(x+1=2)

čitamo: „Postoji tačno jedan realan broj $x$ za koji je $x+1=2$ .” Taj broj je $x=1$ .

Univerzalni iskaz $(\forall x)P(x)$ tačan je samo ako uslov $P(x)$ važi za svaki element domena. Da bismo pokazali da nije tačan, dovoljno je pronaći jedan kontraprimer.
Egzistencijalni iskaz $(\exists x)P(x)$ dokazujemo tako što pronađemo bar jedan element domena koji ispunjava uslov. Ako rešavamo jednačinu, njeno rešenje obavezno proveravamo u zadatom domenu.

Primer: Ispitajmo iskaze u skupu prirodnih brojeva.

Iskaz

(\forall x\in\mathbb{N})(x\cdot1=1)

je netačan. Za $x=2$ dobijamo $2\cdot1=2\ne1$ , pa je $x=2$ kontraprimer.

Iskaz

(\exists x\in\mathbb{N})(x+7=11)

je tačan, jer za $x=4$ važi $4+7=11$ . Broj $4$ je primer koji potvrđuje postojanje traženog elementa.

Provera nekoliko primera nije dokaz univerzalnog iskaza. Jedan kontraprimer dovoljan je da ga opovrgne, ali za dokaz njegove tačnosti uslov mora biti opravdan za proizvoljan element domena.

Kada formula sadrži više kvantifikatora, čitamo ih sleva nadesno. Njihov redosled utiče na značenje formule. U izrazu $(\forall x)(\exists y)P(x,y)$ vrednost $y$ može zavisiti od izabranog $x$ . U izrazu $(\exists y)(\forall x)P(x,y)$ prvo biramo jedno isto $y$ koje zatim mora odgovarati svakom $x$ .

Primer: Za svaki ceo broj postoji njemu suprotan ceo broj:

(\forall x\in\mathbb{Z})(\exists y\in\mathbb{Z})(x+y=0).

Za proizvoljno $x$ možemo izabrati $y=-x$ , pa je iskaz tačan. Broj $y$ zavisi od izabranog broja $x$ .

Ako zamenimo redosled kvantifikatora,

(\exists y\in\mathbb{Z})(\forall x\in\mathbb{Z})(x+y=0),

dobijamo netačan iskaz. Ne postoji jedan ceo broj $y$ koji je istovremeno suprotan svakom celom broju $x$ .

Pri negiranju kvantifikovanog iskaza kvantifikator se menja, a uslov se negira:

Početna negacija	Ekvivalentan zapis
$\neg(\forall x)P(x)$	$(\exists x)\neg P(x)$
$\neg(\exists x)P(x)$	$(\forall x)\neg P(x)$

Rečenica „Nije tačno da svaki element ima svojstvo $P$ ” znači da postoji bar jedan element koji nema svojstvo $P$ . Rečenica „Ne postoji element sa svojstvom $P$ ” znači da nijedan element nema to svojstvo.

Primer: Negirajmo iskaz

(\forall x\in\mathbb{R})(x=0).

Univerzalni kvantifikator prelazi u egzistencijalni, a jednakost se menja u nejednakost:

\neg(\forall x\in\mathbb{R})(x=0) \equiv (\exists x\in\mathbb{R})(x\ne0).

Negacija zato glasi: „Postoji realan broj različit od nule.”

Ako predikat sadrži više uslova, posle promene kvantifikatora negiramo ceo predikat. Tada koristimo i pravila za negaciju logičkih operacija i relacija, na primer:

\neg(x<5)\equiv x\ge5, \qquad \neg(P\lor Q)\equiv\neg P\land\neg Q.

Pri rešavanju prvo odredi domen, zatim pročitaj kvantifikatore sleva nadesno. Za $\forall$ traži opšte obrazloženje ili kontraprimer, a za $\exists$ pokušaj da pronađeš konkretnu vrednost koja zadovoljava uslov.

Započni učenje

Online časovi

Kvantifikatori