رابطه هم ارزی

صفحه 1:
فصل هشتم: رايطه ها (561211015) بخش ۸۰۵ رابطه هم ارز ,3« ‎Equivalence)‏ ‏ممعم ) 

صفحه 2:
(Equi valenc e Relations) ‏ارزی‎ ‏ابط هم ارز‎ ‏رواد‎ نامیده می ارزى نامي مجموعه ‎A‏ رابطه هم ابطه روی مج ‎ab, pst‏ شود. اگر این رب بازتابی |-أمتقارن شد. آمتعدی با 

صفحه 3:
عناصر هم ارز ‎(Equivalent Elements)‏ * دو عنصری که توسط یک رابطه هم ارزی به هم مربوط شده اند را عناصر هم ارز گویند. رابطه هم‌ارزی بازتابی است هر عنصر با خودش هم‌ارز است * رابطه هم ارزی متعدی است >اگر 2و 9 هم ارز باشند و همچنین "و » هم ارز باشند. ۵ و نیز هم ارزند. * نمایش هم ارزی عناصر: ‎a~b‏ 

صفحه 4:
Sh ‏منال‎ * فرض می کنیم 8 رابطه ای است که بر روی مجموعه ۸ تعریف شده است. ‎LT‏ * یک رابطه هم ارزی است؟ (5 ,4 ر3 ,2 ,11 -< ۸ 9 ‎*R= {(1,1), (2,2), (3,3), (4,4), (5,5),‏ })3,1( ,)1,3( 

صفحه 5:
آری 

صفحه 6:
با ‎SS‏ ‏منال ‏* فرض کنید 3 رابطه ای روی رشته هایی با حروف انگلیسی باشد به اين ترتيب که 2۳80 اگر وفقط اگر طول رشته ‎b ga‏ یکی باشد. آیا *1 رابطه هم ارزی است؟ 

صفحه 7:
‎SS ۲ ۲ ۲ 3 ۰ ۰‏ ‎a‏ ‏منال ‏* فرض کنید که 3 رابطه ای روی مجموعه اعداد حقیقی به اين ‏تر تیب تعریف شده باشد که 2۳0 اگر و فقط اگر 0-0 ‎ove‏ ‏صحیح باشد. آیا * رابطه هم ارزی است؟ ‏* فرض کنید 7 عدد صحیح بزرگ تر از ۱ باشد. نشان دهید ‎e@ asl, R= {(a,b)| a=b(mod m)} aa,‏ !)53 روی مجموعه اعدا صحیح است. 

صفحه 8:
EE * (Equivalence Class) ‏كلاس هاى هم ارزى‎ # فرض کنید 1 یک رابطه هم ارزی روی مجموعه ۸ باشد. مجموعه همه عناصری که به عنصر 2 از مجموعه ۸ مربوط است. کلاس هم ارزی 2 نامیده می شود. کلاس هم ارزی 2 متعلق به رابطه 7 با [2]م نشان داده می شود. وقتی فقط یک رنه برد تیچ نس می تانع, زیر تویتن ۶ را حذف [a], = {s| (s, a) © R} 

صفحه 9:
کلاس های هم ارزی ‎(Equivalence Class)‏ ‎pil‏ */ یک رابطه هم ارزی روی ۸ باشد آنگاه کلاس هم ارزی 4 را به شکل زیر می نویسیم: ‎[a], = {s| (s, a) € R} ‏"ااكر م,[2] ع ط آنكاه 6 را يى 161656121211176 كلاس هم ارزى 2 مى ناميم ‏جلطا ع م[2] 

صفحه 10:
ای ۲ لا مثال "" كلاس هاى هم ارزى رابطه 2 بر روى مجموعه لل = {1, 2, 3, 4, 5} = {(1,1), (2,2), (3,3), (4,4), (5,5), a 3), (3,1)} [1] = {1, 3} [2] = {2} [3] = {3, 1} [4] = {4} [5] = {5} 

صفحه 11:
۹۹۰۰۰۰ مثال * فرض کنید که 8 رابطه ای روی مجموعه اعداد صحیح به این ترتیب تعریف شده باشد که 4۳10 اگروفقطاگر ۵-0 یا -عه. آیا 8 رابطه هم ارزی است؟ ‎[a] = {a, -a}‏ ,5{ = ]5-[ }7- ,7{ = ]7[ -5} [0] = {0} 

صفحه 12:
‎SSS ۲۲‏ قضیه مهم در مورد کلاس های‌هم ارزی ‏# فرض کنید 7 رابطه هم ارزی روی مجموعه ۸ باشد. این جمله ها هم ارزند: ‎(۰89 ‏(]ع ما(‎ i) [a] N[B] FB 

صفحه 13:
SS ‏با‎ فرض کنید *1 یک رابطه هم ارزی روی مجموعه ۸ باشد. اجتماع کلاس های هم ارزی ‏ برابر با مجموعه ۸ می باشد. به عبارت دیگر Ulele =4 acA 

صفحه 14:
‎SSS ۲۲‏ قضیه مهم در مورد کلاس های‌هم ارزی "ا كلاس هاى هم ارزى ‎(equal) acu ply ee bl! )015[01121( ‏-أيا كاملا مجزا از هم هستند‎ ‎6 - > ‏0۱ا »۱0۱ ماه‎ # lal 

صفحه 15:
0 2 ‎a‏ ‎(Partitions) b }1 51‏ * کلاس های هم ارزی یک افراز روی ۸ می سازد. زیرا آنها ۸ را به زیرمجموعه های از هم جدا تقسیم می کند * یک افراز از مجموعه ۸ دسته ای از زیر مجموعه های ناتهی ازهم جدای مجموعه ۸ می باشند که اجتماع آنها برابر با ۸ <A) Set A 5 است. 

صفحه 16:
a (Partitions) b }1 51 ‏مجموعه زیر مجموعه های ,4 یک افراز از مجموعه 5 مى‎ " ‏سازند (1 مجموعه اندیس ها می باشد) اگر وفقط اگر:‎ ‏عمط عع بم‎ 61, Aj Aj ‏معطت 0 ع‎ 4 j, and دولا jel 

صفحه 17:
با کی ۲ مثال افرازها ,6 ,0 6 بط ر9) < 5 S, = {a, d, e} S, = {b} ‏دود‎ {c, f} زوك ررك ‎P= {S,,‏ 47 يكلفراز بسرلی‌مجموعه کمی‌ساشد 

صفحه 18:
a ‏منال‎ "" فرض کنید 6 یک رابطه هم ارزی روی مجموعه ۸ باشد. پس کلاس های هم ارزی 7۶ یک افراز از مجموعه کر می سازد. همچنین اگر افراز [ 261 | با روی مجموعه ‎S‏ داده شود. رابطه هم ارزی 18 وجود دارد که مجموعه های بل کلاس های هم ارزی اش باشد. 

صفحه 19:
فصل هشتم: رايطه ها (561211015) مر ترتیب های جزیی 5 ‎(Partial Order:‏ 

صفحه 20:
(Partial Orderings) (23> ‏ترتیب های‎ * یک ‎Partial) 25> as 5S seqox0 69) R sal)‏ 7 ) نامیده می شود اگر اين رابطه بازتابی پاد متقارن متعدی باشد. "ايك مجموعه ‎٩‏ به همراه رابطه ترتیب جزیی 1 مجموعه ترتیب جزیی يا 0706790 09712117 0561 ‎SED‏ نامیده می شود و با (70 ,5) نمایش داده می شود. 

صفحه 21:
2S ee ‏مثال لا‎ ۸ < 11, 2, ‏ر3‎ 4 R= {(1,1), (12), (1,3), (L&, (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)} 

صفحه 22:
"۳۳۲۲۲۲۲۲۲۲۲ ۲ منال ‎w‏ ‏برای مجموعه مورد نظر: }4 ,3 ,2 ,1{ = ,)1,4( ,)1,3( ,)1,2( ,)1,1({ = ,)2 0 })4,4( ,)3,4( ,)3,3( ,)2,4( ,)2,3( 1 يكقرتيبجزئيمىباشد و 10 ,4) ی کمجموعه ‎wh poset lh, jets‏ 

صفحه 23:
a ‏منال‎ # نشان دهید که رابطه بزرگتر یا مساوی روی مجموعه اعداد صحیح. ترتیب جزیی است. # رابطه عاد كردن روى مجموعه اعداد صحیح مثبت. ترتیب جزيى است. * رابطه زير مجموعه بودن روى مجموعه توانى مجموعه 5. ترتيب جزيى است. 

صفحه 24:
a (Partial Orderings) (23> gh i; ‏لا‎ ‏در يك مجموعه ترتيب جزيى (251 به معناى اين است كه‎ ws ae 53 ‏رطری‎ ‎a#b ,a<b....a<b® ينجا منظور علامت (>) نیست. اما ربطه کوچکتر مساوی خود یک مثال از یک رابطه ترتیب جزتی می باشد. 

صفحه 25:
ee eee ‏قابل مقايسه و غير قابل مقايسه‎ (Comparable / Incomparable) poset )5,>( ‏عناصر ۸و از مجموعه ترتیب جزیی يا‎ * 58 ‏قابل مقایسه گفته می شود اگر ۵50 یا‎ ‏باشند که نه 850 و نه‎ ٩ ‏وقتی 2 و 0 عناصری از مجموعه‎ * ‏را داشته باشیم. ۵و 9 غیر قابل مقایسه گفته می‎ > شوند. * منال: در مجموعه ترتیب جزیی (,|) آیا ۳ و ‎٩‏ قابل مقایسه هستند؟ آیا ۵ و ۷ قابل مقایسه هستند؟ 

صفحه 26:
eee w (Total Order) JolS ‏ترتیب‎ ‏اگر(ک,<) . مجموعه ترتیب جزیی باشد و هر دو عنصر از‎ * ‏مجموعه ک قابل مقایسه باشند. ک مجموعه ترتیب کامل يا‎ ‏نامیده می شود. یک‎ )1112687 orden ‏ترتیب خطی‎ ‏مجموعه ترتیب کامل زنجیره (0112110) نیز نامیده می شود.‎ * مثال: مجموعه ترتیب جزیی ‎Cus ys (BZ)‏ كامل است. * مثال: مجموعه ترتیب جزیی (2:|) ترتیب کامل نیست. 

صفحه 27:
‎SS ۲ ۲ ۲ 3 ۰ ۰‏ ‎a‏ ‏اصل خوش ترتیبی * (5,<) یک مجموعه خوش ترتیب است اگر مجموعه ترتیب ‏کامل باشد و هر زیرمجموعه ناتهی 58 یک عنصر مینیمم داشته باشد. ‏* مجموعه زوج مرتب هایی از اعداد صحیح مثبت. 2 ۰۰27 که (یربع) 2 (,0,,0) است اگر , > ره يا اگر <,2 ‏,و و8 که یک مجموعه خوش ترتیب است. 

صفحه 28:
(Lexicographic Order) ‏ترقیب لغوی‎ "ا دو مجموعه ترتيب جزيى ‎Xa) 9 Ay, Sy)‏ ریشرا داریم. ترتيب جزيى < روى 40:()42 به اين ترتيب تعريف مى شود كهء زوج مرتب اول كوجكتر از زوج مرتب دوم است اگر عنصر اول زوج مرتب اول از عنصر اول زوج مرتب دوم کوچکتر باشد یا اگر اولین عنصر ها مساوی باشند. عنصر دوم زوج مرتب اول از عنصر دوم زوج مرتب دوم کوچکتر باشد. 

صفحه 29:
با ‎SS‏ ‏مثال ‏# مثال: در مجموعه ترتیب جزیی (2()2, <<) که << رابطه کوچکتر مساوی است. آیا (۳,۵) << (۴,۸» (۳,۸) < (۴,۵) و (۴,۹) < (۴,۱۱) ۲ 

صفحه 30:
ال ۰ منال © The McGraw-Hill Companies, Inc. all rights reserved : ‏تب های با‎ j رع مره ى 1 ۶ ۰ ۰ ۰ ۰ ۰ ۰ ۵ رنگ قرمز از (۳,۴) ‎4D 6D) GD OD‏ 3,7) 27 )7 ‎cen‏ را هو هو و و وه ۰ (1,6) 2.6) G6) 4,6) G,6) 66) (7,6) Yr 35 ۰ ۰ ۰ ۰ ۰ ec as) 25) G5) 45) G5) 65) (7,5) ۰ ۰ ۰ ۰ ۰ ۰ ۰ )1,4 (2.4) 34۵ 44) (5.4) )64۵( (7.4) ۰ ۰ ۰ ۰ ۰ ۰ ‏و‎ ‎)۱,3( (2,3) G3) 43) 66,33 )63( )7,3( ۰ ۰ ۰ ۰ ۰ ۰ ec (2) )22 G2) 4,2) )5,2 )6,2 (7,2) ۰ ۰ ۰ ۰ ۰ ۰ ec a) QD BD @4)D GY 6) TD 

صفحه 31:
اس ترقیب لغوی ‎(Lexicographic Order)‏ * ترتیب لغوی می تواند روی ضرب کارتزین 2 مجموعه ترتیب ‎Xp) aie‏ ریش ‎Ag, Xp)‏ ... و (رگ رم تعریف شود. به اين ترتیب که ‎Dy, Dy) > yp, Agree, AQ)‏ 0): اگر ‎La,<, b,‏ یک عدد صحیح 1<0 وجود داشته باشد که ,8 - و ..ء ب8 درط و يبرط يبرك يبية "" مثال: آیا (۱,۲,۳,۵) > (۱,۲,:۴,۳) 

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

صفحه 33:
ا يي مراحل "" كراف جهت دار رابطه را ترسيم مى نماييم. "ا يك رابطه ترتيب جزيىء بازتابى است. يس روى همه رئوس حلقه وجود دارد. همه اين حلقه هارا حذف مى كنيم. "" يك رابطه ترتيب جزيىء متعدى است. تمام لبه هايى كه با خاصیت تعدی قابل استنباط است را حذف می کنیم. * تمام لبه ها را به صورتی مرتب می کنیم که جهت فلش ها رو به بالا باشد. "ا جهت همه لبه ها را حذف مى كنيم. 

صفحه 34:
منال ({1, 2, 3}, ee 7 ‏دار هاسه براى مح‎ ‏ساختن نمو‎ "" Ae Ao Loket + Pabst 

صفحه 35:
(©) KK ‏جص‎ © The McGraw-Hill Companies, Inc. all rights reserved. 4 4 * ساختن نمودار هاسه برای مجموعه ترتیب جزنی: ,}3,4 ,2 ,1{( ‎s)‏ ‏1 1 0 0( 

صفحه 36:
(© The MeGraw-Hil Companies, Ine. al ights reserved, Vay Ady VI 

صفحه 37:
a5 72122711161 6۶( ‏عناصر ماکز یمال و مینیمال‎ (minimal عنصری ماکزیمال است. که از هیچ عنصر دیگری از مجموعه ترتیب جزیی کوچکتر نباشد. 7" ۸ در مجموعه ترتییجزیی(٩,‏ ) ماکزیما لٍستلگر هیج 65 2 وجود نطلشته باشد که > عنصری مینیمال است. که از هیچ عنصر دیگری از مجموعه ترتیب جزیی بزرگتر نباشد. ۲ ۵ در مجموعه ترتیبجزیی(۹, ) مینیم |ستلگر هیچ 5 ©[ وجود نطشته باشد که > در نمودار هاسه ماکزیمال ها نقاط بالایی و مینیمال ها نقاط پایینی 

صفحه 38:
a ‏منال‎ مجموعه ترتیب جزئی زیر را در نظر بگیرید. ‎VY) OF Yb‏ ۰:۲۰ ۱۰/۲۵) ©The McGraw-Hill Companies, Inc. all rights reserved. 1 ‏نمودار هاسه آن به صورت‎ 12 20 1 . ABU coo (hile JSS ‏عناصر ماکسیمال:‎ YO ۰ ۲ 4 10 25 3 ‏و عناصر مینیمال آن:‎ oy 

صفحه 39:
a ‏بزرگترین و کوچکترین عناصر‎ (greatest & least element) * عنصر ۸ بزرگترین عنصر مجموعه ترتیب جزیی ‎,٩(‏ <2) است. اگر برای هر 065 داشته باشیم 52 * عنصر ۵ ءکوچکترین عنصر مجموعه ترتیب جزیی (5, <) است. اگر برای هر 065 داشته باشیم 85. این عناصر در صورت وجود. یکتا می باشند. 

صفحه 40:
لد سب در 

صفحه 41:
a ‏منال‎ "" فرض كنيد كه 5 یک مجموعه باشد. بزرگترین عنصر و کوچکترین عنصر را در مجموعه ترتیب جزیی ((۲)5, 2) * آیا در مجموعه ترتیب جزیی (.,|) . بزرگترین عنصر و کوچکترین عنصر وجود دارد؟ 

صفحه 42:
a ‏حد بالا و پایین‎ * فرض کنید ۸ زیر مجموعه ای از 8 باشد. ‎wit‏ ۷ عنصری از مجموعه ‎٩‏ باشد به گونه ای که برای هر ‎(upper bound) ¢¥b a> pace 4 la€A.aXxu‏ ۸ نام دارد. ‏۴ گر ا عنصری از مجموعه ‎٩‏ باشد به گونه ای که برای هر ۵ للع این عنصر حد پایین (0120] 00۲۷۵۲ ۸ نام دارد. 

صفحه 43:
a (least upper bound) B¥b ve oy yS> oS * عنصر ۶ کوچکترین حد بالای زیر مجموعه ۸ نامیده می شود. اگر > حد بالایی باشد که کوچکتر از همه حدبالاهای دیگر ‎A‏ ‏باشد. یعنی» * کوچکترین ‎least UPPeD) Yb v>‏ 0 زیر مجموعه ۸است. اگر به ازاء هر . 26۸ 5 و به ازاء هر 2 که حد بالای 4 است. 3052 

صفحه 44:
a (greatest lower ‏بزرکترین حد پایین (070ظ‎ به همین صورت. عنصر ۷ بزرگترین حد پایین زیر مجموعه ‎A‏ ‏نامیده می شود. اگر ۷ حد پایینی باشد که بزرگتر از همه حدپایین ‎x «px sol A So cb‏ بزرگترین حد پایین 0176065 0 0۲۷67۲) زير مجموعه ۸است. اگر به ازاء هر ۵ 6 و به ازاء هر 2 که حد پایین ۸ است. 25 بزرگترین حد و کوچکترین حد بالا برای هر زیر مجموعه در صورت وجود. یکتا هستند. 

صفحه 45:
منال ماکسیمال: ‏ ,13 مینیمال: ۵ ‎hj‏ ‏بزركترين عنصر: نداريم 6 8 كوجكترين عنصر: © 8 3 حد بالای 6 ,,۵): ظ ‎e, fj,‏ ۳ حد بالای 6 ,6 ,,2): 2ل رأ رگ ‎e,‏ ‏کوچکترین حد بالای (6,ظ,8]: 6 حد پایین 06 ,,6): 2 بزرگترین حد پایین (0,ظ,2): 2 

صفحه 46:
با ‎SS‏ ‏منال * بزرگترین حد پایین و کوچکترین حد بالای مجموعه های [۳,۹,۱۲] و (1۱:۲,۴,۵,۱۰ را در مجموعه ترتیب جزیی (|) چیست؟ 

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

صفحه 48:
(c) ۳ (a) (b) 

صفحه 49:
۹۹۰۰۰۰ منال * آیا مجموعه ترتیب جزیی (|) یک 1۵1106 است؟ "ا مشخص كنيد كه آيا مجموعه هاى ترتيب جزیی ([۱۰۱۱,۲,۱۳,۴۵) و((۱:۲,۴,۸,۱۶]:|) 06لأ1می باشند. * آیا مجموعه ترتیب جزیی ((2,۳)5) یک 121106 است؟ 

صفحه 50:
a (Topological sorting) ‏مرتب سازی توپولوژیکی‎ * فرض کنید که یک پروژه از ۲۰ کار مختلف تشکیل شده است. بعضی کارها تنها زمانی قابل انجامند که بعضی دیگر به اتمام رسیده باشند.چگونه می توان یک ترتیب برای انجام این کارها یافت؟ برای مدل كردن اين مساله يك رابطه تر تيب جزیی روی مجموعه کارها در نظر مى كيريم, بنابراين 2>1 اكر وتنها اكر 4 و 0 كارهايى باشند که " نمى تواند قبل از يايان يافتن 8 شروع شود. براى توليد یک زمانبندی برای پروژه» ما نياز به توليد يك ترتيب براى همه اين ۰ كار كه سازكار با اين مجموعه ترتيب جزيى باشد داريم. ما نشان خواهيم داد كه جكونه اين كار قابل انجام است. 

صفحه 51:
00 2 ‎w‏ ‏مرتب سازی توپولوژیکی ‎(Topological sorting)‏ * ما با یک تعریف شروع می کنیم. یک ترتیب کامل 2 با ترتیب جزیی * سازگار است. اگر هرگاه ۵110 . آنگاه داشته باشیم 0 ساختن یک مجموعه ترتیب کامل سازگار با یک ترتیب جزیی مرتب سازی توپولوژیکی نام دارد. "ا لم ۱ . هر مجموعه ترتیب جزیی ناتهی محدود (5, <2) ۰ یک عنصر مینیمال دارد. 

صفحه 52:
اس الگوریتم مرتب سازی توپولوژیکی ‎Procedure topological sort( S: finite poset)‏ ‎K:=1‏ ‎While S¥@‏ ‎Begin‏ ‎a,:=a minimal element of S {such an‏ ‎element exists by Lemma 1}‏ ‎S:= S - {a,}‏ ‎k:=k+1‏ ‎End‏ 

صفحه 53:
Sh ‏منال‎ ‏یک مجموعه ترتیب کامل سازگار با مجموعه ترتیب جزیی‎ "" ‏بسازید.‎ )| ,]۱,۲,۴,۵,۱۲,۲۰(( ‏برای انجام یک پروژه در یک شرکت کامپیوتری باید ۷ کار‎ * انجام شود. بر اساس نمودار هس این ۷ کار یک ترتیب انجام کار برای به پایان رساندن پروژه پیدا کنید. 

صفحه 54:
ده منال 2 ‏و2‎ | 12 20 | 2 20 | 12 20 4 4 4 a 4 2 5] 2 5| 2 1 Minimal clement 1 5 2 4 chosen FIGURE 9 A Topological Sort of ({1,2, 4, 5, 12, 20}, |). 

صفحه 55:
تس منال g ‏َو‎ 01 QD 2] 2 | ‏بر‎ ‎7 8 8 6 6 & 85 5 6 Minimal ‘element A c 8 chosen FIGURE 11 A Topological Sort of the Tasks. ۸ 6 5 ۲۱6۲۲ ۱0 The Hasse Diagram for Seven Tasks. 

)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 مثال 1 3 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با [ R]aنشان داده می شود .وقتی فقط یک رابطه مورد توجه است می توانیم زیر نویس 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 }[2] = {2 }[4] = {4 }[1] = {1, 3 }[3] = {3, 1 }[5] = {5 مثال فرض کنید که Rرابطه ای روی مجموعه اعداد صحیح به این ترتیب تعریف شده باشد که aRbاگروفقط‌اگر a=bیا . a=-bآیا Rرابطه هم ارزی است؟ }[a] = {a, -a [-5] = {5, }[7] = {7, -7 }-5 }[0] = {0 11 قضیه مهم در مورد کالس های هم ارزی فرض کنید Rرابطه هم ارزی روی مجموعه Aباشد. این جمله ها هم ارزند:  فرض کنید Rیک رابطه هم ارزی روی مجموعه Aباشد. اجتماع کالس های هم ارزی Rبرابر با مجموعه Aمی باشد. به عبارت دیگر 13 قضیه مهم در مورد کالس های هم ارزی کالس های هم ارزی ‏یا با هم برابر هستند ()equal ‏یا کامال مجزا از هم هستند ()disjoint [ ] b[ ≠ ] a ‏R ][a] R ∩[b ∅= افرازها ()Partitions کالس های هم ارزی یک افراز روی Aمی سازد ،زیرا آنها Aرا به زیرمجموعه های از هم جدا تقسیم می کند یک افراز از مجموعه Aدسته ای از زیر مجموعه های ناتهی ازهم جدای مجموعه Aمی باشند که اجتماع آنها برابر با A است. ‏A2 ‏A6 ‏A1 ‏A3 ‏A5 15 ‏A4 ‏Set A افرازها ()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به معنای این است که (R∈)a,b ، 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 ، که ( )b1,b2( ≼ )a1,a2است اگر a1< b1یا اگر =a1 b1و a2≤ b2یک مجموعه خوش ترتیب است. 27 ترتیب لغوی ()Lexicographic Order دو مجموعه ترتیب جزیی ( )A1, ≼1و ()A2, ≼2را داریم. ترتیب جزیی ≼ روی A1╳A2به این ترتیب تعریف می شود که ،زوج مرتب اول کوچکتر از زوج مرتب دوم است اگر عنصر اول زوج مرتب اول از عنصر اول زوج مرتب دوم کوچکتر باشد یا اگر اولین عنصر ها مساوی باشند ،عنصر دوم زوج مرتب اول از عنصر دوم زوج مرتب دوم کوچکتر باشد. 28 مثال مثال :در مجموعه ترتیب جزیی ( )≼ ,Z╳Zکه ≼ رابطه کوچکتر مساوی است .آیا ( )4,5( ≺ )3,8( ،)4,8( ≺ )3,5و ( )4,11( ≺ )4,9؟ 29 مثال زوج مرتب های با رنگ قرمز از ()3,4 کوچکترند ترتیب لغوی ()Lexicographic Order ترتیب لغوی می تواند روی ضرب کارتزین nمجموعه ترتیب جزیی ( ... ، )A2, ≼2( ، )A1, ≼1و ( )An, ≼nتعریف شود .به این ترتیب که (b1, b2,…,( ≺ )a1, a2,…, an )bn؛ اگر a1≺1 b1یا یک عدد صحیح i>0وجود داشته باشد که bi = ai ، ... ، b1 = a1و ai+1≺i+1 bi+1 مثال :آیا ()1,2,4,3( ≺ )1,2,3,5 31 دیاگرام هاسه ()Hasse ‏ 32 نمایش گرافی یک رابطه ترتیب جزیی روی یک مجموعه محدود دارای لبه های زیادی است ،تو سط دیاگرام هاسه می توان یک رابطه ترتیب جزیی را به صورت ساده تری نشان داد. مراحل ‏ ‏ ‏ ‏ ‏ 33 گراف جهت دار رابطه را ترسیم می نماییم. یک رابطه ترتیب جزیی ،بازتابی است .پس روی همه رئوس حلقه وجود دارد .همه این حلقه هارا حذف می کنیم. یک رابطه ترتیب جزیی ،متعدی است .تمام لبه هایی که با خاصیت تعدی قابل استنباط است را حذف می کنیم. تمام لبه ها را به صورتی مرتب می کنیم که جهت فلش ها رو به باال باشد. جهت همه لبه ها را حذف می کنیم. مثال ساختن نمودار هاسه برای مجموعه ترتیب جزئی: )({1, 2, 3},  3 3 2 2 1 1 1 1 2 3 2 3 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 مثال مجموعه ترتیب جزئی زیر را در نظر بگیرید ({) | ,}25 ,20 ,12 ,10 ,5 ,4 ,2 , نمودار هاسه آن به صورت شکل مقابل می باشد عناصر ماکسیمال: 25 ,20 ,12 و عناصر مینیمال آن: 5 ,2 می باشند بزرگترین و کوچکترین عناصر () greatest & least element عنصر ، aبزرگترین عنصر مجموعه ترتیب جزیی ()≼ ,S است ،اگر برای هر b∈Sداشته باشیم .b≼a عنصر ، aکوچکترین عنصر مجموعه ترتیب جزیی ()≼ ,S است ،اگر برای هر b∈Sداشته باشیم .a≼bاین عناصر در صورت وجود ،یکتا می باشند. 39 مثال بزرگترین و کوچکترین عنصر ‏d ‏d ‏c b ‏c ‏a ‏b ‏a ‏d ‏b ‏d ‏c ‏a ‏e ‏c ‏a ‏b مثال فرض کنید که 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 : حد باالی {e, f, j, h :}a,b,c حد باالی {e, f, j, h :}a,b,c,e کوچکترین حد باالی {e :}a,b,c حد پایین {a :}a,b,c بزرگترین حد پایین {a :}a,b,c ‏j ‏h ‏f ‏g ‏e ‏d ‏c ‏b ‏a مثال بزرگترین حد پایین و کوچکترین حد باالی مجموعه های { }3,9,12و { }1,2,4,5,10را در مجموعه ترتیب جزیی ( )|,+Zچیست؟ 46 لتیس ها ( LATTICESمشبکه ها) یک مجموعه ترتیب جزئی که هر زیرمجموعه دو عضوی از عناصرش هم کوچکترین حد باال و هم بزرگترین حد پایین داشته باشد ،لتیس نام دارد. لتیس ها ویژگی های خاصی دارند و دربسیاری از کاربرد های مختلف مانند مدل های جریان اطالعات استفاده می شوند و نقش مهمی در جبر بول ایفا می کنند. 47 مثال مثال آیا مجموعه ترتیب جزیی ( )|,+Zیک latticeاست؟ مشخص کنید که آیا مجموعه های ترتیب جزیی ({ ) | ,}1,2,3,4,5و ({ lattice ) | ,}1,2,4,8,16می باشند. آیا مجموعه ترتیب جزیی () )⊆,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