תחשיב הפרדיקטים – הבדלי גרסאות

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


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

גרסה מ־00:18, 13 באוגוסט 2019

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

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

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

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

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

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

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

סוקרטס הוא פילוסוף
יש לפחות פילוסוף אחד

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

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

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

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

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

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

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

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

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

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

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

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


דוגמאות

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

אין אף טור ריק / אין אף שורה ריקה :
1.
כל אחד נאהב על ידי מישהו.
2.
כל אחד אוהב מישהו.
האלכסון אינו ריק / האלכסון מלא:
5.
מישהו אוהב את עצמו.
6.
כל אחד אוהב את עצמו.
התבנית אינה ריקה / התבנית מלאה:
7.
מישהו אוהב מישהו

8.
מישהו נאהב על ידי מישהו.
9.
כל אחד אוהב כל אחד

10.
כל אחד נאהב על ידי כל אחד.
דיאגרמת הסה (Hasse) של יחסי הנביעה בין הפסוקים: כל מטריצה מייצגת פסוק הנובע מאלו שמתחתיו
שורה אחת מלאה / טור אחד מלא:
3.
מישהו אוהב את כל אחד.
4.
מישהו נאהב על ידי כולם.

ראו גם

קישורים חיצוניים

ויקישיתוף מדיה וקבצים בנושא תחשיב הפרדיקטים בוויקישיתוף