Na tym wykładzie omówimy zdania logiczne, tautologie, tabelki wartości logicznych, formy zdaniowe, kwantyfikatory oraz wspomnimy o dowodach formalnych.
Zanim przejdziemy do wykładu, parę słów wstępnych. Każda dyscyplina naukowa posługuje się charakterystycznym dla niej językiem. Język ten jest specyficzny przede wszystkim dlatego, że słowa zaczerpnięte z języka mówionego w słowniku danej dyscypliny mają często znaczenie bardzo zawężone, a czasem całkiem odmienne od znaczenia pierwotnego. Przykładem takiej zmiany znaczenia może być słowo „ciało”, które ma inne znaczenie w medycynie, inne w fizyce, i jeszcze inne w matematyce. Takie zawężenie znaczenia, czy nadanie znaczenia całkiem nowego jakiemuś pojęciu nazywamy definiowaniem. Jest rzeczą zrozumiałą, że należy ustalić reguły posługiwania się językiem mówionym w nauce, by nie dochodziło do nieporozumień. Konieczność rozpoczynania wszelkiej nauki od ustalenia takich reguł została dostrzeżona już przez Arystotelesa1, dając początek dyscyplinie naukowej zwanej dziś logiką (logos oznacza po grecku słowo). Głównym zadaniem logiki jest ustalenie (stworzenie) reguł wnioskowania dla danej dziedziny nauki – na przykład matematyki, prawa, bądź filozofii. Na tym wykładzie zajmiemy pewnymi fragmentami logiki matematycznej. Na początku wprowadzimy pewne podstawowe pojęcia logiczne, którymi będziemy posługiwać się w dalszych częściach wykładu.
Zacznijmy od pojęcia zdania logicznego.
W języku mówionym zdaniami nazywamy wypowiedzi typu: dziś jest piątek, czy już wróciłaś do domu?, nie lubię szarlotki, wchodzisz czy wychodzisz? dwa dzieli siedem, Kraków jest miastem.
Zauważmy, że nie o każdym z tych zdań można powiedzieć, że jest prawdziwe lub fałszywe.
Takie zdanie oznajmujące, któremu (przynajmniej potencjalnie) możemy przyporządkować ocenę - prawda lub fałsz, czyli możemy powiedzieć, czy zdanie jest prawdziwe czy fałszywe nazywamy zdaniem logicznym.
A zatem, zdanie czy wróciłaś już do domu? nie jest zdaniem logicznym, zdanie dwa dzieli siedem jest zdaniem logicznym (fałszywym), Kraków jest miastem jest zdaniem logicznym prawdziwym, a prawdziwość zdania logicznego dziś jest piątek zależy od dnia tygodnia, w którym je wypowiadamy. Ciekawym przykładem jest zdanie podczas bitwy pod Grunwaldem jednego z rycerzy bolało prawe ucho. Nikt obecnie nie jest w stanie powiedzieć, czy było tak rzeczywiście, niemniej, potencjalnie, gdybyśmy mogli cofnąć się w czasie i zapytać rycerzy o stan uszu, zdanie uzyskałoby status prawdziwego bądź fałszywego. To zdanie jest zatem zdaniem logicznym.
Zdania logiczne oznaczamy najczęściej małymi literami \(p,q,r\ldots \). Mając dane zdanie logiczne \(p\) możemy przyporządkować mu tak zwaną wartość logiczną, \(w(p)\), gdzie \(w(p)=1\) jeśli \(p\) jest zdaniem prawdziwym, \(w(p)=0\) gdy \(p\) jest zdaniem fałszywym.
Jeśli za litery \(p,q,r,\ldots \) podstawiamy dowolne zdanie logiczne to mówimy, że \(p,q,r,\ldots \) są zmiennymi zdaniowymi.
Jeśli mamy dane zdania logiczne, możemy tworzyć nowe zdania logiczne (zwane też formułami zdaniowymi), za pomocą tak zwanych spójników logicznych, zwanych spójnikami zdaniotwórczymi. W języku mówionym też tak, oczywiście, postępujemy, mówiąc na przykład: dziś jest niedziela i dziś na obiad będą kotlety schabowe (spójnik „i”), czy też: sprzedajemy auta na benzynę lub sprzedajemy auta na olej napędowy (spójnik „lub”).
Przy tworzeniu zdań logicznych używamy najczęściej następujących spójników: jednoargumentowego spójnika zaprzeczenia, spójników dwuargumentowych: i, lub, albo, wynika (implikuje), jest równoważne. Oznaczamy (i nazywamy) je następująco:
Jeśli ze zdań logicznych utworzymy za pomocą spójników nowe zdanie logiczne, to musimy tym nowym zdaniom przypisać wartość logiczną.
Bardziej formalnie mówiąc, spójniki logiczne \(n\)-argumentowe możemy traktować jako funkcje, które układowi \((e_1,\dots e_n)\), gdzie \(e_j\in \{0,1\}\) przypisują wartość \(0\) lub \(1\).
Trzeba zatem określić jakie wartości przyjmują zdania z wypisanymi wyżej spójnikami. Najwygodniej będzie to zrobić za pomocą tabelek wartości logicznych. Zdanie \(p\) może mieć wartość logiczną \(0\) lub \(1\), zapisujemy to następująco
| \(p\) |
| 0 |
| 1 |
Jeśli \(p\) ma wartość logiczną \(1\) (względnie \(0\)), to jego zaprzeczenie, \(\neg p\) ma wartość logiczną \(0\) (względnie \(1\)). Zapisujemy to w tabelce następująco:
| \(p\) | \(\neg p\) |
| 0 | 1 |
| 1 | 0 |
Przykład 1. Zdanie \(\neg p\) czytamy jako nieprawda, że \(p\). Zdanie Kraków jest miastem jest prawdziwe, zdanie nieprawda, że Kraków jest miastem jest fałszywe.
Koniunkcja \(p \wedge q\) dwóch zdań \(p\) i \(q\), jest prawdziwa tylko jeśli oba są prawdziwe:
| \(p\) | \(q\) | \(p \wedge q\) |
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
Przykład 2. Zdania dwa dzieli sześć oraz trzy dzieli sześć są oba prawdziwe, zatem prawdziwe też jest zdanie dwa dzieli sześć i trzy dzieli sześć.
Alternatywa \(p \vee q\) dwóch zdań \(p\) i \(q\), jest prawdziwa jeśli chociaż jedno ze zdań jest prawdziwe:
| \(p\) | \(q\) | \(p \vee q\) |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
Przykład 3. Zdania dwa dzieli sześć oraz trzy dzieli sześć są oba prawdziwe, zdanie cztery dzieli sześć jest nieprawdziwe. Alternatywy dwa dzieli sześć lub trzy dzieli sześć oraz dwa dzieli sześć lub cztery dzieli sześć są obie prawdziwe.
Alternatywa rozłączna \(p \dvee q\) dwóch zdań \(p\) i \(q\), jest prawdziwa jeśli dokładnie jedno ze zdań jest prawdziwe:
| \(p\) | \(q\) | \(p \dvee q\) |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
Przykład 4. Zdanie \(p \dvee q\) czytamy jako \(p\) albo \(q\). Tak jak w poprzednim przykładzie, zdania dwa dzieli sześć oraz trzy dzieli sześć są prawdziwe, a zdanie cztery dzieli sześć jest nieprawdziwe, zatem zdanie dwa dzieli sześć albo trzy dzieli sześć jest nieprawdziwe, natomiast dwa dzieli sześć albo cztery dzieli sześć jest prawdziwe.
Zdanie \(p \Longrightarrow q\) nazywamy implikacją. Czytamy z \(p\) wynika \(q\) lub \(p\) implikuje \(q\). Zdanie \(p\) nazywamy poprzednikiem, a zdanie \(q\) następnikiem implikacji. Implikacja jest fałszywa tylko jeśli zdanie \(p\) jest prawdziwe, a zdanie \(q\) fałszywe (co odzwierciedla rozsądną zasadę, że z prawdziwych przesłanek nie powinny wynikać fałszywe wnioski).
| \(p\) | \(q\) | \(p \Longrightarrow q\) |
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
Przykład 5. Zdanie Moskwa leży na zachód od Warszawy jest nieprawdziwe, ale oba zdania: jeśli Moskwa leży na zachód od Warszawy to Berlin leży na wschód od Warszawy oraz jeśli Moskwa leży na zachód od Warszawy to Berlin leży na zachód od Warszawy są prawdziwe. Fałszywe natomiast będzie zdanie jeśli Moskwa leży na wschód od Warszawy to Berlin leży na wschód od Warszawy (poprzednik implikacji jest prawdziwy a następnik fałszywy, implikacja jest wtedy zdaniem fałszywym).
Rysunek 1.1:
Zdanie \(p \iff q\) nazywamy równoważnością, czytamy je \(p\) jest równoważne \(q\) lub \(p\) wtedy i tylko wtedy gdy \(q\). Równoważność jest prawdziwa gdy oba zdania mają tę samą wartość logiczną.
| \(p\) | \(q\) | \(p \iff q\) |
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
Przykład 6. Zdanie dwa dzieli sześć wtedy i tylko wtedy gdy trzy dzieli sześć jest prawdziwe, zarówno jak zdanie nieprawda, że dwa dzieli sześć wtedy i tylko wtedy gdy nieprawda, że trzy dzieli sześć.
Definicja 7. Formuła zdaniowa to wyrażenie utworzone z symboli oznaczających zdania (liter \(p,q,r\) najczęściej) i spójników logicznych.
Przykładowo, wyrażenia \(p\vee q\), \(p\Longrightarrow p\), \(p\wedge q \wedge r\) to formuły zdaniowe. Formuły zdaniowe stają się zdaniami gdy za symbole podstawimy konkretne zdania.
Definicja 8. Formułę zdaniową nazywamy
\(\bullet \) spełnioną jeśli dla danego wartościowania logicznego zmiennych (zdań w tej formule) jest ona prawdziwa (ma wartość logiczną \(1\)).
\(\bullet \) spełnialną jeśli dla pewnego wartościowania logicznego zmiennych (zdań w tej formule) jest ona prawdziwa.
\(\bullet \) tautologią jeśli dla każdego wartościowania logicznego zmiennych (zdań w tej formule) jest ona prawdziwa.
\(\bullet \) fałszywą jeśli dla każdego wartościowania logicznego zmiennych (zdań w tej formule) jest ona fałszywa.
Przykład 9. Formuła \(p\wedge q\) jest spełnialna (bo jest spełniona gdy \(w(p)=w(q)=1\)), ale nie jest tautologią (bo jest fałszywa na przykład gdy \(w(p)=1, w(q)=0\)).
W następnym Stwierdzeniu zobaczymy wybrane tautologie rachunku zdań, niektóre z nich mają specjalne nazwy:
1. \(( \neg (\neg p))\iff p\) zasada podwójnej negacji
2. \((p\wedge q)\iff (q\wedge p)\) przemienność koniunkcji
3. \((p\vee q)\iff (q\vee p)\) przemienność alternatywy
4. \((p\iff q)\iff (q\iff p)\)
5. \(((p\vee q)\vee r)\iff (q\vee (p\vee r))\) łączność alternatywy
6. \(((p\wedge q)\wedge r)\iff (q\wedge (p\wedge r))\) łączność koniunkcji
7. \((p\vee (q\wedge r))\iff ((p\vee q)\wedge (p \vee r))\) rozdzielność alternatywy względem koniunkcji
8. \((p\wedge (q\vee r))\iff ((p\wedge q)\vee (p \wedge r))\) rozdzielność koniunkcji względem alternatywy
9. \(\neg (p\wedge \neg p)\) prawo wyłączonej sprzeczności
10. \(p\vee \neg p\) prawo wyłączonego środka
11. \((p\lra q)\iff (\neg q \lra \neg p)\) prawo kontrapozycji
12. \((\neg (p\lra q))\iff (p \wedge \neg q)\) zaprzeczenie implikacji.
Czytelnik może samodzielnie sprawdzić (na przykład za pomocą tabelek), że wszystkie powyższe zdania są tautologiami. My sprawdzimy tylko wybrane przykłady. Warto może w tym miejscu zwrócić uwagę, że nasze wartościowanie logiczne jest dwuwartościowe (przyjmuje tylko wartości \(0\) i \(1\)), czyli zdania mogą być tylko albo fałszywe, albo prawdziwe. W życiu oczywiście tak nie jest, zainteresowani mogą poczytać o teorii zbiorów rozmytych i logice wielowartościowej na przykład w książce [1]. W stosowanej do naszych potrzeb logice dwuwartościowej tautologia \(9.\) mówi, że nie może być równocześnie prawdziwe zdanie i jego zaprzeczenie, a \(10.\), że zawsze zachodzi zdanie lub jego zaprzeczenie. Sprawdźmy, że rzeczywiście mamy do czynienia z tautologiami:
| \(p\) | \(\neg p\) | \((p\wedge \neg p)\) | \(\neg (p\wedge \neg p)\) |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| \(p\) | \(\neg p\) | \((p\vee \neg p)\) |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
Tautologia \(11.\) służy do dowodzenia nie wprost (zakładamy, że zdanie \(p\) jest prawdziwe; zamiast dowodzić, że ze zdania \(p\) wynika zdanie \(q\), możemy założyć, że zachodzi zdanie \(\neg q\) i wykazać, że wtedy zachodzi zdanie \(\neg p\); niektórzy być może spotkali się z podobnym rozumowaniem przy dowodzie, że pierwiastek z \(2\) jest liczbą niewymierną.)
| \(p\) | \(q\) | \(\neg p \) | \(\neg q\) | \(p\lra q\) | \(\neg q \lra \neg p \) | \(( p\lra q)\iff (\neg q \lra \neg p )\) |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 |
Sprawdźmy jeszcze, że zaprzeczenie implikacji równoważne jest koniunkcji poprzednika i zaprzeczenia następnika tej implikacji:
| \(p\) | \(q\) | \(\neg q\) | \(p\lra q\) | \(\neg ( p\lra q)\) | \(p \wedge \neg q \) | \((\neg ( p\lra q))\iff (p \wedge \neg q )\) |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 1 |
Osobno wypiszemy dwie ważne tautologie, zwane prawami de Morgana2.
Stwierdzenie 11 (Prawa de Morgana). Dla dowolnych zdań \(p, q\) następujące formuły są zawsze prawdziwe
1. \((\neg (p \vee q))\iff (\neg p \wedge \neg q)\)
(zaprzeczenie alternatywy jest równoważne koniunkcji zaprzeczeń)
2. \((\neg (p \wedge q))\iff (\neg p \vee \neg q)\)
(zaprzeczenie koniunkcji jest równoważne alternatywie zaprzeczeń)
Dowód. Faktycznie,
| \(p\) | \(q\) | \(\neg p\) | \(\neg q\) | \(p\vee q\) | \(\neg (p\vee q)\) | \(\neg p \wedge \neg q \) | \((\neg (p\vee q))\iff (\neg p \wedge \neg q)\) |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| \(p\) | \(q\) | \(\neg p\) | \(\neg q\) | \(p\wedge q\) | \(\neg (p\wedge q)\) | \(\neg p \vee \neg q \) | \((\neg (p\wedge q))\iff (\neg p \vee \neg q)\) |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
□
Wprowadzimy teraz pojęcie funkcji zdaniowej. Aby je wprowadzić formalnie potrzebujemy pojęcia zbioru, które pojawi się na następnym wykładzie. Ponieważ jednak pojęcie zbioru jest pojęciem pierwotnym – czyli nie definiuje się go, zakładając, że każdy „intuicyjnie wie co to jest”, możemy już teraz powiedzieć, że bierzemy dowolny niepusty zbiór \(X\).
Definicja 12. Funkcją zdaniową jednej zmiennej \(x\) nazywamy wyrażenie \(\phi (x)\), które staje się zdaniem logicznym jeśli za zmienną \(x\) podstawimy element zbioru \(X\). Zbiór \(X\) nazywamy zakresem zmienności funkcji \(\phi \).
Mówimy, że \(x\) spełnia \(\phi (x)\) jeśli \(w(\phi (x))=1\), zbiór \(x\) spełniających \(\phi (x)\) zapisujemy jako \(\{x\in X : \phi (x)\}.\)
W życiu dość często spotykamy funkcje zdaniowe. Na przykład w teście z historii możemy zobaczyć wyrażenie: „W roku 1656 królem Polski był ......... ”, i w zależności od tego czy wpiszemy zamiast kropek Jana Kazimierza czy Jana III Sobieskiego, dostajemy zdanie prawdziwe albo fałszywe. Naturalnym zakresem zmienności tej funkcji zdaniowej jest oczywiście zbiór królów Polski.
Oto bardziej matematyczny przykład:
Przykład 13. Niech \(X=\mathbb {R}\). Jeśli napiszemy \(x^2>1\) to mamy funkcję zdaniową (o zakresie zmienności \(\mathbb {R}\)), o wyrażeniu \(x^2>1\) nie możemy powiedzieć, czy jest prawdziwe, czy fałszywe póki nie podstawimy za \(x\) konkretnej liczby rzeczywistej. Zbiór \(x\) spełniających \(x^2>1\) czyli \(\{x\in \mathbb {R}: x^2>1\}\) to \(\mathbb {R}\setminus [-1,1]\) i faktycznie, podstawiając \(x\) z tego zbioru do wyrażenia \(x^2>1\) dostajemy zdanie prawdziwe.
Funkcje zdaniowe (o tym samym zakresie zmienności) możemy łączyć omówionymi wyżej spójnikami logicznymi. Innym rodzajem operacji logicznych, które możemy zastosować do funkcji zdaniowych są kwantyfikatory. Kwantyfikatory możemy traktować jako operacje, które z funkcji zdaniowej tworzą zdanie, czyli tak zwane funktory zdaniotwórcze. Kwantyfikatory, których będziemy używać są następujące.
Definicja 14. Niech \(\phi (x)\) będzie formą zdaniową o zakresie zmienności \(X\).
\(\bullet \) \(\forall _{x\in X} \ \phi (x)\) oznacza: dla każdego \(x\in X\) zachodzi \(\phi (x)\)
\(\bullet \) \(\exists _{x\in X}\ \phi (x)\) oznacza: istnieje \(x\in X\), takie, że zachodzi \(\phi (x)\)
Przykład 15. Wyrażenie \(x^2>1\) nie jest zdaniem, ale wyrażenie \(\forall _{x\in \mathbb {R}}\ x^2>1\) jest już zdaniem logicznym (fałszywym). Podobnie, \(x^2\geq 0\) nie jest zdaniem logicznym, ale \(\forall _{x\in \mathbb {R}}\ x^2\geq 0\) jest zdaniem prawdziwym.
1. Nieformalnie mówiąc, możemy patrzeć na kwantyfikatory jako na pewnego rodzaju skrócony zapis: \(\forall _{x\in X} \ \phi (x)\) zastępuje \(\phi (x_1)\wedge \phi (x_2)\wedge \ldots \) gdzie \(x_i\) przebiega wszystkie \(x\) w \(X\), a \(\exists _{x\in X}\ \phi (x)\) zastępuje \(\phi (x_1)\vee \phi (x_2)\vee \ldots \) gdzie znów \(x_i\) przebiega wszystkie \(x\) w \(X\). Dlatego też spotyka się zapis \(\bigwedge \) jako \(\forall \) oraz \(\bigvee \) jako \(\exists \).
2. Jeśli zbiór \(A\subset X\), i chcemy powiedzieć, że dla każdego elementu z \(A\) zachodzi \(\phi (x)\), to zamiast zapisu \(\forall _{x\in X} \ x\in A \lra \phi (x)\) stosujemy skrócony zapis \(\forall _{x\in A} \ \phi (x)\), podobnie postępujemy dla pozostałych kwantyfikatorów.
3. Kwantyfikator \(\forall \) (dla każdego) nazywa się czasem dużym kwantyfikatorem, a kwantyfikator \(\exists \) (istnieje) małym kwantyfikatorem.
4. Oczywiście, zdania możemy tworzyć przy pomocy więcej niż jednego kwantyfikatora, na przykład: \(\forall _{x\in \mathbb {N}} \, \exists _{y\in \mathbb {N}} \ x<y\) to zdanie logiczne (prawdziwe).
5. Tworząc zdania z kwantyfikatorami, należy zwracać uwagę na kolejność kwantyfikatorów. Zdanie dla każdego studenta istnieją spodnie, które nosi znaczy zupełnie coś innego, niż zdanie istnieją spodnie, które nosi każdy student.
6. Używa się również zapisu \(\forall !_{x\in X}\) i \(\exists !_{x\in X}\). Ten pierwszy czytamy „dla prawie wszystkich \(x\in X\)” (czyli dla wszystkich poza skończoną liczbą), \(\forall !_{x\in X} \phi (x)\) jest skróconą formą zapisu „istnieje zbiór \(S\) taki, że \(S\) ma skończenie wiele elementów i dla każdego \(x\in X\setminus S\) zachodzi \(\phi (x)\). Natomiast zapis \(\exists !_{x\in X}\phi (x)\) oznacza, że istnieje dokładnie jeden \(x\in X\) taki, że zachodzi \(\phi (x)\). Jest to skrócony zapis zdania „istnieje \(x\in X\) taki, że zachodzi \(\phi (x)\) i dla dowolnego \(y\in X\) jeśli zachodzi \(\phi (y)\) to \(y=x\).
Zaprzeczeniami zdań z kwantyfikatorami rządzą prawa zwane prawami de Morgana dla kwantyfikatorów:
Stwierdzenie 17. [Prawa de Morgana dla kwantyfikatorów] Niech \(\phi (x)\) będzie formą zdaniową o zakresie zmienności \(X\).
\(\bullet \) \(\neg (\forall _{x\in X}\ \phi (x))\iff (\exists _{x\in X}\ \neg \phi (x))\)
\(\bullet \) \(\neg (\exists _{x\in X}\ \phi (x))\iff (\forall _{x\in X}\ \neg \phi (x))\)
Przykład 18. Zaprzeczając zdaniu \(\forall _{x\in \mathbb {R}}\ x^2>0\) dostajemy zdanie \(\exists _{x\in \mathbb {R}} \ x^2\leq 0\).
Poniższe stwierdzenie podaje pewne prawa dla zdań z kwantyfikatorami.
Stwierdzenie 19. Niech \(\phi (x)\) i \(\psi (x)\) będą formami zdaniowymi o zakresie zmienności \(X\).
1. \(\exists _{x\in X} \ (\phi (x)\vee \psi (x)) \iff \exists _{x\in X} \ \phi (x) \vee \exists _{x\in X} \ \psi (x)\)
2. \(\forall _{x\in X} \ (\phi (x)\wedge \psi (x)) \iff \forall _{x\in X} \ \phi (x) \wedge \forall _{x\in X} \psi (x)\)
3. \(\exists _{x\in X} \ (\phi (x)\wedge \psi (x)) \ \lra \exists _{x\in X} \ \phi (x) \wedge \exists _{x\in X} \ \psi (x)\)
4. \(\forall _{x\in X} \ \phi (x) \vee \forall _{x\in X} \psi (x)\ \lra \forall _{x\in X} \ (\phi (x)\vee \psi (x))\)
Uwaga 20. Zwróćmy uwagę, że w punktach 3. i 4. mamy wynikanie tylko w jedną stronę. Wynikanie w drugą stronę nie musi zachodzić. Weźmy zdanie istnieje człowiek, który jest mężem Małgosi i istnieje człowiek, który jest mężem Kasi (to prawa strona 3.). Nie wynika z tego jednak, że istnieje człowiek, który jest mężem Małgosi i mężem Kasi (lewa strona 3.). Podobnie dla 4., weźmy zdanie każda liczba rzeczywista jest większa od \(2\) lub mniejsza lub równa od \(2\), z tego nie wynika, że każda liczba rzeczywista jest większa od \(2\) lub każda liczba rzeczywista jest mniejsza lub równa \(2\).
Na zakończenie tego wykładu powiedzmy kilka słów o dowodach formalnych. Niech dane będą zdania \(p_1,\dots ,p_n\), które nazwiemy założeniami i zdanie \(q\), które nazwiemy tezą. Postać twierdzeń matematycznych to najczęściej implikacja postaci \((p_1\wedge p_2\wedge \dots \wedge p_n)\lra q\). Chcemy udowodnić prawdziwość tej implikacji, oczywiście dowód jest interesujący tylko w przypadku gdy każde ze zdań \(p_i\) jest prawdziwe. Dowód formalny tej implikacji to ciąg składający się ze zdań, z których każde jest założeniem lub tautologią lub wnioskiem z poprzednich wyrażeń powstałym przy pomocy reguł wnioskowania. Reguły wnioskowania to pewne tautologie, przykładowo:
\(\bullet \) reguła zwana modus ponendo ponens czyli sposób potwierdzający przez potwierdzenie to \((p\wedge (p \lra q))\lra q\)
\(\bullet \) reguła zwana modus tollendo tollens czyli sposób zaprzeczający przez zaprzeczenie to \(((p\lra q )\wedge \neg q)\lra (\neg p)\)
\(\bullet \) sylogizm hipotetyczny to \(((p \lra q)\wedge (q\lra r))\lra (p\lra r)\)
\(\bullet \) sylogizm alternatywny \(((p\vee q)\wedge (\neg p))\lra q\)
\(\bullet \) dowód nie wprost \(((p\wedge \neg q)\lra (r\wedge \neg r))\)
Warto, jako ćwiczenie, sprawdzić, że powyższe reguły są tautologiami. Trzecia z tautologii to inaczej prawo przechodniości implikacji.
Uwaga 21. Warto też przyjrzeć się ostatniej z tych reguł. Opisuje ona sposób rozumowania przy dowodzeniu nie wprost. W dowodzie prowadzonym nie wprost przypuszczamy, że nasza implikacja \(p\lra q\) nie zachodzi. Zachodzi zatem jej zaprzeczenie, \(p\wedge \neg q\). Jeśli z tego zaprzeczenia wyniknie sprzeczność \((r\wedge \neg r)\), to znaczy, że nasze przypuszczenie nie mogło być prawdziwe.
1 Arystoteles (384–322 p.n.e.), filozof grecki.
2 Augustus de Morgan (1806–1871), angielski matematyk i logik.