Martin Jovanovi
ć
UVOD U RA
Č
UNARSTVO
- skripta za ra
č
unske vežbe - prednacrt - nezvani
č
na kompletna verzija -
Istorija verzija:
§
24.12.2004. Prednacrt. Nedostaju objašnjenja za sve oblasti. Primeri su u rukopisu. Ova verzija pokriva
kompletno gradivo, i dovoljna je za pripremu drugog kolokvijuma iz Uvoda u ra
č
unarstvo. Izuzetak
č
ini deo o
zadavanju kona
č
nih automata i putevima u automatu – data je referenca na odgovaraju
ć
e poglavlje u
literaturi. Mogu
ć
e su štamparske greške. Autor se unapred zahvaljuje na svim sugestijama.
§
13.01.2005. Uvodna pri
č
a o kona
č
nim automatima je prepravljena da bi bila jasnija. Na kraju automata je dat
zadatak ("aba"), i detaljno opisan rad automata (sa postepenim crtanjem grafa).
§
20-21.01.2005. Pristupam ponovo skripti na Svetog Jovana. Dodao sam uvod u pri
č
u o Bulovoj algebri (koja je
ina
č
e stavljena suvoparna). Dodatno sam pojasnio, govornim jezikom, svaki od aksioma iz Hantingovog skupa.
Dodatno sam objasnio poglavlje o definisanju osnovnih operacija prekida
č
ke algebre, i još tu uveo pojam
tablice istinitosti. Na po
č
etku tre
ć
eg poglavlja ubacio sam definiciju potpuno i nepotpuno definisane
prekida
č
ke funkcije. Dopunio sam tekst i uradio preglednije tabele. Zadatke posle poglavlja o analiti
č
kim
formama funkcije (skenirane i zalepljene) sam zamenio kucanim zadacima (zadatke kucao Božidar Ze
č
evi
ć
).
§
24.01.2005. Ispravljene štamparske greške (zadavanje PF, zadatak 5, precrtavanja su bila pomerena u desno).
Dodatno sam objasnio osobinu distributivnosti operacija. Ispravljene su neke štamparske greške u postavci
zadatka 2 iz na
č
ina zadavanja PF. Pojasnio sam izraz "idempotentnost". Dodat je prekucan zadatak sa NI i NILI
kolima.
§
17.02.2004. Ispravljena greška kod kombinatorijskog vektora.
2.
Elementi prekida
č
ke algebre
2.1.
Uvod
Prekida
č
ka algebra pruža matemati
č
ku osnovu za bilo kakav rad sa
prekida
č
kim
funkcijama
. A prekida
č
ka funkcija je zapravo matemati
č
ki model rada bilo kog
digitalnog
elektri
č
nog kola
. A opet, cilj koji se postavlja pred studenta u okviru drugog dela Uvoda u
ra
č
unarstvo (ra
č
unske vežbe), je projektovanje digitalnog elektri
č
nog kola (ne na fizi
č
kom
nivou, ve
ć
na
logi
č
kom
– idejno rešenje).
Detaljnije:
www.martinjovanovic.com/uur/koncepcija2.html
Ovo poglavlje u osnovnoj verziji napisala je Valentina Mili
ć
evi
ć
.
2.2.
Bulova algebra
2.2.1. Uvod
Ovo poglavlje je, u osnovnoj verziji, napisala Valentina Mili
ć
evi
ć
. Nad njim su
izvršene obimne promene i dopune od strane autora skripte, Martina Jovanovi
ć
a. Detaljnije
o tim promenama u istoriji verzija. Hvala, Valentina.
2.2.2. Definicija Bulove algebre
Najjednostavnije re
č
eno, da bi jedan skup postao algebarska struktura, njega treba
"oplemeniti" odre
đ
enim skupom operacija. Algebarske strukture su "prostori" u kojima se
kre
ć
emo kada vršimo bilo kakve matemati
č
ke operacije.
Bulova algebra je, po definiciji, algebarska struktura (B, +,
•
,
, 0, 1) koju
č
ine:
•
skup B
•
binarne operacije + i
•
1
•
unarna operacija
2
•
0 – nula Bulove algebre
•
1 – jedinica Bulove algebre
ukoliko važe aksiome iz
Hantingovog
skupa aksioma:
A1 – zatvorenost skupa B za operacije +,
•
,
:
B
x
x
x
x
x
x
B
x
x
∈
⋅
+
⇒
∈
∀
2
1
2
1
2
1
2
1
,
,
,
)
,
(
Druga
č
ije re
č
eno: ako se operandi za pomenute operacije "vuku" iz skupa B, onda i
rezlutati tih operacija pripadaju skupu B, tj. ni u jednom slu
č
aju se ne "izlazi" iz skupa B.
A2 – komutativnost za operacije + i
•
:
1
2
2
1
1
2
2
1
2
1
)
,
(
x
x
x
x
x
x
x
x
B
x
x
⋅
=
⋅
∧
+
=
+
⇒
∈
∀
Komutativnost nije potrebno objašnjavati.Treba samo znati da binarne operacije
moraju biti komutativne, da bi gore opisan sistem bio Bulova algebra.
A3 – distributivnost "·" prema "+" i "+" prema "·" (obe varijante!)
O ovome treba re
ć
i nešto više. Pre toga bi
ć
e date matemati
č
ke interpretacije obe
varijante ove aksiome, a zatim
ć
e biti data dodatna objašnjenja:
)
(
)
(
)
(
)
,
,
(
3
1
2
1
3
2
1
3
1
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
B
x
x
x
+
⋅
+
=
⋅
+
∧
⋅
+
⋅
=
+
⋅
⇒
∈
∀
U "realnom matemati
č
kom životu" (u okviru algebre realnih brojeva) navikli smo na
prvu varijantu, odnosno distributivnost operacije množenja
3
u odnosu na operaciju
1
U osnovi: postoje
nekakve dve binarne operacije
i to je sve; i obeležene su tim simbolima. Ali to nisu
bilo kakve dve binarne operacije, nego (što se kasnije vidi kroz Hantingov skup aksioma), neke dve binarne
operacije koje
zadovoljavaju neke uslove
. Tek kad zadovolje te uslove, onda se skup koji ih sadrži može nazvati
algebrom.
2
Ista logika važi i za unarnu operaciju. Dakle, da bi pomenuti sistem "imao pravo" da nosi naziv Bulova
algebra
, on mora da sadrži i jednu unarnu operaciju; i to ne bilo kakvu, nego sa ta
č
no odre
đ
enim osobinama (koje
su definisane u Hantingovom skupu aksioma).
Martin Jovanovi
ć
– Uvod u ra
č
unarstvo, 2. deo – Realizacije PF
Verzija: 17.02.2005.
Nedovršena, ali potpuno funkcionalna verzija. Nedovršena je u smislu što nisam sve pojasnio na svoj na
č
in.
- 7 -
1
0
)
1
0
(
≠
⇒
∈
∧
∈
B
B
Nula i jedinica Bulove algebre moraju biti dva razli
č
ita elementa, što je i logi
č
no.
2.2.3. Posledice Bulove algebre – neke teoreme
Na osnovu skupa aksioma Bulove algebre izvode se slede
ć
e teoreme. Teoreme
ć
e
biti date bez dokaza. One se dokazuju direktnom primenom aksioma iz Hantingovog skupa.
T1 – teorema o dvostrukom komplementu
x
x
B
x
=
⇒
∈
∀
)
(
T2 – zakon asocijativnosti operacija + i
•
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
)
(
)
(
)
(
)
(
)
,
,
(
x
x
x
x
x
x
x
x
x
x
x
x
B
x
x
x
⋅
⋅
=
⋅
⋅
∧
+
+
=
+
+
⇒
∈
∀
T3 – teorema bez imena
0
0
1
1
)
(
=
⋅
∧
=
+
⇒
∈
∀
x
x
B
x
T4 – zakon idenpotentnosti
Na latinskom idem (grubo prevedeno) zna
č
i isti, isto; a potentia zna
č
i mogu
ć
nost,
sposobnost. Re
č
idempotentia mogla bi se, možda, prevesti kao
istomo
ć
je
. U matematici,
kod binarnih operacija (kao što je slu
č
aj ovde), osobina idempotentnosti zna
č
i da elemenat
koji je ima, ukoliko se operacija primeni na njega (da on bude sa obe strane operatora),
rezultat je on sam. Ovu osobinu imaju oba binarna operatora Bulove algebre.
7
x
x
x
x
x
x
B
x
=
⋅
∧
=
+
⇒
∈
∀
)
(
T5 – zakon apsorpcije
1
2
1
1
1
2
1
1
2
1
)
(
)
,
(
x
x
x
x
x
x
x
x
B
x
x
=
⋅
+
∧
=
+
⋅
⇒
∈
∀
T6 – teorema bez imena
0
1
1
0
)
1
0
(
=
∧
=
⇒
∈
∧
∈
B
B
T7 – De Morganovi zakoni
2
1
2
1
2
1
2
1
2
1
)
,
(
x
x
x
x
x
x
x
x
B
x
x
+
=
⋅
∧
⋅
=
+
⇒
∈
∀
Dvoelementna Bulova algebra, tj. ona kod koje je skup
}
1
,
0
{
=
B
, naziva se
prekida
č
ka algebra
, a funkcije definisane nad njom nazivaju se
prekida
č
ke funkcije
.
Prekida
č
ke funkcije su funkcije sa kojima radimo u nastavku ovog kursa.
2.2.4. Definisanje operacija +, ·,
Kao što je ve
ć
re
č
eno, prekida
č
ka algebra podrazumeva tri operacije: jednu unarnu
(operaciju "nadvu
č
eno" – komplement, u oznaci,"
", koja se naziva i logi
č
ko NE, engl.
NOT), i dve binarne:
1.
operaciju logi
č
kog sabiranja, koja se tako
đ
e naziva i logi
č
ko ILI (OR), odnosno
disjunkcija, i
2.
operaciju logi
č
kog množenja, koja se tako
đ
e naziva i logi
č
ko I (AND), odnosno
konjukcija.
Tanka je linija izme
đ
u pojmova OPERACIJA i FUNKCIJA. U ovom slu
č
aju ovi pojmovi
su
sinonimi
. Dakle ravnopravno možemo govoriti o prekida
č
koj funkciji ILI, ili o operaciji
7
http://en.wikipedia.org/wiki/Idempotency
