83-116 בדידה להנדסה סמסטר א' תשע"ט

83-116 בדידה להנדסה

שעות קבלה

• אריאל: יום חמישי 12-13, בתיאום במייל, relweiz@gmail.com
• עומר: בתיאום במייל, omernete@gmail.com

קישורים

• מערכי תרגול

• מבחנים ובחנים משנים קודמות

הודעות

תרגולי השלמה ביום שני, ב' טבת, 10.12, יתקיימו כדלהלן: הקבוצה של עומר והקבוצה של אריאל בראשון בבוקר בכיתה 53 עם עומר יחסים ויחסי שקילות. הקבוצות של אריאל בראשון ערב ושלישי בכיתה 2 אינדוקציה ויחסים כמה שנספיק..

השלמת מה שלא הספקנו בתרגול

שאלה

תהי $f:\mathbb{Z}_a\to \mathbb{Z}_b$ המוגדרת ע"י $f([k]_a)=[k]_b$ (עבור $a,b\geq 2$). מה הקריטריון לכך שהיא פונקציה?

במסגנון אחר: תהי $f:\mathbb{Z}\to \mathbb{Z}_b$ פונקציה המוגדרת ע"י $f(k)=[k]_b$ (עבור $a,b\geq 2$). מה הקריטריון לכך שהיא מוגדרת היטב על קבוצת המנה $\mathbb{Z}_a$?

תשובה

נלך לפי הסגנון השני, ונטען: $f$ מוגדרת היטב על קבוצת המנה $\mathbb{Z}_a$ אם ורק אם $b|a$ (כלומר, קיים $m\in \mathbb{Z}:a=mb$). הוכחה:

משמאל לימין: נניח שאכן $b|a$ (כלומר, $\exists m\in \mathbb{Z}:a=mb$), ונוכיח שהיא מוגדרת היטב, כלומר שהיא מכבדת את יחס השקילות מודולו $a$. ניזכר ביחס השקילות מודולו $a$ שאומר שלכל $k_1,k_2\in \mathbb{Z}$ מתקיים: $k_1 \stackrel{a}{\sim} k_2\iff a|k_1-k_2$, ומה שצריך להוכיח זה שאם $k_1 \stackrel{a}{\sim} k_2$ אז $f(k_1)=f(k_2)$. לפי ההגדרה $f(k_1)=[k_1]_b,f(k_2)=[k_2]_b$, ולכן מה שצריך להוכיח זה את שיוויון מחלקות השקילות. אבל שתי מחלקות שקילות שוות אם ורק אם הנציגים שקולים, לכן מה שצריך להוכיח זה ש $k_1 \stackrel{b}{\sim} k_2$ שזה שקול ללהוכיח $b|k_1-k_2$. נסכם: נתון לנו ש $b|a$, ובנוסף הנחנו ש- $k_1 \stackrel{a}{\sim} k_2$ כלומר, $a|k_1-k_2$. וצריך להוכיח $b|k_1-k_2$. הדבר נובע ישירות מכך שהיחס "מחלק את" הוא טרנזיטיבי: אם $b|a$ אז $\exists m\in \mathbb{Z}:a=mb$, ואם $a|k_1-k_2$ אז $\exists t\in \mathbb{Z}:k_1-k_2=ta$, ולכן בסה"כ: $\exists tm\in \mathbb{Z}:k_1-k_2=(tm)\cdot b$ מה שאומר $b|k_1-k_2$.

מימין לשמאל: נלך בשיטה של להוכיח אם לא שמאל אז לא ימין. נניח ש$b$ לא מחלק את $a$ ונראה שהפונקציה לא מכבדת את יחס השקיילות מודולו $a$. מהעובדה ש$b$ לא מחלק את $a$ נובע ש-$a$ לא שקול ל$0$ מודולו $b$. אבל כמובן $a$ שקול ל$0$ מודולו $a$, ולכן מצאנו שני מספרים שקולים מודולו $a$ כלומר, $a \stackrel{a}{\sim} 0$, שהפונקציה שולחת אותם לשני איברים שונים: $f(a)=[a]_b\neq [0]_b=f(0)$, ולכן הפונקציה לא מכבדת את יחס השקילות.

תרגילי בית

• המלצה חשובה - נסו לפתור את תרגילי ה-XI לבד לפני שאתם מסתכלים בהדרכה של המערכת!!

מטלות תרגול ממוחשבות XI: בקישור. ברשימת הקורסים בקישור תמצאו את הקורס שלנו, יש להרשם עם חשבון גוגל. נא להכניס תעודת זהות בעת ההרשמה! את המטלות יש להגיש באופן ממוחשב עד שבועיים מיום העלאת התרגיל. בשקלול הציון יכנסו כ-80% מהציונים הטובים ביותר.

תרגילים ידניים

• התרגילים שיופיעו כאן אינם להגשה, ואין עליהם ציון. מטרתם תרגול החומר בנוסף למטלות הממוחשבות. בהצלחה!
• תרגיל 1, פתרון
• תרגיל 2, פתרון שאלות האינדוקציה מיועדות לשבוע הבא, אחרי שנלמד אינדוקציה.
• תרגיל 3, פתרון (התעלמו משאלה 3 סעיף ה, כי כשעוברים לקבוצת החזקה, אז $U$ לאו דוקא מכילה אותה).
• תרגיל 4, פתרון
• תרגיל 5, פתרון
• תרגיל 6, פתרון
• תרגיל 7, פתרון
• עוד תרגיל על יחסי שקילות, פתרון

בוחן

הבוחן יתקיים ביום רביעי, כ' בכסלו, 28.11 בשעות 16:00-18:00.

החומר לבוחן: לוגיקה (טבלאות אמת, שקילויות לוגיות, כמתים, פרדיקטים), וקבוצות (עד הגדרת איחוד, חיתוך, הפרש והפרש סימטרי).

• ציוני הבוחן
• פתרון

בהצלחה!