שיעור פתרון
מבחן תשפ"ד ב', מועד א', שאלה 4 - PNF ותכונות יחס
שיעורי תאוריה רלוונטיים
נוסח השאלה
חשבו צורה פרנקסית נורמלית PNF עבור הנוסחה:
¬∀y [((∃y q(x,y) ∧ ∀x r(x)) → ∃x p(x,y)) ∧ ∃z∃x((p(x,z) ∧ q(y,y)) → q(z,y))]בנוסף, תהי A=P(N), ונגדיר יחס R על A כך:
(D,E)∈R ⇔ D∪E=Nקבעו האם היחס רפלקסיבי, סימטרי, אנטי-סימטרי וטרנזיטיבי. הוכיחו או תנו דוגמה נגדית.
זיהוי השיטה
החלק הראשון דורש טיפול בכמתים ושינוי שמות למשתנים קשורים שחוזרים על עצמם. בגלל שהנוסחה מתחילה בשלילה חיצונית, קודם מכניסים את השלילה פנימה ורק אחר כך מוציאים כמתים. החלק השני הוא בדיקת ארבע תכונות יחס לפי ההגדרות: תכונה כללית מוכיחים בכלליות, ותכונה שנכשלת מפריכים בעזרת דוגמה נגדית אחת מדויקת.
פתרון מודרך
א. צורה פרנקסית נורמלית
נוסח הסעיף: חשבו צורה פרנקסית נורמלית PNF עבור הנוסחה:
¬∀y [((∃y q(x,y) ∧ ∀x r(x)) → ∃x p(x,y)) ∧ ∃z∃x((p(x,z) ∧ q(y,y)) → q(z,y))]נשנה שמות רק למשתנים קשורים שמתנגשים זה בזה או בשם החופשי x. מפת השמות מבהירה איזה כמת קושר כל מופע:
| המופע בנוסחה המקורית | השם בחישוב | הסיבה |
|---|---|---|
| ∀y החיצוני | ∀y₀ | מבדילים אותו מה-∃y הפנימי. |
| ∃y בתוך q(x,y) | ∃a | מונעים ערבוב עם המשתנה החיצוני. |
| ∀x בתוך r(x) | ∀b | מבדילים אותו מה-x החופשי. |
| ∃x בתוך p(x,y) | ∃c | מבדילים אותו משאר כמתיו של x. |
| ∃x בתוך p(x,z) | ∃d | שומרים תחום נפרד בענף השני. |
| x בתוך q(x,y) | x | זהו משתנה חופשי, ולכן אסור לקשור או לשנות אותו. |
| ∃z | ∃z | אין התנגשות בשם הזה, ולכן אין צורך לשנותו. |
נסמן את שני חלקי הקוניונקציה הפנימית:
A = ((∃a q(x,a) ∧ ∀b r(b)) → ∃c p(c,y₀)) B = ∃z∃d((p(d,z) ∧ q(y₀,y₀)) → q(z,y₀))מתחילים בשלילה החיצונית כי היא קובעת את מבנה כל הנוסחה. אחרי הפיכת ¬∀ ל-∃¬ ופתיחת שלילת הקוניונקציה, שני הענפים של החישוב גלויים.
נכניס את השלילה של הכמת החיצוני:
∃y₀ ¬[A ∧ B] ≡ ∃y₀(¬A ∨ ¬B)כעת נפתח את ¬A. כדי לראות את המעבר בלי קפיצה, נסמן את הצד השמאלי של הגרירה ב-C ואת הצד הימני ב-D:
C = (∃a q(x,a) ∧ ∀b r(b)), D = ∃c p(c,y₀) A = (C → D)גרירה נכשלת רק במצב שבו התנאי השמאלי מתקיים והתוצאה הימנית אינה מתקיימת. אלגברית, מחליפים גרירה לפי C→D≡¬C∨D ואז משתמשים בדה-מורגן:
¬A = ¬(C → D) ≡ ¬(¬C ∨ D) ≡ C ∧ ¬Dנציב בחזרה את C ואת D:
¬A ≡ (∃a q(x,a) ∧ ∀b r(b)) ∧ ¬∃c p(c,y₀)נשאר לשלול את כמת הקיום שבצד הימני:
¬A ≡ (∃a q(x,a) ∧ ∀b r(b)) ∧ ∀c ¬p(c,y₀)עבור החלק השני נסמן ב-H את הגרירה הפנימית. השלילה עוברת תחילה דרך שני כמתֵי הקיום:
¬B = ¬∃z∃d H ≡ ∀z∀d ¬Hכעת שוללים את הגרירה עצמה: ההנחה שלה נשארת, והמסקנה נשללת.
¬B ≡ ∀z∀d(p(d,z) ∧ q(y₀,y₀) ∧ ¬q(z,y₀))לפני שמאחדים את הענפים, מוציאים את הכמתים בתוך ¬A. המשתנים a,b,c אינם חופשיים בחלקים האחרים של הקוניונקציה, ולכן מתקבל:
¬A ≡ ∃a∀b∀c(q(x,a) ∧ r(b) ∧ ¬p(c,y₀))נציב את שתי התוצאות בתוך ∃y₀(¬A∨¬B):
∃y₀[(∃a∀b∀c(q(x,a) ∧ r(b) ∧ ¬p(c,y₀))) ∨ (∀z∀d(p(d,z) ∧ q(y₀,y₀) ∧ ¬q(z,y₀)))]כעת מוציאים את הכמתים לקדמת הנוסחה. הכלל שמאפשר זאת הוא שמשתנה קשור שלא מופיע חופשי בצד השני של הקשר יכול לעבור החוצה בלי לשנות את משמעות הנוסחה.
(∃a U) ∨ V ≡ ∃a(U ∨ V), U ∨ (∀z V) ≡ ∀z(U ∨ V)אותו כלל מופעל ברצף על a,b,c,z,d. בתוך הסוגריים נשארת מטריצה בלי כמתים, ולכן זו צורה פרנקסית.
לכן צורה פרנקסית אפשרית היא:
∃y₀ ∃a ∀b ∀c ∀z ∀d [(q(x,a) ∧ r(b) ∧ ¬p(c,y₀)) ∨ (p(d,z) ∧ q(y₀,y₀) ∧ ¬q(z,y₀))]ב. תכונות היחס R
נוסח הסעיף: תהי A=P(N), ונגדיר יחס R על A כך:
(D,E)∈R ⇔ D∪E=Nקבעו האם היחס רפלקסיבי, סימטרי, אנטי-סימטרי וטרנזיטיבי. הוכיחו או תנו דוגמה נגדית.
היחס מוגדר על תתי-קבוצות של N, ולכן כל איבר של A הוא קבוצה.
לפני שבודקים כל תכונה, בוחרים מסלול: סימטריות נובעת מתכונה כללית של איחוד, ולכן מוכיחים אותה לכל D,E. רפלקסיביות, אנטי-סימטריות וטרנזיטיביות הן דרישות כלליות שניתן להפריך באמצעות בחירה אחת שמקיימת את ההנחות אך אינה מקיימת את המסקנה.
רפלקסיביות
כדי שהיחס יהיה רפלקסיבי, צריך שלכל D⊆N יתקיים D∪D=N. אבל אם D=∅, אז D∪D=∅≠N. לכן היחס אינו רפלקסיבי.
סימטריות
אם D∪E=N, אז גם E∪D=N, כי איחוד הוא פעולה קומוטטיבית. לכן היחס סימטרי.
אנטי-סימטריות
ניקח D=N ו-E=∅. אז D∪E=N וגם E∪D=N, אבל D≠E. לכן היחס אינו אנטי-סימטרי.
טרנזיטיביות
ניקח D=∅, E=N, F=∅. מתקיים D∪E=N וגם E∪F=N, אבל D∪F=∅≠N. לכן היחס אינו טרנזיטיבי.
תשובה סופית
PNF אפשרית:
∃y₀ ∃a ∀b ∀c ∀z ∀d [(q(x,a) ∧ r(b) ∧ ¬p(c,y₀)) ∨ (p(d,z) ∧ q(y₀,y₀) ∧ ¬q(z,y₀))]היחס R סימטרי בלבד. הוא אינו רפלקסיבי, אינו אנטי-סימטרי ואינו טרנזיטיבי.
המשך במבחן
מבחן תשפ"ד ב', מועד א' · שאלה 4
המשך לפי סדר השאלות במבחן.
לשאלה הבאה: שאלה 5 - יחס זוגיות ומחלקות שקילות