This is an old revision of the document!
Wstęp
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.
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).
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.