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