हरब्रांडीकरण: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Proof of Herbrand's theorem}} | {{Short description|Proof of Herbrand's theorem}} | ||
तार्किक सूत्र का | तार्किक सूत्र का '''हर्ब्रांडाइजेशन''' ([[जैक्स हेरब्रांड]] के नाम पर) ऐसा निर्माण है जो सूत्र के [[ शोलेमाइजेशन |स्कोलेमाइजेशन]] के लिए [[द्वैत (गणित)]] है। [[ थोरल्फ़ स्कोलेम |थोरल्फ़ स्कोलेम]] ने लोवेनहेम-स्कोलेम प्रमेय (स्कोलेम1920) के अपने प्रमाण के भाग के रूप में [[प्रीनेक्स फॉर्म|प्रीनेक्स प्रारूप]] में सूत्रों के स्कोलेमाइजेशन पर विचार किया था। हेरब्रांड ने हर्ब्रांडाइजेशन की इस दोहरी धारणा के साथ कार्य किया, जिसे हेरब्रांड के प्रमेय (प्रमाण सिद्धांत) को सिद्ध करने के लिए गैर-प्रीनेक्स सूत्रों पर भी प्रारंभ करने के लिए सामान्यीकृत किया गया। | ||
परिणामी सूत्र आवश्यक रूप से मूल सूत्र के | परिणामी सूत्र आवश्यक रूप से मूल सूत्र के [[तार्किक तुल्यता|समतुल्य]] नहीं है। स्कोलेमाइज़ेशन के जैसे, जो केवल [[संतुष्टि]] को स्थिर रखता है, हर्ब्रांडाइज़ेशन स्कोलेमाइज़ेशन की दोहरी [[वैधता (तर्क)]] को संरक्षित करता है: परिणामी सूत्र तभी मान्य होता है जब मूल हो। | ||
==परिभाषा एवं उदाहरण== | ==परिभाषा एवं उदाहरण== | ||
मान लीजिये [[प्रथम-क्रम तर्क]] की भाषा में <math>F</math> सूत्र है। <math>F</math> में ऐसा कोई चर नहीं है जो दो भिन्न-भिन्न परिमाणक घटनाओं से बंधा हो, कोई भी चर बंधा हुआ और मुक्त दोनों प्रकार से नहीं होता है। (इन नियमों को सुनिश्चित करने के लिए, <math>F</math> को दोबारा लिखा जा सकता है, इस प्रकार से कि परिणाम समतुल्य सूत्र हो)। | |||
हर्ब्रांडाइजेशन फिर <math>F</math> इस प्रकार प्राप्त किया जाता है: | |||
* | * सर्वप्रथम, निरंतर प्रतीकों द्वारा <math>F</math> को किसी भी फ्री चर को परिवर्तित कर सकते है। . | ||
* दूसरा, | * दूसरा, चर पर सभी परिमाणक को विस्थापित कर दें जो या तो (1) सार्वभौमिक रूप से परिमाणित हैं और निषेध चिह्नों की सम संख्या के भीतर हैं, या (2) अस्तित्वगत रूप से परिमाणित हैं और विषम संख्या में निषेध चिह्नों के भीतर हैं। | ||
* अंत में, ऐसे प्रत्येक | * अंत में, ऐसे प्रत्येक चर को परिवर्तित कर सकते है। <math>v</math> फलन प्रतीक के साथ <math>f_v(x_1,\dots,x_k)</math>, जहाँ <math>x_1,\dots,x_k</math> वे चर हैं जो अभी भी परिमाणित हैं, और जिनके परिमाणक <math>v</math> नियंत्रित होते हैं। | ||
उदाहरण के लिए, सूत्र पर विचार | उदाहरण के लिए, सूत्र पर विचार <math>F := \forall y \exists x [R(y,x) \wedge \neg\exists z S(x,z)]</math> किया जाता है, प्रतिस्थापित करने के लिए कोई निःशुल्क चर नहीं हैं। चर <math>y,z</math> वे प्रकार हैं जिन पर हम दूसरे चरण के लिए विचार करते हैं, इसलिए हम परिमाणक विस्थापित कर देते हैं <math>\forall y</math> और <math>\exists z</math> अंत में, हम फिर प्रतिस्थापित करते हैं <math>y</math> स्थिरांक के साथ <math>c_y</math> (चूँकि शासन करने वाला कोई अन्य परिमाणक <math>y</math>नहीं था), और <math>z</math> को प्रतिस्थापित करते हैं फलन <math>f_z(x)</math> प्रतीक के साथ प्रतिस्थापित करते हैं: | ||
: <math> F^H = \exists x [R(c_y,x) \wedge \neg S(x,f_z(x))]. </math> | : <math> F^H = \exists x [R(c_y,x) \wedge \neg S(x,f_z(x))]. </math> | ||
किसी सूत्र का स्कोलेमाइज़ेशन समान रूप से प्राप्त किया जाता है, | किसी सूत्र का स्कोलेमाइज़ेशन समान रूप से प्राप्त किया जाता है, अतिरिक्त इसके कि ऊपर के दूसरे चरण में, हम उन चरों पर परिमाणक विस्थापित कर देंगे जो या तो (1) अस्तित्वगत रूप से परिमाणित हैं और निषेधों की सम संख्या के भीतर हैं, या (2) सार्वभौमिक रूप से परिमाणित हैं और विषम संख्या के भीतर हैं नकारों का इस प्रकार, उसी पर विचार किया जा रहा है ऊपर से <math>F</math>, इसका स्कोलेमाइजेशन होगा: | ||
: <math> F^S = \forall y [R(y,f_x(y)) \wedge \neg\exists z S(f_x(y),z)]. </math> | : <math> F^S = \forall y [R(y,f_x(y)) \wedge \neg\exists z S(f_x(y),z)]. </math> | ||
इन निर्माणों के महत्व को | इन निर्माणों के महत्व को अध्ययन के लिए, हेरब्रांड का प्रमेय (प्रमाण सिद्धांत) या लोवेनहेम-स्कोलेम प्रमेय देखें। | ||
== यह भी देखें == | == यह भी देखें == | ||
| Line 29: | Line 29: | ||
* Herbrand, J. "Investigations in proof theory: The properties of true propositions". (In van Heijenoort 1967, 525-81.) | * Herbrand, J. "Investigations in proof theory: The properties of true propositions". (In van Heijenoort 1967, 525-81.) | ||
* [[Jean van Heijenoort|van Heijenoort, J.]] ''From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931''. Harvard University Press, 1967. | * [[Jean van Heijenoort|van Heijenoort, J.]] ''From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931''. Harvard University Press, 1967. | ||
[[Category:Created On 07/07/2023]] | [[Category:Created On 07/07/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:तर्क]] | |||
[[Category:सामान्य रूप (तर्क)]] | |||
Latest revision as of 10:03, 2 August 2023
तार्किक सूत्र का हर्ब्रांडाइजेशन (जैक्स हेरब्रांड के नाम पर) ऐसा निर्माण है जो सूत्र के स्कोलेमाइजेशन के लिए द्वैत (गणित) है। थोरल्फ़ स्कोलेम ने लोवेनहेम-स्कोलेम प्रमेय (स्कोलेम1920) के अपने प्रमाण के भाग के रूप में प्रीनेक्स प्रारूप में सूत्रों के स्कोलेमाइजेशन पर विचार किया था। हेरब्रांड ने हर्ब्रांडाइजेशन की इस दोहरी धारणा के साथ कार्य किया, जिसे हेरब्रांड के प्रमेय (प्रमाण सिद्धांत) को सिद्ध करने के लिए गैर-प्रीनेक्स सूत्रों पर भी प्रारंभ करने के लिए सामान्यीकृत किया गया।
परिणामी सूत्र आवश्यक रूप से मूल सूत्र के समतुल्य नहीं है। स्कोलेमाइज़ेशन के जैसे, जो केवल संतुष्टि को स्थिर रखता है, हर्ब्रांडाइज़ेशन स्कोलेमाइज़ेशन की दोहरी वैधता (तर्क) को संरक्षित करता है: परिणामी सूत्र तभी मान्य होता है जब मूल हो।
परिभाषा एवं उदाहरण
मान लीजिये प्रथम-क्रम तर्क की भाषा में सूत्र है। में ऐसा कोई चर नहीं है जो दो भिन्न-भिन्न परिमाणक घटनाओं से बंधा हो, कोई भी चर बंधा हुआ और मुक्त दोनों प्रकार से नहीं होता है। (इन नियमों को सुनिश्चित करने के लिए, को दोबारा लिखा जा सकता है, इस प्रकार से कि परिणाम समतुल्य सूत्र हो)।
हर्ब्रांडाइजेशन फिर इस प्रकार प्राप्त किया जाता है:
- सर्वप्रथम, निरंतर प्रतीकों द्वारा को किसी भी फ्री चर को परिवर्तित कर सकते है। .
- दूसरा, चर पर सभी परिमाणक को विस्थापित कर दें जो या तो (1) सार्वभौमिक रूप से परिमाणित हैं और निषेध चिह्नों की सम संख्या के भीतर हैं, या (2) अस्तित्वगत रूप से परिमाणित हैं और विषम संख्या में निषेध चिह्नों के भीतर हैं।
- अंत में, ऐसे प्रत्येक चर को परिवर्तित कर सकते है। फलन प्रतीक के साथ , जहाँ वे चर हैं जो अभी भी परिमाणित हैं, और जिनके परिमाणक नियंत्रित होते हैं।
उदाहरण के लिए, सूत्र पर विचार किया जाता है, प्रतिस्थापित करने के लिए कोई निःशुल्क चर नहीं हैं। चर वे प्रकार हैं जिन पर हम दूसरे चरण के लिए विचार करते हैं, इसलिए हम परिमाणक विस्थापित कर देते हैं और अंत में, हम फिर प्रतिस्थापित करते हैं स्थिरांक के साथ (चूँकि शासन करने वाला कोई अन्य परिमाणक नहीं था), और को प्रतिस्थापित करते हैं फलन प्रतीक के साथ प्रतिस्थापित करते हैं:
किसी सूत्र का स्कोलेमाइज़ेशन समान रूप से प्राप्त किया जाता है, अतिरिक्त इसके कि ऊपर के दूसरे चरण में, हम उन चरों पर परिमाणक विस्थापित कर देंगे जो या तो (1) अस्तित्वगत रूप से परिमाणित हैं और निषेधों की सम संख्या के भीतर हैं, या (2) सार्वभौमिक रूप से परिमाणित हैं और विषम संख्या के भीतर हैं नकारों का इस प्रकार, उसी पर विचार किया जा रहा है ऊपर से , इसका स्कोलेमाइजेशन होगा:
इन निर्माणों के महत्व को अध्ययन के लिए, हेरब्रांड का प्रमेय (प्रमाण सिद्धांत) या लोवेनहेम-स्कोलेम प्रमेय देखें।
यह भी देखें
संदर्भ
- Skolem, T. "Logico-combinatorial investigations in the satisfiability or provability of mathematical propositions: A simplified proof of a theorem by L. Löwenheim and generalizations of the theorem". (In van Heijenoort 1967, 252-63.)
- Herbrand, J. "Investigations in proof theory: The properties of true propositions". (In van Heijenoort 1967, 525-81.)
- van Heijenoort, J. From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931. Harvard University Press, 1967.
