תחשיב פסוקים

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

בלוגיקה ובלוגיקה מתמטית, תחשיב פסוקים (propositional calculus או sentential calculus) הוא מערכת המאפשרת לייצג את הקשרים בין ערכי האמת של פסוקים שונים. תחשיב הפסוקים אינו מתחשב בתוכן הפסוקים אלא במידה שיש להם ערכי אמת. תחשיב הפסוקים אינו עוסק, לפיכך, בשאלה כיצד נקבע ערך האמת של פסוקים אטומיים, אלא בשאלה כיצד נקבע ערך האמת של פסוקים מורכבים יותר, המורכבים ממספר פסוקים אטומיים באמצעות קַשַּרים לוגיים. ערך האמת של הפסוקים האטומיים יכול להיקבע על ידי הפירוש הסמנטי שאנו נותנים לאותיות הפסוקיות; אולם ניתן גם להשאיר אותו כמשתנה, ולבחון כך את כלל היחסים האפשריים בין הטענות המורכבות, עבור כל הצבה של ערכי אמת לאותיות הפסוקיות. באמצעות הכללה כזו ניתן לקבוע כי טיעונים הם תקפים, כאשר עבור כל הצבה של ערכי אמת לפסוקים האטומיים המרכיבים את ההנחות, אם הצבה כזו עושה את ההנחות של הטיעון לאמיתיות, היא גם עושה את המסקנה לאמיתית.


הצרנה[עריכת קוד מקור | עריכה]

הסמנטיקה של תחשיב הפסוקים מורה לנו כיצד עלינו להבין את היחס בין הסמלים המייצגים פסוקים שונים, ובין הטענות שהם מייצגים. כאשר אנו מעוניינים לנתח טיעון או הוכחה כלשהי באמצעות תחשיב הפסוקים, הצעד הראשון שעלינו לעשות מכונה הצרנה. בתהליך זה מסמנים כל משפט בסיסי (למשל 'השמש תזרח מחר' או 'יוסי גר בלונדון') בסימן קבוע (בדרך כלל אות אנגלית גדולה כמו P או Q, או הסימן Pi עם האינדקס i, המייצג מספר מסוים). סימן זה משמש לייצג את הטענה בכל מקום שתופיע בטיעון, והוא מכונה "פסוק יסודי", או "פסוק אטומי". גם הקָשַרים הלוגיים אינם נכתבים בתחשיב הפסוקים במלים אלא באמצעות סימונים מוסכמים.

תחביר[עריכת קוד מקור | עריכה]

תחשיב פסוקים מסוים כולל קבוצה של פסוקים יסודיים או "פסוקים אטומיים", ומספר קָשַרים לוגיים סטנדרטיים. לדוגמה, נגדיר ש P מייצג את הטענה "הגביע הוא שלנו", ו-Q מייצג את הטענה "אנחנו במפה"'. או אז ניתן להדגים את התחביר של חמשת הקשרים הלוגיים כך:

שלילה: \neg - זהו קשר אונרי, דהיינו הוא מקושר לאות פסוקית אחת בלבד. לדוגמה, \neg P מייצג את "הגביע הוא לא שלנו".
קוניוקציה ("וגם"): \land או & - קשר בינארי, מקשר בין שני פסוקים. לדוגמה, הפסוק המורכב P \land Q מייצג את הטענה "הגביע הוא שלנו ואנחנו במפה".
דיסיונקציה ("או"): \vee - קשר בינארי, מקשר בין שני פסוקים. לדוגמה, הפסוק המורכב P \vee Q מייצג את הטענה "הגביע הוא שלנו או אנחנו במפה".
תנאי ("אם-אז"): \to - קשר בינארי, מקשר בין שני פסוקים. לדוגמה, הפסוק המורכב P \to Q מייצג את הטענה "אם הגביע הוא שלנו אז אנחנו במפה".
תנאי כפול ("אם-ורק-אם"): \leftrightarrow - קשר בינארי, מקשר בין שני פסוקים. לדוגמה, הפסוק המורכב P \leftrightarrow Q מייצג את הטענה "הגביע הוא שלנו אם ורק אם אנחנו במפה".


באמצעות הקשרים, מאפשר התחביר ליצור רצפים סופיים של פסוקים יסודיים, קָשַרים וסימני סוגריים, שאפשר לקרוא אותו באופן חד-משמעי. רצף כזה נקרא נוסחה בנויה היטב (נקראת גם נוסחה בנויה כהלכה ובראשי תיבות נב"כ, (Well Formed Formula או WFF).
) נוסחה בנויה היטב מוגדרת בצורה הרקורסיבית הבאה:

  • אם P הוא פסוק אטומי, אז P הוא נוסחה בנויה היטב.
  • אם A היא נוסחה בנויה היטב, אז גם (\neg A) היא נוסחה בנויה היטב.
  • אם A ו-B נוסחאות בנויות היטב, אז לכל קשר \Omega כך ש \Omega \in \{ \to,\land,\vee,\leftrightarrow \}, הרי ש (A \Omega B) היא נוסחה בנויה היטב (דהיינו עבור כל שני פסוקים אטומים, הצבתו של אחד מן הקשרים הבינריים ביניהם יוצרת נוסחה בנויה היטב).
  • כל דבר אחר איננו נוסחה בנויה היטב.
  • רצפים חסרי מובן כמו (\to A \neg B) אינם פסוקים, ואינם עונים על ההגדרה הרקורסיבית.

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

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

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

אקסיומות וכללי היסק[עריכת קוד מקור | עריכה]

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

שלוש אקסיומות מן הצורה הבאה:

  1. (p \to (q \to p))
  2. ((p \to (q \to r)) \to ((p \to q) \to (p \to r)))
  3. ((\neg p \to \neg q) \to (q \to p))


כלל היסק אחד, מודוס פוננס, המוגדר כך:

מ-p
ומ- (p \to q)
הסק: q


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

a \lor b מוגדר כ- \neg a \to b
a \land b מוגדר כ- \neg(a \to \neg b)
a \leftrightarrow b מוגדר כ- \neg((a \to b) \to \neg (a \to b))


דוגמה להוכחה. ניתן להוכיח מהמערכת הזו בקלות ש a \to a, כך:


(1) (a\to((a\to a)\to a))\to ((a\to(a\to a))\to (a\to a))  

אקסיומה 2 בו הצבנו r=a, p=a ו q=(a\to a)

(2) a\to((a\to a)\to a)

אקסיומה 1 בו הצבנו q=(a\to a), p=a

(3) (a\to(a\to a))\to(a\to a)

מודוס פוננס על שורות 1 ו-2.

(4) a\to(a\to a)

אקסיומה 1 בו הצבנו p=a, q=a

(5) a\to a

מודוס פוננס על שורות 3 ו-4: מש"ל.

סמנטיקה[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – טבלת אמת

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


טבלת האמת של שלילה
 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


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




מערכות הוכחה[עריכת קוד מקור | עריכה]

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

\ P
\ Q

––––––––––––––––––––––––

\ P\rarr Q


והרי דוגמה לכלל הוצאה של הקשר של הקוניונקציה:

\ P \land Q

––––––––––––––––––––––––

\ P




ראו גם[עריכת קוד מקור | עריכה]