Math-Wiki - תרומות המשתמש [he]

תרגול 6 תשעז

2019-02-07T02:30:45Z

ליאל221: /* פתרון */

חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].

=המשך קבוצות=

== משלים ==

'''הגדרה''': תהי קבוצה <math>U</math>, ונביט בתת קבוצה שלה <math>A</math>. ניתן להגדיר את ה'''משלים''' של <math>A</math> כאוסף האיברים ב-<math>U</math> שאינם ב-<math>A</math> (כלומר ההפרש <math>U\setminus A</math>), המסומן <math>A^c</math>. לא ניתן לדבר על משלים אוניברסלי ללא <math>U</math> מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).

תכונות בסיסיות:
* <math>A\cup A^c = U</math>
* <math>\varnothing^c = U</math>
* <math>U^c = \varnothing</math>
* <math>(A^c)^c = A</math>

על המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):
*<math>(A\cap B)^c = A^c \cup B^c</math>
*<math>(A\cup B)^c = A^c \cap B^c</math>
הערה: באופן כללי מתקיים
* <math>(\bigcap _{i\in I} A_i)^c = \bigcup _{i\in I} A_{i}^c </math>
* <math>(\bigcup _{i\in I} A_i)^c = \bigcap _{i\in I} A_{i}^c </math>

===תרגיל===

הוכיחו כי <math>A \triangle B = A^c \triangle B^c</math>.

===פתרון===

נשתמש בהצגת ההפרש הסימטרי כאיחוד ההפרשים:

<math>x\in A \triangle B \iff (x\in A \land x\notin B)\lor (x\in B \land x\notin A) \iff</math>

<math>(x\notin A^c \land x\in B^c)\lor (x\notin B^c \land x\in A^c)</math> ומחילופיות "וגם" ו"או":

<math>(x\notin B^c \land x\in A^c)\lor (x\notin A^c \land x\in B^c) \iff</math>
<math>(x\in A^c \land x\notin B^c)\lor (x\in B^c \land x\notin A^c) \iff x\in A^c \triangle B^c</math>

===תרגיל===
לכל <math>n\in \mathbb{N}</math> נגדיר <math>A_n=\{k\in \mathbb{N}|2\leq k\leq 2n-1\}</math> ונגדיר <math>B_n=A_{n+1}\smallsetminus A_n</math>.

א. מצאו את <math>\bigcup_{n\in \mathbb{N}} B_n</math>.

ב. נגדיר <math>D_n=\mathbb{N}\smallsetminus B_n</math>. מצאו את <math>\bigcap_{n\in \mathbb{N}} D_n</math>.

====פתרון====

א. התשובה: <math>\mathbb{N}\smallsetminus \{1\}</math>. הוכחה:

<math>\bigcup_{n\in \mathbb{N}} B_n \subseteq \mathbb{N}\smallsetminus \{1\} </math>: הכל תת קבוצות של הטבעיים וכל הקבוצות מוגדרות ע"י איברים הגדולים מ-<math>2</math>.

<math>\mathbb{N}\smallsetminus \{1\} \subseteq \bigcup_{n\in \mathbb{N}} B_n</math>: יהי <math>a\in \mathbb{N}\smallsetminus \{1\}</math> נמצא קבוצה בה הוא נמצא. נשים לב ש-<math>B_n=\{2\leq k\leq 2n+1\}\smallsetminus \{2\leq k\leq 2n-1\}=\{2n,2n+1\}</math>. לכן אם <math>a</math> זוגי הוא נמצא ב- <math>B_{\frac{n}{2}}</math> ואם אי-זוגי אז <math>a\in B_{\frac{n-1}{2}}</math>.

ב. נתייחס ל-<math>\mathbb{N}</math> כקבוצה האוניברסלית לדיוננו. לפי דה-מורגן נקבל:<math>\bigcap_{n\in \mathbb{N}} D_n=\bigcap_{n\in \mathbb{N}} B_n^c=(\bigcup_{n\in \mathbb{N}} B_n)^c=\{1\}</math>.

==קבוצת החזקה==

