ברוכים הבאים ליחידת הלימוד "יחסים ופונקציות" בקורס "מתמטיקה בדידה". יחידה זו היא אבן יסוד בהבנה של מבנים דיסקרטיים ומהווה בסיס חיוני לתחומים רבים במדעי המחשב, החל מאלגוריתמים ומבני נתונים ועד ללוגיקה ותורת החישוביות. נתמקד בהגדרות פורמליות, תכונות מרכזיות ושיטות הוכחה, תוך שימת דגש על סגנון הבחינה הטכניונית המצריך דיוק והבנה עמוקה.
יחסים: קישור בין איברים
יחס הוא דרך לתאר קשר בין איברים בקבוצה או בין איברים משתי קבוצות שונות. זוהי הכללה של מושגים כמו "קטן מ-" או "שווה ל-".
תכונות יחסים על קבוצה A
רפלקסיביות (Reflexivity)
לכל a ∈ A, מתקיים (a,a) ∈ R. כל איבר קשור לעצמו.
סימטריות (Symmetry)
לכל a,b ∈ A, אם (a,b) ∈ R אז גם (b,a) ∈ R. הקשר דו-כיווני.
אנטי-סימטריות (Anti-symmetry)
לכל a,b ∈ A, אם (a,b) ∈ R וגם (b,a) ∈ R, אז בהכרח a=b. אם יש קשר דו-כיווני, האיברים זהים.
טרנזיטיביות (Transitivity)
לכל a,b,c ∈ A, אם (a,b) ∈ R וגם (b,c) ∈ R, אז בהכרח (a,c) ∈ R. אם A קשור ל-B ו-B קשור ל-C, אז A קשור ל-C.
סוגי יחסים חשובים
פונקציות: התאמה חד-ערכית
פונקציה היא סוג מיוחד של יחס, המבטיח שלכל איבר בתחום יש בדיוק איבר אחד מתאים בטווח.
- תחום (Domain): הקבוצה A.
- טווח (Codomain): הקבוצה B.
- תמונה (Range/Image): קבוצת כל האיברים ב-B שהם ערכים של הפונקציה עבור איברים מ-A. מסומן Im(f) = {f(a) | a ∈ A}.
סוגי פונקציות
חד-חד-ערכית (Injective / One-to-one)
לכל a₁, a₂ ∈ A, אם f(a₁) = f(a₂) אז בהכרח a₁ = a₂. איברים שונים בתחום ממופים לאיברים שונים בטווח.
על (Surjective / Onto)
לכל b ∈ B קיים a ∈ A כך ש-f(a) = b. כל איבר בטווח הוא תמונה של לפחות איבר אחד בתחום.
הפיכה / חד-חד-ערכית ועל (Bijective / One-to-one correspondence)
פונקציה שהיא גם חד-חד-ערכית וגם על. פונקציה כזו היא הפיכה (קיימת פונקציה הופכית).
שאלות לדיון
- הגדירו יחס R על Z (קבוצת המספרים השלמים) כך ש-(a,b) ∈ R אם ורק אם a - b הוא כפולה של 3. הוכיחו ש-R הוא יחס שקילות. תארו את מחלקות השקילות.
- בהינתן פונקציה f: Z → Z המוגדרת ע"י f(x) = 2x + 1. האם f חד-חד-ערכית? האם f על? הוכיחו את טענותיכם.
- בהינתן פונקציות f: R → R המוגדרת ע"י f(x) = x² ו-g: R → R המוגדרת ע"י g(x) = x + 1. חשבו את (f ∘ g)(x) ואת (g ∘ f)(x). האם הרכבת פונקציות היא פעולה קומוטטיבית?
נקודות לתשובת מודל
- ליחס שקילות:
- רפלקסיביות: לכל a ∈ Z, a - a = 0, ו-0 הוא כפולה של 3. לכן (a,a) ∈ R.
- סימטריות: נניח (a,b) ∈ R, כלומר a - b = 3k עבור k ∈ Z. אז b - a = -(a - b) = -3k = 3(-k). לכן b - a הוא כפולה של 3, ו-(b,a) ∈ R.
- טרנזיטיביות: נניח (a,b) ∈ R ו-(b,c) ∈ R. אז a - b = 3k₁ ו-b - c = 3k₂ עבור k₁, k₂ ∈ Z. נחבר את המשוואות: (a - b) + (b - c) = 3k₁ + 3k₂, כלומר a - c = 3(k₁ + k₂). לכן a - c הוא כפולה של 3, ו-(a,c) ∈ R.
- מחלקות שקילות: [0] = {..., -3, 0, 3, ...}, [1] = {..., -2, 1, 4, ...}, [2] = {..., -1, 2, 5, ...}. אלו קבוצות המספרים השלמים מודולו 3.
- לפונקציה f(x) = 2x + 1:
- חד-חד-ערכית: נניח f(x₁) = f(x₂). אז 2x₁ + 1 = 2x₂ + 1. נפחית 1 משני האגפים: 2x₁ = 2x₂. נחלק ב-2: x₁ = x₂. לכן f חד-חד-ערכית.
- על: f אינה על Z. ניקח איבר כלשהו בטווח, למשל y = 2 ∈ Z. האם קיים x ∈ Z כך ש-f(x) = 2? כלומר 2x + 1 = 2. אז 2x = 1, ו-x = 1/2. אבל 1/2 ∉ Z. לכן אין x שלם כזה, ו-f אינה על.
- להרכבת פונקציות:
- (f ∘ g)(x) = f(g(x)) = f(x + 1) = (x + 1)² = x² + 2x + 1.
- (g ∘ f)(x) = g(f(x)) = g(x²) = x² + 1.
- מכיוון ש-x² + 2x + 1 ≠ x² + 1 (למשל עבור x=1: 4 ≠ 2), הרכבת פונקציות אינה פעולה קומוטטיבית באופן כללי.