প্রমাণের পদ্ধতি — direct, contrapositive আর contradiction

১ · প্রমাণ কী — axiom, সংজ্ঞা আর আগের উপপাদ্য

বাজারঘরের ক্যাশিয়ার সারাদিন খেয়াল করলেন: যে অর্ডারের পণ্যসংখ্যা বিজোড় আর প্রতিটি পণ্যের দামও বিজোড় টাকা, তার মোট দাম সবসময় বিজোড়। পঞ্চাশটি অর্ডারে মিলেছে। এটি কি সবসময় সত্য? পঞ্চাশটি কেন, পঞ্চাশ হাজারটি মিললেও নিশ্চিত হওয়া যায় না; পর্ব ০১-এ দেখেছেন, n² + n + 41 সূত্রটি চল্লিশবার মৌলিক সংখ্যা দিয়ে একচল্লিশতম বারে ভেঙে পড়ে। নিশ্চয়তা আসে শুধু প্রমাণ থেকে। এই পর্বে প্রমাণ লেখার মূল তিনটি পদ্ধতি শিখবেন, আর প্রতিটির সঙ্গে দেখবেন প্রমাণটি খুঁজে পাওয়া যায় কীভাবে।

এই পর্বে পূর্ণসংখ্যা (integer, ℤ = {…, −2, −1, 0, 1, 2, …}) নিয়ে কাজ করব। যোগ, বিয়োগ, গুণের সাধারণ নিয়ম (বিনিময়, সংযোগ, বণ্টন) আর “দুটি পূর্ণসংখ্যার যোগফল ও গুণফল পূর্ণসংখ্যা” (এটিকে বলে closure ধর্ম) আমরা axiom হিসেবে মেনে নেব। বাকি সবকিছু সংজ্ঞা থেকে আসবে। দুটি সংজ্ঞা পুরো পর্বে বারবার লাগবে:

সংজ্ঞাগুলো খেয়াল করে পড়ুন: “জোড়” মানে “2 দিয়ে ভাগ যায়” বললেও চলে, কিন্তু প্রমাণে কাজের রূপ হলো “n = 2k, k একটি পূর্ণসংখ্যা”। প্রায় প্রতিটি প্রমাণের প্রথম ধাপ হলো সংজ্ঞাকে এই রকম সমীকরণে খুলে লেখা, আর শেষ ধাপ হলো ফলটিকে আবার সংজ্ঞার আকারে ফেরত আনা।

Informal আর formal প্রমাণ

পর্ব ০৬ “অনুমানের নিয়ম — modus ponens থেকে resolution”-এ formal proof দেখেছেন: প্রতিটি লাইনের পাশে নিয়মের নাম আর লাইন নম্বর। গণিতের বই আর পরীক্ষার খাতায় যে প্রমাণ লেখা হয়, তা informal proof: স্বাভাবিক ভাষায়, একাধিক নিয়ম একসঙ্গে প্রয়োগ করে, স্পষ্ট ধাপগুলো (যেমন “বণ্টন নিয়মে”) সবসময় না বলে। Informal মানে ঢিলেঢালা নয়। এর মানে হলো, একজন দক্ষ পাঠক চাইলে প্রতিটি ধাপকে formal proof-এ ভেঙে নিতে পারবেন। এই পর্বে মাঝামাঝি পথ নেব: প্রতিটি প্রমাণ সংখ্যাযুক্ত ধাপে, প্রতিটি ধাপের পাশে কারণ।

প্রায় সব উপপাদ্যের আকার “সব x-এর জন্য, P(x) হলে Q(x)”, অর্থাৎ ∀x (P(x) → Q(x)). পর্ব ০৬-এর universal generalization অনুযায়ী এটি প্রমাণ করতে একটি ইচ্ছামতো x নিয়ে P(x) → Q(x) দেখালেই হয়। তাই প্রমাণ শুরু হয় “ধরি n একটি ইচ্ছামতো বিজোড় পূর্ণসংখ্যা” দিয়ে, “ধরি n = 7” দিয়ে নয়। আর p → q দেখানোর তিনটি প্রধান রাস্তা আছে, নিচের ছবিতে:

২ · Direct proof — সংজ্ঞা খুলে সোজা পথে

