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