Mathematical Proofs (Induction and Contradiction) | गणितीय प्रमेय (आगमन और विरोधाभास द्वारा प्रमाण)

कंप्यूटर विज्ञान और ऑटोमाटा सिद्धांत में गणितीय प्रमाणों (Mathematical Proofs) की विशेष भूमिका होती है। किसी भी एल्गोरिदम, ऑटोमाटा मॉडल या गणनात्मक गुण (Computational Property) को सत्यापित करने के लिए प्रमाण आवश्यक होते हैं। इस ब्लॉग में हम दो प्रमुख प्रमाण तकनीकों — Mathematical Induction और Proof by Contradiction — का अध्ययन करेंगे।

परिचय / Introduction

गणितीय प्रमाण एक तार्किक प्रक्रिया है जिसके माध्यम से किसी कथन या प्रमेय को सत्य सिद्ध किया जाता है। कंप्यूटर विज्ञान में इनका उपयोग Algorithms की सत्यता, Functions के गुण और Automata के व्यवहार को सिद्ध करने के लिए किया जाता है।

1️⃣ Mathematical Induction (गणितीय आगमन)

Mathematical Induction एक ऐसी तकनीक है जिसका उपयोग “n” पर आधारित कथनों को सिद्ध करने के लिए किया जाता है, जहाँ n प्राकृतिक संख्याओं का सदस्य होता है।

आगमन की प्रक्रिया / Steps of Induction

1. Base Case: n = 1 के लिए कथन सत्य है यह दिखाएँ।
2. Inductive Hypothesis: मान लें कि n = k के लिए कथन सत्य है।
3. Inductive Step: यह सिद्ध करें कि n = k + 1 के लिए भी कथन सत्य होगा।

उदाहरण / Example

Statement: सिद्ध करें कि 1 + 2 + 3 + … + n = n(n + 1)/2

Proof:

• Base Case: n = 1 ⇒ LHS = 1, RHS = 1(1 + 1)/2 = 1 ⇒ सत्य ✅
• Inductive Hypothesis: मान लें कि n = k के लिए LHS = k(k + 1)/2 सत्य है।
• Inductive Step: n = k + 1 के लिए LHS = [k(k + 1)/2] + (k + 1)
• ⇒ (k + 1)(k + 2)/2 ⇒ सत्य ✅

अतः कथन सभी n ∈ N के लिए सत्य है।

2️⃣ Proof by Contradiction (विरोधाभास द्वारा प्रमाण)

इस तकनीक में हम जिस कथन को सिद्ध करना चाहते हैं उसका उल्टा मान लेते हैं और यह दिखाते हैं कि यह मान्यता असत्य है।

प्रक्रिया / Steps of Proof by Contradiction

1. मान लें कि कथन असत्य है।
2. उससे एक तार्किक विरोधाभास उत्पन्न करें।
3. विरोधाभास से निष्कर्ष निकालें कि मूल कथन सत्य है।

उदाहरण / Example

Statement: सिद्ध करें कि √2 एक अपरिमेय संख्या है।

Proof:

• मान लें कि √2 परिमेय है। तब √2 = p/q, जहाँ p और q पूर्णांक हैं तथा gcd(p, q) = 1।
• दोनों पक्षों का वर्ग लें: 2 = p²/q² ⇒ p² = 2q²
• इससे स्पष्ट है कि p² सम संख्या है ⇒ p भी सम होगा ⇒ p = 2r
• ⇒ (2r)² = 2q² ⇒ q² = 2r² ⇒ q भी सम है।
• लेकिन यदि p और q दोनों सम हैं तो gcd(p, q) ≠ 1 ⇒ विरोधाभास ❌

अतः √2 अपरिमेय है ✅

3️⃣ Proofs in Automata Theory

ऑटोमाटा सिद्धांत में इन प्रमाणों का उपयोग किया जाता है:

• Regular Languages की Properties सिद्ध करने में।
• Finite Automata के Closure Properties जैसे Union, Intersection, Complement पर।
• Recursive और Non-Recursive Problems को साबित करने में।

तुलना / Comparison Table

Proof Type	Approach	Use Case
Mathematical Induction	Sequential logical steps	Statements over natural numbers
Proof by Contradiction	Assume opposite and derive contradiction	Existence or impossibility proofs

निष्कर्ष / Conclusion

गणितीय आगमन और विरोधाभास दोनों प्रमाण तकनीकें कंप्यूटर विज्ञान में तार्किक तर्क (Logical Reasoning) को सशक्त बनाती हैं। ये ऑटोमाटा सिद्धांत में औपचारिक मॉडल की वैधता को सिद्ध करने के लिए आवश्यक उपकरण हैं।