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