Szukaj

narzędzia

W innych językach

Kwantyfikator

Kwantyfikator – termin przyjęty w matematyce i logice matematycznej na oznaczenie zwrotów: dla każdego, istnieje i im pokrewnych, a także odpowiadającym im symbolom wiążacym zmienne w formułach. Są podstawowym elementem w rozwoju logiki pierwszego rzędu.

Kwantyfikatory odgrywają ważną rolę w formułowaniu twierdzeń i definicji matematycznych.

Spis treści

[edytuj] Kwantyfikatory ogólny i szczegółowy

Zwrot dla każdego x nazywa się kwantyfikatorem ogólnym, kwantyfikatorem dużym lub kwantyfikatorem uniwersalnym wiążącym zmienną x. Kwantyfikator ogólny oznacza się symbolem $\forall$ lub $\bigwedge$ , sporadycznie można spotkać również symbol (x) użyty w tym kontekście.

Zwrot istnieje takie x, że... uważa się za równoważny zwrotowi: dla pewnego x i nazywa się kwantyfikatorem szczegółowym, kwantyfikatorem małym lub kwantyfikatorem egzystencjalnym wiążącym zmienną x. Kwantyfikator szczegółowy oznacza się symbolem $\exists$ lub $\bigvee_x$ , rzadziej także symbolem (Ex).

Stosowany jest także kwantyfikator $\exists ! x$ a wypowiedź w tym przypadku brzmi " istnieje dokładnie jeden x". Formuły używające tego kwantyfikatora można zredukować do formuł odwołujących się tylko do $\forall,\exists$ . Np zdanie $(\exists ! x) P(x)$ jest równoważne

$\Big(\exists x\Big)\Big(P(x)\ \wedge \big(\forall y\big)\big(P(y)\ \Rightarrow\ x=y\big)\Big)$ .

[edytuj] Zmienne związane

Zmienna występująca pod znakiem kwantyfikatora nazywa się zmienną związaną danym kwantyfikatorem. Natomiast zmienna występująca w wyrażeniu matematycznym, która nie jest związana żadnym kwantyfikatorem, nazywa się zmienną wolną. Wyrażenie następujące po kwantyfikatorze, objęte tym kwantyfikatorem, nazywa się zasięgiem kwantyfikatora.

Jeżeli w zasięgu kwantyfikatora znajdują się jakieś inne kwantyfikatory, to kwantyfikator początkowy wiąże tylko te zmienne, które nie są związane żadnym kwantyfikatorem zawartym w jego zasięgu. Stosując kwantyfikator do formy zdaniowej, otrzymuje się nową formę zdaniową lub zdanie. Działanie to, zwane kwantyfikowaniem, jest funkcją jednoargumentową określoną w zbiorze form zdaniowych, której wartościami są zdania lub formy zdaniowe.

Kwantyfikatory przekształcają formy zdaniowe jednej zmiennej w zdania prawdziwe lub fałszywe. Kwantyfikując formę zdaniową mającą więcej niż jedną zmienną wolną, otrzymuje się nową formę zdaniową

[edytuj] Kwantyfikatory ograniczone

Czasami używa się kwantyfikatorów w których zmienna jest ograniczona do jakiegoś zbioru, np $\forall x\in A$ , $\exists x\in A$ . Kwantyfikatory te nazywane są kwantyfikatorami ograniczonymi i czyta się je dla każdego element x ze zbioru A mamy że, istnieje element x w zbiorze A taki, że. Kwantyfikatory te są skrótami następujących zapisów:

$(\forall x\in A)P(x)$ to skrót na $\big(\forall x\big)\big(x\in A\ \Rightarrow\ P(x)\big)$
$(\exists x\in A)P(x)$ to skrót na $\big(\exists x\big)\big(x\in A\ \wedge\ P(x)\big)$ .

Zbiór A powyżej bywa nazywany dziedziną lub uniwersum kwantyfikatora. Należy zwrócić uwagę, że jeśli uniwersum kwantyfikatora jest puste, to wartość logiczna otrzymanego zdania nie zależy od formuły $P (x)$ . I tak, dla każdej formuły $P (x)$ (z jedną zmienną wolną x),

$\big (\forall x\in\emptyset\big)\big(P(x)\big)$ jest zdaniem prawdziwym, a
$\big (\exists x\in\emptyset\big)\big(P(x)\big)$ jest zdaniem fałszywym.

Aby przekonać się o słuszności powyższego stwierdzenia, wystarczy zauważyć iż pierwsze zdanie oznacza

$\big(\forall x\big)\big(x\in \emptyset\ \Rightarrow\ P(x)\big)$ .

Stwierdzenie " $x\in\emptyset$ " jest zdaniem fałszywym (jakikolwiek by nie wziąć x), zatem implikacja $x\in \emptyset\ \Rightarrow\ P(x)$ jest prawdziwa dla wszystkich x.

Rozważając zdanie " $\big (\exists x\in\emptyset\big)\big(P(x)\big)$ " zauważamy, że oznacza ono

$\big(\exists x\big)\big(x\in \emptyset\ \wedge\ P(x)\big)$ .

