अध्ययन के उद्देश्य:
इस कक्षा के अंत में, छात्र सक्षम होगा:

1. समझें अभिव्यक्तियों की जटिलता पर प्रेरण की अवधारणा।
2. लागू करें सूत्रों की जटिलता पर गणितीय प्रेरण को प्रस्तावना तर्कशास्त्र में।
3. समझें जटिलता पर प्रेरण द्वारा प्रमाण और इसे प्रस्तावना तर्कशास्त्र में कैसे लागू किया जाता है।

विषय सूची
जटिलता पर प्रेरण
एक सरल उदाहरण: प्रतिस्थापन प्रमेय

जटिलता पर प्रेरण

मान लीजिए कि हम यह साबित करना चाहते हैं कि एक गुण \mathcal{P} किसी भी अभिव्यक्ति F के लिए सत्य है। इसे साबित करने का एक तरीका यह है कि गणितीय प्रेरण के एक प्रकार का उपयोग किया जाए, जिसे “अभिव्यक्तियों की जटिलता पर प्रेरण” कहा जाता है। यह निम्नलिखित चरणों के माध्यम से किया जाता है:

• पहले हम दिखाते हैं कि सभी परमाणु अभिव्यक्तियाँ उस गुण को संतुष्ट करती हैं (यह पारंपरिक प्रेरण में n=1 के मामले के बराबर है)।
• फिर, मानते हुए कि यह गुण किसी भी अभिव्यक्ति F और G के लिए सत्य है, हम यह साबित करते हैं कि यह गुण F\downarrow G प्रकार की अभिव्यक्तियों के लिए भी सत्य है; या इसके समतुल्य, \neg F और निम्नलिखित में से किसी एक के लिए: F\wedge G, F\vee G, F\rightarrow G.

यदि हम इसे कर लेते हैं, तो हम निष्कर्ष निकालते हैं कि गुण \mathcal{P} सभी प्रस्तावना तर्कशास्त्र अभिव्यक्तियों के लिए सत्य है। इसे “अभिव्यक्तियों की जटिलता पर गणितीय प्रेरण” कहा जाता है।

एक सरल उदाहरण: प्रतिस्थापन प्रमेय

फार्मूलों की जटिलता पर प्रेरण कैसे किया जाता है, इसे समझने के लिए, हम प्रतिस्थापन प्रमेय की समीक्षा करेंगे।

मान लीजिए कि F\equiv G. H एक अभिव्यक्ति है जो F को उप-अभिव्यक्ति के रूप में शामिल करता है और H^\prime वह अभिव्यक्ति है जो F की सभी घटनाओं को G से प्रतिस्थापित करके प्राप्त की जाती है, तब H\equiv H^\prime.

सूत्रों की जटिलता पर प्रेरण द्वारा प्रमाण

जटिलता पर प्रेरण द्वारा प्रमाण का मतलब दो चीजों को साबित करना है: 1) एक प्रारंभिक मामला (परमाणु सूत्रों के लिए) और 2) प्रेरणीय चरण (यदि यह किसी भी अभिव्यक्ति F और G के लिए सत्य है, तो यह F\downarrow G के लिए भी सत्य है, या सरल रूप में: यह \neg F और निम्नलिखित में से कम से कम एक के लिए सत्य है: F\vee G, F\wedge G, F\rightarrow G या F\leftrightarrow G)।

मान लीजिए कि H एक परमाणु अभिव्यक्ति है, F H की उप-अभिव्यक्ति है और F\equiv G. यदि H^\prime H में सभी उप-अभिव्यक्तियों F को प्रतिस्थापित करने का परिणाम है, तो चूंकि H परमाणु है, यह होगा कि H^\prime \equiv G। दूसरी ओर, चूंकि H परमाणु है और F इसकी उप-अभिव्यक्ति है, तो H\equiv F। अंततः, हमें मिलेगा:

H\equiv F \equiv G \equiv H^\prime

इस प्रकार, परमाणु अभिव्यक्तियों के लिए प्रारंभिक मामला सिद्ध हो गया।

अब, प्रेरणीय चरण की समीक्षा करें।

प्रेरण परिकल्पना

मान लीजिए कि यह प्रमेय दो अभिव्यक्तियों H_1 और H_2 के लिए सत्य है, जिनमें से प्रत्येक में F उप-अभिव्यक्ति के रूप में शामिल है और F \equiv G. तो यदि H_1^\prime H_1 में सभी F को G से प्रतिस्थापित करने का परिणाम है और H_2^\prime H_2 में सभी F को G से प्रतिस्थापित करने का परिणाम है, तो हमें मिलेगा कि H_1\equiv H_1^\prime और H_2\equiv H_2^\prime।

प्रेरणीय चरण

यहां हम जांचेंगे कि क्या प्रेरण परिकल्पना के परिणामस्वरूप यह प्रमेय \neg H_1 (या \neg H_2, किसी भी एक के लिए) और निम्नलिखित में से कम से कम एक के लिए सत्य है: H_1 \wedge H_2, H_1 \vee H_2, H_1 \rightarrow H_2.

यदि H:= \neg H_1, तो प्रेरण परिकल्पना के अनुसार, H\equiv \neg H_1^\prime=: H^\prime होगा, जहां H^\prime H में सभी F को G से प्रतिस्थापित करने का परिणाम है। अतः, H\equiv H^\prime.

इसी प्रकार, यदि H:= H_1 \wedge H_2, तो प्रेरण परिकल्पना के अनुसार, H\equiv H_1^\prime \wedge H_2 \equiv H_1^\prime \wedge H_2^\prime =: H^\prime होगा, जहां H^\prime H में सभी F को G. से प्रतिस्थापित करने का परिणाम है। अतः H\equiv H^\prime.

इस प्रकार प्रेरण पूरा हो जाता है और प्रतिस्थापन प्रमेय सभी प्रस्तावना तर्कशास्त्र अभिव्यक्तियों के लिए सत्य है।

इस प्रकार की प्रेरण लागू करने पर, यह सुनिश्चित किया जा सकता है कि एक गुण किसी भी तर्क प्रणाली के सभी अभिव्यक्तियों के लिए सत्य रहेगा, जो प्रस्तावना तर्कशास्त्र में कठोर प्रमाण संरचना के लिए विशेष रूप से उपयोगी है। इसके अलावा, इसकी उपयोगिता कृत्रिम बुद्धिमत्ता और सॉफ्टवेयर विकास जैसे क्षेत्रों में भी विस्तारित होती है, जहां तर्क प्रणालियों का सत्यापन महत्वपूर्ण होता है। इस तकनीक के माध्यम से, प्रमाणों को स्वचालित किया जा सकता है और जटिल अभिव्यक्तियों की संगति सुनिश्चित की जा सकती है, जिससे त्रुटियों की संभावना कम हो जाती है और उन वातावरणों में सटीकता बढ़ जाती है जो गणितीय और तार्किक मान्यताओं पर निर्भर होते हैं।