תוספות
cover image

חדו"א 1
יד ביד

כללי היסק (Rule of inference)

כללי היסק, כשמם כן הם, הם בראש ובראשונה כללים שמתארים היסק. היסק כמו להסיק מסקנות.

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

הכלל

אני אנסח אותו קודם בצורתו הכללית ואז נקח קצת דוגמאות:

אם xx היא טענה נכונה (מורכבת, פשוטה, מה שתרצו רק שתהיה נכונה), וגם (אם xx אז yy) נכונה – אז הטענה yy (פשוטה, מורכבת, מה שרק תרצו) היא נכונה.

וואו… הרבה אותיות, הרבה תובנות. בואו נקח דוגמה מימי התיכון הזוהרים:

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

אני רוצה להוסיף שני סימונים לטענות בשלב זה:

  • טענה xx - במשולש גובה לצלע הוא גם תיכון לאותה צלע
  • טענה yy - המשולש הוא שווה שוקיים

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

בכל מקרה, נניח שיום אחד אתם עושים מבחן במתמטיקה ופתאום, All of a sudden, מופיע לפניכם משולש בו גובה לאחת הצלעות הוא גם תיכון לצלע (וואו מה הסיכויים?). המשולש הזה שהופיע בפנינו בעצם מציין כי הטענה xx היא טענה נכונה. אז מה נותן לנו ה-כלל שלנו? ה-כלל שלנו אומר לנו, שמפני שבמשולש שלנו אנך ותיכון לצלע מתלכדים (הטענה xx נכונה), ומפני שהטענה (אם xx אז yy) גם היא נכונה, אז הטענה yy נכונה – משמע המשלוש שנפל עלינו כך פתאום הוא משולש שווה שוקיים.

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

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

  • xx – היום יום חם
  • yy – אני הולך לים

אז הכלל אומר לנו שאם xx היא טענה נכונה (כלומר היום יום חם), וגם אם xx אז yy נכונה (כלומר יום חם גורר שאני הולך לים), אז yy נכונה (כלומר היום אני הולך לים). מופתעים? אני בספק. מעכשיו ועד סוף חלק הלוגיקה, אני אתייחס לכלל זה בתור “ה-כלל”2.

בנוסף, אני רוצה להציג סימון מקובל לכלי אם…אז והוא: \leftarrow. די טריוויאלי, לא? אז במקום לכתוב אם xx אז yy, נכתוב מעתה yxy\leftarrow x. אני קורא את זה “איקס גורר וואי”. לכן הכלל שלנו הופך להיות: אם xx נכון, וגם yxy\leftarrow x נכון, אז yy נכון.

אבל איפה המשמעות?

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

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

אז נניח שאנחנו מתכוונים להוכיח שהטענה הבאה yxy\leftarrow x היא נכונה. נעקוב אחרי השלבים הבאים:

1. נניח ש-xx נכון

אין הרבה בשלב הזה, פשוט נניח שהוא נכון.

2. נשתמש בכללי היסק, אקסיומות, טענות ידועות, ו-xx כדי להוכיח עוד טענות

מהם כללי ההיסק? אלו הכללים לקביעת נכונות טענות מהחלק הקודם, ובנוסף ה-כלל שלנו. מה הן אקסיומות? שווה לתת מילה או שתיים עליהן.

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

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

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

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

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

אוסף האמצעים בהם נשתמש בהוכחה מרכיב למעשה את “שכבת התיאוריה” עליה הוסבר בסוף פרק הלמידה.

3. בעודנו מבצעים את השלב הקודם, נוכיח כי טענה yy נכונה

למעשה שלב 3 מספר לנו רק מתי סיימנו את שלב 2.

וזהו! הנחנו כי הטענה xx נכונה, והראנו כי זה גורר שהטענה yy נכונה, לכן הטענה yxy\leftarrow x הינה נכונה.

אני חוזר – כדי להוכיח שטענת yxy\leftarrow x היא נכונה צריך:

  1. להניח ש-xx היא טענה נכונה.
  2. להשתמש בכללי ההיסק, האקסיומות, הטענות הידועות ו-xx כדי להוכיח עוד טענות.
  3. תוך כדי שלב 2, להוכיח שטענה yy היא נכונה.

אני חושב שהכי טוב להסביר את השלבים על ידי דוגמה. נניח שיש לנו טענות x,y,zx,y,z כלשהן4, ונניח שחטפו אותי חבורת מדענים מרושעים שרוצים את התשובות למבחן המסכם בקורס, ואלו מוכנים לשחרר אותי אך ורק אם אוכיח להם כי zxz\leftarrow x, או אתן להם את התשובות למבחן. בנוסף, נניח שבטוב ליבם, הם מספרים לי שמתקיימות הנקודות הבאות:

  • הטענה yxy\leftarrow x היא נכונה (זוהי טענה ידועה כפי שציינתי בשלב 2)
  • הטענה zyz\leftarrow y גם היא נכונה (גם זו טענה ידועה)

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

