Przejdź do treści
Strona główna

Kwantyfikatory w logice: definicja, symbole ∀ i ∃ oraz przykłady

Poznaj kwantyfikatory w logice: definicje, symbole ∀ i ∃, praktyczne przykłady i zastosowania w językach formalnych i naturalnych — klarowne wyjaśnienia dla studentów i programistów.

Autor: Utworzono: Zaktualizowano:

W logice kwantyfikator to sposób na stwierdzenie, że pewna liczba elementów spełnia określone kryteria. Na przykład zdanie „każda liczba naturalna ma inną liczbę naturalną większą od niej” wykorzystuje słowo „każda” jako kwantyfikator. Takie zdania nazywamy wyrażeniami kwantyfikowanymi. Kwantyfikatory są podstawowym narzędziem logiki predykatów, ponieważ pozwalają precyzyjnie określić, jak szerokie jest badane kryterium.

Galeria obrazów

2 Obrazy
File:De_Morgan_Augustus.jpg
en.wikipedia.org · Public domain

Rodzaje i symbole

Dwa podstawowe rodzaje kwantyfikatorów to kwantyfikator uniwersalny i egzystencjalny. Kwantyfikator uniwersalny stwierdza, że wszystkie rozważane elementy spełniają warunek. Kwantyfikator uniwersalny jest symbolizowany przez ∀ — często wymawiany jako „dla wszystkich”. Kwantyfikator uniwersalny można zapisać formalnie jako ∀x P(x), co czytamy: „dla każdego x zachodzi P(x)”. Kwantyfikator egzystencjalny (symbolizowany przez ∃) stwierdza, że co najmniej jeden rozważany element spełnia warunek, zapisujemy to jako ∃x P(x): „istnieje x takie, że P(x)”. Kwantyfikator egzystencjalny jest symbolizowany przez "∃", odwrócone "E", oznaczające "istnieje".

Domena dyskursu i składnia

Ważne jest sprecyzowanie domeny dyskursu (zbioru rozważanych obiektów). Bez określenia domeny formuła ∀x P(x) jest niepełna: czy x ma biec po liczbach rzeczywistych, naturalnych, osobach, macierzach? W praktyce często zapisuje się kwantyfikatory wraz z ograniczeniem, np. ∀x ∈ A P(x) lub ∃x ∈ A P(x), co oznacza „dla każdego x z A” lub „istnieje x z A”.

Przykłady formalne

  • Każda liczba naturalna ma większą liczbę naturalną: ∀n ∈ ℕ ∃m ∈ ℕ (m > n).
  • Istnieje liczba parzysta większa od 2: ∃n ∈ ℕ (n > 2 ∧ n mod 2 = 0).
  • Wszystkie koty mają ogon (hipotetyczne): ∀x (Kot(x) → MaOgon(x)).

Negacje i prawa De Morgana dla kwantyfikatorów

Negacja zmienia typ kwantyfikatora:

  • ¬(∀x P(x)) ≡ ∃x ¬P(x) — zaprzeczenie „dla każdego” brzmi: „istnieje przynajmniej jeden, dla którego nie zachodzi P”.
  • ¬(∃x P(x)) ≡ ∀x ¬P(x) — zaprzeczenie „istnieje” brzmi: „dla każdego nie zachodzi P”.

Kolejność kwantyfikatorów

Kolejność kwantyfikatorów ma zasadnicze znaczenie. Na przykład:

  • ∀x ∃y R(x,y) — dla każdego x istnieje (być może zależne od x) y spełniające R.
  • ∃y ∀x R(x,y) — istnieje jedno y takie, że dla wszystkich x zachodzi R.

Są to zazwyczaj różne stwierdzenia. Przykład: „dla każdego człowieka istnieje matka” (∀x ∃y Matka(y,x)) vs „istnieje ktoś, kto jest matką wszystkich ludzi” (∃y ∀x Matka(y,x)) — pierwsze jest prawdziwe (każdy ma jakąś matkę), drugie jest fałszywe.

Zmienne wolne i związane

Kwantyfikatory wiążą zmienne. Zmienna występująca wewnątrz zasięgu kwantyfikatora jest związana; poza zasięgiem może być wolna. Na przykład w formule ∀x P(x,y) zmienna x jest związana przez ∀, natomiast y jest zmienną wolną (jej znaczenie zależy od kontekstu lub dodatkowego kwantyfikatora).

Tłumaczenie z języka naturalnego

