CNF

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

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

דוגמה:

נוסחת CNF במשתנים בעלת צורה כגון

העברת נוסחה לצורת CNF

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

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

ספיקות נוסחה בצורת CNF

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

בהינתן נוסחה בצורת CNF המורכבת מהפסוקיות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ C_1, ..., C_m} , ניתן לשאול האם קיימת השמת ערכי אמת המספקת אותה. מתברר שבעיה זו (המכונה בעיית הספיקות בתחשיב הפסוקים) היא NP-שלמה, ולכן נראה שלא ניתן לענות עליה באופן אוטומטי בזמן סביר (פולינומי ביחס לגודל הקלט במקום אלגוריתם מעריכי שיש כיום לפתרון בעיות כאלה).

ראו גם

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

קישורים חיצוניים

סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0