محاسبات نرم

محاسبات نرم

۱ مطلب با موضوع «ریاضیات پایه :: مشبکه :: نیم مشبکه» ثبت شده است

 نیم مشبکه Semilattice

 مجموعه ی مرتب جزئی S همراه با عمل دوتایی را یک رسند-نیم مشبکه (meet-semilattice) گوییم هرگاه برای هر دو عضو x و y از S بزرگترین کران پایین (Greatest Lower Bound) {x,y} موجود باشد.

 بزرگترین کران پایین {x,y} را با inf{x,y} یا x˄y نمایش می دهیم.

 به همین ترتیب وست-نیم مشکبه را تعریف می کنیم.

 در وست-نیم مشبکه (join-semilattice)، به ازای هر دو عضو x و y از S، کوچکترین کران بالای (Least Upper Bound) {x,y} موجود است.

 کوچکترین کران بالای {x,y} را با sup{x,y} یا x˅y نمایش می دهیم.

 

 می توانیم تعریفی جبری از نیم مشبکه ارائه دهیم.

 برای این منظور مجموعه ی S را همراه با عمل دوتایی ˄ در نظر می گیریم به طوریکه  شرایط زیر برقرار باشد:

x˄x=x

x˄y=y˄x

x˄(y˄z)=(x˄y)˄z

 در این صورت S را رسند-نیم مشبکه گویند.

 و به همین نحو وست-نیم مشبکه تعریف می شود.

 مثال:

                                                       

 این نمودار هاسه، نمایش دهنده ی یک رسند-نیم مشبکه (و وست-نیم مشبکه) است. زیرا meet join) هر دو عضو موجود است و شرایط ذکر شده در بالا برقرار است:

 به وضوح دو شرط اول برقرارند. شرط سوم را بررسی می کنیم:

a˄(b˄c) = a˄a = a

(a˄b)˄c = a˄c = a

 پس دو طرف تساوی با هم برابرند. با بررسی شرط سوم بر تک تک عناصر، نیم مشبکه بودن نمودار فوق، بدست می‌آید.

 

سوال: نشان دهید شکل زیر هیچ یک از انواع نیم مشبکه نیست.

                                            


نکته: با رابطه ی زیر می توان نشان داد دو تعریف فوق (تعریف ترتیبی و تعریف جبری) از نیم مشبکه با هم معادلند:

x y x˅y=y

x y x˄y=x


 

مرور بر مطالب قبل:

                                                           


  • تکراری