Boolske uttrykk-forenkler

Minimering av boolsk algebra med Quine–McCluskey-metoden

Innen digitalteknikk og informatikk er forenkling av boolske uttrykk avgjørende for å redusere antall logiske porter i fysiske kretser, samt for å optimalisere betingelser i programvare. Manuell forenkling ved hjelp av boolske lover eller Karnaugh-diagrammer (K-maps) er utsatt for menneskelige feil og blir raskt uhåndterlig når antall variabler øker.

Boolske uttrykk-forenkler løser dette ved å bruke Quine–McCluskey-metoden, også kjent som metoden for tabulering. Dette er en algoritmisk tilnærming som garanterer at man finner den nøyaktig minimale formen for et gitt uttrykk. Verktøyet beregner og presenterer parallelt de to mest sentrale minimale formene innen digital design: minimal sum av produkter (SOP) og minimalt produkt av summer (POS).

---

Slik brukes verktøyet

Brukergrensesnittet er bygget for direkte interaksjon i nettleseren. Under feltet Uttrykk skriver eller limer du inn det boolske uttrykket som skal minimeres.

Tillatte inndataformater

Verktøyet aksepterer variabler skrevet som enkeltbokstaver. Du kan fritt blande ulike notasjonssystemer fra ingeniørfag, programmering og formell logikk:

• AND (konjunksjon): Kan skrives implisitt som AB, eller med operatorer som A·B, A*B, A AND B, A && B, samt logiske symboler. Flere bokstaver etter hverandre, som ABC, tolkes automatisk som A AND B AND C.
• OR (disjunksjon): Skrives som A + B, A OR B, A || B, eller med logiske symboler.
• NOT (negasjon): Kan angis som A', !A, NOT A, ¬A, eller med et primtegn.
• XOR (eksklusiv OR): Skrives som A ^ B, A XOR B, eller A ⊕ B.
• NAND: Skrives som A NAND B eller ⊼.
• NOR: Skrives som A NOR B eller ⊽.
• Konstanter: Sannhetsverdiene 0 og 1 er tillatte tegn.

Grensesnittets kontroller og snarveier

• Sett inn en operator: Knapper i grensesnittet lar deg sette inn spesifikke operatorer direkte i uttrykket.
• Prøv et uttrykk: Klikkbare snarveier lar deg laste inn ferdige eksempler for å se hvordan verktøyet fungerer:
  • Sammenslåing av ledd (konsensus-eksempel)
  • Negert produkt (De Morgans lov-eksempel)
  • Treveis XOR (XOR-eksempel)
• Tøm: En knapp som fjerner alt innhold i inndatafeltet.

Begrensninger og feilhåndtering

Verktøyet har noen faste rammer for å sikre stabil kjøring og lesbare resultater:

• Variabelgrense: Maksimalt 6 unike variabler støttes. Hvis du skriver inn et uttrykk med flere, vises feilmeldingen: «Dette uttrykket bruker ‹count› forskjellige variabler; forenkleren støtter opptil 6.».
• Tegngrense: Uttrykket må være under 2 000 tegn. Overskrides dette, vises feilmeldingen: «Hold uttrykket under 2 000 tegn.».
• Syntaksfeil: Hvis uttrykket inneholder ugyldige tegn, rapporterer verktøyet: «‹char›» (posisjon ‹position›) er ikke en boolsk operator, variabel eller konstant.. Ved manglende operander vises: «En operator mangler sin operand nær posisjon ‹position› – sjekk for en hengende + · eller ⊕.». Ubalanserte parenteser utløser meldingen: «Parentesene er ubalanserte – legg til eller fjern en parentes.».

---

Tolkning av resultatene

Når et gyldig uttrykk tastes inn, utfører verktøyet beregningen umiddelbart og oppdaterer resultatfeltene.

Normalisert tolkning og minimale former

• Lest som: Viser verktøyets normaliserte tolkning av det innskrevne uttrykket, slik at du kan verifisere at parenteser og operatorer har blitt tolket korrekt.
• Minimal sum av produkter (SOP): Den forenklede sum-av-produkter-formen.
• Minimalt produkt av summer (POS): Den forenklede produkt-av-summer-formen.
• Kopier resultat: En knapp som lar deg kopiere den minimerte formen til utklippstavlen.

Kort oppsummert (Diagnosepanel)

Dette panelet gir en rask statistisk oversikt over uttrykkets egenskaper:

• Variabler: Liste over de identifiserte variablene.
• Rader lik 1: Antall eller liste over mintermer der uttrykket evalueres til 1.
• Primimplikanter: Det totale antallet primimplikanter funnet under sammenslåingen.
• Essensielle primimplikanter: Antallet primimplikanter som er helt nødvendige for å dekke funksjonen.
• Literaler, før → etter: Antall literaler (variabler i komplementert eller ukomplementert form) i uttrykket før og etter forenklingen, som viser nøyaktig hvor mye uttrykket har blitt redusert.
• Metode: Viser minimeringsmetoden som er brukt: «Quine–McCluskey, nøyaktig minimalt dekk».

---

Trinnvis utledning og sannhetstabell

For pedagogisk nytte og verifikasjon viser verktøyet hele prosessen bak forenklingen under seksjonen Hvordan det ble forenklet.

Utledningsskrittene

1. Variabelstatus: Verktøyet etablerer rammene for sannhetstabellen. For uttrykk med flere variabler vises: «Uttrykket bruker ‹count› variabler (‹variables›), så sannhetstabellen har ‹rows› rader.». For én variabel vises: «Uttrykket bruker én variabel, ‹variables›, så sannhetstabellen har ‹rows› rader.». Hvis uttrykket ikke inneholder variabler, opplyses det: «Uttrykket bruker ingen variabler, så det evalueres til en enkelt konstant.».
2. Mintermer og makstermer: Plasseringen av 1-ere og 0-ere i sannhetstabellen identifiseres: «Det er lik 1 på radene Σm(‹minterms›) og 0 på radene ΠM(‹maxterms›).».
3. Sammenslåing av primimplikanter: Verktøyet viser resultatet av å slå sammen tilstøtende rader: «Sammenslåing av tilstøtende 1-rader så langt som mulig etterlater ‹count› primimplikanter: ‹list›.».
4. Essensielle primimplikanter: De implikantene som alene dekker unike 1-rader isoleres: «Essensielle primimplikanter — det eneste gjenværende dekket for minst én rad: ‹list›.». Hvis ingen er unike, vises: «Ingen primimplikant er essensiell: hver 1-rad kan dekkes på mer enn én måte.».
5. Dekking av gjenværende rader: Hvis de essensielle implikantene ikke dekker alle rader, vises det hvordan de resterende lukkes: «Radene som fortsatt ikke er dekket, lukkes med færrest mulig ekstra ledd: ‹list›.». Hvis de essensielle dekker alt, bekreftes dette med: «De essensielle primimplikantene dekker allerede hver 1-rad, så summen er komplett.».
6. POS-utledning: Prosessen gjentas på 0-radene for å finne produktet av summer: «Å kjøre den samme sammenslåingen på 0-radene gir det minimale produktet av summer ‹pos›.».
7. Verifikasjon: Til slutt bekreftes samsvaret: «Begge minimale former samsvarer med det opprinnelige uttrykket på alle ‹rows› rader i sannhetstabellen.».

Sannhetstabell

Under utledningen genereres en komplett Sannhetstabell. Tabellen inneholder kolonner for hver av variablene, en kolonne for det opprinnelige uttrykket (merket Uttrykk), og en kolonne for den minimerte formen (merket Minimert SOP). Dette lar deg visuelt bekrefte at de to uttrykkene gir nøyaktig samme resultat for samtlige kombinasjoner av inndata.

---

Spesialtilfeller og konstante uttrykk

Hvis et innskrevet uttrykk evalueres til en konstant verdi uavhengig av inndata, vil verktøyet identifisere dette og vise en statusmelding:

• Tautologier (alltid sann): Hvis uttrykket alltid gir 1, vises meldingen: «Dette uttrykket er alltid 1: alle kombinasjoner av verdier gjør det sant.». Statuslinjen vil vise: «Dette uttrykket er konstant: det er alltid lik 1.».
• Kontradiksjoner (alltid usann): Hvis uttrykket alltid evalueres til 0, vises meldingen: «Dette uttrykket er alltid 0: ingen kombinasjon av verdier gjør det sant.». Statuslinjen vil vise: «Dette uttrykket er konstant: det er alltid lik 0.».
• Allerede minimalt: Dersom uttrykket du skrev inn ikke kan forenkles ytterligere, informerer verktøyet om dette med teksten: «Uttrykket ditt er allerede en minimal sum av produkter.».

Når forenklingen er fullført uten feil, oppdateres statusen til: «Forenklet og kontrollert på alle ‹rows› rader.».

---

Personvern og databehandling

Når du bruker denne forenkleren, foregår all databehandling og beregning lokalt på din egen enhet. Uttrykkene du skriver inn, forenkles direkte i denne nettleseren og forlater aldri enheten din. Det sendes ingen data til eksterne servere.

---

Ofte stilte spørsmål (FAQ)

Hvilke måter å skrive et uttrykk på blir forstått?

Alle vanlige konvensjoner kan blandes fritt: ingeniørstil (AB + A'C, med underforstått AND og apostrof for NOT), programmeringsstil (A &&!B || C, A ^ B), logiske symboler (¬ ∧ ∨ ⊕ ⊼ ⊽) og vanlige ord (A AND B OR NOT C, NAND, NOR). Sekvenser med flere bokstaver som ABC betyr A AND B AND C, og ordene AND, OR, NOT, XOR, NAND, NOR tolkes alltid som operatorer.

Hvordan finnes den minimale formen?

Verktøyet bygger den fullstendige sannhetstabellen, slår sammen tilstøtende 1-rader til primimplikanter (Quine–McCluskey-metoden), beholder de essensielle og dekker eventuelle gjenværende rader med et nøyaktig minimalt dekk. Resultatet er garantert minimalt for sum-av-produkter-formen – det er ikke en heuristikk – og den samme prosedyren på 0-radene produserer produkt-av-summer-formen.

Hva er forskjellen på SOP- og POS-resultatene?

Begge beskriver den samme funksjonen. Summen av produkter (SOP) gjør en OR-operasjon på AND-ledd, slik som AB' + BC, og kan oversettes direkte til AND–OR-kretser. Produktet av summer (POS) gjør en AND-operasjon på OR-faktorer, slik som (A + B)(B' + C), og kan oversettes til OR–AND-kretser. Avhengig av funksjonen kan den ene formen kreve færre porter enn den andre, så verktøyet viser alltid begge.

Hvorfor støttes maksimalt 6 variabler?

Seks variabler gir allerede en sannhetstabell på 64 rader, noe som er omtrent grensen for hva som fortsatt er lesbart og kontrollerbart for hånd. Utover dette fungerer minimering fortsatt i teorien, men utledningen og tabellen som denne siden er bygget rundt, slutter å være nyttige som bevis. Programvare for logikkdesign med filutdata er bedre egnet for mer omfattende funksjoner.