שיעור פתרון

מבחן תשפ"ג ב', מועד א', שאלה 2 - קבוצה עם כמתים, PNF ו-NAND

שיעורי תאוריה רלוונטיים

נוסח השאלה

  1. תהי N₀={0,1,2,3,...}, ותהיינה A₁={5,7,9,11}, A₂={15,17,19,...}. חשבו את איברי הקבוצה: B={x∈N₀ | ∃y∈A₁, ∀z∈A₂, x<2(y+z)}
  2. חשבו צורה פרנקסית נורמלית עבור הנוסחה: ¬∀y [(((∀x q(x,y) ∨ ∃x r(x)) → ∀x p(x,y)) ∧ ∀z∃x(p(x,z) → ¬q(z,y)))]
  3. הוכיחו שהקבוצה המכילה את הקשר NAND בלבד היא קבוצה מינימלית של קשרים.

זיהוי השיטה

בסעיף א מנתחים את סדר הכמתים ומחפשים את הבחירות הקיצוניות שמקשות או מקלות על האי-שוויון. בסעיף ב משנים שמות למשתנים קשורים, דוחפים את השלילה פנימה ומוציאים את הכמתים. בסעיף ג בונים שלילה וקשרים בסיסיים באמצעות NAND, ואז בודקים מינימליות.

פתרון מודרך

א. חישוב הקבוצה B

נוסח הסעיף: תהי N₀={0,1,2,3,...}, ותהיינה A₁={5,7,9,11}, A₂={15,17,19,...}. חשבו:

B={x∈N₀ | ∃y∈A₁, ∀z∈A₂, x<2(y+z)}

ניקח x∈N₀ ונבדוק מה נדרש כדי שייכנס ל-B. צריך לבחור y אחד מתוך A₁ כך שהאי-שוויון יעבוד לכל z∈A₂.

כדי להקל על האי-שוויון נבחר את y הגדול ביותר, כלומר y=11, כי הגדלת y מגדילה את אגף ימין. לאחר הבחירה, הערך הקטן ביותר של אגף ימין מתקבל ב-z הקטן ביותר, כלומר z=15:

2(y+z)≥2(11+15)=52

לכן לכל x<52, הבחירה y=11 מבטיחה שלכל z∈A₂ מתקיים x<2(11+z). מכאן שכל המספרים 0,1,...,51 שייכים ל-B.

כעת נבדוק שאין איברים נוספים. יהי x≥52. לכל y∈A₁ מתקיים y≤11. נבחר את z=15, ששייך ל-A₂. אז:

2(y+15)≤2(11+15)=52≤x

לכן האי-שוויון x<2(y+z) נכשל כבר עבור z=15, בלי קשר לבחירת y. שום x≥52 אינו שייך ל-B.

B={0,1,2,...,51}

ב. צורה פרנקסית נורמלית

נוסח הסעיף: חשבו צורה פרנקסית נורמלית עבור הנוסחה:

¬∀y [(((∀x q(x,y) ∨ ∃x r(x)) → ∀x p(x,y)) ∧ ∀z∃x(p(x,z) → ¬q(z,y)))]

תחילה נשנה שמות למשתנים הקשורים, כדי שכל כמת יקבל שם נפרד:

המופע המקוריהשם החדשהתפקיד
∀y∀y₀הכמת החיצוני
∀x ב-q(x,y)∀aהענף הראשון
∃x ב-r(x)∃bהענף הראשון
∀x ב-p(x,y)∀cמסקנת הגרירה
∃x אחרי ∀z∃dהענף השני
¬∀y₀ [A∧B]

כאשר:

A=((∀a q(a,y₀)∨∃b r(b))→∀c p(c,y₀)) B=∀z∃d(p(d,z)→¬q(z,y₀))

השלילה החיצונית הופכת את הכמת הכולל לכמת קיום, ודה-מורגן הופך את הקוניונקציה לדיסיונקציה:

