مجموعه ها (Sets)

مجموعه ها (Sets)

اسلاید 1: فصل دوم: ساختارهای ابتدایی: مجموعه، تابع، دنباله و تجمیع بخش 1.2 مجموعه ها (Sets)درس ساختمان های گسسته

اسلاید 2: 2یک مجموعه (Set) چیست؟یک مجموعه یک مجموعه نا مرتب از اشیا است. اسامی افراد کلاس: {علی، احمد، زهرا، ...}استان های ایران: {تهران، مازندران، گیلان، ...}مجموعه می تواند شامل اجزای کاملا نا مرتبط نیز باشد: {تهران، 3، قرمز،ب}خصوصیات مجموعهترتیب مهم نیست{1, 2, 3, 4, 5} برابر است با {3, 5, 2, 4, 1}مجموعه عضو تکراری نمی تواند داشته باشد

اسلاید 3: 3مشخص نمودن مجموعهاز حروف بزرگ (A, S…) برای نام گذاری مجموعهاز حروف کوچک ایتالیک (a, x, y…)برای اعضای مجموعهراه ساده نمایش: لیست نمودن همه اعضای مجموعهA = {1, 2, 3, 4, 5} ، همیشه امکان پذیر نیستممکن است از (...) نیز استفاده شود: B = {3, 5, 7, …}ممکن است ابهام ایجاد کندIf the set is all odd integers greater than 2, it is 9If the set is all prime numbers greater than 2, it is 11معرفي يك مجموعه با بيان خصوصيت مشترك آنهاست (set builder notation )D = {x | x is prime and x > 2}E = {x | x is odd and x > 2}

اسلاید 4: 4مشخص نمودن مجموعهیک مجموعه شامل (contains) تعدادی اعضای (members) یا المان های (elements) متفاوت است که آن مجموعه را می سازندaA : a عنصري از مجموعه A است 4  {1, 2, 3, 4}aA : a عنصري از مجموعه A نيست. 7  {1, 2, 3, 4}

اسلاید 5: مثال مجموعه های پرکاربردمجموعه حروف صدا دار: V = {a, e, I, o, u} مجموعه اعداد فرد زير 10:O = {1,3,5,7,9} مجموعه: T ={ a,2,Fred,New Jersey}اعداد طبيعي : N = { 0, 1, 2, 3,…} اعدادصحيح : Z = {…,-2,-1,0,1,2,…}اعداد صحيح مثبت: Z+ = {1,2,3,…} اعداد گويا: Q={ p/q | p∈Z, q∈Z, q≠0}اعداد حقيقي R

اسلاید 6: 6نمودار ون (Venn diagrams)نمایش گرافیکی مجموعه هامستطیل بیرونی مجموعه عالم را نشان می دهددایره یک مجموعه را نمایش می دهدS مجموعه حروف صدا دار در زبان انگلیسی را نشان می دهدمعمولا اعضای مجموعه در نمودار نوشته نمی شودaeioubcdfghjklmnpqrstvwxyzUS

اسلاید 7: 7مجموعه ای از مجموعه هاS = { {1}, {2}, {3} }T = { {1}, {{2}}, {{{3}}} }V = { {{1}, {{2}}}, {{{3}}}, { {1}, {{2}}, {{{3}}} } }تعداد اعضای مجموعه V سه تا است1 ≠ {1} ≠ {{1}} ≠ {{{1}}}

اسلاید 8: 8مجموعه تهیاگر تعداد اعضای یک مجموعه صفر باشد به آن مجموعه مجموعه تهی (empty یا null) می گوییمعلامت:    = { }تهی خود می تواند عضو یک مجموعه باشد{ , 1, 2, 3, x } ≠ {  }{ } ≠ {{ }}{} = {{ }}

اسلاید 9: 9تساوی مجموعه ها (Set Equality) و زیر مجموعه (Subsets)اگر دو مجموعه اعضای کاملا یکسان داشته باشند با هم مساوی هستند{1, 2, 3, 4, 5} = {5, 4, 3, 2, 1}{1, 2, 3, 2, 4, 3, 2, 1} = {4, 3, 2, 1}{1, 2, 3, 4, 5} ≠ {1, 2, 3, 4}مجموعه S زير مجموعه T است، اگر و فقط اگر هر عضوي از S عضوي از T نيز باشد.اگر S = {2, 4, 6}و T = {1, 2, 3, 4, 5, 6, 7}  S زیرمجموعه T استصورت نمایش: S  T به بیان دیگر  x (x  S  x  T)برای هر مجموعه S داریم: S  S (S S  S)برای هر مجموعه S داریم:   S (S   S)

اسلاید 10: 10مجموعه S زير مجموعه محض (proper subset) T است، اگر و فقط S زير مجموعه T باشد و. S⊂ TT = {0, 1, 2, 3, 4, 5}S = {1, 2, 3}S≠ T و S  T نمایش: S  Tزیرمجموعه محض (Proper Subsets)

اسلاید 11: مثالReal Numbers RRational Numbers QIntegers ZWhole numbers WNatural Numbers NIrrationalNumbersH

اسلاید 12: 12Set cardinalityاگر S يك مجموعه باشد و n تعداد عناصر متمايز مجموعه S كه n عدد صحيح نامنفي است، گوييمS يك مجموعه محدود و n، Cardinality مجموعه S است و با |S| نشان مي دهيم.R = {1, 2, 3, 4, 5}. |R| = 5|| = 0S = {, {a}, {b}, {a, b}}. |S| = 4مثال: اگرA مجموعه اعداد صحيح مثبت فرد كمتر از 10 باشد.مثال: اگرS مجموعه حروف الفباي انگليسي باشد.يك مجموعه نامحدود است اگر تعداد اعضای محدود نباشد.(infinite)مثال: مجموعه اعداد صحيح مثبت

اسلاید 13: 13مجموعه توانی (Power Sets)تمام زیر مجموعه های مجموعه S = {0, 1}  , {0}, {1}, {0, 1} زیر مجموعه تمام مجموعه ها استمجموعه توانی یک مجموعه S، مجموعه تمام زیر مجموعه های آن مجموعه است که آن را با P(S) نمایش می دهیم.P(S) = { , {0}, {1}, {0,1} } -- |S| = 2 و |P(S)| = 4T = {0, 1, 2}. P(T) = { , {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2} }|T| = 3 و |P(T)| = 8P() = {  } -- || = 0 و |P()| = 1مجموعه توانی یک مجموعه با n عضو، 2n عضو دارد.

اسلاید 14: 14تاپل ها (Tuples)در فضای دو بعدی (2-dimensional space) ما از زوج (x, y) برای برای مشخص نمودن یک نقطه استفاده می کنیمدر فضای سه بعدی (3-dimensional space) ما از سه تایی (x, y, z) برای برای مشخص نمودن یک نقطه استفاده می کنیم (1,2,3) ≠ (3,2,1)یک فضای n بعدی (n-dimensional space) یک تاپل n تایی (n-tuple) از اعضا استThree-dimensional space uses triples, or 3-tuplesتوجه کنید که در این تاپل ها برعکس مجموعه ها ترتیب مهم استهمیشه x اولین عنصر است+x+y(2,3)

اسلاید 15: تاپل ها (Tuples)تاپل nتايي مرتب (a1, a2 ,… , an) مجموعه مرتبي است كه a1 اولين عنصر، a2 دومين عنصر ،...، وan n امين عنصر است.گوييم دو تاپل nتايي مرتب مساوي هستند اگر همه اعضاي نظير به نظير آن مساوي باشند.به تاپل 2تايي مرتب، زوج مرتب مي گوييم.

اسلاید 16: ضرب کارتزین (Cartesian products)فرض كنيد A وB مجموعه باشند ضرب كارتزينA وB كه با A✕B نشان داده مي شودA x B = { (a,b) | a  A and b  B }A = { a, b } و B = { 0, 1 }C = A x B = { (a,0), (a,1), (b,0), (b,1) }

اسلاید 17: 17ضرب کارتزین (Cartesian products)S = { Alice, Bob, Chris } و G = { A, B, C }D = { (Alice, A), (Alice, B), (Alice, C), (Bob, A), (Bob, B), (Bob, C), (Chris, A), (Chris, B), (Chris, C) }یک زیرمجموعه از مجموعه حاصل از ضرب کارتزین را رابطه (relation) نیز می نامند

اسلاید 18: فصل دوم: ساختارهای ابتدایی: مجموعه، تابع، دنباله و تجمیع بخش 2.2 عملیات مجموعه (Set Operations)

اسلاید 19: عملیات بر روی مجموعهاجتماع (Union)اشتراک (Intersection)تفاضل (Difference)

اسلاید 20: 20اجتماع (Union)A U B = { x | x  A or x  B }مثال{1, 2, 3} U {3, 4, 5} = {1, 2, 3, 4, 5}{a, b} U {3, 4} = {a, b, 3, 4}{1, 2} U  = {1, 2}خصوصیات اجتماعA U  = AIdentity lawA U U = UDomination lawA U A = AIdempotent lawA U B = B U ACommutative lawA U (B U C) = (A U B) U CAssociative lawA

اسلاید 21: 21اشتراک (Intersection)A ∩ B = { x | x  A and x  B }مثال{1, 2, 3} ∩ {3, 4, 5} = {3}{a, b} ∩ {3, 4} = {1, 2} ∩  = خصوصیات اشتراکA ∩ U = AIdentity lawA ∩  =  Domination lawA ∩ A = AIdempotent lawA ∩ B = B ∩ ACommutative lawA ∩ (B ∩ C) = (A ∩ B) ∩ CAssociative lawUAB

اسلاید 22: 22مجموعه های مجزا (Disjoint sets)دو مجموعه مجزا هستند وقتی اشتراک دو مجموعه تهی باشد.مثال:{1, 2, 3} and {3, 4, 5} are not disjoint{a, b} and {3, 4} are disjoint{1, 2} and  are disjoint and  are disjoint!

اسلاید 23: 23A - B = { x | x  A and x  B }مثال:{1, 2, 3} - {3, 4, 5} = {1, 2}{a, b} - {3, 4} = {a, b}{1, 2} -  = {1, 2}خصوصیات اشتراکA - U = A -  = AA - A = A - B ≠ B - AA - (B - C) ≠ (A - B) - Cتفاضل (Difference)UAAB

اسلاید 24: تفاضل متقارن (Symmetric Difference)UAB

اسلاید 25: 25مجموعه مکمل (Complement set)U – A = { x | x  A } = Ac = A مثال: (فرض می کنیم U = Z){1, 2, 3}c = { …, -2, -1, 0, 4, 5, 6, … }{a, b}c = Zخصوصیات مجموعه مکمل(Ac)c = AComplementation lawA U Ac = U Complement lawA ∩ Ac = Complement lawUAA

اسلاید 26: 26خصوصیات مجموعه ها (Set identities)A = AAU = Aقوانين هماني Identity LawAU = UA = قوانین غلبهDomination lawAA = AAA = Aقوانین خودتوانی Idemptent Law(Ac)c = Aقانون مکمل (نفي دوگانه)Complement LawAB = BAAB = BAقوانين جابجايي Commutative Law(AB)c = AcBc(AB)c = AcBcقوانين دمورگان De Morgan’s LawA(BC) = (AB)CA(BC) = (AB)Cقوانين شركت پذيري Associative LawA(BC) = (AB)(AC)A(BC) = (AB)(AC)قوانين توزيع پذيري Distributive LawA(AB) = AA(AB) = Aقانون جذبAbsorption LawA  Ac = UA  Ac = مکملComplement Law

اسلاید 27: 27چگونه می توان خصوصیات مجموعه ها را اثبات نمود؟برای مثال A∩B=B-(B-A)چهار روش وجود دارداستفاده از خصوصیات پایه ای تراستفاده از جداول عضویتثابت کنیم هر کدام از دو طرف تساوی زیر مجموعه دیگری استاستفاده از set builder notation و هم ارزی منطقی

اسلاید 28: 28می خواهیم ثابت کنیم A∩B=B-(B-A)ABA∩BB-AB-(B-A)=U

اسلاید 29: 29اثبات به کمک خصوصیات پایه ای مجموعه هاA  B = A - (A - B)اثبات A - (A - B) = A - (A  Bc) = A  (A  Bc)c = A  (Ac  B) = (A  Ac)  (A  B) =   (A  B) = A  B

اسلاید 30: 30اثبات به کمک زیر مجموعه بودن و هم ارزی منطقی(A  B)c = Ac  Bcبرای اثبات باید در دو حالت زیر را نشان دهیم که درست است (A  B)c  Ac  Bc and (A  B)c  Ac  Bcx  (A  B)c  x (A  B)   (x  A  B)   (x  A  x  B)   (x  A)   (x  B)  x  A  x  B  x  Ac  x  Bc  x  Ac  Bc  x (x  (A  B)c  x  Ac  Bc) (A  B)c  Ac  Bc

اسلاید 31: استفاده از جداول عضویتاثبات (AB)B = AB

اسلاید 32: 32چند مثالنشان دهید(AUB)  (AUBUC)(A∩B∩C)  (A∩B)(A-B)-C  A-C(A-C) ∩ (C-B) = 

اسلاید 33: اشتراک و اجتماع عمومیت یافته (Generalized)اجتماع دسته ای از مجموعه ها مجموعه ای است که شامل عناصری است که حداقل عضو یکی از این مجموعه ها باشند. اشتراک دسته ای از مجموعه ها مجموعه ای است که شامل عناصری است که عضو همه این مجموعه ها باشند.