একটি direct proof-এ p → q প্রমাণ করতে p সত্য ধরে নেওয়া হয়, তারপর সংজ্ঞা, axiom আর আগের উপপাদ্য দিয়ে এক এক ধাপে q-তে পৌঁছানো হয়। p মিথ্যা হলে p → q এমনিতেই সত্য, তাই শুধু p সত্য ক্ষেত্রটিই দেখার।

প্রমাণ খুঁজে পাওয়া: আগে খসড়া

পরিষ্কার প্রমাণ বইয়ে ছাপা হয়, কিন্তু তার আগে থাকে খসড়ার কাজ, যা কেউ দেখায় না। আমরা দেখাব। ক্যাশিয়ারের প্রশ্নের মূলে আছে জোড়-বিজোড়ের যোগ আর গুণ। প্রথমে কয়েকটি ছোট সংখ্যায় দেখি কী ঘটে, তারপর একটি দাবি বড় পরিসরে যাচাই করি, আর লোভে পড়ে একটি বেশি বড় দাবি করলে কী হয় তাও দেখি। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

def kind(n):
    return "even" if n % 2 == 0 else "odd"

# ধাপ ১: ছোট কয়েকটি জোড়া দেখে প্যাটার্ন খোঁজা
for a, b in [(2, 4), (2, 7), (3, 4), (3, 7), (5, 9), (11, 13)]:
    print(f"{a:>2}+{b:<2} = {a + b:<3} {kind(a + b):4}   "
          f"{a:>2}*{b:<2} = {a * b:<4} {kind(a * b)}")

# ধাপ ২: দাবি "n বিজোড় হলে n² বিজোড়" — বড় পরিসরে যাচাই
odds = range(1, 200_000, 2)
bad = [n for n in odds if (n * n) % 2 == 0]
print("checked", len(odds), "odd n; counterexamples:", bad)

# ধাপ ৩: আরও খুঁটিয়ে দেখলে নতুন প্যাটার্ন: n² mod 8
print("n^2 % 8 for odd n:", sorted({n * n % 8 for n in range(1, 500, 2)}))

# ধাপ ৪: লোভে পড়ে বেশি দাবি: "n বিজোড় হলে n² % 16 == 1"?
cex = next(n for n in range(1, 100, 2) if n * n % 16 != 1)
print("claim 'odd n => n^2 % 16 == 1' fails at n =", cex,
      "because", cex * cex, "% 16 =", cex * cex % 16)

 2+4  = 6   even    2*4  = 8    even
 2+7  = 9   odd     2*7  = 14   even
 3+4  = 7   odd     3*4  = 12   even
 3+7  = 10  even    3*7  = 21   odd
 5+9  = 14  even    5*9  = 45   odd
11+13 = 24  even   11*13 = 143  odd
checked 100000 odd n; counterexamples: []
n^2 % 8 for odd n: [1]
claim 'odd n => n^2 % 16 == 1' fails at n = 3 because 9 % 16 = 9

খসড়ায় একটি প্রশ্ন জিজ্ঞেস করুন: কেন 7 · 9 বিজোড়? 7 = 2·3 + 1, 9 = 2·4 + 1. গুণ করলে চারটি টুকরো: 2·3·2·4, 2·3, 2·4, আর 1·1. প্রথম তিনটিতে 2 আছে, শুধু শেষটিতে নেই। এই পর্যবেক্ষণটিই প্রমাণ, শুধু 3 আর 4-এর জায়গায় অক্ষর বসাতে হবে।

1ধরি m, n বিজোড়2m = 2k+1, n = 2l+13mn = 4kl+2k+2l+14   = 2(2kl+k+l)+15t = 2kl+k+l ∈ ℤ6mn = 2t+1, বিজোড় ∎

একই কৌশলে, m = n বসালে পাই: n বিজোড় হলে n² বিজোড়। Python-এর এক লাখ পরীক্ষা যা “সম্ভবত” বলেছিল, এই ছয় লাইন তা সব অসীম বিজোড় সংখ্যার জন্য নিশ্চিত করল। এবার মূলদ সংখ্যা নিয়ে আরেকটি direct proof, যেখানে একটি শর্ত খুব সহজে চোখ এড়ায়:

