ROZDZIAŁ DRUGI ALGEBRA BOOLE’A, INFORMATYKA, „THE ART OF ASSEMBLY LANGUAGE” [PL]

[ Pobierz całość w formacie PDF ]
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
WYŁĄCZNOŚĆ DO PUBLIKOWANIA TEGO TŁUMACZENIA
POSIADA
RAG
„THE ART OF ASSEMBLY LANGUAGE”
tłumaczone by KREMIK
konsultacje naukowe NEKRO
wankenob@priv5.onet.pl
nekro@pf.pl
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
ROZDZIAŁ DRUGI:
ALGEBRA BOOLE’A
Obwody logiczne są podstawą nowoczesnych systemów komputerowych. Aby zrozumieć, jak system
komputerowy posługuje się nimi, musisz zrozumieć logikę cyfrową i algebrę Boole’a. Ten rozdział wprowadza tylko
podstawowe informacje na temat algebry Boole’a. Temat ten jest często tematem całych podręczników. W rozdziale
tym, skupimy się na tych aspektach, które będą wsparciem przy czytaniu następnych rozdziałów.
2.0 WSTĘP
Logika boolowska stwarza podstawy dla wykonywania obliczeń w nowoczesnych, binarnych systemach
komputerowych. Możemy przedstawiać różne algorytmy, lub różne elektroniczne obwody komputerowe używając
systemu równań boolowskich. Ten rozdział dostarczy krótkiego wprowadzenia do algebry Boole’a, tablic prawdy,
postaci kanonicznej, funkcji boolowskich, upraszczania boolowskich funkcji, projektów logicznych, kombinatoryki i
obwodów sekwencyjnych, i równoważników hardware/software. Ten materiał jest szczególnie ważny dla tych
,którzy chcą projektować obwody elektroniczne lub pisać programy sterujące obwodami elektronicznymi. Nawet,
jeśli nigdy nie planowałeś projektować hardware’u lub pisać programów nim sterujących, wprowadzenie do algebry
boolowskiej, przedstawione w tym rozdziale jest jeszcze ważniejsze, ponieważ możesz używać takiej wiedzy do
optymalizowania pewnych złożonych wyrażeń warunkowych, jak IF,WHILE i wielu innych wyrażeń. Sekcja o
minimalizowaniu (optymalizowaniu) funkcji logicznych używa
Diagramów Veitch’a
lub
Map Karnaugh’a.
Technika optymalizacja to redukcja wielu warunków w funkcjach boolowskich. Musisz zdawać sobie sprawę, że
wielu ludzi uważa tą technikę optymalizacji za przestarzałą ,ponieważ redukcja wielu warunków w równaniach nie
jest już tak ważna jak była kiedyś. W tym rozdziale używamy metody mapowania jako przykład optymalizowania
funkcji boolowskich, ale nie jako technikę stosowaną regularnie. Jeśli jesteś zainteresowany w projektowaniu
obwodów i optymalizacji, musisz sięgnąć po teksty bardziej zaawansowane. Chociaż ten rozdział jest głównie
zorientowany sprzętowo, przyjmij do wiadomości, że wiele pojęć w tym tekście będzie używało boolowskich
równań (funkcji logicznych). Dlatego też powinieneś umieć sobie radzić z funkcjami boolowskimi przed
kontynuowaniem dalszego czytania tej książki.
2.1 ALGEBRA BOOLE’A
Algebra Boole’a jest systemem matematycznym zamkniętym w granicach wartości zero i jeden (prawda lub fałsz).
Operator binarny „° ” określony przez ten zbiór wartości, przyjmuje parę wartości boolowskich jako dane wejściowe
i zwraca pojedynczą wartość boolowską. Na przykład, boolowski operator AND, przyjmuje dwie wartości
boolowskie na wejściu i zwraca na wyjściu pojedynczą wartość boolowską . Z danego systemu algebraicznego
wynika kilka początkowych założeń ,lub aksjomatów, w jakim kierunku ten system pójdzie. Możesz wywnioskować
dodatkowe zasady, twierdzenia, i inne właściwości systemu z tego zbioru podstawowych aksjomatów. System
algebry boolowskiej często stosuje następujące aksjomaty:
∗
Zamknięcia. System boolowski jest zamknięty jeśli dla każdej pary wartości boolowskich, daje boolowski wynik.
Na przykład, logiczne AND jest zamknięte w systemie boolowskim, ponieważ przyjmuje boolowskie operandy i
daje tylko boolowskie wyniki.
∗ Przemienności. Mówimy, że operator binarny „° ” jest przemienny jeśli A°B =B°A dla wszystkich możliwych
wartości boolowskich A i B
∗ Łączności. Mówimy, że operator binarny „° ” jest łączny jeśli (A°B) °C = A°(B°C) dla wszystkich wartości
boolowskich A, B i C
∗ Rozdzielności. Dwa operatory binarne „°” i „%” są rozdzielne jeśli A°(B%C) = (A°B) % (A°C) dla wszystkich
wartości boolowskich A, B i C
∗ Tożsamości. Mówimy, że wartość boolowska I jest elementem tożsamym w stosunku do operatora binarnego „°”
jeśli A°I = A
.
∗ Elementu odwrotnego. Mówimy, że boolowska wartość I jest elementem odwrotnym w stosunku do operatora
binarnego „°´jeśli A°I=B a B jest wartością przeciwną do A w systemie boolowskim.
Dla naszych celów oprzemy algebrę boolowską na następującym zbiorze operatorów i wartości:
Dwie możliwe wartości w systemie boolowskim to zero i jeden. Często będziemy nazywać te wartości
(odpowiednio) fałsz i prawda.
Symbol „• ” przedstawia logiczną operację AND; np. A•B jest wynikiem logicznego ANDowania boolowskich
wartości A i B. Kiedy używamy pojedynczych liter w nazwach zmiennych, wyrzucamy symbol „•” Dlatego też, AB
również przedstawia logiczny AND zmiennych A i B (będziemy to również nazywać iloczynem A i B).
Symbol „+” przedstawia logiczną operację OR; np. A+B jest wynikiem logicznego ORowania wartości boolowskich
A i B (będziemy to również nazywać sumą A i B).
Logiczne dopełnienie, negacja lub nie, jest operatorem bez znakowym. W tym tekście będziemy używać
symbolu (‘) dla oznaczenia logicznej negacji .
Jeśli kilka różnych operatorów pojawia się w pojedynczym wyrażeniu boolowskim, wynik wyrażenia zależy od
„pierwszeństwa” operatorów. Będziemy stosować następujące zasady pierwszeństwa (od najwyższej do najniższej)
dla operatorów boolowskich: nawiasy, logiczne NOT, logiczne AND potem logiczne OR.
.Jeśli dwa operatory o tym samym pierwszeństwie są sąsiadujące, musisz oceniać je od lewej do prawej strony
Możemy także użyć następujących zbiorów postulatów:
P1 Algebra Boole’a jest zamknięta dla operacji AND, OR I NOT
P2 Tożsamość elementów, ze względu, na to że „
•
” reprezentuje jeden a „+” zero. Brak tożsamości elementów
dla operacji logicznej NOT .
P3. Operatory „•” i „+” są zamienne.
P4 • i + są rozdzielne względem siebie, tzn. A• (B+C) = (A•B)+(A•C) i A+(B•C)=(A+B) • (A+C).
P5 Dla każdej wartości A istnieje wartość A’ taka, że A•A’= 0 i A+A’=1. Ta wartość jest logicznym uzupełnieniem
(albo NOT) wartości A.
P6 • i + oba są łączne. Tzn. (A•B) •C = A• (B•C) i (A+B)+C=A+(B+C).
Możemy udowodnić wszystkie inne twierdzenia w algebrze boolowskiej używając tych postulatów. Ten tekst nie
będzie się zagłębiał w formalne dowodzenie tych twierdzeń, jednakże to dobra myśl aby zaznajomić się z kilkoma
ważnymi teoriami w algebrze boolowskiej. Oto próbka:
Th1: A + A = A
Th2: A • A = A
Th3: A + 0 = A
Th4: A • 1 = Α
Τh5: A • 0 = 0
Th6: A + 1 = 1
Th7: (A+B)’ = A’ • Β’
Th8: (A•Β)' = Α’ + B’
Th9: A + A•Β = Α
Τh10: Α•(Α+Β) = Α
Th11: A +A’B = A + B
Th12: A’• (A+B’) =A’B’
Th13: AB + AB’ = A’
Th14: (A’+B’)• (A’+B) = A’
Th15: A + A’ = 1
Th16: A
•
A’ = 0
Twierdzenia siedem i osiem są nazywane Prawami DeMorgana, na cześć matematyka ,który je odkrył. Powyższe
twierdzenia występują parami. Każda para (np. Th1 i Th2,Th3 i Th4) ma postać dualną. Najważniejszą zasadą w
systemie algebry boolowskiej jest ta dualność. Każde ważne wyrażenie można stworzyć używając aksjomatów i
twierdzeń algebry boolowskiej, korzystając z wymiany operatorów i stałych pojawiających się w wyrażeniu. Ściślej,
jeśli wymieniamy operatory • i + i zamieniamy wartości 0 i 1 w wyrażeniu, otrzymujemy wyrażenie przestrzegające
wszystkich zasad algebry boolowskiej. Nie znaczy to, że wyrażenia dualne obliczają takie same wartości., to tylko
znaczy że oba wyrażenia są prawidłowe w systemie algebry boolowskiej. Mimo, że w tym tekście nie będziemy
udowadniać żadnych twierdzeń ze względu na algebrę boolowską, będziemy używać tych teorii dla pokazania ,że
dwa boolowskie równania są identyczne. To jest ważna operacja, wtedy kiedy chcemy stworzyć postać kanoniczną
wyrażenia boolowskiego lub kiedy upraszczamy wyrażenie boolowskie.
2.2 FUNKCJE BOOLOWSKIE I TABLICE PRAWDY
Wyrażenie boolowskie jest sekwencją zer, jedynek i literałów oddzielonych operatorami boolowskim. Literał jest
.nazwą zmiennej. Dla naszych celów wszystkie nazwy zmiennych będą pojedynczymi znakami alfabetu. Funkcja
boolowska jest określonym boolowskim wyrażeniem; zazwyczaj nadajemy funkcji boolowskiej literę „F” czasami z
indeksem dolnym. Na przykład, rozpatrzmy następującą funkcję:
F
0
=AB+C
Ta funkcja oblicza logiczne AND z A i B a następnie logiczne OR z C. Jeśli A=1,B=0 a C=1 wtedy F
0
zwraca
wartość jeden (1•0+1).
Innym sposobem przedstawienia funkcji boolowskiej jest tablica prawdy. W poprzedni rozdziale
mieliśmy tablice prawdy przedstawiające funkcje AND i OR. Wyglądają następująco:
AND
0 1
0
0 0
1
0 1
Tablica 6: Tablica prawdy AND
OR
0 1
0
0 1
1
1 1
Tablica 7: Tablica prawdy OR
Dla operatorów binarnych i dwóch zmiennych wejściowych, taka forma tablic prawdy jest bardzo naturalna i
dogodna. Jednak, rozpatrzmy jeszcze raz powyższa funkcję F
0
. Ta funkcja ma trzy zmienne wejściowe nie dwie
..Zatem nie możemy używać tablic prawdy w formie jaka jest przedstawiona powyżej. Na szczęście, jest bardzo
łatwo zbudować tablice prawdy dla trzech lub więcej zmiennych. Poniższy przykład pokaże sposób zrobienia takiej
tablicy dla funkcji dla trzech lub czterech zmiennych:
BA
F =AB +C
00
01
10
11
0
0
0
0
1
C
1
1
1
1
1
Tablica 8: Tablica prawdy dla funkcji z trzema zmiennymi
BA
F =AB +CD
00
01
10
11
00
0
0
0
1
01
0
0
0
1
DC
10
0
0
0
1
11
1
1
1
1
Tablica 9: Tablica prawdy dla funkcji z czterema zmiennymi
W powyższych tablicach prawdy ,cztery kolumny przedstawiają cztery możliwe kombinacje zer i jedynek dla
zmiennych A i B (B jest bardziej znaczącym bitem ,A jest mniej znaczącym bitem).Podobnie cztery kolumny w
drugiej tablicy prawdy przedstawiają cztery możliwe kombinacje zer i jedynek dla zmiennych C i D.D jest bardziej
znaczącym bitem a C mniej znaczącym bitem. Tablica 10 pokazuje inny sposób przedstawiania tablic prawdy. Ta
forma jest łatwiejsza do wypełniania .Zauważ, że powyższe tablice prawdy uwzględniają wartości dla trzech
oddzielnych funkcji z trzema zmiennymi. Chociaż można stworzyć ogromny zbiór funkcji boolowskich, nie
wszystkie będą unikalne. Na przykład, F=A i F=AA są dwiema różnymi funkcjami. Jednak według twierdzenia
2,łatwo pokazać że te dwie funkcje są równoważne ,tzn. przyniosą dokładnie takie same dane wyjściowe dla
wszystkich kombinacji danych wejściowych. Jeśli określisz liczbę zmiennych wejściowych, otrzymasz skończoną
liczbę unikalnych, możliwych funkcji boolowskich. Na przykład, jest tylko 16 unikalnych funkcji boolowskich przy
dwóch danych wejściowych i tylko 256 możliwych funkcji boolowskich dla trzech danych wejściowych. Dla danych
n zmiennych wejściowych, jest 2**(2
n
) (dwa do potęgi 2
) unikalnych funkcji boolowskich z tych n-zmiennych
wejściowych. Dla dwóch zmiennych wejściowych mamy 2^(2
2
) =2
4
lub 16 różnych funkcji. Dla trzech wartości
wejściowych mamy 2**(2
3
=2
8
lub 256 możliwych funkcji. Dla czterech wartości wejściowych tworzymy 2**(2)
4
lub
2
16
lub 65,536 możliwych unikalnych funkcji boolowskich.
C
B
A
F= ABC
F= AB+C
F=A+BC
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
1
1
0
1
1
1
0
0
0
1
0
1
0
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
1
Tablica 10: Inny format tablicy prawdy
Kiedy mamy do czynieni z 16 funkcjami boolowskimi dosyć łatwo jest nazwać każdą funkcję .Poniższa tablica
zawiera 16 możliwych funkcji boolowskich dla dwóch zmiennych wejściowych wraz z ich popularnymi
nazwami i:
Funkcja #
Opis
0
Zero lub Czyszczenie. Zawsze zwraca zero bez wzgledu na wartosci wejsciowe A i
B
1
Logiczne NOR (NOT (A OR B) ) = (A+B)’
2
Inhibicja = BA’ (B not A). Równiez równowazne B > A lub A < B.
3
NOT A. Ignoruje B i zwraca A’
4
Inhibicja =AB’ (A not B). Równiez równowazne lub B<A
5
NOT B. Zwraca B’ i ignoruje A
6
Exclusive – or (XOR) = A ⊕ B. Równiez równowazne A ≠ B
7
Logiczne NAND (NOT (A AND B)) = (A • B)’
8
Logiczne AND = A • B. Zwraca A AND B
9
Równowaznosc = (A = B). Równiez znana jako exclusive-NOR (not exclusive-or)
10
Kopia B. Zwraca wartosc B i ignoruje wartosc A
11
Implikacja, B implikuje A = A+B’. (jesli B wtedy A). Równiez równowaznik B
>=A
12
Kopia A. Zwraca wartosc A i ignoruje wartosc B
13
Implikacja , A implikuje B = B+A’ (jesli A wtedy B). Równiez równowaznik A
>=B
14
Logiczne OR = A + B. Zwraca A OR B
15
Jeden lub ustawione. Zawsze zwraca jeden bez wzgledu na wartosci wejsciowe A i
B
Tablica 11: 16 możliwych funkcji boolowskich dla dwóch zmiennych
f
0
- funkcja stała,
f
1
- funkcja NOR,
f
2
- funkcja implikacji (zakazu),
f
3
- negacja A,
f
4
- funkcja implikacji (zakazu),
f
5
- negacja B,
f
6
- funkcja sumy wyłączającej, sumy modulo 2 lub funkcja EXOR,
f
7
- funkcja NAND,
f
8
- funkcja iloczynu,
f
9
- funkcja równoważności,
f
10
- funkcja tożsama ze zmienną,
f
11
- funkcja implikacji,
f
12
- funkcja tożsama ze zmienną,
f
13
- funkcja implikacji,
f
14
- funkcja sumy,
f
15
- funkcja stała.
Odwołujemy się do numeru funkcji raczej niż do jej nazwy .Na przykład F
8
oznacza logiczne AND zmiennych A i B
dla dwuwejściowej funkcji ,a F
14
jest logiczną operacją OR. Tylko problemem jest ustalenie numeru funkcji. Na
przykład dana jest funkcja z trzema zmiennymi F=AB+C, jaki jest jej odpowiedni numer? Ten numer jest łatwy do
wyliczenia patrząc na tablicę prawdy dla funkcji (zobacz Tabela 14). Jeśli potraktujemy zmienne A,B i C jako bity w
liczbie binarnej, z C jako najbardziej znaczącym bitem a A jako najmniej znaczącym bitem, stworzą one liczby
binarne w zakresie od zera do siedmiu. Skojarzone z każdym z tych binarnych łańcuchów jest zero lub jeden jako
wynik funkcji. Jeśli zbudujemy wartość binarną przez umieszczenie wyniku funkcji w miejscu określonym przez
A,B i C to wartość końcowa liczby binarnej jest numerem funkcji. Rozpatrzmy tablicę prawdy dla F=AB+C:
CBA
7
6
5
4
3
2
1
0
F=AB+C
1
1
1
1
1
0
0
0
Jeśli potraktujemy wartość funkcji jako liczbę binarną ,otrzymamy wartość F8
16
lub 248
10
.Zwykle będziemy
oznaczać numery funkcji w systemie dziesiętnym. To również pozwala zrozumieć dlaczego jest 2**2
n
różnych
funkcji z n zmiennych: Jeśli mamy n zmiennych wejściowych, jest 2
n
bitów w numerze funkcji. Jeśli mamy m bitów,
jest 2
m
różnych wartości .Dlatego też dla n wartości wejściowych mamy m.=2
n
możliwych bitów i 2
n
lub 2**2
n
możliwych funkcji.
2.3 ALGEBRAICZBNE DZIAŁANIA NA WYRAŻENIACH BOOLOWSKICH
Możemy przetworzyć jedno wyrażenie boolowskie na odpowiadające mu wyrażenie przez zastosowanie aksjomatów
i twierdzeń algebry boolowskiej. Jest to ważne jeśli chcesz przekształcić dane wyrażenie do postaci kanonicznej
(formy ujednoliconej) lub jeśli chcesz zminimalizować liczbę literałów lub warunki w wyrażeniu. Minimalizowanie
warunków i wyrażeń może być ważne ponieważ obwody elektryczne często składają się z pojedynczych
komponentów które implementują każdy warunek lub literał dla danego wyrażenia. Minimalizowanie wyrażenia
pozwala projektantowi zużyć mniej elektrycznych komponentów i dlatego też może zredukować koszt systemu.
Niestety, nie ma stałych zasad które pozwalają optymalizować dane wyrażenie. Podobnie jak budowa
matematycznych dowodów ,indywidualne zdolności ułatwiają zrobienie tej transformacji. Niemniej jednak, można
pokazać kilka przykładów ich możliwości:
ab + ab’ + a’b
=
a(b+b’) + a’b
przez P4
=
a•1 + a’b
przez P5
=
a + a’b
przez Th4
=
a + a’b + 0
przez Th3
=
a + a’b +aa’
przez P5
=
a + b(a + a’)
przez P4
=
a + b•1
przez P5
=
a + b
przez Th4
(a’b +a’b’ + b’)’
=
(a’(b+b’) +b’)’
przez P4
=
(a’ + b’)’
przez P5
=
((ab)’)’
przez Th8
=
ab
brak definicji
b(a+c) + ab’ +bc’ + c
=
ba + bc +ab’ +bc’ + c
przez P4
=
a(b+b’)+b(c+c’) + c
przez P4
=
a•1 + b•1 + c
przez P5
=
a + b + c
przez Th4
[ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • tejsza.htw.pl

    •