Teoria

Logika matematyczna jest bardzo ważnym działem matematyki, wręcz takim, bez którego współczesna matematyka nie mogłaby istnieć. W matematyce rozwija się różne teorie na bazie aksjomatów (prawd przyjętych z góry bez dowodu). Tworząc nowe twierdzenia, należy udowodnić ich prawdziwość. I tutaj właśnie wkracza logika matematyczna.

Podstawowym działem logiki matematycznej jest tzw. algebra Boole'a. Rozpropagował ją angielski matematyk George Boole. Dlaczego jest to dla nas tak ważne? Otóż, jak zobaczysz w dalszej części kursu, działanie wszystkich układów cyfrowych (w tym i mikrokontrolerów) opiera się ściśle o zasady tej algebry. Bez niej nie powstałyby współczesne komputery.

W algebrze Boole'a mamy tylko dwie wartości logiczne: prawdę (ang. true) i fałsz (ang. false). Umówmy się, że prawdę będziemy oznaczać cyfrą 1, a fałsz cyfrą 0. Jednakże cyfry te nie oznaczają tutaj liczb, o czym musisz pamiętać.

Zdanie jest prawdziwe (ma wartość 1), jeśli jest zgodne z prawdą. Jeśli jest niezgodne z prawdą, to jest fałszywe (ma wartość 0). Np:

Czasami pojęcie prawdy i fałszu może być bardzo zawiłe i prowadzić do paradoksów, jeśli nie będziemy ostrożni. Oto prosty przykład:

Zdania będziemy oznaczali małymi literami alfabetu: a, b, c, ... Podobnie w zwykłej algebrze oznacza się liczby.

Nad zdaniami logicznymi (tzn. takimi, które mają wartość prawdy lub fałszu) wykonujemy w algebrze Boole'a różne operacje/działania logiczne. Są one niekiedy podobne do operacji arytmetycznych i posiadają niektóre z ich własności. Musisz jednak pamiętać, że wynikiem operacji arytmetycznej jest jakaś liczba, natomiast w logice będzie to  zawsze wartość logiczna 1 (prawda) lub 0 (fałsz). Operacje logiczne, zwane często funkcjami logicznymi, definiujemy za pomocą tabelek wartości. Tabelki te należy bezwzględnie nauczyć się na pamięć (nie jest to trudne, ponieważ istnieją dla nich proste reguły). Funkcje logiczne posiadają po kilka nazw. Podajemy nazwy polskie oraz angielskie (przydadzą się później przy omawianiu elementów i układów cyfrowych cyfrowych).

Negacja, zaprzeczenie, NIE, NOT

Funkcja logiczna negacji jest podobna do minusa w arytmetyce. Daje ona w  wyniku wartość przeciwną logicznie, czyli z prawdy robi fałsz, a  z fałszu prawdę:

W pierwszej kolumnie tabeli mamy pierwotną wartość argumentu a. W drugiej kolumnie mamy wartość negacji tego argumentu. Negację oznaczamy w różny sposób:

Umówmy się, że my negację będziemy oznaczali przez kreskę ponad literą oznaczającą zdanie logiczne. Zapis a czytamy jako: nieprawda, że a. Jeśli a jest prawdziwe, to  a jest fałszywe i na odwrót. Proste?

Podwójna negacja (negacja negacji) daje niezaprzeczony argument:

Alternatywa, suma logiczna, LUB, OR

Funkcja logiczna alternatywy jest funkcją dwuargumentową, podobnie jak dodawanie w arytmetyce. Tabelka alternatywy jest następująca:

Tabelkę łatwo zapamiętać: alternatywa jest prawdziwa, jeśli jeden z jej argumentów jest prawdziwy. Alternatywę zapisuje się w różny sposób:

Umówmy się, że alternatywę będziemy oznaczać po prostu znakiem +. Jednak w logice nie jest to dodawanie arytmetyczne, co widać wyraźnie w ostatnim wierszu tabelki: 1 + 1 = 1. Wyrażenie logiczne a + b czytamy jako: a lub b. Alternatywa jest podobna do  dodawania liczb nieujemnych, dlatego nosi nazwę sumy logicznej:

Wartość logiczna fałsz 0 jest elementem neutralnym dla alternatywy. Oznacza to, iż dodając logicznie do argumentu a wartość logiczną 0, otrzymujemy niezmienione zdanie a. Również w operacji dodawania arytmetycznego 0 jest elementem neutralnym:

Alternatywę można rozszerzyć na dowolną liczbę argumentów. Obowiązuje zasada: wynik alternatywy jest prawdą, jeśli jeden z  jej argumentów jest prawdziwy:

Działanie jest przemienne:

oraz łączne:

Tego typu własności w logice udowadnia się za pomocą tzw. tabel prawdy. W tablicy prawdy dla każdego składnika wyrażenia tworzymy osobną kolumnę, a następnie sprawdzamy, czy kolumny wynikowe są takie same. Jeśli tak, to równość jest udowodniona. Dla przykładu udowodnimy ostatnią równość, posiłkując się tabelką alternatywy:

Kolumny 5 i 7 są takie same, zatem oba wyrażenia są sobie równe.

Alternatywa argumentu z jego zaprzeczeniem daje zawsze w  wyniku prawdę:

Koniunkcja, iloczyn logiczny, I, AND

Funkcja logiczna koniunkcji jest, podobnie jak alternatywa, dwuargumentowa. Wynik jej działania jest prawdą, jeśli wszystkie argumenty są  prawdziwe. W przeciwnym razie wynikiem jest fałsz. Tabelka koniunkcji jest następująca:

Koniunkcję zapisuje się w różny sposób:

Umówmy się, że my będziemy stosowali kropkę ·, jak przy mnożeniu. Jednak pamiętaj, że operacja koniunkcji nie jest mnożeniem, chociaż jest do niego bardzo podobna:

W arytmetyce liczby mogą mieć inne wartości niż 1 lub 0. W logice zbiór wartości ogranicza się do  prawdy 1 i  fałszu 0. Wyrażenie a · b czytamy jako: a i b.

Koniunkcję można rozszerzyć na dowolną liczbę argumentów. Obowiązuje zasada: wynik koniunkcji jest prawdą, jeśli każdy jej argument jest prawdziwy:

Elementem neutralnym w koniunkcji jest prawda.

Koniunkcja jest przemienna:

oraz łączna:

Alternatywa i  koniunkcja są względem siebie rozdzielne:

Naucz się szczególnie tego drugiego prawa logiki, ponieważ nie występuje ono w arytmetyce (logika posiada własny zestaw praw odmiennych od arytmetyki).

Koniunkcja argumentu z  jego zaprzeczeniem daje zawsze fałsz:

Alternatywa wykluczająca, suma symetryczna, suma modulo 2, ALBO, EXCLUSIVE-OR, XOR

Alternatywa wykluczająca jest funkcją dwuargumentową o  następującej tabelce:

Alternatywę wykluczająca zapisuje się w różny sposób:

Umówmy się, że my będziemy stosowali znak plusa w kółeczku .

Wynik alternatywy wykluczającej jest prawdą, jeśli argumenty się różnią. Gdy są takie same, wynikiem jest fałsz. Wyrażenie a  b czytamy jako: a albo b.

Alternatywę wykluczającą da się rozszerzyć na dowolną liczbę argumentów. Wynik jest prawdziwy, gdy nieparzysta liczba argumentów jest prawdziwa. Inaczej wynik jest fałszem:

Alternatywę wykluczającą da się utworzyć za pomocą trzech poznanych wcześniej funkcji logicznych:

Alternatywa wykluczająca jest przemienna:

oraz łączna:

Implikacja

Implikacja logiczna jest funkcją dwuargumentową o  następującej tabelce:

Implikacja jest fałszywa tylko wtedy, gdy jej pierwszy argument jest prawdziwy, a drugi jest fałszywy. Implikacja oznacza wynikanie. Wyrażenie a b czytaj jako: z a wynika b lub jeżeli a, to b.

Implikację da się zapisać jako:

Implikacja nie jest przemienna:

Nie jest również łączna:

Dowód w prosty sposób uzyskamy za pomocą tabelek prawdy:

Równoważność, ekwiwalencja

Równoważność logiczna jest funkcją dwuargumentową o  następującej tabelce:

Równoważność jest prawdziwa, jeśli oba argumenty mają tę samą wartość logiczną. Wyrażenie a b czytaj jako: a wtedy i tylko wtedy, gdy b.

Równoważność jest zaprzeczeniem alternatywy wykluczającej (porównaj tabelki obu funkcji):

Równoważność możemy otrzymać z implikacji w obie strony:

 

Okazuje się, że podstawowymi operacjami w logice są tylko dwie funkcje: negacja + alternatywa lub negacja + koniunkcja. Za pomocą tych dwóch funkcji można utworzyć wszystkie pozostałe. Wszystko za sprawą angielskiego matematyka, Augusta de Morgana.

Prawa de Morgana

Mamy dwa prawa de Morgana. Pierwsze odnosi się do  zaprzeczenia koniunkcji:

Drugie prawo odnosi się do zaprzeczenia alternatywy:

Wprowadźmy dwie dodatkowe funkcje:

Funkcje te zawierają w sobie (stosuję nazwy angielskie, ponieważ w takiej postaci spotkasz je później):

• NOR (ang. NOT OR) –  negację i alternatywę
• NAND (ang. NOT AND) –  negację i koniunkcję

Za ich pomocą można przedstawić każdą operację logiczną:

Poniżej podajemy pozostałe prawa logiczne. Używamy ich przy upraszczaniu wyrażeń logicznych.

 

Załóżmy, że mamy zdefiniowaną funkcję logiczną trzech zmiennych a, b i c za pomocą tabelki:

Z w ten sposób określonymi funkcjami spotykamy się bardzo często w technice cyfrowej, gdzie wiemy, jaką wartość ma  przyjmować funkcja logiczna dla określonych wartości argumentów (wiemy to ze sposobu działania budowanego przez nas urządzenia, co zobaczysz dalej w tym artykule). Jak zapisać taką funkcję? Wykorzystamy własności funkcji logicznych. Stwórzmy najpierw funkcje cząstkowe, które przyjmują wartość 1 dla określonych wartości argumentów, a 0 dla pozostałych:

Przykładowo, funkcja cząstkowa f₀₀₀ przyjmuje wartość 1 tylko wtedy, gdy a = 0, b = 0 i c = 0. W każdym innym przypadku wartość tej funkcji wynosi 0. Teraz funkcję podstawową możemy przedstawić jako sumę logiczną funkcji cząstkowych:

Funkcja podstawowa przyjmie wartość logiczną 1, jeśli jedna z  funkcji cząstkowych również ma wartość logiczną 1, a to wystąpi tylko przy określonej tabelką kombinacji argumentów. Rozpiszmy naszą funkcję:

Jest to postać surowa, spróbujmy ją uprościć, wykorzystując poznane prawa logiczne:

Teraz sprawdzamy, czy otrzymana funkcja odpowiada wartością funkcji f(a,b,c) z tabelki:

Obie funkcje są zgodne. Otrzymaliśmy dużo prostszą funkcję logiczną, czyli dokonaliśmy minimalizacji funkcji logicznej zadanej tabelką. Ten sposób postępowania jest oczywiście dobry, lecz wymaga czasami stosowania żmudnych rachunków logicznych, gdzie łatwo o pomyłkę. Istnieje inna, prostsza metoda minimalizacji funkcji logicznych, która wykorzystuje tzw. mapy Karnaugh'a.  Metoda ta jest wygodna do 4 zmiennych. Dla większej ilości staje się już zbyt skomplikowana.