Przy tłumaczeniu zdań potocznych należy uważać na ukryte kwantyfikatory i zakresy. Przykładowo:

  • „Każdy student zna jakiegoś wykładowcę” → ∀x (Student(x) → ∃y (Wykładowca(y) ∧ Zna(x,y))).
  • „Jest wykładowca, którego znają wszyscy studenci” → ∃y (Wykładowca(y) ∧ ∀x (Student(x) → Zna(x,y))).

Ograniczone i ogólne kwantyfikatory

W praktycznych zapiskach często używa się kwantyfikatorów związanych z określonym zbiorem: ∀x ∈ A P(x) lub ∃x ∈ A P(x). Istnieją też tzw. uogólnione kwantyfikatory (many, few, most), które formalizują bardziej precyzyjne ilościowe właściwości w logice opisowej lub teorii modeli.

Typowe błędy i uwagi praktyczne

  • Nieprecyzyjna domena dyskursu prowadzi do nieporozumień — zawsze określaj, po czym biegają zmienne.
  • Konwersja między „dla każdego” a „istnieje” wymaga uwagi: nie można zamieniać ∀ i ∃ bez zmiany znaczenia.
  • Pamiętaj o zasięgu kwantyfikatorów — nawiasy i kolejność są istotne.

Podsumowanie

Kwantyfikatory (głównie ∀ i ∃) pozwalają formalnie wyrażać twierdzenia o wszystkich obiektach danej domeny lub o istnieniu pewnych obiektów. Dzięki nim logika predykatów uzyskuje dużą wyrazistość i moc wyrazu, niezbędną do ścisłego formułowania i dowodzenia własności matematycznych i logicznych.

Kwantyfikatory pojawiają się także w językach naturalnych — typowe słowa to każdy, istnieje, wiele, mało, żaden (ang. for all, for some, many, few, a lot, and no). Rozumienie ich formalnych odpowiedników pomaga unikać nieporozumień przy analizie zdań i dowodzeniu twierdzeń.

Matematyka

To stwierdzenie jest nieskończenie długie:

1 - 2 = 1 + 1, i 2 - 2 = 2 + 2, i 3 - 2 = 3 + 3, ..., i 100 - 2 = 100 + 100, i ..., itd.

Jest to problem dla języków formalnych, ponieważ wypowiedź formalna musi mieć skończoną długość. Problemów tych można uniknąć poprzez użycie kwantyfikacji uniwersalnej. W ten sposób otrzymujemy następujące zwarte stwierdzenie:

Dla każdej liczby naturalnej n, n - 2 = n + n.

W ten sam sposób możemy skrócić nieskończoną sekwencję instrukcji połączonych spójnikiem lub:

1 jest równe 5 + 5, lub 2 jest równe 5 + 5, lub 3 jest równe 5 + 5, ... , albo 100 jest równe 5 + 5, albo ..., itd.

które można przepisać używając kwantyfikacji egzystencjalnej:

Dla co najmniej jednej liczby naturalnej n, n jest równe 5+5.

Notacja

Dwa najczęściej używane kwantyfikatory to kwantyfikator uniwersalny i kwantyfikator istnienia.

Uniwersalny kwantyfikator jest używany do twierdzenia, że dla elementów w zbiorze, wszystkie elementy spełniają pewne kryteria. Zazwyczaj stwierdzenie "dla wszystkich elementów" jest skracane do odwróconego "A", czyli "∀".

Kwantyfikator egzystencjalny jest używany do twierdzenia, że dla elementów w zbiorze istnieje przynajmniej jeden element, który spełnia pewne kryteria. Zazwyczaj stwierdzenie "istnieje element" jest skracane do "E" odwróconego do góry nogami, czyli "∃".

Możemy przepisać przykładową wypowiedź angielską za pomocą symboli, predykatów reprezentujących kryteria i kwantyfikatorów. Przykład: "Każdy z przyjaciół Piotra albo lubi tańczyć, albo lubi chodzić na plażę". Niech X będzie zbiorem wszystkich przyjaciół Piotra. Niech P(x) będzie predykatem "x lubi tańczyć". Niech Q(x) będzie predykatem "x lubi chodzić na plażę". Przykład ten możemy przepisać używając notacji formalnej jako ∀ x ∈ X , P ( x ) ∨ Q ( x ) {forall {x}{x}X,P(x)∨ Q(x)} {\displaystyle \forall {x}{\in }X,P(x)\lor Q(x)}. Stwierdzenie to można odczytać jako "dla każdego x, który jest członkiem X, P stosuje się do x lub Q stosuje się do x".

