informatyka:podstawy-dzialania-komputera:algebra_boola

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

informatyka:podstawy-dzialania-komputera:algebra_boola [2026/05/19 11:17] – created kawcixinformatyka:podstawy-dzialania-komputera:algebra_boola [Unknown date] (current) – external edit (Unknown date) 127.0.0.1
Line 1: Line 1:
 +====== 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...
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 + 
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +