Conjunctive Normal Form או הצורה הנורמלית הקוניוקטיבית היא דרך לכתוב נוסחה בלוגיקה הפסוקים כך שהיא מורכבת מפסוקיות המחוברות ב'ו' (קוניונקציה). כל פסוקית היא אוסף של ליטרלים, משתנה או השלילה שלו, שמחוברים ב'או' (דיסיונקציה).
דוגמה טיפוסית היא: (x1 או לא x3) ו-(x2) ו-(x2 או x5 או לא x6 או xn).
כל נוסחה בלוגיקה הפסוקים אפשר לייצג כ-CNF. שיטה אחת היא למצוא את כל ההשמות (הקצאות ערכי אמת) שעושות את הנוסחה לשקר. עבור כל השמה כזו בונים פסוקית שמכילה את המשתנים שהיו שקר ואת השלילות של המשתנים שהיו אמת. הנוסחה בצורת CNF היא ה'ו' של כל הפסוקיות האלה.
בהינתן נוסחה ב-CNF עם הפסוקיות C1,...,Cm שואלים אם קיימת הקצאה שמספקת את כל הפסוקיות. בעיה זו נקראת בעיית הספיקות (SAT). זוהי בעיה NP-שלמה, כלומר לא ידוע על אלגוריתם מהיר שפותר אותה לכל קלט בסיבוכיות פולינומית.
CNF היא דרך לכתוב נוסחאות לוגיות. הנוסחה מורכבת מפסוקיות שמחוברות ב'ו'. קוניונקציה זה 'ו'.
כל פסוקית היא קבוצה של ליטרלים. ליטרל הוא משתנה או לא שלו. בתוך הפסוקית משתמשים ב'או'. דיסיונקציה זה 'או'.
לדוגמה: (x1 או לא x3) ו-(x2) ו-(x2 או x5 או לא x6 או xn).
כדי להעביר נוסחה ל-CNF אפשר למצוא את כל ההקצאות שגורמות לה להיות שקר. לכל הקצאה כזו בונים פסוקית מתאימה. ואז מחברים את כל הפסוקיות ב'ו'.
שאלה חשובה היא האם יש הקצאה שהופכת את כל הפסוקיות לאמת. השאלה הזו קשה לפתור תמיד בזמן קצר.
תגובות גולשים