הדפסות 4 טבלאות אמת

בניית טבלאות גדולות

אם נתונים ערכי אמת (כמו בפרק 4 תרגיל א) - אין צורך לצייר טבלה שלמה! יש לכתוב טור אחד עבור הערכים הרלוונטיים... במצב כזה (שורה אחת בטבלה): לפצל את הטבלה לכמה שורות במחברת. זה קל וזה הרבה יותר שפוי...

בטבלה שלמה: אם יש שני משתנים - לנסות לדחוף בטבלה אחת; אם 3 או יותר (ויש איתם גם מס' ביטויים וכו') - עדיף לפצל את הטבלה ולמספר שורות...

לשים לב ממש טוב - לכל ערך אמת בטבלה...לבדוק פעמיים... ואם יש התניה והסיפה F, תמיד יש לנו T

בבדיקת שקילות: בונים טבלה אחת לכל הביטויים, לא צריך 2 בנפרד אלא אם הם בקושי חולקים משתנים. בכל אופן לדאוג שההצבה זהה (הראשון בטבלה הוא הראשון וכך הלאה) הביטוי האחרון הוא ꞵ↔α! לא מספיק להראות מציינים זהים או שונים, צריך להראות מציין עבור השקילות כפסוק (וכך נדע אם הכל T, כלומר יש שקילות, או לא.)

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

