שאלת מבחן בלוגיקה למדעי המחשב - האוניברסיטה הפתוחה 2024 - תחשיב הפסוקים

השאלה בתחשיב הפסוקים. $\Sigma$ קבוצת פסוקים בשפה $L = \{ \to \}$ שבה רק קשר דו מקומי אחד. $R_\Sigma$ - קבוצת פסוקים בשפה שהמבנה שלהם הוא $(p \to \alpha)$ $p$ - הוא פסוק אלמנטארי ו-$\alpha$ פסוק כל שהוא. הקבוצה $R_\Sigma$ נקראת "קבוצת הפסוקים הימניים של $\Sigma$". הוכיחו או הפריכו כל אחת מהטענות הבאות: א. אם $\varphi$ פסוק ימני של $\Sigma$ אז $\Sigma \models \varphi$. ב. אם $\varphi$ פסוק ימני של $\Sigma$ אז $\Sigma \vdash \varphi$.

רמז: שימו לב היטב להגדרת "קבוצת הפסוקים הימניים של $\Sigma$". מה ניתן להסיק מכך שפסוק $\varphi$ שייך לקבוצה זו על יחסו לקבוצה $\Sigma$ עצמה?

פתרון: לפני שנוכיח או נפריך את הטענות, נבהיר את פירוש המונח "קבוצת הפסוקים הימניים של $\Sigma$". על פי ניסוח השאלה, אנו מפרשים את $R_\Sigma$ כקבוצת כל הפסוקים **השייכים ל-$\Sigma$** שהם מהצורה $(p \to \alpha)$, כאשר $p$ הוא פסוק אטומרי ו-$\alpha$ היא נוסחה כלשהי. כלומר: $R_\Sigma = \{ \psi \in \Sigma \mid \psi \text{ is of the form } (p \to \alpha) \text{ for some atomic } p \text{ and formula } \alpha \}$. מפירוש זה נובע שאם $\varphi \in R_\Sigma$, אז בהכרח $\varphi \in \Sigma$. **א. אם $\varphi$ פסוק ימני של $\Sigma$ אז $\Sigma \models \varphi$.** **הטענה נכונה.** **הוכחה:** נניח כי $\varphi$ הוא פסוק ימני של $\Sigma$. על פי ההגדרה, משמעות הדבר היא ש-$\varphi \in R_\Sigma$. על פי הפירוש שלנו להגדרת הקבוצה $R_\Sigma$, אם $\varphi \in R_\Sigma$ אז בפרט $\varphi \in \Sigma$. כדי להוכיח כי $\Sigma \models \varphi$, עלינו להראות שלכל השמה (או מודל) $v$, אם $v$ מספקת את כל הפסוקים ב-$\Sigma$ (כלומר $v \models \Sigma$), אז $v$ מספקת גם את $\varphi$ (כלומר $v \models \varphi$). תהי $v$ השמה כלשהי המקיימת $v \models \Sigma$. המשמעות של $v \models \Sigma$ היא שלכל פסוק $\psi \in \Sigma$, מתקיים $v(\psi) = T$. מכיוון שהסקנו כי $\varphi \in \Sigma$, נובע ישירות מהנחה זו כי $v(\varphi) = T$. כלומר, $v \models \varphi$. הראינו כי לכל השמה $v$ המקיימת את $\Sigma$, היא מקיימת גם את $\varphi$. לכן, על פי הגדרת ה**נביעה הסמנטית**, מתקיים $\Sigma \models \varphi$. $\blacksquare$ **ב. אם $\varphi$ פסוק ימני של $\Sigma$ אז $\Sigma \vdash \varphi$.** **הטענה נכונה.** **הוכחה:** נניח כי $\varphi$ הוא פסוק ימני של $\Sigma$. כפי שצוין בסעיף א', מכך נובע כי $\varphi \in \Sigma$. כדי להוכיח כי $\Sigma \vdash \varphi$, עלינו להראות שקיימת **הוכחה פורמלית** של $\varphi$ מההנחות שב-$\Sigma$. בכל מערכת הוכחה סטנדרטית, **הוכחה פורמלית** מקבוצת הנחות $\Sigma$ היא סדרה סופית של נוסחאות, שבה כל נוסחה היא או אקסיומה, או אחת ההנחות מ-$\Sigma$, או נובעת מנוסחאות קודמות בסדרה באמצעות כללי היסק. נבנה הוכחה פורמלית של $\varphi$ מ-$\Sigma$ באופן הבא: ההוכחה היא הסדרה בת איבר אחד: $\langle \varphi \rangle$. סדרה זו היא הוכחה פורמלית חוקית, משום ש: 1. היא סדרה סופית (באורך 1). 2. הנוסחה האחרונה בה היא $\varphi$. 3. השורה היחידה בה, $\varphi$, מוצדקת מכיוון שהיא שייכת לקבוצת ההנחות $\Sigma$. מכיוון שבנינו הוכחה פורמלית של $\varphi$ מ-$\Sigma$, הרי שעל פי הגדרת ה**נביעה הסינטקטית**, מתקיים $\Sigma \vdash \varphi$. $\blacksquare$