8 סמנטיקה של תחשיב הפרדיקטים

[[לוגיקה]]

ערך אמת בפשר - פסוקים פשוטים

סמנטיקה של שפה לוגית

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

---

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

קבוצות:

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

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

• {a, b, c} היא הקבוצה הכוללת את a, b, c
  • אין משמעות לסדר ההופעה: ל-{b, c, a} משמעות זהה
• ניתן לציין תכונה שהיא תנאי מספיק והכרחי לשייכות לקבוצה. למשל: {כל האותיות שהמיקום שלהן ב-abc הוא בין 1 ל-3 מההתחלה} היא למעשה קבוצה שזהה ל-`{a, b, c}

פשר:

• פשר כולל תחום דיון (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, וכן הלאה...
• 1. אם פסוק הוא מהצורה α¬, הוא אמיתי בפשר נתון אם ורק אם α שקרי לפי אותו הפשר
  2. הפסוק α∧ꞵ אמיתי בפשר אך ורק אם גם α וגם ꞵ אמיתיים (כמו בפונקציה)
  3. הפסוק α∨ꞵ אמיתי בפשר אך ורק אם α או ꞵ אמיתיים (כמו בפונקציה)
  4. הפסוק α→ꞵ אמיתי בפשר רק אם α שקרי או ש-ꞵ אמיתי (כמו בפונקציה)
  5. הפסוק α↔ꞵ אמיתי בפשר אם לשני הפסוקים אותו ערך אמת (כמו בפונקציה)

[[8 - סמנטיקה של תחשיב הפרדיקטים#כללים לתנאי האמת המשך (כמתים)#|המשך לזה]]

• **דוגמה נוספת: **

• נעבוד עם פשר זה: ![[Pasted image 20250111192330.png]]

• הפסוק Raa אמיתי

• גם Qb¬ אמיתי
• הפסוק Pc∧Rac שקרי מכיוון ש-Pc שקרי

"לספק נוסחה"

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

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

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

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

---

• עוד דוגמה:

![[Pasted image 20250111194126.png]]

• מה הוא ערך האמת של (x(Px∧Sx∃?
• אמת, כי קיים פריט בתחום הדיון ("יוסי", ו-"קארול") שיכול להפוך את Px∧Sx לאמת אם להחליף אותו במשתנים החופשיים של Φ
• שוב: "קארול" מספקת את הנוסחה כי אם היה משתנה רק עבורה, שנקרא לו a, והיינו מחליפים את ה-xים ב-a, הנוסחה Pa∧Sa הייתה אמת

לא הבנתי מה הזיון מוח על משתנים חופשיים... המשתנה x קשור בדוגמה הזו?

[[תרגילים - פרק 8 🏋️#תרגיל |(תרגיל א)]]

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

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

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

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

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

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

• הפסוק x∃yRxy∃ אמיתי רק אם יש פריט מתחום הדיון המספק את הפסוק yRxy∃

• נבדוק את הפריט a: הפריט a מספק את הנוסחה yRxy∃ אם ורק אם yRay∃ (הפסוק עם הצבה של a) הוא אמיתי בפשר
• הפסוק yRay∃ אמיתי בפשר אם ורק אם יש משתנה בתחום הדיון שמספק את הנוסחה החדשה שנוצרה: Ray
• הפריט b הוא בתחום הדיון ויכול להיות Rab לפי הפשר, אז yRay∃ אמיתי בפשר
• לכן הפריט a מספק את הנוסחה yRay∃
• ולכן x∃yRxy∃ אמיתי בפשר

לשים לב שאנחנו מתחילים מ-"להחליף" את x, ואז בודקים אם יש החלפה אפשרית ל-y

• את התשובה יש לכתוב ככה, אבל הפוך (כאן זה מהסוף להתחלה, ועבור פסוק אחר אבל אותו הפשר ): ![[Pasted image 20250111204855.png]]

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

![[Pasted image 20250111205054.png]]

[[תרגילים - פרק 8 🏋️#תרגיל ב#|(תרגיל ב)]]

הוכחות סמנטיות ע"י פשר מתאים

תקפות

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

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

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

• דוגמה להפרכת תקפות באמצעות פשר: ![[Pasted image 20250112155154.png]]

• לא לשכוח שיש [[8 - סמנטיקה של תחשיב הפרדיקטים#פשר#|כללים לפשר]]

• אין מתודה - פשוט צריך לנסות למצוא פשר שלא מתאים...

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

• עוד דוגמה לאופן המחשבה ![[Pasted image 20250112155445.png]]

![[Pasted image 20250112155518.png]]

[[תרגילים - פרק 8 🏋️#תרגיל ג#|תרגיל ג]]

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

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

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

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

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

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

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

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

[[תרגילים - פרק 8 🏋️#תרגיל ד#|תרגיל ד]]

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

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

[[תרגילים - פרק 8 🏋️#תרגיל ה#|תרגיל ה]]

שקילות לוגית

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

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

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

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

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

• לשאלת השקילות יש משמעות בהצרנות:

![[Pasted image 20250113171528.png]]

• הפשר הבא מוכיח שהפסוקים אינם שקולים לוגית: Domain: {a, b} I(P) = {a} I(Q) = {} I(a) = a

• 1 יהיה שקרי בעוד ש-2 אמיתי

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

[[תרגילים - פרק 8 🏋️#תרגיל ו|תרגיל ו]]

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

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

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

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

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

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

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

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

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

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

[[תרגילים - פרק 8 🏋️#תרגיל ז#|תרגיל ז']]