Stwierdzenie " $x\in\emptyset$ " jest zdaniem fałszywym (jakikolwiek by nie wziąć x), zatem koniunkcja $x\in \emptyset\ \wedge\ P(x)$ jest fałszywa dla wszystkich x.

Równoważnie, kwantyfikatory ograniczone można wprowadzić następująco.

Zdanie " $(\forall x\in A)P(x)$ " oznacza, że $\{x\in A:P(x)\}=A$ ,
zdanie " $(\exists x\in A)P(x)$ " oznacza, że $\{x\in A:P(x)\}\neq \emptyset$ .

Jeśli $A=\emptyset$ , to oba zbiory $\{x\in A:P(x)\}$ i $A$ są puste, a więc równe (bez względu na wybór formuły $P (x)$ . Czyli " $(\forall x\in \emptyset)P(x)$ " jest zawsze prawdziwe. Podobnie, " $(\exists x\in \emptyset)P(x)$ " jest fałszywe.

[edytuj] Przykłady

Przypuśćmy, że rozważamy grupę ludzi (zbiór A). W tej grupie pewne osoby znają inne osoby i możemy wprowadzić relację $Z (x, y)$ (na zbiorze A) wyrażającą stwierdzenie, że "osoba x zna osobę y". (Zauważmy, że z faktu iż x zna y wcale nie wynika, że y zna x - np y może być powszechnie znaną osobistościa.) Używając kwantyfikatorów możemy teraz wyrazić następujące obserwacje:

(a) osoba a zna każdą osobe w grupie:

$(\forall x)(Z({\bold a},x))$

(b) są ludzie którzy nie znają a:

$(\exists x)(\neg Z(x,{\bold a}))$

$(\forall x)(\forall y)(Z(x,y))$

(d) pewna osoba nie zna nikogo (poza sobą samą):

$(\exists x)(\forall y)(Z(x,y)\ \Rightarrow\ x=y)$ .

W powyższych przykładach moglibyśmy użyć też kwantyfikatorów ograniczonych (pisząc $\forall x\in A$ itd), nie jest to jednak konieczne gdyż domniemana dziedzina realcji Z to właśnie zbiór A.

Kolejność kwantyfikatorów może mieć znaczenie. Możemy zamienić kolejność kwantyfikatorów tego samego typu, np poniższe dwie formuły są równoważnymi sformułowaniami stwierdzenia, że funkcja $f:{\mathbb R}\longrightarrow{\mathbb R}$ jest ciągła:

$\underbrace{(\forall x\in\mathbb{R})(\forall\epsilon>0)}(\exists\delta>0)(\forall h\in\mathbb{R})(|h|<\delta \ \Rightarrow\ |f(x) - f(x+h)|<\epsilon)$
$(\forall \epsilon>0)\underbrace{(\forall x \in \mathbb{R})(\exists \delta > 0)}(\forall h \in \mathbb{R})(|h|<\delta\ \Rightarrow\ |f(x) - f(x+h)|<\epsilon)$ .

Jednak zmieniając kolejność podkreślonej pary kwantyfikatorów $\forall/\exists$ otrzymamy definicję o wiele silniejszej własności, tzw jednostajnej ciągłości:

$(\forall \epsilon >0)\underbrace{(\exists \delta > 0)(\forall x \in \mathbb{R})}(\forall h \in \mathbb{R})(|h|<\delta\ \Rightarrow\ |f(x) - f(x+h)|<\epsilon)$ .

W formie zdaniowej $(\exists x)(x - y = 1)$ , x jest zmienną związaną, zaś y zmienną wolną. Natomiast w wyrażeniu $(\forall x)(\exists y)(x>y)$ obie zmienne są związane.

[edytuj] Podstawowe własności logiczne

Niech $R (x), S (x), T (x, y)$ będą formułami albo predykatami w pewnym języku. Następujące zdania są tautologiami logicznymi:

$\neg (\forall x)(R(x))\ \Leftrightarrow\ (\exists x)(\neg R(x))$ (Prawa De Morgana),
$(\forall x)(R(x))\ \Rightarrow\ (\exists x)(R(x))$ ,
$(\forall x)(R(x)\ \wedge\ S(x))\ \Leftrightarrow\ [(\forall x)(R(x))\ \wedge (\forall x)(S(x))]$ ,
$[(\forall x)(R(x))\ \vee (\forall x)(S(x))]\ \Rightarrow\ (\forall x)(R(x)\ \vee\ S(x))$ ,
$(\exists x)(\forall y)(T(x,y))\ \Rightarrow\ (\forall y)(\exists x)(T(x,y))$ ,
$(\forall x)(\forall y)(T(x,y))\ \Leftrightarrow\ (\forall y)(\forall x)(T(x,y))$ .

[edytuj] Inne kwantyfikatory

Wprowadzone powyżej kwantyfikatory $\forall,\exists$ nie są jedynymi spotykanymi w matematyce. Czasami rozważa się kwantyfikatory po predykatach (kwantyfikatory drugiego rzędu), kwantyfikatory po specjalnych obiektach czy też kwantyfikatory stwierdzające, że "istnieje dużo obiektów o pewnej własności" albo że "prawie wszystkie obiekty mają pewną własność".