podstawy, Podstawy Informatyki
[ Pobierz całość w formacie PDF ]
B
REPREZENTACJA DANYCH W
PAMIĘCI
Adam Sawicki „Regedit”
sawickiap@poczta.onet.pl
Jest 10 rodzajów ludzi –
- ci, którzy rozumieją kod dwójkowy
i ci, którzy go nie rozumieją.
hakerskie ujęcie socjologii
W tym dodatku mowa będzie o sprawach, które mają miejsce w komputerze praktycznie
na najniższym możliwym poziomie. Będziemy się zajmowali zerami i jedynkami. Poznamy
także sposób, w jaki komputer zapisuje w pamięci wszelkie informacje.
Wbrew temu, co mogłoby się wydawać, wiadomości tego rodzaju nie są bezużyteczne.
Mają one ogromne zastosowanie w praktyce programistycznej. Dlatego radzę podejść do
tej lektury poważnie i postarać się zrozumieć opisane tu, miejscami niestety niełatwe
informacje.
Pamiętaj:
Wszystko wydaje się trudne, dopóki nie stanie się proste!
Algebra Boole’a
Wbrew groźnie brzmiącej nazwie, zaczniemy od rzeczy całkiem prostej. Poznamy
podstawowe, teoretyczne zasady operowania na zerach i jedynkach, zwane algebrą
Boole’a lub logiką dwuwartościową.
Boole George
(1815-1864), logik i matematyk angielski, od 1849 profesor matematyki
w Queen's College w Cork (Irlandia), członek Towarzystwa Królewskiego (Royal Society)
w Londynie. Zajmował się logiką formalną, rachunkiem prawdopodobieństwa, opracował
algebrę dla zbioru dwuelementowego (algebra Boole'a). Główne dzieło -
An Investigation
of The Laws of Thought
(1854).
Algebra Boole’a posługuje się jedynie dwiema możliwymi cyframi. Przyjęło się zapisywać
je jako 0 i 1. Można też wyobrazić je sobie jako dwa przeciwne stany – prawda (ang.
true
) i fałsz (ang.
false
), stan wysoki (ang.
high
– w skrócie H) i niski (ang.
low
– w
skrócie L), gruby i chudy, yin i yang czy cokolwiek innego :)
Działania
Na tych dwóch dostępnych liczbach definiuje się kilka podstawowych działań.
Negacja
Jest to działanie jednoargumentowe oznaczane symbolem ~ (tzw. tylda – czyli taki
wężyk pisany nieco u góry :) Bywa też oznaczane przez takie coś:
¬
lub przez pisany za
97
Źródło:
332
negowanym wyrażeniem apostrof: ‘. Możnaby je porównać znanej z normalnej
matematyki zamiany liczby na przeciwną za pomocą poprzedzającego znaku minus -. Tak
jak liczba –5 jest przeciwna, do liczby 5, tak ~x oznacza stan przeciwny do stanu
oznaczonego przez x. Ponieważ w logice dwuwartościowej wartości są tylko… dwie,
nietrudno jest wypisać tabelkę dla tego działania:
x ~x
0 1
1 0
Tabela 13. Wartości logiczne negacji
Jak widać, zanegowanie wartości powoduje jej zamianę na wartość przeciwną, czyli drugą
spośród dwóch możliwych.
Można jeszcze dodać, że negacja nazywana bywa też przeczeniem, a jej słownym
odpowiednikiem jest słowo „nie” (ang.
not
). Jeśli głębiej zastanowisz się nad tym,
wszystko okaże się… logiczne! Stan, który nie jest zerem – to jedynka. Stan, który nie
jest jedynką – to zero :D
Koniunkcja
Przed nami kolejne działanie kryjące się pod tajemniczą nazwą. Jest to działanie
dwuargumentowe, które można porównać znanego nam mnożenia. Symbolizuje go taki
oto dziwny znaczek przypominający daszek:
∧
.
Mnożąc jakąkolwiek liczbę przez 0, otrzymujemy 0. Z kolei 1*1 daje w wyniku 1.
Identycznie wynika iloczyn wartości Boole’owskich. Skonstruujmy więc tabelkę:
x
y x
∧
y
0
0
0
0
1
0
1
0
0
1
1
1
Tabela 14. Wartości logiczne koniunkcji
Koniunkcja bywa też nazywana iloczynem, a odpowiadającym jej słowem jest „i”.
Faktycznie możemy zauważyć, że aby działanie dało w wyniku jedynkę, jedynką muszą
być obydwa argumenty działania: pierwszy i drugi.
Alternatywa
Skoro jest mnożenie, powinno być też dodawanie. Pan Boole o nim nie zapomniał, więc
mamy kolejne działanie. Jego symbol jest przeciwny do symbolu koniunkcji (odwrócony
daszek) i wygląda tak:
∨
.
Tylko dodawanie dwóch zer daje w wyniku zero. Jeśli choć jednym ze składników jest
jedynka, wynikiem dodawania jest liczba większa od zera – 1 albo 2. Ponieważ dwójka w
algebrze Boole’a nie występuje, zamienia się na… nie nie! Nie „zawija się” z powrotem na
zero, ale zostaje jakby „obcięta” do jedynki.
Tabelka będzie więc wyglądała tak:
x
y x
∨
y
0
0
0
0
1
1
1
0
1
1
1
1
333
Tabela 15. Wartości logiczne alternatywy
Słówkiem odpowiadającym alternatywie jest „lub”. Widzimy, że wynikiem działania jest
1, jeśli wartość 1 ma przynajmniej jeden spośród argumentów działania – pierwszy lub
drugi. A więc wszystko się zgadza.
Różnica symetryczna
Działanie to jest często pomijane w podręcznikach logiki. Tymczasem jego znacznie z
punktu widzenia programisty jest ogromne. Jak bardzo – to okaże się później.
Na razie zajmijmy się jego zdefiniowaniem. Aby sporządzić tabelkę, przyda się angielska
nazwa tej operacji. Brzmi ona
exclusive or
(w skrócie
xor
) – co oznacza „wyłącznie lub”.
Aby w wyniku otrzymać 1, jedynką musi być koniecznie tylko pierwszy lub tylko drugi
argument tego działania, nie żaden ani nie obydwa.
x y x
⊕
y
0 0 0
0 1 1
1 0 1
1 1 0
Tabela 16. Wartości logiczne różnicy symetrycznej
To by było na tyle, jeśli chodzi o operacje logiczne konieczne do wprowadzenia cię w
świat komputerowych bitów. Aby jednak twoja wiedza z dziedziny zwanej logiką (tak,
tak! – na pierwszym roku informatyki jest osobny przedmiot o takiej nazwie, na którym
uczą właśnie tego! :) była pełna, opiszę jeszcze szybciutko pozostałe dwa działania.
Ekwiwalencja
Ekwiwalencja to inaczej równoważność i odpowiada jej nieco przydługie stwierdzenie o
treści: „wtedy i tylko wtedy, gdy”. Daje ono w wyniku jedynkę wtedy i tylko wtedy, gdy
obydwa argumenty są takie same. Można więc utożsamiać to działanie z równością.
Symbolizuje go taka zwrócona w obydwie strony strzałka:
⇔
.
x y x
⇔
y
0 0 1
0 1 0
1 0 0
1 1 1
Tabela 17. Wartości logiczne ekwiwalencji
Implikacja
To zdecydowanie najbardziej zakręcone i najtrudniejsze do zapamiętania działanie
logiczne. Cieszmy się więc, że programista raczej nie musi go pamiętać :)
Inna nazwa implikacji to wynikanie, a odpowiadające mu stwierdzenie brzmi: „jeżeli …, to
…”. Oznaczane jest strzałką skierowaną w prawo:
⇒
. Oto jego tabelka:
x y
x
⇒
y
0 0 1
0 1 1
1 0 0
1 1 1
Tabela 18. Wartości logiczne implikacji
334
Logicznego wyjaśnienia takiej a nie innej postaci tej tabelki nawet nie będę próbował się
podjąć
Przejdźmy teraz lepiej do dalszej części logiki, by jak najszybciej mieć ją już za
sobą :)
Aksjomaty
Poznamy teraz kilka prostych wzorów, które ukażą nam podstawowe zależności pomiędzy
poznanymi działaniami logicznymi.
Przemienność
a
∨
b = b
∨
a
Dodawanie też jest przemienne – jak w matematyce.
a
∧
b = b
∧
a
Mnożenie też jest przemienne.
Łączność
(a
∨
b)
∨
c = a
∨
(b
∨
c)
Dodawanie jest łączne – jak w matematyce.
(a
∧
b)
∧
c = a
∧
(b
∧
c)
Mnożenie też jest łączne.
Rozdzielność
a
∧
(b
∨
c) = (a
∧
b)
∨
(a
∧
c)
Mnożenie jest rozdzielne względem dodawania.
a
∨
(b
∧
c) = (a
∨
b)
∧
(a
∨
c)
Dodawanie też jest rozdzielne względem mnożenia – a w normalnej matematyce nie!!!
Identyczność
a
∨
0 = a
a
∨
1 = 1
a
∧
0 = 0
a
∧
1 = a
To wynika bezpośrednio z tabelek.
Dopełnienie
a
∨
~a = 1
a
∧
~a = 0
Bo jeden z argumentów zawsze będzie przeciwny do drugiego.
Prawa De Morgana
~(a
∨
b) = ~a
∧
~b
~(a
∧
b) = ~a
∨
~b
Logika w programowaniu
Uff… Pora wrócić do sedna sprawy, czyli do programowania. Tutaj często zachodzi
potrzeba reprezentowania jednego z dwóch stanów. Przykładowo zmienna
Blad
w stanie
98
Może niesłusznie, gdyż wyjaśnienie jest dość proste. Implikacja ilustruje wynikanie jednych faktów z drugich,
a takie rozumowanie jest słuszne zawsze, z wyjątkiem sytuacji, gdy ze stwierdzenia prawidziwego
wyprowadzamy stwierdzenie fałszywe. Odpowiada to trzeciemu wierszowi tabelki. [przypis: Xion]
335
1 oznaczałaby fakt wystąpienia błędu, a w stanie 0 fakt jego niewystąpnienia – czyli że
wszystko jest w porządku.
Typ logiczny
Typem danych w C++ reprezentującym wartości logiczne jest
bool
. Dwa stany
reprezentowane są zaś przez specjalne słowa kluczowe –
true
oraz
false
. Można też
używać identyfikatorów
TRUE
i
FALSE
pisanych dużymi literami.
Dla przykładu weźmy linijkę kodu, który tworzy wspomnianą zmienną i wstępnie ją
inicjalizuje:
bool
Blad =
false
;
Wyrażenia logiczne
Oprócz bezpośrednich wartości
true
oraz
false
, wartości typu
bool
zwracane są także
przez operatory porównania takie, jak
==
(równy),
!=
(różny),
<
(mniejszy),
>=
(większy
lub równy) itp.
Każda okazja jest dobra, aby po raz kolejny przestrzec przez typowym błędem, na który
(niestety?) w całej swej zachwalanej przez wielu elastyczności pozwala język C++.
Chodzi o różnicę pomiędzy operatorem przypisania
=
, a operatorem porównania
(równości)
==
. Ten pierwszy także zostanie zawsze zaakceptowany w miejscu drugiego,
ale z pewnością spowoduje inny (czyli nieprawidłowy) efekt.
Uważaj na to!
Wartość innego typu – np. liczba – także może zostać potraktowana jako wartość
logiczna. Przyjęte zostanie wówczas 0 (fałsz), jeśli wartość jest zerowa (np. liczbą jest 0)
oraz prawda w każdym innym wypadku.
Ta cecha języka C++ jest całkiem przydatna, ponieważ pozwala sprawdzać „niezerowość”
zmiennych (szczególnie wskaźników) bez posługiwania się operatorem porównania, np.:
if
(Zmienna)
std::cout<<
"Zmienna jest niezerowa"
;
Operatory logiczne
Poznane na początku działania algebry Boole’a mają, jak można się domyślać, swoje
odpowiedniki w języku programowania. W C++ są to symbole odpowiednio:
¾
!
– negacja – przeczenie – „nie” (jednoargumentowy)
¾
&&
- koniunkcja - iloczyn - „i” (dwuargumentowy)
¾
||
- alternatywa – suma – „lub” (dwuargumentowy)
Najłatwiej zrozumieć istotę działania tych operatorów zapamiętując ich słowne
odpowiedniki (te w cudzysłowach). Rozważmy przykład:
int
Liczba =
7
;
void
* Wskaznik =
0
;
bool
Wartosc = ( !(Wskaznik) || (Liczba == 6) ) &&
false
;
Wskaznik
jest zerowy, a więc jego wartością logiczną jest
false
. Po zanegowaniu
zmienia się w
true
. Zmienna
Liczba
nie jest równa 6, a więc wartością porównania
będzie
false
.
true
lub
false
daje
true
,
true
i
false
daje w końcu
false
. Zmienna
Wartosc
zostanie więc ostatecznie zainicjalizowana wartością
false
.
Postaraj się przeanalizować to jeszcze raz, dokładnie, i w pełni wszystko zrozumieć.
[ Pobierz całość w formacie PDF ]