לוגיקה מתמטית

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

השיטה של הלוגיקה המתמטית לניתוח טענות היא כדלהלן:

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

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

1. $A\rightarrow B$
2. $B\rightarrow C$

כאשר A משמעותו "אני שבע", B משמעותו "אני מאושר" ו-C משמעותו "אני פוצח בשיר" ואילו החץ ($\rightarrow$) משמעותו היא שאמיתות הטענה בצד שמאל של החץ תגרור את אמיתות הטענה בצד ימין של החץ. כלומר, 1 פירושו "אם אני שבע אז אני מאושר" ו-2 פירושו "אם אני מאושר אז אני פוצח בשיר".

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

$A\rightarrow C$

ומכאן אנחנו מסיקים שהטענה "כשאני שבע אני פוצח בשיר" נכונה.

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

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

ראו גם

• תחשיב פסוקים

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

• סטיבן בילאניוק, A Problem Course in Mathematical Logic, אוניברסיטת טרנט, קנדה.
• בועז צבאן, מבוא ללוגיקה מתמטית, המחלקה למתמטיקה, אוניברסיטת בר-אילן, הספר מכיל רקע ותרגילים לנושא תחשיב הפסוקים ולוגיקה מסדר ראשון. נכתב במקור על פי מערכי שיעורים של פרופסור חיים יהודה.
• Metamath Proof Explorer: מאגר של משפטים מתמטיים עם הוכחות מלאות בעזרת לוגיקה מתמטית.