Förenklare för boolesk algebra

Minimering av booleska uttryck med exakta metoder

Inom digitalteknik och datavetenskap är minimering av booleska uttryck avgörande för att reducera antalet logiska grindar i fysiska kretsar och för att optimera villkorssatser i programvara. Genom att mata in ett uttryck i detta verktyg beräknas omedelbart både den minimala disjunktiva normalformen (SOP) och den minimala konjunktiva normalformen (POS).

Verktyget använder Quine–McCluskey-metoden för att garantera en exakt minimal täckning, till skillnad från heuristiska metoder som inte alltid hittar den absolut enklaste formen. Utöver de minimerade uttrycken genereras en fullständig sanningstabell samt en steg-för-steg-härledning som visar hur primimplikatorer har identifierats och valts ut.

Inmatningsformat och notationer

Verktyget stöder upp till 6 unika variabler och en maximal längd på 2 000 tecken. Variabler skrivs som enstaka bokstäver. Eftersom olika discipliner inom ingenjörskonst, programmering och formell logik använder skilda symboler, tillåter verktyget att flera olika notationssystem blandas fritt:

• AND (Konjunktion): Kan skrivas implicit genom att placera variabler intill varandra (exempelvis AB), eller med symbolerna A·B, A*B, A AND B, A && B. Följder av flera bokstäver som ABC tolkas som A AND B AND C.
• OR (Disjunktion): Skrivs som A + B, A OR B, A || B eller med logiska symboler.
• NOT (Negation): Kan anges som A', !A, NOT A, ¬A eller med ett primtecken.
• XOR (Exklusiv OR): Skrivs som A ^ B, A XOR B eller A ⊕ B.
• NAND: Skrivs som A NAND B eller ⊼.
• NOR: Skrivs som A NOR B eller ⊽.
• Konstanter: De binära värdena 0 och 1 är tillåtna.

För att underlätta användningen finns det färdiga exempel som kan laddas direkt via klickbara genvägar:

• Sammanslagning av termer (konsensus-exempel)
• Negerad produkt (De Morgans lagar)
• Tre-vägs XOR (XOR-exempel)

Gränssnittet erbjuder även knappar under Infoga en operator för att lägga till specifika symboler, samt knappen Rensa för att tömma inmatningsfältet.

Analys och diagnostik i realtid

När ett giltigt uttryck har matats in visas en sammanställning under rubriken I korthet. Denna panel innehåller följande diagnostiska data för att ge en snabb överblick över uttryckets struktur och komplexitet:

Om inmatningen är tom visas statusmeddelandet Skriv ett booleskt uttryck för att förenkla det.. När beräkningen är klar visas meddelandet Förenklat och kontrollerat på alla ‹rows› rader..

Skillnaden mellan SOP och POS i kretsdesign

Verktyget presenterar alltid två minimala former: Minimal disjunktiva normalform (SOP) och Minimal konjunktiv normalform (POS).

SOP (Sum of Products) representerar en disjunktion av konjunktioner (t.ex. AB + CD). I fysisk hårdvara mappar detta direkt till en AND–OR-grindstruktur. POS (Product of Sums) representerar en konjunktion av disjunktioner (t.ex. (A + B)(C + D)), vilket mappar till en OR–AND-grindstruktur.

Genom att jämföra dessa två former kan en kretskonstruktör avgöra vilken konfiguration som kräver minst antal fysiska grindar och ingångar, vilket sänker tillverkningskostnaden och strömförbrukningen.

Steg-för-steg-härledning med Quine–McCluskey

Under sektionen Hur det förenklades redovisas hela minimeringsprocessen matematiskt:

1. Variabelanalys: Verktyget fastställer antalet variabler och rader i sanningstabellen. För n variabler genereras 2ⁿ rader. Exempelvis: "Uttrycket använder ‹count› variabler (‹variables›), så sanningstabellen har ‹rows› rader.".
2. Mintermer och maxtermer: De rader där uttrycket är sant (1) respektive falskt (0) identifieras: "Det är lika med 1 på raderna Σm(‹minterms›) och 0 på raderna ΠM(‹maxterms›).".
3. Sammanslagning till primimplikatorer: Intilliggande 1-rader slås samman systematiskt för att eliminera redundanta variabler: "Sammanslagning av intilliggande 1-rader så långt som möjligt lämnar ‹count› primimplikatorer: ‹list›.".
4. Essentiella primimplikatorer: Verktyget isolerar de implikatorer som ensamma täcker minst en minterm: "Essentiella primimplikatorer — det enda återstående täckandet för minst en rad: ‹list›." Om inga sådana finns visas: "Ingen primimplikator är essentiell: varje 1-rad kan täckas på mer än ett sätt.".
5. Täckning av återstående rader: Om det finns oskyddade rader efter att de essentiella har valts, stängs de med minsta möjliga antal extra termer: "De rader som fortfarande inte är täckta stängs med minsta möjliga antal extra termer: ‹list›." Om de essentiella redan täcker allt visas: "De essentiella primimplikatorerna täcker redan varje 1-rad, så summan är komplett.".
6. POS-härledning: Samma algoritm körs på sanningstabellens 0-rader för att ta fram den minimala konjunktiva normalformen: "Samma sammanslagning på 0-raderna ger den minimala konjunktiva normalformen ‹pos›.".
7. Verifiering: Slutligen verifieras att de minimerade formerna ger exakt samma utmatning som det ursprungliga uttrycket på samtliga rader: "Båda minimala formerna matchar det ursprungliga uttrycket på alla ‹rows› rader i sanningstabellen.".

