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

Base Case: n = 1 के लिए कथन सत्य है यह दिखाएँ।
Inductive Hypothesis: मान लें कि n = k के लिए कथन सत्य है।
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

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

उदाहरण / 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) को सशक्त बनाती हैं। ये ऑटोमाटा सिद्धांत में औपचारिक मॉडल की वैधता को सिद्ध करने के लिए आवश्यक उपकरण हैं।

Mathematical Proofs (Induction and Contradiction)

Mathematical proofs form the foundation of logic in computer science. They establish the correctness of algorithms, automata, and computational models. This blog explains two essential proof techniques — Mathematical Induction and Proof by Contradiction.

1️⃣ Mathematical Induction

Used for statements dependent on natural numbers.

Steps:

Base Case: Verify for n = 1.
Inductive Hypothesis: Assume true for n = k.
Inductive Step: Prove true for n = k + 1.

Example

Prove 1 + 2 + 3 + … + n = n(n + 1)/2

✅ Holds true for all n ∈ N.

2️⃣ Proof by Contradiction

Assume the opposite of what you want to prove and show a logical contradiction.

Example

Prove that √2 is irrational.

Assume √2 = p/q, where p, q are integers and gcd(p, q) = 1.
2 = p²/q² ⇒ p² = 2q² ⇒ both p and q are even ⇒ contradiction.

Hence, √2 is irrational ✅

Applications in Automata Theory

Proving closure properties of regular languages.
Verifying equivalence of automata.
Demonstrating undecidable problems.

Comparison Table

Proof Type	Method	Application
Induction	Stepwise verification	Sequences and recursive definitions
Contradiction	Logical negation and disproof	Existence proofs and impossibility

Conclusion

Both proof methods — induction and contradiction — are indispensable tools in theoretical computer science. They build rigorous reasoning required for Automata, Algorithms, and Computation Theory.

Church’s Thesis and Complexity Theory (P vs NP) | चर्च का सिद्धांत और जटिलता सिद्धांत (P बनाम NP समस्याएँ)

Church’s Thesis and Complexity Theory (P vs NP) | चर्च का सिद्...

Solvability and Unsolvability Concepts | हल करने योग्य और अ-हल करने योग्य समस्याएँ

Solvability and Unsolvability Concepts | हल करने योग्य और ...

Halting Problem and Post Correspondence Problem | हॉल्टिंग समस्या और पोस्ट पत्राचार समस्या

Halting Problem and Post Correspondence Problem | हॉल्टिंग समस...

Unrestricted Grammars and Type-0 Languages | असीमित व्याकरण और टाइप-0 भाषाएँ

Unrestricted Grammars and Type-0 Languages | असीमित व्याकर�...

Recursive and Recursively Enumerable Languages | पुनरावर्ती और पुनरावर्ती रूप से गणनीय भाषाएँ

Recursive and Recursively Enumerable Languages | पुनरावर्ती औ�...

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