---
title: "Lecture 1: Logika matematyczna I"
lecture_number: 1
has_solutions: true
has_exercises: true
---

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

# Logika matematyczna I

:::{narration}

Aby dobrze się komunikować, trzeba ustalić język i zasady w nim obowiązujące:
poprawnie sformułować twierdzenie, a następnie -- korzystając z ustalonych
zasad -- **udowodnić**, że jest ono prawdziwe. Zajmiemy się logiką klasyczną
(dwuwartościową).
:::

## Zdania logiczne

:::{prf:definition}

**Zdanie logiczne** {index}`zdanie logiczne` to zdanie oznajmujące, któremu można
przypisać określoną wartość logiczną.
W logice klasycznej zdania dzielimy na:

- prawdziwe (przypisujemy im wartość logiczną $1$)
- fałszywe (o wartości logicznej $0$).

Zdania nieposiadające jednoznacznej wartości logicznej (pytania, rozkazy,
zdania z niepodstawioną zmienną, antynomie w rodzaju "To zdanie jest fałszywe")
nie są zdaniami logicznymi.
:::

::::{prf:example}

1. "Dwa plus dwa równa się cztery." jest zdaniem logicznym.

   Na gruncie zwykłej arytmetyki przypiszemy mu wartość logiczną 1.

2. "Ala ma kota." jest zdaniem logicznym.

   Wartość logiczna tego zdania powinna odzwierciedlać naszą wiedzę na temat tego,
   czy Ala ma kota.

3. Zdanie

   $$
   \forall \ell_1 \in L\; \forall p \in \rr^2\setminus \ell_1 \; \exists ! \ell_2 \in L\; (p\in \ell_2 \wedge \ell_1 \cap \ell_2 = \emptyset)
   $$

   jest zdaniem logicznym (którego części składowe będziemy omawiać dalej na tym wykładzie).

   Przyjmując za $L$ zbiór wszystkich prostych w $\rr^2$, w geometrii euklidesowej zdanie
   to będzie miało wartość logiczną 1 (jest to aksjomat Euklidesa).
   Jednak rozważa się geometrie (na przykład na sferze),
   w których to zdanie ma wartość logiczną 0.

   :::{container} center-text
   **To jaką wartość logiczną przypiszemy danemu zdaniu zależy od nas!**
   :::

4. "Czy to jest zrozumiałe?" nie jest zdaniem logicznym - nie jest zdaniem oznajmującym.

5. "Ach, jak tu pięknie!", "Otwórz okno!" również nie są zdaniami logicznymi.

6. Jeśli nie przyjmiemy konkretnej wartości $x\in\rr$,
   to zdanie "$x > 0$" nie jest zdaniem logicznym.

   Problem w tym, że nie możemy przypisać mu jednoznacznej wartości logicznej,
   gdyż zależy ona od wartości zmiennej $x .$ Wrócimy do tego tematu!

7. "To zdanie jest fałszywe.", "Ja teraz kłamię." też nie są zdaniami logicznymi.

   To **antynomie**, czyli zdania prowadzące do sprzeczności logicznej.

   Istotnie, jeśli przyjąć, że "To zdanie jest fałszywe." ma wartość logiczną 1, to
   wywnioskujemy z niego, że jest ono fałszywe, czyli ma wartość logiczną 0 -- sprzeczność.

   Analogicznie nie możemy przypisać temu zdaniu wartości logicznej 0.
::::

:::{narration}

Zdania logiczne najczęściej oznacza się małymi literami łacińskimi,
najczęściej zaczynając od: $p, q, r, s .$

:::

:::{prf:definition}

**Wartość logiczną** {index}`zdanie logiczne; wartość` zdania $p$ zapisujemy jako
$\LogicValue(p) .$
:::

## Funktory zdaniotwórcze

:::{narration}

Głównym celem wprowadzenia rachunku zdań i praw logiki jest
możliwość przeprowadzania precyzyjnych **rozumowań dedukcyjnych**.
Rozbudowane rozumowanie dedukcyjne prowadzi do sformułowania **twierdzenia**
(lub jeśli ma ono mniejszą wagę **stwierdzenia** albo **lematu**).
Najczęściej twierdzenie ma postać implikacji, w której poprzednik
nazywamy **założeniem** {index}`twierdzenie; założenie`,
a następnik **tezą twierdzenia** {index}`twierdzenie; teza`.

W celu tworzenia złożonych zdań logicznych używa się
**funktorów zdaniotwórczych** {index}`funktor zdaniotwórczy`
(inaczej nazywanych **spójnikami logicznymi** {index}`spójnik logiczny`).
Wyróżniamy kilka podstawowych spójników logicznych.
:::

### Koniunkcja

::::::{prf:definition}

:::::{container} side-by-side

::::{container} column-three-fourth

**Koniunkcja** {index}`koniunkcja`, czyli spójnik logiczny "i",
oznaczany symbolem **$\wedge$**.

Koniunkcja zdań $p$ i $q$ jest prawdziwa jedynie w przypadku,
gdy oba zdania $p$ i $q$ są prawdziwe; w pozostałych przypadkach
jest fałszywa.

Zdania $p$ i $q$ nazywają się **czynnikami** koniunkcji {index}`koniunkcja; czynnik`.

::::

::::{container} column-one-fourth

:::{list-table}
:class: table-auto-width
:header-rows: 1
:widths: 10 10 20

* - $p$
  - $q$
  - $p\wedge q$
* - 1
  - 1
  - 1
* - 1
  - 0
  - 0
* - 0
  - 1
  - 0
* - 0
  - 0
  - 0
:::

::::

:::::

::::::

:::{prf:example}

1. "Ala ma kota. $\wedge$ Jest pochmurno." oznacza zdanie "Ala ma kota i jest pochmurno."

2. "$ 2 > 1 \wedge -3 > 1$"
   oznacza zdanie, które słownie możemy
   zapisać jako "Liczby 2 i $-3$ są (obie) większe od liczby 1."
:::

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

Jaka jest wartość logiczna zdania $p : 2 > 1 \wedge -3 > 1$?
::::

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

$\LogicValue(p) = 0$, czyli zdanie jest fałszywe.
:::

### Alternatywa

::::::{prf:definition}

:::::{container} side-by-side

::::{container} column-three-fourth

**Alternatywa** {index}`alternatywa`, czyli spójnik logiczny "lub",
oznaczany symbolem **$\vee$**.

Alternatywa zdań $p$ i $q$ jest fałszywa jedynie w przypadku,
gdy oba zdania $p$ i $q$ są fałszywe; w pozostałych przypadkach
jest prawdziwa.

Zdania $p$ i $q$ nazywają się **składnikami** alternatywy {index}`alternatywa; składnik`.

::::

::::{container} column-one-fourth

:::{list-table}
:class: table-auto-width
:header-rows: 1
:widths: 10 10 20

* - $p$
  - $q$
  - $p\vee q$
* - 1
  - 1
  - 1
* - 1
  - 0
  - 1
* - 0
  - 1
  - 1
* - 0
  - 0
  - 0
:::

::::

:::::

::::::

:::{prf:example}

1. "Ala ma kota. $\vee$ Jest pochmurno." oznacza zdanie
   "Ala ma kota lub jest pochmurno."

2. "$ 2 > 1 \vee -3 > 1$" oznacza zdanie, które słownie możemy
   zapisać jako "Liczba 2 lub liczba $-3$ jest większa od liczby 1."
:::

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

Jaka jest wartość logiczna zdania $p : 2 > 1 \vee -3 > 1$ ?
::::

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

$\LogicValue(p) = 1$, czyli zdanie jest prawdziwe.
:::

### Implikacja

::::::{prf:definition}

:::::{container} side-by-side

::::{container} column-three-fourth

**Implikacja** {index}`implikacja`, czyli sformułowanie "jeśli $\ldots$ to $\ldots$".
oznaczany symbolem **$\imply$**.

Implikacja $p \imply q$ jest fałszywa jedynie w przypadku,
gdy zdanie $p$ jest prawdziwe, a zdanie $q$ jest fałszywe;
w pozostałych przypadkach jest prawdziwa.

W implikacji $p\Rightarrow q$ zdanie:

- $p$ nazywamy **poprzednikiem** {index}`implikacja; poprzednik` implikacji,
- $q$ -- **następnikiem** {index}`implikacja; następnik` implikacji.

::::

::::{container} column-one-fourth

:::{list-table}
:class: table-auto-width
:header-rows: 1
:widths: 10 10 20

* - $p$
  - $q$
  - $p\imply q$
* - 1
  - 1
  - 1
* - 1
  - 0
  - 0
* - 0
  - 1
  - 1
