הוכיחו שבעיות ההכרעה הבאות שייכות ל-P. 1. קלט: נוסחה בוליאנית מצורת 1CNF. שאלה: האם ספיקה?…

שאלה פתוחהq-7c6810c83d5a

נוסח השאלה

הוכיחו שבעיות ההכרעה הבאות שייכות ל- $P$ .

קלט: נוסחה בוליאנית $\varphi$ מצורת $1CNF$ .
שאלה: האם $\varphi$ ספיקה?
קלט: נוסחה בוליאנית $\varphi$ מצורת $CNF$ .
שאלה: האם קיימת השמה שנותנת ערך $True$ ל-10 משתנים בדיוק ומספקת את $\varphi$ ?
קלט: נוסחה בוליאנית $\varphi$ מצורת $DNF$ - נוסחה המורכבת מפסוקיות שביניהן הקשר "או", כאשר בכל פסוקית רשימת ליטרלים שביניהם הקשר "וגם".
שאלה: האם $\varphi$ ספיקה?
קלט: נוסחה בוליאנית $\varphi$ מצורת $CNF$ .
שאלה: האם כל השמה מספקת את $\varphi$ ?
קלט: נוסחה בוליאנית $\varphi$ מצורת $3CNF$ , שבכל פסוקית שלה מופיעים שלושה משתנים שונים בדיוק, וכל משתנה מופיע בשלוש פסוקיות בדיוק.
שאלה: האם $\varphi$ ספיקה?

הדרכה לסעיף 5: עבור נוסחת הקלט $\varphi$ , הגדירו גרף דו-צדדי והשתמשו במשפט Hall.

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

Exact provenance

Each card is a genuinely distinct file. Printed versions inside one PDF stay in that card and do not inflate the sitting count.

Assignment

2024_02_תרגיל_2.md

Question 1Page 1Human reviewed