5 עצי אמת

[לוגיקה]

הקדמה

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

המבנה של עצי אמת

• עץ אמת בנוי כמו עץ הפוך, או כמו אילן יוחסין (הענפים יוצאים מלמעלה ומסתעפים כלפי מטה) ![[Pasted image 20241129203934.png]]

• נמקם פסוקים בשורש, בצמתים ובקצוות:

• בקצוות נמקם רק אותיות פסוקיות או אותיות פסוקיות שלולות (α או ¬α). זה בגלל ששורש וצומת הם סוג מיוחד של קצה: יתכן גם שורש שהוא קצה... כשאין הסתעפות.
• בשורש נמקם את הפסוק שאנחנו רוצים לבדוק.
• בצומת נקבל בכל פעם תוצאה של הפעלת כלל מסוים על הפסוק שמעליו, או אף באותו הצומת (?)
• ה-'מסלול' בין השורש לקצה מסוים מכונה ענף בעץ
• הכללים קובעים איך אנחנו 'מפרקים' פסוק מצורתו השלמה עד למרכיבים הבסיסיים שלו (בקצוות): המרכיבים הם או פסוקים אטומים או פסוקים אטומיים שלולים

ענפים סגורים ופותחים:

• בכל פעם שנבנה ענף בעץ האמת, נבדוק אם הוא כולל גם מופע של אות פסוקית וגם מופע של השלילה שלה. (לצורך העניין, אנחנו מחפשים לראות באחת מקצות הענף, גם אם הם צמתים או שורש, את p ואת ¬p).
• אם מצאנו את שני המופעים, אנו מסמנים מתחת לענף 'X', וענף זה מכונה "סגור".
• אם לא מצאנו - לא מסמנים דבר, והענף מכונה "פתוח"
• לאחר סימון כל הענפים ניתן לקבוע האם מדובר בעץ סגור או פתוח: רק עץ שכל הענפים שלו סגורים הוא סגור, במקרה אחר הוא פתוח. (תרגיל א)

כללי פירוק הפסוקים:

• ישנם 9 חוקים לפירוק הפסוקים על מנת "להתקדם" בענפים.
  • כללי הפירוק חלים על הקשר הלוגי הראשי בפסוק. לכן יש 4 בסיסיים, 1 לכל קשר דו-מקומי.
  • במקרה שסימן הקשר הראשי הוא שלילה, יש 4 חוקים נוספים שמתחלקים לפי סימן הקשר המשני (בקיצור, עדיין מאפיינים לפי 4 פונקציות האמת הדו-מקומיות, פשוט כקשר המשני כאשר שלילה היא הראשי).
  • יש עוד כלל אחד למקרה של שלילה כפולה.
  • בסך הכל - 9 כללי פירוק.
• הבחנה שלי: נראה שהפירוק אמור "לחלץ" מתוך הפסוק את האפשרויות שהוא יהיה T: אם יש שתי אפשרויות סותרות, יש לנו צומת. אם יש שתי אפשרויות שהן חלק מאותו מצב עניינים, יש מס' פסוקים על אותו קצה.
  • כלומר, כל אות שנכתבת בעץ האמת ככל הנראה מתייחסת למצב שבו היא T.
  • למשל: a∧b מפורק לקצה אחד של a ו-b, כי רק במצב ששניהם נכונים הפסוק נכון.
  • לפי אותו היגיון, a→b מתפרק לa¬ או b. כי או שb נכון ולכן גם a, או ש-a לא נכון ולא משנה לנו מה עם b (הפיצול שלא קיים הוא b¬, כי אם הוא לא נכלל בa¬ השורה היא F.) ![[Pasted image 20241129210943.png]]

אופן הפירוק:

1. לאחר שביצענו את הכלל, נמשיך לפרק את כל מה שנמצא על הצומת שהוא לא אות פסוקית.
2. כל פירוק שאינו מפצל את הענף, נכתב כשורה נוספת על הצומת הקיימת
3. פירוק שמפצל את הענף פותח פיצול חדש.

   מה עושים כשיש באותה צומת כמה כאלה? נבצע את כל הפעולות שלא מפצלות את הענף, ורק לאחריהן את אלה שדורשות פיצול שלו!

4. ברגע שהתהווה ענף סגור, אנחנו מסמנים X, והמשמעות היא שלא נפעיל יותר כללי פירוק על הענף.
5. עץ סגור כידוע הוא כזה שכל הענפים בו סגורים. זה אומר שהמלאכה הסתיימה, ועוד דברים שנגלה בהמשך.
6. אפשר להגיע לסוף גם בלי שהענפים יסגרו! ברגע שהגענו לאות פסוקית/שלולה, אין איך לפרק יותר. ייתכן שנראה את p ואת p¬ על העץ, אך לא באותו ענף. או שלא נראה אחת מהן.

כללי הפירוק של קוניונקציה (ראשי או משני):

• הכלל קובע שהקיוניונקטים בפסוק יכתבו תחת אותה הצומת, בשתי שורות נפרדות. α∧ꞵ | α ꞵ
• כקשר משני לשלילה, הכלל קובע שנפצל את השורש לשני צמתים, כאשר כל צומת הוא השלילה של אחד הקוניונקטים: ¬(α∧ꞵ) left: ¬α right: ¬ꞵ

