שיעור תאוריה
צורות נורמליות בלוגיקה פסוקית
איך מזהים שהנושא מתאים
- מבקשים לכתוב פסוק בצורה דיסיונקטיבית נורמלית או קוניונקטיבית נורמלית.
- מופיעים קשרים כמו ¬, ∧, ∨, →, ↔.
- השאלה מבקשת להשתמש בטבלת אמת או לפשט בלי טבלת אמת.
- צריך להבחין בין צורה קנונית מטבלת אמת לבין צורה שקולה ופשוטה יותר.
- מבקשים להוכיח שקשר יחיד, כמו NAND, או קבוצת קשרים כמו {¬,→}, יוצרים קבוצה שלמה ומינימלית.
אינטואיציה
אפשר לחשוב על פסוק לוגי כמערכת שמקבלת כמה מתגים ומחליטה כן או לא. טבלת האמת בודקת את המערכת בכל צירוף אפשרי, כמו רשימת בדיקות שמוודאת מה יקרה בכל מצב.
DNF מתאר את צד ה"כן": הוא מפרט את המצבים שמספיקים כדי לקבל תשובה חיובית. כל קוניונקציה היא תיאור מלא של מצב אחד, והדיסיונקציה ביניהן אומרת שמספיק שאחד המצבים האלה יתרחש.
CNF מתאר את אותה מערכת דרך צד ה"לא": כל פסוקית נבנית כך שתיכשל במצב שקר מסוים. הקוניונקציה דורשת לעבור את כל הפסוקיות, ולכן היא חוסמת יחד את כל מצבי הכשל.
למשל, המצב p=T, q=F מתואר ב-DNF על ידי p∧¬q. כדי לחסום את אותו מצב ב-CNF כותבים ¬p∨q, מפני ששני הליטרלים בו שקריים דווקא במצב הזה.
פישוט אלגברי הוא דרך אחרת לתאר אותה מערכת החלטה. במקום לעבור על כל המצבים, משנים את צורת הפסוק בעזרת חוקים ששומרים על אותה תשובה בכל הצבה.
קשר NAND הוא אבן בניין אוניברסלית: אם אפשר לבנות ממנו שלילה, קוניונקציה ודיסיונקציה, אפשר לבנות בעזרתו כל מערכת החלטה לוגית גם בלי להשתמש בקשרים אחרים.
הגדרות פורמליות
| מושג | משמעות |
|---|---|
| ליטרל | משתנה פסוקי או שלילתו, למשל p או ¬p. |
| טבלת אמת | טבלה המציגה את ערך האמת של פסוק בכל הצבה אפשרית של ערכי אמת למשתנים שלו. |
| פסוקית | דיסיונקציה של ליטרלים. ב-CNF מחברים כמה פסוקיות באמצעות קוניונקציה. |
| DNF | דיסיונקציה של קוניונקציות: איחוד של מקרים שבהם הפסוק אמת. |
| CNF | קוניונקציה של דיסיונקציות: אוסף תנאים שכל אחד מהם פוסל שורת שקר. |
| צורה קנונית | צורה שבה כל איבר נבנה ישירות משורה מלאה בטבלת אמת, ולכן כל איבר מכיל את כל המשתנים. |
| שקילות לוגית | שני פסוקים שקולים אם הם מקבלים אותו ערך אמת בכל הצבה. הסימון הוא ≡. |
| טאוטולוגיה | פסוק שערכו T בכל הצבה, ולכן צירופו בקוניונקציה אינו מוסיף הגבלה. |
| רזולוציה | כלל היסק שמסלק משתנה המופיע פעם בחיוב ופעם בשלילה בשתי פסוקיות, ומסיק מהן פסוקית חדשה. |
| NAND | קשר שערכו הוא שלילת הקוניונקציה: p↑q≡¬(p∧q). |
| שלמות פונקציונלית | קבוצת קשרים שמאפשרת לבטא כל פונקציית אמת וכל פסוק לוגי. |
| קבוצה מינימלית של קשרים | קבוצה שלמה פונקציונלית שהסרת כל קשר ממנה מבטלת את השלמות. |
החלפות שימושיות:
p → q ≡ ¬p ∨ qגרירה נכשלת רק במקרה שבו p אמת ו-q שקר. גם ¬p∨q שקר בדיוק במקרה הזה, ולכן שני הפסוקים שקולים.
p ↔ q ≡ (p → q) ∧ (q → p)שקילות דורשת התאמה בשני הכיוונים: אם p מתקיים אז q מתקיים, וגם להפך. לכן היא נכתבת כחיבור של שתי גרירות.
¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬qבחוקי דה-מורגן השלילה משנה גם כל רכיב וגם את הקשר ביניהם: כדי שקוניונקציה תיכשל מספיק שלפחות רכיב אחד ייכשל; כדי שדיסיונקציה תיכשל, שני הרכיבים חייבים להיכשל.
X ∨ (Y ∧ Z) ≡ (X ∨ Y) ∧ (X ∨ Z)זהו חוק הפילוג שבו משתמשים כדי לעבור ל-CNF. אם אחד הצדדים הוא קוניונקציה, מחברים את X בדיסיונקציה לכל אחד מאיבריה. כאשר שני הצדדים הם קוניונקציות, מפעילים את החוק שוב ושוב ומקבלים סוגריים עבור כל זוג אפשרי של איבר מהצד הראשון ואיבר מהצד השני.
X ∨ (X ∧ Y) ≡ X, X ∧ (X ∨ Y) ≡ Xבחוק הספיגה, החלק המורכב אינו מוסיף מצב חדש: אם X אמת, הדיסיונקציה כבר אמת; ואם X שקר, גם X∧Y שקר. הטיעון השני מתקבל באופן דואלי.
(p ∨ ¬q) ∧ (q ∨ r) ⟹ p ∨ rזהו כלל הרזולוציה על q. כדי ששתי הפסוקיות משמאל יהיו אמת כאשר p שקר, הראשונה מחייבת את q להיות שקר; ואם גם r שקר, השנייה מחייבת את q להיות אמת. הסתירה מראה שלפחות אחד מבין p,r חייב להיות אמת. לכן פסוקית שכבר מתקבלת ברזולוציה מפסוקיות אחרות אינה מוסיפה תנאי ל-CNF.
בנייה באמצעות NAND:
¬p≡p↑p p∧q≡(p↑q)↑(p↑q) p∨q≡(p↑p)↑(q↑q)הנוסחה הראשונה מזינה את אותו ערך פעמיים ולכן מקבלת את שלילתו. בשנייה מפעילים NAND נוסף כדי לבטל את השלילה של הקוניונקציה. השלישית משתמשת בחוק דה-מורגן. מאחר ששלילה וקוניונקציה כבר יוצרות קבוצה שלמה, הבניות מוכיחות ש-NAND לבדו שלם פונקציונלית.
בנייה באמצעות {¬,→}:
p∧q≡¬(p→¬q)הגרירה שבתוך השלילה שקרית בדיוק כאשר p ו-q אמת. לכן השלילה שלה מתנהגת כמו קוניונקציה. מכיוון ש-{¬,∧} שלמה פונקציונלית, גם {¬,→} שלמה.
כדי להוכיח מינימליות של קבוצה בת שני קשרים, צריך לבדוק את כל תת-הקבוצות הממשיות שלה. עבור {¬,→} אלה {¬}, {→} והקבוצה הריקה. שלילה לבדה אינה יכולה לחבר בין שני משתנים. גרירה לבדה תמיד מקבלת T בהצבה שבה כל המשתנים T, ולכן אינה יכולה לבטא ¬p. בלי קשרים אין אפשרות לבנות פסוק מורכב. לכן כל הסרה מבטלת שלמות.
שיטת פתרון
- מסמנים את המשתנים ובונים את כל שורות טבלת האמת משמאל לימין. עבור p,q,r מתחילים בסדר TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF.
- מסמנים ערכי אמת ב-T ו-F, ולא במילים בעברית, כדי שהטבלה תישאר קצרה וחד-משמעית.
- מחשבים עמודות ביניים מפורטות: שלילות, סוגריים פנימיים, גרירות, שקילויות ורק אז את ערך הפסוק השלם.
- ל-DNF: לכל שורת אמת כותבים קוניונקציה. משתנה שמופיע בערך אמת נכתב כמו שהוא, ומשתנה שמופיע בערך שקר נכתב בשלילה.
- ל-CNF: לכל שורת שקר כותבים דיסיונקציה. משתנה שמופיע בערך אמת נכתב בשלילה, ומשתנה שמופיע בערך שקר נכתב כמו שהוא.
- בפישוט בלי טבלה מחליפים גרירה ושקילות, מפזרים שלילות פנימה, ואז משתמשים בפילוג ובספיגה. לאחר קבלת CNF מסירים טאוטולוגיות ובודקים אם פסוקית נובעת מהאחרות באמצעות גרירה, טרנזיטיביות או רזולוציה. בכל הסרה מציגים את החוק שמוכיח שהפסוקית מיותרת.
- להוכחת שלמות של קשר יחיד בונים באמצעותו קבוצה מוכרת של קשרים שלמים, למשל {¬,∧}. להוכחת מינימליות בודקים שכל הסרה של קשר מבטלת את היכולת הזאת.
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
הערות מוכנות למבחן
- ב-DNF קנוני עובדים עם שורות אמת; ב-CNF קנוני עובדים עם שורות שקר.
- ב-CNF הסימן של כל משתנה בסוגריים מתהפך ביחס לערכו בשורת השקר.
- אם ידוע ש-G→H מתקיים תמיד, אז ב-G↔H ≡ (G→H)∧(H→G) הגרירה הראשונה אינה מוסיפה תנאי. לכן השקילות מצטמצמת ל-H→G, שהוא הכיוון שעדיין דורש בדיקה.
- אין חובה שה-CNF המפושט יהיה קנוני, אלא אם השאלה דורשת זאת במפורש.
- בקבוצה יחידונית כמו {NAND}, בדיקת המינימליות מסתכמת בהשוואה לקבוצה הריקה.
- בקבוצה בת שני קשרים, מינימליות דורשת לבדוק את שתי תת-הקבוצות היחידוניות וגם את הקבוצה הריקה.