Resultatet kan enkelt kopieras till urklipp med knappen Kopiera resultat.

Hantering av fel och specialfall

Verktyget har inbyggd felhantering för att säkerställa att inmatade uttryck är syntaktiskt korrekta. Följande felmeddelanden kan visas vid felaktig inmatning:

• Tom inmatning: Ange ett booleskt uttryck.
• För långt uttryck: Håll uttrycket under 2,000 tecken.
• Ogiltiga tecken: "‹char›" (position ‹position›) är inte en boolesk operator, variabel eller konstant.
• Syntaxfel: En operator saknar sin operand nära position ‹position› — kontrollera om det finns ett hängande + · eller ⊕.
• Obalanserade parenteser: Parenteserna är obalanserade — lägg till eller ta bort en parentes.
• För många variabler: Detta uttryck använder ‹count› olika variabler; förenklaren stöder upp till 6.

Konstanta uttryck och redan minimala former

Om ett uttryck utvärderas till en tautologi (alltid sant) eller en motsägelse (alltid falskt), visas ett av följande meddelanden:

• Tautologi: Detta uttryck är alltid 1: varje kombination av värden gör det sant.
• Motsägelse: Detta uttryck är alltid 0: ingen kombination av värden gör det sant.
• Konstantstatus: Detta uttryck är konstant: det är alltid lika med ‹value›.

Om det inmatade uttrycket inte går att förenkla ytterligare visas meddelandet: Ditt uttryck är redan i minimal disjunktiv normalform..

Integritet och lokal databehandling

När du använder denna förenklare sker all beräkning och minimering lokalt direkt i din webbläsare. Inga uttryck, variabler eller sanningstabeller laddas upp till någon extern server. Detta innebär att bearbetningen sker på din egen enhet.

Vanliga frågor

Vilka sätt att skriva ett uttryck förstås?
Alla vanliga konventioner kan blandas fritt: ingenjörsstil (AB + A'C, med implicit AND och primtecken för NOT), programmeringsstil (A &&!B || C, A ^ B), logiska symboler (¬ ∧ ∨ ⊕ ⊼ ⊽) och vanliga ord (A AND B OR NOT C, NAND, NOR). Följder av flera bokstäver som ABC tolkas som A AND B AND C, och orden AND, OR, NOT, XOR, NAND, NOR läses alltid som operatorer.

Hur hittas den minimala formen?
Verktyget bygger upp hela sanningstabellen, slår samman intilliggande 1-rader till primimplikatorer (Quine–McCluskey-metoden), behåller de essentiella och täcker eventuella återstående rader med ett exakt minimalt täckande. Resultatet är garanterat minimalt för den disjunktiva normalformen (SOP) — det är inte en heuristik — och samma procedur på 0-raderna ger den konjunktiva normalformen (POS).

Vad är skillnaden mellan SOP- och POS-resultaten?
Båda beskriver samma funktion. Den disjunktiva normalformen (SOP) gör en OR-operation av AND-termer, såsom $AB' + BC$, och mappar direkt till AND–OR-kretsar; den konjunktiva normalformen (POS) gör en AND-operation av OR-faktorer, såsom $(A + B)(B' + C)$, och mappar till OR–AND-kretsar. Beroende på funktionen kan den ena formen kräva färre grindar än den andra, så verktyget visar alltid båda.

Varför stöds högst 6 variabler?
Sex variabler ger redan en sanningstabell med 64 rader, vilket är ungefär gränsen för vad som fortfarande är läsbart och kontrollerbart för hand. Utöver det fungerar minimeringen i teorin, men härledningen och tabellen som denna sida är uppbyggd kring upphör att vara användbara som bevis. Programvara för logikdesign med filutmatning är ett bättre alternativ för mer omfattande funktioner.