Introduction

আজকের আর্টিকেলে আমরা Proof (প্রুফ) নিয়ে আলোচনা করবো। প্রুফ অর্থ প্রমাণ করা। এই প্রমাণ করার সাথে আমরা ছোট থেকে অনেক পরিচিত। যেকোনো গাণিতিক সূত্র, উপপাদ্য, গাণিতিক স্টেটমেন্ট ইত্যাদি প্রমাণ করতাম আমরা। তাহলে প্রুফ হলো একটা ভ্যালিড আর্গুমেন্ট যেটা একটা গাণিতিক স্টেটমেন্টের সত্যতা প্রতিষ্ঠা করে। আজকে আমরা এই প্রুফ এর সাথে পরিচিত হবো। চলুন শুরু করা যাক।

কিছু বেসিক সংজ্ঞা

প্রুফ সম্পর্কে আলোচনা করতে গেলে আমাদের কিছু টার্মস আসবে। সেই টার্মসগুলো সম্পর্কে আগে একটু জেনে রাখলে আমাদের জন্য পরবর্তী টপিকগুলো বুঝাটা সহজ হয়ে যাবে।

• Theorem - সাধারণভাবে theorem বা উপপাদ্য হলো একটি স্টেটমেন্ট যার সত্যতা প্রতিষ্ঠিত হয়ে গেছে অর্থাৎ যেটা প্রমাণিত। গণিতে থিওরাম শব্দটা সাধারণত অধিক গুরুত্বপূর্ণ স্টেটমেন্টের জন্য বরাদ্দ রাখা হয়। আর কম গুরুত্বপূর্ণ স্টেটমেন্টকে প্রোপোজিশন বলা হয়।

• Axioms - Axioms হলো এমন কিছু স্টেটমেন্ট যাকে আমরা সত্য বলে বিবেচনা করতে পারি।

Methods of proving theorems

থিওরাম প্রমাণ করা খুবই জটিল। এই প্রুফ তৈরি করতে আমাদের অনেক ধরণের মেথড প্রয়োজন হয়। এই মেথডগুলো ম্যাথমেটিক্যাল প্রুফ কনস্ট্রাক্ট করা এবং কিভাবে পড়তে হবে তা শেখার জন্য গুরুত্বপূর্ণ ভূমিকা পালন করে। আমরা যখন কোনো প্রুফ মেথড সিলেক্ট করে ফেলবো, তখন এই প্রুফ সম্পন্ন করার জন্য আমরা axioms, পূর্বের প্রমাণিত রেজাল্ট এবং rules of inference ব্যবহার করবো।

জানি এত কথা সব মাথার উপর দিয়ে যাচ্ছে আপনাদের। একটু পর আপনারা এসব কথার মানে বুঝতে পারবেন। আমরা এখন কিছু প্রুফ মেথড নিয়ে আলোচনা করি আগে।

Direct Proofs

p → q এই স্টেটমেন্ট প্রমাণের ক্ষেত্রে প্রথম স্টেপ হলো এটা ধরে নেয়া যে p true, পরের স্টেপ হলো কিছু rules of inference ব্যবহার করে ফাইনাল স্টেপে দেখানো যে, q অবশ্যই true হবে যেন p true এবং q false এই কম্বিনেশনটা না আসে। এই যে প্রসেসটা, এটাকে বলা হয় Direct Proof। অর্থাৎ ডিরেক্ট প্রুফে আমরা প্রথমে ধরে নিই p true। এরপর rules of inference এর সাথে axioms, definition, পূর্বের প্রমাণিত থিওরাম ব্যবহার করি q যে true এটা প্রমাণ করার জন্য। কিছু কিছু ডিরেক্ট প্রুফ খুবই স্ট্রেটফরওয়ার্ড, জাস্ট হাইপোথেসিস দিয়ে শুরু, conclusion দিয়ে শেষ। আবার কিছু কিছু ডিরেক্ট প্রুফ আছে যা অনেক ট্রিকি। আমরা দুই রকমেরই উদাহরণ দেখবো।

Give a direct proof of the theorem 'If n is an odd integer, then n² is odd'.

এই স্টেটমেন্ট থেকে আমরা এর গাণিতিক ফর্মটা বের করি প্রথমে। সেটা হলো ∀nP((n) → Q(n)), যেখানে P(n) হলো 'n is an odd integer' এবং q হলো 'n² is odd'। ডিরেক্ট প্রুফের নিয়মানুসারে আমরা প্রথমে ধরে নিই আমাদের হাইপোথিসিস অর্থাৎ p সত্য। তার মানে n একটি বিজোড় সংখ্যা। বিজোড় সংখ্যাকে আমরা বীজগাণিতিকভাবে প্রকাশ করি n = 2k + 1, যেখানে k হলো একটি যেকোনো সংখ্যা। এবার n² একটি বিজোড় সংখ্যা প্রমাণ করার জন্য আমরা ছোটবেলার মতো নিচের ইকুয়েশন সলভ করবো।

n = 2k + 1
=> n² = (2k + 1)² [উভয় পক্ষকে বর্গ করে]
=> n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1 = 2m + 1 [যেখানে m = 2k² + 2k]

n² = 2m + 1 এই সমীকরনটা বুঝাচ্ছে এটি একটি বিজোড় সংখ্যা। অর্থাৎ n² একটি বিজোড় সংখ্যা। তার মানে যদি n বিজোড় সংখ্যা হয় তাহলে n² ও বিজোড় সংখ্যা হবে।

ডিরেক্ট প্রুফের মাধ্যমে দেখান যে যদি m এবং n পারফেক্ট স্কয়ার হয় তাহলে mn ও পারফেক্ট স্কয়ার হবে।

পারফেক্ট স্কয়ার বলতে বুঝানো হচ্ছে a = b², যেখানে a এবং b দুইটা পূর্ণসংখ্যা। এখন ডিরেক্ট প্রুফের নিয়মানুসারে ধরে নিই m এবং n দুইটা পারফেক্ট স্কয়ার অর্থাৎ m = s² এবং n = t², যেখানে s এবং t হলো দুইটা পূর্ণসংখ্যা। এখন mn পারফেক্ট স্কয়ার কিনা তা দেখি আমরা।

mn = s²t² = (ss)(tt) = (st)(st) = (st)²

অতএব mn ও একটি পারফেক্ট স্কয়ার।

Indirect Proofs

ডিরেক্ট প্রুফ সবসময় premises থেকে শুরু হয়, মাঝখানে কিছু কাজ হয়, এরপর conclusion এ গিয়ে শেষ হয়। কিন্তু সবসময় ডিরেক্ট প্রুফ ব্যবহার করলে দেখা যাবে আমরা প্রায়ই একটা dead end এ গিয়ে পৌঁছাচ্ছি। তাই আমরা ডিরেক্ট প্রুফ ছাড়াও অন্য কিছু মেথড ব্যবহার করবো যেখানে premises দিয়ে শুরু হয় না এবং conclusion দিয়েও শেষ হয় না। এই ধরণের প্রুফকে বলা হয় Indirect Proofs। এবার আমরা এর কিছু মেথড দেখবো।

Proof by Contraposition

Indirect proof এর একটা গুরুত্বপূর্ণ টাইপ হলো Proof by Contraposition। এই মেথডে কন্ডিশনালের contrapositive এর থিওরি অ্যাপ্লাই করা হয়। অর্থাৎ p -> q সত্য হবে যদি এর contrapositive ¬q → ¬p সত্য হয়। অর্থাৎ p -> q প্রমাণ করতে হলে আমাদেরকে প্রমাণ করতে হবে ¬q → ¬p। তার মানে আমাদের premises হিসেবে ধরতে হবে ¬q এবং conclusion হিসেবে ধরতে হবে ¬p। যখন আমরা ডিরেক্ট প্রুফের মাধ্যমে কোনোকিছু সহজে প্রমাণ করতে পারি না তখন আমাদেরকে এই মেথড অনেক সাহায্য করে।

প্রমাণ করুন যে, যদি n একটি পূর্ণসংখ্যা হয় এবং 3n + 2 বিজোড় হয়, তাহলে n বিজোড় হবে।

প্রথমে আমরা ট্রাই করবো ডিরেক্ট প্রুফ। তার জন্য আমরা প্রথমে ধরে নিই 3n + 2 একটি বিজোড় সংখ্যা। অর্থাৎ 3n + 2 = 2k + 1 বা, 3n + 1 = 2k। কিন্তু এখানে থেকে আমরা কোনোভাবেই প্রমাণ করতে পারছি না যে n একটি বিজোড় সংখ্যা। সুতরাং ডিরেক্ট প্রুফ এখানে ফেইল। তাহলে আমাদের এখন যেতে হবে Proofs by contraposition এ।

এখানে যেহেতু আমরা Proofs by contraposition ব্যবহার করবো তাহলে আমাদের স্টেটমেন্টের contrapositive হবে ‘যদি n বিজোড় না হয়, তাহলে 3n + 2 বিজোড় হবে না’। এখন ধরি এর premise সত্য অর্থাৎ n বিজোড় না। তার মানে n জোড় সংখ্যা। বীজগাণিতিকভাবে যদি লিখি আমরা তাহলে লিখতে পারি n = 2k। এবার 3n + 2 তে n এর মান 2k বসিয়ে পাই 3.2k + 2 = 2(3k + 1) = 2m (যেখানে m = 3k + 1)। অর্থাৎ আমরা দেখতে পাচ্ছি 3n + 2 হচ্ছে জোড়। অর্থাৎ আমাদের contrapositive ‘If n is not odd, then 3n + 2 is not odd’ সত্য। যেহেতু contrapositive সত্য সেহেতু আমাদের মেইন স্টেটমেন্ট ‘If 3n + 2 is odd, then n is odd’ সত্য হবে Proofs by contraposition এর নিয়মানুসারে।

Vacuous Proofs

আমরা যদি p -> q প্রমাণ করতে চাই তাহলে যদি শুধু এটা প্রমাণ করতে পারি যে p false, তাহলে p -> q প্রমাণিত হবে। কারণ কন্ডিশনালের ক্ষেত্রে যদি p false হয় তাহলে q true বা false যাই হোক না কেন স্টেটমেন্ট সত্য হবে। তাহলে এখানে শুধু আমাদের p যে false সেটা প্রমাণ করতে হবে। এই মেথডকে বলা হয় Vacuous Proofs।

Show that the proposition P(0) is true, where P(n) is “If n > 1, then n² > n” and the domain consists of all integers.

এখানে P(0) বলতে বুঝাচ্ছে ‘If 0 > 1, then 0² > 0’। এখানে আমরা দেখছি আমাদের হাইপোথিসিস অর্থাৎ p false। কারণ 0 > 1 হতে পারে না। যেহেতু p false সুতরাং কন্ডিশনাল স্টেটমেন্ট সত্য হবে। তাই P(0) ও সত্য হবে।

Trivial Proofs

আবার আমরা যদি p -> q এর প্রমাণের ক্ষেত্রে শুধু এটা প্রমাণ করতে পারি যে q true, সেক্ষেত্রেও স্টেটমেন্ট সত্য হবে। কারণ q true হলে p সত্য বা মিথ্যা যাই হোক না কেন স্টেটমেন্ট সত্য হবে। এই মেথডকে বলা হয় Trivial Proofs।

Let P(n) be “If a and b are positive integers with a ≥ b, then a^n ≥ b^n,” where the domain consists of all nonnegative integers. Show that P(0) is true.

P(0) এর জন্য আমাদের স্টেটমেন্ট দাঁড়াচ্ছে ‘If a ≥ b, then a^0 ≥ b^0’। a^0 = b^0 = 1। সুতরাং আমাদের conclusion অর্থাৎ q সত্যি হচ্ছে। তার মানে P(0) সত্য।

Proofs by Contradiction

ধরি আমাদের কাছে একটা কন্ডিশনাল আছে p -> q। আমরা চাইছি আমাদের স্টেটমেন্টও সত্য হবে এবং আমাদের হাইপোথিসিস অর্থাৎ p ও সত্য হবে। এখন যদি p সত্য হয় তাহলে q কে অবশ্যই সত্য হতে হবে। কারণ q যদি false হয় তাহলে p কখনও সত্য হতে পারবে না। এই সকল প্রুফের ক্ষেত্রে আমরা ব্যবহার করবো contradiction অর্থাৎ ¬p -> q। এখানে যদি q মিথ্যা হয় তাহলে ¬p কে মিথ্যা হতে হবে বা p কে সত্য হতে হবে। এই মেথডকে বলা হয় Proofs by Contradiction। এই প্রুফটা আমরা ব্যবহার করবো যখন আমাদের conclusion মিথ্যা হবে তখন, কারণ যেকোনো মূল্যে আমাদের p সত্য হতে হবে। কেন সত্য হতে হবে? কারণ আমাদের রিকোয়ারমেন্টই এটা। p মিথ্যা হতে পারবে না।

এখন প্রশ্ন উঠতে পারে q সত্য হলেই তো ল্যাটা চুকে যায়। হ্যাঁ, তা হয়। কিন্তু যদি আমাদের এমন কোনো স্টেটমেন্ট থাকে যেখানে q মিথ্যা এবং p কে অবশ্যই সত্য হতে হবে, সেসব ক্ষেত্রে আমরা এই মেথড ব্যবহার করবো। ধরুন আমাদের q হলো (r ∧ ¬r), যেখানে r একটি প্রপোজিশন। এক্ষেত্রে সবসময় q মিথ্যা হবে। এখন স্টেটমেন্ট এবং p দুইটাকেই সত্য করতে হলে আমাদের contradiction অর্থাৎ ¬p -> (r ∧ ¬r) ব্যবহার করতে হবে। উদাহরণ দিলে আরো ভালভাবে বোঝা যাবে।

দেখান যে √2 একটি অমূলদ সংখ্যা।

এমন কোনো মানুষ নাই ছোটবেলায় আমরা এটা করিনি। একটি সংখ্যা p মূলদ বা rational হবে যদি p = a/b হয়, যেখানে b ≠ 0 এবং a ও b এর মধ্যে কোনো কমন ফ্যাক্টর নাই। আর যেসকল সংখ্যা মূলদ না সেগুলো অমূলদ বা irrational সংখ্যা।

এবার আসি আমাদের সল্যুশনে। ধরি p হলো √২ অমূলদ সংখ্যা। যদি আমরা proof by contradiction ব্যবহার করি, তাহলে আমাদের ধরে নিতে হবে ¬p সত্য হবে। অর্থাৎ √২ মূলদ সংখ্যা হবে। এখন যদি √2 মূলদ হয় তবে √2 = a/b হবে। এবার আমরা একটু সরল অংক করি।

√2 = a / b
=> 2 = a² / b² [উভয় পক্ষকে বর্গ করে]
=> 2b² = a²

এখান থেকে দেখা যাচ্ছে a² জোড় সংখ্যা। যেহেতু a² জোড় সংখ্যা হবে সেহেতু a ও জোড় সংখ্যা হবে। তাহলে a = 2c হবে, যেখানে c একটি পূর্ণসংখ্যা। এবার a এর জায়গায় 2c বসিয়ে পাই

2b² = 4c²
=> b² = 2c²

তার মানে দেখা যাচ্ছে b² জোড় সংখ্যা হবে। b² যেহেতু জোড় সেহেতু b ও জোড় হবে।

এখানে আমরা দেখছি a ও b দুইটাই জোড় সংখ্যা। কিন্তু মূলদ সংখ্যার সংজ্ঞামতে a এবং b এর মধ্যে কোনো কমন ফ্যাক্টর থাকতে পারবে না। তার মানে √২ মূলদ সংখ্যা নয় অর্থাৎ ¬p মিথ্যা। তার মানে p সত্য। অর্থাৎ √২ অমূলদ সংখ্যা।

Conclusion

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