מכינה למחלקת מתמטיקה/מערכי שיעור/14

שיטות הוכחה

הוכחה בשלילה

הוכחה בשלילה מבוססת על הטאוטולוגיה [math]\displaystyle{ (\sim p \rightarrow F)\rightarrow p }[/math]. בהוכחה בשלילה אנו מניחים את השלילה של מה שצריך להוכיח ומגיעים לסתירה.

שימו לב שאנו לא שוללים את הנתון אלא את הצ"ל.

דוגמא:

תרגיל תהיינה 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]

בסתירה.