منو
 صفحه های تصادفی
توصیه امام علی علیه السلام به رعایت تقوای الهی هنگام شهادت
تاریخچه اصول شمارش
علت حمایت اوزون حسن از سلطان جنید
ابومحمد قاضی عبیدالله
امام حسین در قرآن - نساء : 77
درس هندسه ترسیمی
دلیل قیام نکردن امامان معصوم
مشکلات مراحل نوجوانی
کاردرمانی
ادراک و خطای ادراک
 کاربر Online
659 کاربر online

آشنایی مقدماتی با نظریه مجموعه ها

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)



این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


آشنایی با نظریه مجموعه ها

در این بخش با بحثی به نام نظریه مجموعه ها آشنا می شوید. در اینجا سعی شده است با ارائه قضایا و مسایل جالب در نظریه مجموعه ها، تکنیک هایی برای حل این نوع مسایل به دست آورید. ابتدا با چند تعریف ساده مبحث را شروع می کنیم.

تعریف

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

تعریف

را یک خانواده از زیرمجموعه های مجموعه می نامیم.

تعریف

تعداد اعضای یک مجموعه مانند را با ( کاردینال ) نمایش می دهیم.

مسأله 1

خانواده ای از زیرمجموعه های مجموعه مانند را خوب می نامیم با این شرط که اگر باشند آنگاه . نشان دهید .
اثبات
اعضای را به زوج های افراز می کنیم ( مکمل است) و چون است پس تعداد این زوج ها برابر است. طبق اصل لانه کبوتری اگر باشد آنگاه دو عضو از یک زوج انتخاب می شود و چون اشتراک هر دو عضو از این زوج ها تهی است. پس خانواده ای خوب نیست که با فرض اولیه تناقض دارد. بنابراین نتیجه می شود که ، و برای حالت تساوی می توان یک عضو از ، مانند را در نظر گرفت و تمام زیرمجموعه های را که شامل هستند ایجاب کرد که تعداد این زیرمجموعه ها است.

مسأله 2

در مسأله بالا نشان دهید اگر باشد، می توان یک عضو ازرا که در نیامده است به اضافه کرد و همچنان خوب باقی بماند.
اثبات
چون است طبق اثبات مسأله قبل نتیجه می شود که وجود دارند که یا حال از برهان خلف استفاده می کنیم. فرض کنید و هر دو خوب نباشند درنتیجه وجود دارند که و

که خلاف فرض است. درنتیجه می توان به آنقدر عضو اضافه کرد که شود و خوب باقی بماند.
در زیر با ارائه یک تعریف و حل مسألهای با آن، ایده بسیار خوبی از نظریه مجموعه ها به دست خواهید آورد.



تعریف

ماتریس یک خانواده را به صورت زیر تعریف می کنیم:
فرض کنید ، و که باشد. یک ماتریس را در نظر می گیریم که درایه سطر ام و ستون ام آن 1 است اگر و تنها اگر باشد و در غیر این صورت صفر می باشد.

مسأله 3

یک خانواده عضوی از زیرمجموعه های عضویاست و به ازای هر متعلق به ، است. نشان دهید

اثبات
فرض کنید ، و باشد. ماتریس این خانواده را در نظر می گیریم. در این ماتریس تعداد جفت درایه های واقع در سطر ام را که شامل 1 هستند می گیریم. در واقع تعداد هایی است که . همچنین را مجموع همه ها در نظر می گیریم.
در ضمن می دانیم برابر است با تعداد یک های هم سطری که یک در ستون ام و دیگری در ستون ام قرار دارد. هر دو ستون از این ماتریس را که در نظر بگیریم حداکثر تا از این جفت درایه های شامل یک دارند. زیرا است، پس
(1)



و اگر تعداد یک های واقع در سطر ام را بگیریم تعداد جفت درایه های شامل یک، در سطر ام برابر خواهد بود و نتیجه می شود که

(2)

و چون است پس تعداد یک های کل جدول برابر است یعنی

طبق نامساوی کوشی شوارتز خواهیم داشت

از (1) و (2) نیز نتیجه می شود:




