Rozumowania

Aby się przekonać, że wartością danego zdania rachunku predykatów jest \(\top\) nie wystarczy rachować. Trzeba wpaść na pomysł dowodu i go przeprowadzić. Można przy tym stosować najróżniejsze techniki, jak indukcję, rozważanie przypadków, czy rozumowanie przez sprzeczność. Podstawą są dwie techniki, opisane poniżej.

Ustalmy pomocniczo, że X to jakiś zbiór obiektów (na przykład \(X=\mathbb R\)). Dodatkowo, niech \(\varphi(x)\) będzie jakąś formułą rachunku predykatów, zależną od x oznaczającego jakiś element z X.

Kwantyfikator \(\forall\)

Pierwsza technika pozwala na pozbycie się kwantyfikatora dla każdego. Mianowicie, jeśli chcemy udowodnić, że prawdą jest \(\forall_x \varphi(x)\), możemy powiedzieć:

Weźmy dowolne x z X. Pokażemy że zachodzi \(\varphi(x)\). [...]

Jeśli dla ogólnego x pokazaliśmy, że zachodzi \(\varphi(x)\), to tym samym pokazaliśmy, że prawdą jest całe zdanie \(\forall_x \varphi(x)\).

Przykłady takich rozumowań podane były w poprzednich rozdziałach, bardzo prosty jest następujący:

Pokazujemy, że \(\forall_{n\in \mathbb N}(n+2)^2\geq 4\). Rozumowanie:

Weźmy dowolne n będące liczbą naturalną. Pokażemy, że zachodzi \((n+2)^2\geq 4\). Ale wiemy, że n jest liczbą naturalną, więc oczywiście \(n\geq 0\). Więc w takim razie \(n+2\geq 2\), więc \((n+2)^2\geq 4</math. Więc pokazaliśmy tezę. === Kwantyfikator <math>\exists\) ===

Druga z technik dotyczy kwantyfikatora istnieje. Aby pokazać, że \(\exists_x \varphi(x)\), wystarczy powiedzieć:

Weźmy x równe [...]. Sprawdźmy że dla tego, ustalonego x zachodzi \(\varphi(x)\). [...]

W tym przypadku wskazaliśmy konkretny obiekt (na przykład liczbę) i dla niego sprawdziliśmy, że zachodzi \(\varphi(x)\). A skoro tak, to istnieje takie x, więc udowodniliśmy \(\exists_x \varphi(x)\).

Znowu pora na prosty przykład. Pokażemy zdanie: ,istnieje liczba pierwsza p, taka że każda inna liczba pierwsza jest parzysta, lub jest większa niż p'. Dowód:

Weźmy p równe 3. Sprawdźmy, że takie p spełnia podaną tezę. Oczywiście 0,1 nie są liczbami pierwszymi. Z kolei 2 jest liczbą pierwszą, ale jest też liczbą parzystą. Kolejna liczba to 3 = p. Więc dowolna nieparzysta liczba pierwsza \(q\neq p\) nie może być równa żadnej z liczb 0,1,2,3. Więc musi być większa niż p.

Przykład

Połączeniem opisanych w tym rozdziale technik są tzw. dowody niekonstruktywne. Mianowicie formuła \(\exists_x \varphi(x)\) jest równoważna formule \(\lnot\forall_x \lnot\varphi(x)\). Czyli jeśli pokażemy, że nie może być prawdą, że \(\forall_x \lnot\varphi(x)\), to tym samym udowodnimy, że \(\exists_x \varphi(x)\). W dowodzie takim pomijamy wskazanie konkretnego x spełniającego odpowiedni warunek, więc dowód taki nazywa się niekonstruktywnym.

Przykład rozumowania niekonstruktywnego:

Pokażemy, że istnieje pewna liczba pierwsza, większa niż 10^100'000'000.

Aby zapisać to zdanie w notacji rachunku predykatów, używać będziemy oznaczenia \(\mathbb P\) na zbiór wszystkich liczb pierwszych. Wtedy powyższe zdanie brzmi \(\varphi\equiv\exists_{p\in\mathbb N} p\in\mathbb P\wedge p>10^{100'000'000}\). Niektórzy czytelnicy wiedzą, że liczb pierwszych jest nieskończenie wiele. My postaramy się nie korzystać z tego faktu. Wykazanie bezpośrednie, że prawdą jest \(\varphi\), wymagało by wskazania konkretnej liczby pierwszej, większej niż 10^100'000'000. Ale na dzień dzisiejszy żadna taka liczba nie jest znana. Dlatego przeprowadzimy dowód niekonstruktywny:

Zamiast pokazać, że prawdą jest \(\exists_{p\in\mathbb N} p\in\mathbb P\wedge p>10^{100'000'000}\), pokażemy że nie może być prawdą, że \(\forall_{p\in\mathbb N} \lnot(p\in\mathbb P\wedge p>10^{100'000'000})\).

Teraz pora na rozumowanie przez sprzeczność:

Zamiast pokazać, że nie może być prawdą \(\forall_{p\in\mathbb N} \lnot\left(p\in\mathbb P\wedge p>10^{100'000'000}\right)\), na chwilę założymy że jednak jest to prawda, by dojść do sprzeczności.

1. Załóżmy, że prawdą jest, że \(\forall_{p\in\mathbb N} \lnot\left(p\in\mathbb P\wedge p>10^{100'000'000}\right)\).
2. W takim razie, korzystając z prawa de'Morgana (\(\lnot(P\wedge Q)\equiv \lnot P\vee\lnot Q\)), wiemy że prawdą jest: \(\forall_{p\in\mathbb N} p\notin\mathbb P\vee p\leq 10^{100'000'000})\).
3. Teraz zamiast formuły postaci \(\lnot P\vee Q\), napiszemy równoważnie \(P\Rightarrow Q\). Otrzymamy wtedy zdanie \(\forall_{p\in\mathbb N} p\in\mathbb P\Rightarrow p\leq 10^{100'000'000}\)
4. Czyli każda liczba pierwsza, musi być mniejsza-równa niż 10^100'000'000.
5. Czyli liczb pierwszych jest co najwyżej 10^100'000'000.
6. Czyli można wszystkie liczby pierwsze wypisać w ciągu: \(p_1,p_2,\ldots,p_K\), gdzie \(p_1=2, p_2=3, p_3=5,\ldots\) i \(K\leq 10^{100'000'000}\).
7. Ale wtedy istnieje liczba \(Z=\left(p_1\cdot p_2\cdot p_3\cdot \ldots \cdot p_K\right)\cdot 10^{100'000'000} + 1\).
8. Oczywiście Z > 10^100'000'000. Więc przy naszych założeniach, Z nie może być liczbą pierwszą.
9. Skoro tak, to ma jakiś dzielnik pierwszy. Czyli istnieje taki numer i pomiędzy 1, a K, że liczba p_i dzieli Z.
10. Ale \(Z-1=\left(p_1\cdot p_2\cdot p_3\cdot \ldots \cdot p_K\right)\cdot 10^{100'000'000}\) dzieli się przez wszystkie liczby \(p_1,p_2,\ldots,p_K\), więc w tym przez p_i.
11. Czyli zarówno Z − 1, jak i Z dzielą się przez p_i.
12. Więc ich różnica dzieli się przez p_i.
13. Ale różnica Z i Z − 1, to 1, które nie dzieli się przez żadną liczbę pierwszą! Sprzeczność.
14. Więc otrzymaliśmy szukaną sprzeczność.

Oznaczmy pomocniczo \(\psi(p)\equiv p\in\mathbb P\wedge p>10^{100'000'000}\), by \(\varphi\equiv\exists_{p\in\mathbb N}\psi(p)\).

Pomijając rachunki, w powyższym rozumowaniu wykonaliśmy następujące operacje logiczne:

• chcieliśmy wykazać zdanie \(\exists_{p\in\mathbb N}\psi(p)\),
• zamieniliśmy je na zdanie \(\lnot\forall_p\lnot\psi(p)\),
• zamiast pokazać zdanie postaci \(\lnot\forall_p\lnot\psi(p)\), założyliśmy że \(\forall_p\lnot\psi(p)\) i dążyliśmy do sprzeczności,
• aby dostać odpowiednią sprzeczność, korzystaliśmy z zasad logiki (np. praw de'Morgana), by przekształcać dogodnie postać \(\lnot\psi(p)\),
• na koniec dostaliśmy sprzeczność, bo okazało się, że 1 dzieli się przez jakąś liczbę pierwszą p_i,
• przez co wykazaliśmy, że nie może być \(\forall_p\lnot\psi(p)\), czyli musi być prawdą \(\lnot\forall_p\lnot\psi(p)\)
• co jest równoważne temu, że \(\exists_p \psi(p)\), czyli dokładnie \(\varphi\).