Logika matematyczna II

3. Logika matematyczna II#

3.1. Formy zdaniowe#

Narration

Niech \(X\) będzie zbiorem niepustym (o zbiorach będziemy jeszcze mówić – na razie zadowolimy się intuicyjnym rozumieniem pojęć zbioru, elementu zbioru, należenia do zbioru \(\in\)).

Definicja 3.1

Formą zdaniową lub funkcją zdaniową zmiennej \(x\in X\) nazywamy takie wyrażenie \(\varphi (x)\), które staje się zdaniem logicznym (prawdziwym lub fałszywym), gdy za \(x\) podstawiamy elementy ze zbioru \(X .\)

Zakresem zmienności formy zdaniowej \(\varphi(x)\) jest zbiór \(X .\)

Element \(x_0\in X\) spełnia formę zdaniową \(\varphi(x)\), jeśli \(\varphi(x_0)\) jest zdaniem prawdziwym.

Przykład 3.1

  1. Napis „\(x+2\)” nie jest formą zdaniową zmiennej \(x\in X\) (bez względu na to jaki to zbiór), gdyż po wstawieniu za \(x\) konkretnego elementu nie otrzymamy zdania logicznego.

  2. Zdanie logiczne „\(3 > 7\)” możemy uznać za formę zdaniową zmiennej \(x\in X\) (bez względu na to jaki to zbiór), choć explicite nie występuje w niej zmienna \(x .\) Oczywiście jest to zdanie logiczne fałszywe.

Definicja 3.2

Wykresem formy zdaniowej w zbiorze \(X\) nazywamy zbiór wszystkich elementów \(x\in X\) spełniających formę zdaniową \(\varphi (x)\) i oznaczmy przez

\[\PredicateGraph[X] \varphi = \Set{x\in X : \varphi(x)}\]

Ćwiczenie 3.1

Znajdźmy wykres formy zdaniowej \(\varphi(x): \ x < 0 \imply x^2 \geq 4\)

  1. zmiennej \(x\in \rr\)

  2. zmiennej \(x\in [-2,2) .\)

Informacja

Pomoże rozwiązać Ćw. 3.13, Ćw. 3.17.

Rozwiązanie

W pierwszej kolejności przekształcamy formę zdaniową \(\varphi(x)\):

\[\begin{split}\begin{aligned} x < 0 \imply x^2 \geq 4 & \qlq (\Negation (x < 0)) \vee x^2 \geq 4 \qlq x \geq 0 \vee |x| \geq 2 \\ & \qlq x \geq 0 \vee x \leq -2 \vee x \geq 2 \qlq x \geq 0 \vee x \leq -2. \end{aligned}\end{split}\]

Stąd widzimy, że:

  1. \( \PredicateGraph \varphi = \Set{x\in \rr : \varphi(x)} =(-\infty, -2]\cup [0, +\infty); \)

  2. \( \PredicateGraph[[-2,2)]{\varphi}= \Set{x\in [-2,2) : \varphi(x)} = [-2,2) \cap \Paren{(-\infty, -2]\cup [0, +\infty)} = \Set{-2}\cup [0,2). \)

Ćwiczenie 3.2

Znajdźmy wykres formy zdaniowej \(\psi((x,y)) : \ x^2 + y^2 \leq 4 \Leftrightarrow x + y > 0\)

  1. zmiennej \((x,y)\in \rr^2\)

  2. zmiennej \((x,y)\in X = \Set{(x,1) : x \in \rr} .\)

Informacja

Pomoże rozwiązać Ćw. 3.14, Ćw. 3.18.

Rozwiązanie

W pierwszej kolejności zauważamy, że

\[\begin{split}\begin{aligned} x^2 + y^2 \leq 4 \Leftrightarrow x + y > 0 \qlq \begin{cases} x^2 + y^2 \leq 4 \\ x+y > 0 \end{cases} \vee\quad \begin{cases} x^2 + y^2 > 4 \\ x+y \leq 0 \end{cases} . \end{aligned}\end{split}\]

  1. Wykres formy zdaniowej jest przedstawiony graficznie na czerwono.

  2. W tym przypadku wykres formy zdaniowej będzie przecięciem wykresu z poprzedniego punktu, ze zbiorem \(X\), będącym prostą \(y=1\):

    \[\begin{split}\begin{aligned} (x^2 + y^2 \leq 4 \Leftrightarrow x + y > 0) \wedge y=1 & \qlq \Paren{ \begin{cases} x^2 \leq 3 \\ x > -1 \end{cases} \vee\quad \begin{cases} x^2 > 3 \\ x \leq -1 \end{cases} }\ \wedge \ y=1. \\ & \qlq \Paren{ x \in \IntOC{-1,\ \sqrt 3} \vee x < -\sqrt{3} } \wedge y=1. \\ & \qlq \Paren{ x \in \IntOC{-\infty,\ -\sqrt{3}} \cup \IntOC{-1,\ \sqrt 3} } \wedge y=1. \end{aligned}\end{split}\]

    Graficznie przedstawione na niebiesko.