¬∀y₀[A∧B]≡∃y₀(¬A∨¬B)

נפתח את ¬A. שלילת גרירה משאירה את ההנחה ושוללת את המסקנה:

¬A≡(∀a q(a,y₀)∨∃b r(b))∧¬∀c p(c,y₀) ≡(∀a q(a,y₀)∨∃b r(b))∧∃c¬p(c,y₀)

המשתנים a,b,c אינם חופשיים בחלקים האחרים, ולכן אפשר להוציא את הכמתים לפי סדר המבנה:

¬A≡∀a∃b∃c[(q(a,y₀)∨r(b))∧¬p(c,y₀)]

כעת נפתח את ¬B. השלילה הופכת ∀z∃d ל-∃z∀d. בנוסף, שלילת הגרירה p(d,z)→¬q(z,y₀) דורשת שההנחה תהיה אמת והמסקנה תהיה שקר:

¬B≡∃z∀d[p(d,z)∧q(z,y₀)]

נציב את שני הענפים ונוציא את הכמתים לקדמת הנוסחה. כל משתנה קשור מופיע רק בענף שלו, ולכן ההעברה אינה לוכדת משתנה חופשי:

∃y₀∀a∃b∃c∃z∀d [((q(a,y₀)∨r(b))∧¬p(c,y₀)) ∨ (p(d,z)∧q(z,y₀))]

כל הכמתים נמצאים בתחילת הנוסחה, והמטריצה שבתוך הסוגריים אינה מכילה כמתים. לכן זו צורה פרנקסית נורמלית.

ג. מינימליות של NAND

נוסח הסעיף: הוכיחו שהקבוצה המכילה את הקשר NAND בלבד היא קבוצה מינימלית של קשרים.

נסמן NAND באמצעות ↑:

p↑q≡¬(p∧q)

כדי להראות שהקבוצה {↑} שלמה פונקציונלית, מספיק לבנות באמצעותה את ¬ ואת ∧, מפני ששני הקשרים האלה מאפשרים לבנות כל פסוק לוגי.

כאשר מזינים ל-NAND את אותו פסוק פעמיים, מקבלים שלילה:

p↑p≡¬(p∧p)≡¬p

כדי לבנות קוניונקציה, מפעילים NAND פעם אחת ומבטלים את השלילה באמצעות NAND נוסף עם אותו קלט בשני המקומות:

p∧q≡¬(p↑q)≡(p↑q)↑(p↑q)

לבדיקה נוספת, גם דיסיונקציה מתקבלת באמצעות דה-מורגן:

p∨q≡¬(¬p∧¬q)≡(p↑p)↑(q↑q)

לכן {↑} היא קבוצה שלמה פונקציונלית. כדי להוכיח מינימליות צריך לבדוק שאי אפשר להסיר ממנה קשר ועדיין להישאר עם קבוצה שלמה. הקבוצה היא יחידונית, ולכן תת-הקבוצה הממשית היחידה שלה היא הקבוצה הריקה. בלי קשרים כלל אי אפשר לבנות אפילו את ¬p. לכן הקבוצה הריקה אינה שלמה פונקציונלית, ומכאן {↑} מינימלית.

תשובה סופית

B={0,1,2,...,51}.

PNF אפשרית היא ∃y₀∀a∃b∃c∃z∀d [((q(a,y₀)∨r(b))∧¬p(c,y₀))∨(p(d,z)∧q(z,y₀))].

הקבוצה {NAND} שלמה פונקציונלית, והסרת הקשר היחיד משאירה קבוצה שאינה שלמה; לכן היא מינימלית.

המשך במבחן

מבחן תשפ"ג ב', מועד א' · שאלה 2

המשך לפי סדר השאלות במבחן.

לשאלה הבאה: שאלה 3 - קונטרפוזיציה, דוגמה נגדית וקבוצות חזקה