Rachunek zdań

Rachunek zdań (logika matematyczna) to środek wyrazu, którym posługuje się matematyka. Spotkasz go w najróżniejszej terminologii i we wszelkiego rodzaju twierdzeniach matematycznych.

Do czego służy logika

Logika to nauka, która zajmuje się wnioskowaniem, prawdziwością oraz tym, co da się udowodnić, a co obalić. Przy tym wszystkim chodzi w logice wyłącznie o formę wypowiedzi. Nie interesuje nas, co konkretnie jest przekazywane, tak samo jak nie interesują nas różne interpretacje psychologiczne i podobne rzeczy.

Jeśli mamy na przykład zdanie „liczba 2 jest parzysta i jednocześnie jest nieparzysta”, możemy wywnioskować, że całe zdanie nie jest prawdziwe, bo liczba 2 nie jest nieparzysta. Właśnie takimi sprawami zajmuje się ogólnie logika.

Zdanie logiczne

Podstawą rachunku zdań jest oczywiście zdanie logiczne. Zdaniem logicznym jest każde zdanie oznajmujące, któremu możemy przypisać wartość logiczną, czyli stwierdzić, czy jest prawdziwe, czy fałszywe. Przykłady prostych zdań:

• Bill Gates był najbogatszym człowiekiem na świecie.
• Liczba naturalna pięć jest liczbą nieparzystą.
• HTML jest językiem programowania.
• Dwa plus trzy to sześć.

Wszystko to są zdania logiczne. Niezależnie od tego, czy są prawdziwe (dwa pierwsze), czy fałszywe (dwa ostatnie). Zdaniem logicznym nie jest na przykład zdanie pytające ani zdanie, któremu nie potrafimy jednoznacznie przypisać wartości logicznej. Znowu przykład:

• Czy w przyszłym roku Bill Gates też będzie najbogatszym człowiekiem na świecie?
• Kolor zielony jest najładniejszy.

Pierwsze zdanie nie może być zdaniem logicznym, bo jest pytaniem. Przy drugim z kolei nie rozstrzygniemy, czy jest prawdziwe, czy fałszywe. Takie zdanie nazywa się wtedy hipotezą (przypuszczeniem).

Klasyczna logika matematyczna nie radzi sobie zbyt dobrze z nieostrymi zdaniami typu „Janek jest wysoki” albo „Moja sąsiadka dobrze śpiewa”. Takie zdania lepiej opisuje na przykład logika rozmyta, która jest do nieostrości przystosowana.

Zdanie atomowe

W pierwszym rozdziale mieliśmy przykład zdania „liczba 2 jest parzysta i jednocześnie jest nieparzysta”. Takie zdanie możemy nazwać złożonym, bo w rzeczywistości łączy dwa krótsze zdania: „liczba 2 jest parzysta” i „liczba 2 jest nieparzysta”. Te dwa zdania są połączone spójnikiem logicznym „i”, albo też „i jednocześnie”.

Zdanie atomowe (proste) to więc zdanie, którego nie da się już dalej podzielić. W pewnym sensie jest to najprostsze możliwe stwierdzenie. Wcześniejsze przykłady zdań były w rzeczywistości zdaniami atomowymi:

• Bill Gates był najbogatszym człowiekiem na świecie.
• Liczba naturalna pięć jest liczbą nieparzystą.
• HTML jest językiem programowania.
• Dwa plus trzy to sześć.

Zdania atomowe będziemy dalej oznaczać małymi literami alfabetu, klasycznie p, q, r, …, i będziemy je nazywać zmiennymi zdaniowymi.

Spójniki logiczne

Logika matematyczna posługuje się zwykle pewnym zestawem spójników logicznych. Do podstawowych należą cztery spójniki dwuargumentowe:

• p ∧ q to koniunkcja zdań, czytamy „zdanie p i (jednocześnie) zdanie q”
• p ∨ q to alternatywa zdań, czytamy „zdanie p lub zdanie q”
• $p \Rightarrow q$ to implikacja, czytamy „jeżeli zdanie p, to zdanie q”
• p ⇔ q to równoważność, czytamy „zdanie p wtedy i tylko wtedy, gdy zdanie q”

Konkretne przykłady spójników logicznych:

