संरचनात्मक प्रेरण: Difference between revisions

Latest revision as of 13:59, 14 August 2023

संरचनात्मक प्रेरण प्रमाण विधि है जिसका उपयोग गणितीय तर्क (जैसे Łoś' के सिद्धांत के प्रमाण में), कंप्यूटर विज्ञान, ग्राफ सिद्धांत और कुछ अन्य गणितीय क्षेत्रों में उपयोग की जाती है। यह प्राकृतिक संख्याओं पर गणितीय प्रेरण का सामान्यीकरण है और इसे अधिक विस्तृत रूप से किसी भी नोथेरियन प्रेरण विस्तारित किया जा सकता है। संरचनात्मक पुनरावर्तन, पुनरावर्तन विधि है जो संरचनात्मक संभावना के साथ सामान्य पुनरावर्तन के समान संबंध रखती है, जिस प्रकार सामान्य गणितीय अभिवादन सामान्य प्राकृतिक संख्याओं पर आधारित होता है।

किसी प्रस्ताव को सिद्ध करने के लिए संरचनात्मक प्रेरण का उपयोग किया जाता है $P (x)$ सभी के लिए धारण करता है $x$ किसी प्रकार की पुनरावर्ती परिभाषा संरचना, जैसे प्रथम-क्रम तर्क सूत्र, सूची (कंप्यूटर विज्ञान), या वृक्ष (ग्राफ़ सिद्धांत)। संरचनाओं पर सुस्थापित आंशिक क्रम परिभाषित किया गया है (सूत्रों के लिए उपसूत्र, सूचियों के लिए उपसूची, और वृक्षों के लिए उपवृक्ष)। संरचनात्मक प्रेरण प्रमाण प्रमाण है कि प्रस्ताव सभी न्यूनतम तत्व संरचनाओं के लिए लागू होता है और यदि यह निश्चित संरचना के तत्काल उप-संरचनाओं के लिए लागू होता है $S$ , तो इसे अवश्य धारण करना चाहिए $S$ भी। (औपचारिक रूप से कहें तो, यह फिर वास्तव में किसी भी $x$ के लिए प्रस्तावना सत्य होने के लिए पूर्वाधिकारी अभिवादन की धारणा को पूरा करता है, जो यह दावा करता है कि ये दो शर्तें प्रस्तुत करना पर्याप्त है कि प्रस्तावना सभी $x$ के लिए सत्य है।)

संरचनात्मक पुनरावर्ती फ़ंक्शन पुनरावर्ती फ़ंक्शन को परिभाषित करने के लिए समान विचार का उपयोग करता है: "आधार मामले" ने प्रत्येक न्यूनतम संरचना को संभाला और पुनरावर्तन के लिए नियम। संरचनात्मक पुनरावर्तन सामान्यतः संरचनात्मक संभावना द्वारा सत्य सिद्ध किया जाता है; विशेष रूप से आसान मामलों में, आनुवंशिक चरण को अधिकांशतः छोड़ दिया जाता है। नीचे दिए गए उदाहरण में, लंबाई और ++ (या विवेक, जो संख्या को बढ़ाता है) फ़ंक्शन संरचनात्मक पुनरावर्तक हैं।

उदाहरण के लिए, यदि संरचनाएँ सूचियाँ की हैं, तो सामान्यतः "इससे कम" आंशिक क्रमण "<" का परिचय किया जाता है, जिसमें $L < M$ होता है जबकि सूची $L$ सूची $M$ की पूरी सूची होती है। इस आंशिक क्रमण के अनुसार, रिक्त सूची $[]$ अद्वितीय न्यूनतम तत्व होती है। तो, किसी सुची $L$ के लिए संरचनात्मक अभिवादन प्रमाण $P (L)$ फिर दो भागों से मिलता है: पहले, $P ([])$ सत्य होने का प्रमाण और दूसरे, यदि $P (L)$ किसी सूची $L$ के लिए सत्य है, $L$ और $M$ , की पूरी सूची है, तो $P (M)$ भी सत्य होना चाहिए।

अंततः, फ़ंक्शन या संरचना के निर्माण के तरीके पर निर्भर करके एक से अधिक बेस केस और/या एक से अधिक अनुवंशिक केस के उपस्थिति की संभावना हो सकती है। ऐसे मामलों में, किसी प्रस्तावना $P (L)$ के संरचनात्मक अभिवादन को निम्नलिखित ढंग से पूरा किया जाता है:

प्रत्येक बेस केस $BC$ के लिए $P (BC)$ सत्य होने का प्रमाण।
यदि किसी विशिष्ट उदाहरण $I$ , के लिए $P (I)$ सत्य है, और $M$ उदाहरण $I$ से किसी भी एक पुनरावृत्ति नियम को एक बार लागू करके प्राप्त किया जा सकता है, तो $P (M)$ भी सत्य होना चाहिए।

उदाहरण

प्राचीन पूर्वज वृक्ष, 5 पीढ़ियों में 31 व्यक्तियों को दर्शाता है

पूर्वज वृक्ष सामान्यतः जाने वाली डेटा संरचना है, जो किसी व्यक्ति के माता-पिता, दादा-दादी, आदि को जितना ज्ञात है उतना दिखाती है (उदाहरण के लिए चित्र देखें)। यह पुनरावर्ती रूप से परिभाषित है:

सरलतम मामले में, पूर्वज वृक्ष केवल व्यक्ति को दिखाता है (यदि उनके माता-पिता के बारे में कुछ भी नहीं ज्ञात है);
वैकल्पिक रूप से, पूर्वज वृक्ष व्यक्ति को दर्शाता है और, शाखाओं से जुड़ा हुआ, उनके माता-पिता के दो पूर्वज उपवृक्ष को भी दिखाता है (संक्षेपण के लिए प्रमाणित करने के लिए सरलीकृत मानदंड उपयोग किया जा रहा है कि यदि इनमें से ज्ञात है, तो दोनों ज्ञात हैं)।

उदाहरण के रूप में, "जीवित वृक्ष जो $g$ पीढ़ियों पर फैलता है, अधिकतम $2 g - 1$ व्यक्तियों को दिखाता है" जैसी गुणवत्ता को संरचनात्मक अभिवादन के माध्यम से निम्नलिखित रूप से सिद्ध किया जा सकता है:

सरलतम मामले में, वृक्ष ही व्यक्ति को दिखाता है और इसलिए पीढ़ियों को; ऐसे वृक्ष के लिए गुणवत्ता सत्य है, क्योंकि $1 \leq 2 1 - 1$ है।
विकल्प से, वृक्ष व्यक्ति और उनके माता-पिता के वृक्षों को दिखाता है। क्योंकि उनका प्रत्येक वृक्ष पूरे वृक्ष का उपसंरचना है, इसलिए इसे सिद्ध करने के लिए अनुमान लगाया जा सकता है कि इस गुणवत्ता को प्रमाणित किया जा सकता है (जिसे अनुवंशिक हाइपोथिसिस कहते हैं)। इसका मतलब, p ≤ 2^g − 1 और q ≤ 2^h − 1 को अनुमान लगाया जा सकता है, जहां g और h पिता के उपवृक्ष की पीढ़ियों की संख्या को दर्शाते हैं, और p और q उन व्यक्तियों की संख्या को दर्शाते हैं जिन्हें वे दिखाते हैं।
- यदि $g \leq h$ , हो, तो पूरा वृक्ष $1 + h$ पीढ़ियों पर फैलता है और $p + q + 1$ व्यक्तियों को दिखाता है, और $p+q+1\leq (2^{g}-1)+(2^{h}-1)+1\leq 2^{h}+2^{h}-1=2^{1+h}-1,$ अर्थात संपूर्ण वृक्ष संपत्ति को संतुष्ट करता है।
- यदि $h \leq g$ , हो, तो पूरा वृक्ष $1 + g$ पीढ़ियों पर फैलता है और $p + q + 1 \leq 2 g + 1 - 1$ व्यक्तियों को दर्शाता है, जिसे समान तरीके से कारणांतर द्वारा प्रमाणित किया जा सकता है, अर्थात पूरा वृक्ष इस मामले में भी गुणवत्ता को संतुष्ट करता है।

इस प्रकार, संरचनात्मक अभिवादन के द्वारा, प्रत्येक पूर्वज वृक्ष गुणवत्ता को संतुष्ट करता है।

अन्य, अधिक औपचारिक उदाहरण के रूप में, सूचियों की निम्नलिखित संपत्ति पर विचार करते हैं:

{\text{EQ:}}\quad \operatorname {len} (L+\!+\ M)=\operatorname {len} (L)+\operatorname {len} (M)

जहां $++$ सूचियों का संयोजन ऑपरेशन है $len()$ सूचियों का संयोजन ऑपरेशन है $L$ और $M$ सूचियाँ हैं।

सूचियों के लिए लंबाई और संयोजन ऑपरेशन के लिए हमें परिभाषाएं चाहिए। $(h : t)$ सूची का प्रतिनिधित्व करती है, जिसका मुख्य अंश $h$ है (पहला तत्व) और उसका टेल (बचे हुए तत्वों की सूची) $t$ , है। $[]$ खाली सूची को दर्शाता है। सूचियों की लंबाई और संयोजन ऑपरेशन के लिए परिभाषाएं निम्नलिखित हैं:

{\begin{array}{ll}{\text{LEN1:}}&\operatorname {len} ([\ ])=0\\{\text{LEN2:}}&\operatorname {len} (h:t)=1+\operatorname {len} (t)\\&\\{\text{APP1:}}&[\ ]+\!+\ list=list\\{\text{APP2:}}&(h:t)+\!+\ list=h:(t+\!+\ list)\end{array}}

हमारा प्रस्ताव $P (l)$ यह है कि $EQ$ सभी सूचियों के लिए सत्य है $M$ कब $L$ है $l$ . हम वो दिखाना चाहते हैं $P (l)$ सभी सूचियों के लिए सत्य है $l$ . हम इसे सूचियों में संरचनात्मक प्रेरण द्वारा सिद्ध करेंगे।

पहले हम इसे सिद्ध करेंगे $P ([])$ क्या सच है; वह है, $EQ$ सभी सूचियों के लिए सत्य है $M$ कब $L$ ख़ाली सूची होती है $[]$ . विचार करना $EQ$ :

{\begin{array}{rll}\operatorname {len} (L+\!+\ M)&=\operatorname {len} ([\ ]+\!+\ M)\\&=\operatorname {len} (M)&({\text{by APP1}})\\&=0+\operatorname {len} (M)\\&=\operatorname {len} ([\ ])+\operatorname {len} (M)&({\text{by LEN1}})\\&=\operatorname {len} (L)+\operatorname {len} (M)\\\end{array}}

अतः प्रमेय का यह भाग सिद्ध हो गया है; $EQ$ सभी के लिए सत्य है $M$ , जब $L$ है $[]$ , क्योंकि बायां पक्ष और दायां पक्ष बराबर हैं।

इसके बाद, किसी भी गैर-रिक्त सूची $I$ पर विचार पर करें. जब से $I$ गैर-रिक्त है, इसमें मुख्य आइटम है, $x$ , और पूंछ सूची, $xs$ , अतः हम इसे उस प्रकार व्यक्त कर सकते हैं $(x : xs)$ . प्रेरण परिकल्पना वह है जो $EQ$ के सभी मानों के लिए सत्य है $M$ जब $L$ है $xs$ :

{\text{HYP:}}\quad \operatorname {len} (xs+\!+\ M)=\operatorname {len} (xs)+\operatorname {len} (M)

हम यह दिखाना चाहेंगे कि यदि ऐसा है तो $EQ$ के सभी मानों के लिए भी सत्य है $M$ जब $L = I = (x : xs)$ . हम पहले की प्रकार आगे बढ़ते हैं:

{\begin{array}{rll}\operatorname {len} (L)+\operatorname {len} (M)&=\operatorname {len} (x:xs)+\operatorname {len} (M)\\&=1+\operatorname {len} (xs)+\operatorname {len} (M)&({\text{by LEN2}})\\&=1+\operatorname {len} (xs+\!+\ M)&({\text{by HYP}})\\&=\operatorname {len} (x:(xs+\!+\ M))&({\text{by LEN2}})\\&=\operatorname {len} ((x:xs)+\!+\ M)&({\text{by APP2}})\\&=\operatorname {len} (L+\!+\ M)\end{array}}

इस प्रकार, संरचनात्मक प्रेरण से, हम उसे प्राप्त करते हैं कि सूचि $P (L)$ सभी $L$ सूचियों के लिए सत्य है.

सुव्यवस्थित

सामान्य गणितीय आनुवंशिकता की तरह ही संरचनात्मक आनुवंशिकता भी किसी सुव्यवस्थित सिद्धांत के समान होती है। अगर किसी विशेष प्रकार की सभी संरचनाओं का समुच्चय वेल-संविदित आंशिक क्रम स्वीकार करता है, तो हर गैर-खाली उपसमुच्चय का न्यूनतम तत्त्व होना चाहिए। (यह "वेल-संविदित" के परिभाषा है।) इस संबंध में यह लेख का महत्व है कि यह हमें सिद्ध करने में मदद करता है कि यदि हमारे प्रमाण को खंडन करने के लिए कोई विरोधी उदाहरण होता है, तो उसका न्यूनतम विरोधी उदाहरण होना चाहिए। यदि हम दिखा सकते हैं कि न्यूनतम विरोधी उदाहरण से भी और छोटे विरोधी उदाहरण का सम्भव होना संभव नहीं है, तो हमारे पास विरोधाभास हो जाता है (क्योंकि न्यूनतम विरोधी उदाहरण न्यूनतम नहीं होता है) और इस तरह विरोधी उदाहरणों का समुच्चय खाली होना चाहिए।

उदाहरण के रूप में, सभी बाइनरी ट्री का समुच्चय ले लेते हैं। हम दिखाएंगे कि पूर्ण बाइनरी ट्री में पत्तियों की संख्या, आंतरिक नोड्स की संख्या से अधिक है। मान लें कि कोई विरोधी उदाहरण है; इससे तो निश्चित रूप से उसमें आंतरिक नोड्स की सबसे कम संख्या होगी। इस विरोधी उदाहरण, $C$ , में $n$ आंतरिक नोड्स और $l$ पत्तियाँ होती हैं, जहां $n + 1 \neq l$ । इसके अतिरिक्त, $C$ गैर-तुच्छ होना चाहिए, क्योंकि साधारण वृक्ष में n = 0 और l = 1 होता है और इसलिए यह विपरीत उदाहरण नहीं होता है। इसलिए $C$ में कम से कम पत्ती होती है जिसका मूल नोड आंतरिक नोड होता है। इस पत्ते और उसके मूल नोड को वृक्ष से हटा दें, पत्ती के सहोदर नोड को उस स्थान पर पदोन्नत करें जिस पर पहले उसके मूल नोड का प्रभुत्व था। इससे , $n$ और $l$ 1 से दोनों कम हो जाते हैं, इसलिए नया वृक्ष भी $n + 1 \neq l$ होगा और इसलिए यह छोटा विपरीत उदाहरण है। लेकिन परिकल्पना से, $C$ पहले से ही सबसे छोटा विपरीत उदाहरण था; इसलिए, यह धारणा कि प्रारंभिक में कोई विपरीत उदाहरण उपस्थित थे, ग़लत रहा होगा। यहाँ 'छोटा' केद्वारा निहित आंशिक क्रम वही है जो यही कहता है कि $S < T$ जबकि $S$ में तत्वों की संख्या $T$ से कम होती है।

यह भी देखें

संयोजन
प्रारंभिक बीजगणित
लूप अपरिवर्तनीय, लूप के लिए एनालॉग

संदर्भ

Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages, and Computation (2nd ed.). Reading Mass: Addison-Wesley. ISBN 978-0-201-44124-6.
"Mathematical Logic - Video 01.08 - Generalized (Structural) Induction" on YouTube

Early publications about structural induction include:

Burstall, R. M. (1969). "Proving Properties of Programs by Structural Induction". The Computer Journal. 12 (1): 41–48. doi:10.1093/comjnl/12.1.41.
Aubin, Raymond (1976), Mechanizing Structural Induction, EDI-INF-PHD, vol. 76–002, University of Edinburgh, hdl:1842/6649
Huet, G.; Hullot, J. M. (1980). "Proofs by Induction in Equational Theories with Constructors" (PDF). 21st Ann. Symp. on Foundations of Computer Science. IEEE. pp. 96–107.
Rózsa Péter, Über die Verallgemeinerung der Theorie der rekursiven Funktionen für abstrakte Mengen geeigneter Struktur als Definitionsbereiche, Symposium International, Varsovie septembre (1959) (On the generalization of the theory of recursive functions for abstract quantities with suitable structures as domains).

@@ Line 1: / Line 1: @@
 {{short description|Proof method in mathematical logic}}
-संरचनात्मक प्रेरण [[प्रमाण विधि]] है जिसका उपयोग [[गणितीय तर्क]] में किया जाता है (उदाहरण के लिए, Ultraproduct#Łoś's प्रमेय|Łoś' प्रमेय के प्रमाण में), [[कंप्यूटर विज्ञान]], [[ग्राफ सिद्धांत]] और कुछ अन्य गणितीय क्षेत्रों में। यह [[गणितीय प्रेरण]] का सामान्यीकरण है और इसे मनमाने [[नोथेरियन प्रेरण]] के लिए आगे सामान्यीकृत किया जा सकता है। संरचनात्मक पुनरावर्तन पुनरावर्तन विधि है जिसका संरचनात्मक प्रेरण से वही संबंध होता है जो सामान्य पुनरावर्तन का सामान्य गणितीय प्रेरण से होता है।
+'''संरचनात्मक प्रेरण''' [[प्रमाण विधि]] है जिसका उपयोग [[गणितीय तर्क]] (जैसे Łoś' के सिद्धांत के प्रमाण में), [[कंप्यूटर विज्ञान]], [[ग्राफ सिद्धांत]] और कुछ अन्य गणितीय क्षेत्रों में उपयोग की जाती है। यह प्राकृतिक संख्याओं पर [[गणितीय प्रेरण]] का सामान्यीकरण है और इसे अधिक विस्तृत रूप से किसी भी [[नोथेरियन प्रेरण]] विस्तारित किया जा सकता है। संरचनात्मक पुनरावर्तन, पुनरावर्तन विधि है जो संरचनात्मक संभावना के साथ सामान्य पुनरावर्तन के समान संबंध रखती है, जिस प्रकार सामान्य गणितीय अभिवादन सामान्य प्राकृतिक संख्याओं पर आधारित होता है।
-किसी प्रस्ताव को सिद्ध करने के लिए संरचनात्मक प्रेरण का उपयोग किया जाता है {{math|''P''(''x'')}} [[सभी के लिए]] धारण करता है {{mvar|x}} किसी प्रकार की [[पुनरावर्ती परिभाषा]] संरचना, जैसे
+किसी प्रस्ताव को सिद्ध करने के लिए संरचनात्मक प्रेरण का उपयोग किया जाता है {{math|''P''(''x'')}} [[सभी के लिए]] धारण करता है {{mvar|x}} किसी प्रकार की [[पुनरावर्ती परिभाषा]] संरचना, जैसे प्रथम-क्रम तर्क सूत्र, [[सूची (कंप्यूटर विज्ञान)]], या [[वृक्ष (ग्राफ़ सिद्धांत)]]। संरचनाओं पर सुस्थापित आंशिक क्रम परिभाषित किया गया है (सूत्रों के लिए उपसूत्र, सूचियों के लिए उपसूची, और वृक्षों के लिए उपवृक्ष)। संरचनात्मक प्रेरण प्रमाण प्रमाण है कि प्रस्ताव सभी [[न्यूनतम तत्व]] संरचनाओं के लिए लागू होता है और यदि यह निश्चित संरचना के तत्काल उप-संरचनाओं के लिए लागू होता है {{mvar|S}}, तो इसे अवश्य धारण करना चाहिए {{mvar|S}} भी। (औपचारिक रूप से कहें तो, यह फिर वास्तव में किसी भी {{mvar|x}} के लिए प्रस्तावना सत्य होने के लिए पूर्वाधिकारी अभिवादन की धारणा को पूरा करता है, जो यह दावा करता है कि ये दो शर्तें प्रस्तुत करना पर्याप्त है कि प्रस्तावना सभी {{mvar|x}} के लिए सत्य है।)
-प्रथम-क्रम तर्क#सूत्र, [[सूची (कंप्यूटर विज्ञान)]], या [[वृक्ष (ग्राफ़ सिद्धांत)]]। संरचनाओं पर सुस्थापित आंशिक क्रम परिभाषित किया गया है (सूत्रों के लिए उपसूत्र, सूचियों के लिए उपसूची, और पेड़ों के लिए उपवृक्ष)। संरचनात्मक प्रेरण प्रमाण प्रमाण है कि प्रस्ताव सभी [[न्यूनतम तत्व]] संरचनाओं के लिए लागू होता है और यदि यह निश्चित संरचना के तत्काल उप-संरचनाओं के लिए लागू होता है {{mvar|S}}, तो इसे अवश्य धारण करना चाहिए {{mvar|S}} भी। (औपचारिक रूप से बोलते हुए, यह तब [[अच्छी तरह से स्थापित प्रेरण]] के सिद्धांत के परिसर को संतुष्ट करता है, जो दावा करता है कि ये दो शर्तें सभी के लिए प्रस्ताव को लागू करने के लिए पर्याप्त हैं {{mvar|x}}.)
-संरचनात्मक रूप से पुनरावर्ती फ़ंक्शन पुनरावर्ती फ़ंक्शन को परिभाषित करने के लिए ही विचार का उपयोग करता है: आधार मामले प्रत्येक न्यूनतम संरचना और पुनरावृत्ति के लिए नियम को संभालते हैं। संरचनात्मक पुनरावर्तन आमतौर पर संरचनात्मक प्रेरण द्वारा सही साबित होता है; विशेष रूप से आसान मामलों में, आगमनात्मक चरण को अक्सर छोड़ दिया जाता है। नीचे दिए गए उदाहरण में लंबाई और ++ फ़ंक्शन संरचनात्मक रूप से पुनरावर्ती हैं।
+संरचनात्मक पुनरावर्ती फ़ंक्शन पुनरावर्ती फ़ंक्शन को परिभाषित करने के लिए समान विचार का उपयोग करता है: "आधार मामले" ने प्रत्येक न्यूनतम संरचना को संभाला और पुनरावर्तन के लिए नियम। संरचनात्मक पुनरावर्तन सामान्यतः संरचनात्मक संभावना द्वारा सत्य सिद्ध किया जाता है; विशेष रूप से आसान मामलों में, आनुवंशिक चरण को  अधिकांशतः छोड़ दिया जाता है। नीचे दिए गए उदाहरण में, लंबाई और ++ (या विवेक, जो संख्या को बढ़ाता है) फ़ंक्शन संरचनात्मक पुनरावर्तक हैं।
-उदाहरण के लिए, यदि संरचनाएँ सूचियाँ हैं, तो आमतौर पर आंशिक क्रम < का परिचय दिया जाता है, जिसमें {{math|''L'' < ''M''}} जब भी सूची {{mvar|L}} सूची की पूंछ है {{mvar|M}}. इस आदेश के अंतर्गत, रिक्त सूची {{math|[]}} अद्वितीय न्यूनतम तत्व है. किसी प्रस्ताव का संरचनात्मक प्रेरण प्रमाण {{math|''P''(''L'')}} तो इसमें दो भाग होते हैं: प्रमाण {{math|''P''([])}} सत्य है और इसका प्रमाण है कि यदि {{math|''P''(''L'')}} कुछ सूची के लिए सत्य है {{mvar|L}}, और अगर {{mvar|L}} सूची की पूंछ है {{mvar|M}}, तब {{math|''P''(''M'')}} भी सत्य होना चाहिए.
+उदाहरण के लिए, यदि संरचनाएँ सूचियाँ की हैं, तो सामान्यतः "इससे कम" आंशिक क्रमण "<" का परिचय किया जाता है, जिसमें {{math|''L'' < ''M''}}  होता है जबकि सूची  {{mvar|L}} सूची {{mvar|M}} की पूरी सूची होती है। इस आंशिक क्रमण के अनुसार, रिक्त सूची {{math|[]}} अद्वितीय न्यूनतम तत्व होती है। तो, किसी सुची {{mvar|L}} के लिए संरचनात्मक अभिवादन प्रमाण {{math|''P''(''L'')}} फिर दो भागों से मिलता है: पहले, {{math|''P''([])}} सत्य होने का प्रमाण और दूसरे, यदि {{math|''P''(''L'')}} किसी सूची {{mvar|L}} के लिए सत्य है, {{mvar|L}} और {{mvar|M}}, की पूरी सूची है, तो {{math|''P''(''M'')}} भी सत्य होना चाहिए।
-अंततः, से अधिक आधार मामले और/या से अधिक आगमनात्मक मामले मौजूद हो सकते हैं, यह इस बात पर निर्भर करता है कि फ़ंक्शन या संरचना का निर्माण कैसे किया गया था। उन मामलों में, किसी प्रस्ताव का संरचनात्मक प्रेरण प्रमाण {{math|''P''(''L'')}} फिर इसमें शामिल हैं:
+अंततः, फ़ंक्शन या संरचना के निर्माण के तरीके पर निर्भर करके एक से अधिक बेस केस और/या एक से अधिक अनुवंशिक केस के उपस्थिति की संभावना हो सकती है। ऐसे मामलों में, किसी प्रस्तावना {{math|''P''(''L'')}} के संरचनात्मक अभिवादन को निम्नलिखित ढंग से पूरा किया जाता है:
 {{ordered list|list_style_type=upper-alpha
-|a proof that {{math|''P''(''BC'')}} is true for each base case {{mvar|BC}},
+|प्रत्येक बेस केस  {{mvar|BC}} के लिए {{math|''P''(''BC'')}} सत्य होने का प्रमाण।
-|a proof that if {{math|''P''(''I'')}} is true for some instance {{mvar|I}}, and {{mvar|M}} can be obtained from {{mvar|I}} by applying any one recursive rule once, then {{math|''P''(''M'')}} must also be true.}}
+| यदि किसी विशिष्ट उदाहरण {{mvar|I}}, के लिए {{math|''P''(''I'')}} सत्य है, और {{mvar|M}} उदाहरण {{mvar|I}} से किसी भी एक पुनरावृत्ति नियम को एक बार लागू करके प्राप्त किया जा सकता है, तो {{math|''P''(''M'')}}  भी सत्य होना चाहिए।}}
 ==उदाहरण==
-[[File:Waldburg Ahnentafel.jpg|thumb|प्राचीन पूर्वज वृक्ष, 5 पीढ़ियों में 31 व्यक्तियों को दर्शाता है]]पारिवारिक वृक्ष सामान्य रूप से ज्ञात डेटा संरचना है, जहां तक ज्ञात हो किसी व्यक्ति के माता-पिता, दादा-दादी आदि को दर्शाता है (उदाहरण के लिए चित्र देखें)। इसे पुनरावर्ती रूप से परिभाषित किया गया है:
+[[File:Waldburg Ahnentafel.jpg|thumb|प्राचीन पूर्वज वृक्ष, 5 पीढ़ियों में 31 व्यक्तियों को दर्शाता है]]पूर्वज वृक्ष सामान्यतः जाने वाली डेटा संरचना है, जो किसी व्यक्ति के माता-पिता, दादा-दादी, आदि को जितना ज्ञात है उतना दिखाती है (उदाहरण के लिए चित्र देखें)। यह पुनरावर्ती रूप से परिभाषित है:
-* सबसे सरल मामले में, पूर्वज वृक्ष केवल व्यक्ति को दर्शाता है (यदि उनके माता-पिता के बारे में कुछ भी ज्ञात नहीं है);
+* सरलतम मामले में,   पूर्वज वृक्ष केवल   व्यक्ति को दिखाता है (यदि उनके माता-पिता के बारे में कुछ भी नहीं ज्ञात है);
-* वैकल्पिक रूप से, पूर्वज वृक्ष व्यक्ति को दर्शाता है और, शाखाओं से जुड़ा हुआ, उनके माता-पिता के दो पूर्वज उपवृक्ष (प्रमाण की संक्षिप्तता के लिए सरल धारणा का उपयोग करते हुए कि यदि उनमें से ज्ञात है, तो दोनों हैं)।
+* वैकल्पिक रूप से, पूर्वज वृक्ष व्यक्ति को दर्शाता है और, शाखाओं से जुड़ा हुआ, उनके माता-पिता के दो पूर्वज उपवृक्ष को भी दिखाता है (संक्षेपण के लिए प्रमाणित करने के लिए   सरलीकृत मानदंड उपयोग किया जा रहा है कि यदि इनमें से   ज्ञात है, तो दोनों ज्ञात हैं)।
-उदाहरण के तौर पर, संपत्ति पूर्वज वृक्ष का विस्तार है {{mvar|g}}पीढ़ियाँ अधिक से अधिक दिखाती हैं {{math|2<sup>''g''</sup> − 1}}व्यक्तियों को संरचनात्मक प्रेरण द्वारा निम्नानुसार सिद्ध किया जा सकता है:
+उदाहरण के रूप में, "जीवित वृक्ष जो {{mvar|g}} पीढ़ियों पर फैलता है, अधिकतम {{math|2<sup>''g''</sup> − 1}}व्यक्तियों को दिखाता है" जैसी गुणवत्ता को संरचनात्मक अभिवादन के माध्यम से निम्नलिखित रूप से सिद्ध किया जा सकता है:
-* सबसे सरल मामले में, पेड़ केवल व्यक्ति और इसलिए पीढ़ी को दर्शाता है; ऐसे पेड़ के लिए संपत्ति सत्य है, क्योंकि {{math|1 ≤ 2<sup>1</sup> − 1}}.
+* सरलतम मामले में, वृक्ष   ही व्यक्ति को दिखाता है और इसलिए   पीढ़ियों को; ऐसे वृक्ष के लिए गुणवत्ता सत्य है, क्योंकि {{math|1 ≤ 2<sup>1</sup> − 1}} है।
-* वैकल्पिक रूप से, पेड़ व्यक्ति और उनके माता-पिता के पेड़ को दर्शाता है। चूंकि उत्तरार्द्ध में से प्रत्येक पूरे पेड़ का उपसंरचना है, इसलिए यह माना जा सकता है कि यह सिद्ध की जाने वाली संपत्ति को संतुष्ट करता है (जैसे कि प्रेरण परिकल्पना)। वह है, {{math|''p'' ≤ 2<sup>''g''</sup> − 1}} और {{math|''q'' ≤ 2<sup>''h''</sup> − 1}} माना जा सकता है, कहां {{mvar|g}} और {{mvar|h}} क्रमशः पिता और माता के उपवृक्ष में फैली पीढ़ियों की संख्या को दर्शाता है, और {{mvar|p}} और {{mvar|q}} उनके द्वारा दिखाए गए व्यक्तियों की संख्या को निरूपित करें।
+* विकल्प से, वृक्ष   व्यक्ति और उनके माता-पिता के वृक्षों को दिखाता है। क्योंकि उनका प्रत्येक वृक्ष पूरे वृक्ष का   उपसंरचना है, इसलिए इसे सिद्ध करने के लिए अनुमान लगाया जा सकता है कि इस गुणवत्ता को प्रमाणित किया जा सकता है (जिसे अनुवंशिक हाइपोथिसिस कहते हैं)। इसका मतलब, {{math|''p'' ≤ 2<sup>''g''</sup> − 1}} और {{math|''q'' ≤ 2<sup>''h''</sup> − 1}} को अनुमान लगाया जा सकता है, जहां {{mvar|g}} और {{mvar|h}} पिता के उपवृक्ष की पीढ़ियों की संख्या को दर्शाते हैं, और {{mvar|p}} और {{mvar|q}} उन व्यक्तियों की संख्या को दर्शाते हैं जिन्हें वे दिखाते हैं।
-** यदि {{math|''g'' ≤ ''h''}}, पूरा पेड़ फैला हुआ है {{math|1 + ''h''}} पीढ़ियाँ और शो {{math|1=''p'' + ''q'' + 1}} व्यक्ति, और<math display=block>p+q+1 \leq (2^g-1) + (2^h-1) + 1 \leq 2^h+2^h-1 = 2^{1+h}-1,</math>अर्थात संपूर्ण वृक्ष संपत्ति को संतुष्ट करता है।
+** यदि {{math|''g'' ≤ ''h''}}, हो, तो पूरा वृक्ष {{math|1 + ''h''}} पीढ़ियों पर फैलता है और {{math|1=''p'' + ''q'' + 1}} व्यक्तियों को दिखाता है, और<math display=block>p+q+1 \leq (2^g-1) + (2^h-1) + 1 \leq 2^h+2^h-1 = 2^{1+h}-1,</math>अर्थात संपूर्ण वृक्ष संपत्ति को संतुष्ट करता है।
-** यदि {{math|1=''h'' ≤ ''g''}}, पूरा पेड़ फैला हुआ है {{math|1=1 + ''g''}} पीढ़ियाँ और शो {{math|''p'' + ''q'' + 1 ≤ 2{{sup|''g'' + 1}} − 1}} समान तर्क से व्यक्ति, यानी पूरा पेड़ इस मामले में भी संपत्ति को संतुष्ट करता है।
+** यदि {{math|1=''h'' ≤ ''g''}}, हो, तो पूरा वृक्ष {{math|1=1 + ''g''}} पीढ़ियों पर फैलता है और {{math|''p'' + ''q'' + 1 ≤ 2{{sup|''g'' + 1}} − 1}} व्यक्तियों को दर्शाता है, जिसे समान तरीके से कारणांतर द्वारा प्रमाणित किया जा सकता है, अर्थात पूरा वृक्ष इस मामले में भी गुणवत्ता को संतुष्ट करता है।
-इसलिए, संरचनात्मक प्रेरण द्वारा, प्रत्येक पूर्वज वृक्ष संपत्ति को संतुष्ट करता है।
+इस प्रकार, संरचनात्मक अभिवादन के द्वारा, प्रत्येक पूर्वज वृक्ष गुणवत्ता को संतुष्ट करता है।
-अन्य, अधिक औपचारिक उदाहरण के रूप में, सूचियों की निम्नलिखित संपत्ति पर विचार करें:
+अन्य, अधिक औपचारिक उदाहरण के रूप में, सूचियों की निम्नलिखित संपत्ति पर विचार करते हैं:
 :<math>\text{EQ:} \quad \operatorname{len}(L +\!+\ M) = \operatorname{len}(L) + \operatorname{len}(M)</math>
-यहाँ {{math|++}} सूची संयोजन ऑपरेशन को दर्शाता है, {{math|len()}} सूची की लंबाई, और {{mvar|L}} और {{mvar|M}} सूचियाँ हैं.
+जहां  {{math|++}}  सूचियों का संयोजन ऑपरेशन है {{math|len()}} सूचियों का संयोजन ऑपरेशन है {{mvar|L}} और {{mvar|M}} सूचियाँ हैं।
-इसे सिद्ध करने के लिए, हमें लंबाई और संयोजन संक्रिया के लिए परिभाषाओं की आवश्यकता है। होने देना {{math|(''h'':''t'')}} उस सूची को निरूपित करें जिसका शीर्ष (पहला तत्व) है {{mvar|h}} और पूँछ (शेष तत्वों की सूची) किसकी है {{mvar|t}}, और जाने {{math|[]}}रिक्त सूची को निरूपित करें। लंबाई और संयोजन संक्रिया की परिभाषाएँ हैं:
+सूचियों के लिए लंबाई और संयोजन ऑपरेशन के लिए हमें परिभाषाएं चाहिए। {{math|(''h'':''t'')}}  सूची का प्रतिनिधित्व करती है, जिसका मुख्य अंश {{mvar|h}} है (पहला तत्व) और उसका टेल (बचे हुए तत्वों की सूची) {{mvar|t}}, है। {{math|[]}} खाली सूची को दर्शाता है। सूचियों की लंबाई और संयोजन ऑपरेशन के लिए परिभाषाएं निम्नलिखित हैं:
 :<math>\begin{array}{ll}
@@ Line 44: / Line 43: @@
 हमारा प्रस्ताव {{math|''P''(''l'')}} यह है कि {{math|EQ}} सभी सूचियों के लिए सत्य है {{mvar|M}} कब {{mvar|L}} है {{mvar|l}}. हम वो दिखाना चाहते हैं {{math|1=''P''(''l'')}} सभी सूचियों के लिए सत्य है {{mvar|l}}. हम इसे सूचियों में संरचनात्मक प्रेरण द्वारा सिद्ध करेंगे।
-पहले हम इसे साबित करेंगे {{math|''P''([])}} क्या सच है; वह है, {{math|EQ}} सभी सूचियों के लिए सत्य है {{mvar|M}} कब {{mvar|L}} ख़ाली सूची होती है {{math|[]}}. विचार करना {{math|EQ}}:
+पहले हम इसे सिद्ध करेंगे {{math|''P''([])}} क्या सच है; वह है, {{math|EQ}} सभी सूचियों के लिए सत्य है {{mvar|M}} कब {{mvar|L}} ख़ाली सूची होती है {{math|[]}}. विचार करना {{math|EQ}}:
 :<math>\begin{array}{rll}
@@ Line 54: / Line 53: @@
 &= \operatorname{len}(L) + \operatorname{len}(M)    \\
 \end{array}</math>
-अतः प्रमेय का यह भाग सिद्ध हो गया है; {{math|EQ}} सभी के लिए सत्य है {{mvar|M}}, कब {{mvar|L}} है {{math|[]}}, क्योंकि बायां पक्ष और दायां पक्ष बराबर हैं।
+अतः प्रमेय का यह भाग सिद्ध हो गया है; {{math|EQ}} सभी के लिए सत्य है {{mvar|M}}, जब {{mvar|L}} है {{math|[]}}, क्योंकि बायां पक्ष और दायां पक्ष बराबर हैं।
-इसके बाद, किसी भी गैर-रिक्त सूची पर विचार करें {{mvar|I}}. तब से {{mvar|I}} गैर-रिक्त है, इसमें मुख्य आइटम है, {{mvar|x}}, और पूंछ सूची, {{mvar|xs}}, अतः हम इसे इस प्रकार व्यक्त कर सकते हैं {{math|(''x'':''xs'')}}. प्रेरण परिकल्पना वह है {{math|EQ}} के सभी मानों के लिए सत्य है {{mvar|M}} कब {{mvar|L}} है {{mvar|xs}}:
+इसके बाद, किसी भी गैर-रिक्त सूची {{mvar|I}} पर विचार पर करें. जब से {{mvar|I}} गैर-रिक्त है, इसमें मुख्य आइटम है, {{mvar|x}}, और पूंछ सूची, {{mvar|xs}}, अतः हम इसे उस प्रकार व्यक्त कर सकते हैं {{math|(''x'':''xs'')}}. प्रेरण परिकल्पना वह है जो {{math|EQ}} के सभी मानों के लिए सत्य है {{mvar|M}} जब {{mvar|L}} है {{mvar|xs}}:
 :<math>\text{HYP:} \quad \operatorname{len}(xs +\!+\ M) = \operatorname{len}(xs) + \operatorname{len}(M)</math>
-हम यह दिखाना चाहेंगे कि यदि ऐसा है तो {{math|EQ}} के सभी मानों के लिए भी सत्य है {{mvar|M}} कब {{math|1=''L'' = ''I'' = (''x'':''xs'')}}. हम पहले की तरह आगे बढ़ते हैं:
+हम यह दिखाना चाहेंगे कि यदि ऐसा है तो {{math|EQ}} के सभी मानों के लिए भी सत्य है {{mvar|M}} जब {{math|1=''L'' = ''I'' = (''x'':''xs'')}}. हम पहले की प्रकार आगे बढ़ते हैं:
 :<math>\begin{array}{rll}
@@ Line 70: / Line 69: @@
 &= \operatorname{len}(L +\!+\ M)
 \end{array}</math>
-इस प्रकार, संरचनात्मक प्रेरण से, हम उसे प्राप्त करते हैं {{math|''P''(''L'')}} सभी सूचियों के लिए सत्य है {{mvar|L}}.
+इस प्रकार, संरचनात्मक प्रेरण से, हम उसे प्राप्त करते हैं कि सूचि {{math|''P''(''L'')}} सभी {{mvar|L}} सूचियों के लिए सत्य है.
 ==सुव्यवस्थित==
-जिस प्रकार मानक गणितीय प्रेरण [[सुव्यवस्थित सिद्धांत]] के समतुल्य है, उसी प्रकार संरचनात्मक प्रेरण भी सुव्यवस्थित सिद्धांत के समतुल्य है। यदि निश्चित प्रकार की सभी संरचनाओं का सेट अच्छी तरह से स्थापित आंशिक क्रम को स्वीकार करता है, तो प्रत्येक गैर-रिक्त उपसमुच्चय में न्यूनतम तत्व होना चाहिए। (यह अच्छी तरह से स्थापित की परिभाषा है।) इस संदर्भ में लेम्मा का महत्व यह है कि यह हमें यह निष्कर्ष निकालने की अनुमति देता है कि यदि प्रमेय के कोई प्रति-उदाहरण हैं जिन्हें हम साबित करना चाहते हैं, तो न्यूनतम प्रति-उदाहरण होना चाहिए। यदि हम दिखा सकते हैं कि न्यूनतम प्रति-उदाहरण का अस्तित्व और भी छोटे प्रति-उदाहरण का तात्पर्य है, तो हमारे पास विरोधाभास है (क्योंकि न्यूनतम प्रति-उदाहरण न्यूनतम नहीं है) और इसलिए प्रति-उदाहरण का सेट खाली होना चाहिए।
+सामान्य गणितीय आनुवंशिकता की तरह ही संरचनात्मक आनुवंशिकता भी किसी [[सुव्यवस्थित सिद्धांत]] के समान होती है। अगर किसी विशेष प्रकार की सभी संरचनाओं का समुच्चय वेल-संविदित आंशिक क्रम स्वीकार करता है, तो हर गैर-खाली उपसमुच्चय का न्यूनतम तत्त्व होना चाहिए। (यह "वेल-संविदित" के परिभाषा है।) इस संबंध में यह लेख का महत्व है कि यह हमें सिद्ध करने में मदद करता है कि यदि हमारे प्रमाण को खंडन करने के लिए कोई विरोधी उदाहरण होता है, तो उसका न्यूनतम विरोधी उदाहरण होना चाहिए। यदि हम दिखा सकते हैं कि न्यूनतम विरोधी उदाहरण से भी और छोटे विरोधी उदाहरण का सम्भव होना संभव नहीं है, तो हमारे पास विरोधाभास हो जाता है (क्योंकि न्यूनतम विरोधी उदाहरण न्यूनतम नहीं होता है) और इस तरह विरोधी उदाहरणों का समुच्चय खाली होना चाहिए।
-इस प्रकार के तर्क के उदाहरण के रूप में, सभी बाइनरी पेड़ों के सेट पर विचार करें। हम दिखाएंगे कि पूर्ण बाइनरी पेड़ में पत्तियों की संख्या आंतरिक नोड्स की संख्या से अधिक है। मान लीजिए कि प्रति उदाहरण है; तो आंतरिक नोड्स की न्यूनतम संभव संख्या वाला मौजूद होना चाहिए। यह प्रति उदाहरण, {{mvar|C}}, है {{mvar|n}} आंतरिक नोड्स और {{mvar|l}} पत्ते, कहाँ {{math|1=''n'' + 1 ≠ ''l''}}. इसके अतिरिक्त, {{mvar|C}} गैर-तुच्छ होना चाहिए, क्योंकि तुच्छ वृक्ष के पास है {{math|1=''n'' = 0}} और {{math|1=''l'' = 1}} और इसलिए यह प्रतिउदाहरण नहीं है। {{mvar|C}} इसलिए कम से कम पत्ती होती है जिसका मूल नोड आंतरिक नोड होता है। इस पत्ते और उसके मूल नोड को पेड़ से हटा दें, पत्ती के सहोदर नोड को उस स्थान पर पदोन्नत करें जिस पर पहले उसके मूल नोड का कब्ज़ा था। इससे दोनों कम हो जाते हैं {{mvar|n}} और {{mvar|l}} 1 से, तो नया पेड़ भी है {{math|1=''n'' + 1 ≠ ''l''}} और इसलिए यह छोटा प्रति उदाहरण है। लेकिन परिकल्पना से, {{mvar|C}} पहले से ही सबसे छोटा प्रति उदाहरण था; इसलिए, यह धारणा कि शुरुआत में कोई प्रति-उदाहरण मौजूद थे, ग़लत रहा होगा। यहाँ 'छोटा' द्वारा निहित आंशिक क्रम वही है जो यही कहता है {{math|''S'' < ''T''}} जब कभी भी {{mvar|S}} से कम नोड्स हैं {{mvar|T}}.
+उदाहरण के रूप में, सभी बाइनरी ट्री का समुच्चय ले लेते हैं। हम दिखाएंगे कि पूर्ण बाइनरी ट्री में पत्तियों की संख्या, आंतरिक नोड्स की संख्या से अधिक है। मान लें कि कोई विरोधी उदाहरण है; इससे तो निश्चित रूप से उसमें आंतरिक नोड्स की सबसे कम संख्या होगी। इस विरोधी उदाहरण, {{mvar|C}}, में {{mvar|n}} आंतरिक नोड्स और {{mvar|l}} पत्तियाँ होती हैं, जहां {{math|1=''n'' + 1 ≠ ''l''}}। इसके अतिरिक्त, {{mvar|C}} गैर-तुच्छ होना चाहिए, क्योंकि साधारण वृक्ष में n = 0 और l = 1 होता है और इसलिए यह विपरीत उदाहरण नहीं होता है। इसलिए {{mvar|C}} में कम से कम पत्ती होती है जिसका मूल नोड आंतरिक नोड होता है। इस पत्ते और उसके मूल नोड को वृक्ष से हटा दें, पत्ती के सहोदर नोड को उस स्थान पर पदोन्नत करें जिस पर पहले उसके मूल नोड का प्रभुत्व था। इससे , {{mvar|n}} और {{mvar|l}} 1 से दोनों कम हो जाते हैं, इसलिए नया वृक्ष भी {{math|1=''n'' + 1 ≠ ''l''}} होगा और इसलिए यह छोटा विपरीत उदाहरण है। लेकिन परिकल्पना से, {{mvar|C}} पहले से ही सबसे छोटा विपरीत उदाहरण था; इसलिए, यह धारणा कि प्रारंभिक में कोई विपरीत उदाहरण उपस्थित थे, ग़लत रहा होगा। यहाँ 'छोटा' केद्वारा निहित आंशिक क्रम वही है जो यही कहता है कि {{math|''S'' < ''T''}} जबकि {{mvar|S}} में तत्वों की संख्या {{mvar|T}} से कम होती है।
 ==यह भी देखें==
@@ Line 93: / Line 92: @@
 {{Mathematical logic}}
-[[Category: ग्राफ सिद्धांत]] [[Category: कंप्यूटर विज्ञान में तर्क]] [[Category: गणितीय प्रेरण]] [[Category: गणितीय तर्क]] [[Category: गणितीय प्रमाण]] [[Category: कल्याण]]
+[[Category:CS1]]
+[[Category:Collapse templates]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 25/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Mathematics navigational boxes]]
+[[Category:Navbox orphans]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with empty portal template]]
+[[Category:Pages with script errors]]
+[[Category:Philosophy and thinking navigational boxes]]
+[[Category:Portal-inline template with redlinked portals]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Translated in Hindi]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:कंप्यूटर विज्ञान में तर्क]]
+[[Category:कल्याण]]
+[[Category:गणितीय तर्क]]
+[[Category:गणितीय प्रमाण]]
+[[Category:गणितीय प्रेरण]]
+[[Category:ग्राफ सिद्धांत]]

Anonymous

Search

संरचनात्मक प्रेरण: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 13:59, 14 August 2023

Contents

उदाहरण

सुव्यवस्थित

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

संरचनात्मक प्रेरण: Difference between revisions

Latest revision as of 13:59, 14 August 2023

उदाहरण

सुव्यवस्थित

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories