Számítástudomány epizód tartalma:
Mi az a teljes diszjunktív normálforma? És hogyan kell felírni? Itt lépésről lépésre elmeséljük hogyan lehet egy kifejezés teljes diszjunktív normálformáját előállítani és sok-sok példán keresztül minden érthetővé válik.
Egy ügyes kis trükk segítségével minden kifejezés feldarabolható teljesen különálló részekre.
Itt van például az ekvivalencia, ami azt jelenti, hogy A és B is egyszerre igaz…
vagy egyszerre hamis.
Az implikációnál pedig…
Vagy A és B is egyszerre igaz…
vagy A hamis és B igaz…
vagy A hamis és B is hamis.
A „vagy”-gyal elválasztott részek csak tagadást meg „és”-t tartalmaznak, így mindegyik ilyen rész pontosan egyféleképpen lehet igaz.
Az eredeti kifejezésnek ezt a felírását úgy hívjuk, hogy teljes diszjunktív normálforma.
Nézzük meg, hogy mi lesz például a teljes diszjunktív normálformája ennek:
Azzal kezdjük, hogy elkészítjük a szokásos igazságtáblázatot.
Aztán kiválogatjuk azokat az eseteket, amikor az egész kifejezés igaz.
Ezeket felírjuk szépen egymás után…
És hopp, már kész is a teljes diszjunkt normálforma.
Minden nem azonosan hamis kifejezésnek van teljes diszjunktív normálformája.
És éppen így kell elkészíteni, ahogy az előbb csináltuk.
Nézzük, mi lesz a teljes diszjunktív normálformája ennek itt:
Na, itt túl sok dolgunk nem lesz…
Lássunk még egyet.
Pompás.
Teljes
diszjunktív
normálformák