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$.