Wróćmy do naszego przykładu. Utworzymy dla naszej funkcji mapę Karnaugh'a. Współrzędnymi tej mapy będą nasze zmienne a, b i c. Musimy je podzielić na dwie grupy: współrzędne poziome i pionowe. Umówmy się, że pionowo będzie to  jedna zmienna a, a poziomo dwie zmienne b i c. Zmienna a może przyjąć tylko dwie wartości, para zmiennych b i c przyjmuje tych wartości 4. Ułożymy je w specjalnej kolejności, zwanej kodem Gray'a:

Kod Gray'a ma szczególną cechę: kolejne zbudowane są z cyfr 0  lub 1 i różnią się od siebie stanem tylko jednej cyfry. Kod ten konstruujemy bardzo prosto:

Dla jednej zmiennej jest to ciąg 0 1.

Aby otrzymać ciąg dla dwóch zmiennych, kopiujemy lustrzanie cyfry:

Następnie dopisujemy do połowy początkowych wyrazów zera, a  do reszty 1:

Dla trzech zmiennych powtarzamy powyższe czynności:

Każdy kwadrat mapy Karnaugh'a jest teraz określony przez współrzędne a i bc. W kwadratach wpisujemy wartości funkcji dla tych współrzędnych zgodnie z tabelką funkcji:

Teraz zakreślamy obszary, które zawierają wartości 1. Zakreślony obszar musi obejmować wiersze i kolumny, których ilość jest potęgą liczby 2, zatem: 1, 2, 4, 8,... Obszary mogą na siebie zachodzić oraz łączyć się przez przeciwległe krawędzie. Początkowo może to być niejasne, lecz po wykonaniu kilku prostych projektów stanie się łatwe i oczywiste.

Patrzymy następnie na współrzędne zakreślonych obszarów. Te, które się zmieniają, eliminujemy. Dla pozostałych wypisujemy funkcję, która przyjmuje dla nich wartość logiczną 1. W naszym przypadku mamy dwa obszary: czerwony i zielony. W czerwonym obszarze zmienia się współrzędna c. Niezmienne pozostają współrzędne: a = 0 i b = 0. Tworzymy dla nich funkcję:

Zmienne a i b muszą w niej być zaprzeczone, aby dla a i b równego 0 otrzymać logiczne 1.

W obszarze zielonym z kolei zmienia się współrzędna a. Niezmienne pozostają współrzędne b = 1 i c = 0. Tworzymy dla nich funkcję dającą 1:

Ponieważ nie ma  więcej obszarów z wartością logiczną 1, piszemy:

Otrzymaliśmy zminimalizowaną funkcję, którą wcześniej wyprowadziliśmy ręcznie. Z mapami Karnaugh'a spotkasz się w dalszej części artykułu przy sieciach cyfrowych.

Więcej na ten temat znajdziesz w osobnym artykule: "Bit w zastosowaniach".

Zbiory w matematyce tworzą całą teorię. Nie mam ambicji, aby ją  tutaj prezentować. Podam tylko najbardziej istotne fakty. Więcej znajdziesz w podręcznikach do matematyki.

Zbiór (ang. set) jest pojęciem pierwotnym, tzn. przyjętym z góry. Matematyka bazuje na  pojęciach pierwotnych oraz twierdzeniach. Pojęć pierwotnych się nie wyprowadza. Musi tak być, inaczej powstałoby koło bez wyjścia.

Zbiór składa się z elementów o pewnych cechach. Np. zbiór ludzi, zbiór samochodów, zbiór ptaków, zbiór planet, zbiór liczb, itd.

Jeśli liczba elementów zbioru jest skończona, to zbiór możemy przedstawić następująco:

