„Diszjunktív normálforma” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Opa (vitalap | szerkesztései) a →Szemantikus módszerek. A KDNF: képlet |
|||
65. sor:
Egy diszjunktív normálforma értéktáblázatát elkészítve, a formula adott sorban (interpretációban) pontosan akkor lesz igaz, ha abban az interpretációban legalább egy elemi konjunkció igaz, tehát pontosan akkor hamis, ha abban az interpretációban minden elemi konjunkció hamis. Márpedig egy elemi konjunkció pontosan akkor hamis, ha legalább egy literálja hamis abban az interpretációban, akkor igaz tehát, ha minden literál igaz; azaz negálatlan atomjai igazak, a negáltak pedig hamisak. Adott interpretációt tekintve, ha tehát az atomokat összediszjunkciózzuk úgy, hogy a konjunkcióban negálatlanul szerepeljenek az „igaz” igazságértéket kapott atomok, és negáltan a „hamis” igazságértéket kapottak; akkor a konjunkció értéke igaz lesz. Ezáltal pedig a konjunkciók diszjunkciója is igaz lesz ebben az interpretációban.
Ennek megfelelően a a következőképp konstruálhatunk DNF-t tetszőleges művelethez: a művelet értéktáblázata minden olyan sorához (interpretációjához), melyben az f művelet az i (igaz) logikai értéket veszi fel, konstruálunk egy literálokból álló elemi konjunkciót, mégpedig úgy, hogy ha az X<sub>k</sub> változónak abban a sorban i értéket adtunk, akkor ez a változó a diszjunkcióba mint negálatlan atom (pozitív literál) kerül be, ha pedig h (hamis) értéket,
Formálisan „[[polinom]]mal” adhatjuk meg az f KDNF alakját:
| |||