====== 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.
{{: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.
#include
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).
{{:informatyka:podstawy-dzialania-komputera:ortruthtable.png?200|}}
# 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ą.
{{: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**
(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 XYZ. każda z nich może być 1 albo 0. Dam tutaj przykład
w powyższym przykładzie zakładam że x = 1y = 0z = 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 ??"
{{: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...