Kwantyfikator

Kwantyfikator – termin przyjęty w matematyce i logice matematycznej na oznaczenie zwrotów: dla każdego, istnieje takie 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.

Kwantyfikator 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 x$ lub $\bigwedge_x$, 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 x$ 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)$.

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ą

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 elementu 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 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 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.

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ścią.) Używając kwantyfikatorów możemy teraz wyrazić następujące obserwacje:

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

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

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

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

(c) każdy zna każdego

$(\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.

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))$.

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ść".

W arytmetyce często używa się kwantyfikatorów ograniczonych, czyli takich, które przebiegają tylko pewne przedziały liczb zamiast wszystkich liczb. Wiele twierdzeń ze zwykłymi kwantyfikatorami da się przeformułować do postaci z kwantyfikatorami ograniczonymi, które są znacznie łatwiejsze do dowodzenia zarówno ręcznego jak i maszynowego.

Rozważa się także logiki inne niż klasyczna, np. logiki modalne lub logiki temporalne. W takich systemach istnieją dodatkowe kwantyfikatory wyrażające niestandardowe własności zmiennych.

Zobacz też

• skolemizacja
• forma preneksowa
• prawa rachunku kwantyfikatorów