Proof কী আর Direct Proof: যুক্তি দিয়ে প্রমাণের শুরু

On this page

একটা function হাজারটা test case-এ ঠিক output দিলেও কি নিশ্চিত বলা যায়, সব input-এ এটা ঠিক কাজ করবে? যায় না। Computer scientist Edsger Dijkstra-র বিখ্যাত কথা: test দিয়ে দেখানো যায় যে bug আছে, কিন্তু bug যে নেই সেটা কখনো দেখানো যায় না।

"সব input-এ সত্য" নিশ্চিত করার উপায় একটাই: proof। এই পর্ব থেকে proof লেখা শিখব, শুরু করব সবচেয়ে সোজা পদ্ধতি direct proof দিয়ে। (Section 1.7)

Proof কী?

Proof হলো এমন একটা valid যুক্তি, যেটা একটা statement-এর সত্যতা প্রতিষ্ঠা করে।

গণিত আর CS-এ সাধারণত informal proof লেখা হয়। সেখানে এক ধাপে একাধিক rule use করা হয়, ছোটখাটো ধাপ বাদ দেওয়া হয়, আর কোন rule use হলো সেটা আলাদা করে লেখা হয় না। পড়তে আর বোঝাতে সহজ, তবে ভুল ঢুকে পড়াও সহজ।

Proof-এর বাস্তব ব্যবহার:

Program যে সঠিক, সেটা যাচাই করা (Section 1.4-এর precondition আর postcondition)
Operating system যে secure, সেটা প্রতিষ্ঠা করা
Artificial intelligence-এ program-কে যুক্তি দিয়ে সিদ্ধান্ত নিতে শেখানো
System specification যে consistent, সেটা দেখানো (পর্ব ৩)

কিছু শব্দ

Theorem: এমন statement, যেটা সত্য বলে দেখানো যায়। দেখানো হয় definition, আগে প্রমাণিত theorem, axiom (যে statement গুলো প্রমাণ ছাড়াই সত্য ধরে নেওয়া হয়) আর rules of inference দিয়ে।
Lemma: "সাহায্যকারী theorem"। বড় একটা theorem প্রমাণ করতে যে ছোট ফলাফল লাগে।
Corollary: একটা theorem থেকে সরাসরি পাওয়া ফলাফল।
Proposition: কম গুরুত্বপূর্ণ theorem-কে অনেক সময় এই নামে ডাকা হয়। (পর্ব ১-এর proposition-এর সাথে নাম মিললেও এখানে মানে আলাদা।)
Conjecture: এমন statement, যেটা সত্য বলে প্রস্তাব করা হয়েছে, কিন্তু এখনো প্রমাণ হয়নি। Proof পাওয়া গেলে এটা theorem হয়ে যায়, আর counterexample পাওয়া গেলে মিথ্যা প্রমাণিত হয়।

$Axiom আর definition থেকে lemma, lemma থেকে theorem, theorem থেকে corollary; conjecture proof পেলে theorem হয়, counterexample পেলে false$

Code-এর সাথে মিলিয়ে ভাবলে: lemma হলো helper function, theorem হলো main function, আর corollary হলো main function-এর উপর বানানো ছোট একটা wrapper।

Theorem আসলে কী দাবি করে

"যদি x > y হয়, যেখানে x আর y ধনাত্মক real number, তাহলে x² > y²।"

এখানে "সব" শব্দটা লেখা নেই, কিন্তু মানে আসলে: "সব ধনাত্মক real number x আর y-এর জন্য, যদি x > y, তাহলে x² > y²।" গণিতে universal quantifier প্রায়ই উহ্য রাখা হয়।

তাই বেশিরভাগ theorem-এর আকার: ∀x (P(x) → Q(x))

এটা প্রমাণ করার কৌশল: domain থেকে যেকোনো একটা (arbitrary) element c নিই, যার সম্পর্কে বিশেষ কিছু ধরে নিই না, তারপর দেখাই P(c) → Q(c)। c যেহেতু যেকোনো element হতে পারত, তাই কথাটা সবার জন্যই সত্য। এই যুক্তির নাম universal generalization।

ফলে শেষ পর্যন্ত আমাদের প্রমাণ করতে হয় p → q আকারের কিছু।

দুটো definition

প্রমাণ লিখতে হলে definition একদম স্পষ্ট হতে হবে:

Even (জোড়): integer n জোড়, যদি এমন integer k থাকে যে n = 2k
Odd (বিজোড়): integer n বিজোড়, যদি এমন integer k থাকে যে n = 2k + 1

প্রতিটা integer হয় জোড়, নয়তো বিজোড়, দুটো একসাথে কখনো না। যেমন 6 = 2 × 3, তাই জোড়। আর 7 = 2 × 3 + 1, তাই বিজোড়।

Direct proof

p → q প্রমাণের সবচেয়ে সোজা পথ: p সত্য ধরে নিই, তারপর definition, axiom আর আগে জানা ফলাফল দিয়ে ধাপে ধাপে দেখাই q-ও সত্য।

