Bulio algebra
5 (100%) 1 vote

Bulio algebra

Bulio algebra

Bulio algebra

Bulio algebra yra viena iš matematikos sričių, turinčių labai platų pritaikymą kompiuterių moksle, o ypač kompiuterių aparatūrinės įrangos srityje. Pradžią šiam mokslui davė anglų matematiko Džordžo Bulio (George Boole, 1815-1864) 1854 m. išleistas fundamentalus darbas “Mąstymo dėsnių tyrimas”. Šio mokslininko pavarde ir buvo pavadinta ši algebra.

Kompiuterinės įrangos srityje plačiausią pritaikymą turi viena iš Bulio algebros atšakų arba viena iš jos dalių – dvejetainė algebra. Šios šakos pagrindą sudaro sritis, susidedanti tik iš dviejų elementų aibės (paprastai šie elementai yra įvardijami kaip 0 ir 1). Jos svarbą praktiniame taikyme apsprendžia tai, kad absoliučios daugumos šiuo metu praktikoje naudojamų kompiuterių funkcionavimas grindžiamas dvejetaine sistema. Kompiuterių aparatūros vystymosi istorijoje būta bandymų konstruoti ir kitokiomis skaičiavimo sistemomis pagrįstus kompiuterius (pavyzdžiui, trejetaine), tačiau praktikoje šie bandymai nepasiteisino. Todėl dvejetainė skaičiavimo sistema (o tuo pačiu ir dvejetainė algebra) išliko absoliučiai dominuojanti kompiuterinės įrangos analizės ir sintezės srityje. Fizinės realizacijos aspektu tai paaiškinama labai paprastai: loginės reikšmės 0 ir 1 interpretuojamos kompiuteriuose paprastai – loginį 0 atitinka žemas įtampos lygis (artimas 0 V, “nėra įtampos”), o loginį 1 atitinka tam tikras įtampos lygis (apie +5 V, “yra įtampa”). Naudojant pavyzdžiui, trejetainę skaičiavimo sistemą jau prireiktų dviejų “nenulinės” įtampos lygių, kas reikštų būtinumą analizuoti šiuos lygius, o tuo pačiu ir kur kas sudėtingesnę techninę realizaciją.

1 Bulio algebra kaip algebrinė sistema

Bulio algebrą sudaro sistema

kur

B yra aibė,

 ir  yra dvivietės operacijos konjunkcija ir disjunkcija (toliau tekste vietoje simbolių  ir  naudosime atitinkamai * ir +, nes toks žymėjimas yra labiau įprastas Bulio algebroje),

yra vienvietė operacija neigimas,

0 ir 1 yra atitinkamai nulinis ir vienetinis elementai.

Šioje sistemoje galioja aksiomos:

1. Egzistuoja bent du elementai , tokie, kad a  b.

2. Visiems galioja:

a) ,

b) .

3. galioja:

a) – komutatyvumo atžvilgiu operacijos * dėsnis,

b) – komutatyvumo atžvilgiu operacijos + dėsnis.

4. a)  , toks, kad – egzistuoja nulinis elementas 0, toks, kad kiekvienam a iš aibės B galioja .

b)  , toks, kad – egzistuoja vienetinis elementas 1, toks, kad kiekvienam a iš aibės B galioja .

5. galioja:

b) – distributyvumo atžvilgiu operacijos “+” dėsnis,

b) – distributyvumo atžvilgiu operacijos “*” dėsnis.

6. (a neigimas arba a inversija), toks, kad

a) – kintamojo neigimo egzistavimo dėsnis,

b) – kintamojo neigimo egzistavimo dėsnis.

Aukščiau pateikta aksiomų sistema yra suderinta (t.y. nei viena iš aukščiau pateiktų aksiomų rinkinio neprieštarauja kuriai nors kitai iš šio rinkinio) ir nepriklausoma (t.y. nė viena iš rinkinio aksiomų negali būti įrodoma kitų rinkinio aksiomų pagalba). Egzistuoja panašumas tarp šių aksiomų rinkinio ir įprastinės algebros aksiomų, tačiau pilnos analogijos nėra, pavyzdžiui, distributyvumo atžvilgiu operacijos “+” dėsnis, t.y. įprastinėje algebroje negalioja.

