מתמטיקה דיסקרטית/מציאת CNF ו-DNF

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

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

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

מציאת CNF[עריכה]

f Q P
0 0 0
1 1 0
0 0 1
0 1 1
  • כאשר אנו מתבקשים למצוא CNF ל-f נעקוב אחר האפסים. נזכור כי כל ביטוי בקשר זה בעל קשר "וגם".
  • כל שורה מהווה
  • ה-f הראשון שלנו עם אפס הוא ה-f הראשון ולכן נרצה לייצר משני ביטוי שקר שקר - קיימים 3 אפשרויות לשם כך ולכן נמתין עם f זה.
  • ה-f השני שלנו עם אפס הוא ה-f השלישי ולכן נרצה לייצר מביטוי אמת ושקר שקר - אין לנו בעיה עם P ו-Q ולכן נמשיך הלאה.
  • ה-f השלישי שלנו עם אפס הוא ה-f הרביעי ולכן נרצה לייצר מביטוי אמת ואמת שקר - יש לנו בעיה ולכן בכדי שיווצר ביטוי כזה נצטרך לשלול את P כלומר (¬p). נבדוק ששינוי זה לא השפיע על ה-f במקום השלישי והראשון:
    • ה-f השני שלנו עם אפס הוא ה-f השלישי ולכן נרצה לייצר מביטוי שקר ושקר שקר - אין לנו בעיה עם P ו-Q ולכן נמשיך הלאה.
    • ה-f הראשון שלנו עם אפס הוא ה-f הראשון ולכן נרצה לייצר מביטוי אמת ושקר שקר - אין בעיה

על כן ה-f שנקבל הינה

Q P
0 0 0
1 1 0
0 0 1
0 1 1

DNF[עריכה]

כאשר אנו מתבקשים למצוא DNF נעקוב אחר האחדים.