Zwroty "dla każdego x", "istnieje takie x, że" nazywa się kwantyfikatorami. Pozwalają one budować nowe predykaty (nowe funkcje zdaniowe) z już istniejących. Niech α(x) oznacza funkcję zdaniową, w której występuje tylko jedna zmienna x.

Zwroty "dla każdego x, α(x)", "dla wszystkich x, α(x)", "dla dowolnego x, α(x)" wszystkie oznaczają zdanie prawdziwe, jeżeli niezależnie od tego jaka konkretna wartość a zostanie wstawiona na miejsce zmiennej w predykacie α(x), otrzymane zdanie α(a/x) będzie prawdziwe, tzn. wszystkie możliwe wartości zmiennej x spełniają funkcję zdaniową α(x).

W logice i w matematyce przyjęło się oznaczać kwantyfikator "dla każdego x" symbolem odwróconego A, tzn. ( ∀x). Kwantyfikator ten nazywamy ogólnym lub uniwersalnym.

Przykładami funkcji zdaniowych z użyciem kwantyfikatora ogólnego są wyrażenia:

( ∀x) (x<0), ( ∀x) ((x-3 = 0) ∨ (x+1 < 4)) → (x< 1), (( ∀x)(x> 0) ∨( ∀y) ((y < 4) → (y < 1))).

Zwrot "istnieje takie x, że" (czasami używany w formie "dla pewnego x, ") nazywa się kwantyfikatorem szczegółowym lub egzystencjalnym. Dla oznaczenia tego kwantyfikatora używa się odwróconej litery E, tzn. piszemy ( ∃x). Rozumiemy, że funkcja zdaniowa α(x) poprzedzona tym kwantyfikatorem tworzy zdanie prawdziwe, jeśli istnieje pewien obiekt a, który wstawiony w miejsce zmiennej w predykacie α(x) spowoduje, że otrzymamy zdanie prawdziwe α(a/x). Na przykład, wyrażenie (x-3 = 0) jest funkcją zdaniową określoną w zbiorze liczb rzeczywistych. Natomiast ( ∃x) (x-3 = 0) jest zdaniem prawdziwym, które stwierdza, że istnieje taka liczba rzeczywista a, dla której a-3 = 0.

Pytanie 8.3.1 Niech Z(x) oznacza predykat "student x zda egzamin" określony dla zbioru studentów PJWSTK. Jak zapisać zdanie "każdy student albo zda albo nie zda egzaminu" przy użyciu kwantyfikatorów i predykatu Z(x)?

Przykład 8.3.1

(1) W formule (( ∀x) ((x>0) ∨ (x ≤ 0)) ∧ ( ∃x) (x² ≤0)), zmienna x występująca w wyrażeniu ((x>0) ∨ (x ≤0)) jest związana przez kwantyfikator uniwersalny ( ∀x), a zmienna x występująca w wyrażeniu (x² ≤0), jest związana przez kwantyfikator szczegółowy ( ∃x). Zakresem kwantyfikatora uniwersalnego jest funkcja zdaniowa ((x>0) ∨ (x ≤ 0)), a zakresem kwantyfikatora szczegółowego jest funkcja zdaniowa (x² ≤ 0).

(2) W funkcji zdaniowej ((( ∀x)(x>0) ∨ (x ≤ 0)) ∧ ( ∃x) (x² ≤ 0)), która różni się od rozważanej poprzednio jedynie ustawieniem nawiasów, zmienna x występująca w wyrażeniu (x>0) jest nadal związana przez kwantyfikator uniwersalny ( ∀x). Natomiast wystąpienie zmiennej x w wyrażeniu (x ≤ 0) nie jest związane żadnym kwantyfikatorem. To wystąpienie zmiennej x jest wolne, bo nie znajduje się w zakresie żadnego kwantyfikatora. Zakresem kwantyfikatora uniwersalnego ( ∀x) jest teraz funkcja zdaniowa (x>0).

Uwaga Jeśli w funkcji zdaniowej α(x) występuje tylko jedna zmienna wolna x, to wyrażenia ( ∃x) α(x), ( ∀x) α(x) są zdaniami.

