فصل هشتم: رابطه ها (Relations) بخش 8.5 رابطه هم ارزی (Equivalence Relation)
روابط هم ارزی (Equivalence Relations)
یک رابطه روی مجموعه A رابطه هم ارزی نامیده می شود، اگر این رابطه
بازتابی
متقارن
متعدی باشد.
عناصر هم ارز (Equivalent Elements)
دو عنصری که توسط یک رابطه هم ارزی به هم مربوط شده اند را عناصر هم ارز گویند.
رابطه هم ارزی بازتابی استهر عنصر با خودش هم ارز است
رابطه هم ارزی متعدی استاگر a و b هم ارز باشند و همچنین b و c هم ارز باشند، a و c نیز هم ارزند.
نمایش هم ارزی عناصر:
a b
مثال
فرض می کنیم R رابطه ای است که بر روی مجموعه A تعریف شده است. آیا R یک رابطه هم ارزی است؟
A = {1, 2, 3, 4, 5}
R = {(1,1), (2,2), (3,3), (4,4), (5,5), (1,3), (3,1)}
مثال
3
1
2
5
4
آری
مثال
فرض کنید R رابطه ای روی رشته هایی با حروف انگلیسی باشد به این ترتیب که aRb اگر وفقط اگر طول رشته a و b یکی باشد. آیا R رابطه هم ارزی است؟
6
مثال
فرض کنید که R رابطه ای روی مجموعه اعداد حقیقی به این تر تیب تعریف شده باشد که aRb اگر و فقط اگر a-b عدد صحیح باشد. آیا R رابطه هم ارزی است؟
فرض کنید m عدد صحیح بزرگ تر از 1 باشد. نشان دهید رابطه R={(a,b)| a≡b(mod m)} رابطه هم ارزی روی مجموعه اعدا صحیح است.
7
کلاس های هم ارزی (Equivalence Class)
فرض کنید R یک رابطه هم ارزی روی مجموعه A باشد. مجموعه همه عناصری که به عنصر a از مجموعه A مربوط است، کلاس هم ارزی a نامیده می شود. کلاس هم ارزی a متعلق به رابطه R با [a]R نشان داده می شود. وقتی فقط یک رابطه مورد توجه است می توانیم زیر نویس R را حذف کنیم و بنویسیم [a].
[a]R = {s | (s, a) R}
کلاس های هم ارزی (Equivalence Class)
اگر R یک رابطه هم ارزی روی A باشد آنگاه کلاس هم ارزی a را به شکل زیر می نویسیم:
[a]R = {s | (s, a) R}
اگر b [a]R آنگاه b را یک representative کلاس هم ارزی a می نامیم
[a]R = [b]R
مثال
کلاس های هم ارزی رابطه R بر روی مجموعه A
A = {1, 2, 3, 4, 5}
R = {(1,1), (2,2), (3,3), (4,4), (5,5), (1,3), (3,1)}
[1] = {1, 3} [2] = {2}
[3] = {3, 1} [4] = {4}
[5] = {5}
مثال
فرض کنید که R رابطه ای روی مجموعه اعداد صحیح به این ترتیب تعریف شده باشد که aRb اگروفقط اگر a=b یا a=-b . آیا R رابطه هم ارزی است؟
[a] = {a, -a}
[7] = {7, -7} [-5] = {5, -5}
[0] = {0}
11
قضیه مهم در مورد کلاس های هم ارزی
فرض کنید R رابطه هم ارزی روی مجموعه A باشد. این جمله ها هم ارزند:
فرض کنید R یک رابطه هم ارزی روی مجموعه A باشد. اجتماع کلاس های هم ارزی R برابر با مجموعه A می باشد. به عبارت دیگر
13
قضیه مهم در مورد کلاس های هم ارزی
کلاس های هم ارزی
یا با هم برابر هستند (equal)
یا کاملا مجزا از هم هستند (disjoint)
[a] ≠ [b] [a] R ∩[b] R = ∅
افرازها (Partitions)
کلاس های هم ارزی یک افراز روی A می سازد، زیرا آنها A را به زیرمجموعه های از هم جدا تقسیم می کند
یک افراز از مجموعه A دسته ای از زیر مجموعه های ناتهی ازهم جدای مجموعه A می باشند که اجتماع آنها برابر با A است.
15
افرازها (Partitions)
مجموعه زیر مجموعه های Ai یک افراز از مجموعه S می سازند (I مجموعه اندیس ها می باشد) اگر وفقط اگر:
16
مثال افرازها
S = {a, b, c, d, e, f }
S1 = {a, d, e}
S2 = {b}
S3 = {c, f }
P = {S1, S2, S3}
P یک افراز برای مجموعه Sمی باشد
مثال
فرض کنید R یک رابطه هم ارزی روی مجموعه A باشد. پس کلاس های هم ارزی R یک افراز از مجموعه S می سازد. همچنین اگر افراز { Ai | i∈I} روی مجموعه S داده شود، رابطه هم ارزی R وجود دارد که مجموعه های Ai کلاس های هم ارزی اش باشد.
18
فصل هشتم: رابطه ها (Relations) بخش 8.6 ترتیب های جزیی (Partial Orderings)
ترتیب های جزیی (Partial Orderings)
یک رابطه R روی مجموعه S ترتیب جزیی (partial order ) نامیده می شود، اگر این رابطه
بازتابی
پاد متقارن
متعدی باشد.
یک مجموعه S به همراه رابطه ترتیب جزیی R مجموعه ترتیب جزیی یا poset (partially ordered set) نامیده می شود و با (S, R) نمایش داده می شود.
مثال
A = {1, 2, 3, 4}
R = {(1,1), (1,2), (1,3), (1,4), (2,2),
(2,3), (2,4), (3,3), (3,4), (4,4)}
مثال
برای مجموعه مورد نظر:
A = {1, 2, 3, 4}
R = {(1,1), (1,2), (1,3), (1,4), (2,2),
(2,3), (2,4), (3,3), (3,4), (4,4)}
R یک ترتیب جزئی می باشد و (A, R) یک مجموعه ترتیب جزئی یا poset می باشد
مثال
نشان دهید که رابطه بزرگتر یا مساوی روی مجموعه اعداد صحیح، ترتیب جزیی است.
رابطه عاد کردن روی مجموعه اعداد صحیح مثبت، ترتیب جزیی است.
رابطه زیر مجموعه بودن روی مجموعه توانی مجموعه S ، ترتیب جزیی است.
23
ترتیب های جزیی (Partial Orderings)
در یک مجموعه ترتیب جزیی a≼b به معنای این است که (a,b)∈R
a≺b ، یعنی a≼b و a≠b
اینجا منظور علامت () نیست. اما رابطه کوچکتر مساوی خود یک مثال از یک رابطه ترتیب جزئی می باشد.
24
قابل مقایسه و غیر قابل مقایسه (Comparable / Incomparable)
عناصر a و b از مجموعه ترتیب جزیی یا poset (S,≼) قابل مقایسه گفته می شود اگر a≼b یا b≼a
وقتی a وb عناصری از مجموعه S باشند که نه a≼b و نه b≼a را داشته باشیم، a و b غیر قابل مقایسه گفته می شوند.
مثال: در مجموعه ترتیب جزیی (Z+,|) آیا 3 و 9 قابل مقایسه هستند؟ آیا 5 و 7 قابل مقایسه هستند؟
25
ترتیب کامل (Total Order)
اگر(S,≼) ، مجموعه ترتیب جزیی باشد و هر دو عنصر از مجموعه S قابل مقایسه باشند، S مجموعه ترتیب کامل یا ترتیب خطی (linear order) نامیده می شود. یک مجموعه ترتیب کامل زنجیره (chain) نیز نامیده می شود.
مثال: مجموعه ترتیب جزیی (Z,≤) ترتیب کامل است.
مثال: مجموعه ترتیب جزیی (Z+,|) ترتیب کامل نیست.
26
اصل خوش ترتیبی
(S,≼) یک مجموعه خوش ترتیب است اگر مجموعه ترتیب کامل باشد و هر زیرمجموعه ناتهی S یک عنصر مینیمم داشته باشد.
مجموعه زوج مرتب هایی از اعداد صحیح مثبت، Z+╳ Z+ ، که (a1,a2) ≼ (b1,b2) است اگر a1< b1 یا اگر a1= b1 و a2≤ b2 یک مجموعه خوش ترتیب است.
27
ترتیب لغوی (Lexicographic Order)
دو مجموعه ترتیب جزیی (A1, ≼1) و (A2, ≼2)را داریم. ترتیب جزیی ≼ روی A1╳A2 به این ترتیب تعریف می شود که، زوج مرتب اول کوچکتر از زوج مرتب دوم است اگر عنصر اول زوج مرتب اول از عنصر اول زوج مرتب دوم کوچکتر باشد یا اگر اولین عنصر ها مساوی باشند، عنصر دوم زوج مرتب اول از عنصر دوم زوج مرتب دوم کوچکتر باشد.
28
مثال
مثال: در مجموعه ترتیب جزیی (Z╳Z, ≼) که ≼ رابطه کوچکتر مساوی است. آیا (3,5) ≺ (4,8)، (3,8) ≺ (4,5) و (4,9) ≺ (4,11) ؟
29
مثال
زوج مرتب های با رنگ قرمز از (3,4) کوچکترند
ترتیب لغوی (Lexicographic Order)
ترتیب لغوی می تواند روی ضرب کارتزین n مجموعه ترتیب جزیی (A1, ≼1) ، (A2, ≼2) ، … و (An, ≼n) تعریف شود. به این ترتیب که (a1, a2,…, an) ≺ (b1, b2,…, bn)؛ اگر a1≺1 b1 یا یک عدد صحیح i>0 وجود داشته باشد که bi = ai ، … ، b1 = a1 و ai+1≺i+1 bi+1
مثال: آیا (1,2,3,5) ≺ (1,2,4,3)
31
دیاگرام هاسه (Hasse)
نمایش گرافی یک رابطه ترتیب جزیی روی یک مجموعه محدود دارای لبه های زیادی است، تو سط دیاگرام هاسه می توان یک رابطه ترتیب جزیی را به صورت ساده تری نشان داد.
32
مراحل
گراف جهت دار رابطه را ترسیم می نماییم.
یک رابطه ترتیب جزیی، بازتابی است. پس روی همه رئوس حلقه وجود دارد. همه این حلقه هارا حذف می کنیم.
یک رابطه ترتیب جزیی، متعدی است. تمام لبه هایی که با خاصیت تعدی قابل استنباط است را حذف می کنیم.
تمام لبه ها را به صورتی مرتب می کنیم که جهت فلش ها رو به بالا باشد.
جهت همه لبه ها را حذف می کنیم.
33
مثال
ساختن نمودار هاسه برای مجموعه ترتیب جزئی:
({1, 2, 3}, )
مثال
ساختن نمودار هاسه برای مجموعه ترتیب جزئی:
({1, 2, 3,4}, )
مثال
ساختن نمودار هاسه برای مجموعه ترتیب جزئی:
({1, 2, 3, 4, 6, 8, 12}, |)
عناصر ماکزیمال و مینیمال (maximal & minimal)
عنصری ماکزیمال است، که از هیچ عنصر دیگری از مجموعه ترتیب جزیی کوچکتر نباشد.
a در مجموعه ترتیب جزیی (S, ≼) ماکزیمال است، اگر هیچ b∈S وجود نداشته باشد که a<b.
عنصری مینیمال است، که از هیچ عنصر دیگری از مجموعه ترتیب جزیی بزرگتر نباشد.
a در مجموعه ترتیب جزیی (S, ≼) مینیمال است، اگر هیچ b∈S وجود نداشته باشد که b<a.
در نمودار هاسه ماکزیمال ها نقاط بالایی و مینیمال ها نقاط پایینی هستند.
37
مثال
مجموعه ترتیب جزئی زیر را در نظر بگیرید
({, 2, 4, 5, 10, 12, 20, 25}, | )
نمودار هاسه آن به صورت شکل مقابل می باشد
عناصر ماکسیمال:
12, 20, 25
و عناصر مینیمال آن:
2, 5
می باشند
بزرگترین و کوچکترین عناصر (greatest & least element )
عنصر a ، بزرگترین عنصر مجموعه ترتیب جزیی (S, ≼) است، اگر برای هر b∈S داشته باشیم b≼a.
عنصر a ،کوچکترین عنصر مجموعه ترتیب جزیی (S, ≼) است، اگر برای هر b∈S داشته باشیم a≼b. این عناصر در صورت وجود، یکتا می باشند.
39
مثال بزرگترین و کوچکترین عنصر
مثال
فرض کنید که S یک مجموعه باشد. بزرگترین عنصر و کوچکترین عنصر را در مجموعه ترتیب جزیی (P(S), ⊆) مشخص کنید.
آیا در مجموعه ترتیب جزیی (Z+,|) ، بزرگترین عنصر و کوچکترین عنصر وجود دارد؟
41
حد بالا و پایین
فرض کنید A زیر مجموعه ای از S باشد.
اگر u عنصری از مجموعه S باشد به گونه ای که برای هر a∈A ، a≼u این عنصر حد بالای (upper bound) A نام دارد.
اگر u عنصری از مجموعه S باشد به گونه ای که برای هر a∈A ، u≼a این عنصر حد پایین (lower bound) A نام دارد.
42
کوچکترین حد بالای (least upper bound)
عنصر x کوچکترین حد بالای زیر مجموعه A نامیده می شود، اگر x حد بالایی باشد که کوچکتر از همه حدبالاهای دیگر A باشد. یعنی، x کوچکترین حد بالای (least upper bound) زیر مجموعه Aاست، اگر به ازاء هر a∈A ، a≼x و به ازاء هر z که حد بالای A است، x≼z.
43
بزرگترین حد پایین (greatest lower bound)
به همین صورت، عنصر y بزرگترین حد پایین زیر مجموعه A نامیده می شود، اگر y حد پایینی باشد که بزرگتر از همه حدپایین های دیگر A باشد. یعنی، x بزرگترین حد پایین (greatest lower bound) زیر مجموعه Aاست، اگر به ازاء هر a∈A ، y≼a و به ازاء هر z که حد پایین A است، z≼y.
بزرگترین حد پایین و کوچکترین حد بالا برای هر زیر مجموعه در صورت وجود، یکتا هستند.
44
مثال
ماکسیمال: h, j
مینیمال: a
بزرگترین عنصر: نداریم
کوچکترین عنصر: a
حد بالای {a,b,c}: e, f, j, h
حد بالای {a,b,c,e}: e, f, j, h
کوچکترین حد بالای {a,b,c}: e
حد پایین {a,b,c}: a
بزرگترین حد پایین {a,b,c}: a
مثال
بزرگترین حد پایین و کوچکترین حد بالای مجموعه های {3,9,12} و {1,2,4,5,10} را در مجموعه ترتیب جزیی (Z+,|) چیست؟
46
لتیس ها LATTICES (مشبکه ها)
یک مجموعه ترتیب جزئی که هر زیرمجموعه دو عضوی از عناصرش هم کوچکترین حد بالا و هم بزرگترین حد پایین داشته باشد، لتیس نام دارد.
لتیسها ویژگی های خاصی دارند و دربسیاری از کاربرد های مختلف مانند مدل های جریان اطلاعات استفاده می شوند و نقش مهمی در جبر بول ایفا می کنند.
47
مثال
مثال
آیا مجموعه ترتیب جزیی (Z+,|) یک lattice است؟
مشخص کنید که آیا مجموعه های ترتیب جزیی ({1,2,3,4,5}, | ) و ({1,2,4,8,16}, | ) lattice می باشند.
آیا مجموعه ترتیب جزیی (P(S),⊆) یک lattice است؟
49
مرتب سازی توپولوژیکی (Topological sorting)
فرض کنید که یک پروژه از 20 کار مختلف تشکیل شده است. بعضی کارها تنها زمانی قابل انجامند که بعضی دیگر به اتمام رسیده باشند.چگونه می توان یک ترتیب برای انجام این کارها یافت؟ برای مدل کردن این مساله یک رابطه تر تیب جزیی روی مجموعه کارها در نظر می گیریم، بنابراین a<b اگر وتنها اگر a وb کارهایی باشند که b نمی تواند قبل از پایان یافتن a شروع شود. برای تولید یک زمانبندی برای پروژه، ما نیاز به تولید یک ترتیب برای همه این 20 کار که سازگار با این مجموعه ترتیب جزیی باشد داریم. ما نشان خواهیم داد که چگونه این کار قابل انجام است.
50
مرتب سازی توپولوژیکی (Topological sorting)
ما با یک تعریف شروع می کنیم. یک ترتیب کامل ≼ با ترتیب جزیی R سازگار است، اگر هرگاه aRb ، آنگاه داشته باشیم a≼b. ساختن یک مجموعه ترتیب کامل سازگار با یک ترتیب جزیی مرتب سازی توپولوژیکی نام دارد.
لم 1 . هر مجموعه ترتیب جزیی ناتهی محدود (S, ≼) ، یک عنصر مینیمال دارد.
51
الگوریتم مرتب سازی توپولوژیکی
Procedure topological sort( S: finite poset)
K:=1
While S≠∅
Begin
ak:=a minimal element of S {such an element exists by Lemma 1}
S:= S – {ak}
k:=k + 1
End
52
مثال
یک مجموعه ترتیب کامل سازگار با مجموعه ترتیب جزیی ({1,2,4,5,12,20}, |) بسازید.
برای انجام یک پروژه در یک شرکت کامپیوتری باید 7 کار انجام شود. بر اساس نمودار هس این 7 کار، یک ترتیب انجام کار برای به پایان رساندن پروژه پیدا کنید.
53
مثال
54
مثال
55