---
title: "Lecture 2: Logika matematyczna II"
lecture_number: 2
has_solutions: true
has_exercises: true
---

```{include} ../_includes/sagecell-loader.md
```

# Logika matematyczna II

## 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$).
:::

:::{prf:definition}

**Formą zdaniową** {index}`forma zdaniowa` lub
**funkcją zdaniową** {index}`funkcja zdaniowa`
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** {index}`forma zdaniowa; zakres zmienności`
formy zdaniowej $\varphi(x)$ jest zbiór $X .$

Element $x_0\in X$ **spełnia** {index}`forma zdaniowa; spełniona`
formę zdaniową $\varphi(x)$, jeśli $\varphi(x_0)$ jest zdaniem prawdziwym.

:::

:::{prf:example}

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

:::{prf:definition}

**Wykresem** {index}`forma zdaniowa; wykres`
formy zdaniowej w zbiorze $X$ nazywamy zbiór
wszystkich elementów $x\in X$
spełniających formę zdaniową $\varphi (x)$
i oznaczmy przez

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

:::

::::{exercise}
:label: lec-02-ex-01
:class: [exercise]

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

:::{container} columns-2-auto

1. zmiennej $x\in \rr$
2. zmiennej $x\in [-2,2) .$

:::

:::{note}
:class: [see-problem]

Pomoże rozwiązać {numref}`prob-03-ex-03`, {numref}`prob-03-ex-07`.
:::

::::

:::{solution-without-reference}
:class: [solution] dropdown

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

```{math}
\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}
```

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

::::{exercise}
:label: lec-02-ex-02
:class: [exercise]

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

:::{note}
:class: [see-problem]

Pomoże rozwiązać {numref}`prob-03-ex-04`, {numref}`prob-03-ex-08`.
:::

::::

::::{solution-without-reference}
:label: item:2-2-a
:class: [solution] dropdown

W pierwszej kolejności
zauważamy, że

```{math}
\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}
```

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

   ```{math}
   \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}
   ```

   Graficznie przedstawione na niebiesko.

:::{figure} ../_images/algi-cw-2-2.svg
   :width: 80%

   Rozwiązania: podpunktu 1. przestawione na czerwono; podpunktu 2. -- na niebiesko.

:::

::::

:::{narration}

Niech $X_1, X_2, \ldots, X_n$ będą zbiorami niepustymi.
:::

:::{prf:definition}

**Formą zdaniową** {index}`forma zdaniowa` lub
**funkcją zdaniową** {index}`funkcja zdaniowa`
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** {index}`forma zdaniowa; zakres zmienności`
zmiennej $x_i$ jest zbiór $X_i .$

:::

:::{prf:example}

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

## Kwantyfikatory

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

### Uniwersalny

:::{prf:definition}

**Kwantyfikator uniwersalny** {index}`kwantyfikator; uniwersalny`
(**ogólny**) {index}`kwantyfikator; ogólny`, czyli "dla każdego",
oznaczany symbolem **$\forall, \bigwedge$**.

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

```{math}
\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

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

:::

:::{prf:remark}

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

```{math}
\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}
```

:::

::::{exercise}
:label: lec-02-ex-03
:class: [exercise]

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

Jaką wartość logiczną ma zdanie:

:::{container} columns-3-auto

1. $\forall x\in \rr \; \varphi(x)$
2. $\forall x>1 \; \varphi(x)$
3. $\forall x\in \rr \; \Negation\varphi(x)$?

:::

:::{note}
:class: [see-problem]

Pomoże rozwiązać {numref}`prob-03-ex-02`, {numref}`prob-03-ex-06`.
:::

::::

:::{solution-without-reference}
:class: [solution] dropdown

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

```{math}
\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ż

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

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

### Egzystencjalny

:::{prf:definition}

**Kwantyfikator egzystencjalny** {index}`kwantyfikator; egzystencjalny`
(**szczegółowy**) {index}`kwantyfikator; szczegółowy`, czyli "istnieje",
oznaczany symbolem **$\exists, \bigvee$**.

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