কেন এটা যথেষ্ট? পর্ব ২-এর truth table মনে করুন: p → q false হয় শুধু তখন, যখন p true আর q false। p true ধরে q true দেখাতে পারলে সেই একমাত্র খারাপ case-টা বাদ পড়ে যায়।

উদাহরণ ১: বিজোড়ের square বিজোড়

Theorem: n বিজোড় integer হলে n²-ও বিজোড়।

Proof: ধরি n বিজোড়। Definition অনুযায়ী এমন integer k আছে যে n = 2k + 1। দুই পাশে square করি:

n² = (2k + 1)²
   = 4k² + 4k + 1
   = 2(2k² + 2k) + 1
   = 2r + 1            যেখানে r = 2k² + 2k

k integer, তাই r-ও integer। তাহলে n² = 2r + 1, মানে n² বিজোড়। ∎

(∎ চিহ্ন মানে প্রমাণ শেষ। অনেকে এর বদলে QED লেখেন।)

কৌশলটা খেয়াল করুন: definition দিয়ে শুরু (n = 2k + 1), algebra দিয়ে চেহারা বদলানো, আর শেষে আবার definition-এর আকারে আনা (2r + 1)।

উদাহরণ ২: দুটো rational সংখ্যার যোগফল rational

Definition: real number r rational, যদি এমন integer p আর q থাকে (q ≠ 0) যে r = p/q। যেমন 0.75 = 3/4।

Theorem: দুটো rational number-এর যোগফল rational।

Proof: ধরি r আর s rational। তাহলে এমন integer p, q, t, u আছে (q ≠ 0, u ≠ 0) যে r = p/q আর s = t/u। এখন:

r + s = p/q + t/u
      = (pu + qt) / qu
      = v / w            যেখানে v = pu + qt, w = qu

p, q, t, u integer, তাই v আর w-ও integer। আর q ≠ 0, u ≠ 0 বলে w = qu ≠ 0। তাই r + s rational। ∎

Vacuous আর trivial proof

p → q কিছু ক্ষেত্রে প্রায় বিনা পরিশ্রমে প্রমাণ হয়ে যায়:

Trivial proof: q যদি এমনিতেই সত্য হয়, তাহলে p → q সত্য, p যা-ই হোক। যেমন "যদি বৃষ্টি হয়, তাহলে 1 = 1"।
Vacuous proof: p যদি মিথ্যা হয়, তাহলে p → q সত্য, q যা-ই হোক। যেমন "যদি আমি একসাথে ধনী আর গরিব হই, তাহলে 2 + 2 = 5"।

দুটোই পর্ব ২-এর truth table থেকে সরাসরি আসে। উদাহরণগুলো হাস্যকর শোনালেও, mathematical induction-এ (Chapter 5) এদের সত্যিই কাজে লাগে।

Practice

প্রশ্ন ১. Direct proof দিন: m আর n দুটোই perfect square হলে mn-ও perfect square। (একটা integer a perfect square, যদি এমন integer b থাকে যে a = b²।)

Answer

ধরি m আর n perfect square। তাহলে এমন integer s আর t আছে যে m = s² আর n = t²। তাহলে:

mn = s² · t² = (st)²

s আর t integer, তাই st-ও integer। তাই mn perfect square। ∎

প্রশ্ন ২. Direct proof দিন: দুটো জোড় সংখ্যার যোগফল জোড়।

Answer

ধরি m আর n জোড়। তাহলে এমন integer j আর k আছে যে m = 2j আর n = 2k। তাহলে m + n = 2j + 2k = 2(j + k)। j + k integer, তাই m + n জোড়। ∎

প্রশ্ন ৩. "যদি n একটা integer হয় এবং n² < 0 হয়, তাহলে n = 7।" এটা কোন ধরনের proof দিয়ে প্রমাণ করা যায়, আর কেন?

Answer

Vacuous proof। কোনো integer-এর square ঋণাত্মক হয় না, তাই hypothesis n² < 0 সবসময় মিথ্যা। Hypothesis মিথ্যা হলে implication সবসময় সত্য, conclusion যা-ই হোক।

শেষ কথা

Proof হলো valid যুক্তি, যেটা দেখায় statement সব ক্ষেত্রে সত্য। Test শুধু কিছু ক্ষেত্র দেখে।
Theorem প্রমাণিত সত্য, lemma তার সাহায্যকারী, corollary তার ফলাফল, আর conjecture এখনো অপ্রমাণিত।
বেশিরভাগ theorem আসলে ∀x (P(x) → Q(x))। Arbitrary c নিয়ে P(c) → Q(c) দেখালেই হয়।
Direct proof: p ধরে নিন, definition আর algebra দিয়ে q-তে পৌঁছান।
q সবসময় সত্য হলে trivial proof, আর p সবসময় মিথ্যা হলে vacuous proof।

পরের পর্বে দেখব direct proof কাজ না করলে কী করতে হয়: contraposition, contradiction, আর একটা counterexample দিয়ে কোনো দাবি ভুল প্রমাণ করা।

More in Discrete Math