Nesunku pastebėti, kad aukščiau pateiktoje aksiomų sistemoje beveik visos aksiomos (t.y. 2 – 6) yra sugrupuotos poromis. Taip pat akivaizdu, kad kiekvienoje poroje viena aksioma gali būti gaunama iš kitos, sukeitus vietomis operacijas + ir *, bei 1 ir 0. Šis principas vadinamas dualumo principu.

Pavyzdžiui,

( iš aksiomos 6 (a) gaunama jai duali 6 (b) ).

Praktiniame Bulio algebros taikyme didžiulį vaidmenį vaidina Bulio išraiškų pertvarkymas. Panagrinėsime kai kurias Bulio algebros teoremas, plačiai naudojamas tokiuose pertvarkymuose.

1. 

Įrodymas

– aksioma 4 (b)

– aksioma 6 (a)

– aksioma 5 (a)

– aksioma 6 (b)

– aksioma 4 (a).

Gavome, kad .

Žemiau pateikiamos (be įrodymo) kitos plačiai pertvarkymuose naudojamos teoremos.

2. – ši teorema, o taip pat ir aukščiau pateikta 1-oji teorema, vadinamos vienodos galios ( idempotentiškumo ) dėsniu.

3. ir – veiksmai su nuliniu ir vienetiniu elementais.

4. ir – padengimo (absorbcijos) dėsnis.

5. – dvigubo neigimo (involiucijos) dėsnis.

6. ir – De Morgano teorema.

1 Bulio funkcijos

Tegu yra n-matis vektorius, kur kiekvienas xi įgyja reikšmes iš aibės Bet kuri tokio vektoriaus X reikšmė yra vadinama atomu, o visų galimų atomų aibė Bn sudaro Bulio funkcijos apibrėžimo sritį. Akivaizdu, kad Bulio funkcijos apibrėžimo srities galia yra 2n. Bulio funkcijos kitimo sritis yra aibė Atvaizdavimas iš atomų aibės Bn į aibę yra vadinamas Bulio funkcija:Paprastai Bulio funkcija yra žymima , kur kintamieji yra vadinami Bulio kintamaisiais. Jei Bulio funkciją atitinkantis atvaizdavimas suskaido aibę Bn į du poaibius ir , tokius, kad , o , tai funkcija yra vadinama pilnai apibrėžta.

Jei atvaizdavimas suskaido aibę Bn į tris poaibius ir , tokius, kad , , o , kur d – neapibrėžta reikšmė (nuo angliško žodžio Don’t care), tai funkcija yra vadinama nepilnai apibrėžta.

Priklausomai nuo konkretaus praktinio pritaikymo tikslų, Bulio
funkcijos (BF) yra atvaizduojamos skirtingais būdais. Plačiausiai paplitę praktikoje yra šie būdai:

a) teisingumo lentelės;

b) diagramos;

c) analitinės išraiškos;

d) grafinis būdas;

e) matricinis būdas.

Panagrinėsime detaliau kiekvieną iš šių būdų.

BF atvaizdavimas teisingumo lentelėmis

n kintamųjų Bulio funkcijos teisingumo lentelė yra sudaryta iš stulpelio ir 2n eilučių:

• kiekvienas iš pirmųjų n stulpelių atitinka vieną pradinį kintamąjį;

• – asis stulpelis atitinka nagrinėjamos BF reikšmes;

• kiekviena eilutė atitinka vieną iš 2n BF kintamųjų kombinacijų.

5.2.1 lentelėje pateiktos dviejų funkcijų a) ir b) teisingumo lentelės:

2.1 lentelė. BF ir teisingumo lentelės

a)

b)

0 0 0 0 0 0

0 1 1 0 1 0

1 0 1 1 0 0

1 1 1 1 1 1