* - 0
  - 0
  - 1
:::

::::

:::::

::::::

:::{prf:example}

1. "Ala ma kota. $\imply$ Jest pochmurno." oznacza zdanie
   "Jeśli Ala ma kota to jest pochmurno.", które możemy też zapisać
   "To, że Ala ma kota implikuje, że jest pochmurno."

2. "$ 1 > 2 \imply -3 > 1$" oznacza zdanie, które słownie możemy zapisać jako
   "Jeśli liczba 1 jest większa od liczby 2, to liczba $-3$ jest większa od liczby 1."
:::

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

Jaka jest wartość logiczna zdania $p : 1 > 2 \imply -3 > 1$ ?
::::

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

$\LogicValue(p) = 1$, czyli zdanie jest prawdziwe.
:::

:::{prf:example}

O ile wartości logiczne dla wcześniej zdefiniowanych
funktorów logicznych nie budzą zasadniczych wątpliwości, dla implikacji
nie są na pierwszy rzut oka zupełnie jasne.

Aby uzasadnić podaną definicję
rozważmy, prawdziwe dla każdej liczby $n\in\nn$,
zdanie

```{math}
"4|n \Rightarrow 2|n."
```

czyli "Jeśli liczba $n$ jest podzielna przez $4$, to jest podzielna przez $2 .$"
Zauważmy teraz, że:

1. dla $n=2$ poprzednik ma wartość logiczną $0$, następnik $1$
2. dla $n=3$ poprzednik ma wartość logiczną $0$, następnik $0$
3. dla $n=4$ poprzednik ma wartość logiczną $1$, następnik $1 .$

To pokazuje, że przyjęta przez nas definicja implikacji jest zgodna z oczekiwaniami.

:::

:::{prf:definition}

Jeśli prawdziwa jest implikacja $p\Rightarrow q$, to mówimy, że:

- $p$ jest **warunkiem wystarczającym** {index}`warunek; wystarczający`
lub **dostatecznym** {index}`warunek; dostateczny` dla $q$

- $q$ jest **warunkiem koniecznym** {index}`warunek; koniczny` dla $p .$
:::

::::{prf:example}

Wiadomo, że:

:::{container} center-text

_Jeśli $x$ jest liczbą parzystą, to $x$ jest liczbą całkowitą._

:::

1. Zatem wystarczy, że liczba będzie liczbą parzystą i to implikuje, że jest liczbą całkowitą.
   Innymi słowy,
   warunkiem wystarczającym na to by liczba była całkowita, jest to by była parzysta.

2. Podobnie, jeśli liczba jest parzysta, to koniecznie musi być liczbą całkowitą.
   Innymi słowy,
   warunkiem koniecznym na to by liczba była parzysta, jest
   aby była całkowita.
::::

:::{prf:definition}

Dla danej implikacji $p\Rightarrow q$ (którą nazywamy
**prostą**) {index}`implikacja; prosta`, implikację $q\Rightarrow p$ nazywamy
**odwrotną** {index}`implikacja; odwrotna`.
::::

### Równoważność

::::::{prf:definition}

:::::{container} side-by-side

::::{container} column-three-fourth

**Równoważność** {index}`równoważność`, czyli spójnik logiczny "wtedy i tylko wtedy, gdy",
oznaczany symbolem **$\Leftrightarrow$**.

Równoważność $p \Leftrightarrow q$ jest prawdziwa jedynie,
gdy zdania $p$ i$q$ mają tę samą wartość logiczną;
w pozostałych przypadkach jest fałszywa.

::::

::::{container} column-one-fourth

:::{list-table}
:class: table-auto-width
:header-rows: 1
:widths: 10 10 20

* - $p$
  - $q$
  - $p\Leftrightarrow q$
* - 1
  - 1
  - 1
* - 1
  - 0
  - 0
* - 0
  - 1
  - 0
* - 0
  - 0
  - 1
:::

::::

:::::

::::::

:::{prf:example}

1. "Ala ma kota. $\Leftrightarrow$ Jest pochmurno." oznacza zdanie
   "Ala ma kota wtedy i tylko wtedy, gdy jest pochmurno."
   lub
   "To, że Ala ma kota jest równoważne temu, że jest pochmurno."

2. "$ 2 > 1 \Leftrightarrow -3 > 1$" oznacza zdanie, które słownie możemy
   zapisać jako
   "2 jest większa od 1 wtedy i tylko wtedy, gdy $-3$ jest większa od 1."
