Boole-algebra egyszerűsítő

A Boole-algebra egyszerűsítésének elmélete és gyakorlata

A digitális rendszerek tervezése és a szoftveres feltételrendszerek optimalizálása során kulcsfontosságú a logikai kifejezések legegyszerűbb formára hozatala. A Boole-algebra egyszerűsítő egy olyan eszköz, amely bármely megadott Boole-kifejezést a minimális matematikai alakjára redukál. A felhasználó által megadott kifejezésből a rendszer azonnal kiszámítja és megjeleníti a minimális diszjunktív normálformát (SOP) és a minimális konjunktív normálformát (POS). Az egyszerűsített alakok mellett az eszköz lépésről lépésre bemutatja a Quine–McCluskey-módszer segítségével végzett levezetést, felsorolja az összes prímimplikánst, és egy soronkénti igazságtáblával igazolja az eredmények helyességét az eredeti kifejezéssel szemben.

A számítások teljes egészében a felhasználó böngészőjében történnek, így a megadott kifejezések soha nem hagyják el az eszközt.

---

Támogatott jelölésrendszerek és bemeneti formátumok

A logikai tervezésben, a programozásban és a formális logikában különböző jelölésmódok alakultak ki a Boole-algebrai műveletek leírására. Az eszköz rugalmassága lehetővé teszi, hogy a különböző szintaxisokat szabadon keverve használjuk a bemenetben. A változókat egyetlen betűvel kell jelölni.

A támogatott műveletek és azok bemeneti formátumai a következők:

