CNF

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

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

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

דוגמה:

נוסחת CNF במשתנים \ x_1, \ldots, x_n בעלת צורה כגון

(x_1\or \overline{x_3})\and(x_2)\and(x_2\or x_5 \or \overline{x_6} \or x_n)

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

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

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

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

Postscript-viewer-shaded.png ערך מורחב – בעיית הספיקות

בהינתן נוסחה בצורת CNF המורכבת מהפסוקיות \ C_1, ..., C_m, ניתן לשאול האם קיימת השמת ערכי אמת המספקת אותה. מתברר שבעיה זו (המכונה בעיית הספיקות בתחשיב הפסוקים) היא NP-שלמה, ולכן נראה שלא ניתן לענות עליה באופן אוטומטי בזמן סביר.

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

  • DNF (צורה נורמלית דיסיונקטיבית)