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 yyra į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į 00 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, oo 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 BB 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 ppilnos 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 ffunkcijos 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

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 llentelė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

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 eeilutės 01 sankirtoje esantis 1 reiškia, kad prie įėjimo kintamųjų kombinacijos 00001 nagrinėjamos BF reikšmė yra lygi 1.

2.4 lentelė. Penkių kintamųjų BF Karno diagramos pavyzdys

000 001 011 010 110 111 101 100

00 0 0 1 0 0 1 1 1

01 1 0 0 1 1 1 0 0

11 0 1 0 1 0 1 1 1

10 1 1 0 0 0 0 1 0

BF Veičo diagrama skiriasi nuo aukščiau aprašytos Karno diagramos tik kintamųjų kombinacijų išsidėstymu diagramoje. Jei Veičo diagramoje stulpeliai ir eilutės žymimi dvejetainiais kodais, surašytais leksikografine tvarka, tai Karno diagramoje jie žymimi Grėjaus kodais. Pavyzdžiui, 5.2.5 lentelėje pateikta 5 kintamųjų BF Veičo diagrama, atitinkanti kintamųjų suskaidymą į du poaibius ir :

2.5 lentelė. Penkių kkintamųjų BF Veičo diagrama

000 001 010 011 100 101 110 111

00 0 0 0 1 1 1 0 1

01 1 0 1 0 0 0 1 1

10 0 1 1 0 1 1 0 1

11 1 1 0 0 0 1 0 0

Bet kuriuo atveju (tiek Karno, tiek Veičo diagramų atveju) pusė diagramos langelių atitinka bet kurio kintamojo reikšmę, lygią 0, o kita pusė langelių – to paties kintamojo reikšmę, lygią 1. Pavyzdžiui, Karno diagramoje xx1 reikšmę 1 atitinka išryškinta diagramos dalis, pavaizduota 5.2.6 lentelėje:

2.6 lentelė. Karno diagrama su išryškinta sritimi, atitinkančia x1=1

000 001 011 010 110 111 101 100

00 0 0 1 0 0 1 1 1

01 1 0 0 1 1 1 0 0

11 0 1 0 1 0 1 1 1

10 1 1 0 0 0 0 1 0

Atitinkamai, Karno diagramoje x3 reikšmę 1 atitinka išryškinta diagramos dalis, pavaizduota 5.2.7 lentelėje:

2.7 lentelė. Karno diagrama su išryškinta sritimi, atitinkančia x3=1

000 001 011 010 110 111 101 100

00 0 0 1 0 0 1 1 1

01 1 0 0 1 1 1 0 0

11 0 1 0 1 0 1 1 1

10 1 1 0 0 0 0 1 0

Veičo diagramose kintamųjų x1 ir x3 reikšmes, lygias 1, atitinka 5.2.8 a) ir 5.2.8 b) lentelėse pavaizduotos diagramų dalys.

Nesunku pastebėti, kad interpretuojant kintamųjų kombinacijas kaip dvejetainius skaičius, jų išsidėstymas diagramose yra:

1) Karno diagrama – iš eilės rašomi skaičiai atitinka Grėjaus kodo iš eilės einančias kombinacijas (pavyzdžiui, jei n = 3, tai kombinacijų reikšmės yra 0, 1, 3, 2, 6, 7, 5, 4);

2) Veičo diagrama – kintamųjų reikšmių kombinacijos yra tiesiog iš eilės einantys skaičiai (pavyzdžiui, jei n = 3, tai kombinacijų reikšmės yra 0, 1, 2, 3, 4, 5, 6, 7).

Toks skirtingas kombinacijų išsidėstymas yra svarbus tik tolimesniam diagramų panaudojimui BF minimizacijoje. Pačią diagramą yra paprasčiau sudaryti naudojant Veičo diagramos struktūrą, tačiau naudojant Karno diagramas yra šiek tiek patogiau atlikti BF minimizavimą.

2.8 lentelė. Penkių kintamųjų BF Veičo diagramos

a) išryškinta sritis,atitinkanti x1 = 1

000 001 010 011 100 101 110 111

00 0 0 0 1 1 1 0 1

01 1 0 1 0 0 0 1 1

10 0 1 1 0 1 1 0 1

11 1 1 0 0 0 1 0 0

b) išryškinta sritis, atitinkanti x3 = 1

000 001 010 011 100 101 110 111

00 0 0 0 1 1 1 0 1

01 1 0 1 0 0 0 1 1

10 0 1 1 0 1 1 0 1

11 1 1 0 0 0 1 0 0

Sudarant n kintamųjų BF Karno ir Veičo diagramas, galima vadovautis tokia procedūra:

1. n kkintamųjų aibė suskaidoma į du lygius arba apylygius poaibius

2. Braižoma dydžio diagrama.

3. Naudojant Karno diagramos struktūrą, kintamųjų reikšmių kombinacijos yra išdėstomos kaip Grėjaus kodo skaičių dvejetainės išraiškos. Naudojant Veičo diagramos struktūrą, kintamųjų reikšmių kombinacijos yra išdėstomos kaip iš eilės einantys dvejetainiai skaičiai.

4. Atitinkamuose langeliuose įrašomos BF reikšmės.

Galimi ir kiti Karno ir Veičo diagramų sudarymo būdai. Jau minėjome, kad bet kurioje diagramoje bet kurio kintamojo xi atžvilgiu pusė diagramos langelių atitinka , o kita pusė – . Todėl galima traktuoti, kad bet kokio dydžio (bet kuriam kintamųjų skaičiui n) diagrama yra sudaroma, paimant stačiakampį ir nuosekliai jį dalinant į reikiamą skaičių dalių. Pavyzdžiui, jei turime tik vieną kintamąjį x1, tai vieno kintamojo BF diagramą galima įsivaizduoti kaip stačiakampį, padalintą pusiau:

Įvedant dar vieną kintamąjį x2 , turimą stačiakampį (tiksliau, abi jo dalis) reikia padalinti dar į dvi dalis:

Įvedant dar vieną kintamąjį x3 , turimą diagramą reikia dar padvigubinti. Tas padvigubinimas gali būti atliktas dvejopai:

Šiuo atveju gavome Veičo diagramą.

Šiuo atveju gavome Karno diagramą.

Nesunku pastebėti, kad geometriškai dar vieno kintamojo įvedimas į Veičo diagramą reiškia esamos diagramos pakartojimą šalia kurios nors esamos diagramos kraštinės. Tuo tarpu dar vieno kintamojo įvedimas į Karno diagramą reiškia esamos diagramos pakartojimą kaip veidrodinį atspindį ššalia kurios nors esamos diagramos kraštinės. Pavyzdžiui:

1) Veičo diagrama

2) Karno diagrama

Dar vienas kartais naudojamas praktikoje diagramos BF atvaizdavimui tipas – apskritiminės diagramos. Kaip rodo pavadinimas, šio tipo BF vaizdavimo pagrindą sudaro apskritimas arba skritulys. Jei turime n kintamųjų BF, tai šiai BF atvaizduoti apskritimas yra padalinamas į 2n segmentų, kiekvienas iš kurių ir atitinka vieną įėjimo kintamųjų kombinaciją. Šios kombinacijos paprastai išdėstomos tokioje diagramoje kaip nuosekliai einančios Grėjaus kodo skaičių sekos. Kaip ir bet kurioje kito tipo diagramoje, pusę iš 2n diagramos segmentų atitinka kiekvieną kintamąjį, o likusioji pusė – to kintamojo inversiją.

Pavyzdžiui, trijų kintamųjų BF atvaizdavimui apskritiminės diagramos pagalba, gautume tokio tipo diagramą (žr. 2.1 pav.):

2.1 pav. Trijų kintamųjų BF apskritiminė diagrama

Įvairių BF atvaizdavimui naudojamų diagramų tipų palyginimui žemiau pateikiame penkių kintamųjų BF

atvaizdavimą Karno, Veičo ir apskritiminės diagramų pagalba:

1) Karno diagrama:

000 001 011 010 110 111 101 100

00 1 0 0 0 1 0 0 0

01 0 0 0 0 1 0 0 0

11 0 1 0 0 0 0 1 0

10 0 0 0 0 1 0 0 0

2) Veičo diagrama:

000 001 010 011 100 101 110 111

00 1 0 0 0 0 0 1 0

01 0 0 0 0 0 0 1 0

10 0 0 0 0 0 0 1 0

11 0 1 0 0 0 1 0 0

3) Apskritiminė diagrama (trumpumo dėlei diagramos segmentai, t.y. įėjimo kintamųjų kombinacijos yra pažymėti 8-ainiais Grėjaus kodo skaičiais):

1.1 Analitinis BF užrašymo būdas

Šiuo būdu Bulio funkcija yra atvaizduojama analitinės išraiškos pagalba, naudojant kintamuosius xi bei ir kitų operacijų ženklus.

Pavyzdžiui, . BF užrašo supaprastinimui vietoje disjunkcijos ženklo toliau naudosime ženklą +, o konjunkciją vaizduosime kaip vienas šalia kito parašytus kintamuosius, t.y. pavyzdžiui, vvietoje naudosime . Tuo būdu vietoje aukščiau užrašytos funkcijos naudosime paprastesnį užrašą .

Viena ir ta pati BF analitiniu būdu gali būti atvaizduota nevienodai, todėl dažnai yra naudojami taip vadinami kanoniniai (arba standartizuoti) analitinio atvaizdavimo, kartais dar naudojama sąvoka normaliniai, būdai. Dažniausiai yra naudojami du normaliniai BF pavidalai: disjunktyvinis ir konjunktyvinis. Prieš plačiau aprašant šiuos pavidalus, apibrėšime termo, mintermo ir makstermo sąvokas.

Termu yra vadinama n kintamųjų BF išraiška, sudaryta iš m (m  n) kintamųjų, apjungtų vienos iš operacijų “konjunkcija” arba “disjunkcija” ženklais.

n kintamųjų BF mintermu yra vadinamas termas, sudarytas iš n kintamųjų, apjungtų konjunkcijos operacijos ženklais, t.y. n kintamųjų konjunkcija.

n kintamųjų BF makstermu yra vadinamas termas, sudarytas iš n kintamųjų, apjungtų disjunkcijos operacijos ženklais, t.y. n kintamųjų disjunkcija.

(Termo, mintermo ir makstermo apibrėžimuose naudojama sąvoka “kintamasis” yra suprantama kaip kintamasis tiesioginiame pavidale arba jo inversija (neigimas)). Sąvokų mintermas ir makstermas naudojimas yra pagrįstas tuo, kad mintermas iš visos BF įėjimo kintamųjų reikšmių erdvės išskiria tik vieną reikšmę (vieną iš visų galimų 2n kintamųjų reikšmių), tuo tarpu makstermas iš visos n įėjimo kintamųjų reikšmių erdvės išskiria reikšmes (iš visų galimų 2n kintamųjų reikšmių)

BF disjunktyvine normaline forma (DNF) yra vadinama

nagrinėjamos BF kintamųjų konjunkcijų suma (disjunkcija).

BF konjunktyvine normaline forma (KNF) yra vadinama nagrinėjamos BF kintamųjų disjunkcijų loginė sandauga (konjunkcija).

BF tobula disjunktyvine normaline forma (TDNF) yra vadinama BF kintamųjų mintermų suma (disjunkcija).

BF tobula konjunktyvine normaline forma (TKNF) yra vadinama BF kintamųjų makstermų loginė sandauga (konjunkcija).

Kaip jau buvo minėta, viena ir ta pati BF gali turėti labai daug analitinių pavidalų. TDNF arba TKNF naudojimas turi tą privalumą, kad vienai ir tai pačiai funkcijai egzistuoja vienintelis TDNF arba TKNF ppavidalas, tuo tarpu viena ir ta pati BF gali turėti labai įvairias DNF arba KNF. Iš kitos pusės, ypač kai kalba eina apie techninę BF realizaciją, ekonomiškumo aspektu tikslinga turėti trumpiausią analitinę išraišką. TDNF arba TKNF beveik visada nėra pačios trumpiausios išraiškos. Todėl, pavyzdžiui, pradiniame BF sintezės etape, aprašant skaitmeninių įrenginių darbą ir pan., dažnai yra patogu naudoti TDNF arba TKNF, o vėliau jos minimizuojamos į trumpesnes išraiškas (dažnai DNF arba KNF), kurių aparatūrinė realizacija yra pigesnė.

Pavyzdžiui, tegu turime BBF

Kadangi nagrinėjamos BF DNF sudarantys termai yra mintermai, tai akivaizdu, kad turime TDNF. Ta pati nagrinėjama BF gali būti užrašyta ir taip:

Akivaizdu, kad šis BF pavidalas yra kur kas trumpesnis už anksčiau nagrinėtą TDNF.

Kaip atskirą analitinės išraiškos modifikaciją ggalima taip pat nagrinėti BF užrašą, susidedantį iš ženklo ir po jo skliaustuose einančio nagrinėjamos funkcijos TDN formą sudarančių mintermų numerių sąrašo. Pavyzdžiui, ankstesniajame pavyzdyje pateiktos BF išraiška, užrašyta tokiame pavidale, yra:

Toks BF pavidalas kartais yra vadinamas skaitmeniniu. Jis yra patogus trumpesniam BF užrašymui. Kartais, ypač kai BF kintamųjų skaičius yra didesnis, į TDNF įeinančių mintermų numeriams išreikšti yra patogu naudoti ir kitas skaičiavimo sistemas. Tuo atveju prie ženklo yra nurodoma, kokia skaičiavimo sistema yra naudojama mintermų numerių užrašams.

Pavyzdžiui, tegu turime BF

Šios BF skaitmeninis pavidalas gali būti pateikiamas taip (trys alternatyvūs variantai):

1) ;

2) ;

3) .

1.1 Grafinis BF atvaizdavimo būdas

Šiuo būdu n kintamųjų Bulio funkcija yra atvaizduojama kaip n-mačio hiperkubo viršūnių aibės atvaizdavimas į aibę {0, 1}. KKiekviena įėjimo kintamųjų kombinacija atitinka vieną hiperkubo viršūnę. Taigi grafiniame BF atvaizdavime nagrinėjamos BF reikšmės yra pažymimos ties atitinkama hiperkubo viršūne. Pavyzdžiui, vienetinės BF reikšmės yra pažymimos taškais arba apskritimais ties atitinkamomis viršūnėmis.

Tegu turime 3 kintamųjų BF. Jos atvaizdavimui grafiniu būdu reikia panaudoti 3-matį kubą. Tegu nagrinėjama Bulio funkcija yra . Jos grafinis atvaizdavimas parodytas 5.2.2 pav.:

2.2 pav. Grafinis atvaizdavimas

1.1 Matricinis BF atvaizdavimo būdas

Šiuo būdu Bulio funkcijos yra atvaizduojamos dvejetainių matricų pagalba. Jei turime n kintamųjų BF, tai jai atvaizduoti mmatriciniu būdu yra naudojama ( m x n ) matrica, kur m yra BF įėjimo kintamųjų kombinacijų, prie kurių nagrinėjama BF įgyja vienetines reikšmes, skaičius.

Pavyzdžiui, tegu turime BF

(skaitmeninis pavidalas

Šios funkcijos matricinis pavidalas yra: .

Analogiškai matriciniu būdu galima atvaizduoti tą pačią funkciją, nurodant ne Bulio funkcijos vienetines reikšmes atitinkančių kintamųjų kombinacijų aibę, bet nulines reikšmes atitinkančių kintamųjų kombinacijų aibę. Tam, kad atskirti, kokios kombinacijos (atitinkančios 0 ar 1), yra pateikiamos matriciniame pavidale, yra naudojamos matricos, žymimos F0 ir F1. Aukščiau pateiktam pavyzdžiui matricos ir būtų:

Akivaizdu, kad turint pilnai apibrėžtą BF, abiejų matricų ir eilutės sudaro pilną galimų įėjimo kintamųjų reikšmių aibę, t.y. yra visos galimų kintamųjų reikšmių aibės suskaidymas. Kitaip tariant, matricos ir yra viena kita papildančios, o konkrečiai funkcijai apibrėžti pakanka nurodyti kurią nors vieną iš jų. Jeigu turime nepilnai apibrėžtą BF, tada šalia ir naudojama dar viena matrica Fd, kuri atitinka kintamųjų kombinacijas, prie kurių BF yra neapibrėžta. Šiuo atveju matricos ir ir Fd yra visos galimų kintamųjų reikšmių aibės suskaidymas, ir konkrečiai BF apibrėžti pakanka nurodyti kurias nors dvi iš šių trijų matricų.

Iki šiol nagrinėti visi BF atvaizdavimo būdai, lyginant juos su analitinėmis išraiškomis, atitiko BF atvaizdavimą TDNF. Kaip jau minėjome anksčiau, TTDNF dažniausiai yra labai neekonomiška praktinės realizacijos prasme, todėl praktikoje dažnai yra naudojami įvairūs BF minimizacijos metodai, leidžiantys gauti kitas, trumpesnes BF išraiškas (dažnai – DNF pavidale). Šiek tiek modifikavus matricinį metodą, jo pagalba galima atvaizduoti ir BF, išreikštas DNF. Ši modifikacija susiveda į tai, kad vietoje dvejetainių matricų ir (arba ir ir Fd ) yra naudojamos atitinkamos trejetainės matricos. Šiuo atveju vietoje matricos elementų 0 ir 1 yra naudojami elementai 0, 1 ir “-“, kur elementas “-“ reiškia, kad į nagrinėjamą termą šis kintamasis neįeina (dvejetainėse matricose ir ir Fd j-oji matricos eilutė atitinka pilną n kintamųjų konjunkciją, t.y. j-ajį mintermą).

Pavyzdžiui, tegu turime pilnai apibrėžtą BF

Šios funkcijos matricinis pavidalas yra: .

1 Bulio funkcijų minimizavimas

Aukščiau pateiktame pavyzdyje nagrinėtos funkcijos išraiška gali būti pertvarkyta taip: .

Toks Bulio funkcijos pertvarkymo procesas, kurio pasėkoje gaunama paprastesnė BF išraiška, yra vadinamas Bulio funkcijų minimizavimu. Jį galima atlikti įvairiais būdais. Vienas iš jų – Bulio funkcijos analitinės išraiškos pertvarkymas, pasinaudojant Bulio algebros dėsniais. Pavyzdžiui:

( .

Panašiu būdu gauname, kad , bei ).

pasinaudojame dėsniu

Tokiu būdu vietoje pradinės išraiškos gavome TDNF. Tolimesnis išraiškos pertvarkymas galimas vėl įvairiais būdais. Panagrinėsime bent porą iš jų.

Pirmasis remiasi narių gautoje išraiškoje grupavimu ir bendrų dalių iškėlimu prieš sskliaustus. Pavyzdžiui, sugrupavus ankstesnės išraiškos pabrauktus mintermus ir iškėlus prieš skliaustus , gauname:

nes skliaustuose esantys nariai duoda loginį vienetą (grupavimas, iškėlimas prieš skliaustus ir dėsnis ). Analogiškai paskutinių keturių mintermų suma duoda reikšmę (čia taip pat naudojamės dėsniu, kad , tai leidžia panaudoti mintermus ir po du kartus – vieną kartą kaip įeinančius į pirmąją keturių mintermų sumą, ko pasėkoje gauname , o antrą kartą – kaip įeinančius į antrąją keturių mintermų sumą, ko pasėkoje gauname ). Mintermų ir suma duoda . To rezultate ir gauname:

Antrasis minimizuojamos funkcijos tarpinės išraiškos (TDNF) pertvarkymo būdas remiasi tuo, kad pilnai apibrėžta funkcija yra galimos įėjimo kintamųjų reikšmių aibės suskaidymas į du poaibius: vieną, prie kurio funkcijos reikšmės yra lygios 1, ir antrą, prie kurio funkcijos reikšmės yra lygios 0. Bulio funkcijos tobulą disjunktyvinę normalinę formą sudarantys mintermai atitinka pirmąjį tokį poaibį, t.y. poaibį, prie kurio funkcijos reikšmės yra lygios 1. Jeigu disjunkcijos pagalba apjungsime mintermus, įeinančius į antrąjį poaibį, tai gausime funkciją , priešingą duotajai f, t.y. tokią, kuri įgyja reikšmes, lygias 1, prie tų įėjimo kintamųjų kombinacijų, prie kurių pradinė funkcija lygi 0, ir atvirkščiai. Akivaizdu, kad trijų kintamųjų funkcijai visų galimų įėjimo kintamųjų reikšmių aibę nusako

mintermai , t.y. atitinka įėjimo kintamųjų reikšmių kombinaciją 000; atitinka įėjimo kintamųjų reikšmių kombinaciją 001, ir t.t. Jei į funkcijos TDNF įeinantys mintermai sudaro aibę , tai

kur –poaibis mintermų, atitinkančių BF kintamųjų reikšmių kombinacijas, prie kurių funkcija lygi 0. Todėl, jei funkcijos TDNF apibrėšime kaip

tai jai priešingos funkcijos tobulą disjunktyvinę normalinę formą galima išreikšti taip:

čia – aibių ir skirtumas.

Todėl aukščiau nagrinėto pavyzdžio funkciją galima išreikšti ir kitaip:

(pagal De Morgano dėsnį).

Analitinis būdas BF minimizavimui naudojamas gana retai ir tiktai kaip ppagalbinis metodas, nes reikalauja gana daug darbo sąnaudų. Kur kas plačiau praktikoje yra naudojami kiti metodai. Bene efektyviausiai (bent jau rankiniu būdu) BF yra minimizuojamos naudojant diagramų metodą. Panagrinėsime BF Karno diagramų panaudojimą minimizavimui.

Tegu turime nagrinėjamos funkcijos

Karno diagramą:

00 01 11 10

0 1 1 1 0

1 1 1 1 1

Karno diagramos panaudojimas BF atvaizdavimui turi savybę, kad 2, 4, 8, ., nagrinėjamos BF mintermus atitinkantys diagramos vienetai, esantys greta, gali būti apjungti į vieną junginį ir atitinkamai funkcijos disjunktyvinėje normalinėje formoje gali būti atvaizduoti vienu termu. Pavyzdžiui, du vvienetai, esantys išryškintoje diagramos srityje žemiau ir atitinkantys mintermus ir gali būti apjungti į vieną

00 01 11 10

0 1 1 1 0

1 1 1 1 1

junginį ir atvaizduoti disjunktyvinėje normalinėje formoje kaip termas . Tuo pačiu vietoje nagrinėjamos funkcijos tobuloje disjunktyvinėje normalinėje formoje esančių dviejų mintermų ir sumos tturime atitinkantį tuos du mintermus termą :

Toks funkcijos užrašo sutrumpinimo procesas, pasinaudojant diagramoje greta esančių vienetų savybe, atitinka dviejų mintermų ir grupavimą, bendros dalies iškėlimą prieš skliaustus ir dėsnio pritaikymą.

Analogiškai galima apjungti ir keturis šalia esančius vienetus. Išryškintoje srityje

esantys vienetai, atitinkantys mintermus , , ir duoda termą . Analogiškai:

Tokiu būdu pastarųjų trijų junginių pagalba yra padengiami visi pradinės BF vienetai ir turime minimizuotą BF pavidalą:

Panagrinėsime grafinio BF atvaizdavimo panaudojimą BF minimizacijai. Tegu turime 3 kintamųjų BF . Jos grafinis atvaizdavimas yra:

3.1 pav. BF grafinis atvaizdavimas

Bulio funkcijos grafiniame atvaizdavime tiesės atkarpos (arba plokštumos), apribotos hiperkubo viršūnėmis, atitinkančiomis BF reikšmes, lygias vienetui, sudaro junginius, kurie gali būti atvaizduoti vienu termu. Pavyzdžiui, tiesės atkarpa, apribota vienetiniais taškais 011 ir 111 gali būti aapjungta į vieną junginį, atitinkantį termą , o plokštumos dalis, apribota taškais 000, 001, 010 ir 011, sudaro junginį (žr. 5.3.2 pav.).

3.2 pav. BF minimizavimo grafinis atvaizdavimas

Tokiu būdu, nagrinėjama funkcija minimizuotame pavidale gali būti atvaizduota kaip šių dviejų termų disjunkcija:

Bulio funkcijos vaidina svarbų vaidmenį skaitmeninių įrenginių analizėje ir sintezėje. Praktikoje sutinkami uždaviniai paprastai pasižymi didele apimtimi, todėl yra naudojamos automatizuotos priemonės, tame tarpe BF minimizavimas kompiuterinėmis priemonėmis. Konkrečios kompiuterinės programos šiam uždaviniui spręsti paprastai naudoja kitus BF minimizavimo metodus ir aalgoritmus, kurie yra orientuoti į BF atvaizdavimą kompiuteriuose, įvertina naudojamos techninės įrangos specifiką ir tuo pačiu leidžia efektyviai spręsti didelės apimties uždavinius.