وبلاگ یونیتی لرنینگ

مطالبی بدرد بخور برای درس ریاضی گسسته در مبحث روابط هم ارزی از ویکی پدیا در ادامه مطلب این پسترابطه هم‌ارزیاز ویکی‌پدیا، دانشنامهٔ آزاد
رابطه‌ها در ریاضیات به صورت زیرمجموعه‌هایی از ضرب دکارتی[۱] دو یا چند مجموعهٔ مشابه یا متمایز تعریف می‌شوند. این رابطه‌ها می‌توانند خواص و ویژگی‌های گوناگونی داشته باشند؛ اما ۴ ویژگی از سایر ویژگی‌ها مهم‌تر است. رابطه‌هایی که این خواص را دارند، به این شکل نامیده می‌شوند:بازتابی[۲]تقارنی[۳]پادتقارنیترایایی
رابطه‌ای که بازتابی، تقارنی و ترایایی باشد، رابطهٔ هم‌ارزی[۴] و رابطه‌ای که بازتابی، پادتقارنی و ترایایی باشد، رابطهٔ ترتیب[۵] خوانده می‌شود.
محتویات  [نهفتن] ۱ مثال‌هایی از رابطه‌های هم‌ارزی و ترتیب۲ دسته‌های هم‌ارزی۳ چند مثال از افراز به دسته‌های هم‌ارزی۴ مجموعه‌های مرتب۵ نمایش رابطهٔ ترتیب۶ کاربردها۷ پانویس۸ منابع
مثال‌هایی از رابطه‌های هم‌ارزی و ترتیب[ویرایش]رابطهٔ توازی خطوط در صفحه (||): مثالی از رابطهٔ هم‌ارزی
نشان می‌دهیم که رابطهٔ توازی خطوط در صفحه، یک رابطهٔ هم‌ارزی است:
نخست - هر خط با خودش موازی است؛ پس این رابطه بازتابی است.
دوم - اگر خطی با خط دیگری موازی باشد، آن خط نیز با این خط موازی است؛ پس این رابطه تقارنی است.
سوم - اگر خط d با خط 'd، و خط 'd با خط «d موازی باشند، آن‌گاه بنابر قضایای هندسهٔ اقلیدسی، خط d با خط»d موازی خواهد بود؛ پس این رابطه ترایایی نیز هست.
به این ترتیب مشخص شد که رابطهٔ توازی، یک رابطهٔ هم‌ارزی است.رابطهٔ بزرگ‌تر مساوی بودن (): مثالی از رابطهٔ ترتیب
نشان می‌دهیم که رابطهٔ  یک رابطهٔ ترتیب است:
نخست - هر عدد از خودش بزرگ‌تر یا با خودش مساوی است؛ پس این رابطه بازتابی است.
دوم - اگر  و  آن‌گاه نتیجه می‌شود که ؛ پس این رابطه پادتقارنی است.
سوم - اگر  و  آن‌گاه نتیجه می‌شود که ؛ پس این رابطه ترایایی است.
به این ترتیب مشخص شد که رابطهٔ  یک رابطهٔ ترتیب است.دسته‌های هم‌ارزی[ویرایش]هر رنگ یك دستهٔ هم‌ارزی این خطوط را مشخص میكند
وقتی یک رابطهٔ هم‌ارزی را روی مجموعه‌ای تعریف می‌کنیم، این رابطه مجموعه را به دسته(کلاس)های هم‌ارزی[۶] افراز می‌کند. به عنوان نمونه، همان مثال توازی خطوط را در نظر بگیرید. این رابطه، رابطه‌ای هم‌ارزی است و خطوط موجود در صفحه را به دسته‌های هم‌ارزی افراز می‌کند؛ به طوری که همهٔ خطوط موجود در هر دسته، با هم موازی‌اند.
یک مثال مفید دیگر برای درک بهتر دسته‌های هم‌ارزی، رابطهٔ هم‌باقی‌ماندگی اعداد طبیعی به پیمانه‌ای مشخص[۷] است. نشان دادن این‌که این رابطه هم‌ارزی‌ست، بسیار ساده‌است و لذا از اثبات آن می‌گذریم. به این ترتیب همان‌طور که گفته شد، این رابطه مجموعهٔ اعداد طبیعی را به دسته‌های هم‌ارزی افراز خواهد کرد. اعداد موجود در هریک از این دسته‌ها، به پیمانهٔ m باقی‌ماندهٔ یکسانی خواهند داشت.
معمولاً دسته‌های هم‌ارزی را به کمک یکی از اعضای آن مشخص می‌کنند؛ برای مثال [۲] نمایانگر دستهٔ هم‌ارزی‌ای است که عنصر ۲ در آن قرار دارد یا به عبارت دیگر تمام اعضای مجموعهٔ اصلی که با عنصر ۲ رابطه دارند در [۲] قرار می‌گیرند.چند مثال از افراز به دسته‌های هم‌ارزی[ویرایش]رابطهٔ هم‌رنگ بودن، پرچم را به سه دستهٔ هم‌ارزی سبز و سفید و قرمز افراز كرده‌استرابطهٔ هم‌استانی بودن: رابطه‌ای هم‌ارزی است و مجموعهٔ مردم یک کشور را به دسته‌های هم‌ارزی افراز می‌کند که هر دسته یک استان را مشخص خواهد کرد.رابطهٔ هم‌رنگ بودن: رابطه‌ای هم‌ارزی است و مجموعهٔ نقاط یک صفحه را به دسته‌های هم‌رنگ افراز خواهد کرد.رابطهٔ هم‌دما بودن: رابطه‌ای هم‌ارزی است و مجموعهٔ نقاط یک اتاق را به دسته‌های هم‌دما افراز خواهد کرد.رابطهٔ روز تولد یکسان داشتن: رابطه‌ای هم‌ارزی است و مجموعهٔ انسان‌ها را به ۳۶۵ (یا ۳۶۶) دستهٔ هم‌ارزی افراز خواهد کرد.رابطهٔ یکسانی تعداد یک‌ها در نمایش دودویی[۸] یک عدد: رابطه‌ای هم‌ارزی است و مجموعهٔ اعداد را به دسته‌های هم‌ارزی افراز می‌کند به طوری که در نمایش دودویی اعداد موجود در هر دسته، تعداد یکسانی یک وجود دارد.مجموعه‌های مرتب[ویرایش]
ابتدا لازم است مفهوم سنجش‌پذیر[۹] (مقایسه‌پذیر) را تعریف کنیم. دو عضو (مثل a و b) از یک مجموعه را سنجش‌پذیر با یک رابطهٔ ترتیب گوییم هرگاه (a،b) یا (b،a) عضو آن رابطه باشد. برای مثال اگر رابطهٔ موردنظر رابطهٔ بخش‌پذیری (شمردن/عادکردن) باشد، آن‌گاه دو عدد ۲ و ۴ سنجش‌پذیرند (زیرا ۴|۲ یا به عبارت دیگر (۲٬۴) عضو رابطه‌است) در حالی که دو عدد ۲ و ۳ سنجش‌پذیر نیستند (زیرا هیچ‌یک از (۳٬۲) یا (۲٬۳) عضو رابطه نیست). واضح است که اگر a و b متمایز باشند، به علت پادتقارنی بودن رابطه، امکان ندارد هردوی این زوج‌مرتب‌ها عضو رابطه باشند.
حال به تعریف مجموعه‌های مرتب می‌پردازیم. مجموعهٔ مرتب[۱۰] (یا تمام‌مرتب) در مورد یک رابطهٔ ترتیب تعریف می‌شود و به مفهوم آن است که هر دو عضو آن مجموعه، نسبت به آن رابطه، سنجش‌پذیرند. برای مثال رابطهٔ بزرگ‌تر یا مساوی بودن، روی مجموعهٔ اعداد طبیعی را در نظر می‌گیریم. با توجه به آن‌چه گفته شد، این رابطه ترتیب است و از طرفی در مورد هر دو عدد طبیعی a و b یا  یا . به این ترتیب مجموعهٔ اعداد طبیعی نسبت به این رابطه مرتب است. گاهی چنین مجموعه‌هایی را زنجیر[۱۱] نیز می‌خوانند.نمایش رابطهٔ ترتیب[ویرایش]گراف جهت‌دار مربوط به رابطهنمودار هس مربوط به رابطه
برای نمایش هریک از انواع رابطه‌ها راه‌های گوناگونی هست. به طور کلی یکی از بهترین شیوه‌های نمایش رابطه‌ها، استفاده از گراف جهت‌دار است.
با توجه به آن‌چه گفته شد، یکی از راه‌هایی که برای نمایش رابطهٔ ترتیب استفاده می‌شود به نمودار هس[۱۲] موسوم است. شیوهٔ ترسیم این نمودار به این صورت است که ابتدا گراف جهت‌دار نمایش رابطه را مشخص می‌کنیم. حال از آن‌جا که می‌دانیم رابطهٔ ترتیب بازتابی است، نیازی نیست که طوقه‌ها را نیز در نمودار باقی بگذاریم. پس آن‌ها را حذف می‌کنیم. از طرفی می‌دانیم که رابطهٔ ترتیب ترایایی نیز هست؛ بنابراین محتاج به رسم یال‌هایی که این رابطه را نشان می‌دهند نیز نیستیم. پس می‌شود آن‌ها را هم حذف کرد. آن‌چه که پس از این روال به دست می‌آید، نمودار هس خوانده می‌شود. برای مثال فرض کنید می‌خواهیم رابطهٔ بخش‌پذیری را روی مجموعه {۱٬۳،۴٬۶،۱۲} نمایش دهیم. این کار چنان که می‌بینید به کمک یک گراف جهت‌دار امکان‌پذیر است. حال اگر روال گفته‌شده را روی این گراف اعمال کنیم، نمودار هس به دست می‌آید.کاربردها[ویرایش]
مهم‌ترین کاربرد رابطه‌های ترتیب در مرتب‌سازی[۱۳] است. مرتب‌سازی لکزیکوگرافیک[۱۴] و توپولوژیک[۱۵]، یافتن عنصر بیشینه[۱۶] و کمینه[۱۷]، تعیین کران بالا[۱۸] وکران پایین[۱۹]، تعیین ترتیب اجرای مراحل مختلف یک برنامه، برنامه‌ریزی درسی و... که کمابیش مفهوم ترتیب را دارند، کاربردهای دیگر رابطه‌های ترتیب را آشکار می‌سازند.
رابطه‌های هم‌ارزی نیز برای دسته‌بندی اشیاء، اعداد و پدیده‌ها در زمانی که هویت تک‌تک آن‌ها به اندازهٔ رفتار مشترک‌شان با سایر اعضای مجموعه اهمیت ندارد، کاربرد خواهند یافت.
ادامه :
تعاریف مربوط به افراز مجموعه ها :افراز مجموعهاز ویکی‌پدیا، دانشنامهٔ آزاد
در نظریه مجموعه‌ها افراز یک مجموعه (به انگلیسی: Partition of a set)‏ یعنی تبدیل کردن آن به زیرمجموعه‌هایش به طوری که، اشتراک هر کدام از آن زیرمجموعه‌ها با یکدیگر مجموعه تهیباشد (مجموعه‌های مجزا) و اجتماع تمامی زیر مجموعه‌ها برابر با مجموعه افراز شده باشد.افراز بر روی دایره
محتویات  [نهفتن] ۱ مثال۲ تعداد افرازهای یک مجموعهٔ متناهی۳ پانویس۴ منبع
مثال[ویرایش]
مجموعه‌های  افراز مجموعهٔ  می‌باشند، اما برای  افراز درستی نیستند، زیرا ۳ و ۷ عضوی از زیرمجموعه‌های موجود در  نیستند. مجموعه‌های افرازی از هیچ مجموعه‌ای نمی‌باشند، چون {1,2} و {2,3} مجموعه‌هایی مجزا نیستند.
افرازهای {1, 2, 3} :
افراز مجموعهٔ تهی، تنها خود مجموعهٔ تهی است.

مطالبی از مجموعه توانی :مجموعه توانیاز ویکی‌پدیا، دانشنامهٔ آزاد
در ریاضیات، مجموعه توانی هر مجموعهٔ S، که بصورت ، P(S)، ℘(S)، 2S نوشته می‌شود، مجموعه‌ای از همهٔ زیرمجموعه‌های S است که شامل مجموعهٔ تهی و خود مجموعهٔ S نیز می‌شود. در نظریهٔ اصل موضوعی مجموعه‌ها (آنچنان که برای مثال در اصل موضوع ZFC توسعه پیدا کرده) وجود مجموعهٔ توانی هر مجموعه توسط اصل موضوع مجموعه توانی بدیهی شمرده شده است.
هر زیرمجموعه‌ای از  خانواده‌ای از مجموعه‌ها بر s نامیده می‌شود.مثال[ویرایش]
اگر S مجموعهٔ {x، y، z} باشد، آنگاه زیرمجموعه‌های S این‌ها هستند:{} (مجموعه تهی){x}{y}{z}{x، y}{x، z}{y، z}{x، y، z}
و بنابراین مجموعهٔ توانی  اینچنین است:منابع