Lágmörkun Boole-stæðna með Quine–McCluskey aðferðinni
Boole-algebra er undirstaða stafrænnar rökrásahönnunar og tölvunarfræði. Þegar flóknar rökstæður eru hannaðar er lykilatriði að lágmarka þær til að fækka rökliðum og einfalda útfærslu í vélbúnaði eða hugbúnaði. Boole-algebru einfaldari er sérhæft tól sem reiknar út lágmarksform hvers kyns Boole-stæðna og skilar tveimur jafngildum en ólíkum lágmarksformum: lágmarks-liðasummu (SOP) og lágmarks-liðamargfeldi (POS).
Tólið styður allt að 6 mismunandi breytur og 2,000 tákn. Útreikningurinn fer fram með Quine–McCluskey aðferðinni, sem ólíkt bráðabirgðaaðferðum tryggir nákvæma lágmarksþekju. Öll vinnslan á sér stað beint í vafra notandans. Stæður eru einfaldaðar í þessum vafra og fara aldrei af tækinu þínu, sem tryggir að engin gögn eru send á ytri netþjóna.
Ritháttur og leyfileg inntak
Einfaldarinn skilur margvísleg ritháttarform sem notuð eru í verkfræði, forritun og stærðfræðilegri rökfræði. Breytur eru skrifaðar sem einstaka bókstafir og hægt er að blanda saman ólíkum táknum fyrir sömu virkjana:
- AND (og-virkir): Óbeinn ritháttur þar sem breytur standa saman (t.d.
AB), eða með sértækum táknum eins ogA·B,A*B,A AND B, eðaA && B. Margra bókstafa runur eins ogABCeru túlkaðar semA AND B AND C. - OR (eða-virkir): Skrifað sem
A + B,A OR B, eðaA || B. - NOT (neitun): Skrifað sem prímtákn á eftir breytu
A', eða fyrir framan hana sem!A,NOT A, eða¬A. - XOR (einkvæmt eða): Skrifað sem
A ^ B,A XOR B, eðaA ⊕ B. - NAND: Skrifað sem
A NAND Beða⊼. - NOR: Skrifað sem
A NOR Beða⊽. - Fastar: Gildið
0(ósatt) og1(satt) eru leyfð í stæðum.
Í viðmótinu er hægt að nota hnappinn Hreinsa til að tæma inntaksreitinn. Undir Prófaðu stæðu er hægt að smella á tilbúin dæmi til að sjá hvernig tólið vinnur:
- Sameining liða (dæmi um samhljóðun/consensus)
- Neitað margfeldi (dæmi um lögmál De Morgan)
- Þríhliða XOR (dæmi um XOR-virkja)
Greining og niðurstöður í fljótu bragði
Þegar stæða hefur verið slegin inn birtir tólið greiningarspjald undir heitinu Í fljótu bragði. Þetta spjald sýnir helstu kennistærðir stæðunnar áður en farið er í skref-fyrir-skref útskýringar:
| Heiti í viðmóti | Lýsing á innihaldi |
|---|---|
| Breytur | Listi yfir þær einstöku breytur sem fundust í stæðunni. |
| Raðir jafnar 1 | Fjöldi eða listi yfir lágmarksliði (minterms) stæðunnar. |
| Frumvaldar | Heildarfjöldi frumvalda (prime implicants) sem finnast við sameiningu. |
| Nauðsynlegir frumvaldar | Fjöldi þeirra frumvalda sem eru ómissandi til að þekja lágmarksliðina. |
| Bókstafir, fyrir → eftir | Fjöldi bókstafa (literals) í stæðunni fyrir og eftir lágmörkun. |
| Aðferð | Sýnir útreikningsaðferðina: Quine–McCluskey, nákvæm lágmarksþekja. |
Skref-fyrir-skref einföldun og sannleikstafla
Tólið sýnir nákvæmlega hvernig lágmarksformin voru fengin undir liðnum Hvernig hún var einfölduð. Ferlið fylgir ákveðnum skrefum eftir því hve margar breytur eru notaðar:
- Greining breytna: Tólið tilgreinir fjölda breytna og raða í sannleikstöflunni. Ef stæðan notar margar breytur birtist textinn: *„Stæðan notar
{count}breytur ({variables}), svo sannleikstaflan hefur{rows}raðir.“*Ef aðeins ein breyta er til staðar birtist: *„Stæðan notar eina breytu,{variables}, svo sannleikstaflan hefur{rows}raðir.“*Ef engar breytur eru notaðar birtist: „Stæðan notar engar breytur, svo hún reiknast sem einn fasti.“ - Skilgreining gilda: Sýnt er á hvaða röðum stæðan gefur gildið 1 og á hvaða röðum hún gefur 0: „Hún er jöfn 1 á röðunum Σm(
{minterms}) og 0 á röðunum ΠM({maxterms}).“ - Sameining og frumvaldar: Samliggjandi 1-raðir eru sameinaðar: „Sameining samliggjandi 1-raða eins langt og hægt er skilur eftir
{count}frumvalda:{list}.“ - Nauðsynlegir frumvaldar fundnir: Tólið greinir hvaða frumvaldar verða að vera í lokalausninni: *„Nauðsynlegir frumvaldar — eina eftirstandandi þekjan fyrir að minnsta kosti eina röð:
{list}.“*Ef enginn þeirra er nauðsynlegur birtist: „Enginn frumvaldur er nauðsynlegur: hægt er að þekja hverja 1-röð á fleiri en einn veg.“ - Þekja eftirstandandi raða: Ef einhverjar raðir eru óþaktar er þeim lokað: *„Röðunum sem enn eru óþaktar er lokað með sem fæstum auka liðum:
{list}.“*Ef nauðsynlegu frumvaldarnir duga birtist: „Nauðsynlegu frumvaldarnir þekja þegar hverja 1-röð, svo summan er fullgerð.“ - Liðamargfeldi (POS): Sama lágmörkun er keyrð á 0-raðirnar: „Sama sameining keyrð á 0-raðirnar gefur lágmarks-liðamargfeldið
{pos}.“ - Sannprófun: Að lokum er staðfest að niðurstöðurnar séu réttar: „Bæði lágmarksformin passa við upprunalegu stæðuna á öllum
{rows}röðum sannleikstöflunnar.“
Undir þessum skrefum birtist fullbúin Sannleikstafla. Hún sýnir dálka fyrir allar breytur, upprunalegu stæðuna undir dálkinum Stæða og lágmarkaða formið undir Lágmarks SOP til að sýna fram á að gildin passi saman í hverri einustu röð. Hægt er að nota hnappinn Afrita niðurstöðu til að vista lágmarkaða formið í klemmuspjald tækisins.
Regluvörð og sérstök tilvik
Tólið fylgir ströngum reglum um inntak og meðhöndlun villna til að tryggja rétta útreikninga:
- Takmörk á breytum: Ef slegin er inn stæða með fleiri en 6 breytum birtast villuboðin: „Þessi stæða notar
{count}mismunandi breytur; einfaldarinn styður mest 6.“ - Lengd stæðu: Ef stæðan fer yfir 2,000 tákn birtast villuboðin: „Hafðu stæðuna undir 2,000 táknum.“
- Ógild tákn: Ef slegið er inn tákn sem tólið skilur ekki birtist: „„
{char}“ (í stöðu{position}) er ekki Boole-virki, breyta eða fasti.“ - Málfræðivillur: Ef virkja vantar gildi til að vinna með birtist: „Virkja vantar virkjað stak nálægt stöðu
{position}— athugaðu hvort það sé laust + · eða ⊕.“ - Svigavillur: Ef svigar lokast ekki rétt birtist: „Svigarnir stemma ekki — bættu við eða fjarlægðu sviga.“
- Tóm innsláttur: Ef reynt er að reikna tóman reit birtist: „Sláðu inn Boole-stæðu.“
Fastar og þegar lágmarkaðar stæður
Ef stæðan sem slegin er inn jafngildir fasta gildi (alltaf 0 eða alltaf 1), birtir tólið stöðuboðin: „Þessi stæða er fasti: hún er alltaf jöfn {value}.“
- Fyrir sagnir sem eru alltaf sannar (tautology) birtist: „Þessi stæða er alltaf 1: sérhver gildasamsetning gerir hana sanna.“
- Fyrir mótsagnir sem eru alltaf ósannar (contradiction) birtist: „Þessi stæða er alltaf 0: engin gildasamsetning gerir hana sanna.“
Ef stæðan sem slegin var inn er þegar í sínu einfaldasta formi og verður ekki lágmörkuð frekar, birtir tólið skilaboðin: „Stæðan þín er þegar í lágmarks-liðasummuformi.“
Algengar spurningar
Hvernig er lágmarksformið fundið?
Tólið byggir upp fulla sannleikstöflu, sameinar samliggjandi 1-raðir í frumvalda (Quine–McCluskey aðferðin), heldur nauðsynlegu frumvöldunum og lokar öllum eftirstandandi röðum með nákvæmri lágmarksþekju. Niðurstaðan er tryggilega í lágmarksformi fyrir liðasummu (SOP) — hún er ekki ágiskun — og sama ferli á 0-raðirnar gefur liðamargfeldið (POS).
Hvaða rithættir fyrir stæður eru skildir?
Öll algeng ritháttarform, blönduð frjálslega: verkfræðistíll (AB + A'C, með óbeinu AND og prímtákni fyrir NOT), forritunarstíll (A &&!B || C, A ^ B), rökfræðitákn (¬ ∧ ∨ ⊕ ⊼ ⊽) og venjuleg orð (A AND B OR NOT C, NAND, NOR). Margra bókstafa runur eins og ABC þýða A AND B AND C, og orðin AND, OR, NOT, XOR, NAND, NOR eru alltaf lesin sem virkjar.
Hver er munurinn á SOP og POS niðurstöðunum?
Bæði lýsa sama fallinu. Liðasumma (SOP) tengir saman AND-liði með OR, eins og AB' + BC, og varpast beint á AND–OR rásir; liðamargfeldi (POS) tengir saman OR-liði með AND, eins og (A + B)(B' + C), og varpast á OR–AND rásir. Eftir því hvert fallið er getur annað formið þurft færri hlið en hitt, svo tólið sýnit alltaf bæði.
Af hverju eru að hámarki 6 breytur studdar?
Sex breytur gefa þegar 64-raða sannleikstöflu, sem er nálægt þeim mörkum sem hægt er að lesa og athuga handvirkt. Handan þess virkar lágmörkunin áfram í kenningu, verki skref-fyrir-skref útreikningurinn og taflan sem þessi síða byggir á hætta að vera gagnleg sem sönnunargögn. Hugbúnaður fyrir rökrásahönnun með skráarúttaki hentar betur fyrir stærri föll.