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

[nafise sadeghi]

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

بررسی اصل شمول و عدم شمول(اصل شمول وطرد) ما را یاری خواهد کرد تا فرمولی برای تعداد توابع پوشای http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/4caa0b2c921aeb7491da50461a8e0032.png، به ازای مجموعه‌های ناتهی متناهی A,B،بدست آوریم . دیگر کاربردهای این اصل ، ماهیت عام آن در ریاضیات ترکیباتی، به عنوان روشی غیر مستقیم برای حل مسایل شمارشی ، که در بسیاری از موقعیت های گوناگون پیش می آیند، آشکار می سازند.
ابتدا نمادهایی را برای بیان این اصل شمارشی جدید معرفی می‌کنیم . سپس با استدلالی ترکیباتی ، این اصل را بیان می‌کنیم.لذا با چند مثال این کار را شروع می‌کنیم.
فرض کنید http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/42a5f0032d97163c15c63cbd2d7007d4.pngمجموعه (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%D9%85%D8%AC%D9%85%D9%88%D8%B9%D9%8 7) ای باشد ، که http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/330c243b1df60988274d3470ff6ae557.png و همچنین فرض کنید http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/236a52f483c4acf2bf11a41246fffdb3.png مجموعه ای از ویژگی هایی باشند که برخی از عناصر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/42a5f0032d97163c15c63cbd2d7007d4.png، ویا همه آنها در این شرایط صدق کنند.بعضی از عناصر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/42a5f0032d97163c15c63cbd2d7007d4.png ممکن است در بیش از یک شرط صدق کنند.درحالیکه بعضی دیگرممکن است در هیچ یک از این شروط صدق نکنند.
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/34b26abf7987785edc9b8787e2414e31.png تعداد عناصری را نشان می‌دهد که در شرط http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/5731e99ef155a217aa09109bded9cf1c.png صدق می‌کنند.( می‌دانیم که http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/0135c8dc7292164fd03ce9ddb0e014df.png).لازم به ذکر است که در اینجا ، هم عناصری را می شماریم که فقط در شرط http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/5731e99ef155a217aa09109bded9cf1c.png صدق می‌کنند وهم عناصری که علاوه بر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/5731e99ef155a217aa09109bded9cf1c.png در شرط دیگری مانند http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/db74cb70dc48618aa92ff3a8ef1ef207.png صدق می‌کنند.
همچنین به ازای هر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/36bef87b3344a064112a399a71746f76.png ، با شرط http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/04f3a49883de0f92b870eed40ffd5f07.png ، http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/2d02b009e14d20483f1c1938380b887b.png تعداد عناصری از http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/42a5f0032d97163c15c63cbd2d7007d4.png را نشان می‌دهد که همزمان در هر دو شرط http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/bdafa0a9a4e35d37362b855e670ccdfa.png و شاید هم در دیگر شرایط صدق کنند.در اینجا نیز لازم به ذکر است که http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/2d02b009e14d20483f1c1938380b887b.png تعداد عناصری از http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/42a5f0032d97163c15c63cbd2d7007d4.png که فقط در http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/bdafa0a9a4e35d37362b855e670ccdfa.png ، صدق می‌کنند ، نیست.

[nafise sadeghi]

به همین ترتیب ، اگر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/a9d6ee08b5b54cdec5326d8cf27ecabf.png سه عدد صحیح (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%D8%B9%D8%AF%D8%AF+%D8%B5%D8%AD%DB% 8C%D8%AD) متمایز باشند ، http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/ee96a599eb8941c43ce93a9393c8866d.png تعداد عنصرهایی از s را نشان می‌دهد که در هر سه شرط http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/c4f2fd56aa37b87d3ebf7a6db2ad7b9e.png والبته شاید در شروط دیگر صدق می‌کنند.
به ازای هر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/0135c8dc7292164fd03ce9ddb0e014df.png، عبارت http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/f66460d36c2796b1d8ac086d8f09600a.png تعداد عناصری از s را نشان می‌دهد که در شرط http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/5731e99ef155a217aa09109bded9cf1c.png صدق نمی‌کنند.به همین ترتیب اگر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/36bef87b3344a064112a399a71746f76.png باشد ، http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/1893b52e61883df3bfb06d844ac713f6.png برابر است با تعداد عنصرهایی از http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/42a5f0032d97163c15c63cbd2d7007d4.png که در هیچ یک از شرایط http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/bdafa0a9a4e35d37362b855e670ccdfa.png صدق نمی‌کنند.باید دقت شود که این عدد با http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/41bd44015807cd08a201947b14380c98.png یکی نیست.
با توجه به نمودار ون (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%D9%86%D9%85%D9%88%D8%AF%D8%A7%D8%B 1+%D9%88%D9%86) که در شکل زیر می‌بینید که اگر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/34b26abf7987785edc9b8787e2414e31.pngتعداد عنصرها در دایره سمت چپ و http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/bd048d110f0bea7073b8c9eceabda202.png تعداد عناصر در دایره سمت راست باشند ، http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/2d02b009e14d20483f1c1938380b887b.png تعداد عنصرها در ناحیه مشترک است. در حالیکه http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/74b0f275cfb335399e02ac5461053fb3.png تعداد عناصر خارج از اجتماع این دو دایره (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%D8%AF%D8%A7%DB%8C%D8%B1%D9%87) است.