• AND (és kapcsolat): Megadható implicit módon a változók egymás mellé írásával (például AB), valamint a A·B, A*B, A AND B, A && B formátumokkal, illetve logikai szimbólumokkal. A többbetűs sorozatok, mint az ABC, az A AND B AND C kapcsolatot jelentik.
• OR (vagy kapcsolat): Megadható az A + B, A OR B, A || B formákkal, vagy a megfelelő logikai szimbólummal.
• NOT (tagadás): Jelölhető apostroffal a változó után (A'), felkiáltójellel előtte (!A), a NOT A kifejezéssel, a ¬A szimbólummal, vagy a prímszimbólummal.
• XOR (kizáró vagy): Használható az A ^ B, A XOR B vagy az A ⊕ B jelölés.
• NAND (és-nem): Megadható az A NAND B vagy a ⊼ szimbólum segítségével.
• NOR (vagy-nem): Megadható az A NOR B vagy a ⊽ szimbólum segítségével.
• Konstansok: A 0 és 1 értékek közvetlenül használhatók a kifejezésekben.

A beviteli mező alatt gyorsbillentyűk találhatók az operátorok beillesztésére, valamint előre beállított példák is betölthetők:

• Tagok összevonása (konszenzus tétel bemutatása)
• Negált szorzat (De Morgan-féle azonosság)
• Háromváltozós XOR

A bemenet törlésére a Törlés gomb szolgál. Az egyszerűsítő legfeljebb 6 különböző változót tartalmazó és legfeljebb 2,000 karakter hosszúságú kifejezéseket képes feldolgozni.

---

A Quine–McCluskey-módszer és a prímimplikánsok

A manuális egyszerűsítésre gyakran használt Karnaugh-táblák (K-táblák) 4 változó felett nehezen kezelhetővé válnak, és 6 változónál (ami 64 igazságtábla-sort jelent) elérik az emberi vizuális ellenőrzés gyakorlati határát. Ezzel szemben a Quine–McCluskey-módszer egy szisztematikus, algoritmikus eljárás, amely garantálja az egzakt minimális lefedés megtalálását.

A minimalizálás folyamata a következő lépésekből áll:

1. Igazságtábla felépítése: Az eszköz meghatározza a változók számát. Ha a kifejezés n változót tartalmaz, az igazságtábla 2ⁿ sorból áll.
2. Mintermek és maxtermek azonosítása: A rendszer kigyűjti azokat a sorokat, ahol a kifejezés értéke 1 (mintermek: Σm), illetve ahol az értéke 0 (maxtermek: ΠM).
3. Szomszédos sorok összevonása: A szomszédos 1-es sorok szisztematikus összevonásával az algoritmus meghatározza a prímimplikánsokat.
4. Alapvető prímimplikánsok kiválasztása: Azok a prímimplikánsok, amelyek az egyetlen lefedést biztosítják legalább egy minterm (1-es sor) számára, alapvető (esszenciális) prímimplikánsokká válnak.
5. Lefedetlen sorok lezárása: Ha az alapvető prímimplikánsok nem fedik le az összes 1-es sort, a fennmaradó sorokat a lehető legkevesebb további taggal zárja le az algoritmus.
6. POS meghatározása: Ugyanezt az összevonási eljárást a 0-s sorokon elvégezve kapjuk meg a minimális konjunktív normálformát.

---

SOP és POS alakok a digitális áramkörökben

A logikai függvények fizikai megvalósítása során az áramkörtervező mérnököknek választaniuk kell a diszjunktív (SOP) és a konjunktív (POS) normálformák között.

A két forma közötti választás határozza meg, hogy a fizikai áramkörben melyik konfiguráció igényel kevesebb logikai kaput és ezáltal kisebb késleltetést. Az eszköz mindkét formát kiszámítja, így a tervezők közvetlenül összehasonlíthatják a literálok számát az egyszerűsítés előtt és után.

---

Hibakezelés és speciális esetek

A kifejezések kiértékelése során az eszköz ellenőrzi a szintaktikai szabályokat és a korlátokat. Hiba esetén az alábbi pontos hibaüzenetek jelennek meg:

• Üres mező: „Adjon meg egy Boole-kifejezést.”
• Túl hosszú bemenet: „Tartsa a kifejezést 2,000 karakter alatt.”
• Nem megengedett karakter: „A(z) „‹char›” (‹position›. pozíció) nem Boole-operátor, változó vagy konstans.”
• Hiányzó operandus: „Egy operátornak hiányzik az operandusa a(z) ‹position›. pozíció közelében – ellenőrizze a függőben lévő +, · vagy ⊕ jeleket.”
• Hibás zárójelezés: „A zárójelek nincsenek párban – adjon hozzá vagy töröljön egy zárójelet.”
• Változók korlátja: „Ez a kifejezés ‹count› különböző változót használ; az egyszerűsítő legfeljebb 6 változót támogat.”

Konstans kifejezések és minimális alakok

Ha a megadott kifejezés nem tartalmaz változókat, vagy a változók értékétől függetlenül mindig ugyanazt az eredményt adja, az eszköz az alábbi állapotüzeneteket jeleníti meg:

• Tautológia (mindig igaz): „Ez a kifejezés mindig 1: az értékek minden kombinációja igazzá teszi.”
• Kontradikció (mindig hamis): „Ez a kifejezés mindig 0: az értékek semmilyen kombinációja nem teszi igazzá.”
• Már minimális alak: Ha a bemenet nem egyszerűsíthető tovább, a „A kifejezés már a minimális diszjunktív normálformában van.” üzenet jelenik meg.

Sikeres egyszerűsítés esetén a „Egyszerűsítve és ellenőrizve mind a(z) ‹rows› sorban.” üzenet látható, az eredmény pedig az Eredmény másolása gombbal vágólapra másolható.

---

Gyakran Ismételt Kérdések

Hogyan történik a minimális alak meghatározása?

Az eszköz felépíti a teljes igazságtáblát, összevonja a szomszédos 1-es sorokat prímimplikánsokká (Quine–McCluskey-módszer), megtartja az alapvetőeket, a fennmaradó sorokat pedig egy egzakt minimális lefedéssel zárja le. Az eredmény garantáltan minimális a diszjunktív normálforma (SOP) esetében – ez nem heurisztika –, és ugyanez az eljárás a 0-s sorokon elvégezve megadja a konjunktív normálformát (POS).

Mi a különbség az SOP és de POS eredmények között?

Mindkettő ugyanazt a függvényt írja le. A diszjunktív normálforma (SOP, szorzatok összege) AND-tagokat kapcsol össze OR-kapcsolattal, mint például az AB' + BC, és közvetlenül leképezhető AND–OR áramkörökre; a konjunktív normálforma (POS, összegek szorzata) OR-tagokat kapcsol össze AND-kapcsolattal, mint például az (A + B)(B' + C), és OR–AND áramkörökre képezhető le. A függvénytől függően az egyik alak kevesebb kaput igényelhet, mint a másik, ezért az eszköz mindig mindkettőt megmutatja.

Milyen kifejezésírási módokat ért meg az eszköz?

Minden elterjedt jelölésmód szabadon keverhető: mérnöki stílus (AB + A'C, implicit AND-del és a NOT-ot jelölő apostroffal), programozói stílus (A &&!B || C, A ^ B), logikai szimbólumok (¬ ∧ ∨ ⊕ ⊼ ⊽) és egyszerű szavak (A AND B OR NOT C, NAND, NOR). A többbetűs sorozatok, mint például az ABC, az A AND B AND C kifejezést jelentik, az AND, OR, NOT, XOR, NAND, NOR szavak pedig mindig operátorként értelmezendők.

Miért legfeljebb 6 változó támogatott?

Hat változó már egy 64 soros igazságtáblát eredményez, ami nagyjából a határa annak, ami kézzel még olvasható és ellenőrizhető. Ezen túlmenően a minimalizálás elméletben továbbra is működik, de az ezen az oldalon található levezetés és táblázat már nem igazán használható szemléltetésként. A több változót tartalmazó függvényekhez a fájlkimenettel rendelkező logikai tervezőszoftverek jobban megfelelnek.