הדפסות 8 פשרים (פרדיקטים)

לא לשכוח תמיד להציג בפשר גם את הפריטים מתחום הדיון! כל אחד נמצא באקסטנציה של עצמו... לזכור לגבי "מכלול הפשרים" - אנחנו מציבים בפשר u את התנאים המינימליים שדרושים כדי שההנחות יהיו נכונות, ומראים שהמסקנה מתחייבת. הכוונה היא שאנחנו מציירים "קו כללי" עבור כל פשר בו ההנחות כולן נכונות (כי תקפות זה שאין פשר בו הטיעון שקרי) הנחת הקיום בפשר: אסור פשר ריק, מותר מונח (פרדיקט) ריק
בהוכחת שקילות: לזכור שעושים פעמיים: פעם אחת מניחים ש-u נכון לפסוק א', ומראים מה זה מחייב לגבי a, ושזה מחייב שגם פסוק א' יהיה אמיתי בהתאם. פעם שניה מניחים ש-u נכון לפסוק ב', ומראים מה זה מחייב לגבי a, ושזה מחייב שגם פסוק ב' יהיה אמיתי בהתאם. הוכחת טאוטולוגיה: לא ממש הבנתי את המתודה... צריך עם השלילה? צריך להראות שאין סתירה במכלול? מה עושים??? -- נראה לי שהבנתי: מראים

פשר:

• פשר כולל תחום דיון (Domain) ופונקציית השמה - שמכונה I כמו Interpertation
• תחום הדיון (Domain) הוא קבוצה לא-ריקה של פרטים (למשל: "כל המספרים הראשוניים")

• פונקציית ההשמה (I, Interpertation) מתאימה איברים מתחום הדיון לקבועים הלא-לוגיים בשפה הפורמלית.

• לקבוע (a,b,c) פונקציית ההשמה מתאימה פרט אחד בלבד מתחום הדיון

• לפרדיקט חד-מקומי (נניח Fa) פונקציית ההשמה מתאימה [[7 - יסודות תחשיב הפרדיקטים#אקסטנציה (extension) של פרדיקט|אקסטנציה]] אחת
• לפרדיקט דו, תלת מקומי וכן הלאה פונקציית ההשמה מתאימה זוגות סדורים, שלשות סדורות וכן הלאה (צמד של אקסטנציות שיש להן זוגות מתאימים, וכך עם שלשות).

אופן הסימון:

• אמרנו שפונקציית ההשמה מתאימה לפסוק את האקסטנציה שלו: לכן, כדי לסמן את האקסטנציה של פסוק נכתוב I(P)

• גם אות פרדיקט נכתוב באותו אופן (בלי מציינים בתוך הקלט של פונקציית ההשמה)

  • תרגיל: מדברים על הקבוצה {1, 2, 3, 4, 5}
  • את הקבועים נסמן כך: I(a) = 3 I(b) = 1
  • נסמן פרדיקטים כך:
  • I(F)={1, 4} פרדיקט חד-מקומי

  • I(R)=<1, 3>, <2, 4>} פרדיקט דו-מקומי (בתוך סוגריים משולשים מפרידים התאמות סדורות, עם פסיקים להפרדת האיברים בתוך התאמה, ועם פסיקים תואמים ביניהן)

  • את הפשר של הפסוק נסמן לבסוף כך: Domain = {1, 2, 3, 4, 5} I(R)=<1, 3>, <2, 4>} I(F)={1, 4} I(a) = 3 I(b) = 1

קביעת ערך האמת של פסוק:

• כיצד נקבע ערך האמת של פסוק לפי הפשר הנתון? (מהסעיף הקודם)

• נתחיל באמצעות דוגמאות:

• הפסוק Fa יהיה שקרי לפי הפשר הנתון: זאת מכיוון ש-a=3, ו-F יכול להיות שווה רק ל-1 או ל-4 בהתאם לאקסטנציה שהוגדרה.

• הפסוק Rba הוא אמיתי לפי הפשר: הוגדר ש-R יכול לכלול את 3 ו-1, שהם b ו-a, או את 2 ו-4.
• הפסוק Rba→Raa יהיה שקרי כי כאשר R מכיל את 3 ו-1 (a ו-b), הוא לא יכול להכיל פעמיים את 1 (a).
• הפסוק xFx∀ יהיה שקרי כי נתון שלא עבור כל x (פריט אפשרי בתחום הדיון), יתכן ש-Fx יהיה נכון.

• הפסוק xRxa∃ אמיתי בפשר מכיוון שיש x שיכול להיכלל יחד עם a באקסטנציה של הפרדיקט R - מדובר כמובן ב-b

• לשאלה "מה הוא ערך האמת של הפסוק" יש משמעות רק בהתייחסות לפשר מסוים

כללים לתנאי האמת

• כמו שעשינו עבור נב"כים בפרקים קודמים, נשתמש בהגדרה רקורסיבית ונקבע חוקים בסיסיים לערך האמת, שהם "נקודת המוצא אל האמת", ומהם נסיק לגבי פסוקים מורכבים יותר:

• אם פסוק הוא אטומי (בתחשיב הפרדיקטים: חסר קשרים או כמתים, רק אות פרדיקט ומציינים): אז הוא מהצורה Pa, Rab, Sabc וכן הלאה.

  • הפסוק Pa יהיה אמיתי אך ורק אם a נמצאת באקסנטציה של P בפשר;
  • הפסוק Rab יהיה אמיתי אך ורק אם הזוג הסדור נמצא באקסטנציה של R בפשר;
  • הפסוק Sabc - רק אם השלשה הסדורה בפשר של S, וכן הלאה...

"לספק נוסחה"

• אם נתונה נוסחה כך: Φx, המשמעות היא שבנוסחה זו, המשתנה x הוא היחידי בעל מופעים חופשיים!
• אם נתון פריט a, אנחנו נגיד ש-a 'מספק את הנוסחה' Φx אם ורק אם, הפסוק שנוצר מהצבה של הפריט a במקום כל מופע חופשי של x, הוא אמיתי בפשר.
  • בעצם, בתחשיב הפרדיקטים יש שני סוגים של משתנים: 'קשורים' הם כאלה שנותנים משמעות לאיזושהי אמירה שקשורה לכמת. הם משמשים כדי להביע טענה קטגורית. 'חופשיים' הם כאלה שבאמת אין עבורם ערך קבוע - הם אלה שהולכים לשנות את ערך האמת שלה בהתאם לקלט שהיא תקבל (בעוד שהשאר משמשים ב-'מעגל סגור' כדי לבטא יחסים לוגיים)

כללים לתנאי האמת: המשך (כמתים)

