Kwantyfikator
Z Wikipedii
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 lub , 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 lub , rzadziej także symbolem (Ex).
Stosowany jest także kwantyfikator 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 . Np zdanie jest równoważne
-
- .
[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 , . 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:
- to skrót na
- to skrót na .
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),
- jest zdaniem prawdziwym, a
- jest zdaniem fałszywym.
Aby przekonać się o słuszności powyższego stwierdzenia, wystarczy zauważyć iż pierwsze zdanie oznacza
-
- .
Stwierdzenie "" jest zdaniem fałszywym (jakikolwiek by nie wziąć x), zatem implikacja jest prawdziwa dla wszystkich x.
Rozważając zdanie "" zauważamy, że oznacza ono
-
- .
Stwierdzenie "" jest zdaniem fałszywym (jakikolwiek by nie wziąć x), zatem koniunkcja jest fałszywa dla wszystkich x.
Równoważnie, kwantyfikatory ograniczone można wprowadzić następująco.
- Zdanie "" oznacza, że ,
- zdanie "" oznacza, że .
Jeśli , to oba zbiory i A są puste, a więc równe (bez względu na wybór formuły P(x). Czyli "" jest zawsze prawdziwe. Podobnie, "" 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:
- (b) są ludzie którzy nie znają a:
- (c) każdy zna każdego
- (d) pewna osoba nie zna nikogo (poza sobą samą):
- .
- (a) osoba a zna każdą osobe w grupie:
- W powyższych przykładach moglibyśmy użyć też kwantyfikatorów ograniczonych (pisząc 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 jest ciągła:
-
- .
- Jednak zmieniając kolejność podkreślonej pary kwantyfikatorów otrzymamy definicję o wiele silniejszej własności, tzw jednostajnej ciągłości:
- .
- W formie zdaniowej , x jest zmienną związaną, zaś y zmienną wolną. Natomiast w wyrażeniu 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:
- (Prawa De Morgana),
- ,
- ,
- ,
- ,
- .
[edytuj] Inne kwantyfikatory
Wprowadzone powyżej kwantyfikatory 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ść".
[edytuj] Zobacz też
- przegląd zagadnień z zakresu matematyki
- skolemizacja
- forma preneksowa
- kwantyfikator Magidora-Malitza
[edytuj] Linki zewnętrzne
http://www.romazur.republika.pl/logika-rachunek_kwantyfikatorow.html