```{math}
\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

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

:::

::::{exercise}
:label: lec-02-ex-04
:class: [exercise]

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

Jaką wartość logiczną ma zdanie:

:::{container} columns-3-auto

1. $\exists x\in \rr\; \varphi(x)$
2. $\exists x\in[-1,0] \; \varphi(x)$
3. $\exists x\in \rr_+\; \Negation\varphi(x)$?

:::

:::{note}
:class: [see-problem]

Pomoże rozwiązać {numref}`prob-03-ex-02`, {numref}`prob-03-ex-06`.
:::

::::

:::{solution-without-reference}
:class: [solution] dropdown

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

:::{prf:remark}

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

```{math}
\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}.
$$

:::

### Notacja polska

:::{prf:remark}
:class: [remark]

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

```{math}
\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}
```

To wyjaśnia oznaczenie alternatywnej wersji kwantyfikatorów.

:::

## 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$:

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

:::

:::{prf:definition}

**Zmienną wolną** {index}`zmienna; wolna`
nazywamy tą, która nie jest związana przez kwantyfikator (czyli $x$).

**Zmienną związaną** {index}`zmienna; związana`
nazywamy tą, do której odnosi się kwantyfikator (czyli $y$).

:::

:::{prf:definition}

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):

```{math}
\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}
```

**Zmiennymi wolnymi** {index}`zmienna; wolna`
nazywamy zmienne $x_1,\ldots, x_{a -1}, x_{a +1}, \ldots, x_n .$

**Zmienną związaną** {index}`zmienna; związana`
nazywamy zmienną $x_a .$

:::

:::{prf:example}

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

```{math}
\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.

:::

::::{exercise}
:label: lec-02-ex-05
:class: [exercise]

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

:::{solution-without-reference}
:class: [solution] dropdown

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

```{math}
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

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

:::

::::{exercise}
:label: lec-02-ex-06
:class: [exercise]

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

:::{container} columns-2-auto

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

:::

::::

:::{answer}
:class: [solution] dropdown

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

::::{exercise}
:label: lec-02-ex-07
:class: [exercise]

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

:::{container} columns-2-auto

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

:::

::::

:::{answer}
:class: [solution] dropdown

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

::::{exercise}
:label: lec-02-ex-08
:class: [exercise]

Zapiszmy symbolicznie formę zdaniową:

1. $x$ jest sumą kwadratów dwóch liczb naturalnych.
2. Nie istnieje najmniejsza liczba całkowita.

:::{note}
:class: [see-problem]

Pomoże rozwiązać {numref}`prob-03-ex-01`, {numref}`prob-03-ex-05`.
:::

::::

:::{solution-without-reference}
:class: [solution] dropdown

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:

   ```{math}
   \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:

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

:::

## Prawa rachunku kwantyfikatorów

:::{prf:definition}

**Prawem rachunku kwantyfikatorów** {index}`prawo 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.
:::

:::{prf:remark}

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

```{math}
\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}
```

:::

:::{prf:theorem}

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._
:::

::::{exercise}
:label: lec-02-ex-09
:class: [exercise]

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.

:::{note}
:class: [see-problem]

Pomoże rozwiązać {numref}`prob-03-ex-02`, {numref}`prob-03-ex-06`.
:::

::::

:::{solution-without-reference}
:class: [solution] dropdown

1. Stosując prawo de Morgana:

   ```{math}
   \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}
   ```

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

   ```{math}
   \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}
   ```

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

   ```{math}
   \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}
   ```

:::

:::{prf:theorem}

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)$**.
:::

:::{prf:example}

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

## Zasada indukcji matematycznej

:::{prf:axiom} 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 .$
:::

:::{prf:remark}

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

::::{exercise}
:label: lec-02-ex-10
:class: [exercise]

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

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

:::{note}
:class: [see-problem]

Pomoże rozwiązać {numref}`prob-04-ex-01`, {numref}`prob-04-ex-07`.
:::

::::

:::{solution-without-reference}
:class: [solution] dropdown

Skorzystamy z ZID.

Przyjmujemy:

```{math}
\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

   ```{math}
   \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:

   ```{math}
   \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}
   ```

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