Generator fra sannhetstabell til uttrykk
Klikk resultatkolonnen til formen du trenger, så leser verktøyet formelen ut av den: den kanoniske DNF-en (sum av produkter), den kanoniske KNF-en (produkt av summer) og den korteste ekvivalente formen. Alt kjører i nettleseren din, og tabellen du bygger følger med i lenken.
| p | q | Resultat |
|---|---|---|
| ⊥ | ⊥ | |
| ⊤ | ⊥ | |
| ⊥ | ⊤ | |
| ⊤ | ⊤ |
Klikk på resultatverdiene for å veksle mellom sann (⊤) og usann (⊥)
Uttrykket som ble laget
Slik gjør du en sannhetstabell om til et boolsk uttrykk
Enhver sannhetstabell er sannhetstabellen til en eller annen formel, og to av dem kan leses rett ut av den - uten algebra og uten gjetting:
- Skriv ut alle 2ⁿ radene for de n variablene dine, og merk av dem der resultatet er ⊤.
- Skriv et minterm for hver ⊤-rad: alle variablene bundet sammen med OG, negert der raden gjør dem usanne. Bind mintermene sammen med ELLER, så har du DNF-en.
- Skriv et maksterm for hver ⊥-rad: alle variablene bundet sammen med ELLER, negert der raden gjør dem sanne. Bind makstermene sammen med OG, så har du KNF-en.
- Begge formlene har nøyaktig tabellen du gikk ut fra, så begge er riktige svar. Forenkle etterpå hvis du vil ha den korteste.
Minterm
En konjunksjon av alle variablene, hver enten negert eller ikke, som er sann i nøyaktig én rad i tabellen. DNF-en er disjunksjonen av mintermene for radene der resultatet er ⊤ - derav ett ledd per ⊤-rad.
Maksterm
En disjunksjon av alle variablene, hver enten negert eller ikke, som er usann i nøyaktig én rad i tabellen. KNF-en er konjunksjonen av makstermene for radene der resultatet er ⊥ - derav ett ledd per ⊥-rad.
Gjennomregnet eksempel: eksklusivt eller
Tabellen over er den verktøyet åpner med: p og q, sann i nøyaktig de to radene der inngangene er forskjellige.
- To rader er ⊤, så DNF-en har to mintermer: (p ∧ ¬q) ∨ (¬p ∧ q)
- De to andre er ⊥, så KNF-en har to makstermer: (p ∨ q) ∧ (¬p ∨ ¬q)
Ingen av dem kan gjøres kortere - eksklusivt eller trenger virkelig begge leddene - og det er verdt å se én gang: den kanoniske formen er ikke alltid omveien. Det er ved en tabell som «høyst én av p, q, r» at den minimale formen virkelig drar ifra.
Forstå boolsk syntese
Disjunktiv normalform (DNF)
DNF skriver en formel som et ELLER av OG-er (sum av produkter). For hver rad der resultatet er sant lager vi et minterm som binder alle variablene sammen med OG og negerer dem som er usanne. Mintermene bindes så sammen med ELLER til hele uttrykket.
Konjunktiv normalform (KNF)
KNF skriver en formel som et OG av ELLER-er (produkt av summer). For hver rad der resultatet er usant lager vi et maksterm som binder alle variablene sammen med ELLER og negerer dem som er sanne. Makstermene bindes så sammen med OG til hele uttrykket.
DNF og KNF sammenlignet
| Forhold | Disjunktiv normalform (sum av produkter) | Konjunktiv normalform (produkt av summer) |
|---|---|---|
| Bygd av | Radene der resultatet er ⊤, ett minterm hver | Radene der resultatet er ⊥, ett maksterm hver |
| Form | En disjunksjon av konjunksjoner: et ELLER av OG-er | En konjunksjon av disjunksjoner: et OG av ELLER-er |
| Velg den når | Du vil regne opp tilfellene som gjør formelen sann, eller sette opp en OG-ELLER-krets | Du vil ha betingelsene som alle må gjelde samtidig, eller klausulformen en SAT-løser forventer |
Hvor stor blir tabellen?
En funksjon av n variabler har 2ⁿ rader, så tabellen dobles for hver variabel du legger til: 4 rader ved to variabler, 8 ved tre, 16 ved fire og 32 ved fem, der dette verktøyet stopper. DNF-en tar ett ledd per ⊤-rad og KNF-en ett per ⊥-rad, så til sammen gjør de rede for hver eneste rad nøyaktig én gang - og den ene av dem er alltid det korteste utgangspunktet.
Bruksområder for syntese fra sannhetstabeller
Å gå fra sannhetstabell til logisk uttrykk er en grunnteknikk i informatikk og digitalteknikk. Verktøyet hjelper med:
- Design av digitale kretser - finn de boolske likningene for logiske porter ut fra ønsket sammenheng mellom inn- og utgang
- Programvareutvikling - lag betinget logikk ut fra en spesifikasjonstabell
- Studier - lær og øv på boolsk algebra og utsagnslogikk
- Logisk optimering - sammenlign DNF og KNF for å finne enklere ekvivalente uttrykk
Ofte stilte spørsmål
Finn svar på vanlige spørsmål om bruken av Logikkalkulatoren
Hva gjør verktøyet fra sannhetstabell til uttrykk?
Det kjører kalkulatoren baklengs. Du bestemmer resultatkolonnen i en sannhetstabell ved å klikke på hver rad, og verktøyet lager en formel med nøyaktig den sannhetstabellen — på disjunktiv normalform (et ELLER av OG-er) eller konjunktiv normalform (et OG av ELLER-er).
Hva er forskjellen på DNF og KNF?
DNF er en sum av produkter: én konjunksjon for hver rad der resultatet er sant, bundet sammen med ELLER. KNF er et produkt av summer: én disjunksjon for hver rad der resultatet er usant, bundet sammen med OG. Begge beskriver den samme funksjonen, så velg den som blir kortest for din tabell — en overveiende usann kolonne gir en kort DNF, en overveiende sann en kort KNF.
Hvor mange variabler tåler synteseverktøyet?
Opptil fem, altså en tabell med 32 rader. Hver variabel du legger til dobler radene, og over fem slutter tabellen å være noe man kan fylle ut for hånd.
Hvorfor er det genererte uttrykket så langt?
En normalform bygges rad for rad, med ett ledd i full bredde for hver rad som skal dekkes, så lengden følger sannhetstabellen snarere enn tanken bak. Den er korrekt av konstruksjon, ikke kompakt. Vil du korte den ned, åpner du den i kalkulatoren, som lister opp ekvivalente former, blant dem en minimert DNF.
Kan jeg få en forenklet utgave av en formel?
Ja. Skriv den inn i kalkulatoren og se på de ekvivalente formene under sannhetstabellen. Der finner du former utledet ved omskriving med de algebraiske lovene, og DNF og KNF lest av sannhetstabellen sammen med en minimert DNF.