Bohdan Potopakhin

Logika dwójkowa

W programowaniu na przykład często się sprawdza wszelakie warunki, takie jak np. «czy wiersz nie jest zbyt długi», «czy delta jest ujemna»,
«czy się zmieścimy», «czy potrzebny plik istnieje», «użytkownik wybrał tą opcję pracy czy inną» i wiele innych; poczowszy programować bardzo szybko można się przekonać o tym że wykonywanie nawet najprostrzych programów jest oparte na sprawdzaniu warunków. Przy tym same warunki są wyrażeniami logicznymi, a to są takie wyrażenia, które się oblicza, a wynikiem tych obliczeń staje się wartość logiczna — fałsz lub prawda.

Rozdział matematyki, który bada wyrażenia takiego rodzaju, nazywa się logiką metematyczną; warto dodać, że jest to wystarczająco skąplikowany obszar wiedzy, zawierający wiele nietrywialnych teorji, tak że głębokie poznanie logiki matematycznej może zająć całe życie. My przyjrzymy się jedynie jednej z najprymitywniejszych składowych logiki matematycznej — tak zwanej algebrze logiki dwójkowej.

W swojej istocie logika dwójkowa przypomina arytmetykę, ale zamiast nieskończonego zbioru liczb wykorzystuje się zbiór, składającą się jedynie z dwóch wartości: 0 (fałsz) i 1 (prawda). Nad tymi wartościami określone są różne działania, w wyniku których też otrzymuje się 0 lub 1. Zapewne, jednym z najprostrzych działań logicznych jest — negacja, «nie x», które oznacza się ¬x; w książkach można spotkać także inne oznaczenia, naprzyklad kreskę;. Działanie negacji zmienia wartość na przeciwną, czyli ¬1 = 0 oraz
¬0 = 1. Jako że działanie negacji ma tylko jeden argument, mówi się, że negacja jest operacją unarna.

Za najbardziej znane i najczęściej wykorzystywane binarne (dwójkowe) działania logiczne, czyli działania dwóch argumentów, można uznać logiczne lub i logiczne i, które w matematyce nazywa się też alternatywą i koniunkcją. «Logiczne lub» między dwoma logicznymi wartościami jest prawdziwe, gdy chociażby jedna z pierwotnych wartości jest prawdziwa; naturalnie, one mogą być prawdziwe obie jednocześnie, wtedy «logiczne lub» między nimi też okarze się prawdziwe. Jedyna sytuacja, w której «logiczne lub» okazuje się fałszywe — to kiedy oba jego argumenty są fałszywe. «Logiczne i», naprzeciw, jest prawdziwe wtedy i tylko wtedy, gdy prawdziwe są obydwa jego argumenty, a we wszystkich innych przypadkach jest fałszywe.

Działanie «logicznego lub» zazwyczaj oznacza się znakiem «∨», a tyczy się działania «logicznego i», to najpopularniejszym oznaczeniem dla niego jest ampersand «&», lecz w wielu współczesnych podręcznikach działanie te z jakiegoś powodu wolą oznaczać znakiem «∧».

Tablica 1. Podstawowe binarne operacje logiczne

Nazwę konjunkcja łatwo będzie zapamiętać komuś kto kojarzy takie danie kuchni hiszpańskiej jak chili con carne co w języku hiszpańskim oznacza chili z mięsem, można się domyślić które słowo co oznacza.

Pomimo konjunkcji i dysjunkcji, dosyć często spotyka się działania wyłącznego lub i implikacji. «Wyłączne lub», oznacza się znakiem «⨁», jest prawdziwe, gdy prawdziwy jest jeden z jej argumentów, lecz nie oba naraz, od zwykłego «lub» operacja różni się swoją wartością w przypadku prawdziwości obu argumentów.