מההסקה ש-yy היא טענה נכונה, מהנקודה השנייה שנתנו לי המדענים המרושעים, ומה-כלל שלנו אנחנו יכולים להסיק ש– zz נכונה. וזה בדיוק סוגר את שלב

  1. שוב ניצלתי מידם של המדענים המרושעים.
תרגיל

להלן טענות:

xx = היום יום חם, yy = אני הולך לים, zz = אני נשרף בכתפיים.

בנוסף אני חושף בפניכם את המידע הרגיש שהטענות x,yx,zyx,y\leftarrow x,z\leftarrow y נכונות. האם כדאי לי לקחת קרם הגנה?

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

“נו אז צחוקים ודאחקות, מה כל כך קשה בלכתוב הוכחות של חדו”א?”

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

אין שגיאות נגררות

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

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

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

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

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

דוגמה 1

תהי ana_{n} סדרת קושי . הוכיחו כי ana_{n} חסומה.

במבט ראשון השאלה נראת מוזרה. מה לי ול-ana_{n}? מה לעזאזל הופך סדרה לקושי? ואיך, לכל הרוחות, אני אמור לשכנע אתכם שהיא באמת חסומה? אבל במבט שני השאלה הזו מתיישבת בדיוק עם השלבים שתיארנו לעיל. ראשית בואו נסמן ש-xx = ana_{n} סדרת קושי. טענה לגיטימית. נסמן בנוסף כי yy = ana_{n} חסומה. עכשיו השאלה מתחילה בכך שמספרים לנו ש-xx היא טענה נכונה. לכן מה-כלל שלנו אנחנו יכולים להסיק שאם – באופן קסום – הטענה (yxy\leftarrow x) נכונה, אז גם הטענה yy תהיה נכונה.

איך עושים זאת? פשוט מוכיחים כי הטענה yxy\leftarrow x היא טענה נכונה. ואיך עושים את זה? בעזרת שלושת השלבים! מניחים את xx, משתמשים במשפטים ואקסיומות, למשל בהוכחה זו משתמשים בהגדרה של סדרת קושי, ובטענה שלכל קבוצת מספרים ממשיים בעלת מספר סופי של איברים יש מקסימום, ומשם בעזרת כללי היסק ניתן לקבל את yy. אני יודע שלא באמת הוכחנו כלום כאן, אבל חשוב מאוד לדעת להסתכל על הוכחות “מלמעלה”, שכן זה נותן את הכיוון הכללי בכל הוכחה. כמובן שהקושי (האתגר, לא ה-Cauchy של סדרת קושי), הוא להבין איך בדיוק להשתמש בהגדרת סדרות קושי לטובת ההוכחה, שכן יכולים להיות שימושים רבים להגדרה אחת. בחירת השימוש הנכון הינה מיומנות נרכשת, שאנו צוברים במהלך פתרון שאלות ומסמלת הבנה עמוקה של ההגדרה.

דוגמה 2

תהי f(x+iy)=u(x,y)+iv(x,y)f(x+iy)=u(x,y)+iv(x,y) פונקצייה מוגדרת בסביבת הנקודה z0=x0+iy0z_{0}=x_{0}+iy_{0}, ובנוסף u,vu,v גזירות בנקודה (x0,y0)(x_{0},y_{0}) ומקיימות שם את משוואות קושי5-רימן. הוכיחו כי ff גזירה ב-z0z_{0}.

מקור: MemeCenter
מקור: MemeCenter

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

תרגיל

בדומה לדוגמה הקודמת, סמנו מהן הטענות xx ו-yy המתאימות. xx מציין את הנתונים בשאלה, ו-yy אלו המסקנות.

פתרון

הטענה xx היא –f(x+iy)=u(x,y)+iv(x,y)f(x+iy)=u(x,y)+iv(x,y) פונקצייה מוגדרת בסביבת הנקודה z0=x0+iy0z_{0}=x_{0}+iy_{0}, ובנוסף u,vu,v גזירות בנקודה (x0,y0)(x_{0},y_{0}) ומקיימות שם את משוואות קושי-רימן. (שמתם לב לשימוש בכלי וגם מהחלק הקודם שמופיע בתור מילת הקישור “ובנוסף”?)

הטענה yy היא – ff גזירה ב-z0z_{0}.

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

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

איזו התרגשות, שנמשיך?


  1. מומלץ לקרוא משפט זה לפחות פעמיים. 

  2. בז’רגון מכנים אותוmodus ponens 

  3. הגדרות למעשה הן טענות כלומר אך כפי שציינו טענות כלומר שקולות לשתי טענות אם…אז 

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

  5. די! זה אותו קושי של סדרת קושי?? 

החכמתם? נהנתם? מוזמנים להזמין לי כוס קפה :)