הוכחה
ערך זה עוסק במונח המתמטי והלוגי. אם התכוונתם למשמעות אחרת, ראו הוכחה (פירושונים).
במתמטיקה ובלוגיקה הוכחה היא סדרה סופית של טענות הנובעות זו מזו בעזרת כללי היסק, תוך שימוש בהגדרות, באקסיומות, ובידע קודם שהוכח קודם לכן, המראה שטענה מסוימת היא נכונה.
הפרכה של טענה מהווה גם היא הוכחה - הוכחה שטענה זו אינה נכונה (כלומר ששלילתה של הטענה היא נכונה). טענה שטרם זכתה להוכחה קרויה השערה, וטענה שזכתה להוכחה קרויה משפט או תאורמה.
תפקידה המתמטי של ההוכחה הוא להפוך רעיונות והשערות לדרך סלולה, שממנה אפשר להתקדם לרעיונות חדשים. על המבנה הטיפוסי של הוכחה מורכבת כתב הרמן וייל: "הוכחה מודרנית במתמטיקה דומה למכונה מודרנית: הרעיונות הפשוטים, המרכזיים, חבויים וכמעט אינם נראים תחת גודש הפרטים הטכניים".
תוכן עניינים |
[עריכה] מאפיינים של הוכחות
הוכחה משתמשת בכללים להסקת מסקנות, אך יש בה גם שימוש נרחב בשפה טבעית, ולכן עלולה להיות בה עמימות הנובעת מעמימותה של השפה. כדי להימנע מעמימות זו ניתן להשתמש בהוכחה פורמלית.
להוכחה משמשות טכניקות אחדות:
- הוכחה ישירה, שבה המסקנה נובעת ישירות מההגדרות, מהאקסיומות וממשפטים קודמים. דוגמה להוכחה כזו היא ההוכחה שסכומם של שני מספרים זוגיים יהיה גם זוגי.
- הוכחה באינדוקציה: תחילה בודקים את נכונות הטענה למקרה מסוים, ומכאן ממשיכים להוכחתה לקבוצה אינסופית של מקרים. דוגמה להוכחה כזו היא הוכחת הנוסחה למציאת סכום של סדרה חשבונית.
- הוכחה בדרך השלילה: מניחים שהטענה שיש להוכיח אינה נכונה, ומראים שהנחה זו מובילה לסתירה. דוגמה להוכחה כזו היא הוכחתו של אוקלידס בדבר קיום מספר אינסופי של מספרים ראשוניים.
- הוכחה בדרך טרנספוזיציה.
- הוכחה על ידי בניה, היא הוכחה על ידי בניית דוגמה ספציפית, לדוגמה, כך הוכח קיומם של מספרים טרנסצנדנטיים.
- הוכחה בכוח גס.
ניתן להבדיל בין שני סוגים של הוכחות:
- הוכחת קיום: הוכחה שמראה את קיומו של עצם מסוים, בלי להראות כיצד ליצור עצם זה.
- הוכחה קונסטרוקטיבית: הוכחה שמראה כיצד ליצור עצם בעל תכונה מסוימת.
משפט ארבעת הצבעים, שהוכח בשנת 1976, היה המשפט הראשון שלהוכחתו נדרשה הסתייעות מהותית במחשב. עובדה זו עוררה פולמוס בין המתמטיקאים סביב השאלה האם הוכחה כזו, שאדם אינו יכול לבדוק אותה בכוחות עצמו, יכולה להיחשב כהוכחה מתמטית תקפה.
פעמים רבות ניתן להוכיח טענה מסוימת בדרכים שונות, ולעתים אף דרכים רבות למדי. משפט פיתגורס נודע בעשרות הוכחות שניתנו לו. למשפט הקובע שהמספרים הרציונליים הם קבוצה בת מניה מופיעות בוויקיפדיה העברית שלוש הוכחות שונות, בערכים: קבוצה בת מנייה, מספר רציונלי ועוצמה.
נהוג לחתום הוכחות על ידי סימון מוסכם: בעברית מש"ל, באנגלית .Q.E.D, ולעתים על ידי ציור של ריבוע ריק או מלא (∎).
[עריכה] השערה
טענות לא מעטות דרשו מאות רבות של שנים עד להוכחתן או להפרכתן. דוגמאות לכך הן המשפט האחרון של פרמה שזכה להוכחה כשלוש מאות וחמישים שנה לאחר שהועלה, ושלוש הבעיות של ימי קדם, שהוכחו כבלתי נתנות לפתרון כאלפיים שנה לאחר שהוצגו. בעיות פתוחות (כאלה שטרם זכו להוכחה או להפרכה) רבות ממשיכות ללוות את המתמטיקה, ובין המפורסמות שבהן ניתן למנות את השערת גולדבך והשערת רימן.
האם כל השערה ניתנת להוכחה או להפרכה? ברור שהאקסיומות אינן ניתנות להוכחה ואף לא להפרכה. אם נוכיח שהשערה מסוימת אינה ניתנת להוכחה ואף לא להפרכה, כפי שהוכח לגבי השערת הרצף, נוכל לצרף את ההשערה הזו (או את שלילתה) לאוסף האקסיומות שלנו. האם בדרך זו נוכל להרחיב את אוסף האקסיומות, כך שנגיע למצב שבו כל טענה תהיה ניתנת להוכחה או להפרכה? תשובה לשאלה זו ניתנה בשנת 1931 במסגרת משפט אי השלמות של גדל: במתמטיקה (ולמעשה בכל דיסציפלינה עקבית - שהנחותיה ניתנות לזיהוי מכני ("אפקטיבי") - ושמניחה את האריתמטיקה של החיבור ושל הכפל), תמיד תהיינה השערות אשר מחד גיסא ניתנות לניסוח בשפתה של הדיסציפלינה, ואשר מאידך גיסא אינן ניתנות להוכחה ואף לא להפרכה במסגרת אותה דיסציפלינה.
לעומת זאת, תחשיב הפסוקים - המהוה את הבסיס של הלוגיקה המתמטית - הוא שלם, ולכן לא יהיו בו מקרים כאלו. קיימים ענפים נוספים - כוללניים יותר - שהינם שלמים (במובן זה), למשל האריתמטיקה של החיבור (ללא הכפל).
[עריכה] ראו גם
[עריכה] קישורים חיצוניים
- מרכוס דה סוטוי, חובת ההוכחה, באתר ynet (תיקוני טעויות מופיעים בטוקבק)
