תרגול 1 תשעז

סיכום הנושא המלא של שני התרגולים הראשונים נמצא בדף 88-101 חשיבה מתמטית.

קַשָּרִים, הצרנה וטבלאות אמת

אטומים

הגדרה (לא פורמאלית): השפה העברית מורכבת ממשפטים. המקבילה בשפה המתמטית נקראת "פסוק".האטומים הם חלק מאבני היסוד של הפסוקים. לדוגמא: הפסוק "שנת הלימודים החלה ויש 5 קורסים בשנה א'" מורכב משני אטומים- "שנת הלימודים החלה" ו"יש 5 קורסים בשנה א'" (שני האטומים מקשורים ע"י וו החיבור)

על מנת לבנות פסוקים יותר מורכבים משתמשים בקשרים.

קשרים

הגדרה: יהיו A,B אטומים (או פרדיקטים) היכולים להיות אמת (1) או שקר (0) אזי הקשרים

• $A\to B$ - "גרירה" (חד כיוונית)
• $A \or B$ "או"
• $A\and B$ "וגם"
• $\neg A$ "שלילה"

מוגדרים ע"י טבלאת האמת הבאה:

$\neg A$	$A\and B$	$A \or B$	$A \to B$	$B$	$A$
1	0	0	1	0	0
1	0	1	1	1	0
0	0	1	0	0	1
0	1	1	1	1	1

הערה: קשר נוסף שהינו נפוץ בתחום המתמטקיה והוא גרירה דו-כיוונית (ידוע בכינויו אם ורק אם, אמ"מ). הגדרתו פשוטה (נובעת משמו..) והיא מוגדרת ע"י קשר הגרירה החד כיווני. $A\iff B := (A\Rightarrow B)\and(B\Rightarrow A)$

דוגמאות מילוליות:

• אם נסיים את החומר של השיעור אז נגמור מוקדם. אם נסיים את החומר וגם לא נגמור מוקדם אז הפסוק יקבל ערך F. אם לא נסיים את החומר וגם לא נגמור מוקדם אז הפסוק יקבל ערך T.
• אינדוקציה לומדים בתיכון וגם זה קל. הפסוק יקבל ערך T רק אם האטומים המרכיבים אותו יקבלו ערך T (כלומר שניהם יתקיימו)
• 3 הוא מספר ראשוני או 5 הוא מספר ראשוני. הפסוק הזה מקבל ערך T כיוון ש 3/5 מספר ראשוני. גם הפסוק "3 הוא מספר ראשוני או 4 הוא מספר ראשוני" הוא בעל ערך T.
• מספר (טבעי) מסוים n ניתן להצגה בעזרת 2 ספרות (בבסיס עשרוני) $\iff$ המספר n קטן מ 100. הפסוק יקבל ערך T רק אם שני התנאים יתקיימו ביחד. במילים אחרות, אם אחד מתקיים גם השני. במילים אחרות, אם אחד לא מתקיים אז השני גם לא מתקיים.

הערה (טרמינולוגיה):

• כאשר אומרים ש B הוא תנאי הכרחי ל A פירושו הוא $A \to B$
• כאשר אומרים ש B הוא תנאי מספיק ל A פירושו הוא $B \to A$
• כאשר אומרים ש B הוא תנאי הכרחי ומספיק ל A פירושו הוא $B \iff A$

תכונות הקשרים:

• קיבוציות $(A\land B) \land C =A\land (B \land C), (A\lor B) \lor C =A\lor (B \lor C)$
• חילופיות $A\land B =B\land A, A\lor B = B\lor A$
• פילוג $A\lor (B\land C)= (A\lor B)\land (A\lor C), A\land (B\lor C)= (A\land B)\lor (A\land C)$
• כללי דה מורגן $\neg (A \lor B) = \neg A \land \neg B, \neg (A \land B) = \neg A \lor \neg B$. תוכיחו אחד מהם בתרגיל הבית

הצרנה

הצרנה- כתיבת רעיון בעזרת ניסוח פורמאלי

דוגמא: נצרין את המשפט: "אם יש בגרות בשעה חופפת לקורס אז הוא מתבטל ". נגדיר $A$ = יש בגרות בשעה שחופפת לקורס. $B$= הקורס מתבטל. המשפט אומר $A\to B$. כלומר בגרות בשעה חופפת לקורס זה תנאי מספיק לכך שהקורס מתבטל. שימו לב שזהו לא תנאי הכרחי כי יתכן שהקורס יתבטל מסיבות אחרות.

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

פתרון: נסמן A למדתי לבמחן, B נכשלתי במבחן אזי ההצרנה היא $A\land B$

הצרן: "ערן לובש חולצה סגולה בכל פעם שהוא לובש מכנסיים בצבע שחור"

פתרון: נסמן A ערן לובש חולצה סגולה. נסמן B ערך לובש מכנסיים שחורות. ההצרנה $B\to A$

הצרן: "כאשר אני עייף ורעב אני נעשה עצבני, או שאני הולך לישון; אבל אם אני עצבני ולא עייף, אז אני רעב".

פתרון: נסמן A אני עייף, B אני רעב, C אני עצבני, D אני הולך לישון ההצרנה $[(A\land B)\to (C\lor D)]\and[(C \land \lnot A)\to B]$

הגדרות הקשורות לקבוצות

ההגדרה האינטואיטיבית לקבוצה הינה "אוסף של איברים". בקבוצה אין משמעות לסדר האיברים, ואיבר אינו יכול להופיע פעמיים. דוגמאות ל3 קבוצות (קבוצות נוהגים לסמן בין 2 סוגריים מסולסלות):

$\{1,\mathrm{horse},3\}$, $\{1,2,3\}$ ו$\{1,\{2,3\},\{\}\}$

איבר השייך לקבוצה אנו מסמנים בסימן $\in$. למשל $1\in\{1,2,3\}$, ואילו $4\notin\{1,2,3\}$. שימו לב שגם $1\notin\{\{1,2,3\}\}$ שכן האיבר היחיד בקבוצה זו הינה הקבוצה $\{1,2,3\}$.

• אומרים שקבוצה A מוכלת בקבוצה B (מסומן $A \subseteq B$) אם כל האיברים בA הם גם איברים בB.

• חיתוך של שתי קבוצות A ו B הינו אוסף האיברים השייכים גם לA וגם לB (מסומן $A\cap B$).
• איחוד של שתי קבוצות A ו B הינו אוסף האיברים השייכים לA או לB (מסומן $A\cup B$).
• A הפרש B הינה הקבוצה המכילה את כל האיברים בA שאינם בB (מסומן A\B).
• ההפרש הסימטרי בין שתי קבוצות A וB הוא אוסף האיברים הנמצאים באחת הקבוצות אך לא בחיתוך (מסומן $A\Delta B$).

תרגיל:

• הצרן תנאי השקול לכך ש-a שייך לאיחוד של הקבוצות A וB

פתרון $a\in A \or a\in B$

• הצרן תנאי השקול לכך ש-a אינו שייך לאיחוד של הקבוצות A וB
• הצרן תנאי השקול לכך ש-a שייך לחיתוך של הקבוצות A וB
• הצרן תנאי השקול לכך ש-a אינו שייך לחיתוך של הקבוצות A וB

הגדרה: קבוצה A מוכלת בקבוצה B אם בB נמצאים כל האיברים מA (למשל הטבעיים מוכלים בשלמים $\mathbb{N}\subseteq\mathbb{Z}$, והשלמים מוכלים בממשיים $\mathbb{Z}\subseteq\mathbb{R}$).

• הצרן תנאי השקול לכך ש-C מוכלת בחיתוך של A וB

פתרון: $\forall c [c\in C \rightarrow (c\in A \and c \in B)]$

• הצרן תנאי השקול לכך ש-C אינה מוכלת באיחוד של A וB

טאוטולוגיות

הגדרה : טאוטולוגיה הינה ביטוי שנכון תמיד ללא תלות בערכים שמציבים בו. למשל $A \or \neg A$

הגדרה: נאמר שביטוי $A$ שקול טאוטולוגית לביטוי $B$ (ונסמן $A \equiv B$) אם הביטוי $A \iff B$ הינו טאוטולוגיה (במילים: A קורה אמ"מ B קורה)

הוכח את הבאים:

• $\ \neg(A \or B) \equiv \neg A \and \neg B$
• $\ A\or (B \and C ) \equiv (A \or B ) \and (A \or C)$
• $\ (A\rightarrow B) \equiv ((\neg A) \vee B)$.
• $\ (A \leftrightarrow B) \equiv ((A \wedge B)\vee((\neg A)\wedge (\neg B)$.
• $\ (A \leftrightarrow B) \equiv (A \rightarrow B) \wedge (B \rightarrow A)$.
• $\ (A \rightarrow B) \equiv ((\neg B) \rightarrow (\neg A))$.

דוגמא מילולית:

• מי שלא לומד בסמסטר נכשל במבחן אמ"מ מי שלא נכשל במבחן למד בסמסטר

דרכי הוכחה

הוכח שהפסוקים הבאים הינם טאוטולוגיות:

• $(A\rightarrow B) \iff (\neg B \rightarrow \neg A)$
• $A \iff(\neg A \rightarrow F)$
• $(A\lor B) \iff(\neg A \rightarrow B)$

(נהוג להחליף ביטויים מהצורה הזו בביטויים השקולים להם כי הם נוחים יותר להוכחה מידי פעם.)

דוגמאות מילוליות:

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