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