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

קורס: לוגיקה למדעי המחשב

אוניברסיטה: האוניברסיטה הפתוחה

שנה: 2024

סמסטר: ב

נושאים: תחשיב הפסוקים, נוסחאות, הוכח או הפרך, דרגת נוסחה

רמת קושי: בינוני

השאלה בשפת הפסוקים. הוכיחו או הפריכו כל אחת מהטענות הבאות: א. אם $\varphi$ הוא פסוק אז $\varphi\varphi$ אינו פסוק. ב. קיים פסוק $\varphi$ כך שיש לו 4 קשרים דו מקומיים ושדרגתו היא 2.

רמז: א. פסוק שאינו משתנה פסוקי חייב להיות מהצורה $(\neg \psi)$ או $(\psi \circ \chi)$. נתחו את המבנה של $\varphi\varphi$ לאור הגדרה זו. ב. הגדירו את דרגת הפסוק באופן רקורסיבי ומצאו חסם עליון למספר הקשרים הדו-מקומיים בפסוק מדרגה נתונה.

פתרון: א. הטענה **נכונה**. נוכיח כי אם $\varphi$ הוא פסוק (נוסחה בנויה כהלכה, well-formed formula), אז השרשור $\varphi\varphi$ אינו פסוק. הגדרת פסוק בתחשיב הפסוקים היא רקורסיבית: 1. **בסיס:** כל משתנה פסוקי ($p, q, r, \dots$) הוא פסוק. 2. **צעד רקורסיבי:** * אם $\psi$ הוא פסוק, אז $(\neg \psi)$ הוא פסוק. * אם $\psi$ ו-$\chi$ הם פסוקים, ו-$\circ$ הוא קשר לוגי דו-מקומי ($\land, \lor, \to, \iff$), אז $(\psi \circ \chi)$ הוא פסוק. אחד המאפיינים החשובים של הגדרה זו הוא **עקרון הקריאות היחידה**, שמשמעותו היא שלכל פסוק יש דרך פירוק אחת בלבד. כל פסוק שאינו משתנה פסוקי הוא מהצורה $(\neg \psi)$ או $(\psi \circ \chi)$, כלומר הוא מתחיל בסוגר פותח `(` ומסתיים בסוגר סוגר תואם `)`. נניח בשלילה שקיים פסוק $\varphi$ כך שגם $\varphi\varphi$ הוא פסוק. נבחר $\varphi$ כזה בעל אורך מינימלי. * **אם $\varphi$ הוא משתנה פסוקי**, למשל $p$, אז $\varphi\varphi = pp$. מחרוזת זו אינה משתנה פסוקי, ואינה מתחילה בסוגר פותח, ולכן אינה יכולה להיות פסוק מהצורה $(\neg \psi)$ או $(\psi \circ \chi)$. לכן $pp$ אינו פסוק. זו סתירה. * **אם $\varphi$ אינו משתנה פסוקי**, אז הוא חייב להיות מהצורה $(\neg \psi)$ או $(\psi \circ \chi)$. בכל מקרה, $\varphi$ הוא מחרוזת המתחילה ב-`(` ומסתיימת ב-`)`. המחרוזת $\varphi\varphi$ היא שרשור של שתי מחרוזות כאלו, למשל $(\dots)(\dots)$. כדי ש-$\varphi\varphi$ יהיה פסוק, הוא חייב להתאים לאחת מצורות הבנייה. מכיוון שהוא מתחיל ב-`(` הוא אינו יכול להיות משתנה פסוקי. האם $\varphi\varphi$ יכול להיות מהצורה $(\alpha \circ \beta)$? בצורה זו, הסוגר הפותח בהתחלה מתאים לסוגר הסוגר בסוף המחרוזת. אולם, במחרוזת $\varphi\varphi$, החלק הראשון, $\varphi$, הוא פסוק בפני עצמו, ולכן הסוגריים שלו "מאוזנים". כלומר, הסוגר הפותח בתחילת $\varphi$ נסגר על ידי הסוגר הסוגר בסוף $\varphi$. למשל, אם $\varphi = (p \to q)$, אז $\varphi\varphi = (p \to q)(p \to q)$. הסוגר הראשון נסגר אחרי ה-$q$ הראשון. לכן, אין קשר ראשי $\circ$ אשר נמצא בין שני תת-פסוקים $\alpha$ ו-$\beta$ המרכיבים את *כל* המחרוזת $\varphi\varphi$. למעשה, אחרי תת-הפסוק הראשון $\varphi$, לא מופיע קשר דו-מקומי אלא סוגר פותח `(`, שמתחיל את המופע השני של $\varphi$. מאותה סיבה, $\varphi\varphi$ אינו יכול להיות מהצורה $(\neg \alpha)$. בכל מקרה הגענו לסתירה. לכן, ההנחה הראשונית שגויה, ולא קיים פסוק $\varphi$ כך ש-$\varphi\varphi$ הוא פסוק. $\blacksquare$ ב. הטענה **אינה נכונה**. נוכיח כי לא קיים פסוק בעל 4 קשרים דו-מקומיים ודרגה 2. ראשית, נגדיר במדויק את מושג ה**דרגה** של פסוק $\varphi$, שאותה נסמן $R(\varphi)$: 1. אם $p$ הוא משתנה פסוקי, $R(p) = 0$. 2. אם $\varphi = (\neg \psi)$, אז $R(\varphi) = R(\psi)$. 3. אם $\varphi = (\psi \circ \chi)$, כאשר $\circ$ קשר דו-מקומי, אז $R(\varphi) = 1 + \max(R(\psi), R(\chi))$. בנוסף, נסמן ב-$C(\varphi)$ את מספר הקשרים הדו-מקומיים בפסוק $\varphi$. כעת נוכיח טענת עזר (למה) הקושרת בין דרגת הפסוק למספר הקשרים הדו-מקומיים שבו. **למה:** לכל פסוק $\varphi$, מתקיים $C(\varphi) \le 2^{R(\varphi)} - 1$. **הוכחת הלמה (באינדוקציה על מבנה הפסוק):** * **בסיס האינדוקציה:** $\varphi$ הוא משתנה פסוקי $p$. במקרה זה, $C(p) = 0$ ו-$R(p) = 0$. נציב באי-השוויון: $0 \le 2^0 - 1 = 1 - 1 = 0$. הטענה נכונה עבור הבסיס. * **צעד האינדוקציה:** נניח שהטענה נכונה עבור פסוקים $\psi, \chi$ (הנחת האינדוקציה), ונוכיח עבור פסוק $\varphi$ הנבנה מהם. * **מקרה 1:** $\varphi = (\neg \psi)$. $C(\varphi) = C(\psi)$ ו-$R(\varphi) = R(\psi)$. לפי הנחת האינדוקציה על $\psi$, מתקיים $C(\psi) \le 2^{R(\psi)} - 1$. לכן, $C(\varphi) \le 2^{R(\varphi)} - 1$, והטענה נכונה. * **מקרה 2:** $\varphi = (\psi \circ \chi)$. $C(\varphi) = 1 + C(\psi) + C(\chi)$. $R(\varphi) = 1 + \max(R(\psi), R(\chi))$. נסמן $M = \max(R(\psi), R(\chi))$. לפי הנחת האינדוקציה על $\psi$ ו-$\chi$: $C(\psi) \le 2^{R(\psi)} - 1$ $C(\chi) \le 2^{R(\chi)} - 1$ נשתמש בחסמים אלו: $$ C(\varphi) = 1 + C(\psi) + C(\chi) \le 1 + (2^{R(\psi)} - 1) + (2^{R(\chi)} - 1) = 2^{R(\psi)} + 2^{R(\chi)} - 1 $$ מכיוון ש-$R(\psi) \le M$ ו-$R(\chi) \le M$, אז $2^{R(\psi)} \le 2^M$ ו-$2^{R(\chi)} \le 2^M$. $$ C(\varphi) \le 2^M + 2^M - 1 = 2 \cdot 2^M - 1 = 2^{M+1} - 1 $$ ומאחר ש-$R(\varphi) = M+1$, קיבלנו $C(\varphi) \le 2^{R(\varphi)} - 1$. הטענה נכונה גם במקרה זה. הוכחנו את הלמה באינדוקציה. $\blacksquare$ **הפרכת הטענה המקורית:** הטענה המקורית היא שקיים פסוק $\varphi$ המקיים $C(\varphi) = 4$ ו-$R(\varphi) = 2$. לפי הלמה שהוכחנו, כל פסוק $\varphi$ חייב לקיים $C(\varphi) \le 2^{R(\varphi)} - 1$. נציב את הנתונים של הפסוק ההיפותטי באי-השוויון: $$ 4 \le 2^2 - 1 $$ $$ 4 \le 4 - 1 $$ $$ 4 \le 3 $$ קיבלנו סתירה. מכאן שלא ייתכן קיומו של פסוק כזה. לכן, הטענה המקורית מופרכת. $\blacksquare$

השאלה בשפת הפסוקים.

הוכיחו או הפריכו כל אחת מהטענות הבאות:
א. אם

φ

הוא פסוק אז

φφ

אינו פסוק.
ב. קיים פסוק

φ

כך שיש לו 4 קשרים דו מקומיים ושדרגתו היא 2.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד 81 · 2024 · סמסטר ב

★★★★★

תחשיב הפסוקיםנוסחאותהוכח או הפרךדרגת נוסחה

א. פסוק שאינו משתנה פסוקי חייב להיות מהצורה

(\neg ψ)

או

(ψ \circ χ)

. נתחו את המבנה של

φφ

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

א. הטענה נכונה.
נוכיח כי אם

φ

הוא פסוק (נוסחה בנויה כהלכה, well-formed formula), אז השרשור

φφ

אינו פסוק.

הגדרת פסוק בתחשיב הפסוקים היא רקורסיבית:
1. בסיס: כל משתנה פסוקי (

p, q, r, \dots

) הוא פסוק.
2. צעד רקורסיבי:

אם $ψ$ הוא פסוק, אז $(\neg ψ)$ הוא פסוק.
אם $ψ$ ו- $χ$ הם פסוקים, ו- $\circ$ הוא קשר לוגי דו-מקומי ( $\land, \lor, \to, ⟺$ ), אז $(ψ \circ χ)$ הוא פסוק.

