رابطه هم ارزی

رابطه هم ارزی

اسلاید 1: فصل هشتم: رابطه ها (Relations) بخش 8.5 رابطه هم ارزی (Equivalence Relation)

اسلاید 2: روابط هم ارزی (Equivalence Relations)یک رابطه روی مجموعه A رابطه هم ارزی نامیده می شود، اگر این رابطه بازتابیمتقارن متعدی باشد.

اسلاید 3: عناصر هم ارز (Equivalent Elements)دو عنصری که توسط یک رابطه هم ارزی به هم مربوط شده اند را عناصر هم ارز گویند.رابطه هم‌ارزی بازتابی استهر عنصر با خودش هم‌ارز استرابطه هم ارزی متعدی استاگر a و b هم ارز باشند و همچنین b و c هم ارز باشند، a و c نیز هم ارزند.نمایش هم ارزی عناصر:a  b

اسلاید 4: مثالفرض می کنیم R رابطه ای است که بر روی مجموعه A تعریف شده است. آیا R یک رابطه هم ارزی است؟A = {1, 2, 3, 4, 5} R = {(1,1), (2,2), (3,3), (4,4), (5,5), (1,3), (3,1)}

اسلاید 5: مثال31254آری

اسلاید 6: مثالفرض کنید R رابطه ای روی رشته هایی با حروف انگلیسی باشد به این ترتیب که aRb اگر وفقط اگر طول رشته a و b یکی باشد. آیا R رابطه هم ارزی است؟6

اسلاید 7: مثالفرض کنید که R رابطه ای روی مجموعه اعداد حقیقی به این تر تیب تعریف شده باشد که aRb اگر و فقط اگر a-b عدد صحیح باشد. آیا R رابطه هم ارزی است؟فرض کنید m عدد صحیح بزرگ تر از 1 باشد. نشان دهید رابطه R={(a,b)| a≡b(mod m)} رابطه هم ارزی روی مجموعه اعدا صحیح است.7

اسلاید 8: کلاس های هم ارزی (Equivalence Class)فرض کنید R یک رابطه هم ارزی روی مجموعه A باشد. مجموعه همه عناصری که به عنصر a از مجموعه A مربوط است، کلاس هم ارزی a نامیده می شود. کلاس هم ارزی a متعلق به رابطه R با [a]R نشان داده می شود. وقتی فقط یک رابطه مورد توجه است می توانیم زیر نویس R را حذف کنیم و بنویسیم [a]. [a]R = {s | (s, a)  R}

اسلاید 9: کلاس های هم ارزی (Equivalence Class)اگر R یک رابطه هم ارزی روی A باشد آنگاه کلاس هم ارزی a را به شکل زیر می نویسیم: [a]R = {s | (s, a)  R}اگر b  [a]R آنگاه b را یک representative کلاس هم ارزی a می نامیم [a]R = [b]R

اسلاید 10: مثالکلاس های هم ارزی رابطه 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}

اسلاید 11: مثالفرض کنید که R رابطه ای روی مجموعه اعداد صحیح به این ترتیب تعریف شده باشد که aRb اگروفقط‌اگر a=b یا a=-b . آیا R رابطه هم ارزی است؟ [a] = {a, -a}[7] = {7, -7} [-5] = {5, -5}[0] = {0}11

اسلاید 12: قضیه مهم در مورد کلاس های هم ارزیفرض کنید R رابطه هم ارزی روی مجموعه A باشد. این جمله ها هم ارزند:

اسلاید 13: فرض کنید R یک رابطه هم ارزی روی مجموعه A باشد. اجتماع کلاس های هم ارزی R برابر با مجموعه A می باشد. به عبارت دیگر13

اسلاید 14: قضیه مهم در مورد کلاس های هم ارزیکلاس های هم ارزییا با هم برابر هستند (equal)یا کاملا مجزا از هم هستند (disjoint)[a] ≠ [b]  [a] R ∩[b] R = ∅

اسلاید 15: افرازها (Partitions)کلاس های هم ارزی یک افراز روی A می سازد، زیرا آنها A را به زیرمجموعه های از هم جدا تقسیم می کندیک افراز از مجموعه A دسته ای از زیر مجموعه های ناتهی ازهم جدای مجموعه A می باشند که اجتماع آنها برابر با A است. 15Set AA1A6A5A4A3A2

اسلاید 16: افرازها (Partitions)مجموعه زیر مجموعه های Ai یک افراز از مجموعه S می سازند (I مجموعه اندیس ها می باشد) اگر وفقط اگر:16

اسلاید 17: مثال افرازهاS = {a, b, c, d, e, f }S1 = {a, d, e}S2 = {b}S3 = {c, f }P = {S1, S2, S3}P یک افراز برای مجموعه Sمی باشد

اسلاید 18: مثالفرض کنید R یک رابطه هم ارزی روی مجموعه A باشد. پس کلاس های هم ارزی R یک افراز از مجموعه S می سازد. همچنین اگر افراز { Ai | i∈I} روی مجموعه S داده شود، رابطه هم ارزی R وجود دارد که مجموعه های Ai کلاس های هم ارزی اش باشد.18

اسلاید 19: فصل هشتم: رابطه ها (Relations) بخش 8.6 ترتیب های جزیی (Partial Orderings)

اسلاید 20: ترتیب های جزیی (Partial Orderings)یک رابطه R روی مجموعه S ترتیب جزیی (partial order ) نامیده می شود، اگر این رابطه بازتابیپاد متقارنمتعدی باشد.یک مجموعه S به همراه رابطه ترتیب جزیی R مجموعه ترتیب جزیی یا poset (partially ordered set) نامیده می شود و با (S, R) نمایش داده می شود.

اسلاید 21: مثال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)}

اسلاید 22: مثالبرای مجموعه مورد نظر: 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 می باشد

اسلاید 23: مثالنشان دهید که رابطه بزرگتر یا مساوی روی مجموعه اعداد صحیح، ترتیب جزیی است.رابطه عاد کردن روی مجموعه اعداد صحیح مثبت، ترتیب جزیی است.رابطه زیر مجموعه بودن روی مجموعه توانی مجموعه S ، ترتیب جزیی است.23

اسلاید 24: ترتیب های جزیی (Partial Orderings)در یک مجموعه ترتیب جزیی a≼b به معنای این است که (a,b)∈R a≺b ، یعنی a≼b و a≠bاینجا منظور علامت () نیست. اما رابطه کوچکتر مساوی خود یک مثال از یک رابطه ترتیب جزئی می باشد.24

اسلاید 25: قابل مقایسه و غیر قابل مقایسه (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

اسلاید 26: ترتیب کامل (Total Order)اگر(S,≼) ، مجموعه ترتیب جزیی باشد و هر دو عنصر از مجموعه S قابل مقایسه باشند، S مجموعه ترتیب کامل یا ترتیب خطی (linear order) نامیده می شود. یک مجموعه ترتیب کامل زنجیره (chain) نیز نامیده می شود.مثال: مجموعه ترتیب جزیی (Z,≤) ترتیب کامل است.مثال: مجموعه ترتیب جزیی (Z+,|) ترتیب کامل نیست.26

اسلاید 27: اصل خوش ترتیبی(S,≼) یک مجموعه خوش ترتیب است اگر مجموعه ترتیب کامل باشد و هر زیرمجموعه ناتهی S یک عنصر مینیمم داشته باشد.مجموعه زوج مرتب هایی از اعداد صحیح مثبت، Z+╳ Z+ ، که (a1,a2) ≼ (b1,b2) است اگر a1< b1 یا اگر a1= b1 و a2≤ b2 یک مجموعه خوش ترتیب است.27

اسلاید 28: ترتیب لغوی (Lexicographic Order)دو مجموعه ترتیب جزیی (A1, ≼1) و (A2, ≼2)را داریم. ترتیب جزیی ≼ روی A1╳A2 به این ترتیب تعریف می شود که، زوج مرتب اول کوچکتر از زوج مرتب دوم است اگر عنصر اول زوج مرتب اول از عنصر اول زوج مرتب دوم کوچکتر باشد یا اگر اولین عنصر ها مساوی باشند، عنصر دوم زوج مرتب اول از عنصر دوم زوج مرتب دوم کوچکتر باشد.28

اسلاید 29: مثالمثال: در مجموعه ترتیب جزیی (Z╳Z, ≼) که ≼ رابطه کوچکتر مساوی است. آیا (3,5) ≺ (4,8)، (3,8) ≺ (4,5) و (4,9) ≺ (4,11) ؟29

اسلاید 30: مثالزوج مرتب های با رنگ قرمز از (3,4) کوچکترند

اسلاید 31: ترتیب لغوی (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

اسلاید 32: دیاگرام هاسه (Hasse)نمایش گرافی یک رابطه ترتیب جزیی روی یک مجموعه محدود دارای لبه های زیادی است، تو سط دیاگرام هاسه می توان یک رابطه ترتیب جزیی را به صورت ساده تری نشان داد. 32

اسلاید 33: مراحلگراف جهت دار رابطه را ترسیم می نماییم.یک رابطه ترتیب جزیی، بازتابی است. پس روی همه رئوس حلقه وجود دارد. همه این حلقه هارا حذف می کنیم.یک رابطه ترتیب جزیی، متعدی است. تمام لبه هایی که با خاصیت تعدی قابل استنباط است را حذف می کنیم.تمام لبه ها را به صورتی مرتب می کنیم که جهت فلش ها رو به بالا باشد.جهت همه لبه ها را حذف می کنیم.33

اسلاید 34: مثالساختن نمودار هاسه برای مجموعه ترتیب جزئی: ({1, 2, 3}, ) 1 2 3 1 2 3 1 2 3321321

اسلاید 35: مثالساختن نمودار هاسه برای مجموعه ترتیب جزئی: ({1, 2, 3,4}, )

اسلاید 36: مثالساختن نمودار هاسه برای مجموعه ترتیب جزئی:({1, 2, 3, 4, 6, 8, 12}, |)

اسلاید 37: عناصر ماکزیمال و مینیمال (maximal & minimal)عنصری ماکزیمال است، که از هیچ عنصر دیگری از مجموعه ترتیب جزیی کوچکتر نباشد. a در مجموعه ترتیب جزیی (S, ≼) ماکزیمال است، اگر هیچ b∈S وجود نداشته باشد که a<b. عنصری مینیمال است، که از هیچ عنصر دیگری از مجموعه ترتیب جزیی بزرگتر نباشد. a در مجموعه ترتیب جزیی (S, ≼) مینیمال است، اگر هیچ b∈S وجود نداشته باشد که b<a.در نمودار هاسه ماکزیمال ها نقاط بالایی و مینیمال ها نقاط پایینی هستند.37

اسلاید 38: مثالمجموعه ترتیب جزئی زیر را در نظر بگیرید({, 2, 4, 5, 10, 12, 20, 25}, | ) نمودار هاسه آن به صورت شکل مقابل می باشدعناصر ماکسیمال:12, 20, 25و عناصر مینیمال آن:2, 5می باشند

اسلاید 39: بزرگترین و کوچکترین عناصر (greatest & least element )عنصر a ، بزرگترین عنصر مجموعه ترتیب جزیی (S, ≼) است، اگر برای هر b∈S داشته باشیم b≼a. عنصر a ،کوچکترین عنصر مجموعه ترتیب جزیی (S, ≼) است، اگر برای هر b∈S داشته باشیم a≼b. این عناصر در صورت وجود، یکتا می باشند.39

اسلاید 40: مثال بزرگترین و کوچکترین عنصرb c d a d b c ad e ca b d ca b

اسلاید 41: مثالفرض کنید که S یک مجموعه باشد. بزرگترین عنصر و کوچکترین عنصر را در مجموعه ترتیب جزیی (P(S), ⊆) مشخص کنید.آیا در مجموعه ترتیب جزیی (Z+,|) ، بزرگترین عنصر و کوچکترین عنصر وجود دارد؟41

اسلاید 42: حد بالا و پایینفرض کنید A زیر مجموعه ای از S باشد.اگر u عنصری از مجموعه S باشد به گونه ای که برای هر a∈A ، a≼u این عنصر حد بالای (upper bound) A نام دارد.اگر u عنصری از مجموعه S باشد به گونه ای که برای هر a∈A ، u≼a این عنصر حد پایین (lower bound) A نام دارد.42

اسلاید 43: کوچکترین حد بالای (least upper bound)عنصر x کوچکترین حد بالای زیر مجموعه A نامیده می شود، اگر x حد بالایی باشد که کوچکتر از همه حدبالاهای دیگر A باشد. یعنی، x کوچکترین حد بالای (least upper bound) زیر مجموعه Aاست، اگر به ازاء هر a∈A ، a≼x و به ازاء هر z که حد بالای A است، x≼z.43

اسلاید 44: بزرگترین حد پایین (greatest lower bound)به همین صورت، عنصر y بزرگترین حد پایین زیر مجموعه A نامیده می شود، اگر y حد پایینی باشد که بزرگتر از همه حدپایین های دیگر A باشد. یعنی، x بزرگترین حد پایین (greatest lower bound) زیر مجموعه Aاست، اگر به ازاء هر a∈A ، y≼a و به ازاء هر z که حد پایین A است، z≼y.بزرگترین حد پایین و کوچکترین حد بالا برای هر زیر مجموعه در صورت وجود، یکتا هستند.44

اسلاید 45: مثال h j g f d e b c aماکسیمال: 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

اسلاید 46: مثالبزرگترین حد پایین و کوچکترین حد بالای مجموعه های {3,9,12} و {1,2,4,5,10} را در مجموعه ترتیب جزیی (Z+,|) چیست؟46

اسلاید 47: لتیس ها LATTICES (مشبکه ها)یک مجموعه ترتیب جزئی که هر زیرمجموعه دو عضوی از عناصرش هم کوچکترین حد بالا و هم بزرگترین حد پایین داشته باشد، لتیس نام دارد. لتیسها ویژگی های خاصی دارند و دربسیاری از کاربرد های مختلف مانند مدل های جریان اطلاعات استفاده می شوند و نقش مهمی در جبر بول ایفا می کنند.47

اسلاید 48: مثال

اسلاید 49: مثالآیا مجموعه ترتیب جزیی (Z+,|) یک lattice است؟مشخص کنید که آیا مجموعه های ترتیب جزیی ({1,2,3,4,5}, | ) و ({1,2,4,8,16}, | ) lattice می باشند.آیا مجموعه ترتیب جزیی (P(S),⊆) یک lattice است؟49

اسلاید 50: مرتب سازی توپولوژیکی (Topological sorting)فرض کنید که یک پروژه از 20 کار مختلف تشکیل شده است. بعضی کارها تنها زمانی قابل انجامند که بعضی دیگر به اتمام رسیده باشند.چگونه می توان یک ترتیب برای انجام این کارها یافت؟ برای مدل کردن این مساله یک رابطه تر تیب جزیی روی مجموعه کارها در نظر می گیریم، بنابراین a<b اگر وتنها اگر a وb کارهایی باشند که b نمی تواند قبل از پایان یافتن a شروع شود. برای تولید یک زمانبندی برای پروژه، ما نیاز به تولید یک ترتیب برای همه این 20 کار که سازگار با این مجموعه ترتیب جزیی باشد داریم. ما نشان خواهیم داد که چگونه این کار قابل انجام است.50

اسلاید 51: مرتب سازی توپولوژیکی (Topological sorting)ما با یک تعریف شروع می کنیم. یک ترتیب کامل ≼ با ترتیب جزیی R سازگار است، اگر هرگاه aRb ، آنگاه داشته باشیم a≼b. ساختن یک مجموعه ترتیب کامل سازگار با یک ترتیب جزیی مرتب سازی توپولوژیکی نام دارد.لم 1 . هر مجموعه ترتیب جزیی ناتهی محدود (S, ≼) ، یک عنصر مینیمال دارد.51

اسلاید 52: الگوریتم مرتب سازی توپولوژیکیProcedure topological sort( S: finite poset)K:=1While S≠∅Begin ak:=a minimal element of S {such an element exists by Lemma 1} S:= S – {ak} k:=k + 1End 52

اسلاید 53: مثالیک مجموعه ترتیب کامل سازگار با مجموعه ترتیب جزیی ({1,2,4,5,12,20}, |) بسازید.برای انجام یک پروژه در یک شرکت کامپیوتری باید 7 کار انجام شود. بر اساس نمودار هس این 7 کار، یک ترتیب انجام کار برای به پایان رساندن پروژه پیدا کنید.53

اسلاید 54: مثال 54

اسلاید 55: مثال55