फॉर्मल वेरिफिकेशन क्या है
फॉर्मल वेरिफिकेशन का मतलब है गणितीय प्रमाण के ज़रिए यह दिखाना कि एक प्रोग्राम सभी इनपुट के लिए आवश्यकताएँ पूरी करता है, और कंप्यूटर से उस प्रमाण के हर कदम की जाँच करवाना। इसमें टेस्टिंग से सिर्फ एक फर्क है: टेस्टिंग उन इनपुट की जाँच करती है जो आपने आज़माए, प्रमाण सबको कवर करता है।
यह सेक्शन सीढ़ियाँ बनाकर शुरू होता है, और इस वाक्य को ठोस रूप देता है। कुछ भी इंस्टॉल करने की ज़रूरत नहीं।
सीखने के बाद आप क्या कर सकेंगे
- बता सकें कि टेस्टिंग और प्रमाण अपने-अपने तौर पर क्या गारंटी देते हैं
- समझ सकें कि एक Lean प्रमेय क्या कह रहा है
- जान सकें कि "Lean की जाँच पास होना" किसका मतलब है और किसका नहीं
पहले एक सीढ़ी बनाएँ
ईंटों से सीढ़ियाँ बनाएँ: पहली सीढ़ी में 1 ईंट, दूसरी में 2, तीसरी में 3। n सीढ़ियाँ बनाने में कुल कितनी ईंटें लगेंगी?
एक-एक करके गिनना (टेस्ट)
1 + 2 + … + 4 = 10
n=4 ✓
आपने कभी आज़माया है 1 n। स्लाइडर घुमाकर कुछ और आज़माएँ। लेकिन n अनंत हैं, कभी आज़माकर खत्म नहीं होंगे।
जोड़कर देखें (प्रमाण)
फिर एक बिल्कुल वैसी ही सीढ़ियाँ लें और उलट दें।
आपने दो अलग-अलग काम किए:
- स्लाइडर खींचकर ईंटें गिनना: हर बार सिर्फ एक n का जवाब पता चलता है। कितना भी आज़माएँ, बस इतना ही पता चलता है कि "ये कुछ n ठीक हैं"।
- आयत में जोड़ना: एक ही बार में सभी n दिख गए। सीढ़ियाँ चाहे कितनी भी हों, दोनों हिस्से मिलकर ठीक n पंक्तियाँ और n + 1 कॉलम बनाते हैं, इसलिए दोनों सीढ़ियों में कुल n × (n + 1) ईंटें होती हैं।
पहला तरीका टेस्टिंग है, दूसरा प्रमाण।
- मैंने स्लाइडर खींचा और आयत भी बनाया
सीढ़ी को प्रोग्राम के रूप में लिखें
ईंटें गिनने का काम, Lean के फंक्शन में ऐसे लिखा जाता है। ब्योरे समझ न आएँ तो कोई बात नहीं, यह बस यही कह रहा है कि "n सीढ़ियों की ईंटें = पहली n − 1 सीढ़ियों की ईंटें + nवीं सीढ़ी की n ईंटें":
def sumTo : Nat → Nat
| 0 => 0
| n + 1 => sumTo n + (n + 1)एक फंक्शन, दो तरह की जाँच
टेस्टिंग का तरीका: एक संख्या चुनें, निकाल कर देखें।
#eval sumTo 100आपको यह दिखना चाहिए:
5050100 × 101 ÷ 2 भी 5050 आता है, मिल गया। लेकिन इससे सिर्फ इतना पता चलता है कि n = 100 पर यह सही है। n = 101 पर क्या? n = दस करोड़ पर क्या? आप कुछ और टेस्ट कर सकते हैं, लेकिन कभी पूरा नहीं कर पाएँगे।
प्रमाण का तरीका: अभी आयत बनाकर जो निष्कर्ष मिला, उसे सभी n के लिए सही एक वाक्य के रूप में लिखें, और फिर उसे सिद्ध करें।
theorem sumTo_formula (n : Nat) : 2 * sumTo n = n * (n + 1) := by
induction n with
| zero =>
rfl
| succ k ih =>
simp [sumTo]
rw [Nat.mul_add, ih]
simp [Nat.mul_add, Nat.add_mul]
omegaअभी by के बाद का हिस्सा समझ न आए तो कोई बात नहीं, वह आगे के सेक्शनों की बात है। सिर्फ पहली पंक्ति देखें:
theorem sumTo_formula: एक प्रमेय, जिसका नामsumTo_formulaहै।(n : Nat): किसी भी प्राकृतिक संख्या n के लिए।2 * sumTo n = n * (n + 1): दोनों सीढ़ियों की ईंटों की संख्या, n × (n + 1) के बराबर है। वही आयत जो आपने बनाया था।
Lean ने इस प्रमाण की जाँच पास कर दी। अब से यह वाक्य हर प्राकृतिक संख्या के लिए सही है, दोबारा टेस्ट करने की ज़रूरत नहीं।
- मैं बता सकता हूँ कि
#eval sumTo 100औरtheorem sumTo_formulaअपने-अपने तौर पर क्या गारंटी देते हैं
गलत लिखा तो क्या होगा
मान लीजिए आपने सूत्र गलत याद किया और सोचा कि 1 को n तक जोड़ने पर n × n आता है:
theorem wrong_formula (n : Nat) : sumTo n = n * n := by
induction n with
| zero => rfl
| succ k ih => simp [sumTo, ih]; omegaLean इसे स्वीकार नहीं करता। इसका उत्तर इस वाक्य से शुरू होता है:
omega could not prove the goal:आप "लगभग सही दिखता है" के भरोसे बच नहीं सकते। एक गलत प्रस्ताव को कैसे भी लिखो, सिद्ध नहीं किया जा सकता। यही औपचारिक सत्यापन (formal verification) पर भरोसा करने का कारण है: प्रमाण की जाँच करने वाला एक प्रोग्राम है, इंसान का धैर्य नहीं।
आपकी परीक्षाआपने एक सॉर्टिंग फ़ंक्शन के लिए 200 टेस्ट लिखे, सभी पास हुए। इसका क्या मतलब है?
यह क्या गारंटी नहीं देता
Lean यह गारंटी देता है: जो वाक्य आपने लिखा है, वह सिद्ध हो गया है। यह गारंटी नहीं देता कि आपने जो वाक्य लिखा है वही वास्तव में आपकी मंशा थी।
ऊपर दिया गया प्रमेय कहता है कि "sumTo n का दोगुना n × (n + 1) के बराबर है"। अगर आप वास्तव में कोई और गुणधर्म चाहते थे, पर यही वाक्य लिख दिया, तो Lean आपकी मदद नहीं कर सकता। इसलिए प्रमेय की पहली पंक्ति को समझना, प्रमाण को समझने से ज़्यादा ज़रूरी है। प्रमाण की जाँच Lean करेगा, प्रस्ताव आपको खुद पढ़ना होगा।
- मैं जानता/जानती हूँ कि "प्रमाण पास होना" गारंटी देता है कि प्रस्ताव सही है, यह नहीं कि प्रस्ताव आवश्यकता के अनुसार सही लिखा गया है
चेकपॉइंट
- मैं एक वाक्य में औपचारिक सत्यापन समझा सकता/सकती हूँ: प्रमाण से बताना कि प्रोग्राम सभी इनपुट के लिए सही है, और प्रमाण की जाँच कंप्यूटर से कराना
- मैं परीक्षण (testing) और प्रमाण का अंतर बता सकता/सकती हूँ: आज़माए गए इनपुट, सभी इनपुट
- मैं
theorem 名字 (n : Nat) : 命题के हर हिस्से का अर्थ पढ़ सकता/सकती हूँ - मैं जानता/जानती हूँ कि एक गलत प्रस्ताव Lean में सिद्ध नहीं हो सकता
आम भ्रांतियाँ
"औपचारिक सत्यापन बस और ज़्यादा परीक्षण है।" नहीं। परीक्षण में प्रोग्राम चलाकर परिणाम देखा जाता है; प्रमाण प्रोग्राम नहीं चलाता, वह परिभाषाओं से तर्क करता है और एक ही बार में सभी स्थितियों को कवर करता है।
"प्रमाण पास हो गया, तो प्रोग्राम में कोई भी समस्या नहीं है।" प्रमाण केवल उस वाक्य की बात करता है जो आपने लिखा है। जो गुणधर्म प्रस्ताव में नहीं लिखा गया, वह गारंटी के दायरे में नहीं आता।
आम प्रश्न
औपचारिक सत्यापन का क्या अर्थ है?
औपचारिक सत्यापन का अर्थ है, गणितीय प्रमाण से यह दिखाना कि एक प्रोग्राम सभी इनपुट के लिए आवश्यकता पूरी करता है, और उस प्रमाण के हर कदम की जाँच कंप्यूटर से कराना। इसका परीक्षण से केवल एक अंतर है: परीक्षण उन इनपुट की जाँच करता है जो आपने आज़माए, प्रमाण सभी को कवर करता है। इस पृष्ठ की शुरुआत की परिभाषा और "पहले एक सीढ़ी बनाएँ" अनुभाग ने ईंट के उदाहरण से यह समझाया है।
Lean 4 का क्या अर्थ है?
Lean 4 प्रोग्राम और प्रमाण लिखने का एक उपकरण है। इस पृष्ठ पर आपने इससे फ़ंक्शन sumTo परिभाषित किया, और theorem से सभी प्राकृतिक संख्याओं के लिए सही प्रस्ताव लिखा, जिसके प्रमाण के हर कदम की जाँच Lean ने की। प्रमाण की जाँच करने वाला एक प्रोग्राम है, इंसान का धैर्य नहीं।
औपचारिक सत्यापन कैसे लिखें?
पहले जिस गुणधर्म को दिखाना है उसे सभी इनपुट के लिए सही एक प्रस्ताव के रूप में लिखें, जैसे theorem sumTo_formula (n : Nat) : 2 * sumTo n = n * (n + 1), फिर प्रमाण देकर कंप्यूटर से उसकी जाँच कराएँ। इस पृष्ठ के प्रमाण में आगमन (induction) का उपयोग हुआ है; विवरण आगे के अनुभागों में विस्तार से आएगा।
प्रमाण पास हो गया, तो क्या प्रोग्राम में कोई भी समस्या नहीं रहती?
नहीं। Lean यह गारंटी देता है कि आपने जो वाक्य लिखा है वह सिद्ध हो गया, यह नहीं कि वही वाक्य आपकी वास्तविक मंशा थी। जो गुणधर्म प्रस्ताव में नहीं लिखा गया, वह गारंटी के दायरे में नहीं आता; इसलिए प्रमेय की पहली पंक्ति को समझना प्रमाण को समझने से ज़्यादा ज़रूरी है, देखें "यह क्या गारंटी नहीं देता" अनुभाग।
अगला अनुभाग
इन कोड की जाँच खुद Lean से करना चाहते हैं, तो पहले Lean 4 इंस्टॉल करें।