This is an old revision of the document!
1 Wstęp Algebra Boole'a
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.
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
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.
#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; }
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).
# 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.")
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ą.
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
(x AND (Y AND Z)) to to samo co ( (X AND Y) AND Z )
tak dla ujenoznacznienia, ponieważ dużo osób gubi się. Mamy literki X Y Z. każda z nich może być 1 albo 0. Dam tutaj przykład
w powyższym przykładzie zakładam że x = 1 y = 0 z = 1.
(1 AND (0 AND 1)) =
(1 AND 0) = 0
Wyszło nam 0, teraz z prawa łączności zamieniam “literki”
( (1 AND 0) AND 1) ) =
(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(NOT(X) AND (NOT(X) AND NOT(Y)))
następnie możemy użyć prawa łączności mamy więc:
NOT ( ( NOT( X ) AND NOT( X ) ) AND NOT(Y))
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 ??”
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…