1.2 kwantyfikatory
przypominają, że formuła jest stwierdzeniem, którego wartość prawdy zależy od wartości niektórych zmiennych. Na przykład
” $X \ le 5 \ land x> 3$”
jest true dla $x= 4$ i false dla$x = 6$. Porównaj to ze stwierdzeniem
” dla każdego $x$, $X\le 5 \ land x>3$,”
co jest zdecydowanie fałszywe i stwierdzenie
” istnieje $x$ takie, że $X \ le 5 \ land x>3$,”
co zdecydowanie jest prawdą. Wyrażenie „dla każdego $x$” (czasami „dla wszystkich $x$”) nazywa się kwantyfikatorem uniwersalnym i jest oznaczane przez $ \ forall x$. Wyrażenie „thereexists an $x$ such that”nazywa się existentialquantifier i jest oznaczone przez $ \ exists x$. Formuła zawierająca zmienne nie jest prosta ani fałszywa, chyba że każda z tych zmiennych jest związana kwantyfikatorem. Jeśli zmienna nie jest powiązana, to prawda formuły jest zależna od wartości przypisanej zmiennej z uniwersum dyskursu.
w sekcji 1.1 byliśmy ostrożni, aby precyzyjnie określić wartości prawdy wyrażeń złożonych. To samo robimy dla$ \ forall x\, P (x)$ i $ \ exists x\, p (x)$, chociaż zamierzone znaczenie tych wartości jest jasne.
Kwantyfikator Uniwersalny
zdanie $ \ forall x\, P (x)$ jest prawdziwe wtedy i tylko wtedy, gdy $p (x)$ jest prawdziwe, jaka wartość (z uniwersum dyskursu) jest zastąpiona $x$.
przykład 1.2.1
$ \ bullet$ $ \ forall x (X^2\ge 0)$, czyli ” kwadrat dowolnej liczby nie jest ujemny.”
$ \ bullet$ $ \ forall x\, \ forall y (x+y=y+x)$, czyli przemienne prawo dodawania.
$ \ bullet$ $ \ forall x\, \ forall y\, \ forall z ((x+y)+Z=x+(y+z))$,czyli asocjacyjne prawo dodawania.
$ \ square$
formularz „wszystkie”.Kwantyfikator uniwersalny jest często spotykany w następującym kontekście:$$ \ forall x (P (x) \ implikuje Q (x)),$$, które można odczytać, ” wszystkie $ x $ spełniające $P (x)$ spełniają również$Q (x)$.”Nawiasy są tutaj kluczowe; upewnij się,że rozumiesz różnicę między formą „all” a $\forall x\, P(x)\implikuje\forall x\, Q(x)$ i $(\forall x\, P(x))\implikuje Q(x)$.
ten ostatni wzór może być również zapisany jako $ \ forall x\, P (x) \ impliesQ (x)$, co oznacza, że kwantyfikator uniwersalny ma wyższą predykcję niż warunkowy; aby uniknąć nieporozumień,najlepiej jest podać nawiasy. Znaczenie tego wzoru początkowo nie jest jasne. $ X$ W $ P (x)$ jest związany kwantyfikatorem uniwersalnym, ale $x$ W $Q(x)$ nie jest. Formuła$(\forall x\,P (x))\implikuje Q(x)$ ma takie samo znaczenie jak $(\forallx\,P(x))\implikuje Q(y)$, a jej prawda zależy od wartości przypisanej do zmiennej w $Q(\cdot)$.
przykład 1.2.2
$ \ bullet$ $ \ forall x$ ($x$ jest kwadratem $ \ implikuje$ $x$ jest prostokątem), tzn. ” wszystkie kwadraty są prostokątami.”
$ \ bullet$ $ \ forall x$ ($X $ mieszka w Walla Walla $\implikuje$ $x$ mieszka w Waszyngtonie), czyli ” każda osoba, która mieszka w Walla Walla mieszka w Waszyngtonie.”
$ \ kwadrat$
konstrukcja ta jest czasami używana do wyrażenia zdania amatematycznego w formie „if this, then that,” Z kwantyfikatorem „understand”.
przykład 1.2.3
$ \ bullet$ jeśli mówimy, „jeśli $x$ jest ujemne, tak jak jego sześcian,” zwykle mamy na myśli ” każdy minus $x$ ma ujemny sześcian.”To powinno być zapisane symbolicznie jako$\forall x ((X
$ \ bullet$ „Jeśli dwie liczby mają ten sam kwadrat, to mają tę samą wartość bezwzględną” powinno być zapisane jako$ \ forall x\, \ forall y ((x^2=y^2) \ implikuje (\vert x\vert = \Vert y\vert))$.
$ \ bullet$ ” Jeśli $x = y$, to $x + Z=y+Z$” powinno być zapisane jako $\forall x\,\forally\,\forall z ((x=y)\implikuje (x+Z = y+Z))$.
$ \ square$
jeśli $S$ jest zbiorem, zdanie „każde $x$ W $S$ spełnia $P (x)$” jest pisane formalnie jako$$ \ forall x ((x\in s)\implikuje P (x))$$ dla jasności i zwięzłości, Zwykle zapisuje się to $ \ forall x\, {\in}\, S\, (P (x))$. Aby poprawnie zrozumieć i manipulować formułą $ \ forallx\, {\in}\, S\, (P (x))$, czasami trzeba ją „unabbreviate”, przepisując ją jako $\forall x ((x\in s)\impliesP(x))$.
przykład 1.2.4
$\bullet$ $\forall x\in (\sqrt x\ge X)$oznacza $\forall x (x \in \implikuje\sqrt x \ ge x).$
$\bullet$ $\forall x
$ \ square$
Kwantyfikator egzystencjalny
zdanie $ \ istnieje x\, P (x)$ jest prawdziwe wtedy i tylko wtedy, gdy istnieje co najmniej jedna wartość $x$ (z uniwersum dyskursu), która sprawia, że $P(x)$ jest prawdziwe.
przykład 1.2.5
$ \ bullet$ $ \ exists X (x \ge x^2)$jest prawdziwe, ponieważ $x = 0$ jest rozwiązaniem. Jest wiele innych.
$ \ bullet$ $ \ exists x\, \ exists y (x^2+y^2=2xy)$ jest prawdziwe, ponieważ$x = y = 1$ jest jednym z wielu rozwiązań.
$ \ square$
„jakaś” forma. Existentialquantifier jest często spotykany w następującym kontekście: $$ \ exists x\(P (x) \ land Q(x)),$$, które można odczytać, „niektóre $x$ spełnia $p(x)$ również $Q(x)$.”
przykład 1.2.6
$ \ bullet$ $ \ exists x\, \ hbox {($x$ to profesor $ \ land$ $ x $ to republikanin)}$, tzn. „jakiś profesor jest Republikaninem.”
$ \ bullet$ $ \ exists x\, \ hbox {($x$ jest liczbą pierwszą $ \ land$ $ x $ jest parzystą)}$, tzn.”niektóre liczby pierwsze są parzyste.”
$ \ kwadrat$
na początku może się wydawać, że” jakieś $x$ spełniające $P(x)$spełnia $Q(x)$ ” powinno być przetłumaczone jako$$\exists x (P(x)\implikuje Q(x)),$$jak kwantyfikator uniwersalny. Aby zobaczyć,dlaczego to nie działa, Załóżmy, że $p (x)=\hbox{„$x$ is an apple”}$ i $Q (x) = \hbox{„$x$ is anorange.”} $ Zdanie „niektóre jabłka to pomarańcze” jest pewne, ale$$\exists x (P(x)\implikuje Q(x))$$jest prawdziwe. Aby zobaczyć to Załóżmy, że $x_0$ jest jakimś konkretnym pomarańczowym. Następnie$P (x_0) \ implikuje Q (x_0)$ oblicza wartość do $\hbox{F} \ implikuje \hbox{T}$, czyli T, A kwantyfikator egzystencjalny jest spełniony.
używamy skrótów formy „niektóre”, podobnie jak te dla formy”wszystkie”.
przykład 1.2.7
$ \ bullet$ $ \ exists X
$ \ bullet$ $ \ exists x\in (2x^2+x =1)$ oznacza $ \ exists X ((x\in) \ land (2x^2+x=1))$$ \ square$
jeśli $ \ forall$ odpowiada „wszystkim”, a $\exists$ odpowiada”niektórym”, czy potrzebujemy trzeciego kwantyfikatora odpowiadającego”none”? Jak pokazano poniżej, nie jest to konieczne:
przykład 1.2.8
$ \ bullet$ „No democrats are republicans,” można napisać $\forall x$ ($x$ to demokrata $\implikuje$ $x$ nie jest Republikaninem).
$ \ bullet$ „żadne Trójkąty nie są prostokątami”, można zapisać $ \ forall x$ ($x$ jest trójkątem $ \ implikuje$ $ x$ nie jest prostokątem).
$ \ square$
ogólnie rzecz biorąc, stwierdzenie ” nie $x $ spełnia $P (x) $ spełnia $Q (x)$” można zapisać $$\forall x(P(x)\implikuje \lnot Q (x)).$$(Możesz się zastanawiać dlaczego nie używamy $\lnot \exists x\, (P(x)\land Q (x))$. W rzeczywistości moglibyśmy-jest to równoważne $ \ forall x(P(x)\implikuje \Lnot Q (x))$.)
ćwiczenia 1.2
w tych problemach Załóżmy, że wszechświat dyskursu jest liczbami.
Ex 1.2.1 wyrażają następujące formuły zawierające kwantyfikatory:
a) każda liczba podniesiona do czwartej potęgi jest nieujemna.
b) pewna liczba podniesiona do trzeciej potęgi jest ujemna.
c) sinus kąta jest zawsze pomiędzy $ + 1$ i $-1$.
d) sekant kąta nigdy nie jest ściśle pomiędzy $ + 1$ i $-1$.
Ex 1.2.2 Załóżmy, że $X$ i $Y$ są zestawami. Wyrażaj następujące wyrażenia jako formuły obejmujące kwantyfikatory.
a) każdy element $X$ jest elementem $Y$.
b) pewien element $X$ jest elementem $Y$.
c) jakiś element $X$ nie jest elementem $Y$.
d) żaden element $X$ nie jest elementem $Y$.
Ex 1.2.3 Przypomnij (z rachunku), że funkcja $f$ rośnie, jeśli$$ \forall a \forall b (a
A) $f$ maleje.
b) $f$ jest stała.
C) $f$ ma zero.
Ex 1.2.4 wyrażają następujące prawa symbolicznie:
a) prawo przemienne mnożenia
b) prawo asocjacyjne mnożenia
c) prawo rozdzielności
Ex 1.2.5 czy poniższe zdania są prawdziwe czy fałszywe?
a) $\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-2+2Z)$
Ex 1.2.6 Załóżmy, że $P (x)$ i $Q (y)$ są formułami.
a) czy $ \ forall x \forall y (P (x) \ implikuje Q (y)) $ odpowiada $\forall x(P(x)) \implikuje \forall y(Q (y))$?
b) czy $ \ exists x \exists y (P (x)\land Q (y)) $ odpowiada $\exists x(P(x)) \land \exists y(Q (y))$?