Jei nagrinėjamos kelios BF, priklausančios nuo tų pačių įėjimo kintamųjų, tada funkcijų užrašymo kompaktiškumo tikslu dviejų ar daugiau funkcijų teisingumo lentelių kairiosios dalys (atitinkančios įėjimo kintamuosius) yra sutapdinamos. Pavyzdžiui, BF ir galima užrašyti vienoje lentelėje (žr. 5.2.2 lentelė):

2.2 lentelė. BF ir teisingumo lentelė

0 0 0 0

0 1 1 0

1 0 1 0

1 1 1 1

Jei nagrinėjama funkcija yra nepilnai apibrėžta, tada jos teisingumo lentelėje funkcijos reikšmių stulpelyje yra ne tik reikšmės iš aibės bet ir d, t.y. iš aibės .

2.1. BF atvaizdavimas diagramomis

Plačiausiai naudojamas diagramų, naudojamų BF atvaizdavimui, tipas yra Karno ir Veičo diagramos. Bet kuriuo iš šių dviejų būdų atvaizduojant n kintamųjų funkciją , yra naudojama diagrama, turinti 2n langelių. Dažniausiai naudojamas diagramų pavidalas – stačiakampės. Jei nagrinėjama BF turi n kintamųjų, tai diagrama turi turėti 2n langelių, o pačios diagramos struktūra paprastai parenkama taip: skaičius n yra padalinamas maždaug pusiau, t.y. n = p + q, čia p ir q gali būti lygūs, bet nebūtinai. Pati diagrama yra konstruojama kaip stačiakampė struktūra, su kraštinėmis sudalintomis viena į dalių, kita į dalių. Skaičiaus n suskaidymas į dvi dalis p ir q ( n = p + q ) atitinka Bulio funkcijos kintamųjų aibės suskaidymą į du poaibius ir . Kiekvienas diagramos stulpelis (ir atitinkamai kiekviena eilutė) atitinka vieną kintamųjų kombinaciją. Pavyzdžiui, tegu turime 5 kintamųjų BF . Įėjimo kintamųjų aibę suskaidysime į du poaibius: ir . Tokiam suskaidymui atitinkanti BF atvaizduota 5.2.3 lentelėje.

2.3 lentelė. BF diagrama

000 001 011 010 110 111 101 100

00

01

10

11

Tokios struktūros BF diagrama vadinama Karno diagrama. Jos (kaip ir kiekvienos kito tipo diagramos) kiekvienas langelis atitinka vieną įėjimo kintamųjų kombinaciją. Tuo pačiu tame langelyje diagramoje rašoma BF reikšmė, atitinkanti duotą įėjimo kintamųjų kombinaciją (iš aibės pilnai apibrėžtoms BF ir iš aibės – nepilnai apibrėžtoms BF). Pavyzdžiui, 5.2.4 lentelėje pateikta diagrama atvaizduoja penkių kintamųjų pilnai apibrėžtą BF. Stulpelio 000 ir eilutės 00 sankirtoje esantis 0 reiškia, kad prie įėjimo kintamųjų kombinacijos 00000 nagrinėjamos BF reikšmė yra lygi 0. Analogiškai, stulpelio 000 ir eilutės 01 sankirtoje esantis 1 reiškia, kad prie įėjimo kintamųjų kombinacijos 00001 nagrinėjamos BF reikšmė yra lygi 1.

Šiuo metu Jūs matote 31% šio straipsnio.
Matomi 1221 žodžiai iš 3945 žodžių.
Peržiūrėkite iki 100 straipsnių per 24 val. Pasirinkite apmokėjimo būdą:
El. bankininkyste - 1,45 Eur.
Įveskite savo el. paštą (juo išsiųsime atrakinimo kodą) ir spauskite Tęsti.
SMS žinute - 2,90 Eur.
Siųskite sms numeriu 1337 su tekstu INFO MEDIA ir įveskite gautą atrakinimo kodą.
Turite atrakinimo kodą?
Po mokėjimo iškart gausite atrakinimo kodą, kurį įveskite į laukelį žemiau:
Kodas suteikia galimybę atrakinti iki 100 straispnių svetainėje ir galioja 24 val.