88-101 חשיבה מתמטית קיץ תשעא/תרגילים

תרגיל 1 להגשה ליום רביעי ה20 ביולי

הצרנות

• הצרן את הטענות הבאות (מותר לכם להשתמש בפרדיקטים סבירים, בתנאי שתגדירו אותם):
  • לכל מספר ממשי יש מספר טבעי הגדול ממנו.
  • אקסיומת האינדקוציה: אם פרידקט כלשהו אמיתי באחד ($P(1)\equiv T$) וכמו כן, העובדה שהוא אמיתי עבור n גוררת שהוא אמיתי עבור n+1 אזי הוא אמיתי תמיד.
  • x הינו מספר ראשוני (מספר המתחלק רק בעצמו ובאחד).
  • כל מספר ראשוני הינו סכום של מספרים זוגיים.
  • קיימים אינסוף תאומים (תאומים הם זוג ראשוניים אשר ההפרש בינהם הינו שתים.)

קבוצות

הגדרה: איחוד של שתי קבוצות A וB הוא קבוצת האיברים שנמצאים לפחות באחת הקבוצות. החיתוך הוא קבוצת האיברים שנמצאים בשתי הקבוצות.

• הצרן תנאי השקול לכך ש-a שייך לאיחוד של הקבוצות A וB
• הצרן תנאי השקול לכך ש-a אינו שייך לאיחוד של הקבוצות A וB
• הצרן תנאי השקול לכך ש-a שייך לחיתוך של הקבוצות A וB
• הצרן תנאי השקול לכך ש-a אינו שייך לחיתוך של הקבוצות A וB

הגדרה: קבוצה A מוכלת בקבוצה B אם בB נמצאים כל האיברים מA (למשל הטבעיים מוכלים בשלמים $\mathbb{N}\subseteq\mathbb{Z}$, והשלמים מוכלים בממשיים $\mathbb{Z}\subseteq\mathbb{R}$).

• הצרן תנאי השקול לכך ש-C מוכלת בחיתוך של A וB
• הצרן תנאי השקול לכך ש-C אינה מוכלת באיחוד של A וB

(מותר לכם להשתמש בכמתים באופן הבא $\forall a\in A, \exists a\in A$)

שקילות

הגדרה: טענות $A_1,A_2,...,A_n$ שקולות אם ((כולן אמיתיות יחד) או (כולן שקריות יחד)).

• הוכח שמספיק להוכיח את הטענות הבאות על מנת להוכיח ש$A_1,A_2,...,A_n$ שקולות:

$A_1\rightarrow A_2$,

$A_2\rightarrow A_3$,

$\vdots$

$A_{n-1}\rightarrow A_n$,

$A_n\rightarrow A_1$

דרכי הוכחה

הוכח שהפסוקים הבאים הינם טאוטולוגיות:

• $(A\rightarrow B) \leftrightarrow (\neg B \rightarrow \neg A)$
• $A \leftrightarrow (\neg A \rightarrow F)$

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

פתרון תרגיל 1

תרגיל שני

הגדרה: הגבול של הפונקציה f בנקודה x הינו L אם לכל סדרה $x_n$ המתכנסת לx ושאבריה שונים מx מתקיים שהסדרה $f(x_n)$ מתכנסת ל-L.

(הגדרת גבול של סדרה היא כפי שלמדנו בשיעור)

• הצרן את ההגדרה לעיל
• הצרן את השלילה להגדרה (כלומר, מתי L אינו גבול הפונקציה בנקודה x)

יהי הפרדיקט $P(x,y)$ האומר אדם x צעיר יותר מאדם y. ויהי הפרדיקט $Q(x)$ האומר שאדם x הינו שמח.

הצרן את הטענות הבאות, ואז הצרן את השלילה שלהן:

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

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

1. יש חתול שאינו שורט ואינו נושך כאשר הוא רואה כלב
2. כל החתולים, כאשר הם רואים כלב הם שורטים ונושכים
3. לכל החתולים יש כלב שכאשר הם רואים אותו הם שורטים או נושכים
4. יש חתול שלא משנה איזה כלב יעבור מולו, הוא ינשך או ישרוט.
5. יש חתול ששורט ונושך כל פעם שהוא רואה כלב.
6. לכל החתולים יש כלב שיעבור מולם והם לא ינשכו ולא ישרטו.
7. יש חתול שינשוך וישרוט כאשר הוא רואה כלב כלשהו.
8. יש חתול שינשוך או ישרוט כאשר הוא רואה כלב כלשהו.
9. זה לא נכון שיש חתול ויש כלב כך שהחתול רואה את הכלב הוא לא נושך או לא שורט.
10. יש כלב שחתול מסויים אף פעם לא שורט ולא נושך כאשר הוא עובר מולו.
11. כל החתולים שורטים או נושכים כאשר הם רואים כלב.
12. כל החתולים לא נושכים או לא שורטים כאשר הם רואים כלב.
13. כל החתולים לא נושכים ולא שורטים כאשר הם רואים כלב.
14. אין חתול שכאשר הוא רואה כלב הוא לא שורט או לא נושך.

פתרון תרגיל 2