Discrete Mathematics - 2.1 - Sets

Discrete Mathematics - 2.1 - Sets

Introduction

এই আর্টিকেলে আমরা একটা ফান্ডামেন্টাল ডিসক্রিট স্ট্রাকচার নিয়ে আলোচনা করবো যার উপর বাকি সব ডিসক্রিট স্ট্রাকচারগুলো তৈরি হয়েছে। এই স্ট্রাকচারের নাম হলো সেট। সেট সম্পর্কে আমরা কমবেশি সবাই জানি। এটা মূলত কিছু বস্তুকে একটা গ্রুপে একীভূত করতে ব্যবহার করা হয়। যেমন আমরা সকল ফলকে একটা লিস্ট করলে সেটাকে আমরা বলতে পারি এটা একটা ফলের সেট। আবার ফলের মধ্যে আমের বিভিন্ন প্রকার নিয়ে আমের একটা সেট তৈরি করতে পারি। অর্থাৎ কিছু বস্তুর একটা গ্রুপ আমরা একটা সেটের মধ্যে রাখতে পারি। সেটের যেটা ফরমাল ডেফিনিশন সেটা আমরা দেখবো এখন।

সেট

সেট হচ্ছে বাস্তব বা চিন্তাজগতের বস্তুর যেকোনো সুনির্ধারিত সংগ্রহ। এই বস্তুগুলোকে বলা হয় উপাদান বা সদস্য যাকে ইংরেজিতে element বা member বলা হয়। একটা সেটকে এসব সদস্য বা এলিমেন্টের কন্টেইনার হিসেবে কল্পনা করা যায়। ধরি a হলো A সেটের সদস্য। এটাকে লেখা যায় a ∈ A রূপে। আর যদি a, A সেটের সদস্য না হয় তাহলে এটাকে লেখা যায় a ∉ A।

সেটের নামকে ইংরেজি বড় হাতের অক্ষর দিয়ে প্রকাশ করা হয়। আর সেটের সদস্যগুলোকে ইংরেজি ছোট হাতের অক্ষর দিয়ে প্রকাশ করা হয়।

একটা সেটকে প্রকাশে অনেক ধরণের মেথড আছে। একটা মেথড হচ্ছে লিস্ট আকারে একটা সেটের সব সদস্যকে লেখা। এটা সাধারণত {} অর্থাৎ কার্লি ব্র্যাকেটের মধ্যে লেখা হয়। যেমন - {a, b, c, d} হলো a, b, c, d সদস্যগুলোর একটা সেট। এই মেথডকে বলা হয় Roaster Method (রোস্টার মেথড)

উদাহরণ - ১ঃ ইংরেজি বর্ণমালার Vowel এর সেটকে লিখতে পারি আমরা V = {a, e, i, o, u}।

উদাহরণ - ২ঃ ১০ এর নিচে সকল বিজোড় ধনাত্মক সংখ্যার সেট হলো O = {1, 3, 5, 7, 9}।

আরেক ধরণের মেথড আছে যাকে set builder মেথড বলা হয়। এটা লেখা যায় {x | x has property P}। এটাকে পড়া হয় the set of all x such that x has property P, অর্থাৎ সকল x এর সেট যেন x এর মধ্যে P প্রোপার্টি থাকে। আমরা যদি ১০ এর নিচে সকল বিজোড় ধনাত্মক সংখ্যার সেট এই মেথড দিয়ে লিখতে চাই তাহলে আমরা লিখতে পারি -

O = {x | x is an odd positive integer less than 10}

Intervals