../_images/algi-cw-2-2.svg

Rysunek 3.1 Rozwiązania: podpunktu 1. przestawione na czerwono; podpunktu 2. – na niebiesko.#

Narration

Niech \(X_1, X_2, \ldots, X_n\) będą zbiorami niepustymi.

Definicja 3.3

Formą zdaniową lub funkcją zdaniową zmiennych \(x_1\in X_1,\ \ldots,\ x_n\in X_n\) nazywamy takie wyrażenie \(\varphi (x_1, \ldots, x_n)\), które staje się zdaniem logicznym (prawdziwym lub fałszywym), gdy za \(x_1,\ldots,x_n\) podstawiamy odpowiednio elementy zbiorów \(X_1,\ldots, X_n .\)

Zakresem zmienności zmiennej \(x_i\) jest zbiór \(X_i .\)

Przykład 3.2

Zgodnie z przyjętymi definicjami mamy:

  1. formę zdaniową

    \[\varphi((x,y)):\ x^2 + y^2 \leq 4 \Leftrightarrow x + y > 0\]

    zmiennej \((x,y)\in \rr^2\)

  2. formę zdaniową

    \[\varphi(x,y):\ x^2 + y^2 \leq 4 \Leftrightarrow x + y > 0\]

    zmiennych \(x,y\in \rr .\)

3.2. Kwantyfikatory#

Niech \(\varphi(x)\) będzie formą zdaniową zmiennej \(x\in X .\) Wyróżniamy dwa kwantyfikatory.

3.2.1. Uniwersalny#

Definicja 3.4

Kwantyfikator uniwersalny (ogólny) , czyli „dla każdego”, oznaczany symbolem \(\forall, \bigwedge\).

Zdanie logiczne z użycie kwantyfikatora ogólnego ma postać

\[\forall x\!\in\!\! X \; \varphi(x)\qquad \text{lub}\qquad \forall_{x\in X} \; \varphi(x)\]

i czytamy je „dla każdego elementu \(x\) ze zbioru \(X\) zachodzi \(\varphi(x)\)”.

Zdanie \(\forall x\!\in\!\! X \; \varphi(x)\) jest prawdziwe, jeśli

\[\begin{aligned} \PredicateGraph[X] \varphi = X. \end{aligned}\]

Uwaga 3.1

Używa się też skróconego zapisu dziedziny kwantyfikatora. Na przykład

\[\begin{aligned} \text{zamiast} \qquad \forall x\in\Set{x\in \rr : x > 7}\;\varphi(x) \qquad \text{napiszemy} \qquad \forall x > 7\;\varphi(x) \end{aligned}\]

Ćwiczenie 3.3

Niech \(\varphi(x) : x < 0 \imply x^2 \geq 4.\)

Jaką wartość logiczną ma zdanie:

  1. \(\forall x\in \rr \; \varphi(x)\)

  2. \(\forall x>1 \; \varphi(x)\)

  3. \(\forall x\in \rr \; \Negation\varphi(x)\)?

Informacja

Pomoże rozwiązać Ćw. 3.12, Ćw. 3.16.

Rozwiązanie

Na początek zapiszmy formę zdaniową \(\varphi(x)\) w przyjaźniejszej postaci:

\[\begin{aligned} x < 0 \imply x^2 \geq 4 \qlq x \geq 0 \vee |x| \geq 2 \qlq x \leq -2 \vee x \geq 0. \end{aligned}\]

  1. Zdanie w tym punkcie jest fałszywe, bo np. \(x=-1\) nie spełnia \(\varphi(x)\), czyli \(\PredicateGraph \varphi \neq \rr .\)

  2. Dla \(x > 1\) mamy \(x \geq 0\), stąd \(\varphi(x)\) jest prawdziwe. Zdanie \(\forall x>1 \; \varphi(x)\) jest prawdziwe.

  3. Zdanie w tym punkcie jest fałszywe, ponieważ

    \[\begin{aligned} \Negation \varphi \qlq x > -2 \wedge x < 0, \end{aligned}\]

    czyli \(\PredicateGraph{\Negation \varphi} = (-2,0) \neq \rr .\)