প্রমাণ:

1. ধরি r, s মূলদ। সংজ্ঞায় এমন পূর্ণসংখ্যা a, b, c, d আছে যে b ≠ 0, d ≠ 0, r = a/b, s = c/d. — মূলদের সংজ্ঞা
2. r + s = a/b + c/d = (ad + bc)/(bd). — ভগ্নাংশের যোগের নিয়ম
3. ad + bc আর bd পূর্ণসংখ্যা। — closure
4. b ≠ 0 আর d ≠ 0, তাই bd ≠ 0; দুটি অশূন্য পূর্ণসংখ্যার গুণফল শূন্য হয় না। — পূর্ণসংখ্যার ধর্ম
5. অতএব r + s = p/q আকারে লেখা গেল, যেখানে p = ad + bc, q = bd ≠ 0; সংজ্ঞায় r + s মূলদ। ∎

উদাহরণ: 3/4 + 5/6 = (3·6 + 4·5)/(4·6) = 38/24 = 19/12. ধাপ ৪ না লিখলে প্রমাণ অসম্পূর্ণ, কারণ সংজ্ঞায় হর শূন্য হওয়া নিষেধ। “মূলদ যোগ অমূলদ” বা “অমূলদ যোগ অমূলদ” সম্পর্কে কী বলা যায়? দ্বিতীয়টির কোনো নিয়ম নেই: √2 + (−√2) = 0 মূলদ, অথচ √2 + √2 অমূলদ। Counterexample দিয়ে খণ্ডনের এই কৌশল বিস্তারিত দেখবেন পর্ব ০৯ “প্রমাণের কৌশল — case, existence, uniqueness আর counterexample”-এ।

৩ · Contrapositive দিয়ে প্রমাণ — উল্টো দিক থেকে ঢোকা

এবার দাবি: n² জোড় হলে n জোড়। Direct proof চেষ্টা করি। n² = 2k ধরলাম। তাহলে n = ±√(2k). এখান থেকে n জোড় কি না বলার কোনো সরল উপায় নেই; বর্গমূল নিয়ে পূর্ণসংখ্যার কথা বলা কঠিন। রাস্তাটি বন্ধ।

পর্ব ০২-এ দেখেছেন, p → q আর তার contrapositive ¬q → ¬p সব সারিতে সমান মান দেয়। তাই একটি প্রমাণ করলেই অন্যটি প্রমাণিত। এই কৌশলের নাম proof by contrapositive. এখানে contrapositive হলো “n জোড় নয় হলে n² জোড় নয়”, অর্থাৎ “n বিজোড় হলে n² বিজোড়”। এবার শুরুতে n-এর সমীকরণ হাতে পাই, আর বর্গ করা সহজ কাজ।

1লক্ষ্য: n² জোড় → n জোড়2সমতুল্য: n বিজোড় → n² বিজোড়3ধরি n = 2k+14n² = 4k²+4k+15   = 2(2k²+2k)+16n² বিজোড়; মূল দাবি ∎

কখন contrapositive বেছে নেবেন? যখন উপসংহার q-এর অস্বীকার ¬q থেকে একটি সুবিধাজনক সমীকরণ পাওয়া যায়, অথচ p থেকে পাওয়া যায় না। বিশেষ করে যখন q দেখতে “নেতিবাচক” (“… নয়”, “… অমূলদ”) বা “অথবা” দিয়ে গড়া। বাজারঘরের একটি কুপন নিয়ম দেখুন:

প্রমাণ (contrapositive):

1. Contrapositive: “x ≥ 500 অথবা y ≥ 500” মিথ্যা হলে x + y ≥ 1000 মিথ্যা। De Morgan-এর নিয়মে (পর্ব ০৩) প্রথম অংশের অস্বীকার হলো “x < 500 এবং y < 500”. — contrapositive, De Morgan
2. ধরি x < 500 আর y < 500. — অনুমান
3. অসমতা যোগ করলে x + y < 500 + 500 = 1000. — অসমতার যোগ
4. অর্থাৎ x + y ≥ 1000 মিথ্যা; contrapositive প্রমাণিত, তাই মূল দাবিও। ∎

