Zmienna wolna


Kwantyfikator w encyklopedii

Z Wikipedii, wolnej encyklopedii (Przekierowano z Zmienna wolna) Przejdź do nawigacji Przejdź do wyszukiwania

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ążącym 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

Kwantyfikator ogólny i szczegółowy | edytuj kod

 Osobne artykuły: Kwantyfikator ogólnyKwantyfikator egzystencjalny.

Zwrot dla każdego x nazywa się kwantyfikatorem ogólnym, kwantyfikatorem dużym lub kwantyfikatorem uniwersalnym wiążącym zmienną x . {\displaystyle x.} Kwantyfikator ogólny oznacza się symbolem x {\displaystyle \forall x} lub x , {\displaystyle \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 . {\displaystyle x.} Kwantyfikator szczegółowy oznacza się symbolem x {\displaystyle \exists x} lub x , {\displaystyle \bigvee _{x},} rzadziej także symbolem (Ex).

Stosowany jest także kwantyfikator ! x {\displaystyle \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 , . {\displaystyle \forall ,\exists .} Np zdanie ( ! x ) P ( x ) {\displaystyle (\exists !x)P(x)} jest równoważne

( x ) ( P ( x )   ( y ) ( P ( y )     x = y ) ) . {\displaystyle {\Big (}\exists x{\Big )}{\Big (}P(x)\ \wedge {\big (}\forall y{\big )}{\big (}P(y)\ \Rightarrow \ x=y{\big )}{\Big )}.}

Zmienne związane | edytuj kod

Zmienna występująca przy znaku 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, ani nie ma wartości ustalonej we wcześniejszym rozumowaniu, nazywa się zmienną wolną. Wyrażenie następujące po kwantyfikatorze, objęte tym kwantyfikatorem, nazywa się zasięgiem kwantyfikatora.

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 | edytuj kod

Czasami używa się kwantyfikatorów w których zmienna jest ograniczona do jakiegoś zbioru, np x A , {\displaystyle \forall x\in A,} x A . {\displaystyle \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:

  • ( x A ) P ( x ) {\displaystyle (\forall x\in A)P(x)} to skrót na ( x ) ( x A     P ( x ) ) , {\displaystyle {\big (}\forall x{\big )}{\big (}x\in A\ \Rightarrow \ P(x){\big )},}
  • ( x A ) P ( x ) {\displaystyle (\exists x\in A)P(x)} to skrót na ( x ) ( x A     P ( x ) ) . {\displaystyle {\big (}\exists x{\big )}{\big (}x\in A\ \wedge \ P(x){\big )}.}

Zbiór A {\displaystyle 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 ) . {\displaystyle P(x).} I tak, dla każdej formuły P ( x ) {\displaystyle P(x)} (z jedną zmienną wolną x {\displaystyle x} ),

  • ( x ) ( P ( x ) ) {\displaystyle {\big (}\forall x\in \emptyset {\big )}{\big (}P(x){\big )}} jest zdaniem prawdziwym, a
  • ( x ) ( P ( x ) ) {\displaystyle {\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

( x ) ( x     P ( x ) ) . {\displaystyle {\big (}\forall x{\big )}{\big (}x\in \emptyset \ \Rightarrow \ P(x){\big )}.}

Stwierdzenie „ x {\displaystyle x\in \emptyset } ” jest zdaniem fałszywym (jakikolwiek wziąć x {\displaystyle x} ), zatem implikacja x     P ( x ) {\displaystyle x\in \emptyset \ \Rightarrow \ P(x)} jest prawdziwa dla wszystkich x . {\displaystyle x.}

Rozważając zdanie „ ( x ) ( P ( x ) ) {\displaystyle {\big (}\exists x\in \emptyset {\big )}{\big (}P(x){\big )}} ”, zauważamy, że oznacza ono

( x ) ( x     P ( x ) ) . {\displaystyle {\big (}\exists x{\big )}{\big (}x\in \emptyset \ \wedge \ P(x){\big )}.}

Stwierdzenie „ x {\displaystyle x\in \emptyset } ” jest zdaniem fałszywym (jakikolwiek wziąć x {\displaystyle x} ), zatem koniunkcja x     P ( x ) {\displaystyle x\in \emptyset \ \wedge \ P(x)} jest fałszywa dla wszystkich x . {\displaystyle x.}

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

  • Zdanie „ ( x A ) P ( x ) {\displaystyle (\forall x\in A)P(x)} ” oznacza, że { x A : P ( x ) } = A , {\displaystyle \{x\in A\colon P(x)\}=A,}
  • zdanie „ ( x A ) P ( x ) {\displaystyle (\exists x\in A)P(x)} ” oznacza, że { x A : P ( x ) } . {\displaystyle \{x\in A\colon P(x)\}\neq \emptyset .}

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

Przykłady | edytuj kod

  • Przypuśćmy, że rozważamy grupę ludzi (zbiór A {\displaystyle A} ). W tej grupie pewne osoby znają inne osoby i możemy wprowadzić relację Z ( x , y ) {\displaystyle Z(x,y)} (na zbiorze A {\displaystyle A} ) wyrażającą stwierdzenie, że „osoba x {\displaystyle x} zna osobę y {\displaystyle y} ”. (Zauważmy, że z faktu iż x {\displaystyle x} zna y {\displaystyle y} wcale nie wynika, że y {\displaystyle y} zna x {\displaystyle x} – np y {\displaystyle 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: ( x ) ( Z ( a , x ) ) , {\displaystyle (\forall x)(Z(\mathbf {a} ,x)),} (b) są ludzie którzy nie znają a: ( x ) ( ¬ Z ( x , a ) ) , {\displaystyle (\exists x)(\neg Z(x,\mathbf {a} )),} (c) każdy zna każdego ( x ) ( y ) ( Z ( x , y ) ) , {\displaystyle (\forall x)(\forall y)(Z(x,y)),} (d) pewna osoba nie zna nikogo (poza sobą samą): ( x ) ( y ) ( Z ( x , y )     x = y ) . {\displaystyle (\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 x A {\displaystyle \forall x\in A} itd.), nie jest to jednak konieczne, gdyż domniemana dziedzina relacji Z {\displaystyle Z} to właśnie zbiór A . {\displaystyle 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 : R R {\displaystyle f\colon {\mathbb {R} }\longrightarrow {\mathbb {R} }} jest ciągła:
( x R ) ( ϵ > 0 ) ( δ > 0 ) ( h R ) ( | h | < δ     | f ( x ) f ( x + h ) | < ϵ ) , {\displaystyle \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 ),} ( ϵ > 0 ) ( x R ) ( δ > 0 ) ( h R ) ( | h | < δ     | f ( x ) f ( x + h ) | < ϵ ) . {\displaystyle (\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 / , {\displaystyle \forall /\exists ,} otrzymamy definicję o wiele silniejszej własności, tzw. jednostajnej ciągłości: ( ϵ > 0 ) ( δ > 0 ) ( x R ) ( h R ) ( | h | < δ     | f ( x ) f ( x + h ) | < ϵ ) . {\displaystyle (\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 ( x ) ( x y = 1 ) , {\displaystyle (\exists x)(x-y=1),} x {\displaystyle x} jest zmienną związaną, zaś y {\displaystyle y} zmienną wolną. Natomiast w wyrażeniu ( x ) ( y ) ( x > y ) {\displaystyle (\forall x)(\exists y)(x>y)} obie zmienne są związane.

Podstawowe własności logiczne | edytuj kod

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

  • ¬ ( x ) ( R ( x ) )     ( x ) ( ¬ R ( x ) ) {\displaystyle \neg (\forall x)(R(x))\ \Leftrightarrow \ (\exists x)(\neg R(x))} (prawa De Morgana),
  • ( x ) ( R ( x ) )     ( x ) ( R ( x ) ) , {\displaystyle (\forall x)(R(x))\ \Rightarrow \ (\exists x)(R(x)),} o ile dziedzina formy zdaniowej R {\displaystyle R} jest niepusta,
  • ( x ) ( R ( x )     S ( x ) )     ( x ) ( R ( x ) )   ( x ) ( S ( x ) ) , {\displaystyle (\forall x)(R(x)\ \wedge \ S(x))\ \Leftrightarrow \ [(\forall x)(R(x))\ \wedge (\forall x)(S(x))],}
  • ( x ) ( R ( x ) )   ( x ) ( S ( x ) )     ( x ) ( R ( x )     S ( x ) ) , {\displaystyle [(\forall x)(R(x))\ \vee (\forall x)(S(x))]\ \Rightarrow \ (\forall x)(R(x)\ \vee \ S(x)),}
  • ( x ) ( y ) ( T ( x , y ) )     ( y ) ( x ) ( T ( x , y ) ) , {\displaystyle (\exists x)(\forall y)(T(x,y))\ \Rightarrow \ (\forall y)(\exists x)(T(x,y)),}
  • ( x ) ( y ) ( T ( x , y ) )     ( y ) ( x ) ( T ( x , y ) ) . {\displaystyle (\forall x)(\forall y)(T(x,y))\ \Leftrightarrow \ (\forall y)(\forall x)(T(x,y)).}
  • ( x ) ( y ) ( T ( x , y ) )     ( y ) ( x ) ( T ( x , y ) ) . {\displaystyle (\exists x)(\exists y)(T(x,y))\ \Leftrightarrow \ (\exists y)(\exists x)(T(x,y)).}

Inne kwantyfikatory | edytuj kod

Wprowadzone powyżej kwantyfikatory , {\displaystyle \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ż | edytuj kod

Linki zewnętrzne | edytuj kod

Artykuły na Stanford Encyclopedia of Philosophy (ang.) [dostęp 2018-08-07]:

Na podstawie artykułu: "Zmienna wolna" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy