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

תוכן עניינים

1 יחסים

יחסים

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

הגדרה: המכפלה הקרטזית של שתי קבוצות $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$ עליה אזי:

$R$ נקרא רפלקסיבי אם כל איבר מקיים את היחס עם עצמו ( מתקיים $\forall a\in A:(a,a)\in R$ ).
$R$ נקרא סימטרי אם $aRb$ גורר שגם $bRa$ (מתקיים $\forall a,b\in A:[(a,b)\in R \rightarrow (b,a)\in R]$ ).
$R$ נקרא טרנזיטיבי אם יחס בין ראשון לשני ( $aRb$ ), ויחס בין השני לשלישי ( $bRc$ ) גורר יחס בין הראשון לשלישי ( $aRc$ ). (מתקיים $\forall a,b,c\in A:[((a,b)\in R) \and ((b,c)\in R) \rightarrow ((a,c)\in R)]$ ).
$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$ לא ולא.

@@ שורה 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 מקוננות.
 ===תרגיל===
-הוכח שלכל קבוצות 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 ל -B).
+הגדרה: יהיו <math>A,B</math> קבוצות, <math>R\subseteq A\times B</math>  אזי <math>R</math> יקרא יחס (בין <math>A</math> לבין <math>B</math>).
-הרעיון שעומד בבסיסו של יחס הוא האפשרות "להשוות" בין איברי A ל B
+הרעיון שעומד בבסיסו של יחס הוא האפשרות "להשוות" בין איברי <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>. מה מיוחד בזוגות אלה?
-זוגות אלה הינן כל זוגות האיברים (a,b) כך ש <math>a\leq 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>S=\{(1,2),(1,6),(2,0),(2,2)\}</math> היא יחס. גם <math>\emptyset</math> היא יחס. וגם <math>A\times B</math> הוא יחס.
+זוגות אלה הינם כל זוגות האיברים <math>(a,b)</math> כך ש-<math>a\leq b</math>. (כלומר הגדרנו את היחס המייצג "קטן שווה").
-סימון: אם זוג מסוים, (a,b), נמצא בקבוצת היחס R נהוג לסמן aRb, או <math>(a,b)\in R</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>).
-דוגמא: נביט בקבוצת האנשים A. נגדיר את יחס "בן של" על ידי קבוצת הזוגות הסדורים <math>R\subseteq A\times A</math> כך ש <math>(x,y)\in R</math> אם"ם x הוא בן של y. שימו לב שיש משמעות לכיוון היחס, שכן יש הבדל בין העובדה שאני הבן של מישהו לבין העובדה שהוא הבן שלי.
+דוגמה: נביט בקבוצת האנשים <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>
-הגדרה: תהי קבוצה A. '''יחס הזהות''' הוא <math>R\subseteq A\times A</math> כך ש: <math>I_A=R=\{(a,a):a\in 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>S\circ R=\{(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>.
 ===תרגיל===
 יהיו <math>A=\{1,2\}, B=\{3,4,5\}</math>. נגדיר את היחס: <math>R=\{(1,3),(2,4)\}</math>. בדוק האם:
-א. <math>R^{-1}\circ R=I_A</math>
+א. <math>RR^{-1}=I_A</math>
-ב. <math>R\circ R^{-1}=I_B</math>
+ב. <math>R^{-1}R=I_B</math>
 ==תכונות של יחסים על קבוצה==
-הגדרה: יחס R על קבוצה A פירושו  <math>R\subseteq A\times A</math>
+הגדרה: יחס <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>)
 דוגמאות:
@@ שורה 55: / שורה 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> ואז R גם וגם, S לא ולא.
+'''הערה:''' יחס יכול להיות גם סימטרי וגם אנטי סימטרי. וכמו כן הוא יכול להיות לא זה ולא זה! לדוגמה: <math>A=\{ 1,2,3\} , R=\{ (1,1)\} , S=\{ (1,2),(2,1),(3,2)\}</math> ואז <math>R</math> גם וגם, ואילו <math>S</math> לא ולא.

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

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

תוכן עניינים

יחסים

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

תרגיל

פתרון

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

תרגיל

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

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים