הבדלים בין גרסאות בדף "תרגול 8 תשעז"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(יצירת דף עם התוכן "=יחסים= הגדרה: '''המכפלה הקרטזית''' של שתי קבוצות A וB הינה אוסף כל ה'''זוגות הסדורים''' - <math>A\time...")
 
(←‏פתרון)
 
(8 גרסאות ביניים של 4 משתמשים אינן מוצגות)
שורה 1: שורה 1:
 +
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
 +
 
=יחסים=
 
=יחסים=
−
הגדרה: '''המכפלה הקרטזית''' של שתי קבוצות A וB הינה אוסף כל ה'''זוגות הסדורים''' - <math>A\times B = \{(a,b)|a\in A \and b\in B\}</math>. ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים <math>(1,2),(2,1)</math> והאיבר הבא הינו זוג חוקי <math>(1,1)</math>.
+
==המכפלה הקרטזית==
 +
הגדרה: '''המכפלה הקרטזית''' של שתי קבוצות <math>A</math> ו-<math>B</math> הינה אוסף כל ה'''זוגות הסדורים''' - <math>A\times B = \{(a,b)|a\in A \and b\in B\}</math>. ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים <math>(1,2),(2,1)</math> והאיבר הבא הינו זוג חוקי <math>(1,1)</math>.
  
−
ניתן להכליל את ההגדרה לעיל לn-יה סדורה - כלומר n איברים מסודרים.
+
ניתן להכליל את ההגדרה לעיל ל-<math>n</math>-יה סדורה - כלומר <math>n</math> איברים מסודרים.
  
−
דוגמא: <math>A=\{1,2,3\}</math> ו<math>B=\{a,b\}</math> אזי מתקיים <math>A\times B =\{(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)\}</math>
+
דוגמה: <math>A=\{1,2,3\}</math> ו-<math>B=\{a,b\}</math> אזי מתקיים <math>A\times B =\{(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)\}</math>
  
−
 
+
למתכנתים: זה מאוד דומה ללולאות for מקוננות.
−
ניתן להגדיר זוגות סדורים באמצעות הגדרת הקבוצות בלבד, כפי שנראה בתרגיל הבא:
+
  
 
===תרגיל===
 
===תרגיל===
−
הוכח/הפרך:
+
הוכח שלכל קבוצות <math>A,B,C,D</math> מתקיים <math>(A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D)</math>
  
−
1. <math>[(a=c)\and(b=d)]\iff \{\{a\},b\}=\{\{c\},d\}</math>
+
====פתרון====
 +
<math>(x,y)\in (A\times B)\cap (C\times D) \iff </math>
  
−
2. <math>[(a=c)\and(b=d)]\iff \{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}</math>
+
<math>(x,y)\in A\times B \land (x,y)\in C\times D \iff</math>
  
−
====פתרון====
+
<math>(x\in A \and y\in B) \and (x\in C\and y\in D) \iff</math>
  
−
1. הפרכה ע"י הדוגמא הנגדית <math>a=2,b=\{3\},c=3,d=\{2\}</math>
+
<math>(x\in A\and x\in C) \and (y\in B\and y\in D) \iff</math>
  
 +
<math>(x,y)\in (A\cap C)\times (B\cap D)</math>
  
−
2.  
+
==יחסים כתת קבוצה של הזוגות הסדורים==
 +
הגדרה: יהיו <math>A,B</math> קבוצות, <math>R\subseteq A\times B</math>  אזי <math>R</math> יקרא יחס (בין <math>A</math> לבין <math>B</math>).
 +
הרעיון שעומד בבסיסו של יחס הוא האפשרות "להשוות" בין איברי <math>A</math> ל-<math>B</math>.
  
−
הוכחה: הכיוון משמאל לימין הוא ברור. מימין לשמאל, נניח והקבוצות שוות אזי <math>\{a\}=\{c\}</math> או ש <math>\{a\}=\{c,d\}</math>.
+
דוגמה: <math>A=\{1,2,3\},B=\{0,2,6\}</math> ונביט בתת הקבוצה <math>R\subseteq A\times B</math> הבאה: <math>R=\{(1,2),(1,6),(2,2),(2,6),(3,6)\}</math>. מה מיוחד בזוגות אלה?
  
−
במקרה הראשון, נובע a=c ובמקרה השני נובע a=c=d, כך או כך a=c. כעת, <math>\{a,b\}=\{c,b\}=\{c\}</math> או <math>\{c,b\}=\{c,d\}</math> ונובע משניהם ש b=d.
+
זוגות אלה הינם כל זוגות האיברים <math>(a,b)</math> כך ש-<math>a\leq b</math>. (כלומר הגדרנו את היחס המייצג "קטן שווה").
  
 +
הערה: יחס לא חייב לייצג חוקיות מסוימת למשל גם הקבוצה <math>S=\{(1,2),(1,6),(2,0),(2,2)\}</math> היא יחס. גם <math>\varnothing</math> היא יחס, וגם <math>A\times B</math> הוא יחס.
  
−
לכן, ניתן להגדיר זוג סדור על ידי קבוצות בלבד (באופן דומה לכך שכל המתמטיקה פחות או יותר נבנת על קבוצות בלבד).
+
סימון: אם זוג מסוים,נניח <math>(a,b)</math>, נמצא בקבוצת היחס <math>R</math> נהוג לסמן <math>aRb</math>, או <math>(a,b)\in R</math>. (אם יש משמעות ליחס כמו לעיל ניתן גם לסמן פשוט <math>a\leq b</math>).
  
 +
דוגמה: נביט בקבוצת האנשים <math>A</math>. נגדיר את יחס "בן של" על ידי קבוצת הזוגות הסדורים <math>R\subseteq A\times A</math> כך ש-<math>(x,y)\in R</math> אם"ם <math>x</math> הוא בן של <math>y</math>. שימו לב שיש משמעות לכיוון היחס, שכן יש הבדל בין העובדה שאני הבן של מישהו לבין העובדה שהוא הבן שלי.
  
−
===תרגיל===
+
הגדרה: בהינתן יחס <math>R\subseteq A\times B</math>, '''היחס ההפוך''' <math>R^{-1}\subseteq B\times A</math> הוא היחס המוגדר ע"י היפוך הזוגות הסדורים:
−
הוכח שלכל קבוצות A,B,C מתקיים <math>A\times(B\cap C)=(A\times B)\cap(A\times C)</math>
+
<math>R^{-1}=\{(b,a):aRb\}</math>
  
−
====פתרון====
+
הגדרה: תהי קבוצה <math>A</math>. '''יחס הזהות''' על <math>A</math> הוא <math>R\subseteq A\times A</math> כך ש-<math>I_A=R=\{(a,a):a\in A\}</math>.
−
<math>(x,y)\in A\times(B\cap C) \iff (x\in A) \and [(y\in B)\and (y\in C)] \iff [(x\in A)\and(y\in B)] \and [(x\in A)\and(y\in C)] \iff (x,y)\in[(A\times B)\cap(A\times C)]</math>
+
  
−
==יחסים כתת קבוצה של הזוגות הסדורים==
+
הגדרה: יהיו <math>A,B,C</math> קבוצות, ו-<math>R\subseteq A\times B, S\subseteq B\times C</math> '''יחס הכפל''' הוא היחס: <math>RS=\{(a,c)\in A\times C | \exists b\in B : (a,b)\in R \land (b,c)\in S\}</math>.
−
הגדרה: יהיו A,B קבוצות, <math>R\subseteq A\times B</math> אזי R יקרא יחס (בין A ל -B).
+
−
הרעיון שעומד בבסיסו של יחס הוא האפשרות "להשוות" בין איברי A ל B
+
−
דוגמא: <math>A=\{1,2,3\},B=\{0,2,6\}</math> ונביט בתת הקבוצה <math>R\subseteq A\times B</math> הבאה: <math>R=\{(1,2),(1,6),(2,2),(2,6),(3,6)\}</math>. מה מיוחד בזוגות אלה?
+
  
−
זוגות אלה הינן כל זוגות האיברים (a,b) כך ש <math>a\leq b</math>. (כלומר הגדרנו את היחס המייצג  "קטן שווה")  
+
===תרגיל===
 +
יהיו <math>A=\{1,2\}, B=\{3,4,5\}</math>. נגדיר את היחס: <math>R=\{(1,3),(2,4)\}</math>. בדוק האם:
  
−
הערה: יחס לא חייב לייצג חוקיות מסוימת למשל גם הקבוצה <math>S=\{(1,2),(1,6),(2,0),(2,2)\}</math> היא יחס. גם <math>\emptyset</math> היא יחס. וגם <math>A\times B</math> הוא יחס.
+
א. <math>RR^{-1}=I_A</math>
  
