Serwis Edukacyjny
Nauczycieli
w I-LO w Tarnowie

Do strony głównej I LO w Tarnowie

Materiały dla uczniów liceum

  Wyjście       Spis treści       Poprzedni       Następny  

©2017 mgr Jerzy Wałaszek
I LO w Tarnowie

Autor artykułu: mgr Jerzy Wałaszek
Konsultacje: Wojciech Grodowski, mgr inż. Janusz Wałaszek

 

 

Logika

Rozdziały artykułu:
Wstęp
Teoria
    Logika
    Funkcje
    Trygonometria
    Liczby zespolone
    Logarytmy
    Macierze
    Wektory
    Pochodne i całki
    Elektryczność
    Prawa elektryczne
    Pojemność elektryczna
    Magnetyzm
    Indukcyjność
    Prąd przemienny
    Półprzewodniki
Warsztat

 

Algebra Boole'a

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). 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:

Ten dom jest zielony – prawda – 1
Ten dom jest czerwony – fałsz – 0

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:

 

Dawno temu na wielkiej równinie leżało miasto otoczone zewsząd wysokim murem, w którym znajdowała się tylko jedna brama. Przy bramie stali uzbrojeni strażnicy. Każdy przybysz musiał powiedzieć, po co tu przyszedł. Wszystkich tych, którzy powiedzieli prawdę, puszczano wolno. Wszystkich tych, którzy skłamali, ścinano mieczem u bramy. Pewnego dnia pojawił się podróżny, który na pytanie o cel przybycia, odpowiedział: "Przybyłem, aby mnie ścięto." Co mieli zrobić biedni strażnicy. Jeśli by go ścieli, to znaczy, że powiedział prawdę, a wtedy należałoby go puścić wolno. Ale, puszczając go wolno, sprawiliby, że podróżny skłamał, zatem należałoby go ściąć. I błędne koło się zamyka. Gdzie był błąd?

 

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

 

Operacje logiczne

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ą sie później przy omawianiu elementów 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ę:

a a
0 1
1 0

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?

Nieprawda, że ten dom jest zielony – fałsz – 0
Nieprawda, że ten dom jest czerwony – prawda – 1

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:

a b a + b
0 0 0
0 1 1
1 0 1
1 1 1

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:

logika arytmetyka
0+0=0 0+0=0
0+1=1 0+1=1
1+0=1 1+0=1
1+1=1 1+1=2

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:

a b c a + b + c
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

Działanie jest przemienne:

oraz łączne:

Tego typu własności w logice udowadnia się za pomocą tzw. tablic 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:

1 2 3 4 5 6 7
a b c (b+c) a + (b + c) (a+b) (a+b)+c
0 0 0 0 0 0 0
0 0 1 1 1 0 1
0 1 0 1 1 1 1
0 1 1 1 1 1 1
1 0 0 0 1 1 1
1 0 1 1 1 1 1
1 1 0 1 1 1 1
1 1 1 1 1 1 1

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:

a b a · b
0 0 0
0 1 0
1 0 0
1 1 1

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:

logika arytmetyka
0·0=0 0·0=0
0·1=0 0·1=0
1·0=0 1·0=0
1·1=1 1·1=1

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:

a b c a · b · c
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1

 

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:

a b a  b
0 0 0
0 1 1
1 0 1
1 1 0

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:

a b c a  b c
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1

Alternatywę wykluczającą da się zsyntezować 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:

a b a  b
0 0 1
0 1 1
1 0 0
1 1 1

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:

1 2 3 4
a b a  b b  a
0 0 1 1
0 1 1 0
1 0 0 1
1 1 1 1

Kolumna 3 różna od 4

1 2 3 4 5 6 7
a b c ( c)  (b c) ( b) (a b) c
0 0 0 1 1 1 1
0 0 1 1 1 1 1
0 1 0 0 1 1 1
0 1 1 1 1 1 1
1 0 0 1 1 0 1
1 0 1 1 1 0 0
1 1 0 0 0 1 1
1 1 1 1 1 1 1

Kolumna 5 różna od 7

Równoważność, ekwiwalencja

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

a b a  b
0 0 1
0 1 0
1 0 0
1 1 1

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:

 

 

Prawa logiczne

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:

Zaprzeczenie koniunkcji jest równoważne alternatywie zaprzeczeń

Drugie prawo odnosi się do zaprzeczenia alternatywy:

Zaprzeczenie alternatywy jest równoważne koniunkcji zaprzeczeń

Wprowadźmy dwie dodatkowe funkcje:

Zaprzeczenie alternatywy, NIE-LUB, NOR

a b a + b
0 0 1
0 1 0
1 0 0
1 1 0

Zaprzeczenie koniunkcji, NIE-I, NAND

a b a · b
0 0 1
0 1 1
1 0 1
1 1 0

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ą:

NOR          NAND
 
 
 

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

Prawo wyłączonego środka

Prawo podwójnej negacji

Prawa przemienności

Prawa łączności

Prawa rozdzielności

Prawo przechodniości implikacji

Prawo eliminacji implikacji

 

Minimalizacja funkcji logicznych

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

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:

a b c f(a,b,c)  
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0  
1 0 0 0  
1 0 1 0  
1 1 0 1
1 1 1 0  

Przykładowo, funkcja f000 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:

a b c f(a,b,c) a b a·b c c a·b+b·c
0 0 0 1 1 1 1 1 0 1
0 0 1 1 1 1 1 0 0 1
0 1 0 1 1 0 0 1 1 1
0 1 1 0 1 0 0 0 0 0
1 0 0 0 0 1 0 1 0 0
1 0 1 0 0 1 0 0 0 0
1 1 0 1 0 0 0 1 1 1
1 1 1 0 0 0 0 0 0 0

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ę nieco 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:

0 1 1 0

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

00 01 11 10

Dla trzech zmiennych powtarzamy powyższe czynności:

00 01 11 10 10 11 01 00

000 001 011 010 110 111 101 100

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.

 

Zbiory

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, jakby 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żą 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:

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:

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2017 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl