Boole'i algebra lihtsustaja

Boole'i algebra minimeerimine digitaaltehnikas

Boole'i algebra lihtsustamine on digitaalloogika ja skeemidisaini nurgakivi. Keeruliste loogikaavaldiste taandamine nende lihtsaimale kujule võimaldab luua optimaalsemaid digitaalskeeme, mis nõuavad vähem loogikaelemente, tarbivad vähem energiat ja töötavad kiiremini.

Käsitsi minimeerimine muutub aga muutujate arvu kasvades kiiresti veaohtlikuks ja keeruliseks. Boole'i algebra lihtsustaja lahendab selle probleemi, pakkudes kohest ja täpset arvutust, mis teisendab sisestatud avaldise otse selle minimaalseteks matemaatilisteks kujudeks. Tööriist arvutab paralleelselt välja nii minimaalse disjunktiivse normaalkuju (SOP) kui ka minimaalse konjunktiivse normaalkuju (POS). Lisaks lõpptulemusele genereeritakse täielik rida-realt tõetabel ning detailne sammsammuline tuletuskäik, mis põhineb Quine–McCluskey algoritmil.

Sisendvormingud ja kasutusliides

Tööriist toetab kuni 6 erinevat muutujat ja maksimaalselt 2 000 märgi pikkuseid avaldisi. Muutujad kirjutatakse ühekordsete tähtedena. Erinevate valdkondade harjumuste toetamiseks aktsepteerib sisendväli väga erinevaid tähistussüsteeme, mida võib vajadusel ka omavahel segada:

• AND (konjunktsioon): Võib kirjutada kaudselt ilma sümbolita (näiteks AB), punktiga A·B, tärniga A*B, programmeerimisstiilis A && B, loogikasümboliga või tavasõnaga A AND B. Mitmetähelised jadad nagu ABC tõlgendatakse automaatselt konjunktsioonina A AND B AND C.
• OR (disjunktsioon): Kirjutatakse plussmärgina A + B, programmeerimisstiilis A || B, loogikasümboliga või tavasõnaga A OR B.
• NOT (eitus): Võib märkida ülakomaga pärast muutujat A', hüüumärgiga !A, loogikasümboliga ¬A või tavasõnaga NOT A.
• XOR (välistav OR): Kirjutatakse sümbolitega A ^ B või A ⊕ B, samuti tavasõnaga A XOR B.
• NAND: Kirjutatakse kujul A NAND B või sümboliga ⊼.
• NOR: Kirjutatakse kujul A NOR B või sümboliga ⊽.
• Konstandid: Lubatud on kasutada väärtusi 0 ja 1.

Kasutajaliides sisaldab mugavaid juhtelemente operaatorite lisamiseks ja sisendi tühjendamiseks nupuga "Tühjenda". Kiireks testimiseks on lisatud kolm näidisavaldist:

• "Terminite ühendamine" (konsensuse seaduse näide)
• "Eitatud korrutis" (De Morgani seaduse näide)
• "Kolme muutuja XOR" (XOR-tehte näide)

Kui sisestusväli on tühi, kuvatakse juhis: "Sisestage Boole'i avaldis, et näha selle lihtsaimat konjunktiivset normaalkuju, disjunktiivset normaalkuju ja nende leidmise käiku.".

Quine–McCluskey algoritm ja lihtsustamise etapid

Erinevalt heuristilistest meetoditest, mis ei pruugi alati tagada absoluutset miinimumi, kasutab see tööriist Quine–McCluskey algoritmi koos täpse minimaalse katte leidmisega. See on tabelipõhine meetod, mis sobib ideaalselt arvutiga minimeerimiseks ja tagab matemaatiliselt kõige lihtsama tulemuse.

Minimeerimisprotsess koosneb järgmistest sammudest, mida kuvatakse jaotises "Kuidas seda lihtsustati":

1. Tõetabeli ja mintermide leidmine: Tööriist tuvastab muutujate arvu ja koostab tõetabeli. Kui avaldis kasutab näiteks kolme muutujat, kuvatakse teade: "Avaldis kasutab 3 muutujat (A, B, C), seega on tõetabelis 8 rida.". Kui muutujaid on üks, kuvatakse vastav teade ühe muutuja kohta, ning muutujate puudumisel viidatakse konstantsele väärtusele. Seejärel kaardistatakse read, kus funktsiooni väärtus on 1 (mintermid) ja kus see on 0 (makstermid), näiteks kujul: "See võrdub 1-ga ridadel Σm(1, 3, 5, 7) ja 0-ga ridadel ΠM(0, 2, 4, 6).".
2. Lihtimplikantide leidmine: Külgnevaid 1-ridu koondatakse süstemaatiliselt, asendades muutuvaid literaale kriipsudega, kuni edasine koondamine pole võimalik. Tulemusena kuvatakse leitud lihtimplikantide arv ja nimekiri.
3. Oluliste lihtimplikantide eraldamine: Tööriist tuvastab olulised lihtimplikandid, mis on ainsaks katteks vähemalt ühele 1-reale. Kui sellised implikandid eksisteerivad, loetletakse need üles. Kui iga 1-rida saab katta mitmel viisil, kuvatakse teade: "Ükski lihtimplikant pole oluline: iga 1-rida saab katta rohkem kui ühel viisil.".
4. Katte optimeerimine: Kui olulised lihtimplikandid ei kata veel kõiki 1-ridu, lahendatakse katteprobleem vähima võimaliku arvu lisaterminitega. Kui kõik read on juba kaetud, kuvatakse teade: "Olulised lihtimplikandid katavad juba iga 1-rea, seega on summa täielik.".
5. POS-kuju tuletamine: Sama koondamisprotseduur viiakse läbi tõetabeli 0-ridadel, mis annab tulemuseks minimaalse konjunktiivse normaalkuju.

Väljundandmed ja diagnostika

Pärast avaldise edukat analüüsimist kuvatakse tulemused jaotises "Minimaalne kuju". Kasutajale esitatakse järgmised andmed:

• Tõlgendus: Sisestatud avaldise normaliseeritud ja standarditud kuju.
• Minimaalne disjunktiivne normaalkuju (SOP): Minimeeritud korrutiste summa.
• Minimaalne konjunktiivne normaalkuju (POS): Minimeeritud summade korrutis.
• Lühikokkuvõte: Diagnostikapaneel, mis näitab tuvastatud muutujaid, 1-ga võrduvaid ridu, lihtimplikantide ja oluliste lihtimplikantide arvu, literaalide arvu enne ja pärast lihtsustamist ning kasutatud meetodit ("Quine–McCluskey, täpne minimaalne kate").
• Tõetabel: Täielik tabel, mis sisaldab veergusid muutujate, algse avaldise ("Avaldis") ja lihtsustatud SOP-kuju ("Minimaalne SOP") kohta, võimaldades visuaalselt veenduda nende samasuses.

Tulemusi saab mugavalt kopeerida nupuga "Kopeeri tulemus". Eduka lihtsustamise korral kuvatakse olekuteade: "Lihtsustatud ja kontrollitud kõigil ‹rows› real.".

Erandjuhud ja veatuvastus

Tööriist käsitleb korrektselt kõiki matemaatilisi erandjuhte ja süntaksivigu:

• Konstantsed avaldised: Kui avaldis on tautoloogia (alati tõene) või vastuolu (alati väär), kuvatakse teade "See avaldis on konstantne: selle väärtus on alati ‹value›." koos selgitusega, et ükski väärtuste kombinatsioon ei muuda tulemust või et iga kombinatsioon teeb selle tõeseks.
• Juba minimaalne kuju: Kui sisestatud avaldist ei saa enam lihtsamaks teha, teavitab süsteem: "Teie avaldis on juba minimaalsel disjunktiivsel normaalkujul.".
• Süntaksivead: Vigaste sisestuste korral kuvatakse täpsed eestikeelsed veateated, mis aitavad viga positsiooni järgi tuvastada. Näiteks teavitatakse kasutajat tasakaalustamata sulgudest, lubamatutest märkidest, liiga suurest muutujate arvust või puuduvatest operandidest operaatorite +, · või ⊕ lähedal.

Privaatsus ja andmetöötlus

Kasutaja privaatsus on tagatud sellega, et kogu andmetöötlus ja Boole'i avaldiste lihtsustamine toimub otse kasutaja veebibrauseris. Sisestatud avaldisi ja andmeid ei edastata välisserveritesse ega salvestata kolmandate osapoolte poolt.

Korduma kippuvad küsimused

Miks on toetatud maksimaalselt 6 muutujat?

Kuus muutujat annavad juba 64-realise tõetabeli, mis on piiriks, mida inimene suudab veel käsitsi lugeda ja kontrollida. Sellest edasi minimeerimine teoorias küll toimib, kuid tuletuskäik ja tabel, millele see leht on üles ehitatud, ei ole enam tõestusmaterjalina kasulikud. Suurema muutujate arvuga funktsioonide jaoks sobib paremini failiväljundiga loogika projekteerimise tarkvara.

Kuidas leitakse minimaalne kuju?

Tööriist koostab täieliku tõetabeli, koondab külgnevad 1-read lihtimplikantideks (Quine–McCluskey meetod), jätab alles olulised implikandid ja katab ülejäänud read täpse minimaalse kattega. Tulemuseks on garanteeritult minimaalne disjunktiivne normaalkuju (SOP) — see ei ole heuristika — ning sama protseduur 0-ridadel annab minimaalse konjunktiivse normaalkuju (POS).

Milliseid avaldise kirjutamise viise toetatakse?

Kõiki levinud tähistusi võib vabalt segada: inseneristiil (AB + A'C, kus AND on kaudne ja NOT on ülakomaga), programmeerimisstiil (A &&!B || C, A ^ B), loogikasümbolid (¬ ∧ ∨ ⊕ ⊼ ⊽) ja tavasõnad (A AND B OR NOT C, NAND, NOR). Mitmetähelised jadad nagu ABC tähendavad A AND B AND C ning sõnu AND, OR, NOT, XOR, NAND, NOR loetakse alati operaatoriteks.

Mis vahe on SOP- ja POS-tulemustel?

Mõlemad kirjeldavad sama funktsiooni. Disjunktiivne normaalkuju (SOP) liidab OR-tehtega kokku AND-terminid, näiteks AB' + BC, ja vastab otse AND–OR-skeemidele; konjunktiivne normaalkuju (POS) korrutab AND-tehtega kokku OR-tegurid, näiteks (A + B)(B' + C), ja vastab OR–AND-skeemidele. Sõltuvalt funktsioonist võib üks kuju vajada vähem loogikaelemente kui teine, mistõttu näitab tööriist alati mõlemat.