3.2.2. Egzystencjalny#

Definicja 3.5

Kwantyfikator egzystencjalny (szczegółowy) , czyli „istnieje”, oznaczany symbolem \(\exists, \bigvee\).

Zdanie logiczne z użycie kwantyfikatora szczegółowego ma postać

\[\exists x\!\in\!\! X \; \varphi(x)\qquad \text{lub}\qquad \exists_{x\in X} \; \varphi(x)\]

i czytamy je „istnieje element \(x\) w zbiorze \(X\), dla którego zachodzi \(\varphi(x)\)”.

Zdanie \(\exists x\!\in\!\! X \; \varphi(x)\) jest prawdziwe, jeśli

\[\PredicateGraph[X] \varphi = \Set{x\in X : \varphi(x)} \neq \emptyset.\]

Ćwiczenie 3.4

Niech \(\varphi(x) : x < 0 \imply x^2 \geq 4.\)

Jaką wartość logiczną ma zdanie:

  1. \(\exists x\in \rr\; \varphi(x)\)

  2. \(\exists x\in[-1,0] \; \varphi(x)\)

  3. \(\exists x\in \rr_+\; \Negation\varphi(x)\)?

Informacja

Pomoże rozwiązać Ćw. 3.12, Ćw. 3.16.

Rozwiązanie

Korzystamy z przekształceń poprzedniego zadania.

  1. Zdanie w tym punkcie jest prawdziwe, bo np. \(x=7\) spełnia \(\varphi(x)\), czyli \(\PredicateGraph \varphi \neq \emptyset .\)

  2. Ponieważ \([-1,0] \cap \PredicateGraph \varphi = [-1,0] \cap \Paren{(-\infty, -2]\cup [0, +\infty)} = \Set{0}\), to mamy \(x=0 \in [-1,0]\), dla którego \(\varphi(x)\) jest prawdziwe. Zatem zdanie \(\exists x\in[-1,0] \; \varphi(x)\) jest prawdziwe.

  3. Zdanie w tym punkcie jest fałszywe, ponieważ \(\rr_+ \cap \PredicateGraph{\Negation \varphi} = \rr_+ \cap(-2,0) = \emptyset .\)

Uwaga 3.2

Kwantyfikator szczegółowy można „wzbogacić o wykrzyknik” i wówczas zdanie

\[\exists! x\!\in\!\! X \; \varphi(x)\qquad \text{lub}\qquad \exists!_{x\in X} \; \varphi(x)\]

czytamy „istnieje dokładnie jeden element \(x\) w zbiorze \(X\), dla którego zachodzi \(\varphi(x)\)”, więc jest ono prawdziwe wtedy i tylko wtedy, gdy

\[ \exists a\in X\; \Set{x\in X : \varphi(x)} = \Set{a}. \]

3.2.3. Notacja polska#

Uwaga 3.3

Jeśli zbiór \(X = \{a_1, \ldots, a_n\}\) jest skończony to

\[\begin{split}\begin{aligned} \forall x\in X \; \varphi(x) \qlq \bigwedge_{x\in X} \; \varphi(x) & \qlq \varphi(a_1) \wedge \cdots \wedge \varphi(a_n), \\ \exists x\in X \; \varphi(x) \qlq \bigvee_{x\in X} \; \varphi(x) & \qlq \varphi(a_1) \vee \cdots \vee \varphi(a_n). \end{aligned}\end{split}\]

To wyjaśnia oznaczenie alternatywnej wersji kwantyfikatorów.

3.3. Zmienne wolne i związane#

Narration

Niech \(\varphi(x,y)\) będzie formą zdaniową zmiennych \(x\in X, y\in Y .\) Wówczas możemy utworzyć formy zdaniowe zmiennej \(X\):

\[\begin{aligned} & \psi_1(x): \forall y\in Y \; \varphi(x,y), && \psi_2(x): \exists y\in Y \; \varphi(x,y). \end{aligned}\]

Definicja 3.6

Zmienną wolną nazywamy tą, która nie jest związana przez kwantyfikator (czyli \(x\)).

Zmienną związaną nazywamy tą, do której odnosi się kwantyfikator (czyli \(y\)).

Definicja 3.7

Dla formy zdaniowej \(\varphi(\mathbf{x})\) zmiennych \(x_1\in X_1, \ldots, x_n\in X_n\) i wybranego indeksu \(a \in \Set{1,\ldots, n},\) możemy utworzyć formy zdaniowe (odpowiednich zmiennych):

\[\begin{split}\begin{aligned} & \psi_1(x_1,\ldots, x_{a -1}, x_{a +1}, \ldots, x_n ): \forall x_{a}\in X_{a} \; \varphi(x_1, \ldots, x_n), \\ & \psi_2(x_1,\ldots, x_{a -1}, x_{a +1}, \ldots, x_n ): \exists x_{a}\in X_{a} \; \varphi(x_1, \ldots, x_n). \end{aligned}\end{split}\]

Zmiennymi wolnymi nazywamy zmienne \(x_1,\ldots, x_{a -1}, x_{a +1}, \ldots, x_n .\)

Zmienną związaną nazywamy zmienną \(x_a .\)

Przykład 3.3

Jeśli \(x \in [5,9)\) i \(n \in \nn\), to

\[\psi(n): \forall x\in [5,9) \quad x - n > 2\]

jest formą zdaniową zmiennej \(n\in \nn .\) Zmienna \(x\) jest związana, zaś \(n\) jest wolna.

Ćwiczenie 3.5

Znajdźmy wykres f. zdaniowej \(\psi(n): \forall x\in [5,9) \; x - n > 2\) zmiennej \(n\in\nn .\)

Rozwiązanie

Przekształćmy formę zdaniową pod kwantyfikatorem do postaci

\[n < x-2.\]

Układ nierówności \(5 \leq x < 9\) jest równoważny \(3 \leq x -2 < 7 .\)

Pytamy: jakie liczby naturalne \(n\) są mniejsze od każdej liczby z przedziału \([3,7)\)?

Odpowiedź to \(1\) i \(2 .\) Zatem

\[\PredicateGraph[\nn] \psi = \Set{1,2}.\]

Ćwiczenie 3.6

Niech \(x\in [-2,2] .\) Znajdźmy wykresy form zdaniowych:

  1. \(\psi_1(x): \forall y\in \rr \; x > \sin y\)

  2. \(\psi_2(x): \forall y\in [-\pi,0) \; x > \sin y.\)

Odpowiedź

  1. \(\PredicateGraph[{[-2,2]}] {\psi_1} = (1,\ +\infty) \cap [-2,2] = (1,\ 2]\)

  2. \(\PredicateGraph[{[-2,2]}] {\psi_2} = (0,\ +\infty) \cap [-2,2] = (0,\ 2]. \)

Ćwiczenie 3.7

Niech \(x\in [-4,4] .\) Znajdźmy wykres form zdaniowych:

  1. \(\psi_1(x): \exists y\in \rr \; x > y^2\)

  2. \(\psi_2(x): \exists y\in [1,3) \; x > y^2.\)

Odpowiedź

  1. \(\PredicateGraph[{[-4,4]}] {\psi_1} = (0, +\infty) \cap [-4,\ 4] = (0,\ 4] \)

  2. \(\PredicateGraph[{[-4,4]}] {\psi_2} = (1, +\infty) \cap [-4,\ 4] = (1,\ 4]. \)

Ćwiczenie 3.8

Zapiszmy symbolicznie formę zdaniową:

  1. \(x\) jest sumą kwadratów dwóch liczb naturalnych.

  2. Nie istnieje najmniejsza liczba całkowita.

Informacja

Pomoże rozwiązać Ćw. 3.11, Ćw. 3.15.

Rozwiązanie

W tym zadaniu możliwych jest wiele poprawnych odpowiedzi.

  1. Chcemy znaleźć formę zdaniową, której wykres (w zbiorze liczb) będzie podzbiorem sum kwadratów dwóch liczb naturalnych. Możemy to sformułować na przykład:

    \[\begin{aligned} \exists a\in\nn \ \exists b\in\nn \quad x = a^2 + b^2. \end{aligned}\]

  2. Jest to zdanie logiczne – nie występują zmienne wolne. Można je zapisać tak:

    \[\begin{aligned} \Negation \Brack{ \exists n_{min}\in \zz \ \forall m \in \zz \quad n_{min} \leq m}. \end{aligned}\]

3.4. Prawa rachunku kwantyfikatorów#

Definicja 3.8

Prawem rachunku kwantyfikatorów nazywamy formułę zawierającą symbole kwantyfikatorów, która jest zdaniem prawdziwym dla dowolnej interpretacji symboli i form zdaniowych w niej występujących.