בצורה דיסיונקטיבית נורמלית: חשוב לזכור שמחברים כל "שורה" בטבלת האמת בדיסיונקציה ורק את ערכי האמת של האיברים בכל שורה בקוניונקציה (בסוגריים). עוד חשוב לזכור: לא ליצור שרשראות של a∧b∧c, בקורס שלנו זו טעות. יש לעשות (a∧(b∧c כשהמיקום של הסוגריים שרירותי...

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

כדי לוודא שהטבלה בנויה נכון (חשוב כשיש הרבה שורות):

1. נוודא שמס' השורות הוא 2^N
2. נוודא שעבור הפסוק האטומי הראשון, חצי מהמצבים הם T וחצי הם F (2^N\2)
3. נוודא שעבור הפסוק השני, בחצי מהמצבים שהראשון T השני F, ובחצי הנותר השני T; בחצי מהמצבים שהראשון F השני T, ובחצי הנותר השני F. (היגיון של Brute Force - כל הקומביצניות האפשריות). המשוואה תהיה שנרשום (2^N חלקי 2²) פעמים T ברצף ו-F ברצף לסירוגין (חוזר חלילה). (2 בחזקת 2 במחלק - הדרך שלנו "לחצות" את החלוקה - לאחר מכן זה יהיה בחזקת 3 או 4? לחשוב.)
4. בטור האחרון, נכתוב את T ואת F לסירוגין (2^N חלקי 2^N) פעמים (מס' השורות... ). מאחר שערך החלוקה הוא כמובן 1, למעשה נכתוב F ו-T פעם אחת בלבד ברצף, לסירוגין.

בניית טבלת אמת של פסוק

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

מציאת המציין, אפיון פסוק:

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

• כדי לאפיין פסוק, דרושים לנו:

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

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

הסדר הרשמי ליצירת טבלת אמת שלמה לפסוק:

1. ניצור טור 'קומבינטורי' של ערכי האמת של הפסוקים האטומיים
2. נחלק את הפסוק לתתי-פסוקים, בהתאם לסוגריים ולקשרי האמת, מהצרים ביותר ועד לפסוק השלם.
3. כעת נחשב את ערכי האמת של כל הפסוקים בהתאם לטבלאות האמת של הפונקציה שלהם. החוברת מציעה בחכמה לעבוד מהפסוק הצר לרחב, ולמלא את כל הטור לפני שממשיכים לאחד הבא.
4. לאחר שבנינו את טבלת האמת של הפסוק השלם, טור ערכי האמת של הקשר הראשי הוא המציין של הפסוק.
5. כשאנחנו עובדים עם פסוק שהוא שלילה (ꞵ?α)¬), אנחנו ניצור טבלה עבור הפסוק בצורתו החיובית, ולאחר מכן טור אחרון והופכי של הפסוק בצורתו הנתונה. זהו המציין...

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

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

בדיקת שקילות לוגית ותקפות בטבלות אמת

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

איך נבדוק שקילות בין פסוקים?**

1. או שנציב את הפסוקים בפונקציה של שקילות ↔ ונראה באמצעות טבלת האמת שהפונקציה טאוטולוגית
2. או שנכין טבלת אמת שבה לכל פסוק יש מציין משלו, ונראה שערכי האמת של המציינים זהים בכל שורה...

אז איך בודקים תקפות בתחתית השורה?

• די קל - בונים טבלת אמת עבור:
• כל האותית הפסוקיות בטיעון
• כל הביטויים המרכיבים את הטענות והמסקנה
• הטענות והמסקנה
• קוניונקציית ההנחות (הנחה א AND הנחה ב AND הנחה ג' וכו' - כפסוק אחד) - נסמן ב-α
• התניה שבה הקוניונקציה של ההנחות היא הרישה והמסקנה היא הסיפה - נסמן את המסקנה כ-ꞵ ונכתוב α→ꞵ
• עדיף לא ממש לכתוב את הקוניונקציה ואת ההתניה (מאוד ארוך) אלא לכתוב אלפה ובטא ואז למעלה או מתחת לכתוב מה המשמעות שלהם אפשר גם סתם לסמן שורה שבה כל ההנחות T - אם יש כזו שבה המסקנה F (אם אין - תקף)

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

צורה דיסיונקטיבית נורמלית

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

איך כותבים צורה דיסיונקטיבית נורמלית של טבלת אמת?

1. מסתכלים על השורות בהן המציין הוא T בלבד
2. מסתכלים על ערכי האמת של האותיות הפסוקיות בשורות אלה
3. עבור כל שורה, יוצרים פסוק שהוא קוניונקציה של כל האותיות שערך האמת שלהן הוא T, ושל שלילת כל האותיות שערך האמת שלהן הוא F.
   (לצורך העניין: אם p היא T ו-q היא F, כותבים (p∧¬q).
4. מחברים את הפסוקים שהתקבלו בכל אחת מן השורות (של מציין = T) בקשר של דיסיונקציה.

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

6. צורה דיסיונקטיבית נורמלית היא ביטוי של טבלת האמת באמצעות קשרי האמת, כלומר באמצעות בניית נב"ך מתאים

7. לפעמים, יש לנו רק שורה אחת עם T במציין. אז, הדיסיונקציה הנורמלית תהיה למעשה קוניונקציה נורמלית, בהיעדר סימן דיסיונקציה בפסוק... זה עדיין נקרא צורה דיסיונקטיבית במצב כזה...*
8. יש מקרה אחד של טבלת אמת שאי אפשר להפעיל עליו את השיטה הזו... נלמד בהמשך

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

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

10. כאן נכנס לתמונה הכלל שלמדנו, שלפיו לא צריך סוגריים בין דיסיונקציה, קוניונקציה ושקילות מטריאלית.

11. אם נתונה שורה שבה p=T, q=T, q=T, ניצור פסוק קוניונקציה כזה: (p∧q∧r).
    • עבור שורה נוספת שבה r=F, נכתוב ככה: (p∧q∧¬r).
    • וכמובן, נחבר את הפסוקים לכדי הצורה הדיסיונקטיבית הנורמלית (נניח לצורך העניין שיש רק שתי שורות בטבלת האמת - זה לא יתכן כמובן:) (p∧q∧¬r)∨(p∧q∧r)
12. המשמעות היא שניתן לבטא כל טבלת אמת באמצעות AND, OR ו-NOT בלבד. למערכת קשרים שיכולה לבטא כל טבלת אמת קוראים מערכת קשרים שלמה, או מערכת קשרים בעלת שלמות פונקציונלית.
13. כמובן שאם כך, גם המערכת שאנו לומדים שכוללת בנוסף את IFF ואת IMPLIES היא מערכת בעלת שלמות פונקציונלית.
14. בהמשך נכיר מערכות שלמות שבנויות רק משני קשרים, ואת קשרי שפר שכל אחד מהם הוא שלם בפני עצמו.

קבוצת קשרים שלמה:

• המשמעות של העובדה ש-AND, OR ו-NOT הם קבוצת קשרים שלמה, היא שניתן לבטא כל קשר לוגי אחר (נניח, IMPLIES) באמצעות הקשרים האלה בלבד, כך שהמציין יהיה זהה.
• ושוב, קבוצת קשרים שלמה לעולם לא תאבד את מעמדה ככזו בעקבות הוספה של קשרים - כמובן. (אז גם הקבוצה שכוללת IMPLIES ו-IFF היא שלמה...)
• כעת נוכיח שגם הקבוצה של {AND, NOT} היא קבוצת קשרים שלמה. מאחר שהוכחנו את שלמות הקבוצה AND, NOT ו-OR - אנחנו רק צריכים להראות שניתן לבטא את OR באמצעות AND+NOT!
• ¬(¬p∧¬q) שקול לוגית ל (p∨q)
  • לא באמת דרושה טבלת אמת כדי להבין: להגיד "או P או Q" זה כמו להגיד "לא יהיה מצב שגם לא P וגם לא Q".
  • אפשר לבטא אימפליקציה בין הפסוקים הללו כ- (p∧¬q)¬
  • ¬(p∧¬q)∧¬(¬p∧q) ואפשר לבטא שקילות כ
  • כמובן שלא באמת היינו צריכים להראות את IMPLIES ואת IFF, כי בהינתן שאפשר לבטא את OR באמצעות AND+NOT, הרי כבר הוכחנו שאפשר לבטא את IMPLIES ואת IFF באמצעות הקבוצה של AND+NOT+OR.
• בפרק 6 נלמד את חוקי החילוף הלוגיים, שהם ממש מתודה להעמדה של קשרים על קבוצות שהם לא נכללים בהן. בינתיים, אנחנו עובדים לפי האינטואיציה ובהסתמך על טור המציין בטבלאות האמת.
• אם נניח יש פונקציה מורכבת שכוללת את P, והיא T רק במצב אחד שבו P אמיתי, אפשר להמיר פשוט ל-"P". העיקר שהפונקציות שקולות לוגית ברמת המציין בטבלת האמת.

שלבים בהמרה למערכת קשרים אחרת:

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

קו שפר:

• עוד ב-1880, הפילוסוף האמריקאי צ'ארלס סאנדרס פירס כתב שמעניינת אותו האפשרות שישנו קשר לוגי יחיד שהוא שלם פונקציונלית.
• הקשר שהוא חשב עליו הוא, בשפה הטבעית, "לא... ולא.." (דו מקומי)
• ב-1913 פרסם המתמטיקאי הנרי מ' שפר את הפורמליזציה, שזכתה לשם 'קו שפר'.
• קו שפר מסומן כך α|ꞵ, והפונקציה שלו מחזירה ערך אמת T אך ורק כששני הפסוקים הם F.
• איך מבטאים שלילה וקוניונקציה באמצעות קו שפר? שלילה: α|α קוניונקציה: (α|α)|(ꞵ|ꞵ) ("לא (השלילה של α) ולא (השלילה של ꞵ)" למעשה שקול ללהגיד "α וגם ꞵ".
  • זה בעצם די משעשע, הקשר שהוא חשב עליו הוא שילוב של קוניונקציה ושלילה. ב-"לא... ולא..." יש גם "לא" וגם "ו-"...
• החוברת מאשרת, אפשר להפוך כל קשר דו מקומי לחד מקומי על ידי כך שנציב את אותו הפסוק משני הצדדים שלו...
• הוכחנו כבר ש-AND+NOT היא קבוצה שלמה פונקציונלית, אז בכך שהעמדנו את שניהם על קו שפר, הוכחנו שהוא שלם פונקציונלית.
• שאלה למחשבה מהחוברת: אם את כל הפונקציות שאנחנו לומדים, ניתן לבטא באמצעות קו שפר בלבד, למה אנחנו טורחים עם כל היתר?
  • התשובה שלי היא כמובן שזה קריא יותר, זו אותה סיבה שיש לנו מילים שניתן להגדיר באמצעות מילים אחרות.
  • החוברת מוסיפה: אם ככה, למה לא 20 קשרים? התשובה היא כמובן שזה מסורבל - איך נזכור את טבלאות האמת?
  • ולמה דווקא החמישה שאנו לומדים? כי הם הרווחים ביותר בשפה הטבעית.