88-195 בדידה לתיכוניסטים קיץ תשעג/תרגילים/פתרון 1

חלק ראשון

1

1. "אם ערן רעב הוא עצבני."
2. "כאשר ערן אינו עצבני הוא לא רעב."

נסמן

• p = ערן רעב
• q = ערן עצבני

אזי ההצרנה של הפסוקים הינה:

1. $p\rightarrow q$
2. $\urcorner q \rightarrow \urcorner p$

למדנו בכיתה כי שני הפסוקים הללו שקולים.

2

1. "מי שטוב לו ושמח כף ימחה"
2. "מי שלא טוב לא או לא שמח לא ימחה כף"

נסמן

• $p(x)$ = טוב לx
• $q(x)$ = שמח לx
• $r(x)$ = x ימחא כף

אזי ההצרנה של הפסוקים הינה:

1. $\forall x:p(x)\and q(x) \rightarrow r(x)$
2. $\forall x: \urcorner p(x) \or \urcorner q(x) \rightarrow \urcorner r(x)$

הפסוקים אינם שקולים.

הפרכה: אדם שמוחא כף אך אינו שמח ולא טוב לו. כלומר $p(x)=F,q(x)=F,r(x)=T$

הפסוק הראשון מתקיים ואילו השני לא מתקיים.

3

1. "אם אייל שמח ענת גבוהה, ואם ענת גבוהה צחי חמוד"
2. "אם אייל שמח אז צחי חמוד"

נסמן

• p = אייל שמח
• q = ענת גבוהה
• r = צחי חמוד

אזי ההצרנה של הפסוקים הינה:

1. $(p \rightarrow q)\and (q\rightarrow r)$
2. $p\rightarrow r$

הפסוקים אינם שקולים.

הפרכה: אייל אינו שמח, ענת גבוהה וצחי אינו חמוד.

הפסוק הראשון אינו מתקיים ואילו הפסוק השני מתקיים.

4

1. "אם ערן רעב הוא עצבני."
2. "ערן עצבני או שאינו רעב"

נסמן

• p = ערן רעב
• q = ערן עצבני

אזי ההצרנה של הפסוקים הינה:

1. $p\rightarrow q$
2. $q \or \urcorner p$

למדנו בכיתה כי שני הפסוקים הללו שקולים.

5

1. "ערן עצבני או רעב, וגם עייף"
2. "ערן עצבני או עייף וגם רעב או עייף"

נסמן

• p = ערן רעב
• q = ערן עצבני
• r = ערן עייף

אזי ההצרנה של הפסוקים הינה:

1. $(q\or p)\and r$
2. $(q\or r)\and (p\or r)$

הפסוקים אינם שקולים.

הפרכה: ערן רעב וגם עצבני אבל לא עייף.

הפסוק הראשון שגוי אבל השני נכון.

6

1. "הקרנף רץ או הגירפה אוכלת, והאריה צד או הקוף קופץ"
2. "הקרנף רץ והאריה צד או הקרנף רץ והקוף קופץ או הג'ירפה אוכלת והאריה צד או הג'ירפה אוכל והקוף קופץ"

נסמן

• p = הקרנף רץ
• q = הגי'רפה אוכלת
• r = האריה צד
• s = הקוף קופץ

אזי ההצרנה של הפסוקים הינה:

1. $(p \or q) \and (r \or s)$
2. $(p\and r) \or (p\and s) \or (q\and r) \or (q\and s)$

קל להראות באמצעות חוק הדיסטריביוטיביות (פילוג) כי שני הפסוקים הללו שקולים.

חלק שני

1

• "כל מאכל, יש שף שמכין אותו טעים"

נסמן:

• A קבוצת המאכלים
• B קבוצת השפים
• $P(a,b)$ = השף b מכין את המאכל a טעים.

הצרנת הפסוק הינה

• $\forall a\in A\exists b\in B:P(a,b)$

סמנו את השלילות

• 1. "כל מאכל, יש שף שמכין אותו לא טעים"

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

• 2. "יש מאכל שכל השפים מכינים אותו לא טעים"

שלילה. הצרנת הפסוק: $\exists a\in A\forall b\in B: \urcorner P(a,b)$

• 3. "כל מאכל, כל השפים מכינים אותו טעים"

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

• 4. "יש מאכל, שכל השפים מכינים טעים"

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

• 5. "יש מאכל, שאף שף לא מכין טעים"

שלילה. הצרנת הפסוק: $\exists a\in A :\urcorner\Big(\exists b\in B:P(a,b)\Big)$

• 6. "כל מאכל, אף שף לא מכין לא טעים"

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

2

• "לכל דג עם קשקשים ולכל חרק עם מחושים, אם הדג שמח החרק יושב על פרח"

נסמן:

• A קבוצת הדגים
• B קבוצת החרקים
• $p(a)$ = לדג a יש קשקשים
• $q(a)$ = הדג a שמח
• $r(b)$ = לחרק b יש מחושים
• $s(b)$ = החרק b יושב על פרח

