שיעור תאוריה
צורה פרנקסית נורמלית
איך מזהים שהנושא מתאים
- מופיעים כמתים כמו ∀ ו-∃.
- מבקשים צורה פרנקסית נורמלית או PNF.
- יש גרירות, שלילות וכמתים שחוזרים עם אותם שמות משתנים.
- צריך להוציא את כל הכמתים לקדמת הנוסחה ולהשאיר מטריצה בלי כמתים.
אינטואיציה
תחשבו על נוסחה עם כמתים כמו על הוראות שיבוץ: קודם צריך לדעת את מי בוחרים ובאיזה סדר, ורק אחר כך בודקים אם השיבוץ עומד בתנאי. צורה פרנקסית מרכזת את כל הוראות הבחירה בתחילת הנוסחה ואת התנאי שנבדק בסוף.
סדר הבחירות משנה את החופש שיש לנו. ∀x∃y דומה למצב שבו לכל אדם מותר להתאים משימה אחרת. לעומת זאת, ∃y∀x דורש למצוא משימה אחת שמתאימה לכולם. לכן אי אפשר להחליף את סדר הכמתים רק כדי לקבל נוסחה נוחה יותר.
שינוי שם של משתנה קשור דומה להחלפת תג שם. אם שני אנשים שונים מסומנים בטעות באותו שם, קשה לדעת למי כל הוראה שייכת. החלפת השם אינה משנה את האדם או את התנאי; היא רק מפרידה בין התפקידים ומונעת מכמת אחד להשתלט על משתנה שלא שייך לו.
לפני שמרכזים את הכמתים, מסירים גרירות ודוחפים שלילות פנימה. כך כל הוראת בחירה נשארת מחוברת לתנאי שעליו היא פועלת, ואפשר להעביר אותה לקדמת הנוסחה בלי לשנות את משמעותה.
הגדרות פורמליות
| מושג | משמעות |
|---|---|
| פרדיקט | ביטוי שמקבל ערך אמת לאחר שנותנים ערכים למשתנים שלו, למשל P(x). |
| כמת | ∀x דורש שטענה תתקיים לכל ערך של x; ∃x דורש שקיים לפחות ערך אחד שעבורו היא מתקיימת. |
| תחום כמת | תת-הנוסחה שעליה הכמת פועל. מופעי המשתנה בתוך התחום הזה קשורים לכמת. |
| משתנה קשור | מופע של משתנה שנמצא בתחום של כמת המתייחס אליו. |
| משתנה חופשי | מופע של משתנה שאינו נמצא בתחום של כמת המתייחס אליו, ולכן ערכו מגיע מבחוץ. |
| מטריצה | החלק של נוסחת PNF שנשאר אחרי רצף הכמתים ואינו מכיל כמתים. |
| לכידת משתנה | מצב שבו העברת כמת גורמת למשתנה שהיה חופשי להיכנס לתחומו ולהפוך לקשור. פעולה כזאת משנה את משמעות הנוסחה. |
צורה פרנקסית נראית כך:
Q₁x₁ Q₂x₂ ... Qnxn [מטריצה בלי כמתים]כל Qi הוא אחד מהכמתים ∀ או ∃.
כללי שלילה שימושיים:
¬∀x φ ≡ ∃x ¬φ ¬∃x φ ≡ ∀x ¬φהיפוך הכמת נובע ממשמעות השלילה: הטענה "לא כל x מקיים את φ" אומרת שקיים לפחות x אחד שאינו מקיים אותה. באופן דומה, "לא קיים x שמקיים" אומר שכל x נכשל.
¬(φ ∧ ψ) ≡ ¬φ ∨ ¬ψ, ¬(φ ∨ ψ) ≡ ¬φ ∧ ¬ψאחרי היפוך כמת ממשיכים לדחוף את השלילה בעזרת חוקי דה-מורגן. השלילה משנה גם את הקשר בין החלקים, עד שכל שלילה צמודה לפרדיקט ולא לביטוי מורכב.
¬(φ → ψ) ≡ ¬(¬φ ∨ ψ) ≡ φ ∧ ¬ψהמשמעות של שלילת גרירה: התנאי השמאלי מתקיים, אבל התנאי הימני אינו מתקיים. לכן כששוללים גרירה, לא שוללים את שני הצדדים; משאירים את הצד השמאלי ושוללים רק את הצד הימני.
כללי הוצאת כמתים החוצה דורשים שהמשתנה של הכמת לא יהיה חופשי בצד השני של הקשר:
(Qx φ) ∧ ψ ≡ Qx(φ ∧ ψ), (Qx φ) ∨ ψ ≡ Qx(φ ∨ ψ)כאן Q הוא ∀ או ∃, והכלל תקף כאשר x אינו מופיע חופשי ב-ψ.
התנאי הזה מונע לכידת משתנה. אם x אינו חופשי ב-ψ, הרחבת תחום הכמת על הקשר אינה משנה את ψ. אם x כן חופשי שם, העברת הכמת תהפוך אותו בטעות למשתנה קשור ותשנה את משמעות הנוסחה.
בשינוי שם של משתנה קשור משנים את הכמת ואת כל המופעים שהוא קושר, ורק אותם. לדוגמה, מותר להחליף ∃x P(x) ב-∃u P(u), כל עוד u אינו גורם להתנגשות חדשה. משתנה חופשי בשם x מחוץ לתחום הכמת נשאר ללא שינוי.
שיטת פתרון
- משנים שמות למשתנים קשורים שחוזרים באותה נוסחה או מתנגשים במשתנה חופשי. משתנה קשור שאינו יוצר התנגשות יכול להישאר בשמו.
- מבטלים גרירות ושקילויות בעזרת קשרי ¬, ∧, ∨.
- כאשר שוללים גרירה, מסמנים קודם את הצד השמאלי ואת הצד הימני, ואז משתמשים בכלל ¬(φ→ψ)≡φ∧¬ψ.
- דוחפים שלילות פנימה עד שהן צמודות לפרדיקטים בלבד; במיוחד מטפלים בשלילה חיצונית לפני הוצאת הכמתים.
- לפני כל העברת כמת בודקים שהמשתנה שלו אינו חופשי בצד השני. אם הוא חופשי, משנים תחילה את שם המשתנה הקשור לשם חדש.
- מוציאים את הכמתים לפי סדר הופעתם במבנה שהתקבל; אין להחליף באופן חופשי בין כמת קיום לכמת כולל.
- בודקים שבסוף אין כמתים בתוך הסוגריים הפנימיים, שכל משתנה קשור בכמת המתאים, ושקבוצת המשתנים החופשיים נשארה כפי שהייתה בנוסחה המקורית.
| שלב | פעולה | למה זה חשוב |
|---|---|---|
| שינוי שמות | משנים שמות למשתנים קשורים שחוזרים על עצמם. | מונעים לכידת משתנים ובלבול בין תפקידים. |
| ביטול גרירות | מחליפים גרירות ושקילויות בקשרים בסיסיים. | מאפשרים טיפול מסודר בשלילות. |
| דחיפת שלילות | מכניסים שלילות פנימה עד שהן צמודות לפרדיקטים. | מכינים את הנוסחה להוצאת כמתים. |
| הוצאת כמתים | מעבירים כמתים לקדמת הנוסחה לפי הכללים. | יוצרים את מבנה הצורה הפרנקסית. |
| בדיקה סופית | מוודאים שהחלק הפנימי בלי כמתים. | מאשרים שהגענו ל-PNF. |
הערות מוכנות למבחן
- אסור לתת לאותו שם משתנה לשמש גם כמשתנה חופשי וגם כמשתנה קשור באותו חישוב.
- שינוי שם של משתנה קשור הוא כלי למניעת בלבול, לא חובה טכנית על כל כמת.
- כאשר שוללים כמת, סוג הכמת מתהפך.
- כאשר שוללים גרירה, מקבלים את התנאי השמאלי יחד עם שלילת התנאי הימני.
- בדרך כלל יש יותר מתשובה נכונה אחת ל-PNF, כי מותר לשנות שמות של משתנים קשורים.