תחשיב הפרדיקטים

בלוגיקה ובלוגיקה מתמטית, תחשיב פְרֶדִיקַטִים הוא מערכת פורמלית לטיפול בפסוקים הכוללים פרדיקטים (פרדיקט הוא נשוא, או תכונה, ובשפה המתמטית - יחס). בשפה מסדר ראשון חלים הפרדיקטים והמשתנים על אובייקטים בלבד. לעומת זאת בשפה מסדר שני פרדיקטים יכולים לחול גם על פרדיקטים אחרים וכמתים יכולים לחול גם על פרדיקטים.

הצרנה של פסוקים יסודיים

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

$Pa$

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

$Rab$

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

$\ \forall xPx$

וכך מובעת הטענה "יש דבר אחד לפחות שהוא חכם":

$\exists xPx$

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

סוקרטס הוא פילוסוף

יש לפחות פילוסוף אחד

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

$\ \forall x\exists yRxy$

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

תחביר של תחשיב הפרדיקטים

לכל שפה מותאם תחשיב משלה, בהתאם לסימני הקבועים, סימני המשתנים, סימני הפונקציות וסימני היחסים שלה.

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

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

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

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

תחום הדיון

D

הוא קבוצת האובייקטים {דני, רני, יוני}

השמות:

a

ו-

b

מייצגים את דני ורני בהתאמה

הפרדיקטים: הפרדיקט החד-מקומי "חכם" מצוין על ידי

P

, ומקבל ערך אמת עבור האובייקטים {דני, רני}

הפרדיקט הדו-מקומי "חבר של" מצוין על ידי R והקבוצה של האובייקטים המשויכת אליו היא הקבוצה המכילה את הזוג {<רני, יוני>}.

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

כעת ניתן להעריך את ערך האמת של הפסוקים הבאים בפירוש הנוכחי:

$\neg \forall xPx$

- מכיוון שבתחום הדיון שלנו לא לכל

x

הפרדיקט

P

מחזיר אמת, הפסוק אמיתי.

$\neg \exists xRxa$ או הפסוק השקול: $\forall x\neg Rxa$

- מכיוון שבתחום הדיון שלנו אין אף אובייקט

x

כך שבזוג יחד עם דני (

a

) הפרדיקט

R

מחזיר אמת, הפסוק אמיתי.

$\forall x(Px\to \exists yPy)$

- מכיוון שבתחום הדיון שלנו, עבור כל

x

ש-

P

חל עליו ניתן למצוא אובייקט

y

ש-

P

חל עליו, הפסוק אמיתי.

דוגמאות

כדוגמה נבחן את עשרת הפסוקים שניתן ליצור מן היחס "אוהב את" או לחלופין "נאהב על ידי", המקבל שני ארגומנטים, בצירופים שונים של שני הכמתים. כסמנטיקה נניח שמדובר בעולם בעל חמישה אובייקטים, $a,b,c,d,e$ , ונראה אילו פירושים שונים יכולים להינתן בעולם כזה עבור היחס "אוהב את", וכיצד הטענה המכומתת יכולה לבטא פירושים אלו.

אין אף טור ריק / אין אף שורה ריקה :
1. $\forall x\exists yLyx$ כל אחד נאהב על ידי מישהו.	2. $\forall x\exists yLxy$ כל אחד אוהב מישהו.

האלכסון אינו ריק / האלכסון מלא:
5. $\exists xLxx$ מישהו אוהב את עצמו.
6. $\forall xLxx$ כל אחד אוהב את עצמו.

התבנית אינה ריקה / התבנית מלאה:
7. $\exists x\exists yLxy$ מישהו אוהב מישהו 8. $\exists x\exists yLyx$ מישהו נאהב על ידי מישהו.
9. $\forall x\forall yLxy$ כל אחד אוהב כל אחד 10. $\forall x\forall yLyx$ כל אחד נאהב על ידי כל אחד.

שורה אחת מלאה / טור אחד מלא:
3. $\exists x\forall yLxy$ מישהו אוהב את כל אחד.	4. $\exists x\forall yLyx$ מישהו נאהב על ידי כולם.