رابطه هم ارزی

صفحه 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.