http://daneshnameh.roshd.ir/mavara/img/daneshnameh_up/3/30/van001.JPG

درنتیجه ، بنا به شکل فوق ، http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/0d9fc0f09553f8531b8950eb8d79c193.png، که در آن جمله اخیر را به این جهت اصافه کرده‌ایم که در جمله http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/744bbd847b8ae6e67586ab14af5c25ae.png دوبار حذف شده است و اصلا شمرده نشده بود.
به همین ترتیب ، بنا به شکل زیر خواهیم داشت:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh_up/9/93/van002.JPG



http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/af6cfec643612eeb7b4faa4a59d21132.png

[nafise sadeghi]

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

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

مجموعه ای مانند s با شرط http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/7a2093190744e04255e2a0b90d1f788d.png، وشروط http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/aaeb52c6abb20b82cb323bf490a1b94a.png که http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/20fca1ce1a5bc64bb38ba7d90f11d05e.png را که برخی از عناصر s در آنها صدق می‌کنند ، در نظر می‌گیریم. تعداد عناصری از s که در هیچ یک از شرایط http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/aaeb52c6abb20b82cb323bf490a1b94a.png ،صدق نمی‌کنند، با http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/2f2274dc9dae99c7782247107ce2c251.png نمایش داده می‌شود و داریم:



http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/603279bd8861f331af051332ce2e6c47.png

اثبات:
برای اثبات این مهم نشان می‌دهیم به ازای هر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/88fb7c1eae188ebfa56fe38979e47c89.png که http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/de6c653c9c8c35d84f7178bcd15210bc.png در شمارش هر دو طرف معادله فوق ،سهمی یکسان(صفر یا یک) دارد.
اگر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/de6c653c9c8c35d84f7178bcd15210bc.png در هیچ یک از شرایط ، صدق نکند،در این صورت http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/de6c653c9c8c35d84f7178bcd15210bc.png یکبار در http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/34b321595d708fcc2cf04b448071b250.png شمرده می‌شود و یکبار در http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/1cd585f681165f5f7a8e2d7c9e8cf30b.png.ولی در هیچ جمله دیگری از معادله مذکور ، شمرده نمی‌شود. در نتیجه سهم شمارش http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/de6c653c9c8c35d84f7178bcd15210bc.png در دوطرف معادله ، یک است.اما امکان دارد http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/de6c653c9c8c35d84f7178bcd15210bc.png دقیقا درhttp://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/1167e4d24d34c39386f7d089a88eb2af.png شرط که http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/cbe73de27b8242e485ebc7833a3b6230.png ، صدق کند.در این حالتhttp://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/de6c653c9c8c35d84f7178bcd15210bc.png، هیچ سهمی در شمارش http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/34b321595d708fcc2cf04b448071b250.png ندارد.اما سهم http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/de6c653c9c8c35d84f7178bcd15210bc.png در شمارش سمت راست معادله به صورت زیر خواهد بود:

[nafise sadeghi]

)یکبار در http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/1cd585f681165f5f7a8e2d7c9e8cf30b.png

2)http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/1167e4d24d34c39386f7d089a88eb2af.png بار ، در http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/57c683b600602f8200ee656140e3f068.png.(یکبار برای هر یک از http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/1167e4d24d34c39386f7d089a88eb2af.png شرط)

3)http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/401d5552a6c0d78ed9b9b78e2e8c42cb.png بار در http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/6358ba14301bb47f9f9c518addbd3219.png.(یکبار برای هر دو شرط از این http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/1167e4d24d34c39386f7d089a88eb2af.png شرط.)

4)http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/3eecaa7d527369f773db75614f046d79.pngبار در http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/8a7a0b8a4b89530c5d124f3c298db016.png.(یکبار برای هر سه شرط از این http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/1167e4d24d34c39386f7d089a88eb2af.png شرط.)
.
.
.
r+1)http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/6ad7305b879d0348479ff080d3e97628.png بار در http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/b7172ab95492282bc30cdc2b2af0c376.png، که در آن مجموع روی همه انتخاب‌های http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/1167e4d24d34c39386f7d089a88eb2af.png تایی از http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/0ce224de805126f572515674bd682521.png شرط، محاسبه می‌شود.
در نتیجه تعداد دفعاتی که http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/de6c653c9c8c35d84f7178bcd15210bc.png در هر دو طرف معادله صورت قضیه ، شمرده می‌شود، بنا بر قضیه دو جمله ای ، برابر است با:


http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/399032c76e0c4c91aa47f25978a26879.png

بنابراین در هر دو طرف معادله ، تعداد مساوی از عناصر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/42a5f0032d97163c15c63cbd2d7007d4.png شمرده می‌شود و تساوی برقرار است.

نتیجه

با مفروضات قضیه فوق ، تعداد عناصری از http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/42a5f0032d97163c15c63cbd2d7007d4.png که حداقل در یکی از شروط http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/5731e99ef155a217aa09109bded9cf1c.png صدق کنند ، برابر است با http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/ce004c8ce18dcd47c875463e38878b47.png که در اینجا "," به معنی "یا" می باشد