האוניברסיטה הפתוחה · קורס 20476
פתרון מבחן — מתמטיקה בדידה
- סמסטר2025ג
- מועד ב
- קשה
נושאים:לוגיקה · עוצמות · עצים מתויגים (פרופר) · יחסי שקילות · פונקציות יוצרות · קומבינטוריקה (פיזורים) · מישוריות (קורטובסקי) · מעגלי המילטון ואוילר · גרף הקשתות
6שאלות
מצב סימולציה: פתרו כל שאלה בעצמכם, חשפו את התשובה, וסמנו אם צדקתם. ההתקדמות נשמרת במכשיר שלכם.
0/6 נבדקו
שאלה 1
4/5סעיף א (6 נק'): נתון ש- פסוקים פורמליים (לאו דווקא משתנים פסוקיים!) וש- גורר טאוטולוגית את . אזי:[1] מהנתון נובע, כי גורר טאוטולוגית את ;[2] מהנתון נובע, כי גורר טאוטולוגית את ;[3] מהנתון נובע, כי גורר טאוטולוגית את ;[4] אף אחת מהטענות [1]–[3] אינה נכונה.
(תוכלו להיעזר בעובדה הבאה: אם הוא לוח אמת המאוחד של פסוקים , אז: גורר טאוטולוגית את אם"ם מתקיים התנאי הבא: הוא אמת בכל שורה ב- שבה אמת.)
סעיף ב (7 נק'): תהי קבוצת כל הפונקציות שעבורן הקבוצה סופית. אזי:[1] ;[2] ;[3] ;[4] אף אחת מהטענות [1]–[3] אינה נכונה. (רמז: חשבו על קבוצת כל הסדרות מהצורה המקיימות . מהי עוצמתה? ומה הקשר לשאלה שלעיל?)
סעיף ג (6 נק'): נתבונן בתנאים הבאים על עץ מתויג : התגים של הם ; צמתי שתגיהם הם עלים ב-; לצמתים שתגיהם יש שכן משותף ב-, וגם לצמתים שתגיהם יש שכן משותף ב-. יהי מספר העצים המתויגים המקיימים את התנאים –, כאשר עצים מתויגים איזומורפיים (במובן של הגדרה 2.8) נחשבים זהים. אזי:[1] ;[2] ;[3] ;[4] ;[5] אף אחת מהטענות [1]–[4] אינה נכונה.
שאלה 2
4/5סעיף א (9 נק'): הוכיחו כי הוא יחס שקילות על .
סעיף ב: יהיו שונות. (1, 5 נק') יהי המספר הטבעי המינימלי ששייך לאחת בדיוק מבין הקבוצות . הוכיחו כי אחד המספרים קטן ב- מהשני. (2, 4 נק') האם מתקיים ? נמקו.
סעיף ג (9 נק'): תהי קבוצת מחלקות השקילות של . מהי ? הוכיחו את תשובתכם.
שאלה 3
4/5סעיף ב (15 נק'): מצאו את מספר הפתרונות במספרים טבעיים למשוואה המקיימים את התנאים (i)–(iii). תנו תשובה מספרית. נמקו. הערות: 1) זכרו כי הוא מספר טבעי. 2) הנוסחה עשויה לעזור כאן.
שאלה 4
4/5סעיף א (13 נק'): מהו מספר הפיזורים האפשריים של הכדורים בתאים, שבהם שניים מהתאים מכילים כדורים לבנים (אחד לפחות בכל אחד מהם), ושניים מהתאים ריקים?
סעיף ב (14 נק'): מהו מספר הפיזורים האפשריים, שבהם כל תא שמכיל כדור צבעוני מכיל גם כדור לבן אחד לפחות? (ניתן לפתור סעיף זה על-ידי התייחסות למספר מקרים שונים, שאחד מהם טופל כבר בסעיף א'.)
שאלה 5
5/5סעיף א (9 נק'): הוכיחו כי אינו מכיל, כתת-גרף, העדנה של .
סעיף ב (9 נק'): הוכיחו כי ל- יש תת-גרף פורש, המהווה העדנה של .
סעיף ג (9 נק'): הוכיחו כי המילטוני. תוכלו להיעזר בטענה הבאה מבלי להוכיח אותה: לכל קשת של , יש מעגל המילטון ב- כך ש- מופיעה ב-.
שאלה 6
4/5סעיף א (9 נק'): הוכיחו: אם אוילרי, אז המילטוני.
סעיף ב (9 נק'): הפריכו את הטענה הבאה בעזרת דוגמה נגדית: לכל גרף , אם המילטוני, אז אוילרי. הקפידו להראות, כי הדוגמה שנתתם היא אכן דוגמה נגדית לטענה הנתונה.
סעיף ג (9 נק'): הוכיחו: אם גרף פשוט ויש צומת שדרגתו ב- היא לפחות , אז אינו מישורי. תוכלו להסתמך על הטענה הבאה מבלי להוכיח אותה: כל תת-גרף של גרף מישורי הוא גרף מישורי.