Obsah:
- Definícia - Čo znamená disjunktívna normálna forma (DNF)?
- Techopedia vysvetľuje disjunkčný normálny formulár (DNF)
Definícia - Čo znamená disjunktívna normálna forma (DNF)?
Disjunktívna normálna forma (DNF) je normalizácia logického vzorca v booleovskej matematike. Inými slovami, o logickom vzorci sa hovorí, že je v disjunkčnej normálnej forme, ak je disjunkciou spojov s každou premennou a jeho negácia je prítomná raz v každej spojitosti. Všetky disjunkčné normálne formy nie sú jedinečné, pretože všetky disjunkčné normálne formy pre tú istú ponuku sú vzájomne rovnocenné.
Disjunkčná normálna forma sa široko používa v oblastiach, ako je automatizované dokazovanie teorémov.
Techopedia vysvetľuje disjunkčný normálny formulár (DNF)
Logický vzorec je v disjunkčnej normálnej forme vtedy a len vtedy, ak existuje striedanie jedného alebo viacerých spojení jedného alebo viacerých literálov. Vzorec sa považuje za úplne disjunktívny normálny tvar, ak sú všetky zúčastnené premenné zastúpené v každej časti iba raz. Podobne ako v spojivej normálnej forme sú výrokové operátory v disjunkčnej normálnej forme rovnaké: AND, OR a NOT.
Všetky logické vzorce možno previesť na ekvivalentný disjunkčný normálny tvar. V niektorých prípadoch je však možná exponenciálna explózia logickej funkcie v dôsledku konverzie na disjunkčnú normálnu formu. Ďalším dôležitým bodom je, že akákoľvek jedinečná booleovská funkcia môže byť zastúpená iba jednou a jedinečnou úplnou disjunkčnou normálnou formou. Pomocou techník, ako je metóda tabuľky pravdy, stromy pravdy alebo tabuľka logických ekvivalencií, je možné pre logické vzorce vygenerovať disjunktívny normálny tvar. K-DNF, variácia disjunkčnej normálnej formy, je široko používaná a obľúbená pri štúdiu výpočtovej zložitosti.