Operacja implikacji (oznacza się «→») jest trochę trudniejsza do zrozumienia. Ona jest oparta na zasadzie, że we wnioskach z prawdziwych przesłanek może wynikać tylko prawda, a z fałszywych przesłanek może wynikać cokolwiek, czyli może wyjść prawda, a może — fałsz. Aby zrozumieć, dlaczego tak jest, można przypomnieć, że wcale nie wszystkie teorie naukowe były prawdziwe, ale mimo to były doskonale wykorzystywane, a nawet dawały poprawne wyniki. W szczególności, wiadomo, że bracia Montgolfier unieśli w powietrze pierwszy balon, napełniając go dymem z mieszanki słomy i sierści; słome rozpatrywali jako roślinny początek życia, a sierść — jako zwierzęcy początek, co według nich miało doprowadzić do możliwości lotu, i lot rzeczywiście się udał, mimo tego że zwierzęcy i roślinny początek niemiał z tym nic wspólnego. Mówiąc inaczej, możliwe jest otrzymanie absolutnie poprawnych wyników, opierając się o absolutnie fałszywe przesłanki. Odpowiednio do tego implikacja jest fałszywa tylko w tym przypadku, gdy jej lewy argument — prawda, a prawy — fałsz (z prawdy niemoże wynikać fałsz), we wszystkich innych przypadkach implikacja jest prawdziwa.

Oznaczmy zbiór {0, 1} literą B od słowa Boolean (po imieniu angielskiego matematyka, Georga Boola, który po raz pierwszy zaproponował formalny system, zwany współcześnie jako algebra logiki, bądź algebra Boola). Działania logiczne dwóch argumentów można rozpatrywać jako funkcje, dziedziną których jest B ⨯ B (czyli zbiór par {(0,0),(0,1),(1,0),(1,1)}), a zbiorem wartości — samo B. Jako że dziedzina funkcji logicznych jest skończona, można ją zadać za pomocą tablic, w których w jawnej postaci wskazana jest wartość dla każdego elementu z dziedziny. Te tabele funkcji logicznych nazywa się tablicami prawdy; w szczególnści, tablica 2. zawiera tablicę prawdy dla rozpatrzonej przez nas konjunkcji, dysjunkcji, «alternatywy rozłącznej» i implikacji.

Tablica 2. Wszystkie możliwe funkcje binarne dwóch argumentów

Jako że funkcja logiczna dwóch argumentów definiuje się w całości swoimi wartościami, których ma cztery, czyli, poprostu mówiąc, zestawem z czterech wartości dwójkowych, przypominając nasze poznania w kombinatoryce, możemy stwierdzić, że ich wszystkich istnieje 16. Zbiór wszystkich możliwych funkcji logicznych dwóch argumentów znajduje się na tabelce 2, gdzie one są uporządkowane od najmniejszego do największego zestawu ich wartości, tak jakby zestaw wartości był dwójkowym zapisem liczby. Zaczynając wyliczanie od funkcji «konstanta 0», która jest fałszywa dla dowolnych argumentów i kończąc «konstanta 1», bądź tautologią — funkcją, która, naprzeciw, dla dowolnych argumentów jest prawdziwa. Jak łatwo można się przekonać, tablica posiada w sobie oprócz reszty, przed chwilą rozpatrzoną przez nas konjunkcję, dysjunkcję, implikację i «alternatywe rozłączną». Oprócz tego, w tablicy można zauważyć funkcję x (zawsze równą pierwszemu argumentowi, niezależnie od drugiego) i y (zawsze równą drugiemu argumentowi, niezależnie od pierwszego), a także ich negacje; funkcje, oznaczone «↓» i «∣», nazywają się odpowiednio «strzałka peirca;» «kreska sheffera;» oznaczają negację dysjunkcji i negację konjunkcji:

Funkcja, oznaczona znakiem «≡», nazywa się ekwiwalentnośćią, bądź tożsamością: jest ona prawdziwa, kiedy jej argumenty są równe, i fałszywa, gdy się różnią. Nietrudno jest się przekonać, że ekwiwalentność jest negacją «alternatywy rozłącznej». Zostały jeszcze tylko trzy funkcje, a to jest «implikacja odwrotna» («x ← y = y → x»), a także funkcje «większe» i «mniejsze», które oznaczają negacje implikacji. Podsumowując, zaczynając od konstant, wyliczyliśmy dokładnie 16 fukcji, czyli wszystkie.