שיעור פתרון
מבחן תשפ"א ב', מועד א', שאלה 1 - אינדוקציה, CNF ו-DNF
שיעורי תאוריה רלוונטיים
נוסח השאלה
- הוכיחו באינדוקציה כי לכל n טבעי, הביטוי n3+2n מתחלק ב-3 ללא שארית.
- חשבו באמצעות זהויות צורה קוניונקטיבית נורמלית CNF, לאו דווקא מלאה, של הביטוי (q∧r)↔(r∨(q∧¬p)).
- חשבו באמצעות טבלת אמת צורה דיסיונקטיבית נורמלית DNF של הביטוי שמופיע בסעיף ב.
זיהוי השיטה
בסעיף א מציגים עד שלם להתחלקות ומשלבים את הנחת האינדוקציה בביטוי של השלב הבא. בסעיף ב מפרקים את השקילות לשתי גרירות ומזהים שאחת מהן טאוטולוגית. בסעיף ג מחשבים טבלת אמת מלאה ומפיקים איבר DNF מכל שורת אמת.
פתרון מודרך
א. הוכחת ההתחלקות באינדוקציה
נוסח הסעיף: הוכיחו באינדוקציה כי לכל n טבעי, הביטוי n3+2n מתחלק ב-3 ללא שארית.
נוכיח את הטענה לכל n∈N0; מכאן היא נכונה בפרט לכל מספר טבעי חיובי.
בסיס האינדוקציה. עבור n=0:
03+2·0=0=3·0קיים עד שלם, ולכן הבסיס מתקיים.
הנחת האינדוקציה. יהי k∈N0 שרירותי. נניח שהטענה נכונה עבורו. לפי הגדרת התחלקות, קיים t∈Z כך ש:
k3+2k=3tצעד האינדוקציה. נתחיל מן הביטוי עבור k+1 ונפתח אותו כדי לחשוף את הביטוי שבהנחת האינדוקציה:
(k+1)3+2(k+1) =k3+3k2+3k+1+2k+2 =(k3+2k)+3(k2+k+1)כעת מציבים את הנחת האינדוקציה:
=3t+3(k2+k+1)=3(t+k2+k+1)מכיוון ש-t,k∈Z, גם t+k2+k+1∈Z. מצאנו עד שלם להתחלקות הביטוי עבור k+1 ב-3. לפי עקרון האינדוקציה, הטענה נכונה לכל n∈N0.
ב. CNF באמצעות זהויות
נוסח הסעיף: חשבו באמצעות זהויות צורה קוניונקטיבית נורמלית CNF, לאו דווקא מלאה, של (q∧r)↔(r∨(q∧¬p)).
נסמן L=q∧r ו-R=r∨(q∧¬p). אם L אמת, אז r אמת ולכן גם R אמת. מכאן שהגרירה L→R היא טאוטולוגיה ואינה מוסיפה תנאי לשקילות:
L↔R≡(L→R)∧(R→L)≡R→Lנחליף את הגרירה ונפזר דיסיונקציה על הקוניונקציה L=q∧r:
R→L≡¬R∨L≡(¬R∨q)∧(¬R∨r)נפתח את ¬R לפי דה-מורגן:
¬R=¬(r∨(q∧¬p))≡¬r∧(¬q∨p)נפשט כל פסוקית בנפרד. בפסוקית הראשונה, הפילוג יוצר טאוטולוגיה אחת:
¬R∨q≡[¬r∧(¬q∨p)]∨q ≡(¬r∨q)∧(¬q∨p∨q)≡¬r∨qבפסוקית השנייה מתקבלת באותו אופן:
¬R∨r≡[¬r∧(¬q∨p)]∨r ≡(¬r∨r)∧(¬q∨p∨r)≡¬q∨p∨rלכן הצורה הקוניונקטיבית המבוקשת היא:
(q∨¬r)∧(p∨¬q∨r)ג. DNF באמצעות טבלת אמת
נוסח הסעיף: חשבו באמצעות טבלת אמת צורה דיסיונקטיבית נורמלית DNF של הביטוי שמופיע בסעיף ב.
נחשב את רכיבי הפסוק משמאל לימין. סדר השורות הוא TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF.
| p | q | r | ¬p | q∧r | q∧¬p | r∨(q∧¬p) | F |
|---|---|---|---|---|---|---|---|
| T | T | T | F | T | F | T | T |
| T | T | F | F | F | F | F | T |
| T | F | T | F | F | F | T | F |
| T | F | F | F | F | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | T | T | F |
| F | F | T | T | F | F | T | F |
| F | F | F | T | F | F | F | T |
שורות האמת הן TTT, TTF, TFF, FTT, FFF. מכל שורה כותבים קוניונקציה שמתארת אותה בדיוק:
(p∧q∧r)∨(p∧q∧¬r)∨(p∧¬q∧¬r)∨(¬p∧q∧r)∨(¬p∧¬q∧¬r)תשובה סופית
3 מחלק את n3+2n לכל n∈N0.
CNF אפשרית: (q∨¬r)∧(p∨¬q∨r).
DNF קנוני: (p∧q∧r)∨(p∧q∧¬r)∨(p∧¬q∧¬r)∨(¬p∧q∧r)∨(¬p∧¬q∧¬r).
המשך במבחן
מבחן תשפ"א ב', מועד א' · שאלה 1
המשך לפי סדר השאלות במבחן.
לשאלה הבאה: שאלה 2 - קבוצה עם כמתים, PNF וקשרים מינימליים