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