שיטות הוכחה בסיסיות

מתוך Math-Wiki
גרסה מ־16:45, 7 ביולי 2015 מאת ארז שיינר (שיחה | תרומות) (שיטות הוכחה)

קפיצה אל: ניווט, חיפוש

שיטות הוכחה

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

לכן נציג מספר שיטות להתחלת פתרון תרגילים מתמטיים.

ראשית מומלץ לקרוא את החלק הרלוונטי בקורס לחשיבה מתמטית

הוכחה בשלילה

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

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

מבנה שאלה והוכחה בשלילה

מבנה שאלה:

  • נתונים.
  • טענה שצריך להוכיח.

מבנה ההוכחה:

  • נניח את הנתונים.
  • נניח את השלילה של הטענה שצריך להוכיח.
  • נסיק סתירה.

דוגמא 1

  • תהיינה A,B קבוצות המקיימות A\backslash B=B\backslash A.
  • הוכיחו כי A=B


הוכחה בשלילה:

  • נתון: A\backslash B=B\backslash A
  • צ"ל: A=B

נניח בשלילה כי A\neq B.

לכן קיים a\in A כך ש a\notin B (או ההפך)

לכן לפי ההגדרה a\in A\backslash B אבל a\notin B\backslash A (או ההפך)

לכן A\backslash B\neq B\backslash A

בסתירה.

דוגמא 2

  • תהיינה A,B קבוצות כך ש (A\backslash B)\cup B = (A\cup B)\backslash B.
  • הוכיחו כי  B = \phi

הוכחה בשלילה:

נניח בשלילה כי B\neq \phi.

לכן קיים איבר b\in B.

לכן b\in B \or b\in(A\backslash B).

שימו לב השתמשנו כאן בכלל ההיסק הבא: מהנחת טענה א', ניתן להסיק שטענה א' או טענה ב' נכונות.

לכן b\in(A\backslash B)\cup B.

מצד שני כיוון שb\in B, ניתן להסיק כי b\in B \or b\not\in(A\cup B).

אבל זה שקול לפי דה מורגן לטענה \neg \left(b\not\in B \and b\in(A\cup B)\right).

כלומר \neg \left(b\in(A\cup B)\backslash B\right) .

לכן b\not\in(A\cup B)\backslash B .


בסתירה לכך ש (A\backslash B)\cup B = (A\cup B)\backslash B.


דוגמא 3

  • יהי מספר ממשי x\geq 0 המקיים את הטענה- לכל מספר חיובי \epsilon>0 מתקיים x<\epsilon.
  • הוכיחו כי x=0

הוכחה בשלילה:

נניח בשלילה כי x\neq 0.

כיוון ש x\geq 0 נובע כי x>0.

לכן 0<\frac{x}{2}<x.

כלומר קיים מספר חיובי \epsilon=\frac{x}{2} עבורו x\not<\epsilon, בסתירה לנתון.

שימו לב המסקנה שהגענו אליה היא בדיוק שלילת הנתון.