بستار (ریاضی): تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز {{بدون منبع}} |
Mohsen mzlm (بحث | مشارکت‌ها) صفحهٔ جدید: {{بستار رابطه ها}} ==بستار رابطه ها== فرض کنيد R رابطه ای روی مجموعه ی A باشد. R ممکن است بعضی از ويژگی ه... |
||
خط ۱:
{{بستار رابطه ها}}
==بستار رابطه ها==
فرض کنيد R رابطه ای روی مجموعه ی A باشد. R ممکن است بعضی از ويژگی ها مثلا ويژگی P (که می تواند بازتابی, تقارنی, تعدی و ... باشد) را داشته باشد يا نداشته باشد. اگر رابطه ای مانند S وجود داشته باشد که ويژگی P را دارا باشد و رابطه ی R را شامل شود و زير مجموعه ی هر رابطه ی ديگری که ويژگی P را دارد و رابطه ی R زير مجموعه ی آن است باشد آنگاه S بستار رابطه ی R نسبت به ويژگی P است.
در زير بستار رابطه ها ی بازتابي, تقارنی و تعدی را می بينيم.
----
===بستار بازتابی===
رابطه ی {(R={(1,1),(1,2),(2,1),(3,2 روی مجموعه ی {A={1,2,3 را در نظر بگيريد R بازتابی نيست برای اينکه R را بازتابی کنيم کافی است دو عضو (2,2) و (3,3) را به R اضافه کنيم چون اين دو عضو تنها دو عضو به شکل (a,a) هستند که a عضو A است و (a,a) عضو A نيست. رابطه ی بازتابی ساخته شده شامل رابطه ی R است همچنين اين رابطه زيرمجموعه ی همه ی روابط بازتابی است که R زير مجموعه ی آنهاست پس اين مجموعه ی جديد بستار بازتابی رابطه ی R است.
در حالت کلي برای اينکه بستار بازتابی رابطه ی R را بدست آوريم کافی است همه ی عضوهای (a,a) متمايز ممکن که a عضو مجموعه ی A باشد و (a,a) عضو R نباشد را به R اضافه کنيم پس اگر تعريف کنيم { Δ={(a,a) | a ∈ A بستار بازتابی R از رابطه ی R∪Δ بدست می آيد (Δ رابطه ی قطری روی A ناميده می شود)
----
===بستار تقارنی===
رابطه ی {(R={(1,1),(1,2),(2,2),(2,3),(3,1),(3,2 روی مجموعه ی {A={1,2,3 را در نظر بگيريد اين رابطه تقارنی نيست. برای اينکه R را تقارنی کنيم کافی است دو عضو (1,3) و (2,1) را به R اضافه کنيم زيرا اين دو تنها عضو های به فرم (a,b) هستند که (b,a) عضو R است ولی خودشان عضو R نيستند. مجموعه ی حاصل تقارنی است و شامل R نيز می باشد و همچنين زير مجموعه ی هر مجموعه ی تقارنی است که R زير مجموعه ی آنهاست پس اين رابطه بستار تقارنی R است.
از اين مثال می توان نتيجه گرفت که بستار تقارنی R با اضافه کردن هر عضو به فرم (a,b) به R بدست می آيد به شرط اينکه (b,a) عضو R باشد ولی خود (a,b) عضو R نباشد. اگر تعريف کنيم {R<sup>-1</sup>={(a,b)|(b,a)∈R بستار تقارنی R از رابطه ی R∪R<sup>-1</sup> بدست می آيد.(R<sup>-1</sup> رابطه ی معکوس رابطه ی R ناميده می شود.)
----
===بستار تعدی===
فرض کنيد می خواهيم بستار تعدی رابطه ی R را بدست آوريم آيا اضافه کردن هر عضو به فرم (a,c) به R به شرط اينکه (a,b) و(b,c) عضو R باشند کافی است؟
به مثال دقت کنيد:
رابطه ی {(R={(1,3),(1,4),(2,1),(3,2 روی مجموعه ی {A={1,2,3,4 را در نظر بگيريد.
اين رابطه تعدی نيست زيرا شامل همه ی عضوهای (a,c) به شرط اينکه (a,b) و (b,c) عضو R باشند نمي شود. عضو های به اين فرم عبارت اند از (1,2) , (2,3) , (2,4) و (3,1) اضافه کردن اين عضو ها رابطه ی R را تعدی نخواهد کرد! چون رابطه ی حاصل شامل اعضا ی (3,1) و (1,4) است ولی عضو (3,4) را ندارد اين مثال نشان می دهد که ساختن بستار تعدی رابطه ی R به سادگی ساختن بستار بازتابی يا تقارنی رابطه ی R نيست.
برای بدست آوردن تعريف کلی به چند تعريف اوليه نياز داريم که در زير آمده است.
ترکيب دو تابع:
:فرض کنيد R رابطه ای از A به B ,S رابطه ای از B به C باشد, رابطه ی SoR رابطه ای از A به C است که شامل همه ی عضو های به صورت (a,c) است به طوريکه (a,b) عضو R و (b,c) عضو S باشد.
R<sup>n</sup>:
:R<sup>n</sup> را به صورت بازگشتي نعريف می کنيم داريم:
:R<sup>1</sup>=R
:R<sup>n</sup>= R<sup>n-1</sup>oR
برای اينکه تعريف R<sup>n</sup> درست باشد لازم است که R رابطه ای روی يک مجموعه باشد.
حال اگر <sup>*</sup>R بستار تعدی رابطه ی R باشد داريم:
اين مطلب را به صورت شهودی اثبات می کنيم اثبات دقيق آن با استفاده از نظريه گراف ها ممکن است.
گفتيم در مرحله ی اول برای اينکه R تعدی کنيم لازم است همه ی اعضای (a,c) که (a,b) و (b,c) عضو R است ولی خودشان عضو R نيستند را به R اضافه کنيم اين مطلب معادل با اين است که R<sup>2</sup> يا RoR را با R اجتماع کنيم به عبارت ديگر R∪R<sup>2</sup> . حال فرض کنيد سه عضو (c,d) , (b,c) و (a,b) عضو R باشند می دانيم با اين عمل اعضای (a,c) و (b,d) به R اضافه می شوند حال چون دو عضو (a,b) و (b,d) عضو مجموعه ی حاصل هستند بايد عضو (a,d) هم عضو آن باشد. اما اگر به تعريف R<sup>3</sup> دقت کنيم در اين تعريف داريم R<sup>3</sup>= R<sup>2</sup>oR .يعنی R<sup>3</sup> شامل همه ی عضو های (x,z) است به شرطی که (x,y) عضو R و (y,z) عضو R<sup>2</sup> باشد پس R<sup>3</sup> شامل (a,d) نيز هست چون (a,b) عضو R و (b,d) عضو R<sup>2</sup> است.
پس می توان رابطه ی بهتری به صورت R∪R<sup>2</sup>∪R<sup>3</sup> نوشت و به بستار تعدی R نزديک تر شد اما اين کافی نيست. به صورت بالا می توان مشاهده کرد که برای بدست آوردن بستار تعدی R لازم است اجتماع R<sup>n</sup> ها (n∈N) را بدست آوريم يا همان:
R<sup>*</sup> = <math>\bigcup_{n=1}^{\infty}</math> R<sup>n</sup>
| |||