Show pageOld revisionsBacklinksBack to top This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong. ====== 1 Wstęp Algebra Boole'a ====== <callout type="danger" title="Strona w budowie!"></callout> Zaczniemy z jedną najbardziej podstawową rzeczą w informatyce. Na pewno słyszałeś/aś że komputery działają dzięki 0 i 1. To prawda, można powiedzieć że jedynka oznacza prąd, a zero jego brak. {{:informatyka:podstawy-dzialania-komputera:bipolar.jpg?200|}} Możemy powiedzieć, że jedynka to prawda, a zero - fałsz. Co możemy zrobić, mając tylko jedynki i zera? Możemy np wykonać operację AND. (zwraca prawdę, tylko jeżeli dwie wartości to prawda) Jest to iloczyn czyli mnożenie. ===== Operacja AND ===== {{:informatyka:podstawy-dzialania-komputera:andtruthtable.png?200|}} jak widać, AND zwróci prawdę, tylko kiedy dwie wartości są prawdą. (0*0 = 0, 1*0 = 0 , 0*1 = 0 ,1*1 = 1) Ta tabelka to tablica prawdy. A i B reprezentują zera i jedynki. W tabelkach prawdy mamy wszystkie możliwości. <button collapse="foo">Przykład użycia and w "programowaniu"</button> <collapse id="foo" collapsed="true"><well> <code cpp > #include <iostream> using namespace std; string login, haslo; int main() { cout << "Podaj login: "; cin >> login; cout << "Podaj haslo: "; cin >> haslo; if ((login=="admin")&&(haslo=="szarlotka")) // && to AND, jeśli dwa warunki będą spełnione, kod się wykona { cout<<"Udalo sie zalogowac!"; } else { cout<<"nie udalo sie zalogowac!"; } return 0; } </code> </well></collapse> ===== Operacja OR ===== Kolejną bardzo popularną operacją jest OR ( lub ) zwraca prawdę, gdy przynajmniej jeden z dwóch argumentów to prawda. Jest to suma (0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 1). {{:informatyka:podstawy-dzialania-komputera:ortruthtable.png?200|}} <button collapse="or_example">Przykład użycia OR w "programowaniu"</button> <collapse id="or_example" collapsed="true"><well> <code python > # Sprawdzamy, czy podana liczba jest mniejsza od 5 lub większa od 10 liczba = 3 if liczba < 5 or liczba > 10: print("Liczba jest mniejsza od 5 lub większa od 10.") else: print("Liczba znajduje się między 5 a 10.") </code> </well></collapse> ===== Operacja NOT ===== Operacja NOT czyli negacja po prostu odwraca wartość na przeciwną. Jest to działanie jednoargumentowe z angielskiego unary operation. Czyli przyjmuje tylko jeden argument. Jedynka staje się zerem, a zero jedynką. {{:informatyka:podstawy-dzialania-komputera:nottruthtable.png?200|}} ===== Przykład połączenia różnych operacji ===== Zacznijmy łączyć te operację. Przykład: NOT(0 OR (1 AND 1)) Czy potrafisz powiedzieć jaka będzie wartość tego wyrażenia ? Mamy tutaj nawiasy, tak jak w matematyce. Pokazują one nam "kolejność" działań. Okej. z naszej tabeli wiemy że 1 AND 1 zwróci nam 1 czyli zostaje nam NOT(0 OR 1) 0 OR 1 zwraca nam 1 czyli zostaje NOT(1) - NOT(1) zwraca nam 0 . a więc wartość wyrażenia NOT(0 OR (1 AND 1)) to 0 ===== Pewne prawa algebry boola ===== Wszystkie prawa pojawią się razem z wytłumaczeniem na innej stronie. Tutaj tylko taki wstęp. W algebrze boola mamy pewne prawa,np **prawo przemienności** (x AND Y) to to samo co (Y AND X) logiczne prawda ? Oba te wyrażenia zwrócą nam to samo. np (1 AND 0) = 0 (0 AND 1) = 0 - to to samo ---- (X OR Y ) to to samo co (Y OR X) np (1 OR 0) = 1 (0 OR 1) = 1 ---- **Prawo łączności** (<color #ed1c24>x</color> AND (<color #fff200>Y</color> AND <color #00a2e8>Z</color>)) to to samo co ( (<color #ed1c24>X</color> AND <color #fff200>Y</color>) AND <color #00a2e8>Z</color> ) tak dla ujenoznacznienia, ponieważ dużo osób gubi się. Mamy literki <color #ed1c24>X</color> <color #fff200>Y</color> <color #00a2e8>Z</color>. każda z nich może być 1 albo 0. Dam tutaj przykład w powyższym przykładzie zakładam że <color #ed1c24>x = 1</color> <color #fff200>y = 0</color> <color #00a2e8>z = 1.</color> (<color #ed1c24>1</color> AND (<color #fff200>0</color> AND <color #00a2e8>1</color>)) = (1 AND 0) = **0** Wyszło nam 0, teraz z prawa łączności zamieniam "literki" ( (<color #ed1c24>1</color> AND <color #fff200>0</color>) AND <color #00a2e8>1</color>) ) = (0 AND 1) = 0 - wyszło to samo co wcześniej, czyli prawo łączności nie kłamie Kolejne prawo łączności, którego nie będę udowadniać, ale możesz sam podstawić sobie coś pod x y z i zobaczyć, że wyjdzie to samo. (X OR ( Y OR Z ) ) to to samo co ( (X OR Y ) OR Z ) ---- W innych źródłach, prawa mogą być zapisane troszkę inaczej niż ja to zrobiłem. Uważam, że "mój" sposób jest czytelniejszy ale np prawo łączności można zapisać (AB)C = A(BC) ( (X AND Y) AND Z ) to to samo co (x AND (Y AND Z)) Poprostu operacja AND to mnożenie więc można to zapisać jako mnożenie( w matematyce gdy między literami nie ma znaku, jest między nimi mnożenie) To jakimi literkami sobie zdefiniujemy nasze zera i jedynki nie ma znaczenia oczywiście W operacji OR mamy sumę więc zamiast pisać X OR Y możemy zapisać X + Y ... ---- **prawo rozdzielności** Abyś się przyzwyczaił podam tutaj dwie formy zapisu... 1 prawo rozdzielnosci ( X and ( Y OR Z ) ) = (X AND Y) OR (X AND Z) ( A ( B + C) = AB + AC 2 prawo rozdzielnosci (X OR ( y AND z) ) = (x OR y) AND (X OR Z) A + (BC) = (A + B) (A + C) ---- **prawa De Morgana** - opisują wpływ negacji na pewne operacje NOT(X AND Y) = NOT(x) OR NOT(Y) NOT(X OR Y) = NOT(X) AND NOT(Y) ===== Przykład zastosowania praw ===== Możemy je wykorzystać do zmienienia formy wyrażenia, uproszczenia jej. przykład NOT( NOT( X ) AND NOT ( X OR Y ) ) możemy użyć prawa De morgana aby zamienić NOT(X OR Y ) na NOT(X) AND NOT(Y) więc: NOT<color #ed1c24>(</color>NOT(X) AND <color #fff200>(</color>NOT(X) AND NOT(Y)<color #fff200>)</color><color #ed1c24>)</color> następnie możemy użyć prawa łączności mamy więc: NOT <color #ed1c24>(</color> <color #fff200>(</color> NOT( X ) AND NOT( X ) <color #fff200>)</color> AND NOT(Y)<color #ed1c24>)</color> Następnie, nie zapisaliśmy tego "prawa", ale mamy NOT(X) AND NOT(X). Skraca się to do jednego NOT(X). Możesz sobie to rozpisać i jest to prawda. Więc: NOT(NOT(X) AND NOT(Y)) Znowu możemy użyć prawa De morgana NOT( NOT( X ) ) OR NOT(NOT(Y)) Nie zapisaliśmy tego "prawa", ale not not x zawsze da nam x. NOT(NOT(Y)) również da nam y Czyli wychodzi nam: X OR Y Ten przykład miał pokazać, że możemy różnie manipulować wyrażeniami algebry boole'a, upraszczać je itp. ===== Teoria - nie potrzebujemy operacji OR aby stworzyć wszystkie możliwe wyrażenia ===== bardziej ciekawostka. Każda funkcja boola może być stworzona tylko za pomocą AND i NOT przypomina nam się prawo de morgana (X OR Y) = NOT(NOT(X) AND NOT(Y)) wyrażenie OR może być zaprezentowane przez operacje NOT I AND. Czy możemy "zejść jeszcze niżej ??" {{:informatyka:podstawy-dzialania-komputera:nandtruthtable.png?200|}} Oto NAND, czyli negacja AND Dzięki samemu NAND, jesteśmy w stanie skonstruować wszystkie funkcję boola... jak ? (X NAND Y) = NOT ( X AND Y ) wiemy że nand to negacja AND Skoro dzięki, AND i NOT możemy zbudować każde wyrażenie boola, musimy wymyśleć jak zrobić NOT używając samego NAND NOT (X) = (X NAND X) prostę ? możesz spojrzeć na tablicę prawdy dla NAND i udowodnić sobie, że tak jest. A jak z nand zrobić AND ? (x AND y) = NOT(X NAND Y) Skoro wiemy jak zrobić not z nand wychodzi nam: (x and y) = (x nand x)(x NAND Y) Jeśli chcielibyśmy zbudować komputer tylko z funkcji nand. Jest to możliwe... informatyka/podstawy-dzialania-komputera/algebra_boola.txt Last modified: 2024/04/07 00:34by kawcix