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