From Wikipedia, the free encyclopedia
جبر مجموعهها خواص و قوانین مجموعه، تقاطع و متمم و روابط برابری و شمول مجموعهها را بیان میکند. همچنین روشی اصولی برای ارزیابی عبارات و انجام محاسبات شامل این عملیات و روابط فراهم میکند. هر مجموعهای تحت عملیات نظریه مجموعهها یک جبر بولی را تشکیل میدهد. (عملگر همان اجتماع، عملگر همان اشتراک و عملگر متمم بیانگر متمم مجموعه است)
جبر مجموعهها مجموعهای نظری مشابه جبر اعداد است. درست مانند جمع حسابی و ضرب که دارای خاصیت انجمنی (شرکت پذیری) و جا به جایی اند، اجتماع و اشتراک نیز این خواص را دارند. درست مانند رابطهٔ حسابی «کوچکتر مساوی» که خواص بازتابی، پاد متقارن و متعدی است، در نظریهٔ مجموعهها نیز عملگری به نام «زیرمجموعه بودن» دارای این خواص است.
جبر مجموعهها، جبری از عملیات اجتماع، اشتراک و متمم، و روابط برابری و شمول نظریهٔ مجموعهها است. برای یک آشنایی ساده با مجموعهها، به مقالات مجموعه (ریاضی) نگاه کنید، برای یک آشنایی بیشتر و عمیقتر، نظریه طبیعی مجموعهها را ببینید، و برای بررسی دقیق و کامل نظریهٔ مجموعهها، نظریه مجموعهها را ببینید.
عملیات باینری اجتماع(∪) و اشتراک(∩) خواصی را به وجود آوردهاند که برخی از این خواص یا «قوانین» دارای نامهای به خصوص و مشهوری هستند:
قانون پخشی:
شباهت بین اجتماع و اشتراک مجموعهها، و جمع و ضرب اعداد، کاملاً قابل توجه است. مانند جمع و ضرب، عملیات اجتماع و اشتراک دارای خواص جابجایی و شرکتپذیری هستند، و اشتراک بر روی اجتماع پخش پذیر است. البته بر خلاف جمع و ضرب، اجتماع نیز بر روی اشتراک پخش پذیر است.
دو قانون دیگر شامل مجموعههای خاصی با نام مجموعهٔ تهی (∅) و مجموعه جهانی (U) میشود؛ که متمم یکدیگرند. مجموعهٔ تهی هیچ عضوی ندارد، و مجموعهٔ جهانی است شامل همهٔ اعضای امکانپذیر است (در یک زمینه خاص).
قوانین هویت (همراه با قوانین جابجایی) میگویند که، درست مثل ۰ و ۱ برای جمع و ضرب، ∅ و U عناصر هویت برای اجتماع و اشتراکاند.
بر خلاف جمع و ضرب، اجتماع و اشتراک عناصر معکوس ندارند. با این حال قوانین مکمل، باعث به وجود آمدن خاصیتی بنیادی از عمل یگانی متمم که تا حدودی شبیه معکوس است، میشود.
پنج قانون یادشده - جابجایی، شرکت پذیری، پخش پذیری، هویت و متمم – تمام جبر مجموعهها را در بر میگیرد، به این معنا که هر گزاره معتبر در جبر مجموعهها میتواند از آنها استنتاج شود.
توجه داشته باشید که اگر قوانین مکمل به قانون تقلیل داده شود، این دقیقاً همان جبر منطق خطی است.
هر جفت از خواص مطرح شده در بالا را میتوان با جایگزینی ∪ به جای ∩ و برعکس و همچنین ∅ به جای U و برعکس، به یکدیگر تبدیل نمود.
اینها مثالهایی از یکی از ویژگیهای بسیار مهم و قدرتمند جبر مجموعهها یعنی، اصل دوگانگی است، که ادعا میکند که برای هر عبارت درست در مورد مجموعهها، عبارت دوگان توسط تبادل اجتماعها و اشتراکها و همچنین تبادل U و ∅ به دست میآید که این عبارت نیز درست است. اگر دوگان یک عبارت با خود عبارت برابر باشد، عبارت را خود-دوگان میگوییم.
گزاره زیر، شش قانون مهم دیگر از جبر مجموعهها -شامل اجتماعها و اشتراک ها- را بیان میکند. گزاره ۳: هر زیر مجموعهای از مجموعهٔ جهانی U، مانند A و B، خواص زیر را دارا میباشند:
همانطور که در بالا اشاره شد، هر یک از قوانین مندرج در گزاره ۳ را میتوان از پنج قانون بنیادی استنتاج کرد. به عنوان مثال، یک اثبات برای قانون همانی اجتماع در زیر بیان شدهاست.
اثبات:
طبق قانون هویت اشتراک | ||
طبق قانون متمم اجتماع | ||
طبق قانون پخشپذیری اجتماع بر روی اشتراک | ||
طبق قانون متمم اشتراک | ||
طبق قانون هویت اجتماع |
اثبات زیر نشان میدهد که دوگان اثبات فوق، اثبات «دوگان قانون همانی برای اجتماع»، یعنی «قانون همانی برای اشتراک» است.
اثبات:
طبق قانون هویت اجتماع | ||
طبق قانون متمم اشتراک | ||
طبق قانون پخشپذیری اشتراک بر روی اجتماع | ||
طبق قانون متمم اجتماع | ||
طبق قانون هویت اشتراک |
اشتراک دو مجموعه را میتوان با عملگر «تفاضل دو مجموعه» بیان کرد:
گزارهٔ زیر چند قانون مهمتر در باب متممها را بیان میکند:
گزارهٔ ۴: فرض کنید A و B، زیرمجموعههایی از مجموعهٔ جهانی U باشند:
توجه کنید که مکمل دوتایی، خود-دوگان است.
گزارهٔ بعدی، که آن هم خود-دوگان است، بیان میکند که متمم یک مجموعه تنها مجموعهای است که قوانین متمم برایش صادق است. به عبارت دیگر، متمم توسط قوانین متمم مشخص میشود.
گزارهٔ ۵: فرض کنید A و B، زیرمجموعههایی از مجموعهٔ جهانی U باشند:
گزارهٔ زیر بیان میکند که شمول دارای خاصیت ترتیب است:
گزارهٔ 6: B , A و C سه مجموعه هستند:
گزاره زیر میگوید که برای هر مجموعه S، مجموعه توانی S، یک توری محدود است، و از این رو همراه با قوانین توزیع و متمم فوق، نشان داده میشود که یک جبر بولی است.
گزارهٔ ۷: اگر B , A و C سه زیرمجموعه از S باشند:
گزارهٔ زیر بیان میکند که عبارت معادل عبارتهای دیگر از جمله اشتراک، اجتماع و مکمل است.
گزارهٔ ۸: برای هر دو مجموعهٔ A و B عبارتهای زیر همگی معادل اند:
گزاره فوق نشان میدهد که رابطهٔ شمول میتواند با عملگرهای اجتماع یا اشتراک مشخص شود. این به این معناست که نظریهٔ شمول به وضوح غیرضروری است.
گزارهٔ زیر شامل چند خاصیت پیرامون اصل متمم است.
گزارهٔ ۹: برای هر مجموعهٔ جهانی U و زیرمجموعههای B , A و C از این مجموعه داریم:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.