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

השאלה בתחשיב היחסים. א. האם הפסוק הבא אמיתי בכל מודל? אם כן הוכיחו אם לא תנו דוגמא נגדית. $\varphi = (R(c) \land \forall x(R(x) \to R(f(x)))) \to \forall x R(x)$ ב. נתונה השפה $L = \{<, 1\}, (x<y)$ נתון מודל $M$ שתחומו $N$ - קבוצת המספרים הטבעיים. נתון הפסוק הבא: $\varphi = \exists y(1<y)$. $M$ הוא מודל של $\varphi$. האם כל תת מודל של $M$ הוא גם מודל של הפסוק $\varphi$? נמקו את תשובתכם.

רמז: א. הרישא של הפסוק מבטיחה שהיחס $R$ מתקיים עבור $c, f(c), f(f(c)), \ldots$. בנו מודל עם איבר שאינו שייך לסדרת איברים זו. ב. "עד" (witness) לקיום בפסוק קיומי עשוי להתקיים במודל הגדול, אך לא בהכרח בתת-מודל. בנו תת-מודל המכיל את הקבוע 1, אך לא מכיל אף איבר הגדול ממנו.

פתרון: א. הפסוק אינו אמיתי בכל מודל (כלומר, אינו **תקף**). כדי להראות זאת, נציג דוגמה נגדית – **מודל** $M$ שבו הפסוק שקרי. נגדיר את המודל $M$ באופן הבא: - **תחום (Domain):** $D_M = \{a, b\}$ - **פירושים (Interpretations):** - $c^M = a$ - $f^M(a) = a, \quad f^M(b) = a$ - $R^M = \{a\}$ כעת, נראה כי במודל $M$ הפסוק $\varphi = (R(c) \land \forall x(R(x) \to R(f(x)))) \to \forall x R(x)$ הוא שקרי. לשם כך, עלינו להראות שהרישא של הגרירה אמיתית ב-$M$, והסיפא שקרית ב-$M$. 1. **בדיקת הרישא:** $R(c) \land \forall x(R(x) \to R(f(x)))$ - **בדיקת $R(c)$:** הפירוש של $c$ הוא $c^M = a$. מכיוון ש-$a \in R^M$, הפסוק $R(c)$ אמיתי ב-$M$. - **בדיקת $\forall x(R(x) \to R(f(x)))$:** עלינו לבדוק את התנאי לכל איבר בתחום $D_M$. - עבור $x=a$: האיבר $a \in R^M$, לכן עלינו לוודא שגם $f^M(a) \in R^M$. לפי הגדרתנו, $f^M(a) = a$, ואכן $a \in R^M$. לכן הגרירה $R(a) \to R(f(a))$ אמיתית. - עבור $x=b$: האיבר $b \notin R^M$. לכן, הרישא של הגרירה $R(b) \to R(f(b))$ שקרית, ועל כן הגרירה כולה אמיתית (בלי תלות בערך של $R(f(b))$). מכיוון שהנוסחה הפנימית $(R(x) \to R(f(x)))$ אמיתית עבור כל איבר בתחום, הפסוק $\forall x(R(x) \to R(f(x)))$ אמיתי ב-$M$. מאחר ושני חלקי הרישא אמיתיים ב-$M$, הרישא כולה אמיתית ב-$M$. 2. **בדיקת הסיפא:** $\forall x R(x)$ - הפסוק טוען שכל האיברים בתחום מקיימים את התכונה $R$. ניקח את האיבר $b \in D_M$. לפי הגדרתנו, $b \notin R^M$. לכן, הטענה אינה נכונה עבור כל האיברים, והפסוק $\forall x R(x)$ שקרי ב-$M$. **מסקנה:** מצאנו מודל $M$ שבו הרישא של $\varphi$ אמיתית והסיפא שקרית. לכן, הפסוק $\varphi$ כולו שקרי במודל זה, ואינו תקף. $\blacksquare$ --- ב. התשובה היא לא. לא כל תת-מודל של $M$ הוא גם מודל של הפסוק $\varphi$. **נימוק:** ראשית, נגדיר מהו **תת-מודל** בהקשר זה. יהי $M'$ תת-מודל של $M$. התחום של $M'$, שנסמנו $D_{M'}$, חייב להיות תת-קבוצה של התחום של $M$, כלומר $D_{M'} \subseteq \mathbb{N}$. כמו כן, מכיוון שהשפה $L$ מכילה את סמל הקבוע '1', הפירוש של קבוע זה במודל $M$ חייב להיות איבר בתחום של תת-המודל $M'$. במקרה שלנו, $1^M = 1$, ולכן חייב להתקיים $1 \in D_{M'}$. הפסוק $\varphi = \exists y(1<y)$ הוא אמיתי במודל $M'$ אם קיים "עד" (witness) בתחום של $M'$, כלומר איבר $d \in D_{M'}$ כך שהתנאי $1<d$ מתקיים. כעת נבנה דוגמה נגדית – תת-מודל $M'$ של $M$ שאינו מקיים את $\varphi$. נגדיר את תת-המודל $M'$ כך: - **תחום:** $D_{M'} = \{1\}$. תחום זה הוא אכן חוקי, מכיוון ש-$D_{M'} \subseteq \mathbb{N}$ וגם $1 \in D_{M'}$. כעת נבדוק את אמיתות הפסוק $\varphi = \exists y(1<y)$ במודל $M'$. הפסוק אמיתי ב-$M'$ אם ורק אם קיים איבר $d \in D_{M'} = \{1\}$ כך ש-$1<d$. האיבר היחיד שניתן לבדוק בתחום $D_{M'}$ הוא $d=1$. היחס $1<1$ הוא שקרי. מכיוון שלא קיים אף איבר בתחום $D_{M'}$ המקיים את התנאי, הפסוק הקיומי $\exists y(1<y)$ הוא שקרי במודל $M'$. לפיכך, מצאנו תת-מודל $M'$ של $M$ שאינו מודל של $\varphi$. $\blacksquare$