סריג מתמטיקה דיסקרטי - מתמטיקה בדידה

תן L להיות קבוצה לא ריקה הסגורה תחת שתי פעולות בינאריות הנקראות מפגש והצטרפות, מסומנות ב- ∧ ו- ∨. אז L נקרא סריג אם האקסיומות הבאות מתקיימות כאשר a, b, c הם אלמנטים ב-L:

1) חוק קוממוטטיבי: -
(א) a ∧ b = b ∧ a (ב) a ∨ b = b ∨ a

2) משפט אסוציאטיבי:-
(א) (a ∧ b)∧ c = a ∧(b∧ c) (b) (a ∨ b) ∨ c = a ∨ (b ∨ c)

3) חוק הקליטה: -
(א) a ∧ ( a ∨ b) = a (ב) a ∨ ( a ∧ b) = a

שְׁנִיוּת:

הדואל של כל משפט בסריג (L,∧ ,∨ ) מוגדר כהצהרה שמתקבלת על ידי החלפת ∧ ו∨.

לדוגמה , הדואל של a ∧ (b ∨ a) = a ∨ a הוא a ∨ (b ∧ a )= a ∧ a

סריג מוגבל:

סריג L נקרא סריג מוגבל אם יש לו את האלמנט הגדול ביותר 1 והאלמנט הקטן ביותר 0.

דוגמא:

קבוצת הכוח P(S) של קבוצת S בפעולות של חיתוך ואיחוד היא סריג מוגבל שכן ∅ הוא האלמנט הקטן ביותר של P(S) והקבוצה S היא האלמנט הגדול ביותר של P(S).
קבוצת +ve המספר השלם I ₊לפי הסדר הרגיל של ≦ אינו סריג מוגבל מכיוון שיש לו אלמנט 1 לפחות אבל האלמנט הגדול ביותר אינו קיים.

תכונות של סריג מוגבל:

אם L הוא סריג מוגבל, אז עבור כל אלמנט a ∈ L, יש לנו את הזהויות הבאות:

a ∨ 1 = 1
a ∧1= א
a ∨0=a
a ∧0=0

מִשׁפָּט: הוכח שכל סריג סופי L = {a ₁,א ₂,א ₃....א _נ} מוגבל.

הוכחה: נתנו את הסריג הסופי:

L = {א ₁,א ₂,א ₃....א _נ}

לפיכך, האלמנט הגדול ביותר של סריג L הוא a ₁∨ א ₂∨ א _{3∨....∨א _נ.}

כמו כן, האלמנט הקטן ביותר של הסריג L הוא a ₁∧ א ₂∧א ₃∧....∧א _נ.

מאז, היסודות הגדולים והקטנים ביותר קיימים עבור כל סריג סופי. לפיכך, L מוגבל.

סריג משנה:

שקול תת-קבוצה לא ריקה L ₁של סריג ל' ואז ל' ₁נקרא תת-סריג של L אם L ₁עצמו הוא סריג כלומר, הפעולה של L כלומר, a ∨ b ∈ L ₁ו- a ∧ b ∈ L ₁בכל פעם ש- ∈ L ₁ו-b ∈ L ₁.

דוגמא: שקול את הסריג של כל +ve המספרים השלמים I ₊תחת פעולת החלוקה. הסריג ד _נמכל המחלקים של n > 1 הוא תת-סריג של I ₊.

קבע את כל תת-הסריגים של D ₃₀המכילים לפחות ארבעה יסודות, D ₃₀={1,2,3,5,6,10,15,30}.

פִּתָרוֹן: הסריגים המשנה של ד ₃₀המכילים לפחות ארבעה אלמנטים הם כדלקמן:

1. {1, 2, 6, 30} 2. {1, 2, 3, 30}
3. {1, 5, 15, 30} 4. {1, 3, 6, 30}
5. {1, 5, 10, 30} 6. {1, 3, 15, 30}
7. {2, 6, 10, 30}

סריג איזומורפי:

שני סריג ל ₁ול ₂נקראים סריג איזומורפי אם יש בידוקציה מ-L ₁ל-L ₂כלומר, f: ל ₁⟶ ל ₂, כך ש-f (a ∧ b) =f(a)∧ f(b) ו-f (a ∨ b) = f (a) ∨ f (b)

דוגמא: קבע אם הסריגים המוצגים בתאנה הם איזומורפיים.

פִּתָרוֹן: הסריגים המוצגים בתאנה הם איזומורפיים. שקול את המיפוי f = {(a, 1), (b, 2), (c, 3), (d, 4)}. לדוגמה f (b ∧ c) = f (a) = 1. כמו כן, אנו יש f (ב) ∧ f(c) = 2 ∧ 3 = 1

סריג הפצה:

סריג L נקרא סריג חלוקתי אם עבור רכיבים a, b ו-c של L, הוא עונה על המאפיינים ההפצתיים הבאים:

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

אם הסריג L אינו עונה על המאפיינים הנ'ל, הוא נקרא סריג לא חלוקתי.

דוגמא:

ערכת הכוח P (S) של הקבוצה S תחת פעולת הצומת והאיחוד היא פונקציה חלוקתית. מאז,
a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c)
וכן, גם a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪c) עבור כל קבוצות a, b ו-c של P(S).
הסריג המוצג באיור II הוא חלוקה. מכיוון שהוא עונה על מאפייני ההפצה עבור כל השלשות המוסדרות שנלקחו מ-1, 2, 3 ו-4.

סריגים משלימים ומשלימים:

תן L להיות סריג מוגבל עם גבול תחתון o וגבול עליון I. תן a להיות אלמנט אם L. אלמנט x ב-L נקרא משלים של a אם a ∨ x = I ו- a ∧ x = 0

אומרים שסריג L הוא משלים אם L מוגבל ולכל אלמנט ב-L יש משלים.

דוגמא: קבע את המשלים של a ו-c באיור:

פִּתָרוֹן: המשלים של a הוא ד. מאז, a ∨ d = 1 ו- ∧ d = 0

המשלים של c לא קיים. מכיוון שלא קיים אלמנט c כך ש-c ∨ c'=1 ו-c ∧ c'= 0.

סריג מודולרי:

סריג (L, ∧,∨) נקרא סריג מודולרי אם a ∨ (b ∧ c) = (a ∨ b) ∧ c בכל פעם a ≦ c.

מוצר ישיר של סריג:

תן (ל ₁∨ ₁∧ ₁) ו (ל ₂∨ ₂∧ ₂) יהיו שני סריג. אז (L, ∧,∨) הוא המכפלה הישירה של סריג, כאשר L = L ₁x L ₂שבה הפעולה הבינארית ∨(join) ו∧(נפגשים) על L הן כאלה שעבור כל (a ₁,ב ₁) ו (א ₂,ב ₂) ב-L.