הבדלים בין גרסאות בדף "88-101 חשיבה מתמטית קיץ תשעא/תרגילים/פתרון 1"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(יצירת דף עם התוכן "===הצרנות=== *הצרן את הטענות הבאות (מותר לכם להשתמש בפרדיקטים סבירים, בתנאי שתגדירו אותם): **לכ...")
 
(←‏דרכי הוכחה)
 
(5 גרסאות ביניים של אותו משתמש אינן מוצגות)
שורה 1: שורה 1:
 
===הצרנות===
 
===הצרנות===
−
*הצרן את הטענות הבאות (מותר לכם להשתמש בפרדיקטים סבירים, בתנאי שתגדירו אותם):
+
 
 
**לכל מספר ממשי יש מספר טבעי הגדול ממנו.
 
**לכל מספר ממשי יש מספר טבעי הגדול ממנו.
 +
<math>\forall x\in\mathbb{R}\exists n\in\mathbb{N}:n>x</math>
 +
 +
 
**אקסיומת האינדקוציה: אם פרידקט כלשהו אמיתי באחד (<math>P(1)\equiv T</math>) וכמו כן, העובדה שהוא אמיתי עבור n גוררת שהוא אמיתי עבור n+1 אזי הוא אמיתי תמיד.
 
**אקסיומת האינדקוציה: אם פרידקט כלשהו אמיתי באחד (<math>P(1)\equiv T</math>) וכמו כן, העובדה שהוא אמיתי עבור n גוררת שהוא אמיתי עבור n+1 אזי הוא אמיתי תמיד.
 +
<math>\Big[P(1)\and (\forall n\in\mathbb{N}:P(n)\rightarrow P(n+1))\Big]\rightarrow\forall n\in\mathbb{N}:P(n)</math>
 +
 +
 
**x הינו מספר ראשוני (מספר המתחלק רק בעצמו ובאחד).
 
**x הינו מספר ראשוני (מספר המתחלק רק בעצמו ובאחד).
 +
נגדיר את הפרדיקט בעל שני המשתנים "x מחלק את y" ונסמן אותו באופן הנהוג <math>x|y</math>. לכן x ראשוני אם <math>\forall n\in\mathbb{N}: (n|x)\rightarrow ((n=1)\or(n=x))</math>
 +
 +
 
**כל מספר ראשוני הינו סכום של מספרים זוגיים.
 
**כל מספר ראשוני הינו סכום של מספרים זוגיים.
 +
<math>\forall x\in\mathbb{N}:\Big[\forall n\in\mathbb{N}: (n|x)\rightarrow ((n=1)\or(n=x))\Big]\rightarrow \Big[\exists n\in\mathbb{N}\exists k\in\mathbb{N}:2n+2k=x\Big]</math>
 +
 +
 
**קיימים אינסוף תאומים (תאומים הם זוג ראשוניים אשר ההפרש בינהם הינו שתים.)
 
**קיימים אינסוף תאומים (תאומים הם זוג ראשוניים אשר ההפרש בינהם הינו שתים.)
 +
"קיימים אינסוף" הוא תנאי שיש להגדיר. ההגדרה האינטואיטיבית הינה לא קיים מספר סופי של איברים כאלה, כלומר ההנחה שיש מספר סופי תוביל לשלילה. הראנו בתרגיל אחר שזה שקול לטענה לכל מספר יש מספר הגדול ממנו המקיים את התנאי, וזה מה שנצרין כאן.
 +
 +
<math>\forall n\in\mathbb{N}\exists x\in\mathbb{N}:\Big[x>n\Big]\and\Big[\forall k\in\mathbb{N}: (k|x)\rightarrow ((k=1)\or(k=x))\Big] \and \Big[\forall k\in\mathbb{N}: (k|x+2)\rightarrow ((k=1)\or(k=x+2))\Big]</math>
  
 
===קבוצות===
 