:::

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

Jaka jest wartość logiczna zdania $p : 2 > 1 \Leftrightarrow -3 > 1$ ?
::::

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

$\LogicValue(p) = 0$, czyli zdanie jest fałszywe.
:::

:::{prf:definition}

Jeśli prawdziwa jest równoważność $p\Leftrightarrow q$ to mówimy,
że $p$ jest **warunkiem koniecznym i wystarczającym** {index}`warunek; konieczny i wystarczający`
dla $q .$
:::

### Negacja

::::::{prf:definition}

:::::{container} side-by-side

::::{container} column-three-fourth

**Negacja** {index}`negacja`, czyli sformułowanie "nieprawda, że",
oznaczany symbolem **$\Negation$** lub **$\neg$**.

Jeśli zdanie $p$ jest prawdziwe to $\Negation p$ jest fałszywe;
jeśli zdanie $p$ jest fałszywe to $\Negation p$ jest prawdziwe.

::::

::::{container} column-one-fourth

:::{list-table}
:class: table-auto-width
:header-rows: 1
:widths: 10 20

* - $p$
  - $\Negation p$
* - 1
  - 0
* - 0
  - 1
:::

::::

:::::

::::::

:::{prf:example}

1. "$\Negation$ Dwa plus dwa równa się siedem." oznacza zdanie
   "Nieprawda, że dwa plus dwa równa się siedem."

2. "$\Negation 2 < 1$" jest równoważne zdaniu "$2 \geq 1$".

3. "$\Negation -3 \neq 1$" jest równoważne zdaniu "$-3 = 1$".
:::

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

Jaka jest wartość logiczna zdań:

:::{container} columns-2-auto

1. $\Negation -3 \neq 1$
2. $((\Negation 5 \neq 1) \Leftrightarrow \sin\pi = 0) \imply \sqrt 2 > 1$
3. $(\Negation 5 \neq 1) \Leftrightarrow (\sin\pi = 0 \imply \sqrt 2 > 1)$
4. $(\Negation (5 \neq 1 \Leftrightarrow \sin\pi = 0)) \imply \sqrt 2 > 1$ ?

:::

::::

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

1. fałsz
2. prawda
3. fałsz
4. prawda
:::

## Prawa rachunku zdań

:::{prf:definition}

**Prawami rachunku zdań** {index}`prawo rachunku zdań` (lub **tautologiami** {index}`tautologia`)
nazywamy formułę zdaniową, która jest prawdziwa dla każdego wartościowania
występujących w niej zdań.

**Równoważnymi** {index}`zdanie logiczne; równoważne`
nazwiemy zdania logiczne $\Phi$ i $\Psi$,
jeśli tautologią jest zdanie $\Phi \Leftrightarrow \Psi .$
:::

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

Sprawdźmy, czy tautologią jest formuła:

:::{container} columns-2-auto

1. $[(p \Rightarrow q) \wedge p] \Rightarrow q$
2. $p \Rightarrow [(\Negation p) \vee q]$?

:::

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

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

::::

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

1. **Metoda 1.**

   Można to zrobić przy pomocy metody zero-jedynkowej:

   :::{list-table}
   :widths: 10 10 20 20 15
   :header-rows:

   * - $p$
     - $q$
     - $r = (p\Rightarrow q)$
     - $s = (r \wedge p)$
     - $s \Rightarrow q$
   * - 1
     - 1
     - 1
     - 1
     - 1
   * - 1
     - 0
     - 0
     - 0
     - 1
   * - 0
     - 1
     - 1
     - 0
     - 1
   * - 0
     - 0
     - 1
     - 0
     - 1

   :::

   Ponieważ w ostatniej kolumnie (która odzwierciedla wartości logiczne formuły z przykładu)
   pojawiła się tylko wartość $1$, to wnioskujemy, że omawiana formuła jest tautologią.

   **Metoda 2.**

   Często łatwiej jest posłużyć się metodą uproszczoną:

   - Ponieważ głównym spójnikiem logicznym naszej formuły jest implikacja, to wiemy, że
     wartość 0 pojawi się jedynie, gdy $s = [(p \Rightarrow q) \wedge p]$ przyjmie wartość 1 i
     jednocześnie $q$ przyjmie wartość 0.

   - Dalej, $s$ jako koniunkcja jest prawdziwe pod warunkiem, że zdania
     $p \Rightarrow q$ i $p$ są prawdziwe.

   - Z drugiej strony, skoro $q$ jest fałszywe,
     to co najmniej jedno ze zdań $p \Rightarrow q$, $p$ jest fałszywe.

   Zachodzi zatem sprzeczność, więc nie istnieją wartości logiczne zdań $p$ i $q$,
   dla których $[(p \Rightarrow q) \wedge p] \Rightarrow q$ byłoby fałszywe.
   Stąd rozpatrywana formuła jest tautologią.

