Musisz mi wybaczyć, iż zmusiłem Cię do czekania tak długo na artykuł mówiący o tym, czym jest algebra Boole’a. Z perspektywy matematyki, a później informatyki algebra Boole’a stała się kluczowa. Bez algebry tej nie moglibyśmy dziś programować, nie byłoby komputerów i całej elektroniki, która nas otacza.
W dzisiejszym wpisie odpowiem na następujące pytania:
- Czym jest algebra Boole’a?
- Co to jest tablica prawdy?
- Jakie znamy funkcje logiczne?
Od razu uprzedzam. Temat nie jest łatwy, więc zapnij pasy i lecimy!
Zatrzymaj się!
Książka „Programistą być” to obowiązkowa pozycja dla wszystkich zainteresowanego programowaniem!
Jest to zdecydowanie najlepsza na polskim rynku książka na temat programowania! Zyskasz przewagę w branży IT i osiągniesz dużo jako deweloper.
Z książki dowiesz się między innymi o tym:
- Czy matematyka, studia techniczne i język angielski są konieczne do tego, by rozpocząć pracę jako programista?
- Gdzie szukać informacji o programowaniu i w jaki sposób się uczyć?
- Jak znaleźć pierwszą pracę i w jaki sposób rozwijać swój programistyczny potencjał?
- Czym na co dzień zajmuje się programista?
- Czy każdy może zostać programistą?
I wiele, wiele więcej…
Algebra Boole’a — Wprowadzenie
Matematyka to nic innego jak ogromny zbiór reguł, często połączonych ze sobą. Mikroskopijnym wycinkiem całego tego matematycznego świata abstrakcji jest algebra Boole’a.
Algebra Boole’a działa na zbiorze dwóch wartości, czyli 0 oraz 1. Wartości zero i jeden to podstawa informatyki oraz programowania, dlatego tak ważne jest zrozumienie tytułowej algebry.
Z formalnego punktu widzenia operujemy na wartościach Prawda oraz Fałsz, dlatego zmienna tego typu nazywa się zmienną typu bool, właśnie od twórcy algebry Boole’a. W cyfrowych systemach operujemy na wartości włączony/wyłączony lub jest napięcie, lub go nie ma. Można również usłyszeć, iż stan jest wysoki lub niski. Chodzi o to, iż układy logiczne operują tylko na dwóch stanach – 0, czyli stan napięcia
bliski zeru oraz 1, czyli stan napięcia bliski napięciu zasilania 5V. Czasami są to też wartości 3.3V lub 1.5V.
Zbierając całość do kupy, algebra Boole’a opera się na wartościach, które możemy nazywać:
- 0, logiczne zero, fałsz, wyłączone napięcie, stan niski;
- 1, logiczna jedynka, prawda, włączone napięcie, stan wysoki;
Powstanie algebry Boole’a datuje się na długo przed powstaniem pierwszej elektroniki oraz komputerów. Matematyczne podstawy opracował angielski matematyk George Boole, a pierwsze zapiski na ten temat możemy znaleźć już w połowie XIX wieku.
Algebra Boole’a — Reguły
Skoro mamy trochę informacji, to czas zadbać o pewne reguły. Każde matematyczne (i nie tylko takie) zagadnienie musi mieć pewien zebrany zbiór reguł, których wszyscy musimy się trzymać. Nie będę wchodził w szczegóły, bo nie jest to do niczego potrzebne, ale pokażę Ci kilka kluczowych reguł.
Z racji tego, iż algebra Boole’a opiera się tylko na dwóch wartościach, to reguł tych nie będziemy mieć zbyt wiele.
Odnosić się będą one do dwóch ulubionych w informatyce działań, czyli dodawania:
- a + 1 = 1
- a + 0 = a
oraz mnożenia:
- a · 1 = a
- a · 0 = 0
Zapamiętaj z tego kilka faktów.
Po pierwsze zero jest neutralne w dodawaniu. Robiąc dodawanie 1+0 zawsze dostajemy 1. Niby oczywiste, ale jak za chwilę zobaczysz, binarne liczenie jest nieco inne. 1+1 to 1, nie zaś 2.
Po drugie jedynka jest neutralna w mnożeniu. Robiąc mnożenie 1 · 1 zawsze otrzymamy 1. Inaczej ma się w przypadku 0, gdzie 1 · 0 równa się po prostu 0. Więcej o systemach liczbowych napiszę w przyszłości osobny artykuł, bo to również bardzo istotny element świata IT.
Algebra Boole’a — Funkcja NOT
Przechodzę do meritum. Algebra Boole’a bazuje na funkcjach, które operują na wartościach 0 oraz 1. Zaczynam od najprostszej, bo funkcja NOT to zwykła negacja. W programowaniu negacja oznaczana jest różnymi znakami przez zmienną typu bool. W języku C# czy Java będzie to wykrzyknik (!).
Funkcja negacji, nazywana jest również funkcją zaprzeczenia i jest jedyną funkcją w algebrze Boole’a, która jest funkcją jednoargumentową. Najprościej mówiąc, negujemy argument.
Jeśli zanegujemy 1, to otrzymamy 0. Gdy natomiast zanegujemy 0, to otrzymamy przeciwną zeru wartość, czyli 1.
Znakiem negacji zwykle jest ~, który dajemy przed wartością. Akceptujemy też znak ’ po wartości.
Każda z funkcji ma tak zwaną tablicę prawdy, czyli tabelę, w której na wyjściu prezentujemy wartości, które powstały na skutek zastosowania danej funkcji na wartości wejściowe. Tablica prawdy będzie prezentować się następująco dla funkcji NOT.
Algebra Boole’a — Funkcja AND
Drugą najpopularniejszą funkcją jest funkcja AND. Nazywana często koniunkcją lub iloczynem logicznym. Skoro jest to iloczyn, to musi dotyczyć dwóch wartości. Wartościami niech będą p oraz q. Wtedy koniunkcję zapisywać będziemy jako p ^ q. Tablica prawdy mówi o tym, iż na wyjściu będzie 1 tylko wtedy, gdy zarówno p, jak i q będą równe 1.
Wynika to z reguły, którą zaprezentowałem powyżej. jeżeli coś mnożymy przez 0, to zawsze otrzymujemy zero.
- a · 0 = 0
Algebra Boole’a — Funkcja OR
Trzecią istotną funkcją i drugą po AND dwuwartościową jest funkcja OR. Nazywana również alternatywą lub sumą logiczną. W tym przypadku skoro jest to suma, to dotyczyć musi dwóch wartości. I w tym przypadku będą to p oraz q.
Wtedy alternatywę zapisywać będziemy jako p ∨ q. Tablica prawdy mówi o tym, iż na wyjściu będzie 1 zawsze, gdy p lub q będą równe 1. Albo jedno i drugie będzie równe 1
Wynika to z reguły, którą zaprezentowałem powyżej. jeżeli coś dodajemy do 1, to zawsze otrzymujemy jeden.
- a + 1 = 1
Algebra Boole’a — Funkcja XOR
Czas na nieco komplikacji. Funkcję XOR omawiałem w ostatnim mailu z serii Mailowej Akademii Programowania. Nazywana jest alternatywą rozłączną lub wykluczającą. W przypadku XOR mówi się, iż albo jedna wartość wynosi 1, albo druga. jeżeli p lub q jest 1, to wtedy 1 na wyjście. W innych przypadkach na wyjściu zero.
XOR zapisuje się jako 
Algebra Boole’a — Funkcja równoważności
Skoro funkcja XOR była prawdą tylko wtedy, gdzie jeden albo drugi argument był prawdą, tak w przypadku równoważności mówimy, iż wtedy i tylko wtedy, gdy oba argumenty są takie same. Jest to więc przeciwieństwo XOR, bo na wyjściu dostajemy 1 tylko wtedy, gdy p i q są zerami lub jedynkami.
Równoważność zapisuje się jako p <-> q lub (p -> q) ^ (p <- q).
Tablica prawdy dla funkcji równoważności wygląda następująco.
Algebra Boole’a — Funkcja NAND
Nazywana też dysjunkcją lub funkcją Sheffera. Można śmiało napisać, iż jest to przeciwieństwo funkcji AND, ponieważ na wyjściu zero ma jedynie wtedy, gdy zarówno p, jak i q równają się 1. Oznaczana jest jako p/q.
Na wyjściu dostaniemy prawdę, jeżeli na wejściu p lub q jest zerem. I oczywiście, jeżeli p oraz q jest zerem.
Tablica prawdy dla funkcji NAND jest następująca.
Algebra Boole’a — Funkcja NOR
Ostatnia w tym zestawieniu. Funkcja NOR nazywana również binegacją. jeżeli NAND było przeciwieństwem AND, tak NOR jest przeciwieństwem OR. NOR na wyjściu dostaje jedynkę tylko wtedy, gdy p oraz q nie są równe 1. jeżeli chociaż jeden argument jest równy jeden, to na wyjściu dostaniemy zero. Używając wyrażenia, możemy powiedzieć, iż funkcja NOR, to funkcja „ani.. ani…”.
Zapisuje się ją po prostu jako p NOR q.
Tablica prawdy dla NOR wygląda następująco.
Algebra Boole’a — Podsumowanie
Uważam, iż taką wiedzę, jaką zaprezentowałem w artykule, powinien posiadać każdy programista. Oczywiście algebra Boole’a to piękny i duży obszar matematyki i można na ten temat napisać publikację na dziesiątki tysięcy słów. Ja ograniczyłem się do koniecznego minimum, bo jak wiadomo, im mniej matematyki w ciężkiej formie, tym lepiej.
Mógłbym opowiadać tu o dodatkowych prawach, takich jak prawa De Morgana albo o całej gałęzi układów cyfrowych. O ile prawa De Morgana mogę pominąć, tak układy cyfrowe wymagają osobnego miejsca na blogu i do nich jeszcze wrócimy. Bramki logiczne pozwolą Ci zrozumieć jeszcze mocniej całą algebrę Boole’a.
Patrząc jeszcze nieco na funkcje logiczne dwuargumentowe, możemy zauważyć ciekawą prawidłowość. Są one parzyste, czyli mają swoje przeciwieństwa.
- AND oraz NAND;
- OR oraz NOR;
- XOR oraz Równoważność;
Zapamiętaj taką prawidłowość na przyszłość.
Newsletter
Nie przegap i dołącz już dziś do 815 osób będących w tym Newsletter! Otrzymuj co niedzielę o godzinie 20 listę kilku ciekawych tematów, które miałem okazję obserwować w mijającym tygodniu.
Tematy będą głównie techniczne, ale czasami pojawi się coś, co może wprowadzi Cię w stan zadumy i zmusi do dyskusji w szerszym gronie. Zero spamu!
Sprawdź swoją skrzynkę odbiorczą (albo katalog na spam) i potwierdź swoją subskrypcję.
