1.2 Kvantifikátory
připomeňme, že vzorec je prohlášení, jehož pravdivá hodnotamůže záviset na hodnotách některých proměnných. Například
“ $x\le 5 \ land x> 3$“
platí pro $x= 4$ a false pro $ x= 6$. Porovnejte si to s tvrzením,
„Pro každé $x$, $x\le 5 \půdy x>3$,“
což je určitě nepravdivé a prohlášení
„existuje $x$ taková, že $x\le 5 \půdy x>3$,“
což je určitě pravda. Fráze „pro každý $x$“ (někdy “ pro všechny $x$“) se nazýváuniverzální kvantifikátor a je označen $\forall x$. Fráze „thereexists a $x$ such that“ se nazývá existencialquantifier a označuje se $\X$. Vzorec, který obsahuje proměnné, není prostěpravdivé nebo nepravdivé, pokud každá z těchto proměnných není vázána kvantifikátorem. Pokud proměnná není vázána, pravdivost vzorce je podmíněna hodnotou přiřazenou proměnnémuod vesmíru diskurzu.
v oddíle 1.1 jsme byli opatrní, abychom přesně definovali pravdivé hodnoty složených výroků. Totéž děláme pro$\forall x\, P (x)$ a $\exists x\, P (x)$, ačkoli zamýšlené významy z nich jsou jasné.
Univerzální Kvantifikátor
věta $\forall x\,P(x)$ je pravda tehdy a jen tehdy, když $P(x)$ je pravda, nomatter jaké hodnoty (z vesmíru diskurzu) dosadíme za $x$.
příklad 1.2.1
$ \ bullet$ $ \ forall x (x^2\ge 0)$, tj. “ čtverec libovolného čísla není záporný.“
$ \ bullet$ $\forall x\,\forall y (x+y=y+x)$, tj. komutativní zákon sčítání.
$ \ bullet$ $ \ forall x\, \ forall y\,\forall z ((x+y)+z=x+(y+z))$,tj. asociativní zákon sčítání.
$ \ čtverec$
formulář „vše“.Univerzální kvantifikátor se často vyskytuje v následujícím kontextu:$$\forall x (P(x)\implikuje Q (x)),$$, které lze číst, “ všechny $x $ uspokojující $P (x)$ také uspokojují$Q (x)$.“Závorky jsou zde rozhodující; ujistěte se, že rozumíte si rozdílu mezi „všechny“ forma a $\forall x\,P(x)\znamená,\forall x\,Q(x)$ a $(\forall x\,P(x))\implikuje Q(x)$.
Ten vzorec by mohl být také zapsán jako $\forall x\,P(x)\impliesQ(x)$, která je říci, že univerzální kvantifikátor má higherprecedence než podmíněné; aby nedošlo k nedorozumění,je nejlepší zahrnout závorky. Význam tohoto vzorcemusí být zpočátku jasné. $X$ v $P(x)$ je vázán univerzální kvantifikátor, ale $x$ v $Q(x)$ není. Vzorec$(\forall x\,P(x))\implikuje Q(x)$ má stejný význam jako $(\forallx\,P(x))\implikuje Q(y)$, a jeho pravda závisí na hodnotě rozděleni do proměnné $Q(\cdot)$.
příklad 1.2.2
$ \ bullet$ $\forall x$ ($x$ je čtverec $ \ implikuje$ $ x$ je obdélník), tj. “ všechny čtverce jsou obdélníky.“
$ \ bullet$ $ \ forall x$ ($x $ žije ve Walla Walla $ \ implikuje$ $ x $ žije ve Washingtonu), tj. “ každý člověk, který žije ve Walla Walla žije ve Washingtonu.“
$\square$
Tato konstrukce někdy se používá k vyjádření amathematical věty typu „pokud toto, pak to,“ s“pochopil“, kvantifikátor.
příklad 1.2.3
$ \ bullet$ pokud řekneme: „pokud $x$ je záporné, tak je jeho kostka, „obvykle znamená“ každý záporný $x$ má zápornou kostku.“To by mělo být napsáno symbolicky jako$\forall x ((x
$\bullet$ „Pokud dvě čísla mají stejný metr, pak mají stejnou absolutní hodnotu“, by měl být napsán jako$\forall x\,\forall y ((x^2=y^2)\znamená(\vert x\vert = \vert y\vert))$.
$ \ bullet$ “ pokud $x=y$, pak $x + Z=y + Z$“ by měl být zapsán jako $\forall x\,\forally\,\forall z ((x=y)\implikuje (x+Z=y+z))$.
$\square$
Pokud je $S$ je množina věta „každé $x$ v $S$ splňuje $P(x)$“ iswritten formálně jako$$\forall x ((x\in Y)\implikuje P(x))$$ Pro přehlednost a stručnost, to je obvykle napsáno $\forall x\,{\v}\,Y\,(P(x))$. Chcete-li správně pochopit a manipulovat se vzorcem $\forallx\,{\in}\,S\, (P(x))$, budete jej někdy muset“unabbreviate“ a přepsat jej jako $\forall x ((x\in s)\impliesP(x))$.
příklad 1.2.4
$ \ bullet$ $ \ forall x \ in (\sqrt x \ ge x)$je zkratka pro $ \ forall x (x\in \implikuje\sqrt x \ GE x).$
$\bullet$ $\forall x
$\square$
Existenční Kvantifikátor
věta $\exists x\,P(x)$ je pravda, pokud a pouze pokud je v leastone hodnotu $x$ (z vesmíru diskurzu), který činí $P(x)$ je pravda.
příklad 1.2.5
$ \ bullet$ $ \ existuje x (x \ge x^2)$je pravda, protože $x=0$ je řešení. Existuje mnoho dalších.
$ \ bullet$ $\existuje x\, \ existuje y (x^2+y^2=2xy)$ je pravda, protože$x=y=1$ je jedním z mnoha řešení.
$ \ čtverec$
formulář“ některé“. S existenciálním kvantifierem se často setkáváme v následujícím kontextu: $$\x \ (P (x)\land Q(x)),$$, které lze číst, „některé $x$ p(x) $také odpovídají$ Q(x)$.“
Příklad 1.2.6
$\bullet$ $\exists x\, \h{($x$ je profesor $\pozemků$ $x$ je republikán)}$, tj. „nějaký profesor je republikán.“
$ \ bullet$ $ \ existuje x\, \hbox {($x$ je prvočíslo $ \ land$ $ x$ je sudé)}$, tj.“některé prvočíslo je sudé.“
$\square$
To může na první pohled zdát, že „Nějaké $x$ splňující $P(x)$splňuje $Q(x)$“ by mělo být přeloženo jako$$\exists x (P(x)\implikuje Q(x)),$$jako univerzální kvantifikátor. Vidím, proč to nefunguje,předpokládám, že $P(x)=\h{„$x$ je jablko“}$ a $Q(x)=\h{„$x$ je anorange.“} $ Věta „některá jablka jsou pomeranče“ je jistáfalse, ale$$\existuje x (P(x)\znamená Q (x))$$je pravda. Chcete-li to vidět, předpokládejme, že $x_0$ je nějaká konkrétní oranžová. Pak$P(x_0)\implikuje Q(x_0)$ hodnotí na $\h{F}\znamená \h{T}$,což je T, a existenční kvantifikátor je spokojen.
používáme zkratky formuláře „některé“ podobně jako zkratky pro formulář“ vše“.
Příklad 1.2.7
$\bullet$ $\exists x
$\bullet$ $ \exists x\in (2x^2+x =1)$ znamená $ \exists x ((x\), \land (2x^2+x=1))$$\square$
Pokud $\forall$ odpovídá „všechny“ a $\exists$ odpovídá „některé“potřebujeme třetí kvantifikátor odpovídá „nic“? Jak ukazuje následující, není to nutné:
příklad 1.2.8
$ \ bullet$ „žádní demokraté nejsou republikáni,“ lze napsat $\forall x$ ($x$ je demokrat $ \ implikuje$ $ x$ není republikán).
$ \ bullet$ „žádné trojúhelníky jsou obdélníky,“ lze zapsat $\forall x$ ($x$ je trojúhelník $ \ implikuje$ $x$ není obdélník).
$ \ čtverec$
obecně lze příkaz „no $ x $ satisfying $P (x)$ satisfying $Q (x)$“ napsat $$ \ forall x (P (x) \ implikuje \lnot Q(x)).$$(Možná se divíte, proč nepoužíváme $\lnot \existuje x\, (P (x)\land Q (x))$. Ve skutečnosti bychom mohli-to je ekvivalentní $\forall x (P (x) \ implikuje \lnot Q (x))$.)
cvičení 1.2
v těchto problémech předpokládáme, že vesmír diskurzu je tamální čísla.
Ex 1.2.1 Vyjadřují následující vzorce zahrnující kvantifikátory:
a) libovolný počet zvýšil na čtvrtou je non-negativní.
b) některé číslo zvýšené na třetí mocninu je záporné.
c) sinus úhlu je vždy mezi $+1$ a $ -1$.
d) sekant úhlu není nikdy striktně mezi $ + 1$ A $ -1$.
Ex 1.2.2 Předpokládejme, že $X$ a $Y$ jsou sady. Vyjádřete následující jako vzorce zahrnující kvantifikátory.
a) každý prvek $X$ je prvek $Y$.
b) nějaký prvek $X$ je prvek $Y$.
c) nějaký prvek $X$ není prvek $Y$.
d) žádný prvek $X$ není prvek $Y$.
Ex 1.2.3 Připomeňme (z počtu), že funkce $f$ se zvyšuje, pokud$$ \forall a \forall b (a
A) $f$ klesá.
b) $f$ je konstantní.
c) $f$ má nulu.
Ex 1.2.4 vyjadřují symbolicky následující zákony:
a) komutativní zákon násobení
b) asociativní zákon pro násobení
c) distributivní zákon,
Ex 1.2.5 Jsou následující věty pravdivé nebo nepravdivé?
) $\forall x \forall y (x
b) $\forall x \forall y \forall z\ne 0 (xz=yz\implikuje x=y)$
c) $\exists x
d) $\exists x \exists y \exists z (x^2+y^2+z^2=2xy-z 2+2z)$
Ex 1.2.6 Předpokládejme, že $P(x)$ a $Q(y)$ jsou vzorce.
a) je $\forall x \forall y (P (x) \ implikuje Q (y)) $ ekvivalentní $\forall x(P (x)) \implikuje \forall y(Q (y))$?
b) je $\existuje x \existuje y (P (x)\land Q (y)) $ ekvivalentní $ \ existuje x(P (x)) \land \existuje y(Q (y))$?