Zbiory będziemy oznaczać dużymi literami alfabetu. Powyższy zapis oznacza, że zbiór A zawiera 5  początkowych liczb naturalnych. Możemy to również zapisać tak:

Teraz zapis przeczytamy jako: zbiór A to ogół takich elementów x należących do liczb naturalnych, które są mniejsze od 6.

Mówimy, że element należy do zbioru, jeśli jest jego elementem. Dla powyższego zbioru prawdziwy jest zapis:

Również prawdziwe jest:

Czytamy to jako: liczba 7 nie należy do zbioru A.

Zbiór, który nie zawiera żadnego elementu, nazywamy zbiorem pustym (ang. empty set):

Zapis matematyczny jest zapisem międzynarodowym. Dzięki temu matematycy mogą się wymieniać wiedzą bez koniecznej znajomości języka obcego. Dobrym pomysłem jest poznanie tego zapisu. W  teorii zbiorów często spotyka się dwa zwroty:

Dla każdego i istnieje takie. W zapisie matematycznym posiadają one odpowiednie symbole:

Pierwszy symbol nazywamy kwantyfikatorem ogólnym, a  drugi kwantyfikatorem szczegółowym. Przy ich pomocy matematyk może zapisywać wygodnie różne twierdzenia. Na  przykład:

Czytamy to następująco: dla każdego x należącego do liczb naturalnych, x należy do A wtedy i tylko wtedy, gdy x jest mniejsze od 6. Zapis ten zrozumie każdy matematyk na całym świecie. Jest to zatem język matematyczny.

Dugi zapis:

czytamy jako: istnieje takie x należące do liczb naturalnych, że x nie należy do zbioru A. Aby to zdanie było prawdziwe, wystarczy wskazać np. x = 7, które spełnia to twierdzenie dla naszego zbioru A.

Mając kwantyfikatory, możemy już bez problemów zapisywać różne twierdzenia i definicje matematyczne.

Podzbiór

Zbiór B zawiera się w zbiorze A, jeśli każdy element zbioru B jest elementem zbioru A. O takim zbiorze B mówimy, że jest podzbiorem (ang. subset) zbioru A. O zbiorze A mówimy, że jest nadzbiorem (ang. superset) zbioru B.

Zbiór nie zawiera się w zbiorze A, jeśli istnieje taki element x ze zbioru B, który nie jest elementem ze zbioru A.

Przykład:

Podzbiorem każdego zbioru jest zbiór pusty.

Suma zbiorów

W teorii zbiorów również wykorzystywane są funkcje logiczne, które tradycyjnie oznaczamy symbolami:

• Alternatywa:
• Koniunkcja:
• Negacja:

Przez sumę zbiorów będziemy rozumieli zbiór, który zawiera elementy obu zbiorów. Formalnie zapisujemy to tak:

Zapis czytamy jako: suma zbiorów A i  B jest zbiorem ogółu takich x, że x należy do zbioru A lub x należy do zbioru B.

Przykład:

Część wspólna zbiorów

Częścią wspólną (iloczynem) zbiorów będziemy nazywać zbiór, którego elementy należą jednocześnie do  obu zbiorów:

Zapis czytamy jako: część wspólna zbiorów A i B jest zbiorem ogółu takich x, że x należy do  zbioru A i x należy do zbioru B.

Przykład:

Jeśli częścią wspólną jest zbiór pusty, to zbiory A i B nie posiadają elementów wspólnych:

Zapis czytamy jako: część wspólna zbiorów A i B jest zbiorem pustym wtedy i tylko wtedy, gdy dla każdego x należącego do zbioru A, x nie należy do zbioru B i dla każdego y należącego do  zbioru B, y nie należy do zbioru A.

Różnica zbiorów

Różnicę zbiorów definiujemy następująco:

Zapis czytamy jako: różnica zbiorów A i B jest zbiorem ogółu takich x, że x należy do zbioru A i x nie należy do zbioru B.

Przykład: