اصل شمول و عدم شمول

[nafise sadeghi]

اصل شمول و عدم شمول

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

[nafise sadeghi]

به همین ترتیب ، اگر سه عدد صحیح متمایز باشند ، تعداد عنصرهایی از s را نشان می‌دهد که در هر سه شرط والبته شاید در شروط دیگر صدق می‌کنند.
به ازای هر ، عبارت تعداد عناصری از s را نشان می‌دهد که در شرط صدق نمی‌کنند.به همین ترتیب اگر باشد ، برابر است با تعداد عنصرهایی از که در هیچ یک از شرایط صدق نمی‌کنند.باید دقت شود که این عدد با یکی نیست.
با توجه به نمودار ون که در شکل زیر می‌بینید که اگر تعداد عنصرها در دایره سمت چپ و تعداد عناصر در دایره سمت راست باشند ، تعداد عنصرها در ناحیه مشترک است. در حالیکه تعداد عناصر خارج از اجتماع این دو دایره است.

درنتیجه ، بنا به شکل فوق ، ، که در آن جمله اخیر را به این جهت اصافه کرده‌ایم که در جمله دوبار حذف شده است و اصلا شمرده نشده بود.
به همین ترتیب ، بنا به شکل زیر خواهیم داشت:

[nafise sadeghi]

حال قضیه زیر را که تعمیم عبارات فوق است ،چنین بیان می‌کنیم:

قضیه اصل شمول وطرد

مجموعه ای مانند s با شرط ، وشروط که را که برخی از عناصر s در آنها صدق می‌کنند ، در نظر می‌گیریم. تعداد عناصری از s که در هیچ یک از شرایط ،صدق نمی‌کنند، با نمایش داده می‌شود و داریم:

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

[nafise sadeghi]

)یکبار در

2) بار ، در .(یکبار برای هر یک از شرط)

3) بار در .(یکبار برای هر دو شرط از این شرط.)

4)بار در .(یکبار برای هر سه شرط از این شرط.)
.
.
.
r+1) بار در ، که در آن مجموع روی همه انتخاب‌های تایی از شرط، محاسبه می‌شود.
در نتیجه تعداد دفعاتی که در هر دو طرف معادله صورت قضیه ، شمرده می‌شود، بنا بر قضیه دو جمله ای ، برابر است با:

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

نتیجه

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