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à.

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:

Egzistuoja bent du elementai , tokie, kad a b.

Visiems galioja:

a)   

b)  

galioja:

a)    - komutatyvumo atžvilgiu operacijos * dësnis,

b)   - komutatyvumo atžvilgiu operacijos + dësnis.

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

galioja:

a)    - distributyvumo atžvilgiu operacijos “+” dësnis,

b)   - distributyvumo atžvilgiu operacijos “*” dësnis.

(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.

Á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.

- ši teorema, o taip pat ir aukšèiau pateikta 1-oji teorema, vadinamos vienodos galios idempotentiškumo dësniu.

ir - veiksmai su nuliniu ir vienetiniu elementais.

ir - padengimo (absorbcijos) dësnis.

- dvigubo neigimo (involiucijos) dësnis.

ir - De Morgano teorema.

Bulio funkcijos

Tegu yra n-matis vektorius, kur kiekvienas x_i ágyja reikšmes iš aibës Bet kuri tokio vektoriaus X reikšmë yra vadinama atomu, o visø galimø atomø aibë B_n sudaro Bulio funkcijos apibrëžimo sritá. Akivaizdu, kad Bulio funkcijos apibrëžimo srities galia yra 2ⁿ. Bulio funkcijos kitimo sritis yra aibë Atvaizdavimas iš atomø aibës B_n á aibæ yra vadinamas Bulio funkcija:

Paprastai Bulio funkcija yra žymima , kur kintamieji yra vadinami Bulio kintamaisiais. Jei Bulio funkcijà atitinkantis atvaizdavimas suskaido aibæ B_n á du poaibius ir , tokius, kad , o , tai funkcija yra vadinama pilnai apibrëžta.

Jei atvaizdavimas suskaido aibæ B_n á 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 2ⁿ 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š 2ⁿ BF kintamøjø kombinacijø.

2.1 lentelëje pateiktos dviejø funkcijø a) ir b)  teisingumo lentelës:

2.1 lentelë. BF ir teisingumo lentelës

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. 2.2 lentelë):

2.2 lentelë. BF ir teisingumo lentelë

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 .

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 2ⁿ langeliø. Dažniausiai naudojamas diagramø pavidalas – staèiakampës. Jei nagrinëjama BF turi n kintamøjø, tai diagrama turi turëti 2ⁿ 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 2.3 lentelëje.

2.3 lentelë. BF diagrama

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, 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.

2.4 lentelë Penkiø kintamøjø BF Karno diagramos pavyzdys

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, 2.5 lentelëje pateikta 5 kintamøjø BF Veièo diagrama, atitinkanti kintamøjø suskaidymà á du poaibius ir :

2.5 lentelë. Penkiø kintamøjø BF Veièo diagrama

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 x reikšmæ 1 atitinka išryškinta diagramos dalis, pavaizduota 2.6 lentelëje:

2.6 lentelë. Karno diagrama su išryškinta sritimi, atitinkanèia x₁=1

Atitinkamai, Karno diagramoje x reikšmæ 1 atitinka išryškinta diagramos dalis, pavaizduota 2.7 lentelëje:

2.7 lentelë. Karno diagrama su išryškinta sritimi, atitinkanèia x₃=1

Veièo diagramose kintamøjø x₁ ir x reikšmes, lygias 1, atitinka 2.8 a) ir 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:

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

Veièo diagrama – kintamøjø reikšmiø kombinacijos yra tiesiog iš eilës einantys skaièiai (pavyzdžiui, jei n = , 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à.

lentelë. Penkiø kintamøjø BF Veièo diagramos

a) išryškinta sritis,atitinkanti x₁ = 1

b) išryškinta sritis, atitinkanti x₃ = 1

Sudarant n kintamøjø BF Karno ir Veièo diagramas, galima vadovautis tokia procedûra:

n kintamøjø aibë suskaidoma á du lygius arba apylygius poaibius

Braižoma dydžio diagrama.

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.

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 x_i 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á x , tai vieno kintamojo BF diagramà galima ásivaizduoti kaip staèiakampá, padalintà pusiau:

Ávedant dar vienà kintamàjá x₂ , turimà staèiakampá (tiksliau, abi jo dalis) reikia padalinti dar á dvi dalis:

Ávedant dar vienà kintamàjá x , 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:

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 á 2ⁿ 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š 2ⁿ 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:

Karno diagrama:

Veièo diagrama:

Apskritiminë diagrama (trumpumo dëlei diagramos segmentai, t.y. áëjimo kintamøjø kombinacijos yra pažymëti 8-ainiais Grëjaus kodo skaièiais):

Analitinis BF užrašymo bûdas

Šiuo bûdu Bulio funkcija yra atvaizduojama analitinës išraiškos pagalba, naudojant kintamuosius x_i 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, vietoje 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ø ⁿ kintamøjø reikšmiø , tuo tarpu makstermas iš visos n áëjimo kintamøjø reikšmiø erdvës išskiria reikšmes iš visø galimø ⁿ 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 pavidalas, 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 BF

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à galima 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):

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æ . Kiekviena áë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 . pav.:

2.2 pav Grafinis atvaizdavimas

Matricinis BF atvaizdavimo bûdas

Šiuo bûdu Bulio funkcijos yra atvaizduojamos dvejetainiø matricø pagalba. Jei turime n kintamøjø BF, tai jai atvaizduoti matriciniu 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 F⁰ ir F¹. 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 F^d, kuri atitinka kintamøjø kombinacijas, prie kuriø BF yra neapibrëžta. Šiuo atveju matricos ir ir F^d 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, TDNF 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 F^d ) 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 F^d 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:  .

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š skliaustus. 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à ; atitinka áëjimo kintamøjø reikšmiø kombinacijà , 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 pagalbinis 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à:

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 vienetai, esantys išryškintoje diagramos srityje žemiau ir atitinkantys mintermus ir gali bûti apjungti á vienà

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 turime 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 apjungta á vienà junginá, atitinkantá termà , o plokštumos dalis, apribota taškais 000, 001, 010 ir 011, sudaro junginá (žr. 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 algoritmus, 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.