אחד המאפיינים החשובים של הגדרה זו הוא עקרון הקריאות היחידה, שמשמעותו היא שלכל פסוק יש דרך פירוק אחת בלבד. כל פסוק שאינו משתנה פסוקי הוא מהצורה

(\neg ψ)

או

(ψ \circ χ)

, כלומר הוא מתחיל בסוגר פותח ( ומסתיים בסוגר סוגר תואם ).

נניח בשלילה שקיים פסוק

φ

כך שגם

φφ

הוא פסוק.
נבחר

φ

כזה בעל אורך מינימלי.

אם $φ$ הוא משתנה פסוקי, למשל $p$ , אז $φφ = pp$ . מחרוזת זו אינה משתנה פסוקי, ואינה מתחילה בסוגר פותח, ולכן אינה יכולה להיות פסוק מהצורה $(\neg ψ)$ או $(ψ \circ χ)$ . לכן $pp$ אינו פסוק. זו סתירה.

אם $φ$ אינו משתנה פסוקי, אז הוא חייב להיות מהצורה $(\neg ψ)$ או $(ψ \circ χ)$ . בכל מקרה, $φ$ הוא מחרוזת המתחילה ב-( ומסתיימת ב-).

המחרוזת

φφ

היא שרשור של שתי מחרוזות כאלו, למשל

(\dots) (\dots)

.
כדי ש-

φφ