در حل مسأله فوق از روشی به نام دوگانه شمردن استفاده شده است. در این روش همان طور که در حل مسأله دیدید تعداد یک سری اعضای خاص یک بار در ستون ها شمرده می شود و یک بار در سطرها و چون تعداد این اعضای خاص در هر دو حالت برابر با تعداد اعضای خاص کل جدول می باشد، درنتیجه یک تساوی یا نامساوی بین مفروضات مسأله به دست می آید.

مسأله 4

فرض کنید یک خانواده از مجموعه عضوی باشد و به ازا هر ، باشد نشان دهید که تابع وجود دارد که به ازای هر ، .
اثبات


فرض کنید . حال حکم را با استقرا روی اثبات می کنیم. حکم برای بدیهی است زیرا تابع با شرط و در شرط مسأله صدق می کند. فرض کنید حکم برای برقرار باشد، حکم را برای اثبات می کنیم. را به دو زیرمجموعه و افراز می کنیم به طوری که:


همچنین را به صورت زیر تعریف می کنیم:

طبق فرض مسأله هر عضو به متعلق است پس است. با توجه به فرض استقرا، توابع و وجود دارند که در شرط مسأله صدق می کنند. حال را به صورت زیر تعریف می کنیم:
اگر

اگر

اگر


و

به سادگی دیده می شود که تابع جواب مسأله است.



مسأله 5

فرض کنید مجموعه ای دلخواه با حداقل 12 عضو و زیرمجموعه هایی 12 عضوی از باشند (ها لزوماً متمایز نیستند) ثابت کنید دو زیرمجموعه و وجود دارند به طوری که و و به ازای هر ،

اثبات
برهان خلف اگر چنین زیرمجموعه هایی وجود نداشته باشند، آنگاه برای هر افراز به دو مجموعه و ، و وجود دارند به طوری که. بدون کاسته شدن از کلیت مسأله می توان فرض کرد که مجموعه ای متناهی است زیرا قرار می دهیم و به جای با کار می کنیم. فرض کنید ، در این صورت تعداد افرازهای به دو مجموعه و برابر است با . حال تعداد حالاتی را می شماریم که به دو مجموعه و افراز شده است به طوری که به ازای یک اندیس معلوم یا .
اگر ، آنگاه برای ، حالت موجود است و با مشخص شدن ، نیز مشخص می شود. به همین ترتیب اگر آنگاه برای ، حالت موجود است و با مشخص شدن ، معلوم خواهد شد.
بنابراین تعداد حالات بالا حداکثر برابر با است، ولی

پس لااقل یک حالت باقی می ماند که در شرایط مسأله صدق می کند.



قضیه اسپرنر

خانواده شامل زیرمجموعه هایی غیرتهی از مفروض است. به طوری که برای هر و داریم img/daneshnameh_up/2/21/com0032a.jpg ، آنگاه

اثبات
ابتدا نشان می دهیم تعداد خانواده های با شرط
img/daneshnameh_up/8/8c/com0032b.jpg

برابر با است.
با توجه به اینکه ، نتیجه می شود و ، 1 حالت دارد و ، حالت داریم، ، حالت دارد و ... و ، 1 حالت دارد پس تعداد این خانواده ها برابر است. حال نشان می دهیم اگر ثابت باشد تعداد این خانواده ها برابر با است، زیرا:
حالت

حالت

حالت

img/daneshnameh_up/2/2f/com0032c.jpg

و تعداد خانواده های برابر باو تعداد خانواده های برابر با است، پس تعداد این خانواده ها برابر است. حال به اثبات قضیه می پردازیم. اگر در این صورت تعداد خانواده های که شامل است برابرنیز از هر کدام از این خانواده ها حداکثر یک عضو دارد. پس

زیرا تعداد خانواده هایی که img/daneshnameh_up/9/9b/com0032d,e.jpg و در آن ثابت باشد از تعداد خانواده هایی که شرطی به جز img/daneshnameh_up/9/9b/com0032d,e.jpg ندارند بیشتر نیست. پس با فرض داریم:



با توجه به اینکه

(1)

(2)

از (1) و (2)


و اگر تساوی برقرار باشد در این صورت هر عضو یا عضوی است و از هر خانواده دقیقاً یک عضو دارد.

قضیه (Edros-ko-rado)

