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

שיטות הוכחה

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

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

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

הוכחה בשלילה

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

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

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

מבנה שאלה:

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

מבנה ההוכחה:

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

דוגמא 1

• תהיינה A,B קבוצות המקיימות [math]\displaystyle{ A\backslash B=B\backslash A }[/math].
• הוכיחו כי [math]\displaystyle{ A=B }[/math]

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

• נתון: [math]\displaystyle{ A\backslash B=B\backslash A }[/math]
• צ"ל: [math]\displaystyle{ A=B }[/math]

נניח בשלילה כי [math]\displaystyle{ A\neq B }[/math].

לכן קיים [math]\displaystyle{ a\in A }[/math] כך ש [math]\displaystyle{ a\notin B }[/math] (או ההפך)

לכן לפי ההגדרה [math]\displaystyle{ a\in A\backslash B }[/math] אבל [math]\displaystyle{ a\notin B\backslash A }[/math] (או ההפך)

לכן [math]\displaystyle{ A\backslash B\neq B\backslash A }[/math]

בסתירה.

דוגמא 2

• תהיינה A,B קבוצות כך ש [math]\displaystyle{ (A\backslash B)\cup B = (A\cup B)\backslash B }[/math].
• הוכיחו כי [math]\displaystyle{ B = \phi }[/math]

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

נניח בשלילה כי [math]\displaystyle{ B\neq \phi }[/math].

לכן קיים איבר [math]\displaystyle{ b\in B }[/math].

לכן [math]\displaystyle{ b\in B \or b\in(A\backslash B) }[/math].

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

לכן [math]\displaystyle{ b\in(A\backslash B)\cup B }[/math].

מצד שני כיוון ש[math]\displaystyle{ b\in B }[/math], ניתן להסיק כי [math]\displaystyle{ b\in B \or b\not\in(A\cup B) }[/math].

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

כלומר [math]\displaystyle{ \neg \left(b\in(A\cup B)\backslash B\right) }[/math].

לכן [math]\displaystyle{ b\not\in(A\cup B)\backslash B }[/math].

בסתירה לכך ש [math]\displaystyle{ (A\backslash B)\cup B = (A\cup B)\backslash B }[/math].

דוגמא 3

• יהי מספר ממשי [math]\displaystyle{ x\geq 0 }[/math] המקיים את הטענה- לכל מספר חיובי [math]\displaystyle{ \epsilon\gt 0 }[/math] מתקיים [math]\displaystyle{ x\lt \epsilon }[/math].
• הוכיחו כי x=0

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

נניח בשלילה כי [math]\displaystyle{ x\neq 0 }[/math].

כיוון ש [math]\displaystyle{ x\geq 0 }[/math] נובע כי [math]\displaystyle{ x\gt 0 }[/math].

לכן [math]\displaystyle{ 0\lt \frac{x}{2}\lt x }[/math].

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

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

הוכחת שיוויון בין קבוצות

ראשית, שימו לב שהקבוצות בתרגיל כזה יכולות להופיע באופן עקיף ולא ישיר. למשל, במשוואה [math]\displaystyle{ A\cup (B\backslash C) = P(D) }[/math] מופיעות שתי קבוצות המיוצגות על ידי ארבע הקבוצות A,B,C,D.

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

שיטה I: להוכיח שלכל איבר x, מתקיים ש x שייך לקבוצה הימנית אם ורק אם x שייך לקבוצה השמאלית.

שיטה II: הכלה דו כיוונית. להוכיח שהקבוצה הימנית מוכלת בשמאלית וגם הקבוצה השמאלית מוכלת בימנית.