יהיה פסוק, הוא חייב להתאים לאחת מצורות הבנייה. מכיוון שהוא מתחיל ב-( הוא אינו יכול להיות משתנה פסוקי.
האם

φφ

יכול להיות מהצורה

(α \circ β)

?
בצורה זו, הסוגר הפותח בהתחלה מתאים לסוגר הסוגר בסוף המחרוזת.
אולם, במחרוזת

φφ

, החלק הראשון,

φ

, הוא פסוק בפני עצמו, ולכן הסוגריים שלו "מאוזנים". כלומר, הסוגר הפותח בתחילת

φ

נסגר על ידי הסוגר הסוגר בסוף

φ

.
למשל, אם

φ = (p \to q)

, אז

φφ = (p \to q) (p \to q)

. הסוגר הראשון נסגר אחרי ה-

q

הראשון. לכן, אין קשר ראשי

\circ

אשר נמצא בין שני תת-פסוקים

α

ו-

β

המרכיבים את *כל* המחרוזת

φφ

. למעשה, אחרי תת-הפסוק הראשון

φ

, לא מופיע קשר דו-מקומי אלא סוגר פותח (, שמתחיל את המופע השני של

φ

.
מאותה סיבה,

φφ

אינו יכול להיות מהצורה

(\neg α)

.

בכל מקרה הגענו לסתירה. לכן, ההנחה הראשונית שגויה, ולא קיים פסוק

φ

כך ש-

φφ

הוא פסוק.

■

ב. הטענה אינה נכונה.
נוכיח כי לא קיים פסוק בעל 4 קשרים דו-מקומיים ודרגה 2.

ראשית, נגדיר במדויק את מושג הדרגה של פסוק

φ

, שאותה נסמן

R (φ)

:
1. אם

p

הוא משתנה פסוקי,

R (p) = 0

.
2. אם

φ = (\neg ψ)

, אז

R (φ) = R (ψ)

.
3. אם

φ = (ψ \circ χ)

, כאשר

\circ

קשר דו-מקומי, אז

R (φ) = 1 + max (R (ψ), R (χ))

.

בנוסף, נסמן ב-

C (φ)

את מספר הקשרים הדו-מקומיים בפסוק

φ

.

כעת נוכיח טענת עזר (למה) הקושרת בין דרגת הפסוק למספר הקשרים הדו-מקומיים שבו.
למה: לכל פסוק

φ

, מתקיים

C (φ) \leq 2^{R (φ)} - 1

.

הוכחת הלמה (באינדוקציה על מבנה הפסוק):

בסיס האינדוקציה: $φ$ הוא משתנה פסוקי $p$ .

במקרה זה,

C (p) = 0

ו-

R (p) = 0

. נציב באי-השוויון:

0 \leq 2^{0} - 1 = 1 - 1 = 0

.
הטענה נכונה עבור הבסיס.

צעד האינדוקציה: נניח שהטענה נכונה עבור פסוקים $ψ, χ$ (הנחת האינדוקציה), ונוכיח עבור פסוק $φ$ הנבנה מהם.
מקרה 1: $φ = (\neg ψ)$ .

C (φ) = C (ψ)

ו-

R (φ) = R (ψ)

.
לפי הנחת האינדוקציה על

ψ

, מתקיים

C (ψ) \leq 2^{R (ψ)} - 1

.
לכן,

C (φ) \leq 2^{R (φ)} - 1

, והטענה נכונה.

מקרה 2: $φ = (ψ \circ χ)$ .

C (φ) = 1 + C (ψ) + C (χ)

R (φ) = 1 + max (R (ψ), R (χ))

. נסמן

M = max (R (ψ), R (χ))

.
לפי הנחת האינדוקציה על

ψ

ו-

χ

C (ψ) \leq 2^{R (ψ)} - 1

C (χ) \leq 2^{R (χ)} - 1

נשתמש בחסמים אלו:

C (φ) = 1 + C (ψ) + C (χ) \leq 1 + (2^{R (ψ)} - 1) + (2^{R (χ)} - 1) = 2^{R (ψ)} + 2^{R (χ)} - 1

מכיוון ש-

R (ψ) \leq M

ו-

R (χ) \leq M

, אז

2^{R (ψ)} \leq 2^{M}

ו-

2^{R (χ)} \leq 2^{M}

C (φ) \leq 2^{M} + 2^{M} - 1 = 2 \cdot 2^{M} - 1 = 2^{M + 1} - 1

ומאחר ש-

R (φ) = M + 1

, קיבלנו

C (φ) \leq 2^{R (φ)} - 1

.
הטענה נכונה גם במקרה זה.

הוכחנו את הלמה באינדוקציה.

■

הפרכת הטענה המקורית:
הטענה המקורית היא שקיים פסוק

φ

המקיים

C (φ) = 4

ו-

R (φ) = 2

.
לפי הלמה שהוכחנו, כל פסוק

φ

חייב לקיים

C (φ) \leq 2^{R (φ)} - 1

.
נציב את הנתונים של הפסוק ההיפותטי באי-השוויון:

4 \leq 2^{2} - 1

4 \leq 4 - 1

4 \leq 3

קיבלנו סתירה. מכאן שלא ייתכן קיומו של פסוק כזה.
לכן, הטענה המקורית מופרכת.

■

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