הצרנת הפסוק הינה

• $\forall a\in A\forall b\in B:\Big(p(a)\and r(b)\Big)\rightarrow \Big(q(a)\rightarrow s(b)\Big)$

סמנו את השלילות

• 1. "לכל דג עם קשקשים ולכל חרק ללא מחושים הדג שמח והחרק אינו יושב על פרח"

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

• 2. "יש דג ללא קשקשים ויש חרק ללא מחושים כך שאם הדג שמח החרק יושב על פרח"

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

• 3. "יש דג ללא קשקשים ויש חרק ללא מחושים כך שהדג שמח והחרק אינו יושב על פרח"

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

• 4. "יש דג עם קשקשים ויש חרק עם מחושים כך שהדג שמח אך החרק אינו יושב על פרח"

שלילה. ההצרנה של הפסוק הינה: $\forall a\in A\forall b\in B:p(a)\and r(b)\and q(a)\and\urcorner s(b)$

זכרו כי $\urcorner(p\rightarrow q) \equiv \urcorner (\urcorner p \or q) \equiv p \and \urcorner q$

• 5. "קיים דג עם קשקשים וקיים חרק עם מחושים כך שלא נכון לומר שהחרק יושב על פרח או הדג שמח"

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

3

• "אם לכל אדם יש מטרה המתאימה לו אז לכל מטרה יש מי שיגשים אותה"

נסמן:

• A קבוצת האנשים
• B קבוצת המטרות
• $p(a,b)$ = המטרה b מתאימה לאדם a
• $q(a,b)$ = האדם a יגשים את המטרה b

הצרנת הפסוק הינה

• $\Big(\forall a\in A \exists b\in B: p(a,b)\Big)\rightarrow \Big(\forall b\in B \exists a\in A:q(a,b)\Big)$

סמנו את השלילות

• 1. "אם יש אדם ללא מטרה המתאימה לו, אין לאותה המטרה מי שיגשים אותה"

לא שלילה. זה אפילו לא פסוק תקני - מי היא אותה המטרה שאנו מדברים עליה?

• 2. "אם יש אדם שכל מטרה אינה מתאימה לו, אז יש מטרה שאין מי שיגשים אותה"

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

• 3. "לכל מטרה יש מי שיגשים אותה או שיש אדם שכל המטרות אינן מתאימות לו"

לא שלילה. למעשה פסוק זה שקול לחלוטין לפסוק המקורי. הצרנת הפסוק הינה: $\Big(\exists a\in A \forall b\in B: \urcorner p(a,b)\Big)\or \Big(\forall b\in B \exists a\in A:q(a,b)\Big)$

• 4. "לכל אדם יש מטרה המתאימה לו ויש מטרה שאין מי שיגשים אותה"

שלילה. ההצרנה של הפסוק הינה: $\Big(\forall a\in A \exists b\in B: p(a,b)\Big)\and \Big(\exists b\in B \urcorner(\exists a\in A:q(a,b))\Big)$

חלק שלישי

1. לכל איש יש שם
2. קיים איש עם שם יחיד
3. אם קיים איש עם שם יחיד אז לא קיים איש ללא שם
4. לכל איש עם שם יש שם נוסף (שונה מהראשון)
5. קיימים שני אנשים שונים עם אותו שם
6. לכל איש עם שם קיים איש אחר עם אותו שם

• אם טענות 2 ו3 נכונות אזי גם טענה 1 נכונה

נכון. ידוע כי קיים איש עם שם יחיד (לפי טענה 2) לכן לא קיים איש ללא שם (לפי טענה 3). המשפט לא קיים איש ללא שם שקול למשפט לכל איש יש שם (טענה 1).

• אם טענה 6 נכונה אז טענה 5 נכונה

לא נכון. אם אין אנשים אז טענה 6 נכונה באופן ריק ואילו טענה 5 לא נכונה כלל.

• אם טענה 2 שקרית וטענה 3 שקרית, אז אני צנצנת וגם לא צנצנת

נכון. אם טענה 2 שקרית, אזי לכל האנשים אין שם יחיד. אם טענה 3 שקרית, אז קיים איש עם שם יחיד וקיים איש ללא שם.

משתי הטענות ביחד, נובעת הסתירה "קיים איש עם שם יחיד וגם לא קיים איש עם שם יחיד".

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

• טענה 3 נכונה אם ורק אם טענה 4 נכונה

לא נכון. ייתכן שקיים איש עם שם יחיד ולא קיים איש ללא שם (כלומר טענה 3 נכונה) ואז לאיש עם השם היחיד יש שם אבל אין שם נוסף ולכן טענה 4 שגוייה.

• אם טענות 3 ו4 נכונות אז טענה 2 שקרית

נכון. נניח בשלילה שטענה 2 נכונה. לכן קיים איש עם שם יחיד, זה סותר את טענה 4 שטוענת שלכל איש עם שם יש שם נוסף (כלומר אין לו שם יחיד).