دراین فصلها مجموعههای باترتیب جزئی، شامل شبکهها وحیربول رامورد مطالعه قرار میدهد.دین سافتارها درتئوری مجموعهها، جیر، مرتب سازی وجستجو، وبویژه دربیربول برای ساخت نمایشات منطقی مدارهای کامپیوتری مفید هستند.
مجموعهها با ترتییب جزئی (poset):
یک رابطه R در A ترتیب جزئی خواهیم گفت هرگاه بازتابی، نامتقارن ومستعدی باشد مجموعه A را بهمراه ترتیب جزیی R، مجموعه با ترتیب جزیی گفته و آنرا (R,A) نمایش خواهیم داد. معروفترین ترتیب جزیی، روابط≥,≤ در R می باشند. بدین دلیل، وقتی که در حالت عمومی جهت از ترتیب جزیی R میشود، ما اغلب سمبولهای ≥,≤ رابکار خواهیم بود. این مطلب، بخاطر سپردن ویژگیهای R را ساده تر و آشنا تر می کندئ . سمبول ≤ می تواند برای ترتیبهای جزیی متفاوت در مجموعههای متفاوت بکار برده شود. بنابراین، نباید این سمبولها را با رابطه متفاوت ≤ و یا ≥ در و یا در R اشتباه کرد. اگر الزامی به تمیز دادن ترتیبهای جزیی از یکدیگر باشد، و این ترتیبهای جزیی را با (≥ , ≥_1 ) ́ , ≤ ́ , ≤_1 و غیره نمایش خواهیم داد.
اگر (A ,≤) یک مجموعه با ترتیب جزیی باشد، در این صورت ماهواره سمبول ≥ را برای دادن ترتیب جزیی بکار خواهیم بود، در نتیجه (A ,≥) دو گان (A ,≤) خواهد بود. بهمین طریق دو گان (A ,≤) با (A ,≤)، دو گان (B ,≤) با (B ,≤) نمایش داده خواهند شد.
اگر (A ,≤) یک مجموعه با ترتیب جزیی باشد، عناصر a و b را قابل مقایسه خواهیم داشت . (b ,≤a) یا (a ,≤b)
دقت کنید که در یک poset لزومی ندارد که هر زوج از عناصر قابل مقایسه باشند.
اگر (A ,≤) و (B ,≤) ودو poset باشند در این صورت (A ,≤) فیزیک poset است که در آن ترتیب جزیی بصورت زیر تعریف شده است :
(a,b) ≤ (a ́,b ́) اگر B b≤b ,A a≤a
دقت کنید که سمبول ≤ بعنوان سه ترتیب جزیی متفاوت بکار رفته است خواننده براحتی می تواند در هر لحظه تعیین کنید که کدامیک از آنها مورد نظر است .
اگر (A ,≤) یک poset باشد، گوییم که a
بدین تریب را ترتیب قاموسی و یا ترتیب دیکسیونری می خوانند . وقتی که A و B مجموعههای کاملا مرتب باشند، در این صورت ترتیب قاموسی در A*B فیزیک ترتیب کامل است .
توپولوژیکی :
اگر A یک مجموعه با ترتیب جزیی ≤ باشد، بعضی مواقع لازم است تا ترتیب کاملی مثل ≺ برای مجموعه A پیدا کنیم . بطوریکه صرفا گسترشی از ترتیب جزیی داده شده باشد، به عبارت دیگر اگر a≤b . فرآیند تشکیل یک ترتیب کامل مثل ≺ را ترتیب توپولوژیکی گویند. ما با این مسیله وقتی که مواجه خواهیم شد که بخواهیم مجموعه متناهی با ترتیب جزیی A را وارد کاممپیوتر بکنیم .
بدیهی است که عناصر A باید بطور متوالی وارد شوند. بنابراین ممکن است لازم باشد که این عناصر بنحوی وارد شوند تا ترتیب جزیی آنها حفظ شود. بعبارت دیگر اگر a≤b آنگاه a باید از قبل از b وارد شود. ترتیب توپولوژیکی ≺ نحوه وارد کردن عناصر را بگونه یاد شده فراهم می آورد.
مورفیم:
فرض کنید (A ,≤) و (A ,≤) دو poset و یک تناظر یک به یک بین A,A باشد. تابع f را یک ایزومورینم از (A ,≤) به (A ,≤) خواهیم گفت هر گاه (A ,≤) اگر تنها اگر f(a) ≤ f (b) اگر f:A →A یک ایزومورفیم باشد در این صورت خواهیم گفت که (A ,≤) و (A ,≤) ایزومورف هستند. فرض کنید f:A →A یک ایزومورفیم از مجموعه با ترتیب جزیی (A ,≤) به مجموعه با ترتیب جزیی (A ,≤) باشد. فرض کنید B ́=f(B)⊆A ́,B⊆A در این صورت بنا به تعریف
اصل تناظر
اگر عناصر B دارای خاصیتی، نسبت به یکدیگر و یا نسبت به دیگر عناصر A باشند و اگر این خاصیت را بتوان بطور کامل بوسیله ≤ تعریف کرد، در ابن صورت عناصر B نیز می باید دارای همان خاصیت، تعریف شد.
برای یک poset متناهی، یکی از موضوعاتی که بطور کامل بوسیله ترتیب جزیی تعریف میشود نمودارهای آن میباشد . بنابراین از اصل تناظر نتیجه میشود که دو piset متناهی و ایزومورف دارای نمودارهای همان مباشند. بعبارت دقیقتر فرض کنید (A ́,≤ ́ ),(A,≤) دو poset متناهی و f:A →A تناظر یک به یک بین آندو باشد. فرض کنید H نمودارهاس (A ,≤) باشد .
در این صورت :
1-اگر f یک ایزومورفیم بوده و هر بر چسب a در H را به f(b) تبدیل کنیم، در این صورت H به نمودار هاس (A ́,≤ ́ ) تبدیل شود، در این صورت F یک ایزومورفیم است .
عناصر خارجی poset ها
بعضی از عناصر در یک poset دارای اهمیت ویژه ای در بسیاری از عملیات و کاربردهای مربوط به posetها می باشند . در این بخش ما ] این عناصر را مورد مطالعه قرار داده و در بخشهای بعدی رل مهم ایفا شده توسط آنها را مورد بحث قرار خواهیم داد. در این بخش فرض ما این است که (A ́,≤ ́ ) یک poset می باشد.
عنصر a∈A را یک عضو ماکزیمال A خواهیم گفت اگر برای هیچ عنصو C∈A رابطه a عضو a∈A را یک عضو می نیمال A هواهیم خواند اگر برای هیچ عنصو C∈A رابطه c
از تعاریف فوق نتیجه میشود که اگر (A ,≤) یک مجموعه با ترتیب جزیی و (A ,≥) دوگان آن باشد، آنگاه a∈A یک عضو ماگزمال (A ,≤) است اگر تنها اگر a یک عضو مینیمال (A ,≥)باشد . بطریق مشابه ، a یک عضو نیمال (A ,≤) است و تنها اگر a یک عضو ماگزیمال(A ,≥)باشد. a∈A، بزرگترین عضو a خوانده میشود هر گاه ⋎x∈A داشته باشیم x≤a . a∈A کوچکترین عضو A خوانده میشود هر گاه رابطه a∈x بازای تمامی a∈A برقرار باشد. به مشابه آنچه قبلا نیز گفته شد ، a بزرگترین (کوچکترین) عضو (A ,≤)است، اگر تنها کوچکترین (بزرگترین ) عضو (A ,≥)باشد. یک شبکه مجموعه ایست با ترتیب جزیی مثل (A ,≤) که در آن هر زیر مجموعه شامل دو عنصر مثل {a,b}دارای یکL∪B و یک GLBباشد ماL∪B({a,b} ) را باavb نمایش داده وآنرا Jom b,a خواهیم گفت . بطریق مشابه GLB({a,b} )را باavb نمایش داده و آنرا b,a meetخواهیم خواند. ساختارهای شبکه ای اکثرا در کاربردهای ریاضی و محاسباتی بچشم می خورند. اگر (L ,≤) ، (L_2 ,≤)دو شبکه باشند، در اینصورت (L ,≤) نیز یک شبکه است که در آن L=L_1x L_2ترتیب جزیی برابر ترتیب جزیی حاصلضرب است . اثبات meet , join در L_1را بترتیب با و را بترتیب با ∧_1 ∨_1 meet , join درL_2 به ترتیب با ∧_2 ∨_2 نمایش می دهیم . بنابه قضیه 1 از بخش 1 همکین فصل می دانیم که L یک مجموعه با ترتیب جزیی است . اکنون کافی است نشان دهیم که اگر (a_1 b_1 )و(a_2 b_2 )∈Lانگاه (a_1 b_1 )∨(a_2 b_2 ) و(a_1 b_1 )∧(a_2 b_2 ) در L موجود هستند این موضوع را به عنوان تمرین به خواننده واگذار می کنیم که تحقیق کنید که : (a_1 b_1 )∧(a_2 b_2 )=(a_1 ∨_1 a_2,l_1 ∨_2 b_2) (a_1 b_1 )∨(a_2 b_2 )=(a_1 ∧_1 a_2,l_1 ∧_2 b_2)
شبکهها (Lattice)
قبل از اینکه وارد دانشگاه شیم برای دانشگاه نظرهای زیادی داشتیم ولی حالا که وارد دانشگاه شدیم هیچ نظری نداریم!!!!!