پاورپوینت مجموعه، تابع، دنباله و تجمیع ساختمان گسسته

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

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

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

مثال مجموعه های پرکاربرد
مجموعه حروف صدا دار: 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
نمودار ون (Venn diagrams)
نمایش گرافیکی مجموعه ها
مستطیل بیرونی مجموعه عالم را نشان می دهد
دایره یک مجموعه را نمایش می دهد
S مجموعه حروف صدا دار در زبان انگلیسی را نشان می دهد
معمولا اعضای مجموعه
در نمودار نوشته نمی شود

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

1 ≠ {1} ≠ {{1}} ≠ {{{1}}}

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

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
مجموعه S زیر مجموعه محض (proper subset) T است، اگر و فقط S زیر مجموعه T باشد و. S⊂ T
T = {0, 1, 2, 3, 4, 5}
S = {1, 2, 3}
S≠ T و S  T
نمایش: S  T
زیرمجموعه محض (Proper Subsets)

مثال
Real Numbers R
Rational Numbers Q
Integers Z
Whole numbers W
Natural
Numbers N
Irrational
Numbers
H

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

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

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 اولین عنصر است

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

ضرب کارتزین (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
ضرب کارتزین (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) نیز می نامند

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

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

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  = A Identity law
A U U = U Domination law
A U A = A Idempotent law
A U B = B U A Commutative law
A U (B U C) = (A U B) U C Associative law

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 = A Identity law
A ∩  =  Domination law
A ∩ A = A Idempotent law
A ∩ B = B ∩ A Commutative law
A ∩ (B ∩ C) = (A ∩ B) ∩ C Associative law

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
A – 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 –  = A
A – A = 
A – B ≠ B – A
A – (B – C) ≠ (A – B) – C
تفاضل (Difference)

تفاضل متقارن (Symmetric Difference)
U
A
B

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 = A Complementation law
A U Ac = U Complement law
A ∩ Ac =  Complement law

26
خصوصیات مجموعه ها (Set identities)

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

28
می خواهیم ثابت کنیم A∩B=B-(B-A)
A
B
A∩B
B-A
B-(B-A)
=
U

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
اثبات به کمک زیر مجموعه بودن و هم ارزی منطقی
(A  B)c = Ac  Bc
برای اثبات باید در دو حالت زیر را نشان دهیم که درست است
(A  B)c  Ac  Bc and (A  B)c  Ac  Bc

x  (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

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

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

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

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