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