Do tej pory, nasze przykłady funkcji zdaniowych z kwantyfikatorami były bardzo proste dzięki temu, że występowała w nich tylko jedna zmienna wolna. Oczywiście nie jest to obowiązująca reguła: w funkcjach zdaniowych może występować wiele różnych zmiennych.

Niech α(x,x₁,x₂,...x_n) będzie funkcją zdaniową o zmiennych wolnych x, x₁, x₂,..., x_n. Dopisując symbol kwantyfikatora wiążemy wymienioną zmienną i tylko tę zmienną. ( ∃x) α(x, x₁, x₂, ...x_n ) oraz ( ∀x) α(x, x₁, x₂,...x_n ) są funkcjami zdaniowymi o zmiennych wolnych x₁, x₂, ..., x_n, natomiast zmienna x jest w tych funkcjach zdaniowych zmienną związaną.

W dalszym ciągu będziemy wymieniali tylko te zmienne wolne, które będą istotne ze względu na prowadzone rozważania. Na przykład, pisząc α(x) chcemy zaznaczyć, że istotną dla nas zmienną wolną w funkcji zdaniowej α(x) jest x. Być może wyrażenie α posiada jeszcze inne zmienne wolne, ale w tej chwili nie są one dla nas istotne i wobec tego nie wymieniamy ich.

Przykład 8.3.2

1. Rozważmy funkcję zdaniową ( ∀x) ( ∃y) (x+y<6 ∨ x*y<0) określoną w zbiorze liczb rzeczywistych. Obie występujące w niej zmienne x i y są związane przez kwantyfikatory. Funkcja zdaniowa (x+y<6 ∨ x*y<0) jest zakresem kwantyfikatora egzystencjalnego ( ∃y), natomiast funkcja zdaniowa ( ∃y) (x+y<6 ∨ x*y<0) jest zakresem kwantyfikatora uniwersalnego( ∀x).
2. W funkcji zdaniowej ( ∃x) (x+z<6 ∧ ( ∀y) ( x*y>0)), zmienna x (występująca dwukrotnie) jest związana przez kwantyfikator egzystencjalny ( ∃x). Zakresem tego kwantyfikatora jest funkcja zdaniowa (x+z<6 ∧ ( ∀y) ( x*y>0)). Zmienna y, występująca w drugiej części wyrażenia, jest związana przez kwantyfikator uniwersalny ( ∀y). Zakresem tego kwantyfikatora jest funkcja zdaniowa (x*y>0). Zmienna z, nie jest związana przez żaden kwantyfikator i jest to jedyna zmienna wolna w tej funkcji zdaniowej.

Pytanie 8.3.2 Ile jest zmiennych wolnych w pierwszej, a ile w drugiej formule?

1. ( ∃ x) ( ∃ y)((x*y >0) ∧ (y<0))

2. (( ∃ x) (x*y>0) ∧ ( ∃ y) (y<0))

Niech α(x) będzie funkcją zdaniową określoną w zbiorze X, z jedną tylko zmienną wolną x. Przyjmujemy następującą definicję spełniania dla funkcji zdaniowych

Bezpośrednią konsekwencją tej definicji jest następujący wniosek: Dla dowolnego predykatu α(x) określonego w zbiorze X,

- ( ∀ x) α(x) jest zdaniem fałszywym w X (tzn. ma wartość 0) wttw {x ∈ X: α(x)} ≠ X,

- ( ∃ x) α(x) jest zdaniem fałszywym w X (tzn. ma wartość 0) wttw {x ∈ X: α(x)} = ∅.

Przykład 8.3.3

1. Rozważmy funkcję zdaniową (x+2)*(x-3)<0 w zbiorze liczb rzeczywistych R. Ponieważ liczba 2 spełnia tę funkcję, a liczba 3 nie spełnia tej funkcji, to

   ( ∃x) ((x+2)*(x-3)<0) jest zdaniem prawdziwym w R, a

   ( ∀x) ( (x+2)*(x-3)<0) jest zdaniem fałszywym w R.

2. Funkcja zdaniowa (A ⊆ B → (A ∪ C) ⊆ (B ∪ C)) określona w zbiorze podzbiorów pewnego zbioru X jest spełniona dla wszystkich A, B i C. Zatem

   ( ∀ A)( ∀ B) ( ∀C)(A ⊆ B → (A ∪ C) ⊆ (B ∪ C))

   jest zdaniem prawdziwym w zbiorze potęgowym P(X).

