2. Logika#
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
„Dwa plus dwa równa się cztery.” jest zdaniem logicznym.
Na gruncie zwykłej arytmetyki przypiszemy mu wartość logiczną 1.
„Ala ma kota.” jest zdaniem logicznym.
Wartość logiczna tego zdania powinna odzwierciedlać naszą wiedzę na temat tego, czy Ala ma kota.
„Czy to jest zrozumiałe?” nie jest zdaniem logicznym - nie jest zdaniem oznajmującym.
„Ach, jak tu pięknie!”, „Otwórz okno!” również nie są zdaniami logicznymi.
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 .\)
„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, zaczynając od: \(p, q, r, s .\)
2.2. Funktory zdaniotwórcze#
Narration
Zdania złożone budujemy ze zdań prostych za pomocą spójników logicznych (funktorów zdaniotwórczych) .
Definicja 2.2
Dla zdań \(p, q\) definiujemy:
negację: \(\quad \Negation p\) („nieprawda, że \(p\)”)
koniunkcję: \(\quad p\wedge q\) (”\(p\) i \(q\)”)
alternatywę: \(\quad p\vee q\) (”\(p\) lub \(q\)”)
implikację: \(\quad p \imply q\) („jeśli \(p\), to \(q\)”)
równoważność: \(\quad p\Leftrightarrow q\) (”\(p\) wtedy i tylko wtedy, gdy \(q\)”)
których wartościowanie określamy zgodnie z tabelą:
\(p\) |
\(q\) |
\(\Negation p\) |
\(p\wedge q\) |
\(p\vee q\) |
\(p \imply q\) |
\(p\Leftrightarrow q\) |
|---|---|---|---|---|---|---|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
W koniunkcji zdania \(p\) i \(q\) nazywają się czynnikami.
W alternatywie zdania \(p\) i \(q\) nazywają się składnikami.
W implikacji \(p\Rightarrow q\) zdanie:
\(p\) nazywamy poprzednikiem
\(q\) – następnikiem.
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 .\)
Dla danej implikacji \(p\Rightarrow q\) (którą nazywamy prostą) , implikację \(q\Rightarrow p\) nazywamy odwrotną .
Przykład 2.2
Ze zdań prostych „Ala ma kota.” i „Jest pochmurno.” możemy utworzyć zdania złożone:
„\(\Negation\) Ala ma kota.”, które możemy odczytać jako „Nieprawda, że Ala ma kota”, czyli w skrócie „Ala nie ma kota.”
„Ala ma kota. \(\wedge\) Jest pochmurno.”, czyli w skrócie zdanie „Ala ma kota i jest pochmurno.”
„Ala ma kota. \(\vee\) Jest pochmurno.”, czyli w skrócie zdanie „Ala ma kota lub jest pochmurno.”
„Ala ma kota. \(\imply\) Jest pochmurno.”, czyli w skrócie zdanie „Jeśli Ala ma kota to jest pochmurno.”, które możemy też zapisać „To, że Ala ma kota implikuje, że jest pochmurno.”
„Ala ma kota. \(\Leftrightarrow\) Jest pochmurno.”, czyli w skrócie 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.”
Uwaga 2.1
Budując zdania złożone z wieloma spójnikami, ograniczamy liczbę nawiasów, przyjmując priorytety (od najsilniej wiążącego):
Przykład 2.3
Dzięki priorytetom zdanie
zapiszemy krócej jako
Podstawiając \(p=0,\ q=1\) otrzymamy kolejno:
czyli dla tego wartościowania zdanie jest fałszywe.
2.3. Tautologie i prawa rachunku zdań#
Definicja 2.3
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 .\)
Przykład 2.4
Prawo Dunsa Szkota \(\quad p \imply(\Negation p \imply q) \quad\) jest tautologią:
\(p \) |
\( q\) |
\(\Negation p \) |
\(\Negation p \imply q\) |
\(p \imply (\Negation p \imply q)\) |
|---|---|---|---|---|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
W ostatniej kolumnie występują same jedynki, więc formuła jest tautologią.
Prawo to mówi, że z dwóch zdań wzajemnie sprzecznych, \(p\) oraz \(\Negation p\), można wywnioskować dowolne zdanie \(q .\)
Twierdzenie 2.1
Dla dowolnych zdań logicznych \(p, q,r\) następujące zdania są tautologiami:
\((p\wedge p) \Leftrightarrow p \quad\) oraz \(\quad p \Leftrightarrow (p\vee p ) \quad\) – prawa idempotentności
\(\Negation(\Negation p) \Leftrightarrow p \quad\) – prawo podwójnej negacji
\(p\vee (\Negation p)\quad\) – prawo wyłączonego środka
\(\Negation(p\wedge(\Negation p)) \quad\) – prawo sprzeczności
\(\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
\((p\Rightarrow q)\Leftrightarrow ((\Negation q)\Rightarrow (\Negation p)) \quad\) – prawo kontrapozycji
\(\Negation(p\Rightarrow q)\Leftrightarrow (p\wedge (\Negation q)) \quad\) – prawo negacji implikacji
\(p\wedge q \Leftrightarrow q \wedge p \quad\) oraz \(\quad p\vee q \Leftrightarrow q \vee p \quad\) – prawa przemienności
\(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
\(p\wedge (q\vee r) \Leftrightarrow (p\wedge q)\vee (p\wedge r) \quad\) – prawo rozdzielności koniunkcji względem alternatywy
\(p\vee (q\wedge r) \Leftrightarrow (p\vee q)\wedge (p\vee r) \quad\) – prawo rozdzielności alternatywy względem koniunkcji
\(((p\Rightarrow q)\wedge(q\Rightarrow r))\Rightarrow(p\Rightarrow r) \quad\) – prawo przechodniości implikacji
\((p \Leftrightarrow q) \Leftrightarrow ((p \imply q) \wedge (q \imply p))\)
2.4. Postać normalna#
Definicja 2.4
Formułę zdaniową zapisaną w postaci
a \(p_{ij}\) są zdaniami prostymi lub ich zaprzeczeniami, nazywamy postacią normalną alternatywno-koniunkcyjną (dysjunkcyjną).
Twierdzenie 2.2
Korzystając z praw rachunku zdań, każdą formułę zdaniową można sprowadzić do postaci normalnej alternatywno-koniunkcyjnej.
Ćwiczenie 2.1
Sprowadźmy formułę \( \Negation \big( (p \imply q) \land (r \Leftrightarrow \Negation s) \big) \) do postaci normalnej alternatywno-koniunkcyjnej.
Rozwiązanie
Poniżej wykonujemy przekształcenia, za każdym razem otrzymując formuły równoważne:
W kolejnych krokach:
Eliminujemy spójniki: Zastępujemy implikację alternatywą (\(p \imply q \equiv \Negation p \lor q\)) oraz rozbijamy równoważność na alternatywę dwóch koniunkcji.
Stosujemy I prawo de Morgana: Zamieniamy negację głównej koniunkcji na alternatywę zanegowanych składników.
Ponownie wykorzystujemy prawa de Morgana: Wprowadzamy negację do wnętrza nawiasów, zmieniając spójniki na przeciwne (koniunkcję na alternatywę i odwrotnie).
Upraszczamy podwójną negację: Usuwamy powtarzające się zaprzeczenia przy zmiennych \(p\), \(r\) oraz \(s\), przywracając ich pierwotną formę.
Stosujemy prawo rozdzielności: Rozdzielamy koniunkcję względem alternatywy („mnożymy nawiasy”), aby uzyskać strukturę sumy iloczynów.
Redukujemy sprzeczności: Wykreślamy człony typu \(a \land \Negation a\) (fałsz), ponieważ nie zmieniają one wyniku całej alternatywy.
Otrzymujemy postać normalną: Zapisujemy finalną formułę jako alternatywę trzech koniunkcji.
2.5. 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 2.5
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 2.5
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.
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 2.6
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
Przykład 2.6
Rozważmy formę zdaniową
zmiennej \(x\in \rr .\) Możemy zastosować do niej prawa rachunku zdań:
Stąd \( \quad \PredicateGraph \varphi = \Set{x\in \rr : \varphi(x)} =(-\infty, -2]\cup [0, +\infty); \)
Narration
Niech \(X_1, X_2, \ldots, X_n\) będą zbiorami niepustymi.
Definicja 2.7
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 2.7
Forma zdaniowa
dwóch zmiennych \(x, y \in \rr\)
2.6. Kwantyfikatory#
Definicja 2.8
Kwantyfikator ogólny , oznaczany symbolem \(\forall\), oznacza „dla każdego …”:
Zdanie „\(\forall x \in X\; \varphi(x)\)” jest prawdziwe, jeśli wyrażenie \(\varphi(x)\) jest prawdziwe dla wszystkich \(x \in X\), czyli
Definicja 2.9
Kwantyfikator egzystencjalny , oznaczany symbolem \(\exists\), oznacza „istnieje …”:
Zdanie „\(\exists x \in X\; \varphi(x)\)” jest prawdziwe, jeśli wyrażenie \(\varphi(x)\) jest prawdziwe dla przynajmniej jednego \(x \in X\), czyli
Przykład 2.8
Zdanie \(\quad \Forall {x \in \rr} x^2\geq 0 \quad\) jest prawdziwe – każda liczba rzeczywista podniesiona do kwadratu jest nieujemna.
Zdanie \(\quad \Exists{x\in \rr} x^2 + 1 = 0 \quad\) jest fałszywe – wielomian \(x^2 + 1\) nie ma pierwiastków rzeczywistych.
Uwaga 2.2
Gdy zakres zmienności \(X\) formy zdaniowej zmiennej \(x\) jest określony, to:
Definicja 2.10
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.
Twierdzenie 2.3
Dla dowolnego zbioru niepustego \(X\) i zmiennej \(x\in X\), następujące formuły są prawami rachunku kwantyfikatorów:
\(\Forall{x} \varphi(x) \Rightarrow \exists x\; \varphi(x)\)
\(\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
\(\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
\(\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.
Twierdzenie 2.4
Dla dowolnych zbiorów niepustych \(X, Y\) i zmiennych \(x\in X\), \(y\in Y\), mamy następujące prawa przemienności kwantyfikatorów:
\(\Exists{x} \Exists{y} \varphi(x,y) \Leftrightarrow \Exists{y} \Exists{x} \varphi(x,y)\)
\(\Forall{x} \Forall{y} \varphi(x,y) \Leftrightarrow \Forall{y} \Forall{x}\varphi(x,y)\)
\(\Exists{x} \Forall{y} \varphi(x,y) \Rightarrow \Forall{y} \Exists{x} \varphi(x,y)\).
Przykład 2.9
W punkcie 3. z Tw. 2.4 implikacja przeciwna nie musi być prawdziwa:
zdanie \(\quad \Forall {y\in \rr} \Exists{ x\in \rr} x > y \quad\) jest prawdziwe – dla danego \(y\) wystarczy wziąć \(x=y+1\)
zdanie \(\quad \Exists {x\in \rr} \Forall {y\in \rr} x > y \quad\) jest fałszywe – nie istnieje liczba rzeczywista większa od wszystkich innych.
2.7. Dowodzenie twierdzeń#
Narration
Typowe twierdzenie ma postać implikacji \( P \imply Q \), gdzie \(P\) to założenie, a \(Q\) – teza.
2.7.1. Dowód wprost (\(P \imply Q\))#
Narration
Dowód wprost to najbardziej naturalna metoda dowodzenia. Zakładamy w nim prawdziwość założenia \(P\) i używając logicznych kroków, algebry lub definicji, dochodzimy bezpośrednio do wniosku \(Q\).
Przykład 2.10
Stwierdzenie 2.5
Jeśli \(n\) jest liczbą nieparzystą, to \(n^2\) jest liczbą nieparzystą.
Dowód
Zakładamy \(P\): Niech \(n\) będzie dowolną liczbą nieparzystą. Z definicji możemy zapisać \(n = 2k + 1\) dla pewnej liczby całkowitej \(k .\)
Obliczamy \(n^2\):
\[n^2 = (2k + 1)^2 = 4k^2 + 4k + 1\]Przekształcamy wzór: Wyciągamy dwójkę przed nawias z pierwszych dwóch składników:
\[n^2 = 2(2k^2 + 2k) + 1\]Wniosek (\(Q\)): Ponieważ \((2k^2 + 2k)\) jest liczbą całkowitą, to \(n^2\) ma postać \(2 \cdot (\text{liczba całkowita}) + 1\), czyli z definicji jest liczbą nieparzystą.
2.7.2. Dowód przez transpozycję (\(\Negation Q \imply \Negation P\))#
Narration
Dowód przez transpozycję polega na udowodnieniu zdania \(P \imply Q\) poprzez udowodnienie zdania do niego równoważnego: \(\Negation Q \imply \Negation P\).
Zamiast pokazywać, że
Jeśli zachodzi \(P\), to zachodzi \(Q\),
pokazujemy, że
Jeśli nie zachodzi \(Q\), to nie zachodzi \(P\).
Przykład 2.11
Stwierdzenie 2.6
Jeśli \(n^2\) jest liczbą nieparzystą, to \(n\) jest liczbą nieparzystą.
Dowód
Zamieniamy twierdzenie na zdanie przeciwstawne:
Jeśli \(n\) jest liczbą parzystą (\(\Negation Q\)), to \(n^2\) jest liczbą parzystą (\(\Negation P\)).
Zakładamy, że \(n\) jest parzyste. Z definicji możemy zapisać \(n = 2k\) dla pewnej liczby całkowitej \(k .\)
Podnosimy obie strony do kwadratu:
\[n^2 = (2k)^2 = 4k^2 = 2(2k^2)\]Ponieważ \(2k^2\) jest liczbą całkowitą, to \(n^2\) wyraża się jako wielokrotność liczby 2 – a więc \(n^2\) jest liczbą parzystą.
Wykazanie zdania \(\Negation Q \imply \Negation P\) automatycznie dowodzi prawdziwości pierwotnego twierdzenia \(P \imply Q .\)
2.7.3. Dowód nie wprost#
Narration
Dowód nie wprost (reductio ad absurdum) polega na założeniu, że twierdzenie \(\alpha\), które chcemy udowodnić, jest fałszywe, a następnie wywiedzeniu z tego założenia nieprawdy. Owa nieprawda najczęściej przyjmuje w dowodzie postać sprzeczności \(\Negation \beta \wedge \beta\), dla pewnego zdania \(\beta\).
Formalnie, korzystamy z tego, że jeśli zdanie
jest prawdziwe, to koniecznie \(\Negation \alpha\) jest fałszywe, a więc \(\alpha\) jest prawdziwe.
Przykład 2.12
Lemat 2.7
Liczba \(\sqrt{2}\) jest niewymierna.
Dowód
Zakładamy nieprawdę: Załóżmy nie wprost, że \(\sqrt{2}\) jest liczbą wymierną. Oznacza to, że da się ją zapisać w postaci ułamka nieskracalnego:
\[\sqrt{2} = \frac{a}{b}\]gdzie \(a\) i \(b\) są dodatnimi liczbami całkowitymi, a ułamek jest maksymalnie uproszczony – czyli \(a\) i \(b\) nie mają wspólnych dzielników oprócz 1 (są względnie pierwsze).
Przekształcamy równanie: Podnosimy obie strony do kwadratu:
\[2 = \frac{a^2}{b^2} \implies a^2 = 2b^2\]Wnioskujemy o liczbie \(a\): Ponieważ \(a^2 = 2b^2\), to \(a^2\) jest liczbą parzystą. Z właściwości liczb całkowitych wynika, że skoro kwadrat liczby jest parzysty, to sama liczba \(a\) również musi być parzysta. Możemy więc zapisać \(a = 2k\) dla pewnej liczby całkowitej \(k .\)
Podstawiamy \(a = 2k\) do równania:
\[(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2\]Wnioskujemy o liczbie \(b\): Skoro \(b^2 = 2k^2\), to \(b^2\) jest liczbą parzystą. Stąd wynika, że sama liczba \(b\) również jest parzysta.
Sprzeczność: Otrzymaliśmy wynik, że zarówno \(a\), jak i \(b\) są liczbami parzystymi (dzielą się przez 2). To jest sprzeczne z założeniem z punktu 1, w którym przyjęliśmy, że ułamek \(\frac{a}{b}\) jest nieskracalny (że \(a\) i \(b\) nie mają wspólnych dzielników).
Wniosek: Nasze wstępne założenie, że \(\sqrt{2}\) jest liczbą wymierną, doprowadziło do logiki bez wyjścia. Zatem \(\sqrt{2}\) musi być liczbą niewymierną.
2.7.4. Dowód niekonstruktywny#
Narration
Dla niektórych twierdzeń nie da się znaleźć bezpośredniego dowodu wprost ani kontrapozycji – wtedy często stosuje się inne techniki, np. dowód przez wyczerpanie przypadków (wykorzystując prawo wyłączonego środka).
Przykład 2.13
Twierdzenie 2.8
Istnieją liczby niewymierne \(a\) i \(b\) takie, że \(a^b\) jest liczbą wymierną.
Dowód
Aby to udowodzić, rozważmy zdanie \(p\):
\(\sqrt{2}^{\sqrt{2}}\) jest liczbą wymierną.
Z prawa \(p \vee \Negation p\) wnioskujemy, że zdanie \(p\) jest prawdziwe albo fałszywe.
Jeśli \(p\) jest prawdziwe, wystarczy wziąć \(a = b = \sqrt{2} .\)
Jeśli \(p\) jest fałszywe (czyli \(\sqrt{2}^{\sqrt{2}}\) jest niewymierna), to biorąc \(a = \sqrt{2}^{\sqrt{2}},\ b=\sqrt{2}\), mamy
\[ \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}=\sqrt{2}^{\sqrt{2}\cdot \sqrt{2}}=\sqrt{2}^2=2\in \qq, \]więc znów znaleźliśmy szukaną parę.
W obu przypadkach odpowiedź brzmi TAK – ale dowód jest niekonstruktywny: nie rozstrzyga, która z liczb \(a\) faktycznie działa, tzn. czy \(\sqrt{2}^{\sqrt{2}}\) jest wymierna czy nie.