संरचनात्मक प्रेरण

संरचनात्मक प्रेरण प्रमाण विधि है जिसका उपयोग गणितीय तर्क (जैसे Ł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) के संरचनात्मक अभिवादन को निम्नलिखित ढंग से पूरा किया जाता है:

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

उदाहरण

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

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

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

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

• सरलतम मामले में, वृक्ष ही व्यक्ति को दिखाता है और इसलिए पीढ़ियों को; ऐसे वृक्ष के लिए गुणवत्ता सत्य है, क्योंकि 1 ≤ 2¹ − 1 है।
• विकल्प से, वृक्ष व्यक्ति और उनके माता-पिता के वृक्षों को दिखाता है। क्योंकि उनका प्रत्येक वृक्ष पूरे वृक्ष का उपसंरचना है, इसलिए इसे सिद्ध करने के लिए अनुमान लगाया जा सकता है कि इस गुणवत्ता को प्रमाणित किया जा सकता है (जिसे अनुवंशिक हाइपोथिसिस कहते हैं)। इसका मतलब, p ≤ 2^g − 1 और q ≤ 2^h − 1 को अनुमान लगाया जा सकता है, जहां g और h पिता के उपवृक्ष की पीढ़ियों की संख्या को दर्शाते हैं, और p और q उन व्यक्तियों की संख्या को दर्शाते हैं जिन्हें वे दिखाते हैं।
  • यदि g ≤ 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 ≤ g, हो, तो पूरा वृक्ष 1 + g पीढ़ियों पर फैलता है और p + q + 1 ≤ 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 ≠ l। इसके अतिरिक्त, C गैर-तुच्छ होना चाहिए, क्योंकि साधारण वृक्ष में n = 0 और l = 1 होता है और इसलिए यह विपरीत उदाहरण नहीं होता है। इसलिए C में कम से कम पत्ती होती है जिसका मूल नोड आंतरिक नोड होता है। इस पत्ते और उसके मूल नोड को वृक्ष से हटा दें, पत्ती के सहोदर नोड को उस स्थान पर पदोन्नत करें जिस पर पहले उसके मूल नोड का प्रभुत्व था। इससे , n और l 1 से दोनों कम हो जाते हैं, इसलिए नया वृक्ष भी n + 1 ≠ 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).