Przykład 8.3.4

1. Rozważmy funkcję zdaniową ( ∀x) ( ∃y) (x+y<6 ∨ x*y<0). Funkcja ta reprezentuje w zbiorze liczb rzeczywistych zdanie prawdziwe. Jeśli natomiast będziemy to samo wyrażenie rozważali w zbiorze liczb naturalnych, to nie jest to zdanie prawdziwe: nie dla wszystkich liczb naturalnych będących wartościami zmiennej x (np. dla 6) potrafimy znaleźć taką liczbę naturalną, która wstawiona w miejsce y spełni funkcję zdaniową (x+y<6 ∨ x*y<0).
2. Jeśli potraktujmy wyrażenie ( ∃x) (x+z<6 ∧ ( ∃y) ( x*y>0)) jako funkcję zdaniową określoną w zbiorze liczb rzeczywistych, to przyjmując jako wartość zmiennej wolnej z liczbę 6 (z=6), otrzymamy zdanie prawdziwe, bo istnieje liczba rzeczywista a (np. a=-1), taka że a+6<6 oraz istnieje taka liczba rzeczywista b (np. b=1), taka że a*b<0. W zbiorze liczb rzeczywistych rozważana funkcja zdaniowa jest więc spełniona przez liczbę 6. Co więcej, funkcja zdaniowa jest zdaniem prawdziwym w zbiorze liczb rzeczywistych. Jeśli to samo wyrażenie ( ∃x)(x+z<6 ∧ ( ∃y)( x*y>0)) potraktujemy jako funkcję zdaniową w zbiorze liczb naturalnych, to dla pewnych wartości z (np. z=6) wartością wyrażenia jest fałsz. Zatem nie wszystkie liczby naturalne spełniają tę funkcję zdaniową.

Zauważmy, że nazwa zmiennej w wyrażeniu z kwantyfikatorem ( ∀x) α(x) lub ( ∃x) α(x) nie ma znaczenia: wszystko jedno, czy napiszemy ( ∃x) (x-3<0), czy ( ∃y) (y-3<0), czy też ( ∃z) (z-3<0). Wszystkie te zdania w dowolnym zbiorze albo są prawdziwe, tzn. jest taki obiekt a, że a-3<0, albo wszystkie są fałszywe, bo nie ma takiego obiektu.

Pytanie 8.3.3 Czy wartość funkcji zdaniowej określonej w zbiorze X zależy od wartości występujących w niej zmiennych związanych?

Jeśli A jest skończonym zbiorem o elementach a₁, a₂,..., a_n, a α(x) jest funkcją zdaniową określoną w zbiorze A, to prawdziwa jest następująca równoważność

( ∃x) α(x) ↔ ( α(a₁/x) ∨ α(a₂/x) ∨ ... ∨ α(a_n/x)).

Rzeczywiście, zdanie ( ∃ x) α(x) ma wartość 1 w zbiorze A wtedy i tylko wtedy, gdy chociaż jeden element zbioru A spełnia funkcję zdaniową α(x), tzn. wtedy i tylko wtedy, gdy spełniona jest alternatywa ( α(a₁/x) ∨ α(a₂/x) ∨ ... ∨ α(a_n/x)). Kwantyfikator szczegółowy jest więc uogólnieniem spójnika logicznego alternatywy.

Analogicznie rozważmy kwantyfikator ogólny. Jeśli A = {a₁, a₂, ... a_n}, a α(x) jest funkcją zdaniową określoną w zbiorze A, to prawdziwa jest następująca równoważność

( ∀x) α(x) ↔ ( α(a₁/x) ∧ α(a₂/x) ∧ ... ∧ α(a_n/x)).

Zdanie ( ∀x) α(x) ma wartość 1 w zbiorze A wtedy i tylko wtedy, gdy wszystkie elementy zbioru A spełniają funkcję zdaniową α(x), tzn. wtedy i tylko wtedy, gdy koniunkcja ( α(a₁/x) ∧ α(a₂/x) ∧ ... ∧ α(a_n/x) ) jest zdaniem prawdziwym. Kwantyfikator ogólny można więc uważać za uogólnienie operatora koniunkcji.

