बूलियन बीजगणित के लिए न्यूनतम स्वयंसिद्ध: Difference between revisions
From Vigyanwiki
(Created page with "गणितीय तर्क में, बूलियन बीजगणित के लिए न्यूनतम स्वयंसिद्ध वे धा...") |
(change some english word in pure hindi and minor change.) |
||
| Line 1: | Line 1: | ||
[[गणितीय तर्क]] में, [[बूलियन बीजगणित]] के लिए न्यूनतम स्वयंसिद्ध वे धारणाएँ हैं जो बूलियन बीजगणित (या प्रस्तावक कलन) के स्वयंसिद्धों के समतुल्य हैं, जिन्हें यथासंभव छोटा चुना | [[गणितीय तर्क]] में, [[बूलियन बीजगणित]] के लिए न्यूनतम स्वयंसिद्ध वे धारणाएँ हैं जो बूलियन बीजगणित (या प्रस्तावक कलन) के स्वयंसिद्धों के समतुल्य हैं, जिन्हें यथासंभव छोटा होने के लिए चुना गया है। उदाहरण के लिए, यदि कोई क्रम विनिमेयता को हल्के में लेना चाहता है,<ref>{{cite web |last1=Wolfram |first1=Stephen |title=तर्क, व्याख्या और समझ का भविष्य|url=https://writings.stephenwolfram.com/2018/11/logic-explainability-and-the-future-of-understanding/ |website=Stephen Worfram Writings}}</ref> छह एनएएनडी संचालन और तीन चर के साथ एक स्वयंसिद्ध बूलियन बीजगणित के समतुल्य है: | ||
: <math>((a\mid b)\mid c) \mid (a\mid((a\mid c)\mid a)) = c</math> | : <math>((a\mid b)\mid c) \mid (a\mid((a\mid c)\mid a)) = c</math> | ||
जहां ऊर्ध्वाधर पट्टी | जहां ऊर्ध्वाधर पट्टी एनएएनडी तार्किक संचालन का प्रतिनिधित्व करती है (जिसे [[शेफ़र लाइन|शेफ़र स्ट्रोक]] के रूप में भी जाना जाता है)। | ||
यह [[स्टीफन वोल्फ्राम]] द्वारा पहचानी गई इस संपत्ति के लिए 25 | यह [[स्टीफन वोल्फ्राम]] द्वारा पहचानी गई इस संपत्ति के लिए 25 प्रत्याशी स्वयंसिद्धों में से एक है, जिसमें 15 तत्वों (दर्पण छवियों को छोड़कर) से कम या समतुल्य लंबाई की शेफ़र पहचान की गणना की गई है, जिनके पास चार या उससे कम चर के साथ कोई गैर-अनुवांशिक मॉडल नहीं है, और पहली बार [[विलियम मैकक्यून]], [[ब्रैंडन फिटेलसन]], और [[लैरी वोस]] द्वारा समकक्ष प्रमाणित किया गया था।<ref>{{cite book |last1=Wolfram |first1=Stephen |author-link=Stephen Wolfram |title=[[A New Kind of Science]] |date=2002 |publisher=Wolfram Media |isbn=978-1579550080 }}</ref><ref name=mccune>{{citation | ||
| last1 = McCune | first1 = William |author-link1 = William McCune | | last1 = McCune | first1 = William |author-link1 = William McCune | ||
| last2 = Veroff | first2 = Robert | | last2 = Veroff | first2 = Robert | ||
| Line 18: | Line 18: | ||
| title = Short single axioms for Boolean algebra | | title = Short single axioms for Boolean algebra | ||
| volume = 29 | | volume = 29 | ||
| year = 2002| s2cid = 207582048 }}</ref> वोल्फ्राम से जुड़ी साइट [[मैथवर्ल्ड]] ने | | year = 2002| s2cid = 207582048 }}</ref> वोल्फ्राम से जुड़ी साइट [[मैथवर्ल्ड]] ने स्वयंसिद्ध को वोल्फ्राम स्वयंसिद्ध नाम दिया है।<ref>{{MathWorld|id=WolframAxiom|title=Wolfram Axiom|author=Rowland, Todd|author2=Weisstein, Eric W.}}</ref> मैकक्यून एट अल विच्छेदन और निषेध के आधार पर बूलियन बीजगणित के लिए एक लंबा एकल स्वयंसिद्ध भी पाया गया।<ref name=mccune/> | ||
1933 में, [[एडवर्ड वर्मिली हंटिंगटन]] ने स्वयंसिद्ध की पहचान की | 1933 में, [[एडवर्ड वर्मिली हंटिंगटन]] ने स्वयंसिद्ध की पहचान की | ||
:<math>{\neg({\neg x} \lor {y})} \lor {\neg({\neg x} \lor {\neg y})} = x</math> | :<math>{\neg({\neg x} \lor {y})} \lor {\neg({\neg x} \lor {\neg y})} = x</math> | ||
बूलियन बीजगणित के समतुल्य होने के नाते, जब इसे तार्किक | बूलियन बीजगणित के समतुल्य होने के नाते, जब इसे तार्किक ओआर ऑपरेशन की क्रमविनिमेयता के साथ जोड़ा जाता है, <math>x \lor y = y \lor x</math>, और साहचर्य की धारणा, <math>(x \lor y) \lor z = x \lor (y \lor z)</math>। <ref>{{cite journal|last=Huntington |first=E. V. |title=व्हाइटहेड और रसेल के ''प्रिंसिपिया मैथमेटिका'' के विशेष संदर्भ में, तर्क के बीजगणित के लिए स्वतंत्र अभिधारणाओं के नए सेट|journal=[[Trans. Amer. Math. Soc.]] |volume=25 |pages=247–304 |year=1933}}</ref> [[हर्बर्ट रॉबिंस]] ने अनुमान लगाया कि हंटिंगटन के स्वयंसिद्ध को प्रतिस्थापित किया जा सकता है | ||
:<math>\neg(\neg(x \lor y) \lor \neg(x \lor {\neg y})) = x,</math> | :<math>\neg(\neg(x \lor y) \lor \neg(x \lor {\neg y})) = x,</math> | ||
जिसके लिए तार्किक निषेध ऑपरेटर | जिसके लिए तार्किक निषेध ऑपरेटर <math>\neg</math> के एक कम उपयोग की आवश्यकता होती है। न तो रॉबिंस और न ही हंटिंगटन इस अनुमान को सिद्ध कर सके; न ही [[अल्फ्रेड टार्स्की]], जिन्होंने बाद में इसमें काफी रुचि ली। अंततः 1996 में प्रमेय सिद्ध सॉफ़्टवेयर की सहायता से यह अनुमान सिद्ध हो गया।<ref>{{cite book |last1=Henkin |first1=Leon |author-link1=Leon Henkin |last2=Monk |first2=J. Donald |last3=Tarski |first3=Alfred |author-link3=Alfred Tarski |title=बेलनाकार बीजगणित, भाग I|publisher=[[North-Holland Publishing Company|North-Holland]] |isbn=978-0-7204-2043-2 |year=1971 |oclc=1024041028 |url-access=registration |url=https://archive.org/details/cylindricalgebra0000henk }}</ref><ref>{{cite journal|last=McCune |first=William |title=रॉबिन्स समस्या का समाधान|journal=[[Journal of Automated Reasoning]] |volume=19 |year=1997 |issue=3 |pages=263–276 |doi=10.1023/A:1005843212881|s2cid=30847540 }}</ref><ref>{{cite news|last=Kolata |first=Gina |author-link=Gina Kolata |title=कंप्यूटर गणित प्रमाण तर्क शक्ति को दर्शाता है|work=[[The New York Times]] |date=1996-12-10 |url=https://archive.nytimes.com/www.nytimes.com/library/cyber/week/1210math.html}} For errata, see {{cite web|url=http://www.mcs.anl.gov/home/mccune/nyt-corrections.html |archive-url=https://web.archive.org/web/19970605011316/http://www.mcs.anl.gov/home/mccune/nyt-corrections.html |date=1997-01-23 |archive-date=1997-06-05 |last=McCune |first=William |website=[[Argonne National Laboratory]] |title=Comments on Robbins Story}}</ref> इस प्रमाण ने स्थापित किया कि रॉबिंस स्वयंसिद्ध, साहचर्यता और क्रमविनिमेयता के साथ मिलकर, बूलियन बीजगणित के लिए 3-आधार बनाते हैं। 2-आधार का अस्तित्व 1967 में [[कैरव आर्थर मेरेडिथ]] द्वारा स्थापित किया गया था:<ref>{{cite journal|last1=Meredith |first1=C. A. |author-link1=Carew Arthur Meredith |last2=Prior |first2=A. N. |author-link2=Arthur Prior |title=समतामूलक तर्क|journal=[[Notre Dame J. Formal Logic]] |year=1968 |volume=9 |issue=3 |pages=212–226 |doi=10.1305/ndjfl/1093893457 |mr=0246753|doi-access=free }}</ref> | ||
:<math>\neg({\neg x} \lor y) \lor x = x,</math> | :<math>\neg({\neg x} \lor y) \lor x = x,</math> | ||
:<math>\neg({\neg x} \lor y) \lor (z \lor y) = y \lor (z \lor x).</math> | :<math>\neg({\neg x} \lor y) \lor (z \lor y) = y \lor (z \lor x).</math>। | ||
अगले वर्ष, मेरेडिथ को शेफ़र स्ट्रोक के संदर्भ में 2-आधार मिला:<ref>{{cite journal|last=Meredith |first=C. A. |author-link1=Carew Arthur Meredith |title=शेफ़र स्ट्रोक के लिए समीकरणात्मक अभिधारणाएँ|journal=[[Notre Dame J. Formal Logic]] |volume=10 |year=1969 |issue=3 |pages=266–270 |doi=10.1305/ndjfl/1093893713 |mr=0245423|doi-access=free }}</ref> | अगले वर्ष, मेरेडिथ को शेफ़र स्ट्रोक के संदर्भ में 2-आधार मिला:<ref>{{cite journal|last=Meredith |first=C. A. |author-link1=Carew Arthur Meredith |title=शेफ़र स्ट्रोक के लिए समीकरणात्मक अभिधारणाएँ|journal=[[Notre Dame J. Formal Logic]] |volume=10 |year=1969 |issue=3 |pages=266–270 |doi=10.1305/ndjfl/1093893713 |mr=0245423|doi-access=free }}</ref> | ||
:<math>(x\mid x) \mid (y\mid x) = x,</math> | :<math>(x\mid x) \mid (y\mid x) = x,</math> | ||
:<math>x|(y\mid(x\mid z)) = ((z\mid y)\mid y)\mid x.</math> | :<math>x|(y\mid(x\mid z)) = ((z\mid y)\mid y)\mid x.</math>। | ||
1973 में, पद्मनाभन और क्वेकेनबश ने एक ऐसी विधि का प्रदर्शन किया, जो सिद्धांत रूप में, बूलियन बीजगणित के लिए 1-आधार प्रदान करेगी।<ref>{{cite journal |last1=Padmanabhan |first1=R. |last2=Quackenbush |first2=R. W. |title=वितरणात्मक सर्वांगसमताओं के साथ बीजगणित के समीकरणात्मक सिद्धांत|journal=[[Proc. Amer. Math. Soc.]] |date=1973 |volume=41 |issue=2 |pages=373–377 |doi=10.1090/S0002-9939-1973-0325498-2|doi-access=free }}</ref> इस विधि को सीधे तरीके से लागू करने से विशाल लंबाई के स्वयंसिद्ध परिणाम प्राप्त हुए,<ref name=mccune />जिससे यह प्रश्न उठता है कि छोटे स्वयंसिद्ध कैसे पाए जा सकते हैं। इस खोज से ऊपर दिए गए शेफ़र स्ट्रोक के संदर्भ में 1-आधार, साथ ही 1-आधार प्राप्त हुआ | 1973 में, पद्मनाभन और क्वेकेनबश ने एक ऐसी विधि का प्रदर्शन किया, जो सिद्धांत रूप में, बूलियन बीजगणित के लिए 1-आधार प्रदान करेगी।<ref>{{cite journal |last1=Padmanabhan |first1=R. |last2=Quackenbush |first2=R. W. |title=वितरणात्मक सर्वांगसमताओं के साथ बीजगणित के समीकरणात्मक सिद्धांत|journal=[[Proc. Amer. Math. Soc.]] |date=1973 |volume=41 |issue=2 |pages=373–377 |doi=10.1090/S0002-9939-1973-0325498-2|doi-access=free }}</ref> इस विधि को सीधे तरीके से लागू करने से विशाल लंबाई के स्वयंसिद्ध परिणाम प्राप्त हुए,<ref name=mccune />जिससे यह प्रश्न उठता है कि छोटे स्वयंसिद्ध कैसे पाए जा सकते हैं। इस खोज से ऊपर दिए गए शेफ़र स्ट्रोक के संदर्भ में 1-आधार, साथ ही 1-आधार प्राप्त हुआ | ||
:<math>\neg(\neg(\neg(x \lor y) \lor z) \lor \neg(x \lor \neg(\neg z \lor \neg(z \lor u)))) = z,</math> | :<math>\neg(\neg(\neg(x \lor y) \lor z) \lor \neg(x \lor \neg(\neg z \lor \neg(z \lor u)))) = z,</math> | ||
जो | जो ओआर और एनओटी के संदर्भ में लिखा गया है।<ref name=mccune /> | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 14:40, 6 July 2023
गणितीय तर्क में, बूलियन बीजगणित के लिए न्यूनतम स्वयंसिद्ध वे धारणाएँ हैं जो बूलियन बीजगणित (या प्रस्तावक कलन) के स्वयंसिद्धों के समतुल्य हैं, जिन्हें यथासंभव छोटा होने के लिए चुना गया है। उदाहरण के लिए, यदि कोई क्रम विनिमेयता को हल्के में लेना चाहता है,[1] छह एनएएनडी संचालन और तीन चर के साथ एक स्वयंसिद्ध बूलियन बीजगणित के समतुल्य है:
जहां ऊर्ध्वाधर पट्टी एनएएनडी तार्किक संचालन का प्रतिनिधित्व करती है (जिसे शेफ़र स्ट्रोक के रूप में भी जाना जाता है)।
यह स्टीफन वोल्फ्राम द्वारा पहचानी गई इस संपत्ति के लिए 25 प्रत्याशी स्वयंसिद्धों में से एक है, जिसमें 15 तत्वों (दर्पण छवियों को छोड़कर) से कम या समतुल्य लंबाई की शेफ़र पहचान की गणना की गई है, जिनके पास चार या उससे कम चर के साथ कोई गैर-अनुवांशिक मॉडल नहीं है, और पहली बार विलियम मैकक्यून, ब्रैंडन फिटेलसन, और लैरी वोस द्वारा समकक्ष प्रमाणित किया गया था।[2][3] वोल्फ्राम से जुड़ी साइट मैथवर्ल्ड ने स्वयंसिद्ध को वोल्फ्राम स्वयंसिद्ध नाम दिया है।[4] मैकक्यून एट अल विच्छेदन और निषेध के आधार पर बूलियन बीजगणित के लिए एक लंबा एकल स्वयंसिद्ध भी पाया गया।[3]
1933 में, एडवर्ड वर्मिली हंटिंगटन ने स्वयंसिद्ध की पहचान की
बूलियन बीजगणित के समतुल्य होने के नाते, जब इसे तार्किक ओआर ऑपरेशन की क्रमविनिमेयता के साथ जोड़ा जाता है, , और साहचर्य की धारणा, । [5] हर्बर्ट रॉबिंस ने अनुमान लगाया कि हंटिंगटन के स्वयंसिद्ध को प्रतिस्थापित किया जा सकता है
जिसके लिए तार्किक निषेध ऑपरेटर के एक कम उपयोग की आवश्यकता होती है। न तो रॉबिंस और न ही हंटिंगटन इस अनुमान को सिद्ध कर सके; न ही अल्फ्रेड टार्स्की, जिन्होंने बाद में इसमें काफी रुचि ली। अंततः 1996 में प्रमेय सिद्ध सॉफ़्टवेयर की सहायता से यह अनुमान सिद्ध हो गया।[6][7][8] इस प्रमाण ने स्थापित किया कि रॉबिंस स्वयंसिद्ध, साहचर्यता और क्रमविनिमेयता के साथ मिलकर, बूलियन बीजगणित के लिए 3-आधार बनाते हैं। 2-आधार का अस्तित्व 1967 में कैरव आर्थर मेरेडिथ द्वारा स्थापित किया गया था:[9]
- ।
अगले वर्ष, मेरेडिथ को शेफ़र स्ट्रोक के संदर्भ में 2-आधार मिला:[10]
- ।
1973 में, पद्मनाभन और क्वेकेनबश ने एक ऐसी विधि का प्रदर्शन किया, जो सिद्धांत रूप में, बूलियन बीजगणित के लिए 1-आधार प्रदान करेगी।[11] इस विधि को सीधे तरीके से लागू करने से विशाल लंबाई के स्वयंसिद्ध परिणाम प्राप्त हुए,[3]जिससे यह प्रश्न उठता है कि छोटे स्वयंसिद्ध कैसे पाए जा सकते हैं। इस खोज से ऊपर दिए गए शेफ़र स्ट्रोक के संदर्भ में 1-आधार, साथ ही 1-आधार प्राप्त हुआ
जो ओआर और एनओटी के संदर्भ में लिखा गया है।[3]
संदर्भ
- ↑ Wolfram, Stephen. "तर्क, व्याख्या और समझ का भविष्य". Stephen Worfram Writings.
- ↑ Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. ISBN 978-1579550080.
- ↑ 3.0 3.1 3.2 3.3 McCune, William; Veroff, Robert; Fitelson, Branden; Harris, Kenneth; Feist, Andrew; Wos, Larry (2002), "Short single axioms for Boolean algebra", Journal of Automated Reasoning, 29 (1): 1–16, doi:10.1023/A:1020542009983, MR 1940227, S2CID 207582048
- ↑ Rowland, Todd; Weisstein, Eric W. "Wolfram Axiom". MathWorld.
- ↑ Huntington, E. V. (1933). "व्हाइटहेड और रसेल के प्रिंसिपिया मैथमेटिका के विशेष संदर्भ में, तर्क के बीजगणित के लिए स्वतंत्र अभिधारणाओं के नए सेट". Trans. Amer. Math. Soc. 25: 247–304.
- ↑ Henkin, Leon; Monk, J. Donald; Tarski, Alfred (1971). बेलनाकार बीजगणित, भाग I. North-Holland. ISBN 978-0-7204-2043-2. OCLC 1024041028.
- ↑ McCune, William (1997). "रॉबिन्स समस्या का समाधान". Journal of Automated Reasoning. 19 (3): 263–276. doi:10.1023/A:1005843212881. S2CID 30847540.
- ↑ Kolata, Gina (1996-12-10). "कंप्यूटर गणित प्रमाण तर्क शक्ति को दर्शाता है". The New York Times. For errata, see McCune, William (1997-01-23). "Comments on Robbins Story". Argonne National Laboratory. Archived from the original on 1997-06-05.
- ↑ Meredith, C. A.; Prior, A. N. (1968). "समतामूलक तर्क". Notre Dame J. Formal Logic. 9 (3): 212–226. doi:10.1305/ndjfl/1093893457. MR 0246753.
- ↑ Meredith, C. A. (1969). "शेफ़र स्ट्रोक के लिए समीकरणात्मक अभिधारणाएँ". Notre Dame J. Formal Logic. 10 (3): 266–270. doi:10.1305/ndjfl/1093893713. MR 0245423.
- ↑ Padmanabhan, R.; Quackenbush, R. W. (1973). "वितरणात्मक सर्वांगसमताओं के साथ बीजगणित के समीकरणात्मक सिद्धांत". Proc. Amer. Math. Soc. 41 (2): 373–377. doi:10.1090/S0002-9939-1973-0325498-2.
 | ||
