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