বাস্তব অর্থ: ১০০০ টাকার বেশি বিলে “অন্তত একটি পণ্য ৫০০ টাকা বা বেশি দামের” ধরে নিয়ে কুপন ডিজাইন করা যায়। Direct পথে “x + y ≥ 1000 থেকে x বা y বড়” দেখাতে আপনাকে আবার দুই ক্ষেত্রে ভাঙতে হতো; উল্টো দিক থেকে এক লাইনেই শেষ।

৪ · Vacuous আর trivial proof — যখন প্রমাণ প্রায় বিনা কাজে

p → q-এর truth table-এ দুটি সহজ সারি আছে: p মিথ্যা হলে বাক্যটি সত্য, q যা-ই হোক; আর q সত্য হলে বাক্যটি সত্য, p যা-ই হোক। এই দুটি থেকে দুটি ছোট পদ্ধতি আসে।

উদাহরণ (vacuous): P(n): “n > 1 হলে n² > n”. দাবি: P(0) সত্য। প্রমাণ: 0 > 1 মিথ্যা, তাই শর্তসাপেক্ষ বাক্যটি ফাঁকাভাবে সত্য। ∎ (n² = 0 > 0 মিথ্যা হওয়ায় কিছু আসে-যায় না।) বাজারঘরের ভাষায়: “যে অর্ডারে পণ্যের সংখ্যা ঋণাত্মক, সেই অর্ডার ফ্রি ডেলিভারি পায়” বাক্যটি সত্য, কারণ এমন অর্ডার নেই। প্রোগ্রামেও একই নিয়ম: Python-এ all([]) ফেরত দেয় True, কারণ “তালিকার প্রতিটি উপাদান শর্ত মানে” দাবি ভাঙার মতো কোনো উপাদান নেই।

উদাহরণ (trivial): P(n): “a আর b ধনাত্মক পূর্ণসংখ্যা, a ≥ b হলে aⁿ ≥ bⁿ”. দাবি: P(0) সত্য। প্রমাণ: a⁰ = 1 = b⁰, তাই a⁰ ≥ b⁰ সবসময় সত্য, শর্ত a ≥ b ব্যবহার না করেই। ∎

এগুলো খেলনা মনে হলেও দুই জায়গায় খুব কাজের। এক, পর্ব ১০ “Mathematical induction — এক ধাপ থেকে অসীম পর্যন্ত”-এ প্রায়ই basis ক্ষেত্রটি vacuous বা trivial হয়, আর সেটি স্পষ্ট লিখতে হয়। দুই, প্রোগ্রামের specification-এ ফাঁকা তালিকা বা শূন্য ইনপুটের “প্রান্তিক ক্ষেত্র” প্রায়ই ফাঁকাভাবে সত্য, আর পরীক্ষকেরা ঠিক এটিই জিজ্ঞেস করেন: “ফাঁকা অর্ডার তালিকার প্রতিটি অর্ডার পরিশোধিত কি?” উত্তর হ্যাঁ।

৫ · Contradiction দিয়ে প্রমাণ — √2 কেন ভগ্নাংশ নয়

Proof by contradiction (বিরোধের মাধ্যমে প্রমাণ; লাতিন নাম reductio ad absurdum) এভাবে চলে: একটি বাক্য p প্রমাণ করতে ধরে নিন ¬p সত্য। তারপর যুক্তি চালিয়ে এমন একটি বাক্য r বের করুন, যার সঙ্গে ¬r-ও সত্য হয়: অর্থাৎ r ∧ ¬r, একটি contradiction (সবসময় মিথ্যা বাক্য)। মিথ্যা কিছু বেরিয়েছে মানে অনুমানটিই মিথ্যা: ¬p মিথ্যা, তাই p সত্য। Logic-এর ভাষায় (¬p → (r ∧ ¬r)) → p একটি tautology. Conditional p → q-এর জন্য ধরে নিতে হয় p ∧ ¬q, কারণ ¬(p → q) ≡ p ∧ ¬q.

সবচেয়ে বিখ্যাত উদাহরণ: √2 অমূলদ। আগে একটি সহায়ক তথ্য, যা প্রমাণে লাগবে: প্রতিটি মূলদ সংখ্যাকে লঘিষ্ঠ আকারে (lowest terms) লেখা যায়, অর্থাৎ a/b আকারে যেখানে a আর b-এর 1 ছাড়া কোনো সাধারণ ধনাত্মক উৎপাদক নেই। (যেকোনো p/q-এর লব আর হরকে তাদের গরিষ্ঠ সাধারণ গুণনীয়ক দিয়ে ভাগ করলেই হয়; GCD-র বিস্তারিত পর্ব ২১ “GCD আর Euclid-এর algorithm”-এ।)

1ধরি √2 = a/b, লঘিষ্ঠ2a² = 2b²3a² জোড় ⟹ a জোড়4a = 2c ⟹ b² = 2c²5b² জোড় ⟹ b জোড়62 ∣ a আর 2 ∣ b: বিরোধ7√2 অমূলদ ∎

এই প্রমাণ কেন অসীম অনুসন্ধানের চেয়ে শক্তিশালী, তা দেখতে একবার খুঁজে দেখা যাক: q = 1 থেকে 10000 পর্যন্ত প্রতিটি হরের জন্য এমন লব p আছে কি, যাতে p² = 2q²? সঙ্গে দেখব কোন ভগ্নাংশগুলো “প্রায়” মিলে যায়।

from math import isqrt

# √2 = p/q হলে p² = 2q². q = 1 … 10000 পর্যন্ত খুঁজি
found, near = [], []
for q in range(1, 10_001):
    p = isqrt(2 * q * q)          # p² ≤ 2q² এমন সবচেয়ে বড় p
    for c in (p, p + 1):
        d = c * c - 2 * q * q
        if d == 0:
            found.append((c, q))
        elif abs(d) == 1:
            near.append((c, q, d))

print("exact p/q with p^2 = 2q^2:", found)
print("near misses, p^2 - 2q^2 = ±1:")
for c, q, d in near:
    print(f"  {c}/{q}  diff {d:+d}  value {c / q:.10f}")
print("sqrt(2) as float:      ", f"{2 ** 0.5:.10f}")

exact p/q with p^2 = 2q^2: []
near misses, p^2 - 2q^2 = ±1:
  1/1  diff -1  value 1.0000000000
  3/2  diff +1  value 1.5000000000
  7/5  diff -1  value 1.4000000000
  17/12  diff +1  value 1.4166666667
  41/29  diff -1  value 1.4137931034
  99/70  diff +1  value 1.4142857143
  239/169  diff -1  value 1.4142011834
  577/408  diff +1  value 1.4142156863
  1393/985  diff -1  value 1.4142131980
  3363/2378  diff +1  value 1.4142136249
  8119/5741  diff -1  value 1.4142135516
sqrt(2) as float:       1.4142135624

৬ · মৌলিক সংখ্যা অসীম — Euclid-এর প্রমাণ আর একটি প্রচলিত ভুল

একটি মৌলিক সংখ্যা (prime) হলো 1-এর চেয়ে বড় এমন পূর্ণসংখ্যা, যার ধনাত্মক ভাজক শুধু 1 আর সে নিজে। বাজারঘর অর্ডার আইডির hashing-এ মৌলিক সংখ্যা ব্যবহার করে (পর্ব ২৬-এ দেখবেন), আর প্রকৌশলীর প্রশ্ন: যত বড় চাই, তত বড় মৌলিক কি সবসময় পাওয়া যাবে? প্রমাণে একটি তথ্য লাগবে, যা আগে প্রমাণিত ধরে নিচ্ছি:

প্রমাণ (contradiction):

