fbpx

Musisz mi wybaczyć, że 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 każdego, kto interesuje się tematem programowania!

Z książki dowiesz się między innymi o tym:

  • Czy matematykastudia 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ć, że stan jest wysoki lub niski. Chodzi o to, że 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, że 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 ważny 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 zazwyczaj 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.

Tablica prawdy - negacja

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, że 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śli coś mnożymy przez 0, to zawsze otrzymujemy zero.

  • a · 0 = 0

Funkcja AND - tablica prawdy

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, że 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śli coś dodajemy do 1, to zawsze otrzymujemy jeden.

  • a + 1 = 1

Funkcja OR - tablica prawdy

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ę, że albo jedna wartość wynosi 1, albo druga. Jeśli p lub q jest 1, to wtedy 1 na wyjście. W innych przypadkach na wyjściu zero.

XOR zapisuje się jako , czyli znak podłogi ( _ )oraz V. Tablica dla XOR wygląda następująco.

Alternatywa rozłączna XOR - tablica prawdy

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, że 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.

Równoważność - tablica prawdy

Algebra Boole’a – Funkcja NAND

Nazywana też dysjunkcją lub funkcją Sheffera. Można śmiało napisać, że 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śli na wejściu p lub q jest zerem. I oczywiście, jeśli p oraz q jest zerem.

Tablica prawdy dla funkcji NAND jest następująca.

Funkcja NAND - tablica prawdy

Algebra Boole’a – Funkcja NOR

Ostatnia w tym zestawieniu. Funkcja NOR nazywana również binegacją. Jeśli 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śli chociaż jeden argument jest równy jeden, to na wyjściu dostaniemy zero. Używając wyrażenia, możemy powiedzieć, że funkcja NOR, to funkcja „ani.. ani…”.

Zapisuje się ją po prostu jako p NOR q.

Tablica prawdy dla NOR wygląda następująco.

Funkcja NOR - tablica prawdy

Algebra Boole’a – Podsumowanie

Uważam, że 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ść. 

PS. Będę wdzięczny za komentarze pod tym postem!

PS2. Czeka też na Ciebie prezent. Wystarczy, że zapiszesz się na Newsletter poniżej!

PS3. Dołącz do naszej grupy na Facebook!

Subskrybuj

Zapisz się do Mailowej Akademii Programowania.

MAP to jedyne takie miejsce, gdzie co niedzielę otrzymasz rozwiązanie programistycznego zadania.

Do tego otrzymasz darmowe konsultacje w przypadku odpowiedzi na moje maile. Wspólnie staniemy się lepszymi programistami!

Nie przegap i dołącz już dziś do 746 osób będących w MAP!

Brzmi ciekawie? Nie zwlekaj i dołącz już teraz!

PS. Na start otrzymasz bonus w formie PDF z rozwiązanymi dziesięcioma programistycznymi problemami!

Autor

👨‍💻 .NET and Python programming passionate 🏦 Digtial Banking Solutions 🎓 Student 📊 Psychology 📚 Bookworm 🏠 Warsaw

Napisz komentarz

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.

Programistą być to przewodnik po programistycznym świecie, który każdy zainteresowany programowaniem powinien przeczytać!

X