• W centrum Opola pada deszcz i jednocześnie świeci słońce. (koniunkcja)
• W centrum Opola pada deszcz lub świeci słońce. (alternatywa)
• Apple to najfajniejsza firma i Steve Jobs to największy gość. (koniunkcja)
• Jeżeli weźmiesz środek przeczyszczający, to wkrótce się po… (implikacja)
• Jeżeli liczba x jest podzielna przez cztery, to jest też podzielna przez dwa. (implikacja)
• Agata jest ładna i jednocześnie mądra. (koniunkcja)
• Piosenkarki odnoszą sukces wtedy i tylko wtedy, gdy są ładne. (równoważność)
• Jeśli nie będzie padać, nie zmokniemy. (implikacja)
• Jeżeli mój wujek umie śpiewać, to jestem chińskim bogiem humoru. (implikacja)

Znamy jeszcze jeden popularny spójnik: negację. Negację oznacza się kreską $p^\prime$ albo symbolem $\neg p$. W polskich szkołach najczęściej spotkasz zapis $\sim p$, czytany „nieprawda, że p”.

Formuły

Za pomocą zmiennych zdaniowych (zdań atomowych) i spójników logicznych możemy złożyć bardziej skomplikowane zdanie, które będziemy nazywać formułą. Wszystkie przykłady z poprzedniej listy zdań były w rzeczywistości formułami, bo mieliśmy dwie formuły atomowe, na przykład „W centrum Opola pada deszcz” i „świeci słońce”, i połączyliśmy je spójnikami logicznymi. W pierwszym przypadku połączyliśmy je spójnikiem „i jednocześnie” i dostaliśmy formułę „W centrum Opola pada deszcz i jednocześnie świeci słońce”, w drugim przypadku użyliśmy „lub” i dostaliśmy formułę „W centrum Opola pada deszcz lub świeci słońce”.

Formalnie zdefiniujemy formułę tak:

• Każda zmienna zdaniowa (zdanie atomowe) jest formułą (dokładniej możemy powiedzieć, że jest to formuła atomowa).
• Jeżeli A i B są formułami, to $\neg A$, (A ∧ B), (A ∨ B), $(A \Rightarrow B)$, (A ⇔ B) też są formułami.

Definicja ma sens: w pierwszym punkcie mówimy, że każde zdanie atomowe jest jednocześnie formułą. Jeśli więc mamy dwa zdania atomowe, na przykład „W centrum Opola pada deszcz” i „świeci słońce”, to mamy jednocześnie dwie formuły. W tym momencie możemy zastosować drugi punkt i zbudować bardziej złożoną formułę, na przykład tak:

• W centrum Opola pada deszcz i jednocześnie świeci słońce.
• W centrum Opola pada deszcz lub świeci słońce.
• Jeżeli w centrum Opola świeci słońce, to pada deszcz.
• Słońce w centrum Opola świeci wtedy i tylko wtedy, gdy pada deszcz.

Formuły oczywiście wcale nie muszą być prawdziwe. W tej chwili dostaliśmy kolejny zestaw formuł, więc możemy złożyć jeszcze bardziej skomplikowane formuły. Jeśli oznaczymy A = „W centrum Opola świeci słońce lub pada deszcz.” (już wiemy, że to formuła) i B = „widać tęczę” (załóżmy, że znowu w centrum Opola, żeby nie trzeba było tego w kółko powtarzać), to możemy utworzyć kolejne formuły. Nawiasy w zdaniach tylko zaznaczają, do których części odnosi się spójnik.

• A ∧ B: (W centrum Opola świeci słońce lub pada deszcz) i jednocześnie (widać tęczę).
• A ∨ B: (W centrum Opola świeci słońce lub pada deszcz) lub (widać tęczę).
• $A \Rightarrow B$: (Jeżeli w centrum Opola świeci słońce lub pada deszcz), to (widać tęczę).
• A ⇔ B: (W centrum Opola świeci słońce lub pada deszcz) wtedy i tylko wtedy, gdy (widać tęczę).

Wszystko to są formuły. Możemy więc znowu wziąć jedną z nich i dołączyć do niej jakąś kolejną formułę. Możemy w ten sposób utworzyć na przykład takiego potworka: „Jeżeli w centrum Opola świeci słońce lub pada deszcz, lub widać tęczę, to słońce świeci lub pada deszcz wtedy i tylko wtedy, gdy widać tęczę.”

W kolejnej części zajmiemy się wartością logiczną formuł.