[[8 - סמנטיקה של תחשיב הפרדיקטים#כללים לתנאי האמת|המשך לזה]] 1. 1. פסוק מהצורה xΦx∃ הוא אמיתי אם ורק אם יש בתחום הדיון פריט ש-מספק את הנוסחה Φx (כאמור: שמחזיר T אם הוא מחליף כל מופע חופשי של x) (המשמעות המילולית: אם יש x כך ש(פאי x), אז צריך להיות פריט שעבורו (פאי x) - כלומר פאי שהמשתנים החופשיים שלה מוגדרים כ-x, היא אמת) 2. פסוק מהצורה xΦx∀ הוא אמיתי אך ורק אם כל פריט בתחום הדיון מספק את הנוסחה Φx

• לא להתבלבל במטא-שפה - המשמעות של Φx היא שזו נוסחה שיש בה משתנה חופשי x, ולא שהיא אות פרדיקט עם מציין אישי אחד x

פסוקים מרובי כמתים

• המורכבות של תחשיב הפרדיקטים עולה משמעותית כאשר אנחנו כותבים פסוקים מרובי כמתים: כאלה שכוללים כמתים נוספים בטווח של כמתים.

• זו גם התכונה שמאפשרת לתחשיב הפרדיקטים לבטא הרבה יותר מאשר הלוגיקה האריסטוטלית ותחשיב הפסוקים גם יחד (זה מרגיש כמו שילוב אבל העוצמה היא יותר מאשר של סתם שילוב)

• נבחן פסוק: x∃yRxy∃ להלן הפשר: ![[Pasted image 20250111203041.png]]

• לשים לב - לפריט a אין "שם בשפה" - שם בשפה הוא מציין קבוע שמוצמד לפריט בודד.

• בהיעדר שם בשפה, אפשר לדבר על הפריט a ולקרוא לו זמנית "a", אבל כדי לכתוב Aa עלינו תחילה לקרוא ל-a בשם a (כרגע הוא "data" ולא "variable")

תקפות

• ניזכר בהגדרת התקפות: טיעון הוא תקף אם אין מצב שבו ההנחות נכונות והמסקנה לא.
  • בתחשיב הפסוקים בדקנו זאת ע"י מציאת המציין - אם המציין הוא F כאשר ההנחות כולן T באחת האפשרויות, הפסוק אינו תקף
• בתחשיב הפרדיקטים: טיעון הוא תקף אם ורק אם **אין פשר שבו הנחותיו אמיתיות ומסקנתו שקרית **

• בתחשיב הפרדיקטים: אנחנו לא יכולים להוכיח תקפות ע"י בדיקת הפשר עבור מצב בו ההנחות אמתיות והמסקנה שקרית

• כלומר, נחדד: אפשר להוכיח אי תקפות ע"י מציאת פשר שעבורו, הנחות הטיעון אמתיות אך המסקנה שקרית. אי אפשר להוכיח תקפות ע"י פשר.

סתירה עצמית, טאוטולוגיה וקונטינגנציה

• נזכיר: טאוטולוגיה נכונה בכל מצב, סתירה עצמית היא שקרית בכל מצב, קונטינגנציה זה כל מיקס
• נתרגם לתחשיב הפרדיקטים:
• סתירה עצמית: אם הפסוק שקרי בכל פשר
• טאוטולוגיה: אם הפסוק אמיתי בכל פשר

• קונטינגנציה: אם הפסוק לפעמים שקרי ולפעמים אמיתי, תלוי בפשר

• להוכיח טאוטולוגיה באמצעות פשר זה כמובן בלתי אפשרי כי יש אינסוף אפשרויות

• כן אפשר להוכיח שפסוק הוא לא טאוטולוגיה - ע"י מציאת פשר שקרי אחד לפחות
• אותו דבר רק הפוך עם סתירה עצמית - אי אפשר להוכיח שפסוק הוא סתירה עצמית כי יש אינסוף פשרים, אבל אפשר להוכיח שהוא לא סתירה עצמית ע"י מציאת פשר אחד לפחות **שלפיו הוא אמיתי **

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

  • שאלה למחשבה: לדעתי אי אפשר להוכיח שפסוק הוא לא קונט' בגלל אותה בעיה שמונעת להוכיח שהוא כן טאוטולוגיה או סתירה

• רק מחדד: פסוק הוא שקרי אם אין בפשר פריטים שיספקו אותו, ואמיתי אם יש

קונסיסטנטיות

• ניזכר מה זה קונסיסטנטיות בתחשיב הפסוקים: אם יש לפחות מצב אחד שבו כל הפסוקים בקבוצת פסוקים (גזע "עץ האמת") הם אמיתיים
• בתחשיב הפרדיקטים: קונסיסטנטית היא קבוצת פסוקים אם קיים פשר שלפיו כל הפסוקים בקבוצה אמיתיים
  • ניחוש: זה אומר שאי אפשר להוכיח שקבוצה אינה קונסיסטנטית, רק שהיא כן
• את הקבוצה מקבלים ככה {פסוק, פסוק}

שקילות לוגית

• שני פסוקים הם שקולים לוגית אם הם מקיימים ביניהם את פונקציית השקילות: כלומר, אם בכל פשר, יש להם אותו ערך אמת.

• שוב, אי אפשר להוכיח את זה לגבי כל פשר, אבל אפשר להוכיח שהם לא שקולים ע"י מציאת פשר מתאים אחד

  האם הטענה שפסוקים הם שקולים לוגית היא תלויית-פשר? לדעתי: לא. המשמעות של שקילות לוגית היא אותו ערך אמת בכל פשר, בעוד שפשר מסוים הוא מספיק כדי להוכיח שלא מתקיימת שקילות.

• רק ערך אמת הוא יחסי לפשר

• יש מקרים שבהם ברור לנו שהפסוקים נובעים זה מזה ואין לנו איך להוכיח שאין פשר בו הם לא שקולים - נלמד בהמשך איך מוכיחים 'קביעות' על מכלול הפשרים

הוכחות על מכלול הפשרים

• כדי לעשות זאת, נדגים על מצב שאנחנו רוצים להראות תקפות של טיעון.
• נמצא פשר שבו כל הפסוקים אמיתיים ונקרא לו μ
• לפי ההגדרה של אמת בפשר, כל פריט בתחום הדיון שלו מספק את כל נוסחאות הטיעון
• נכנה פריט שרירותי מתחום הדיון בשם a - ניתן להציבו בכל אחת מנוסחאות הטיעון והוא יספק אותה (בפשר μ)
• נציב אותו (a) במקום x בכל אחד מהטיעונים ונבדוק האם יתכן שיספק את כל הנוסחאות שהוא אמור לספק
• לפעמים ישנן שתי אפשרויות - כלומר אפשר שSa יהיה שקרי או אמיתי, והכל זורם בהתאם (כך שההנחות נכונות והמסקנה גם)
• חשוב לזכור את הנחת הקיום: אנחנו נצמדים בקורס להנחה שאם יש פשר, תחום הדיון שלו אינו ריק
• בלוגיקה האריסטוטלית הנחת הקיום שלמדנו היא מחמירה יותר - ולפיה, אין מונחים ריקים (אם אמרנו שכל s הוא p, שתי הקבוצות כוללות פרטים)
  • נזכור פה את העיקרון שלמדנו מסעיף 2, שמצדיק את הנחת הקיום - בקבוצה ריקה, כל טענה מסוג s הוא p היא נכונה! (עקרון ההתפוצצות קצת שונה ואומר שמהנחה שגויה אפשר לגזור כל מסקנה)

הוכחת טאוטולוגיה על מכלול הפשרים

• ניקח פסוק שהוא ללא ספק טאוטולוגיה: ∃x(Px∨¬Px)
• נניח שוב פשר μ
• בפשר μ, יש פריט כלשהו בתחום הדיון שמספק את הנוסחה
• בהינתן הנחת הקיום, אנחנו יכולים להגיד שקיים בפשר פריט a
• ואם קיים פריט a, הוא מספק כמובן את הנוסחה

• כשאנחנו עובדים עם הצבה של a ועם פשר "מדומיין" כזה - השיקולים נכונים עבור כל הפשרים! ולכן הוכחנו טאוטולוגיה, שהיא אמיתות על מכלול הפשרים

• באותו אופן ניתן להוכיח שקילות לוגית - לשים לב שצריך להראות את שני הכיוונים!

• אם לחדד: כשאנחנו יוצרים את μ ואת a, אנחנו מניחים שהם מספקים את מה שאנחנו מניחים שהם מספקים... למשל את ההנחות בטיעון, או את האמיתות של אחד משני פסוקים...
• יש גם את מה שאנחנו בודקים בהתאם להנחות: את המסקנה בטיעון תקף, או את הפסוק הנוסף בבדיקת שקילות....
• כלומר, אם רוצים להראות ש-Px ו-Bx שקולים לוגית, יש להראות שעבור μ ש-Px אמיתי בו, גם Bx בהכרח אמיתי (באמצעות שימוש ב-a)
• ואז להראות להיפך: שעבור μ ש-Bx אמיתי בו, גם Px יהיה אמיתי
• מיותר לציין (אבל החוברת מציינת) שאם הוכחנו שקילות על אמת/שקר, אין צורך להוכיח את האפשרות השניה (כי זה בינארי...)