Istnieją inne sposoby użycia kwantyfikatorów w języku formalnym. Każde z poniższych stwierdzeń mówi to samo, co ∃ x ∈ X , P ( x ) {istnieje {x}{x}X,P(x)} {\displaystyle \exists {x}{\in }X,P(x)}:

  • ∃ x P {displaystyle ∃ istnieje {x}P}. {\displaystyle \exists {x}P}
  • ( ∃ x ) P { {displaystyle (∃ ∃ istnieje {x})P}. {\displaystyle (\exists {x})P}
  • ( ∃ x . P ) {displaystyle (∃ istnieje x . P )} {\displaystyle (\exists x\ .\ P)}
  • ∃ x ⋅ P {displaystyle ∃ istnieje x ∃ ∃ P} {\displaystyle \exists x\ \cdot \ P}
  • ( ∃ x : P ) {displaystyle (∃ istnieje x:P)} {\displaystyle (\exists x:P)}
  • ∃ x ∈ X P {{displaystyle ∈ ∈ X P} {\displaystyle \exists {x}{\in }X\,P}
  • ∃ x : X P {{displaystyle \i0}istnieje \i0}. {\displaystyle \exists \,x{:}X\,P}

Istnieje jeszcze kilka innych sposobów reprezentowania kwantyfikatora uniwersalnego:

  • ( x ) P {{displaystyle (x)} {\displaystyle (x)\,P}
  • ⋀ x P {{displaystyle {bigwedge _{x}P}} {\displaystyle \bigwedge _{x}P}

Kilka powyższych stwierdzeń wyraźnie zawiera X, zbiór elementów, do których odnosi się kwantyfikator. Ten zbiór elementów jest również znany jako zakres kwantyfikacji lub uniwersum dyskursu. Niektóre z powyższych stwierdzeń nie zawierają takiego zbioru. W takim przypadku zbiór ten będzie musiał być podany przed stwierdzeniem. Na przykład, "x jest jabłkiem" musi być podane przed ∃ x P ( x ) {istnieje {x}P(x)}{\displaystyle \exists {x}P(x)} . W tym przypadku składamy oświadczenie, że co najmniej jedno jabłko pasuje do predykatu P.

Formalne użycie kwantyfikatorów nie wymaga użycia symbolu x. Symbol x został użyty w tym artykule, ale można użyć dowolnego symbolu, np. y. Przy wyborze symboli należy pamiętać, aby nie odnosić się do dwóch różnych rzeczy za pomocą tego samego symbolu.

Zagnieżdżanie

Ważne jest, aby umieścić kwantyfikatory we właściwej kolejności. To jest przykładowe zdanie angielskie pokazujące, jak znaczenie zmienia się wraz z kolejnością:

Dla każdej liczby naturalnej n, istnieje liczba naturalna s taka, że s = n2.

To stwierdzenie jest prawdziwe. Mówi ono, że każda liczba naturalna ma kwadrat. Jeśli jednak odwrócimy kolejność kwantyfikatorów:

Istnieje liczba naturalna s, taka, że dla każdej liczby naturalnej n, s = n2.

To stwierdzenie jest fałszywe. Twierdzi ono, że istnieje jedna liczba naturalna s, która jest kwadratem każdej liczby naturalnej.

W pewnych okolicznościach zmiana kolejności kwantyfikatorów nie zmienia znaczenia wypowiedzi. Na przykład:

Istnieje liczba naturalna x i istnieje liczba naturalna y taka, że x = y2.

Inne kwantyfikatory

Istnieją również mniej popularne kwantyfikatory używane przez matematyków.

Przykładem jest kwantyfikator rozwiązania. Służy on do określenia, które elementy rozwiązują dane równanie. Kwantyfikator rozwiązania jest reprezentowany przez § (znak sekcji). Na przykład, poniższe twierdzenie mówi, że kwadraty liczb 0, 1 i 2 są mniejsze od 4. : [ § n ∈ N n 2 ≤ 4 ] = { 0 , 1 , 2 } { {displaystyle ¨left[¨S n¨ w ¨mathbb {N} ¨quad n^{2} ¨leq 4¨right]¨ = ¨left ¨{0,1,2¨right}} {\displaystyle \left[\S n\in \mathbb {N} \quad n^{2}\leq 4\right]=\left\{0,1,2\right\}}

Innymi kwantyfikatorami są:

  • Jest wiele elementów takich, że...
  • Niewiele jest elementów takich, że...
  • Istnieje nieskończenie wiele elementów takich, że...
  • Dla wszystkich, ale nieskończenie wielu elementów... (czasami wyrażane jako "dla prawie wszystkich elementów...").
  • Istnieje niepoliczalnie wiele elementów takich, że...
  • Dla wszystkich, ale niezliczonych elementów...

Historia

Logika terminowa została opracowana przez Arystotelesa. Była to wczesna forma logiki, zawierająca kwantyfikację. Użycie kwantyfikacji było bliższe temu, które występuje w języku naturalnym. Oznaczało to, że wypowiedzi w logice termicznej z kwantyfikatorami były mniej odpowiednie do analizy formalnej. Logika terminowa zawierała kwantyfikatory dla All, Some i No (żaden) w IV wieku p.n.e.

W 1879 roku Gottlob Frege stworzył notację dla kwantyfikacji uniwersalnej. Inaczej niż dzisiaj, reprezentowałby on kwantyfikację uniwersalną poprzez zapisanie zmiennej nad wgłębieniem w prostej linii. Frege nie stworzył notacji dla kwantyfikacji egzystencjalnej. Zamiast tego, połączył kwantyfikację uniwersalną i szereg negacji, aby stworzyć równoważne stwierdzenie. Użycie kwantyfikacji przez Fregego nie było szeroko znane aż do wydania przez Bertranda Russella w 1903 roku Principles of Mathematics.

W 1885 roku Charles Sanders Peirce i jego uczeń Oscar Howard Mitchell również stworzyli notację dla kwantyfikatorów uniwersalnych i egzystencjalnych. Pisali Πx i Σx tam, gdzie my teraz piszemy ∀x i ∃x. Notacja Pierce'a była używana przez wielu matematyków do lat pięćdziesiątych.

W 1897 roku William Ernest Johnson i Giuseppe Peano stworzyli kolejną notację dla kwantyfikacji uniwersalnej i egzystencjalnej. Byli oni pod wpływem poprzedniego zapisu kwantyfikatorów Pierce'a. Johnson i Peano użyli prostego (x) dla kwantyfikacji uniwersalnej i ∃x dla kwantyfikacji egzystencjalnej. Wpływ Peano na matematykę rozpowszechnił tę notację w całej Europie.

W 1935 roku Gerhard Gentzen stworzył symbol ∀ dla uniwersalnej kwantyfikacji. Nie był on powszechnie stosowany aż do lat 60-tych XX wieku.

Powiązane strony

Pytania i odpowiedzi

P: Co to jest kwantyfikator?

O: Kwantyfikator to sposób na stwierdzenie, że określona liczba elementów spełnia pewne kryteria.

P: Jaki jest przykład wyrażenia kwantyfikowanego?

O: Przykładem wyrażenia kwantyfikatorowego jest "każda liczba naturalna ma inną liczbę naturalną większą od niej".

P: Dlaczego kwantyfikatory i wyrażenia kwantyfikowane są użyteczne?

O: Kwantyfikatory i wyrażenia kwantyfikowane są użyteczne, ponieważ pozwalają rygorystycznym stwierdzeniom twierdzić, jak powszechne jest dane kryterium.

P: Jakie są dwa podstawowe rodzaje kwantyfikatorów używanych w logice predykatów?

O: Dwa podstawowe rodzaje kwantyfikatorów używanych w logice predykatów to kwantyfikatory uniwersalne i egzystencjalne.

P: Co stwierdza kwantyfikator uniwersalny?

A: Kwantyfikator uniwersalny stwierdza, że wszystkie rozważane elementy spełniają kryteria.

P: Jaki jest symbol kwantyfikatora uniwersalnego?

O: Symbolem kwantyfikatora uniwersalnego jest "∀", odwrócone "A", oznaczające "wszystkie".

P: Co stwierdza kwantyfikator istnienia?

O: Kwantyfikator istnienia stwierdza, że co najmniej jeden rozważany element spełnia kryteria.

P: Jaki jest symbol kwantyfikatora egzystencjalnego?

O: Symbolem kwantyfikatora egzystencjalnego jest "∃", czyli odwrócone "E", oznaczające "istnieje".

Powiązane artykuły

Autor

AlegsaOnline.com Kwantyfikatory w logice: definicja, symbole ∀ i ∃ oraz przykłady

URL: https://pl.alegsaonline.com/art/58867

Udostępnij

Źródła