اگر خانواده ای از زیرمجموعه های عضوی مجموعه باشد به طوری که برای هر ، ، در این صورت .
اثبات
فرض کنید

اعضای مجموعه را به پیمانه در نظر بگیرید، همچنین فرض کنید ، در این صورت زیرا در غیر این صورت دو عضو از مثلاً و یافت می شوند به طوری که


.

برای هر جایگشت از مجموعه های و را به شکل زیر تعریف می کنیم:


با استدلال مشابه حالت قبل می توان نشان داد ، پس و چون داریم:
(چرا؟) درنتیجه خواهیم داشت:



تعریف

فرض کنید خانواده ای از زیرمجموعه های مجموعه باشد، منظور از برای این خانواده یعنی عضو دو به دو متمایز از ، به طوری که .

قضیه فیلپ هال

خانواده ، دارد اگر و تنها اگر اجتماع هر عضو این خانواده حداقل عضو داشته باشد.
(اثبات قضیه فوق را در این مقاله نمی آوریم.)

تعریف

ماتریس مربعی را جایگشتی گوییم، هرگاه در هر سطر و هر ستون فقط یک درایه 1 و بقیه درایه ها صفر باشند.



قضیه

فرض کنید ماتریسی با درایه های متعلق به اعداد صحیح نامنفی باشد، اگر مجموع درایه های هر سطر و هر ستون برابر باشد در این صورت را می توان به صورت مجموع ماتریس جایگشتی نوشت.
اثبات
تعریف کنید ، سطر را در نظر بگیرید. مجموع درایه های آنها است، پس حداقل در ستون درایه های ناصفر وجود دارند، زیرا مجموع درایه های هر ستون نیز است. بنابراین در شرط قضیه فیلیپ هال صدق می کند، پس تا درایه وجود دارد که هیچ دوتایی در یک سطر یا یک ستون نبوده و هر کدام از صفر بیشتر هستند، بنابراین می توان از این درایه ها یک واحد کم کرد و یک ماتریس جایگشتی تولید کرد و با استقراء روی این ماتریس جدید حکم اثبات می شود. (جزئیات اثبات به عهده خواننده گذاشته می شود).

قضیه konig

فرض کنید ماتریسی باشد که درایه های آن 0 یا 1 هستند، در این صورت اگر کمترین تعداد سطرها یا ستون هایی که همه 1ها را شامل شوند بنامیم و بیشترین تعداد 1هایی که هیچ دوتایی هم سطر و یا هم ستون نیستند را بنامیم آنگاه .
اثبات
واضح است که . فرض کنید و سطر و ستون شامل همه 1ها باشد. بدون ازدست دادن کلیت فرض کنید این سطرها و ستون ها، سطر و ستون اول ماتریس باشند. به ازای تعریف کنید: .
خانواده در شرط هال صدق می کند زیرا اگر سطر باشند که حداکثر با ستون اشتراک داشته باشند می توان به جای سطر، ستون را انتخاب کرد که با مینیمم بودن در تناقض است. پس خانواده فوق دارد، یعنی در بلوک سمت راست بالا، تا 1 دو به دو غیر هم خط وجود دارد به طور مشابه در بلوک سمت چپ پایین، تا 1 دو به دو غیر هم خط وجود دارد، پس حداقل تا 1 دو به دو غیر هم خط وجود دارد، بنابراین ، لذا.

قضیه

فرض کنید

با این شرط که
img/daneshnameh_up/c/c8/com0032f.jpg

آنگاه ، و اگر در شرط (2)، به جای ، را قرار دهیم داریم:


مسأله 6

مفروض است. اگر و به ازای هر ، و در این صورت نشان دهید .
اثبات


مجموعه و را به صورت زیر تعریف می کنیم:


در این صورت اگر آنگاه و اگر ، آنگاه و نیز اگر
img/daneshnameh_up/3/38/com0032g.jpg


طبق قضیه گفته شده داریم:

و چون اشتراک هر دو عضوی از ناتهی و اجتماع هر دو عضوی از ، مخالف است داریم:


و با توجه به اینکه خواهیم داشت:



پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0057.pdf

همچنین ببینید



تعداد بازدید ها: 19856


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..