সেটের মধ্যে আরেকটা কনসেপ্ট আছে সেটাকে বলে intervals। Intervals দুই প্রকার। যথাঃ closed intervals এবং open intervals। closed intervals বুঝাতে আমরা '[' ও ']' ব্যবহার করি। এবং open intervals বুঝাতে আমরা ব্যবহার করি '(' এবং ')'। ধরেন একটা সেট দুইটা বাস্তব সংখ্যার মধ্যে যতগুলো সংখ্যা আছে সব। এখন closed intervals বলতে বুঝাচ্ছে ঐ দুইটা বাস্তব সংখ্যাসহ এই দুইটা নাম্বারের মধ্যবর্তী সকল সংখ্যার সেট। আর open intervals বলতে বুঝাচ্ছে এই দুইটা বাস্তব সংখ্যা বাদ দিয়ে এই দুইটা সংখ্যার মধ্যবর্তী সকল সংখ্যার সেট। চারভাবে সাধারণত আমরা এগুলো লিখতে পারি। ধরি a ও b দুইটি বাস্তব সংখ্যা যেখানে a ≤ b।

  • [a, b] = {x | a ≤ x ≤ b}
  • [a, b) = {x | a ≤ x < b}
  • (a, b] = {x | a < x ≤ b}
  • (a, b) = {x | a < x < b}

প্রথমটাকে বলা হচ্ছে closed interval, যেখানে a এবং b এর মধ্যে এই দুইটা সহ সকল সংখ্যার সেট বুঝাচ্ছে। দ্বিতীয়টাকে বলা হচ্ছে closed open interval যেখানে a এবং b এর মধ্যে a সহ কিন্তু b বাদে বাকি সকল সংখ্যার সেট বুঝাচ্ছে। তৃতীয়টাকে বলা হচ্ছে open closed interval যেখানে a এবং b এর মধ্যে a বাদে কিন্তু b সহ বাকি সকল সংখ্যার সেট বুঝাচ্ছে। চতুর্থটাকে বলা হচ্ছে open interval যেখানে a এবং b এর মধ্যে a ও b দুইটা সংখ্যা বাদ দিয়ে বাকি সংখ্যাগুলোর সেট বুঝাচ্ছে। আশা করি intervals সম্পর্কে আপনারা বুঝে গেছেন।

Set of sets

একটা সেটে সদস্য হিসেবে একাধিক সেটও থাকতে পারে। অর্থাৎ সদস্য হিসেবে সেট থাকত পারে। যাকে Set of sets বলা হয়। যেমন - {N, Z, Q, R} হলো N, Z, Q, R এই চারটা সেটের সেট, যেখানে N হলো সকল স্বাভাবিক সংখ্যার সেট, Z হলো সকল পূর্ণসংখ্যার সেট, Q হলো সকল মূলদ সংখ্যার সেট এবং R হলো সকল বাস্তব সংখ্যার সেট।

Equality of sets

দুইটা সেট তখনই সমান হবে যদি ও কেবল যদি এদের একই সদস্য থাকে। এখানে কোন অর্ডারে সেগুলো আছে এবং কতবার আছে সেটা বিবেচ্য বিষয় নয়। দুইটা সেটের সদস্যসমূহ একই হলেই সেই দুইটা সেট সমান বলে ধরে নেয়া যাবে। যেমন - {1, 2, 3} এবং {3, 2, 1} সেটের সদস্যত্রয় সমান। এরা একই অর্ডারে না থাকলেও আমরা সেট দুইটিকে সমান বলতে পারি। আবার {1, 2, 3} এবং {1, 2, 2, 2, 3, 3} সেটদ্বয়ও সমান। কারণ প্রথম সেটের সকল সদস্য দ্বিতীয় সেটে আছে এবং দ্বিতীয় সেটের সকল সদস্য প্রথম সেটে আছে। এই কনসেপ্টকে গাণিতিক স্টেটমেন্টে প্রকাশ করতে হলে আমাদের পূর্বের চাপটারে শেখা বাইকন্ডিশনাল এবং ইউনিভার্সাল কোয়ান্টিফায়ার ব্যবহার করতে হবে। একে লেখা যায় যদি A এবং B দুইটা সেট হয়, তাহলে A ও B সমান হবে যদি ∀x(x ∈ A ↔ x ∈ B)। অর্থাৎ ডোমেইনের সকল ভ্যালু x যদি ও কেবল যদি A এবং B এর সদস্য হয় তবেই A ও B সমান হবে। A এবং B সমান হলে আমরা লিখতে পারি A = B।