===קבוצות===
−
הגדרה: איחוד של שתי קבוצות A וB הוא קבוצת האיברים שנמצאים לפחות באחת הקבוצות. החיתוך הוא קבוצת האיברים שנמצאים בשתי הקבוצות.
 
 
*הצרן תנאי השקול לכך ש-a שייך לאיחוד של הקבוצות A וB
 
*הצרן תנאי השקול לכך ש-a שייך לאיחוד של הקבוצות A וB
 +
<math>x\in A\cup B \iff (x\in A) \or (x\in B)</math>
 +
 +
 
*הצרן תנאי השקול לכך ש-a אינו שייך לאיחוד של הקבוצות A וB
 
*הצרן תנאי השקול לכך ש-a אינו שייך לאיחוד של הקבוצות A וB
 +
<math>x\notin A\cup B \iff \neg\Big[(x\in A) \or (x\in B)\Big]\iff (x\notin A) \and (x\notin B)</math>
 +
 +
 
*הצרן תנאי השקול לכך ש-a שייך לחיתוך של הקבוצות A וB
 
*הצרן תנאי השקול לכך ש-a שייך לחיתוך של הקבוצות A וB
 +
<math>x\in A\cap B \iff (x\in A) \and (x\in B)</math>
 +
 +
 
*הצרן תנאי השקול לכך ש-a אינו שייך לחיתוך של הקבוצות A וB
 
*הצרן תנאי השקול לכך ש-a אינו שייך לחיתוך של הקבוצות A וB
 +
<math>x\notin A\cap B \iff \neg\Big[(x\in A) \and (x\in B)\Big]\iff (x\notin A) \or (x\notin B)</math>
 +
  
−
הגדרה: קבוצה A מוכלת בקבוצה B  אם בB נמצאים כל האיברים מA (למשל הטבעיים מוכלים בשלמים <math>\mathbb{N}\subseteq\mathbb{Z}</math>, והשלמים מוכלים בממשיים  <math>\mathbb{Z}\subseteq\mathbb{R}</math>).
 
 
*הצרן תנאי השקול לכך ש-C מוכלת בחיתוך של A וB
 
*הצרן תנאי השקול לכך ש-C מוכלת בחיתוך של A וB
−
*הצרן תנאי השקול לכך ש-C אינה מוכלת באיחוד של A וB
+
<math>C\subseteq (A\cap B)\iff \forall c\in C: c\in (A\cap B) \iff \forall c\in C: (c\in A) \and (c\in B)</math>
  
  
−
(מותר לכם להשתמש בכמתים באופן הבא <math>\forall a\in A, \exists a\in A</math>)
+
*הצרן תנאי השקול לכך ש-C אינה מוכלת באיחוד של A וB
 +
<math>\neg\Big[C\subseteq (A\cap B)\Big]\iff  \neg\Big[\forall c\in C: (c\in A) \and (c\in B)\Big]\iff \exists c\in C: (c\notin A)\or (c\notin B)</math>
  
 
===שקילות===
 
===שקילות===
−
הגדרה: טענות <math>A_1,A_2,...,A_n</math> שקולות אם ((כולן אמיתיות יחד) או (כולן שקריות יחד)).
 
 
*הוכח שמספיק להוכיח את הטענות הבאות על מנת להוכיח ש<math>A_1,A_2,...,A_n</math> שקולות:
 
*הוכח שמספיק להוכיח את הטענות הבאות על מנת להוכיח ש<math>A_1,A_2,...,A_n</math> שקולות:
  
שורה 34: שורה 58:
  
 
<math>A_n\rightarrow A_1</math>
 
<math>A_n\rightarrow A_1</math>
 +
 +
 +
*הוכחה:
 +
נניח שהטענות שקולות ונניח ש<math>A_i</math> אמיתית. לכן <math>A_{i+1}</math> חייבת להיות אמיתית, לכן <math>A_{i+2}</math> גם וכן הלאה עד <math>A_n</math> זה גורר את נכונות <math>A_1</math> וכך הלאה עד שנגיע לכל הטענות.
 +
 +
לכן, אם טענה אחת אמיתית, כולן אמיתיות. נובע בקלות שאם אחת תהא שקרית, לא ייתכן שאף אחת אחרת תהא אמיתית ולכן כולם אמיתיות ושקריות יחדיו.
  
 
===דרכי הוכחה===
 
===דרכי הוכחה===
שורה 41: שורה 71:
  
  
−
(נהוג להחליף ביטויים מהצורה הזו בביטויים השקולים להם כי הם נוחים יותר להוכחה מידי פעם.)
+
התשובה הינה בדיקה קלה בטבלת אמת.

גרסה אחרונה מ־06:25, 5 באוגוסט 2011

הצרנות

    • לכל מספר ממשי יש מספר טבעי הגדול ממנו.

\forall x\in\mathbb{R}\exists n\in\mathbb{N}:n>x


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

\Big[P(1)\and (\forall n\in\mathbb{N}:P(n)\rightarrow P(n+1))\Big]\rightarrow\forall n\in\mathbb{N}:P(n)


    • x הינו מספר ראשוני (מספר המתחלק רק בעצמו ובאחד).

נגדיר את הפרדיקט בעל שני המשתנים "x מחלק את y" ונסמן אותו באופן הנהוג x|y. לכן x ראשוני אם \forall n\in\mathbb{N}: (n|x)\rightarrow ((n=1)\or(n=x))


    • כל מספר ראשוני הינו סכום של מספרים זוגיים.

\forall x\in\mathbb{N}:\Big[\forall n\in\mathbb{N}: (n|x)\rightarrow ((n=1)\or(n=x))\Big]\rightarrow \Big[\exists n\in\mathbb{N}\exists k\in\mathbb{N}:2n+2k=x\Big]


    • קיימים אינסוף תאומים (תאומים הם זוג ראשוניים אשר ההפרש בינהם הינו שתים.)

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

\forall n\in\mathbb{N}\exists x\in\mathbb{N}:\Big[x>n\Big]\and\Big[\forall k\in\mathbb{N}: (k|x)\rightarrow ((k=1)\or(k=x))\Big] \and \Big[\forall k\in\mathbb{N}: (k|x+2)\rightarrow ((k=1)\or(k=x+2))\Big]

קבוצות

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

x\in A\cup B \iff (x\in A) \or (x\in B)


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

x\notin A\cup B \iff \neg\Big[(x\in A) \or (x\in B)\Big]\iff (x\notin A) \and (x\notin B)


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

x\in A\cap B \iff (x\in A) \and (x\in B)


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

x\notin A\cap B \iff \neg\Big[(x\in A) \and (x\in B)\Big]\iff (x\notin A) \or (x\notin B)


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

C\subseteq (A\cap B)\iff \forall c\in C: c\in (A\cap B) \iff \forall c\in C: (c\in A) \and (c\in B)


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

\neg\Big[C\subseteq (A\cap B)\Big]\iff \neg\Big[\forall c\in C: (c\in A) \and (c\in B)\Big]\iff \exists c\in C: (c\notin A)\or (c\notin B)

שקילות

  • הוכח שמספיק להוכיח את הטענות הבאות על מנת להוכיח ש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_i אמיתית. לכן A_{i+1} חייבת להיות אמיתית, לכן A_{i+2} גם וכן הלאה עד A_n זה גורר את נכונות A_1 וכך הלאה עד שנגיע לכל הטענות.

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

דרכי הוכחה

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

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


התשובה הינה בדיקה קלה בטבלת אמת.

מקור: https://math-wiki.com/index.php?title=88-101_חשיבה_מתמטית_קיץ_תשעא/תרגילים/פתרון_1&oldid=12389