Związek działań uogólnionych z kwantyfikatorami jest dość oczywisty, gdy przypomnimy sobie ich definicje (por. 1.6). Jeśli A={A_i}_{i ∈ I} jest indeksowaną rodziną podzbiorów pewnej przestrzeni X, to

Inaczej mówiąc

oraz

Do zdefiniowania działań uogólnionych użyliśmy kwantyfikatorów. Odwrotnie, aby wyjaśnić spełnianie funkcji zdaniowych z kwantyfikatorami, użyjemy działań uogólnionych.

Powyższy lemat stwierdza, że ogół wartości x, które spełniają funkcję zdaniową ( ∃y) α(x,y) jest sumą wszystkich zbiorów X_b = {x ∈ X: α(x,b/y)} dla b ∈ Y. Natomiast przecięcie wszystkich zbiorów X_b daje te wartości zmiennej x, które spełniają funkcję zdaniową ( ∀y) α(x,y).

Przykład 8.3.5

1. Rozważmy funkcję zdaniową ((0 < n) ∧ (0 ≤ x*n ≤ 1)) dwóch zmiennych x, n przebiegających zbiór liczb rzeczywistych i zbiór liczb naturalnych odpowiednio. Zbiór tych liczb rzeczywistych, które spełniają funkcję zdaniową ( ∀n) ((0 < n) ∧ (0 ≤ x*n ≤ 1)) jest przecięciem teoriomnogościowym wszystkich zbiorów postaci {x ∈R : 0 ≤x ≤ 1/n} dla wszystkich liczb naturalnych n>0. Jest to więc zbiór jednoelementowy {0}.

   {x ∈ R : ( ∀n ∈ N⁺)((0 < n) ∧ (0 ≤ x*n ≤ 1)) } = ⎧⎫ _{n ∈ N+}{x ∈ R : ((0 < n) ∧ (0 ≤ x*n ≤ 1)) }=

   = ⎧⎫ _{n ∈ N+}{ x ∈ R : 0 ≤ x ≤ 1/n}= {0}.

   Jedyną wartością, która spełnia funkcję zdaniową ( ∀n) ((0 < n) ∧ (x*n ≤ 1)) jest liczba rzeczywista 0.

2. Zbiór tych liczb rzeczywistych, które spełniają funkcję zdaniową ( ∃n) ((0 < n) ∧ (0 ≤ x*n ≤ 1)) jest sumą teoriomnogościową wszystkich zbiorów postaci {x ∈ R : 0 ≤ x ≤ 1/n} dla liczb naturalnych n>0. Jest to więc przedział domknięty [0,1].

   {x ∈ R: ( ∃n ∈ N⁺)((0 < n) ∧ (0 ≤ x*n ≤ 1)) } = ⎩⎭ _{n ∈ N+}{x ∈ R: ((0 < n) ∧ (0 ≤ x*n ≤ 1))}=

   ⎩⎭ _{n ∈ N+}{x ∈ R: 0 ≤ x ≤ 1/n}= [0, 1].

   Wszystkie liczby rzeczywiste z przedziału [0,1] spełniają rozważaną funkcję zdaniową.

Tworząc funkcje zdaniowe z kwantyfikatorami często zastrzegamy pewne warunki, które ograniczają wartości zmiennych występujących w formule, w szczególności tych zmiennych, które są związane przez kwantyfikatory. Rozważmy zdanie:

Chociaż w tym zdaniu występuje słowo" każdy", a więc kwantyfikator ogólny, to zdanie to nie dotyczy wszystkich osób, a tylko tych osób które ukończyły 18 lat. Mówimy, że kwantyfikator ogólny jest w tym przypadku ograniczony, przez pewien warunek dotyczący możliwych wartości zmiennej "osoba".

Kwantyfikator ogólny o zakresie ograniczonym przez funkcje zdaniową β(x) zapisujemy w postaci

Wyrażenie to oznacza, że będziemy rozważali nie wszystkie elementy ustalonej dziedziny, a tylko te spełniające warunek β(x). Podobnie jak przy zwykłych kwantyfikatorach, użycie kwantyfikatora ( ∀ β(x)) wiąże zmienną wolną x występującą w formule, przed którą stoi kwantyfikator. W formule ( ∀ β(x)) α(x), α(x) jest zakresem kwantyfikatora ogólnego, a x jest zmienną związaną przez ten kwantyfikator.

