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