טבלת אמת

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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


טבלת האמת של שלילה
 P  \neg P
F T
T F
טבלת האמת של התנאי
 P  Q P \to Q
T T T
T F F
F T T
F F T
טבלת האמת של הקוניונקציה
 P  Q P \land Q
T T T
T F F
F T F
F F F
טבלת האמת של הדיסיונקציה
 P  Q P \vee Q
T T T
T F T
F T T
F F F
טבלת האמת של התנאי הכפול
 P  Q P \leftrightarrow Q
T T T
T F F
F T F
F F T




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


טבלאות אמת ככלי לבדיקת תקפות טיעונים[עריכת קוד מקור | עריכה]

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


  1. השמש זורחת וגם אם האגם קפוא הברווזים עפים
  2. אם השמש זורחת האגם אינו קפוא

מסקנה: הברווזים לא עפים


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

P: השמש זורחת
Q: האגם קפוא
R: הברווזים עפים


על פי ההצרנה, זהו הטיעון בו אנו דנים:

  1. P \and (Q \to R)
  2. P \to \neg Q

מסקנה: \neg R


והנה טבלת האמת של הטיעון:

 P  Q  R P \and (Q \to R) P \to \neg Q \neg R
1 T T T T F F
2 T T F F F T
3 T F T T T F
4 T F F T T T
5 F T T F T F
6 F T F F T T
7 F F T F T F
8 F F F F T T


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



טבלאות אמת לחישוב תוצאותיהם של ביטויים בוליאנים[עריכת קוד מקור | עריכה]

לשם חישוב תוצאותיהם של ביטויים באלגברה בוליאנית, ניתן להשתמש בטבלאות אמת בהן הערכים מיוצגים על ידי 0 ו-1. לדוגמה:

טבלת האמת של "And"
קלטים תוצאה
0 0 0
1 0 0
0 1 0
1 1 1
טבלת האמת של "Or"
קלטים תוצאה
0 0 0
1 0 1
0 1 1
1 1 1
טבלת האמת של "Xor"
קלטים תוצאה
0 0 0
1 0 1
0 1 1
1 1 0
טבלת האמת של "שקילות"
קלטים תוצאה
0 0 1
1 0 0
0 1 0
1 1 1
טבלת האמת של "Not"
קלט תוצאה
0 1
1 0



והרי דוגמה לטבלת אמת המראה תוצאה של ביטויים מורכב יותר:

טבלת האמת של (Not(A And B
קלטים A And B
Not(A And B)
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0