Analogicznie, kwantyfikator szczegółowy o zakresie ograniczonym przez funkcję zdaniową β(x) zapisujemy w postaci

W formułach rachunku predykatów używamy tego kwantyfikatora podobnie jak zwykłego kwantyfikatora szczegółowego: piszemy ( ∃ β(x)) α(x) i czytamy 'istnieje takie x spełniające β(x), że α(x). Oznacza to, że w rozważanej dziedzinie nie poszukujemy dowolnej wartości, która spełnia α(x), ale takiej wartości dla x, która dodatkowo spełnia warunek β(x). Zakresem kwantyfikatora egzystencjalnego w wyrażeniu ( ∃ β(x)) α(x) jest formuła α(x), a zmienna x jest zmienną związaną przez ten kwantyfikator.

Kwantyfikatory o zakresie ograniczonym przez funkcję zdaniową nie są niezbędne. Własności, które są wyrażone przez te kwantyfikatory, równie dobrze możemy opisać zwykłymi kwantyfikatorami. Wyjaśnia to lemat 7.3. Korzyści płynące z użycia kwantyfikatorów o zakresie ograniczonym staną się oczywiste, gdy przyjrzymy się przykładowi 7.9. Własność zapisana z użyciem kwantyfikatorów o zakresie ograniczonym jest często o wiele bardziej czytelna (i krótsza), niż zapisana przy użyciu zwykłych kwantyfikatorów.

Lemat 8.3.2 stwierdza, że jeśli jest prawdziwa funkcja zdaniowa ( ∀ β(x)) α(x), to jest również prawdziwa funkcja zdaniowa ( ∀x) ( β(x) → α(x)) i odwrotnie. Analogicznie, w drugiej części lemat 8.3.2 stwierdza, że funkcja zdaniowa ( ∃ β(x)) α(x) ma zawsze taką samą wartość logiczną jak funkcja zdaniowa ( ∃x) ( β(x) ∧ α(x)).

Przykład 8.3.6

1. Warunek Cauchy'ego mówi, że ciąg liczb rzeczywistych (a_n) jest zbieżny do liczby a wttw dla każdego ε>0 istnieje liczba naturalna n₀ taka, że dla każdego n>n₀, |a_n -a | < ε.

   Zapiszmy tę definicję najpierw z użyciem kwantyfikatorów, a potem z użyciem kwantyfikatorów o zakresie ograniczonym:

   lim_{n → ∞} a_n = a wttw ( ∀ ε)( ε > 0 → ( ∃ n₀)(n₀ ∈ N ∧ ( ∀ n)(n>n₀ → |a_n -a | < ε)))

   lim_{n → ∞} a_n = a wttw ( ∀ ε > 0) ( ∃ n₀ ∈ N) ( ∀ n>n₀) |a_n -a | < ε.

2. Zasada indukcji matematycznej (por. wykład IX) głosi, że dla dowolnego podzbioru liczb naturalnych, jeżeli 1. liczba 0 należy do A i 2. z tego że jakaś liczba naturalna i należy do podzbioru wynika, że następna liczba naturalna należy też do tego podzbioru, to wszystkie liczby naturalne należą do tego podzbioru. Zasada indukcji może być zapisana z użyciem kwantyfikatorów ograniczonych przez funkcję zdaniową następująco

   ( ∀ A ⊆ N ) (0 ∈ A ∧ ( ∀ i ∈N) (i ∈ A → i+1 ∈ A)) → ( ∀ n ∈ N)(n ∈ A).

Pytanie 8.3.4 Niech C(x) oznacza, że kolor x jest czerwony, K(x) oznacza, że x jest kurą, Z(x) oznacza, że x znosi złote jajka. Jak zapisać przy użyciu kwantyfikatorów o zakresie ograniczonym i podanych predykatów elementarnych następujące zdania?

1. Wszystkie kury, jeśli tylko są czerwone, to znoszą złote jajka.
2. Istnieją kury, które chociaż są czerwone, nie znoszą złotych jajek.

Zobacz odpowiedź

« poprzedni punkt

następny punkt »