DNF

ערך זה עוסק בבמשמעות הלוגית של DNF. אם התכוונתם למשחק המחשב של חברת 3D Realms, ראו Duke Nukem Forever.

ערך זה עוסק בבמשמעות הלוגית של DNF. אם התכוונתם למושג שיפוט בקוביה הונגרית, ראו Did Not Finish.

Disjunctive Normal Form או הצורה הנורמלית הדיסיונקטיבית - הוא ביטוי המורכב מאוסף פרדיקטים לוגיים המחוברים ביניהם על ידי ביטויי "או" כאשר כל פרידיקט הוא אוסף של ביטויים המחוברים ביניהם על ידי ביטויי "וגם". השימושית מתבטאת בכך שניתן להביא כל ביטוי לוגי לצורת DNF.

ניסוח מילולי

ביטוי מצורת DNF מורכב מאוסף "פסוקיות" המחוברות ביניהן על ידי פעולות "או", כאשר כל פסוקית היא אוסף של ליטרלים (משתנים ושלילות משתנים) המחוברים ביניהם על ידי פעולות "וגם".

העברת נוסחא לצורת DNF

כל נוסחא בתחשיב הפסוקים ניתנת להצגה כנוסחת DNF כך:

1. מציאת כל השמות ערכי האמת המספקות את הנוסחא - בדר"כ בעזרת טבלת אמת.
2. עבור כל השמה כזו, בניית פסוקית אשר מכילה את כל המשתנים שערכם "אמת", ואת שלילת כל המשתנים המקבלים ערך "שקר"(בהם פעולות "וגם")

דוגמאות

נוסחאות DNF במשתנים $\ x_1, \ldots, x_n$ הינם נוסחאות מהצורה:

$x_1 \and x_2$

$x_1\!$

$(x_1 \and x_2) \or x_3$

$(x_1 \and \neg x_2 \and \neg x_3) \or (\neg x_4 \and x_5 \and x_6)$

ראו גם

• CNF