כלל היסק

כְּלָלֵי הֶסֵּק (באנגלית: Inference rules, או Rules of inference) הם הכללים הבסיסיים ביותר בלוגיקה ובמתמטיקה, הקובעים מתי מותר לעבור מטענה אחת לטענה אחרת, כלומר להסיק או להוכיח אותה.

כללי ההיסק הנפוצים ביותר

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

1. כל הברווזים הם עופות.
2. כל העופות הם בעלי כנף.

לכן: כל הברווזים הם בעלי כנף.

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

1. אם הברווזים עפים אז האגם קפוא.
2. הברווזים עפים,

לכן: האגם קפוא.

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

${\begin{array}{rl}(1)&P\to Q\\(2)&P\\\hline \therefore &Q\end{array}}$

לעיתים מצוין היסק כזה באמצעות הסימן $\vdash$, כך:

$\{P\to Q,P\}\vdash Q$

כלל היסק נפוץ נוסף הוא מודוס טולנס:

$\{P\to Q,\neg Q\}\vdash \neg P$

וכן מקובל לקבל את הקונטרה פוזיטיב ככלל היסק:

$\{P\to Q\}\vdash (\neg Q\to \neg P)$

תחביר וסמנטיקה

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

כללי היסק מול אקסיומות

יש להבחין הבחנה חדה בין כללי ההיסק ובין האקסיומות. אקסיומות הן טענות אמיתיות, המשמשות כבסיס לכל היסק במערכת. ואולם כללי ההיסק אינם חלק מן המערכת: הם כללים אודות המערכת, המאפשרים לנו לייצר היסק תקף או להבחין בין היסק תקף ושאינו תקף. משום כך, אין לראות בסימן $\vdash$ קשר לוגי, ואת הייצוג של הטיעון, $\{P\to Q,P\}\vdash Q$ אין לראות כמשפט מתוך השפה שאנו מתארים, אלא כתיאור של קשר בין שלושה משפטים מתוך השפה. אילו היינו מנסים לתפוס את כלל ההיסק כאקסיומה, היינו נגררים לרגרסיה האינסופית אותה מתאר לואיס קרול במאמרו הידוע, מה שהצב אמר לאכילס.

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

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

דוגמה לכלל הכנסה (אינטרודוקציה) להקשר של פסוק התנאי:

${\begin{array}{rl}(1)&P\\(2)&Q\\\hline \therefore &P\to Q\end{array}}$

דוגמה לכלל הוצאה (אלימינציה) להקשר של פסוק ההלחם (הקוניונקציה):

${\begin{array}{rl}(1)&P\land Q\\\hline \therefore &P\end{array}}$

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

ראו גם

• מה שהצב אמר לאכילס
• מודוס פוננס
• מודוס טולנס

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

• כלל היסק, באתר MathWorld (באנגלית)