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