Empty sets

যেসকল সেটের কোনো সদস্য বা উপাদান থাকে না তাদের ফাঁকা সেট বা Empty sets বলে। এদেরকে null sets বা শূন্য সেটও বলা হয়ে থাকে। ফাঁকা সেটকে দুইভাবে প্রকাশ করা হয়ে থাকে। ∅ বা { }।

Singleton sets

যে সকল সেটের শুধুমাত্র একটা সদস্য বা উপাদান থাকে তাদের singleton sets বলা হয়ে থাকে। যেমন - {1}, {a}, {apple} ইত্যাদি। অনেকেই {∅} কে ফাঁকা সেট বলে মনে করে থাকেন। কিন্তু এটা আসলে একটা singleton set। কারণ এই সেটের একটা উপাদান আছে যেটা হলো ফাঁকা সেট। তাই এটাকে ফাঁকা সেট বলা যাবেন। এর উপাদান ফাঁকা সেট। কিন্তু এই সেট ফাঁকা নয়।

Venn Diagrams

সেটকে গ্রাফিক্যালি রিপ্রেজেন্ট করার জন্য ব্যবহৃত হয় ভেন ডায়াগ্রাম। একজন ব্রিটিশ ম্যাথমেটিশিয়ান জন ভেন ১৮৮১ সালে এটি আবিষ্কার করেন। এতে একটা ইউনিভার্সাল সেট থাকে যাকে U দিয়ে প্রকাশ করা হয়। এই সেটকে একটা আয়তাক্ষেত্র দিয়ে প্রকাশ করা হয়। এর মধ্যে বৃত্ত বা অন্যান্য জ্যামিতিক ফিগার দিয়ে সেটসমূহকে বুঝানো হয়। ভেন ডায়গ্রাম মূলত সেটসমূহের মধ্যে সম্পর্ক বুঝানোর জন্য ব্যবহৃত হয়।

উদাহরণঃ ভেন ডায়াগ্রামের মাধ্যমে ইংরেজি বর্ণমালার সকল Vowel এর সেট V কে প্রকাশ করা হলো।

venn-vowels.jpg

Subsets

ধরি দুইটা সেট A এবং B। এখন A সকল সদস্য বা উপাদান যদি B এর ও সদস্য বা উপাদান হয় তাহলে A কে বলা হয় B এর সাবসেট, যাকে লেখা যায় A ⊆ B এভাবে এবং B কে বলা হয় A এর সুপারসেট যাকে লেখা যায় B ⊇ A। আমরা যদি সাবসেটের কনসেপ্টকে কোয়ান্টিফিকেশনের মাধ্যমে লিখি তাহলে লিখতে পারি, A ⊆ B সাবসেট হবে যদি ∀x(x ∈ A → x ∈ B) সত্য হয়। অর্থাৎ ডোমেইনের সকল ভ্যালু x এর জন্য যদি x, সেট A এর উপাদান হয় তাহলে সেট B এরও উপাদান হবে। A যদি B এর সাবসেট না হয় তাহলে সেটাকে লেখা যায় A ⊈ B এভাবে।

সাবসেটের কয়েকটা উদাহরণ দেখি।

  • ১০ এর নিচে সকল ধনাত্মক বিজোড় পূর্নসংখ্যার সেট, ১০ এর নিচে সকল ধনাত্মক পূর্ণসংখ্যার সেটের সাবসেট।
  • সকল মূলদ সংখ্যার সেট, সকল বাস্তব সংখ্যার সেটের সাবসেট।
  • ক্লাসের সকল কম্পিউটার সায়েন্সের ছাত্রছাত্রীর সেট, ক্লাসের সকল ছাত্রছাত্রীর সেটের সাবসেট।

A ⊆ B কে ভেন ডায়াগ্রামের মাধ্যমে যদি আমরা দেখাই তাহলে নিচের মতো দেখাবে -

venn-subset.jpg

উদাহরণ A = {1, 3, 5}, B = {1, 2, 3, 4, 5}। এখানে A ⊆ B কিনা তা আমরা দেখি। যেহেতু A এর প্রতিটা উপাদান B এর মধ্যে আছে তাই A ⊆ B আমরা বলতে পারি।

Size of a set

ধরি S একটি সেট। S এর n সংখ্যক উপাদান রয়েছে। তাহলে আমরা S কে বলতে পারি সসীম সেট বা Finite Sets এবং n কে বলতে পারি Cardinality of S। অর্থাৎ S এর আকার হলো n। একে প্রকাশ করা যায় |S| দিয়ে। কয়েকটা উদাহরণ দেখি আমরা -

  • যদি A ১০ এর নিচে সকল ধনাত্মক বিজোড় পূর্ণসংখ্যার সেট হয় তাহলে |A| = 5। কারণ A = {1, 3, 5, 7, 9} অর্থাৎ A এর ৫টি উপাদান রয়েছে।
  • যদি S ইংরেজি বর্ণমালার সেট হয় তাহলে |S| = 26।
  • একটা ফাঁকা সেটের সাইজ হবে |∅| = 0, কারণ এর কোনো উপাদান নেই।

যেসকল সেটের উপদানকে গুণে শেষ করা যায় না বা যেসকল সেট সসীম নয় তাদের বলে অসীম সেট বা Infinite Sets। যেমন - সকল ধনাত্মক পূর্নসংখ্যার সেট হলো অসীম। Cardinality of sets এর উপরে আমাদের পরবর্তীতে একটা ডেডিকেটেড আর্টিকেল থাকবে। সেখানে আমরা এ সম্পর্কে বিস্তারিত আলোচনা করবো।

Power Sets

কোনো একটা সেটের সকল সাবসেটের সেটকে Power set বা শক্তি সেট বলে। একে P(s) দ্বারা প্রকাশ করা হয়। একটা উদাহরণ দিলে সেটা পরিস্কার হয়ে যাবে আপনাদের।

{0, 1, 2} এর শক্তি সেট কি হতে পারে? প্রথমে আমাদের বের করতে হবে এই সেটের সম্ভাব্য সাবসেটগুলো কি কি হতে পারে। এগুলো হতে পারে ∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}। তাহলে সংজ্ঞানুযায়ী এসকল সাবসেটের সেটই হবে আমাদের শক্তি সেট।

অর্থাৎ P({0, 1, 2}) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}

ফাঁকা সেট এবং একটা সেট নিজে শক্তি সেটের সদস্য।

একটা ফাঁকা সেটের শক্তি সেট হবে P(∅) = {∅}।

{∅} সেটের শক্তি সেট হবে {∅, {∅}}।

Cartesian Products

দুইটি সেটের কার্টেসীয়ান গুণফল নিয়ে আমরা আলোচনা করবো এয়ার। ধরি A ও B দুইটা সেট। এদের কার্টেসীয়ান গুণফল প্রকাশ করা হয় A x B দিয়ে, তা হলো সকল ordered pairs (a, b) এর সেট, যেখানে a ∈ A এবং b ∈ B। অর্থাৎ

A x B = {(a, b) ∣ a ∈ A ∧ b ∈ B}

একটা উদাহরণ দিলে মাথায় ভালভাবে ঢুকে যাবে।

ধরি A = {1, 2} এবং B = {a, b, c}। এদের কার্টেসীয়ান গুণফল হবে -

A x B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}

একটা জিনিস মাথায় রাখতে হবে যেটা, সেটা হলো A x B ≠ B x A। কেন সেটা এখনই বুঝবেন যখন আমরা B x A বের করবো।

B x A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}

একদম স্পষ্টভাবেই দেখা যাচ্ছে A x B ≠ B x A। শুধুমাত্র যখন A = ∅ এবং B = ∅ হবে তখনই A x B = B x A হবে।

এতক্ষণ দুইটা সেটের কার্টেসীয়ান গুণফল দেখলাম। এবার তিনটার জন্য দেখি।

দেয়া আছে, A = {0, 1}, B = {1, 2}, C = {0, 1, 2}। বের করতে হবে A x B x C। চলুন বের করি।

A x B x C = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2)}

A x B x C কে আপনারা আবার যেন (A x B) X C এবং A x (B x C) এর সাথে গুলিয়ে ফেলবেন না। কেন সেটা আপনাদের জন্য টাস্ক। প্রথমে A x B বের করবেন। ধরলাম এর কার্টেসীয়ান গুণফল হিসেবে X পাবেন। এরপর X x C বের করবেন। A x (B x C) এর ক্ষেত্রেও একইভাবে বের করবেন। করে দেখবেন সেগুলো A x B x C এর সাথে মিলে কিনা। তাহলেই এর উত্তর পেয়ে যাবেন।

Truth sets and quantifiers

আমরা এখন সেট এবং predicate logic এর থিওরি একত্র করবো। ধরি আমাদের কাছে একটা predicate আছে P এবং একটা ডোমেইন আছে D। এখন P এর truth set বা সত্য সেট হবে D এর মধ্যে থাকা সকল উপাদান x এর সেট যার জন্য P(x) সত্য হবে। P(x) এর সত্য সেট প্রকাশ করা হয় {x ∈ D | P(x)} দিয়ে। চলুন একটা উদাহরণ দেখি।

ধরি আমাদের কাছে তিনটা predicates আছে যেগুলো হলো - P(x), Q(x), R(x) যেখানে P(x) হলো |x| = 1, Q(x) হলো x² = 2 এবং R(x) হলো |x| = x. এদের সত্য সেটগুলো আমাদের বের করতে হবে। এখানে ডোমেইন হলো সকল পূর্ণসংখ্যার সেট, Z।

প্রথম ক্ষেত্রে P এর সত্য সেট, {x ∈ Z | |x| = 1}, হলো একটা পূর্ণসংখ্যার সেট যার জন্য |x| = 1 হবে। যেহেতু শুধুমাত্র x = 1 অথবা x = -1 হলেই |x| = 1 হবে, অন্য কোনো পূর্ণসংখ্যার জন্য |x| = 1 হবে না, তাই P এর সত্য সেট হবে {-1, 1}।

দ্বিতীয় ক্ষেত্রে Q এর সত্য সেট, {x ∈ Z | x² = 2}, হলো একটা পূর্ণসংখ্যার সেট যার জন্য x² = 2 হবে। কিন্তু এমন কোনো পূর্ণসংখ্যা নেই যার জন্য x² = 2 সত্য হবে। সুতরাং Q এর সত্য সেট হবে ফাঁকা সেট অর্থাৎ ∅।

তৃতীয় ক্ষেত্রে R এর সত্য সেট {x ∈ Z ∣ |x| = x}, হলো একটা পূর্ণসংখ্যার সেট যার জন্য |x| = x হবে। |x| = x হবে যদি ও কেবল যদি x ≥ 0 হয়। সুতরাং R এর সত্য সেট হবে N বা সকল অঋণাত্মক পূর্ণসংখ্যার সেট।

Conclusion

আজকের আর্টিকেলটা মূলত আমরা এসএসসিতে সেটের যে ধারণা পেয়েছিলাম তারই একটা রিভিউ বলে ধরে নিতে পারেন। আরেকবার সেই পড়াগুলো ঝালাই হয়ে গেলো। পরবর্তী আর্টিকেলে আমরা সেটের বিভিন্ন অপারেশন সম্পর্কে আলোচনা করবো।