Logika matematyczna I

2. 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ą).

2.1. Zdania logiczne#

Definicja 2.1

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.

Przykład 2.1

  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.

    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 .\)

Definicja 2.2

Wartość logiczną zdania \(p\) zapisujemy jako \(\LogicValue(p) .\)

2.2. 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 , a następnik tezą twierdzenia .

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

2.2.1. Koniunkcja#

Definicja 2.3

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 .

\(p\)

\(q\)

\(p\wedge q\)

1

1

1

1

0

0

0

1

0

0

0

0

Przykład 2.2

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

Ćwiczenie 2.1

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

Odpowiedź

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

2.2.2. Alternatywa#

Definicja 2.4

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 .

\(p\)

\(q\)

\(p\vee q\)

1

1

1

1

0

1

0

1

1

0

0

0

Przykład 2.3

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

Ćwiczenie 2.2

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

Odpowiedź

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

2.2.3. Implikacja#

Definicja 2.5

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 implikacji,

  • \(q\) – następnikiem implikacji.

\(p\)

\(q\)

\(p\imply q\)

1

1

1

1

0

0

0

1

1

0

0

1

Przykład 2.4

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

Ćwiczenie 2.3

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

Odpowiedź

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

Przykład 2.5

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

\["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.

Definicja 2.6

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

  • \(p\) jest warunkiem wystarczającym lub dostatecznym dla \(q\)

  • \(q\) jest warunkiem koniecznym dla \(p .\)

Przykład 2.6

Wiadomo, że:

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.

Definicja 2.7

Dla danej implikacji \(p\Rightarrow q\) (którą nazywamy prostą) , implikację \(q\Rightarrow p\) nazywamy odwrotną .

2.2.4. Równoważność#

Definicja 2.8

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.

\(p\)

\(q\)

\(p\Leftrightarrow q\)

1

1

1

1

0

0

0

1

0

0

0

1

Przykład 2.7

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

Ćwiczenie 2.4

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

Odpowiedź

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

Definicja 2.9

Jeśli prawdziwa jest równoważność \(p\Leftrightarrow q\) to mówimy, że \(p\) jest warunkiem koniecznym i wystarczającym dla \(q .\)

2.2.5. Negacja#

Definicja 2.10

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.

\(p\)

\(\Negation p\)

1

0

0

1

Przykład 2.8

  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\)”.

Ćwiczenie 2.5

Jaka jest wartość logiczna zdań:

  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\) ?

Odpowiedź

  1. fałsz

  2. prawda

  3. fałsz

  4. prawda

2.3. Prawa rachunku zdań#

Definicja 2.11

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

Równoważnymi nazwiemy zdania logiczne \(\Phi\) i \(\Psi\), jeśli tautologią jest zdanie \(\Phi \Leftrightarrow \Psi .\)

Ćwiczenie 2.6

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

  1. \([(p \Rightarrow q) \wedge p] \Rightarrow q\)

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

Informacja

Pomoże rozwiązać Ćw. 2.9, Ćw. 2.12, Ćw. 2.14.

Rozwiązanie

  1. Metoda 1.

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

    \(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.

Twierdzenie 2.1

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

Ćwiczenie 2.7

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

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

Informacja

Pomoże rozwiązać Ćw. 2.13, Ćw. 2.14.

Rozwiązanie

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. \]

Ćwiczenie 2.8

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

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

Rozwiązanie

Korzystamy kolejno z praw rachunku zdań:

\[\begin{split}\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}\end{split}\]