בהוכחת משפט קוק-לוין שראינו בשיעור, ייצגנו ריצה של מכונה M על קלט (x,w) על ידי טבלה TM,x. במהלך ההוכחה, בנינו…

בהוכחת משפט קוק-לוין שראינו בשיעור, ייצגנו ריצה של מכונה M על קלט (x,w) על ידי טבלה TM,x. במהלך ההוכחה, בנינו טבלאות אמת עבור תאים בטבלה TM,x והמרנו אותן לצורת CNF. נניח שמצבי המכונה M הם Q = {0 ... 5} וא"ב העבודה של M הוא $. Γ={0,1,B}$ השאלה היא לגבי טבלת האמת עבור התא השמאלי ביותר בשורה השנייה בשורה הראשונה של TM,x (השורה שמייצגת את הקונפיגורציה ההתחלתית): מה מספר השורות בטבלת אמת זו שערכם הוא 0 (כלומר False)?