Generator fra sandhedstabel til udtryk
Klik resultatkolonnen på plads, så læser værktøjet formlen ud af den: den kanoniske DNF (sum af produkter), den kanoniske CNF (produkt af summer) og den korteste ækvivalente form. Alt kører i din browser, og den tabel, du bygger, følger med i linket.
| p | q | Resultat |
|---|---|---|
| ⊥ | ⊥ | |
| ⊤ | ⊥ | |
| ⊥ | ⊤ | |
| ⊤ | ⊤ |
Klik på resultatværdierne for at skifte mellem sand (⊤) og falsk (⊥)
Sådan omdanner du en sandhedstabel til et boolesk udtryk
Enhver sandhedstabel er sandhedstabellen for en eller anden formel, og to af dem kan læses direkte ud af den - uden algebra og uden gætteri:
- Skriv alle 2ⁿ rækker for dine n variable op, og markér dem, hvor resultatet er ⊤.
- Skriv et minterm for hver ⊤-række: alle variable forbundet med OG, negeret dér, hvor rækken gør dem falske. Forbind mintermerne med ELLER, og du har DNF'en.
- Skriv et maksterm for hver ⊥-række: alle variable forbundet med ELLER, negeret dér, hvor rækken gør dem sande. Forbind makstermerne med OG, og du har CNF'en.
- Begge formler har præcis den tabel, du gik ud fra, så begge er et rigtigt svar. Forenkl bagefter, hvis du vil have den korteste.
Minterm
En konjunktion af alle variable, hver enten negeret eller ej, som er sand i præcis én række af tabellen. DNF'en er disjunktionen af mintermerne for de rækker, hvor resultatet er ⊤ - derfor ét led per ⊤-række.
Maksterm
En disjunktion af alle variable, hver enten negeret eller ej, som er falsk i præcis én række af tabellen. CNF'en er konjunktionen af makstermerne for de rækker, hvor resultatet er ⊥ - derfor ét led per ⊥-række.
Gennemregnet eksempel: eksklusivt eller
Tabellen ovenfor er den, værktøjet åbner med: p og q, sand i præcis de to rækker, hvor indgangene er forskellige.
- To rækker er ⊤, så DNF'en har to mintermer: (p ∧ ¬q) ∨ (¬p ∧ q)
- De to andre er ⊥, så CNF'en har to makstermer: (p ∨ q) ∧ (¬p ∨ ¬q)
Ingen af dem kan gøres kortere - eksklusivt eller har virkelig brug for begge led - og det er værd at se én gang: den kanoniske form er ikke altid omvejen. Det er ved en tabel som »højst ét af p, q, r«, at den minimale form for alvor løber fra den.
Forstå boolesk syntese
Disjunktiv normalform (DNF)
DNF udtrykker en formel som et ELLER af OG'er (sum af produkter). For hver række, hvor resultatet er sandt, danner vi et minterm, der forbinder alle variable med OG og negerer dem, der er falske. Mintermerne forbindes derefter med ELLER til det færdige udtryk.
Konjunktiv normalform (CNF)
CNF udtrykker en formel som et OG af ELLER'er (produkt af summer). For hver række, hvor resultatet er falsk, danner vi et maksterm, der forbinder alle variable med ELLER og negerer dem, der er sande. Makstermerne forbindes derefter med OG til det færdige udtryk.
DNF og CNF sammenlignet
| Forhold | Disjunktiv normalform (sum af produkter) | Konjunktiv normalform (produkt af summer) |
|---|---|---|
| Bygget af | Rækkerne hvor resultatet er ⊤, ét minterm hver | Rækkerne hvor resultatet er ⊥, ét maksterm hver |
| Form | En disjunktion af konjunktioner: et ELLER af OG'er | En konjunktion af disjunktioner: et OG af ELLER'er |
| Vælg den, når | Du vil opregne de tilfælde, der gør formlen sand, eller lægge et OG-ELLER-kredsløb ud | Du vil have de betingelser, der alle skal gælde på én gang, eller den klausulform, en SAT-løser forventer |
Hvor stor bliver tabellen?
En funktion af n variable har 2ⁿ rækker, så tabellen fordobles for hver variabel, du tilføjer: 4 rækker ved to variable, 8 ved tre, 16 ved fire og 32 ved fem, hvor dette værktøj stopper. DNF'en tager ét led per ⊤-række og CNF'en ét per ⊥-række, så tilsammen gør de rede for hver eneste række præcis én gang - og den ene af dem er altid det korteste udgangspunkt.
Anvendelser af syntese fra sandhedstabeller
At omdanne sandhedstabeller til logiske udtryk er en grundlæggende teknik i datalogi og digital elektronik. Værktøjet hjælper med:
- Design af digitale kredsløb - find de booleske ligninger for logiske porte ud fra den ønskede sammenhæng mellem ind- og udgang
- Softwareudvikling - dan betinget logik ud fra en specifikationstabel
- Studier - lær og træn boolesk algebra og udsagnslogik
- Logisk optimering - sammenlign DNF og CNF for at finde enklere ækvivalente udtryk
Ofte stillede spørgsmål
Find svar på almindelige spørgsmål om brugen af Logikberegneren
Hvad gør værktøjet fra sandhedstabel til udtryk?
Det kører beregneren baglæns. Du fastlægger resultatkolonnen i en sandhedstabel ved at klikke på hver række, og værktøjet frembringer en formel med præcis den sandhedstabel — på disjunktiv normalform (et ELLER af OG'er) eller konjunktiv normalform (et OG af ELLER'er).
Hvad er forskellen på DNF og CNF?
DNF er en sum af produkter: én konjunktion for hver række, hvor resultatet er sandt, forbundet med ELLER. CNF er et produkt af summer: én disjunktion for hver række, hvor resultatet er falsk, forbundet med OG. Begge beskriver den samme funktion, så vælg den, der bliver kortest for din tabel — en overvejende falsk kolonne giver en kort DNF, en overvejende sand en kort CNF.
Hvor mange variabler kan synteseværktøjet klare?
Op til fem, altså en tabel på 32 rækker. Hver variabel, du tilføjer, fordobler rækkerne, og over fem holder tabellen op med at være noget, man kan udfylde i hånden.
Hvorfor er det genererede udtryk så langt?
En normalform bygges række for række med ét led i fuld bredde for hver række, der skal dækkes, så længden følger sandhedstabellen frem for tanken bag. Den er korrekt af konstruktion, ikke kompakt. Vil du forkorte den, så åbn den i beregneren, der viser ækvivalente former, heriblandt en minimeret DNF.
Kan jeg få en forenklet udgave af en formel?
Ja. Skriv den i beregneren og se på de ækvivalente former under sandhedstabellen. De omfatter former udledt ved omskrivning med de algebraiske love samt DNF og CNF aflæst af sandhedstabellen sammen med en minimeret DNF.