שיעור פתרון
מבחן תשפ"א ב', מועד א', שאלה 2 - קבוצה עם כמתים, PNF וקשרים מינימליים
שיעורי תאוריה רלוונטיים
נוסח השאלה
- תהי N0={0,1,2,3,...}, ותהיינה A1={5,7,9}, A2={11,13,15,...}. חשבו: B={x∈N0 | ∀y∈A1, ∃z∈A2: yz<x}
- חשבו צורה פרנקסית נורמלית עבור הנוסחה: ¬∀y [((∃x p(x)→(∀x q(x,y)∨∃x r(x)))∧∀z(p(x,z)→¬∃y q(z,y)))]
- הוכיחו שהקבוצה {¬,→} היא קבוצה מינימלית של קשרים.
זיהוי השיטה
בסעיף א פותחים את סדר הכמתים ומזהים את הערכים הקיצוניים שקובעים את הסף. בסעיף ב משנים שמות למשתנים קשורים, אך שומרים על המשתנה החופשי x. בסעיף ג מוכיחים תחילה שלמות פונקציונלית, ואז מראים שכל תת-קבוצה ממשית מאבדת יכולת חיונית.
פתרון מודרך
א. חישוב הקבוצה B
נוסח הסעיף: תהי N0={0,1,2,3,...}, ותהיינה A1={5,7,9}, A2={11,13,15,...}. חשבו:
B={x∈N0 | ∀y∈A1, ∃z∈A2: yz<x}יהי x∈N0. כדי ש-x יהיה ב-B, לכל y מתוך A1 צריך למצוא לפחות z אחד מתוך A2 שעבורו yz<x.
עבור y קבוע, המכפלה הקטנה ביותר מתקבלת ב-z=11. מכיוון שהתנאי חייב לעבוד לכל y, המקרה הקשה ביותר הוא y=9, הערך הגדול ביותר ב-A1:
9·11=99אם x>99, אפשר לבחור z=11 עבור כל y∈A1. אז yz≤9·11=99<x, ולכן x∈B.
אם x≤99, נבחר y=9. לכל z∈A2 מתקיים z≥11, ולכן:
yz=9z≥9·11=99≥xבמקרה זה לא קיים z שמקיים yz<x. לכן המספרים הטבעיים שמקיימים את התנאי הם בדיוק:
B={100,101,102,...}ב. צורה פרנקסית נורמלית
נוסח הסעיף: חשבו צורה פרנקסית נורמלית עבור:
¬∀y [((∃x p(x)→(∀x q(x,y)∨∃x r(x)))∧∀z(p(x,z)→¬∃y q(z,y)))]אותו שם משמש כאן כמה כמתים שונים, ובנוסף x ב-p(x,z) הוא משתנה חופשי. לכן נשנה רק את שמות המשתנים הקשורים:
| המופע | שם חדש |
|---|---|
| ∀y החיצוני | ∀a |
| ∃x p(x) | ∃u p(u) |
| ∀x q(x,y) | ∀v q(v,a) |
| ∃x r(x) | ∃w r(w) |
| ∃y q(z,y) | ∃t q(z,t) |
המשתנה החופשי x נשאר ללא שינוי. נסמן את שני חלקי הקוניונקציה ב-A וב-C. השלילה החיצונית הופכת את הכמת הכולל לקיומי ואת הקוניונקציה לדיסיונקציה:
¬∀a(A∧C)≡∃a(¬A∨¬C)בחלק הראשון משתמשים בכלל ¬(P→Q)≡P∧¬Q, ולאחר מכן הופכים את הכמתים שנמצאים תחת שלילה:
¬A≡∃u p(u)∧¬(∀v q(v,a)∨∃w r(w)) ≡∃u p(u)∧∃v¬q(v,a)∧∀w¬r(w) ≡∃u∃v∀w[p(u)∧¬q(v,a)∧¬r(w)]בחלק השני שלילת הכמת הכולל מספקת z שעבורו הגרירה נכשלת. גרירה נכשלת כאשר ההנחה אמת והמסקנה שקר:
¬C≡¬∀z(p(x,z)→¬∃t q(z,t)) ≡∃z∃t[p(x,z)∧q(z,t)]אף אחד מן המשתנים הקשורים אינו חופשי בענף האחר, ולכן אפשר להעביר את כל הכמתים לקדמת הנוסחה לפי סדרם:
∃a∃u∃v∀w∃z∃t[(p(u)∧¬q(v,a)∧¬r(w))∨(p(x,z)∧q(z,t))]המטריצה אינה מכילה כמתים, והמשתנה החופשי x נשאר חופשי. לכן זו צורה פרנקסית נורמלית תקינה.
ג. מינימליות של {¬,→}
נוסח הסעיף: הוכיחו שהקבוצה {¬,→} היא קבוצה מינימלית של קשרים.
תחילה נוכיח שלמות. באמצעות שלילה וגרירה אפשר לבנות קוניונקציה:
p∧q≡¬(p→¬q)הגרירה p→¬q שקרית בדיוק כאשר p ו-q אמת; השלילה הופכת את המצב היחיד הזה לאמת. מאחר שהקבוצה {¬,∧} שלמה פונקציונלית, גם {¬,→} שלמה.
כעת נבדוק מינימליות. תת-הקבוצות הממשיות הן {¬}, {→} והקבוצה הריקה.
- באמצעות ¬ בלבד אפשר לשנות ערך של משתנה יחיד, אך אי אפשר לחבר בין שני משתנים ולכן אי אפשר לבטא למשל p∧q.
- כל נוסחה שנבנית רק מ-→ מקבלת T כאשר כל משתניה מקבלים T: הדבר נכון למשתנים עצמם, ואם שני חלקי גרירה אמת גם הגרירה אמת. לכן אי אפשר לבטא ¬p, שערכו F כאשר p=T.
- בלי קשרים כלל אפשר לכתוב רק משתנים, ולכן הקבוצה הריקה אינה שלמה.
כל הסרה של קשר מבטלת שלמות פונקציונלית, ולכן {¬,→} היא קבוצה מינימלית של קשרים.
תשובה סופית
B={100,101,102,...}.
PNF אפשרית היא ∃a∃u∃v∀w∃z∃t[(p(u)∧¬q(v,a)∧¬r(w))∨(p(x,z)∧q(z,t))].
{¬,→} שלמה פונקציונלית, ואף אחת מתת-הקבוצות הממשיות שלה אינה שלמה; לכן היא מינימלית.
המשך במבחן
מבחן תשפ"א ב', מועד א' · שאלה 2
המשך לפי סדר השאלות במבחן.
לשאלה הבאה: שאלה 3 - קונטרפוזיציה והפרש סימטרי במכפלה קרטזית