Uwaga 3.4

Gdy zakres zmienności \(X\) formy zdaniowej zmiennej \(x\) jest określony, to:

\[\begin{split}\begin{aligned} \Forall{x} \varphi(x) & \quad \text{oznacza} \quad \forall x\in X \;\varphi(x) \\ \Exists{x} \varphi(x) & \quad \text{oznacza} \quad \exists x\in X \;\varphi(x). \end{aligned}\end{split}\]

Twierdzenie 3.1

Dla dowolnego zbioru niepustego \(X\) i zmiennej \(x\in X\), następujące formuły są prawami rachunku kwantyfikatorów:

  1. \(\Forall{x} \varphi(x) \Rightarrow \exists x\; \varphi(x)\)

  2. \(\Negation (\Forall{x} \varphi(x)) \Leftrightarrow \exists x\; (\Negation \varphi(x))\)

    \(\Negation (\Exists{x} \varphi(x)) \Leftrightarrow \forall x\; (\Negation \varphi(x))\) – prawa de Morgana

  3. \(\Exists{x} (\varphi(x)\vee \psi (x)) \Leftrightarrow \Exists{x} \varphi(x) \vee \Exists{x} \psi(x)\)

    \(\Exists{x} (\varphi(x)\wedge \psi (x)) \Rightarrow \Exists{x} \varphi(x) \wedge \Exists{x} \psi(x)\) – prawa rozdzielności kwantyfikatora szczegółowego

  4. \(\Forall{x} (\varphi(x)\wedge \psi (x)) \Leftrightarrow \Forall{x} \varphi(x) \wedge \Forall{x} \psi(x)\)

    \(\Forall{x} \varphi(x) \vee \Forall{x} \psi(x) \Rightarrow \Forall{x} (\varphi(x)\vee \psi (x))\) – prawa rozdzielności kwantyfikatora ogólnego.

Ćwiczenie 3.9

Zapiszmy zaprzeczenia zdań:

  1. \(\forall x\in \rr \; x^2=2 \)

  2. \(\exists x> 3 \; x\in\zz \imply 2x > 3 \)

  3. \(\forall x>1 \ \exists y\in\nn \; x+y =0 \wedge x-y \in \zz\)

zawierające jedynie funktory koniunkcji i alternatywy.

Informacja

Pomoże rozwiązać Ćw. 3.12, Ćw. 3.16.

Rozwiązanie

  1. Stosując prawo de Morgana:

    \[\begin{split}\begin{aligned} \Negation\; & \forall x\in \rr \; x^2=2 \\ & \exists x\in \rr \; \Negation x^2 = 2 \\ & \exists x\in \rr \; x^2\neq 2 \end{aligned}\end{split}\]

  2. Stosując prawo de Morgana dla kwantyfikatora i koniunkcji:

    \[\begin{split}\begin{aligned} \Negation\; & \exists x> 3 \; x\in\zz \imply 2x > 3 \\ & \forall x> 3 \; \Negation \Paren{x\in\zz \imply 2x > 3} \\ & \forall x> 3 \; x\in\zz\ \wedge \Negation (2x > 3) \\ & \forall x> 3 \; x\in\zz \wedge 2x \leq 3 \end{aligned}\end{split}\]

  3. Stosując potrójnie prawa de Morgana:

    \[\begin{split}\begin{aligned} \Negation\; & \forall x>1 \ \exists y\in\nn \; x+y =0 \wedge x-y \in \zz \\ & \exists x>1 \Negation \exists y\in\nn \; x+y =0 \wedge x-y \in \zz \\ & \exists x>1 \forall y\in\nn \; \Negation \Paren{x+y =0 \wedge x-y \in \zz} \\ & \exists x>1 \forall y\in\nn \; x+y \neq 0 \vee x-y \notin \zz \ . \end{aligned}\end{split}\]

Twierdzenie 3.2

Dla dowolnych zbiorów niepustych \(X, Y\) i zmiennych \(x\in X\), \(y\in Y\), mamy następujące prawa przemienności kwantyfikatorów:

  1. \(\Exists{x} \Exists{y} \varphi(x,y) \Leftrightarrow \Exists{y} \Exists{x} \varphi(x,y)\)

  2. \(\Forall{x} \Forall{y} \varphi(x,y) \Leftrightarrow \Forall{y} \Forall{x}\varphi(x,y)\)

  3. \(\Exists{x} \Forall{y} \varphi(x,y) \Rightarrow \Forall{y} \Exists{x} \varphi(x,y)\).