1. ধরি মৌলিক সংখ্যা সসীম, আর তাদের সম্পূর্ণ তালিকা p₁, p₂, …, p_n. — অনুমান (দাবির অস্বীকার)
2. Q = p₁p₂⋯p_n + 1 লিখি। Q একটি পূর্ণসংখ্যা, আর Q ≥ 2 + 1 > 1. — closure; তালিকায় অন্তত 2 আছে
3. Lemma ৬.১ অনুযায়ী Q-এর একটি মৌলিক ভাজক p আছে। — lemma
4. তালিকাটি সম্পূর্ণ, তাই p তালিকার কোনো একটি p_i; ফলে p ∣ p₁p₂⋯p_n. — ধাপ ১
5. p ∣ Q আর p ∣ p₁⋯p_n, তাই p তাদের পার্থক্যকেও ভাগ করে: p ∣ Q − p₁⋯p_n = 1. — a ∣ x আর a ∣ y হলে a ∣ x − y
6. কিন্তু কোনো মৌলিক সংখ্যা 1-কে ভাগ করে না, কারণ p ≥ 2. এটি বিরোধ। — মৌলিকের সংজ্ঞা
7. অতএব অনুমান মিথ্যা; মৌলিক সংখ্যা অসীম। ∎

যাচাই করে দেখা যাক, প্রথম আটটি মৌলিকের ক্ষেত্রে Q কেমন:

from math import prod

def factor(n):
    # ছোট থেকে বড় ভাজক দিয়ে ভাগ করে মৌলিক উৎপাদক
    f, d = [], 2
    while d * d <= n:
        while n % d == 0:
            f.append(d)
            n //= d
        d += 1
    return f + [n] if n > 1 else f

primes = [2, 3, 5, 7, 11, 13, 17, 19]
for k in range(1, len(primes) + 1):
    P = primes[:k]
    Q = prod(P) + 1
    fs = factor(Q)
    tag = "prime" if len(fs) == 1 else " x ".join(map(str, fs))
    fresh = all(p not in P for p in fs)
    print(f"up to {P[-1]:>2}: Q = {Q:<8} {tag:<14} new? {fresh}")

print("check:", 2 * 3 * 5 * 7 * 11 * 13 + 1, "=", 59 * 509)

up to  2: Q = 3        prime          new? True
up to  3: Q = 7        prime          new? True
up to  5: Q = 31       prime          new? True
up to  7: Q = 211      prime          new? True
up to 11: Q = 2311     prime          new? True
up to 13: Q = 30031    59 x 509       new? True
up to 17: Q = 510511   19 x 97 x 277  new? True
up to 19: Q = 9699691  347 x 27953    new? True
check: 30031 = 30031

৭ · “যদি এবং কেবল যদি” — দুই দিকের প্রমাণ

অনেক উপপাদ্যের আকার p ↔ q (if and only if, সংক্ষেপে iff, বাংলায় “যদি এবং কেবল যদি”)। পর্ব ০২-এর biconditional থেকে জানেন, p ↔ q ≡ (p → q) ∧ (q → p). তাই প্রমাণ দুই অংশে: (⇒) p ধরে q, আর (⇐) q ধরে p. দুই অংশে আলাদা পদ্ধতিও ব্যবহার করা যায়।

প্রমাণ:

1. (⇒) n বিজোড় হলে n² বিজোড়: উপপাদ্য ২.১-এ m = n বসিয়ে (direct proof).
2. (⇐) n² বিজোড় হলে n বিজোড়: contrapositive হলো “n জোড় হলে n² জোড়”। ধরি n = 2k; তাহলে n² = 4k² = 2(2k²), আর 2k² ∈ ℤ, তাই n² জোড়।
3. দুই দিক প্রমাণিত, তাই biconditional প্রমাণিত। ∎

কয়েকটি বাক্য সমতুল্য — চক্র দিয়ে প্রমাণ

কখনো দাবি হয় “নিচের বাক্যগুলো সমতুল্য”: p₁ ↔ p₂ ↔ … ↔ p_k. প্রতিটি জোড়ার দুই দিক আলাদা প্রমাণ করলে অনেক কাজ (k = 3-এ ছয়টি conditional). চতুর উপায়: একটি চক্র p₁ → p₂ → p₃ → p₁ প্রমাণ করুন। Hypothetical syllogism-এর শিকলে (পর্ব ০৬) যেকোনো p_i থেকে যেকোনো p_j-তে পৌঁছানো যায়।

প্রমাণ (চক্র):

