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

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

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

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