Przykład 3.4

  1. Wyrażenie

    \[ \Forall {y\in \rr} \Exists {x\in \rr} x+y=\pi \]

    jest zdaniem prawdziwym.

    Wystarczy dla \(y\in\rr\) przyjąć \(x= \pi -y .\)

  2. Wyrażenie

    \[ \Exists {x\in \rr} \Forall {y\in \rr} x+y=\pi \]

    jest zdaniem fałszywym.

    Istotnie, nie istnieje jeden wspólny \(x\) „pasujący” do wszystkich \(y\) w podanej równości.

  3. Z powyższego widzimy, że wyrażenie

    \[ \Forall{y} \Exists{x} \varphi(x,y) \Rightarrow \Exists{x} \Forall{y} \varphi(x,y) \]

    może być fałszywe, czyli nie jest prawem logicznym.

  4. Wyrażenie

    \[ \Forall {y\in \rr} \Exists {x\in \zz} x+y=\pi \]

    jest zdaniem fałszywym

    Nie każda liczba \(y\in\rr\) jest postaci \(y = \pi - x\), gdzie \(x\in\zz .\)

  5. Wyrażenie

    \[ \Forall {x\in \rr} \Exists {y\in \rr} x+y\neq\pi \]

    jest zdaniem prawdziwym, jako zaprzeczenie zdania z punku 2.

3.5. Zasada indukcji matematycznej#

Aksjomat 3.3 (Zasada indukcji matematycznej (ZID))

Niech \(\varphi(n)\) będzie formą zdaniową zmiennej \(n\in\nn_0 .\) Załóżmy, że istnieje \(n_0\in\nn_0\) takie, że:

  1. \(\varphi(n_0)\) jest zdaniem prawdziwym,

  2. dla każdego \(k\in \nn_0\) takiego, że \(k\geq n_0\) prawdziwa jest implikacja

    \[ \varphi(k)\Rightarrow \varphi(k+1).\]

Wówczas \(\varphi(n)\) jest zdaniem prawdziwym dla każdej liczby naturalnej \(n\geq n_0 .\)

Uwaga 3.5

Jeśli zdanie \(\varphi(k)\) jest fałszywe to implikacja \(\varphi(k)\Rightarrow \varphi(k+1)\) jest automatycznie prawdziwa.

Wystarczy założyć, że zdanie \(\varphi(k)\) jest prawdziwe i z niego wywieść prawdziwość zdania \(\varphi(k+1) .\)

Ćwiczenie 3.10

Wykażmy, że dla każdego \(n\in \nn\) zachodzi

\[ 1 + 2 + \ldots + n = \frac{n(n+1)} 2. \]

Informacja

Pomoże rozwiązać Ćw. 4.13, Ćw. 4.19.

Rozwiązanie

Skorzystamy z ZID.

Przyjmujemy:

\[\begin{aligned} \varphi(n) : 1 + 2 + \ldots + n = \frac{n(n+1)} 2, & & n_0 = 1. \end{aligned}\]

  1. Sprawdzamy prawdziwość \(\varphi(1) .\)

    Istotnie, \(\varphi(1) : 1 = \frac{1\cdot(1 + 1)} 2 .\)

    To jest równoważne prawdziwemu zdaniu \(1 = 1 .\)

  2. Ustalmy \(k \geq 1 .\)

    Załóżmy, że

    \[\varphi(k): 1 + 2 + \ldots + k = \frac {k(k+1)} 2\]

    jest prawdziwe.

    Pokażemy, że

    \[\varphi(k+1) : 1 + 2 + \ldots + (k+1) = \frac{(k+1)((k+1)+1)} 2\]

    jest również prawdziwe.

    Istotnie, przekształcając lewą stronę \(L\) równości \(\varphi(k+1)\), otrzymujemy kolejno:

    \[\begin{split}\begin{aligned} L & = 1 + 2 + \ldots + k + (k+1) \\ & =\frac{k(k+1)} 2 + (k+1) & & \text{ponieważ $\varphi(k)$ jest prawdziwe} \\ & = \frac{k(k+1) + 2(k+1)} 2\\ & = \frac{(k + 1)(k+2)} 2 \\ & = P, \end{aligned}\end{split}\]

    gdzie \(P\) jest prawą stroną równości w \(\varphi(k+1) .\)

Zatem z zasady indukcji matematycznej \(\varphi(n)\) jest prawdziwe dla każdego \(n \geq 1 .\)