−
סימון: אם זוג מסוים, (a,b), נמצא בקבוצת היחס R נהוג לסמן aRb. (אם יש משמעות ליחס כמו לעיל ניתן גם לסמן פשוט <math>a\leq b</math>.
+
ב. <math>R^{-1}R=I_B</math>
  
 +
==תכונות של יחסים על קבוצה==
 +
הגדרה: יחס <math>R</math> על קבוצה <math>A</math> פירושו <math>R\subseteq A\times A</math>.
  
−
דוגמא: נביט בקבוצת האנשים A. נגדיר את יחס "בן של" על ידי קבוצת הזוגות הסדורים <math>R\subseteq A\times A</math> כך ש <math>(x,y)\in R</math> אם"ם x הוא בן של y. שימו לב שיש משמעות לכיוון היחס, שכן יש הבדל בין העובדה שאני הבן של מישהו לבין העובדה שהוא הבן שלי.
+
תהי קבוצה <math>A</math> ויחס <math>R</math> עליה אזי:
 +
#<math>R</math> נקרא '''רפלקסיבי''' אם כל איבר מקיים את היחס עם עצמו ( מתקיים <math>\forall a\in A:(a,a)\in R</math>).
 +
#<math>R</math> נקרא '''סימטרי''' אם <math>aRb</math> גורר שגם <math>bRa</math> (מתקיים <math>\forall a,b\in A:[(a,b)\in R \rightarrow (b,a)\in R]</math>).
 +
#<math>R</math> נקרא '''טרנזיטיבי''' אם יחס בין ראשון לשני (<math>aRb</math>), ויחס בין השני לשלישי (<math>bRc</math>) גורר יחס בין הראשון לשלישי (<math>aRc</math>). (מתקיים <math>\forall a,b,c\in A:[((a,b)\in R) \and ((b,c)\in R) \rightarrow ((a,c)\in R)]</math>).
 +
#<math>R</math> נקרא '''אנטי סימטרי (חלש)''' אם <math>aRb</math> וגם <math>bRa</math> גורר כי <math>a=b</math> (מתקיים <math>\forall a,b\in A:[(a,b)\in R \and (b,a)\in R \rightarrow a=b]</math> ובאופן שקול: <math>\forall a\neq b\in A: \lnot (aRb\land bRa)</math>)
  
−
הגדרה: בהינתן יחס <math>R\subseteq A\times B</math> '''היחס ההפוך''' <math>R^{-1}\subseteq B\times A</math> הוא היחס המוגדר ע"י היפוך הזוגות הסדורים:
+
דוגמאות:
−
<math>R^{-1}=\{(b,a):aRb\}</math>
+
*יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי
 +
*יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי
 +
*יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי
 +
*יחס 'שיוויון מודולו <math>n</math>' הינו רפלקסיבי, סימטרי וטרנזיטיבי
 +
*יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
 +
*יחס '<math>a</math> מחלק את <math>b</math>' הינו רפלקסיבי וטרנזיטיבי
 +
*יחס 'אדם <math>x</math> שמע על אדם <math>y</math>' הינו רפלקסיבי
 +
 
 +
'''הערה:''' יחס יכול להיות גם סימטרי וגם אנטי סימטרי. וכמו כן הוא יכול להיות לא זה ולא זה! לדוגמה: <math>A=\{ 1,2,3\} , R=\{ (1,1)\} , S=\{ (1,2),(2,1),(3,2)\}</math> ואז <math>R</math> גם וגם, ואילו <math>S</math> לא ולא.

גרסה אחרונה מ־17:04, 5 בדצמבר 2017

חזרה לדף מערכי התרגול.

יחסים

המכפלה הקרטזית

הגדרה: המכפלה הקרטזית של שתי קבוצות A ו-B הינה אוסף כל הזוגות הסדורים - A\times B = \{(a,b)|a\in A \and b\in B\}. ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים (1,2),(2,1) והאיבר הבא הינו זוג חוקי (1,1).

ניתן להכליל את ההגדרה לעיל ל-n-יה סדורה - כלומר n איברים מסודרים.

דוגמה: A=\{1,2,3\} ו-B=\{a,b\} אזי מתקיים A\times B =\{(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)\}

למתכנתים: זה מאוד דומה ללולאות for מקוננות.

תרגיל

הוכח שלכל קבוצות A,B,C,D מתקיים (A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D)

פתרון

(x,y)\in (A\times B)\cap (C\times D) \iff

(x,y)\in A\times B \land (x,y)\in C\times D \iff

(x\in A \and y\in B) \and (x\in C\and y\in D) \iff

(x\in A\and x\in C) \and (y\in B\and y\in D) \iff

(x,y)\in (A\cap C)\times (B\cap D)

יחסים כתת קבוצה של הזוגות הסדורים

הגדרה: יהיו A,B קבוצות, R\subseteq A\times B אזי R יקרא יחס (בין A לבין B). הרעיון שעומד בבסיסו של יחס הוא האפשרות "להשוות" בין איברי A ל-B.

דוגמה: A=\{1,2,3\},B=\{0,2,6\} ונביט בתת הקבוצה R\subseteq A\times B הבאה: R=\{(1,2),(1,6),(2,2),(2,6),(3,6)\}. מה מיוחד בזוגות אלה?

זוגות אלה הינם כל זוגות האיברים (a,b) כך ש-a\leq b. (כלומר הגדרנו את היחס המייצג "קטן שווה").

הערה: יחס לא חייב לייצג חוקיות מסוימת למשל גם הקבוצה S=\{(1,2),(1,6),(2,0),(2,2)\} היא יחס. גם \varnothing היא יחס, וגם A\times B הוא יחס.

סימון: אם זוג מסוים,נניח (a,b), נמצא בקבוצת היחס R נהוג לסמן aRb, או (a,b)\in R. (אם יש משמעות ליחס כמו לעיל ניתן גם לסמן פשוט a\leq b).

דוגמה: נביט בקבוצת האנשים A. נגדיר את יחס "בן של" על ידי קבוצת הזוגות הסדורים R\subseteq A\times A כך ש-(x,y)\in R אם"ם x הוא בן של y. שימו לב שיש משמעות לכיוון היחס, שכן יש הבדל בין העובדה שאני הבן של מישהו לבין העובדה שהוא הבן שלי.

הגדרה: בהינתן יחס R\subseteq A\times B, היחס ההפוך R^{-1}\subseteq B\times A הוא היחס המוגדר ע"י היפוך הזוגות הסדורים: R^{-1}=\{(b,a):aRb\}

הגדרה: תהי קבוצה A. יחס הזהות על A הוא R\subseteq A\times A כך ש-I_A=R=\{(a,a):a\in A\}.

הגדרה: יהיו A,B,C קבוצות, ו-R\subseteq A\times B, S\subseteq B\times C יחס הכפל הוא היחס: RS=\{(a,c)\in A\times C | \exists b\in B : (a,b)\in R \land (b,c)\in S\}.

תרגיל

יהיו A=\{1,2\}, B=\{3,4,5\}. נגדיר את היחס: R=\{(1,3),(2,4)\}. בדוק האם:

א. RR^{-1}=I_A

ב. R^{-1}R=I_B

תכונות של יחסים על קבוצה

הגדרה: יחס R על קבוצה A פירושו R\subseteq A\times A.

תהי קבוצה A ויחס R עליה אזי:

  1. R נקרא רפלקסיבי אם כל איבר מקיים את היחס עם עצמו ( מתקיים \forall a\in A:(a,a)\in R).
  2. R נקרא סימטרי אם aRb גורר שגם bRa (מתקיים \forall a,b\in A:[(a,b)\in R \rightarrow (b,a)\in R]).
  3. R נקרא טרנזיטיבי אם יחס בין ראשון לשני (aRb), ויחס בין השני לשלישי (bRc) גורר יחס בין הראשון לשלישי (aRc). (מתקיים \forall a,b,c\in A:[((a,b)\in R) \and ((b,c)\in R) \rightarrow ((a,c)\in R)]).
  4. R נקרא אנטי סימטרי (חלש) אם aRb וגם bRa גורר כי a=b (מתקיים \forall a,b\in A:[(a,b)\in R \and (b,a)\in R \rightarrow a=b] ובאופן שקול: \forall a\neq b\in A: \lnot (aRb\land bRa))

דוגמאות:

  • יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי
  • יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי
  • יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי
  • יחס 'שיוויון מודולו n' הינו רפלקסיבי, סימטרי וטרנזיטיבי
  • יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
  • יחס 'a מחלק את b' הינו רפלקסיבי וטרנזיטיבי
  • יחס 'אדם x שמע על אדם y' הינו רפלקסיבי

הערה: יחס יכול להיות גם סימטרי וגם אנטי סימטרי. וכמו כן הוא יכול להיות לא זה ולא זה! לדוגמה: A=\{ 1,2,3\} , R=\{ (1,1)\} , S=\{ (1,2),(2,1),(3,2)\} ואז R גם וגם, ואילו S לא ולא.

מקור: https://math-wiki.com/index.php?title=תרגול_8_תשעז&oldid=73710