הבדלים בין גרסאות בדף "תרגול 8 תשעז"
(←פתרון) |
|||
שורה 16: | שורה 16: | ||
====פתרון==== | ====פתרון==== | ||
<math>(x,y)\in (A\times B)\cap (C\times D) \iff </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,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 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\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> | <math>(x,y)\in (A\cap C)\times (B\cap D)</math> | ||
גרסה אחרונה מ־17:04, 5 בדצמבר 2017
חזרה לדף מערכי התרגול.
תוכן עניינים
יחסים
המכפלה הקרטזית
הגדרה: המכפלה הקרטזית של שתי קבוצות ו- הינה אוסף כל הזוגות הסדורים - . ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים והאיבר הבא הינו זוג חוקי .
ניתן להכליל את ההגדרה לעיל ל--יה סדורה - כלומר איברים מסודרים.
דוגמה: ו- אזי מתקיים
למתכנתים: זה מאוד דומה ללולאות for מקוננות.
תרגיל
הוכח שלכל קבוצות מתקיים
פתרון
יחסים כתת קבוצה של הזוגות הסדורים
הגדרה: יהיו קבוצות, אזי יקרא יחס (בין לבין ). הרעיון שעומד בבסיסו של יחס הוא האפשרות "להשוות" בין איברי ל-.
דוגמה: ונביט בתת הקבוצה הבאה: . מה מיוחד בזוגות אלה?
זוגות אלה הינם כל זוגות האיברים כך ש-. (כלומר הגדרנו את היחס המייצג "קטן שווה").
הערה: יחס לא חייב לייצג חוקיות מסוימת למשל גם הקבוצה היא יחס. גם היא יחס, וגם הוא יחס.
סימון: אם זוג מסוים,נניח , נמצא בקבוצת היחס נהוג לסמן , או . (אם יש משמעות ליחס כמו לעיל ניתן גם לסמן פשוט ).
דוגמה: נביט בקבוצת האנשים . נגדיר את יחס "בן של" על ידי קבוצת הזוגות הסדורים כך ש- אם"ם הוא בן של . שימו לב שיש משמעות לכיוון היחס, שכן יש הבדל בין העובדה שאני הבן של מישהו לבין העובדה שהוא הבן שלי.
הגדרה: בהינתן יחס , היחס ההפוך הוא היחס המוגדר ע"י היפוך הזוגות הסדורים:
הגדרה: תהי קבוצה . יחס הזהות על הוא כך ש-.
הגדרה: יהיו קבוצות, ו- יחס הכפל הוא היחס: .
תרגיל
יהיו . נגדיר את היחס: . בדוק האם:
א.
ב.
תכונות של יחסים על קבוצה
הגדרה: יחס על קבוצה פירושו .
תהי קבוצה ויחס עליה אזי:
- נקרא רפלקסיבי אם כל איבר מקיים את היחס עם עצמו ( מתקיים ).
- נקרא סימטרי אם גורר שגם (מתקיים ).
- נקרא טרנזיטיבי אם יחס בין ראשון לשני (), ויחס בין השני לשלישי () גורר יחס בין הראשון לשלישי (). (מתקיים ).
- נקרא אנטי סימטרי (חלש) אם וגם גורר כי (מתקיים ובאופן שקול: )
דוגמאות:
- יחס 'שיוויון' הינו רפלקסיבי, סימטרי וטרנזיטיבי
- יחס 'קטן שווה' הינו רפלקסיבי, טרנזיטיבי ואנטי סימטרי
- יחס 'קטן ממש' הינו טרנזיטיבי ואנטי-סימטרי
- יחס 'שיוויון מודולו ' הינו רפלקסיבי, סימטרי וטרנזיטיבי
- יחס 'הכלה' הינו רפלקסיבי, טרנזיטיבי ואנטי-סימטרי
- יחס ' מחלק את ' הינו רפלקסיבי וטרנזיטיבי
- יחס 'אדם שמע על אדם ' הינו רפלקסיבי
הערה: יחס יכול להיות גם סימטרי וגם אנטי סימטרי. וכמו כן הוא יכול להיות לא זה ולא זה! לדוגמה: ואז גם וגם, ואילו לא ולא.