'''הגדרה''': תהי קבוצה <math>A</math>. נגדיר את '''קבוצת החזקה''' של <math>A</math> בתור אוסף כל תת הקבוצות של <math>A</math>. נסמן <math>P(A)=\{X:X\subseteq A\}</math>.

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

===תרגיל===
הוכיחו או הפריכו: <math>A\cap P(P(A))=\varnothing</math>.

====פתרון====
הפרכה : ניקח <math>A=\{1,\{\{1\}\}\}</math>.

===תרגיל===
הוכיחו או הפריכו:

א. <math>P(A)\cap P(B)=P(A\cap B)</math>

ב. <math>P(A)\cup P(B)=P(A\cup B)</math>

====פתרון====

א. הוכחה: <math>X\in P(A)\cap P(B) \iff X\subseteq A\land X\subseteq B\iff</math>

<math>X\subseteq A\cap B\iff X\in P(A\cap B)</math>

ב. הפרכה: ניקח <math>A=\{1\},B=\{2\}</math>. אז <math>\{1,2\} \in P(A\cup B)</math>, אבל לא ל-<math>P(A)\cup P(B)</math>.

למעשה הוכיחו כי <math>P(A)\cup P(B)=P(A\cup B)</math> אם ורק אם <math>A\subseteq B</math> או <math>B\subseteq A</math>.

===תרגיל ממבחן===
תהינה <math>A,B,C</math> קבוצות. הוכיחו או הפריכו:

א. אם <math>A \not\subseteq B \cap C</math> אזי <math>(A\setminus B)\cap(A\setminus C)\neq \varnothing</math>

ב. אם <math>A\subseteq B</math> אזי <math>A\cup (B\setminus A)=B</math>

ג. אם <math>A\cap B=\varnothing</math> אזי <math>P(A)\cap P(B) = \{\varnothing\}</math>

===פתרון===
א. '''הפרכה''': <math>A=\{1,2\},B=\{1\},C=\{2\}</math>. אזי ברור ש-<math>A</math> איננה מוכלת בחיתוך <math>B\cap C</math> אבל <math>(A\setminus B)\cap(A\setminus C)=\{2\}\cap\{1\}=\varnothing</math>.

ב. נתון שלכל <math>a\in A</math> מתקיים <math>a \in B</math>. אזי

<math>x\in [A\cup(B\setminus A)] \iff (x\in A) \or [(x\in B)\and (x\notin A)] \iff</math>

<math>[(x\in A) \or (x\in B)] \and [(x \in A)\or (x\notin A)] </math>

כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון <math>(x\in A)\rightarrow (x\in B)</math> ניתן להסיק בקלות ש-<math>(x\in A)\or (x\in B) \iff (x\in B)</math>, כפי שרצינו.

דרך נוספת: נגדיר את <math>B</math> להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי
<math>A\cup A^c =U</math> וזה אכן נכון!

ג. נניח בשלילה ש-<math>P(A)\cap P(B)\neq \{\varnothing\}</math>. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה, החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה <math>C \ne\varnothing</math> השייכת לחיתוך <math>P(A)\cap P(B)</math>. קבוצות החזקה הן אוסף תת הקבוצות, ולכן <math>C\subseteq A \and C\subseteq B</math>. מכיוון ש-<math>C</math> אינה ריקה קיים בה איבר <math>c\in C</math> וקל לראות ש-<math>(c\in A)\and (c\in B) </math> ולכן <math>c</math> מוכל בחיתוך, בסתירה לכך שהחיתוך ריק.

תרגול 1 תשעז

2019-02-06T10:53:31Z

ליאל221: /* תרגיל */

חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].

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

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

=== אטומים ===

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

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

=== קשרים ===

הגדרה: יהיו A,B אטומים (או פרדיקטים) היכולים להיות אמת (1) או שקר (0) אזי הקשרים
* <math>A\to B</math> - "גרירה" (חד כיוונית)
* <math>A \or B</math> "או"
* <math>A\and B</math> "וגם"
* <math>\neg A</math> "שלילה"
מוגדרים ע"י טבלאת האמת הבאה:

{| border="1" align="center" style="text-align:center;"
| <math>\neg A</math>
|<math>A\and B</math>
|<math>A \or B</math>
|<math>A \to B</math>
|<math>B</math>
|<math>A</math>
|-
|1
|0
|0
|1
|0
|0
|-
|1
|0
|1
|1
|1
|0
|-
|0
|0
|1
|0
|0
|1
|-
|0
|1
|1
|1
|1
|1
|-

|}

הערה: קשר נוסף שהינו נפוץ בתחום המתמטיקה והוא גרירה דו-כיוונית (ידוע בכינויו "אם ורק אם", ובקיצור אמ"מ, או אם"ם).
הגדרתו פשוטה (נובעת משמו..) והיא מוגדרת בעזרת קשר הגרירה החד-כיווני:
<math>A\leftrightarrow B := (A\rightarrow B)\and(B\rightarrow A)</math>

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

=== הצרנה ===

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

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

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

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

הצרן: אם כדור הארץ שטוח אז הסוס שלי שחור.

פתרון: נסמן A = כדור הארץ שטוח, B = הסוס שלי שחור. ונקבל <math>A\rightarrow B</math>.

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

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

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

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

===הכרחי ומספיק===
'''הנה כמה הגדרות המשמשות בתואר מתמטי:'''
*כאשר אומרים ש B הוא תנאי הכרחי ל A פירושו הוא <math>A \to B</math>
*כאשר אומרים ש B הוא תנאי מספיק ל A פירושו הוא <math>B \to A</math>
*כאשר אומרים ש B הוא תנאי הכרחי ומספיק ל A פירושו הוא <math>B \leftrightarrow A</math>

====תרגיל====
השלם את המשפט הבא: כדי שירד גשם _____ שיהיו עננים בשמים. לכן אם נסמן ע"י "יש עננים בשמים = A", "יורד גשם = B" נקבל "A____B".

פיתרון: הכרחי, <math>\leftarrow </math>

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

הגדרה: נאמר שביטוי <math>A</math> שקול טאוטולוגית לביטוי <math>B</math> (ונסמן <math>A \equiv B</math>)
אם הביטוי <math>A \leftrightarrow B</math> הינו טאוטולוגיה (במילים: A קורה אמ"מ B קורה)

====תכונות הקשרים====
* קיבוציות (אסוציאטיביות) - <math>(A\land B) \land C \equiv A\land (B \land C), (A\lor B) \lor C \equiv A\lor (B \lor C) </math>
* חילופיות (קומוטטיביות) - <math>A\land B \equiv B\land A, A\lor B \equiv B\lor A</math>
* פילוג (דיסטריביוטיביות) - <math>A\lor (B\land C)\equiv (A\lor B)\land (A\lor C), A\land (B\lor C)\equiv (A\land B)\lor (A\land C)</math>
* כללי דה מורגן - <math>\neg (A \lor B) \equiv \neg A \land \neg B, \neg (A \land B) \equiv \neg A \lor \neg B</math>.

====תרגיל====
האם המשפטים הבאים שקולים:

א. אם אייל שמח אז ענת גבוהה, ואם ענת גבוהה אז צחי חמוד.

ב. כאשר אייל שמח אז צחי חמוד.

פיתרון: לא, בעזרת הצרנה וטבלת אמת. אייל לא שמח, ענת גבוהה וצחי לא חמוד נותן <math>T</math> בשני ו<math>F</math> בראשון.

====תרגיל====
הוכח את הבאים:
* <math>A \equiv A</math>
* <math>\ (A\rightarrow B) \equiv ((\neg A) \vee B)</math>.
* <math>\ (A \leftrightarrow B) \equiv ((A \wedge B)\vee((\neg A)\wedge (\neg B)</math>.
* <math>\ (A \oplus B) \equiv \lnot(A \leftrightarrow B)</math>.
* <math>\ (A \rightarrow B) \equiv ((\neg B) \rightarrow (\neg A))</math>.

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

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

===טענת גרירה===
הביטוי <math>A\Rightarrow B</math> הוא טענת גרירה ופירושו: הפסוק <math>A\rightarrow B</math> הינו אמת. לכן:

1. כשנדרשים להוכיח משפט מהצורה הזו מה שצריך להראות זה שאם A נכון אז גם B נכון. או במילים אחרות: נניח שA נכון ונוכיח שגם B נכון.

2. כשנדרשים להפריך משפט מהצורה הזו מה שצריך להראות זה שיש השמת ערכי אמת למשתנים כל ש A נכון וB לא נכון.

====תרגיל====
רשום נכון או לא נכון:

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

ב. אם אני לא מנגן בחצוצרה אז אני לא מנגן בפסנתר.

מסקנה: אני לא מנגן בפסנתר אז אני מנגן בתופים.

פתרון: לא נכון: ניקח שקר בשלושתם (לא מנגן בכלום..) א+ב מקבלים ערך <math>T</math> והמסקנה <math>F</math>.

====תרגיל====
רשום נכון או לא נכון:

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

ב. אם אני לא מנגן בחצוצרה אז אני לא מנגן בפסנתר.

מסקנה: אם אני מנגן בפסנתר אני לא מנגן בתופים.

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

===דרכי הוכחה===
הוכח שהפסוקים הבאים הינם טאוטולוגיות:
*<math>(A\rightarrow B) \iff (\neg B \rightarrow \neg A)</math>
*<math>A \iff(\neg A \rightarrow F)</math>
*<math>(A\lor B) \iff(\neg A \rightarrow B)</math>

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

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

====תרגיל====
[https://en.wikipedia.org/wiki/Wason_selection_task ניסוי מפורסם] בפסיכולוגיה של החשיבה עוסק בקלפים שעל כל אחד מהם סימן בשני הצדדים - אות באחד הצדדים ומספר הצד האחר.

מניחים על השולחן ארבעה קלפים, שצידם החשוף מראה את הסימנים A, P, 2, 3. אילו כרטיסים יש להפוך על-מנת לבדוק את הטענה "אם בצד אחד של הכרטיס יש אות אהו"י (AEIOU), אז בצידו האחר יש מספר זוגי"? התשובה הנפוצה ביותר שאנשים השיבו הייתה שיש להפוך את הכרטיסים הראשון והשלישי (אחרים ענו רק את הכרטיס הראשון). מדוע, לדעתך? ומה התשובה הנכונה?

תרגול 1 תשעז

2019-02-06T10:51:03Z

ליאל221: /* תרגיל */

חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].

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

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

=== אטומים ===

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

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

=== קשרים ===

הגדרה: יהיו A,B אטומים (או פרדיקטים) היכולים להיות אמת (1) או שקר (0) אזי הקשרים
* <math>A\to B</math> - "גרירה" (חד כיוונית)
* <math>A \or B</math> "או"
* <math>A\and B</math> "וגם"
* <math>\neg A</math> "שלילה"
מוגדרים ע"י טבלאת האמת הבאה:

{| border="1" align="center" style="text-align:center;"
| <math>\neg A</math>
|<math>A\and B</math>
|<math>A \or B</math>
|<math>A \to B</math>
|<math>B</math>
|<math>A</math>
|-
|1
|0
|0
|1
|0
|0
|-
|1
|0
|1
|1
|1
|0
|-
|0
|0
|1
|0
|0
|1
|-
|0
|1
|1
|1
|1
|1
|-

|}

הערה: קשר נוסף שהינו נפוץ בתחום המתמטיקה והוא גרירה דו-כיוונית (ידוע בכינויו "אם ורק אם", ובקיצור אמ"מ, או אם"ם).
הגדרתו פשוטה (נובעת משמו..) והיא מוגדרת בעזרת קשר הגרירה החד-כיווני:
<math>A\leftrightarrow B := (A\rightarrow B)\and(B\rightarrow A)</math>

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

=== הצרנה ===

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

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

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

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

הצרן: אם כדור הארץ שטוח אז הסוס שלי שחור.

פתרון: נסמן A = כדור הארץ שטוח, B = הסוס שלי שחור. ונקבל <math>A\rightarrow B</math>.

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

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

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

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

===הכרחי ומספיק===
'''הנה כמה הגדרות המשמשות בתואר מתמטי:'''
*כאשר אומרים ש B הוא תנאי הכרחי ל A פירושו הוא <math>A \to B</math>
*כאשר אומרים ש B הוא תנאי מספיק ל A פירושו הוא <math>B \to A</math>
*כאשר אומרים ש B הוא תנאי הכרחי ומספיק ל A פירושו הוא <math>B \leftrightarrow A</math>

====תרגיל====
השלם את המשפט הבא: כדי שירד גשם _____ שיהיו עננים בשמים. לכן אם נסמן ע"י "יש עננים בשמים = A", "יורד גשם = B" נקבל "A____B".

פיתרון: הכרחי, <math>\leftarrow </math>

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

הגדרה: נאמר שביטוי <math>A</math> שקול טאוטולוגית לביטוי <math>B</math> (ונסמן <math>A \equiv B</math>)
אם הביטוי <math>A \leftrightarrow B</math> הינו טאוטולוגיה (במילים: A קורה אמ"מ B קורה)

====תכונות הקשרים====
* קיבוציות (אסוציאטיביות) - <math>(A\land B) \land C \equiv A\land (B \land C), (A\lor B) \lor C \equiv A\lor (B \lor C) </math>
* חילופיות (קומוטטיביות) - <math>A\land B \equiv B\land A, A\lor B \equiv B\lor A</math>
* פילוג (דיסטריביוטיביות) - <math>A\lor (B\land C)\equiv (A\lor B)\land (A\lor C), A\land (B\lor C)\equiv (A\land B)\lor (A\land C)</math>
* כללי דה מורגן - <math>\neg (A \lor B) \equiv \neg A \land \neg B, \neg (A \land B) \equiv \neg A \lor \neg B</math>.

====תרגיל====
האם המשפטים הבאים שקולים:

א. אם אייל שמח אז ענת גבוהה, ואם ענת גבוהה אז צחי חמוד.

ב. כאשר אייל שמח אז צחי חמוד.

פיתרון: לא, בעזרת הצרנה וטבלת אמת. אייל לא שמח, ענת גבוהה וצחי לא חמוד נותן <math>T</math> בשני ו<math>F</math> בראשון.

====תרגיל====
הוכח את הבאים:
* <math>A \equiv A</math>
* <math>\ (A\rightarrow B) \equiv ((\neg A) \vee B)</math>.
* <math>\ (A \leftrightarrow B) \equiv ((A \wedge B)\vee((\neg A)\wedge (\neg B)</math>.
* <math>\ (A \oplus B) \equiv \lnot(A \leftrightarrow B)</math>.
* <math>\ (A \rightarrow B) \equiv ((\neg B) \rightarrow (\neg A))</math>.

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

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

===טענת גרירה===
הביטוי <math>A\Rightarrow B</math> הוא טענת גרירה ופירושו: הפסוק <math>A\rightarrow B</math> הינו אמת. לכן:

1. כשנדרשים להוכיח משפט מהצורה הזו מה שצריך להראות זה שאם A נכון אז גם B נכון. או במילים אחרות: נניח שA נכון ונוכיח שגם B נכון.

2. כשנדרשים להפריך משפט מהצורה הזו מה שצריך להראות זה שיש השמת ערכי אמת למשתנים כל ש A נכון וB לא נכון.

====תרגיל====
רשום נכון או לא נכון:

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

ב. אם אני לא מנגן בחצוצרה אז אני לא מנגן בפסנתר.

מסקנה: אני לא מנגן בפסנתר אז אני מנגן בתופים.

פתרון: לא נכון: ניקח שקר בשלושתם (לא מנגן בכלום..) א+ב מקבלים ערך <math>T</math> והמסקנה <math>F</math>.

====תרגיל====
רשום נכון או לא נכון:

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

ב. אם לא מנגן בחצוצרה אז לא מנגן בפסנתר.

מסקנה: אם מנגן בפסנתר לא מנגן בתופים.

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

===דרכי הוכחה===
הוכח שהפסוקים הבאים הינם טאוטולוגיות:
*<math>(A\rightarrow B) \iff (\neg B \rightarrow \neg A)</math>
*<math>A \iff(\neg A \rightarrow F)</math>
*<math>(A\lor B) \iff(\neg A \rightarrow B)</math>

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

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

====תרגיל====
[https://en.wikipedia.org/wiki/Wason_selection_task ניסוי מפורסם] בפסיכולוגיה של החשיבה עוסק בקלפים שעל כל אחד מהם סימן בשני הצדדים - אות באחד הצדדים ומספר הצד האחר.

מניחים על השולחן ארבעה קלפים, שצידם החשוף מראה את הסימנים A, P, 2, 3. אילו כרטיסים יש להפוך על-מנת לבדוק את הטענה "אם בצד אחד של הכרטיס יש אות אהו"י (AEIOU), אז בצידו האחר יש מספר זוגי"? התשובה הנפוצה ביותר שאנשים השיבו הייתה שיש להפוך את הכרטיסים הראשון והשלישי (אחרים ענו רק את הכרטיס הראשון). מדוע, לדעתך? ומה התשובה הנכונה?

תרגול 1 תשעז

2019-02-06T10:49:31Z

ליאל221: /* תרגיל */

חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].

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

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

=== אטומים ===

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

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

=== קשרים ===

הגדרה: יהיו A,B אטומים (או פרדיקטים) היכולים להיות אמת (1) או שקר (0) אזי הקשרים
* <math>A\to B</math> - "גרירה" (חד כיוונית)
* <math>A \or B</math> "או"
* <math>A\and B</math> "וגם"
* <math>\neg A</math> "שלילה"
מוגדרים ע"י טבלאת האמת הבאה:

{| border="1" align="center" style="text-align:center;"
| <math>\neg A</math>
|<math>A\and B</math>
|<math>A \or B</math>
|<math>A \to B</math>
|<math>B</math>
|<math>A</math>
|-
|1
|0
|0
|1
|0
|0
|-
|1
|0
|1
|1
|1
|0
|-
|0
|0
|1
|0
|0
|1
|-
|0
|1
|1
|1
|1
|1
|-

|}

הערה: קשר נוסף שהינו נפוץ בתחום המתמטיקה והוא גרירה דו-כיוונית (ידוע בכינויו "אם ורק אם", ובקיצור אמ"מ, או אם"ם).
הגדרתו פשוטה (נובעת משמו..) והיא מוגדרת בעזרת קשר הגרירה החד-כיווני:
<math>A\leftrightarrow B := (A\rightarrow B)\and(B\rightarrow A)</math>

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

=== הצרנה ===

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

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

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

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

הצרן: אם כדור הארץ שטוח אז הסוס שלי שחור.

פתרון: נסמן A = כדור הארץ שטוח, B = הסוס שלי שחור. ונקבל <math>A\rightarrow B</math>.

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

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

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

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

===הכרחי ומספיק===
'''הנה כמה הגדרות המשמשות בתואר מתמטי:'''
*כאשר אומרים ש B הוא תנאי הכרחי ל A פירושו הוא <math>A \to B</math>
*כאשר אומרים ש B הוא תנאי מספיק ל A פירושו הוא <math>B \to A</math>
*כאשר אומרים ש B הוא תנאי הכרחי ומספיק ל A פירושו הוא <math>B \leftrightarrow A</math>

====תרגיל====
השלם את המשפט הבא: כדי שירד גשם _____ שיהיו עננים בשמים. לכן אם נסמן ע"י "יש עננים בשמים = A", "יורד גשם = B" נקבל "A____B".

פיתרון: הכרחי, <math>\leftarrow </math>

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

הגדרה: נאמר שביטוי <math>A</math> שקול טאוטולוגית לביטוי <math>B</math> (ונסמן <math>A \equiv B</math>)
אם הביטוי <math>A \leftrightarrow B</math> הינו טאוטולוגיה (במילים: A קורה אמ"מ B קורה)

====תכונות הקשרים====
* קיבוציות (אסוציאטיביות) - <math>(A\land B) \land C \equiv A\land (B \land C), (A\lor B) \lor C \equiv A\lor (B \lor C) </math>
* חילופיות (קומוטטיביות) - <math>A\land B \equiv B\land A, A\lor B \equiv B\lor A</math>
* פילוג (דיסטריביוטיביות) - <math>A\lor (B\land C)\equiv (A\lor B)\land (A\lor C), A\land (B\lor C)\equiv (A\land B)\lor (A\land C)</math>
* כללי דה מורגן - <math>\neg (A \lor B) \equiv \neg A \land \neg B, \neg (A \land B) \equiv \neg A \lor \neg B</math>.

====תרגיל====
האם המשפטים הבאים שקולים:

א. אם אייל שמח אז ענת גבוהה, ואם ענת גבוהה אז צחי חמוד.

ב. כאשר אייל שמח אז צחי חמוד.

פיתרון: לא, בעזרת הצרנה וטבלת אמת. אייל לא שמח, ענת גבוהה וצחי לא חמוד נותן <math>T</math> בשני ו<math>F</math> בראשון.

====תרגיל====
הוכח את הבאים:
* <math>A \equiv A</math>
* <math>\ (A\rightarrow B) \equiv ((\neg A) \vee B)</math>.
* <math>\ (A \leftrightarrow B) \equiv ((A \wedge B)\vee((\neg A)\wedge (\neg B)</math>.
* <math>\ (A \oplus B) \equiv \lnot(A \leftrightarrow B)</math>.
* <math>\ (A \rightarrow B) \equiv ((\neg B) \rightarrow (\neg A))</math>.

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

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

===טענת גרירה===
הביטוי <math>A\Rightarrow B</math> הוא טענת גרירה ופירושו: הפסוק <math>A\rightarrow B</math> הינו אמת. לכן:

1. כשנדרשים להוכיח משפט מהצורה הזו מה שצריך להראות זה שאם A נכון אז גם B נכון. או במילים אחרות: נניח שA נכון ונוכיח שגם B נכון.

2. כשנדרשים להפריך משפט מהצורה הזו מה שצריך להראות זה שיש השמת ערכי אמת למשתנים כל ש A נכון וB לא נכון.

====תרגיל====
רשום נכון או לא נכון:

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

ב. אם לא מנגן בחצוצרה אז לא מנגן בפסנתר.

מסקנה: לא מנגן בפסנתר אז מנגן בתופים.

פתרון: לא נכון: ניקח שקר בשלושתם (לא מנגן בכלום..) א+ב מקבלים ערך <math>T</math> והמסקנה <math>F</math>.

====תרגיל====
רשום נכון או לא נכון:

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

ב. אם לא מנגן בחצוצרה אז לא מנגן בפסנתר.

מסקנה: אם מנגן בפסנתר לא מנגן בתופים.

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

===דרכי הוכחה===
הוכח שהפסוקים הבאים הינם טאוטולוגיות:
*<math>(A\rightarrow B) \iff (\neg B \rightarrow \neg A)</math>
*<math>A \iff(\neg A \rightarrow F)</math>
*<math>(A\lor B) \iff(\neg A \rightarrow B)</math>

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

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

====תרגיל====
[https://en.wikipedia.org/wiki/Wason_selection_task ניסוי מפורסם] בפסיכולוגיה של החשיבה עוסק בקלפים שעל כל אחד מהם סימן בשני הצדדים - אות באחד הצדדים ומספר הצד האחר.

מניחים על השולחן ארבעה קלפים, שצידם החשוף מראה את הסימנים A, P, 2, 3. אילו כרטיסים יש להפוך על-מנת לבדוק את הטענה "אם בצד אחד של הכרטיס יש אות אהו"י (AEIOU), אז בצידו האחר יש מספר זוגי"? התשובה הנפוצה ביותר שאנשים השיבו הייתה שיש להפוך את הכרטיסים הראשון והשלישי (אחרים ענו רק את הכרטיס הראשון). מדוע, לדעתך? ומה התשובה הנכונה?