DNF

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

ניסוח מילולי[עריכת קוד מקור | עריכה]

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

העברת נוסחה לצורת DNF[עריכת קוד מקור | עריכה]

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

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

דוגמאות[עריכת קוד מקור | עריכה]

הנוסחאות הבאות במשתנים הן בצורת DNF:

ספיקות נוסחה בצורת DNF[עריכת קוד מקור | עריכה]

בהינתן נוסחה בצורת DNF המורכבת מהפסוקיות , ניתן לשאול האם קיימת השמת ערכי אמת המספקת אותה. מתברר שבעיה זו, בניגוד לבעיית הספיקות בתחשיב הפסוקים, היא ב-P, כלומר קיים אלגוריתם פולינומי דטרמיניסטי העונה על שאלה זו.

אלגוריתם לבדיקת הספיקות[עריכת קוד מקור | עריכה]

תהי נוסחה בצורת DNF ויהי A אלגוריתם המכריע אם ספיקה. האלגוריתם יבצע:

  1. בדוק אם היא אכן בצורת DNF (בדיקת תקינות קלט).
  2. לכל פסוקית בדוק:
    1. אם הפסוקית אינה מכילה סתירה מהצורה של החזר כי קיימת השמה מספקת.
  3. החזר כי לא קיימת השמה מספקת.

בהינתן משתנים ו- פסוקיות, זמן ריצת האלגוריתם הוא .

ראו גם[עריכת קוד מקור | עריכה]

  • CNF (צורה נורמלית קוניוקטיבית)