1. p₁ → p₂: n = 2k হলে n − 1 = 2k − 1 = 2(k − 1) + 1, আর k − 1 ∈ ℤ; তাই n − 1 বিজোড়। — direct
2. p₂ → p₃: n − 1 = 2k + 1 হলে n = 2k + 2 = 2(k + 1), আর n² = 4(k + 1)² = 2 · 2(k + 1)²; তাই n² জোড়। — direct
3. p₃ → p₁: উপপাদ্য ৩.১। — আগে প্রমাণিত (contrapositive দিয়ে)
4. চক্র সম্পূর্ণ, তাই তিনটি বাক্য পরস্পর সমতুল্য। ∎

৮ · প্রমাণের সাধারণ ভুল — ভুল ধরা শেখা

ভালো প্রমাণ লেখার সমান গুরুত্বপূর্ণ ভুল প্রমাণ চেনা: নিজের খাতায়, বইয়ে, আর এখন AI-এর উত্তরে। চারটি ভুল সবচেয়ে বেশি দেখা যায়।

ভুল ১: উপসংহার ধরে নিয়ে শুরু করা

দাবি: প্রতিটি বাস্তব x-এর জন্য x² + 1 ≥ 2x. একজন লিখলেন: “x² + 1 ≥ 2x ⟹ x² − 2x + 1 ≥ 0 ⟹ (x − 1)² ≥ 0, যা সত্য। ∎” এখানে যা প্রমাণ করার কথা, সেখান থেকে শুরু করে একটি সত্য বাক্যে পৌঁছানো হয়েছে। এটি দেখায় শুধু “দাবি → সত্য বাক্য”, যা দাবি মিথ্যা হলেও ঘটতে পারে: “−1 = 1” থেকে দুই দিক বর্গ করে “1 = 1” পাওয়া যায়, অথচ −1 = 1 মিথ্যা। এই ভুলের নাম begging the question বা circular reasoning, অথবা উল্টো দিকে লেখা।

সংশোধন: খসড়ায় উল্টো দিকে ভাবা ঠিক আছে, কিন্তু চূড়ান্ত প্রমাণ সামনে লিখুন: “যেকোনো বাস্তব সংখ্যার বর্গ অঋণাত্মক, তাই (x − 1)² ≥ 0. বিস্তার করে x² − 2x + 1 ≥ 0. দুই দিকে 2x যোগ করে x² + 1 ≥ 2x. ∎” এখানে প্রতিটি ধাপ উল্টানো যায় বলেই সংশোধন সম্ভব হলো; বর্গ করার মতো এক-দিকের ধাপ থাকলে হতো না।

ভুল ২: Converse প্রমাণ করা

দাবি “n² বিজোড় হলে n বিজোড়”-এর প্রমাণে কেউ লিখলেন “ধরি n = 2k + 1; n² = 2(2k² + 2k) + 1 বিজোড়। ∎” এটি প্রমাণ করেছে “n বিজোড় হলে n² বিজোড়”, অর্থাৎ converse. এই ক্ষেত্রে converse-টিও সত্য বলে ভুলটি চোখে পড়ে না, কিন্তু “a² = b² হলে a = b” ধরনের দাবিতে converse সত্য (a = b হলে a² = b²) অথচ মূল দাবি মিথ্যা।

ভুল ৩: উদাহরণ থেকে সাধারণ দাবি

কয়েকটি উদাহরণ একটি “সব”-দাবি প্রমাণ করে না, কিন্তু একটি counterexample তা খণ্ডন করে। নিচের ব্লক কয়েকটি বিশ্বাসযোগ্য দাবির প্রথম counterexample খোঁজে:

from itertools import product

def is_prime(n):
    return n > 1 and all(n % d for d in range(2, int(n ** 0.5) + 1))

def first_cex(name, claim, domain):
    # domain-এর প্রথম যে মানে দাবি ভাঙে, সেটি ছাপি
    for x in domain:
        if not claim(*x):
            print(f"{name:26} FALSE at {x}")
            return
    print(f"{name:26} no counterexample here")

ones = [(n,) for n in range(1, 300)]
pairs = list(product(range(-5, 6), repeat=2))

first_cex("p prime => 2^p-1 prime",
          lambda p: not is_prime(p) or is_prime(2 ** p - 1), ones)
first_cex("n^2+n+1 is prime",
          lambda n: is_prime(n * n + n + 1), ones)
first_cex("a^2 = b^2 => a = b",
          lambda a, b: a * a != b * b or a == b, pairs)
first_cex("a^2 > b^2 => a > b",
          lambda a, b: a * a <= b * b or a > b, pairs)
first_cex("n odd => n^2 odd",
          lambda n: n % 2 == 0 or n * n % 2 == 1, ones)
print("2^11 - 1 =", 2 ** 11 - 1, "=", 23 * 89)

p prime => 2^p-1 prime     FALSE at (11,)
n^2+n+1 is prime           FALSE at (4,)
a^2 = b^2 => a = b         FALSE at (-5, 5)
a^2 > b^2 => a > b         FALSE at (-5, -4)
n odd => n^2 odd           no counterexample here
2^11 - 1 = 2047 = 2047

ভুল ৪: লুকানো শূন্য দিয়ে ভাগ — প্রমাণের ভুল ধরুন

নিচের “প্রমাণ” দেখায় 2 = 1. প্রতিটি ধাপ পড়ে ভুলটি নিজে খুঁজুন, তারপর নিচের ব্যাখ্যা পড়ুন।

1. ধরি a = b, আর a, b ধনাত্মক।
2. দুই দিকে a দিয়ে গুণ: a² = ab.
3. দুই দিক থেকে b² বিয়োগ: a² − b² = ab − b².
4. উৎপাদকে ভাঙা: (a + b)(a − b) = b(a − b).
5. দুই দিক (a − b) দিয়ে ভাগ: a + b = b.
6. a = b বসিয়ে: 2b = b, তাই 2 = 1.

ভুল কোথায়: ধাপ ৫. a = b, তাই a − b = 0, আর শূন্য দিয়ে ভাগ সংজ্ঞায়িত নয়। ধাপ ৪ পর্যন্ত সব সমীকরণ সত্য (দুই দিকই 0). শিক্ষা: কোনো রাশি দিয়ে ভাগ করার আগে লিখুন “এটি শূন্য নয় কারণ …”, ঠিক যেমন উপপাদ্য ২.২-এর ধাপ ৪-এ bd ≠ 0 লিখেছিলাম।

৯ · AI-এর যুগে — AI-এর লেখা প্রমাণ কীভাবে যাচাই করবেন

AI সহকারী আত্মবিশ্বাসী ভাষায়, সুন্দর বিন্যাসে প্রমাণ লেখে। কিন্তু এই পর্বের প্রতিটি ভুল সে-ও করে, আর প্রায়ই এমনভাবে যে প্রথমবার পড়ার সময় চোখে পড়ে না। যে ভুলগুলো বেশি দেখা যায়:

AI-এর প্রমাণ হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রথম লাইনের অনুমান পদ্ধতির সঙ্গে মেলে: direct-এ p, contrapositive-এ ¬q, contradiction-এ দাবির অস্বীকার
• শেষ লাইন হুবহু দাবিটি, তার converse বা দুর্বল রূপ নয়; iff হলে দুই দিকই আছে
• প্রতিটি ধাপের কারণ আছে, আর “k পূর্ণসংখ্যা”, “≠ 0” ধরনের ধাপ বাদ পড়েনি
• উল্লেখ করা প্রতিটি উপপাদ্যের শর্ত এখানে পূরণ হয়েছে
• Python-এ ছোট ক্ষেত্রগুলো পরীক্ষা করেছি, এলোমেলো ইনপুটেও চালিয়েছি, counterexample খুঁজেছি
• বইয়ের নাম বা ঐতিহাসিক দাবি একটি বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

মনে রাখুন, Python-এর পরীক্ষা প্রমাণ নয়, কিন্তু ভুল প্রমাণ ধরার সবচেয়ে সস্তা উপায়: একটি counterexample পেলেই পুরো “প্রমাণ” বাতিল। অ্যালগরিদমের সঠিকতা প্রমাণে এই পদ্ধতিগুলো কীভাবে লাগে, তা DSA কোর্সের পর্ব ৩-এ আছে; আর টেস্ট কেন বাগের উপস্থিতি দেখায় কিন্তু অনুপস্থিতি প্রমাণ করে না, তা সফটওয়্যার ইঞ্জিনিয়ারিং ও Git কোর্সের পর্ব ৪৫-এ।