2. Korzystając z jednej z podanych wyżej metod łatwo dojść do wniosku, 
   że dla $p=1$ i $q=0$ formuła jest fałszywa. Zatem to nie jest tautologia.
::::

:::{prf:theorem}

Dla dowolnych zdań logicznych $p, q,r$ następujące zdania są tautologiami:

1. $(p\wedge p) \Leftrightarrow p \quad$
   oraz
   $\quad p \Leftrightarrow (p\vee p ) \quad$
   -- _prawa idempotentności_

2. $\Negation(\Negation p) \Leftrightarrow p \quad$
   -- _prawo podwójnej negacji_

3. $p\vee (\Negation p)\quad$
   -- _prawo wyłączonego środka_

4. $\Negation(p\wedge(\Negation p)) \quad$
   -- _prawo sprzeczności_

5. **$\Negation(p\wedge q) \Leftrightarrow (\Negation p) \vee (\Negation q) \quad$**
   oraz **$\quad \Negation(p\vee q)\Leftrightarrow (\Negation p) \wedge(\Negation q) \quad$**
   -- _prawa de Morgana_

6. **$(p\Rightarrow q)\Leftrightarrow ((\Negation q)\Rightarrow (\Negation p)) \quad$**
   -- _prawo kontrapozycji_

7. **$\Negation(p\Rightarrow q)\Leftrightarrow (p\wedge (\Negation q)) \quad$**
   -- _prawo negacji implikacji_

8. $p\wedge q \Leftrightarrow q \wedge p \quad$ oraz
   $\quad p\vee q \Leftrightarrow q \vee p \quad$
   -- _prawa przemienności_

9. $p\wedge (q\wedge r) \Leftrightarrow (p\wedge q)\wedge r \quad$ oraz
   $\quad p\vee (q\vee r) \Leftrightarrow (p\vee q)\vee r \quad$
   -- _prawa łączności_

10. **$p\wedge (q\vee r) \Leftrightarrow (p\wedge q)\vee (p\wedge r) \quad$**
-- _prawo rozdzielności koniunkcji względem alternatywy_

11. **$p\vee (q\wedge r) \Leftrightarrow (p\vee q)\wedge (p\vee r) \quad$**
-- _prawo rozdzielności alternatywy względem koniunkcji_

12. $((p\Rightarrow q)\wedge(q\Rightarrow r))\Rightarrow(p\Rightarrow r) \quad$
-- _prawo przechodniości implikacji_

13. **$(p \Leftrightarrow q) \Leftrightarrow ((p \imply q) \wedge (q \imply p))$**
:::

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

Pokażmy, że tautologią jest formuła

$$
(p\Rightarrow q) \Leftrightarrow (\Negation p)\vee q.
$$

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

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

::::

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

Z praw podwójnej negacji, negacji implikacji, de Morgana i przechodniości implikacji:

$$
(p\Rightarrow q) \quad\Leftrightarrow\quad
\Negation(\Negation(p\Rightarrow q)) \quad\Leftrightarrow\quad
\Negation(p\wedge (\Negation q)) \quad\Leftrightarrow\quad
(\Negation p)\vee q.
$$
:::

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

Znajdźmy
formułę zawierającą jedynie funktory: koniunkcji, alternatywy, negacji
równoważną formule

$$
(p\Leftrightarrow q) \vee [(\Negation p)\Rightarrow q].
$$
::::

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

Korzystamy kolejno z praw rachunku zdań:

```{math}
\begin{aligned}
(p\Leftrightarrow q)   & \vee  [(\Negation p)\Rightarrow q]
  \\
  ((p \imply q) \wedge (q \imply p)) & \vee  [(\Negation p)\Rightarrow q]
\\
  (((\Negation p) \vee q) \wedge ((\Negation q) \vee p)) & \vee   p \vee q
\end{aligned}
```

:::