זה מחזק לי כמובן את ההבנה שהפיצול הוא שני מצבים אקסלוסיביים. כדי ש-"לא (a ו-b)" יהיה נכון, צריך ש ¬α או ¬ꞵ יהיו נכונים.

כללי הפירוק של דיסיונקציה (ראשי או משני:)

• כקשר ראשי: טוב, זה די קל, פותחים פיצול, וכל דיסיונקט הוא צומת/קצה חדש.ה
• כקשר משני לשלילה: תחת אותו הענף (בלי לפצל), כותבים את השלילה של כל אחד מדיסיונקטים.
  • ¬(ꞵ∨α) | ¬ꞵ ¬α
• לשים לב ❗ יכול להיות פסוק כמו (ꞵ∨¬α)¬. במצב כזה, אנחנו מקבלים ענף שיושבים עליו ꞵ¬ ו- ᬬ. (למעשה, מקבלים α...)

בגדול האמירה פה היא "לא (לפחות a או b)", שזה כמו להגיד "לא a ולא b", לכן השלילה של כל אחד מהם נמצאת על אותו ענף, כלומר, שייכת לאותו מצב שבו הפסוק הוא T.

כללי הפירוק של אימפליקציה מטריאלית (ראשי או משני):

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

כקשר משני זה אמור בעצם להיות T רק כשהרישה אמת והסיפה שקר. לדעתי, לא מפצלים, וכותבים באותה הצומת את הרישה ואת השלילה של הסיפה. (צדקתי)

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

כללי הפירוק של שקילות מטריאלית (ראשי או משני):

• כקשר ראשי: נפצל את הענף לשני צמתים, בכל אחד שתי שורות: ענף 1 יכלול את הרישה ואת הסיפה, ענף 2 יכלול את השלילה של הרישה ואת השלילה של הסיפה.

  • α↔ꞵ ^ α ¬α
    ꞵ ¬ꞵ

• כקשר משני לשלילה: אותו דבר רק שבצד אחד של הפיצול יש לנו את α ואת ꞵ¬, ובצד השני את α¬ ואת ꞵ.

  ניחוש: המשמעות היא שהפסוק T רק כשהערכים שונים. לדעתי זה אותו דבר רק שבצד אחד של הפיצול יש לנו את α ואת ꞵ¬, ובצד השני את α¬ ואת ꞵ. צדקתי

כללי הפירוק של שלילה כפולה:

• ראינו כבר שהרבה מכללי הפירוק כוללים הוספה של ¬, כאשר לפסוקים רבים יש כבר ¬ בהתחלה, כך שמתקבלת שלילה כפולה: ¬¬
• מתבקש לתרגם את ᬬ ל-α מבלי להמתין, אבל מדובר בכלל פירוק ויש לבטא אותו בכתב.
• הכלל קובע שנפרק את הסימן לאותו הסימן ללא השלילות, בשורה חדשה, מבלי לפצל את הענף
• חשוב מאוד ❗ - לשים לב שאנחנו עושים את זה רק כשהשלילות הן הקשר הראשי והמשני בפסוק. p∧q¬¬ הוא לא פסוק שניתן להחיל עליו את הכלל, כי הקשר הראשי הוא קוניונקציה ולא שלילה.
  • בהמשך לזה, אם השלילות הן כן הקשרים הראשי והמשני, אפשר להפעיל את הכלל גם כשישנם קשרים נוספים: כך, P¬¬¬ הופך לP¬¬ ¬¬¬¬P הופך ל- ¬¬P וכו'

• גם החוברת מדגישה: **לכתוב את כל השלבים! בלי קיצורי דרך. **

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

• לשאלה שמטרידה אותי מההתחלה: מה קורה, במצב כזה, אם אנחנו צריכים לפצל את אותה הצומת פעמיים? בדרכים שונות?
• התשובה היא שאנחנו מפרקים את הפסוק בכל ענף פתוח (שנמצא כבר מתחת לפסוק) בנפרד ![[Pasted image 20241129220621.png]]

☝ **זה מצב שיכול לקרות גם כשיש פסוק אחד! ככה שאין באמת הבדל, וצריך לדעת לעשות את זה.

(תרגיל ב)

graph TD;
id1("¬(α∧ꞵ)"
ꞵ
ꞵ
ꞵ
ꞵ
) --> id2(¬α);
id1("¬(α∧ꞵ)"
ꞵ
ꞵ
ꞵ
ꞵ
) --> id3(¬ꞵ);

הסבר על עצי אמת:

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

מה בודקת השיטה?

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

אפיון פסוקים בעצי אמת

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

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

  • אם α הוא טאוטולוגיה, העץ של α¬ חייב להיות סגור (כי אין מצב שבו הפסוק F, כלומר אין מצב שהשלילה שלו T)
  • לכן, כדי לאפיין את פסוק α, נתחיל מלבנות לו עץ רגיל:
    • אם העץ סגור, הפסוק הוא סתירה עצמית
    • אם העץ פתוח, נבנה עץ ל-α¬:
    • אם העץ פתוח, הפסוק הוא קונטינגנציה
    • אם העץ סגור, הפסוק הוא טאוטולוגיה

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

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

![[Pasted image 20241205194018.png]]

• 'אם"ם' זה 'iff' באנגלית - 'אם ורק אם'

(תרגיל ד)

בדיקת תקפות בעצי אמת

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

(תרגיל ה)