1. תהא נוסחה בוליאנית מצורת 5CNF בעלת m הסגרים, שבכל אחד מהם מופיעים חמישה משתנים שונים, ב…

שאלה פתוחהq-57407b5958ac

נוסח השאלה

תהא $\varphi$ $φ$ נוסחה בוליאנית מצורת $5CNF$ $5 C N F$ בעלת $m$ $m$ הסגרים, שבכל אחד מהם מופיעים חמישה משתנים שונים, בחיוב או בשלילה.
1. חשבו את תוחלת מספר ההסגרים המסופקים בנוסחה $\varphi$ על ידי השמה מקרית מהתפלגות אחידה.
2. חשבו את תוחלת מספר ההסגרים המסופקים במובן $NAE$ בנוסחה $\varphi$ על ידי השמה מקרית מהתפלגות אחידה.
3. נסחו טענות "קיום" שנובעות משני הסעיפים הקודמים ונמקו אותן.
4. כיצד היו משתנות התשובות אם היה נתון שבכל הסגר של $\varphi$ מופיעים חמישה ליטרלים שונים — אך לא בהכרח חמישה משתנים שונים — ושמספר ההסגרים שבהם מופיעים משתנה ושלילתו הוא $m_0$ ?
יהא $G=(V,E)$ גרף פשוט. מגרילים מהתפלגות אחידה צביעה מקרית של קודקודי $G$ ב- $10$ צבעים. מהי תוחלת מספר הקשתות בגרף $G$ המחברות שני קודקודים בעלי צבעים שונים לפי צביעה זו? נסחו טענת "קיום" שנובעת מהחישוב ונמקו אותה.
הוכיחו כי לכל $n$ טבעי קיים גרף תחרות על $n$ קודקודים שבו לפחות $\frac{n!}{2^{n-1}}$ מסלולי המילטון.

נוסח מטלה שנבדק אנושית.

ייחוס מדויק

כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.

מטלה

2025_06_תרגיל_6.md

שאלה 2עמוד 1נבדק אנושית

1 עמודים

העמודים נבחרו לפי חפיפת מילים בין הטקסט כאן לתמלול העמוד — לא אומתו ידנית. הם הצעה לבדיקה, לא ציטוט.

שיעור 26 · עמוד 5תרגילים
מילים משותפותחשבו · המסופקים · במובן · מקרית · אחידה · נסחו