View source for बूलियन बीजगणित के लिए न्यूनतम स्वयंसिद्ध

[[गणितीय तर्क]] में, [[बूलियन बीजगणित]] के लिए न्यूनतम स्वयंसिद्ध वे धारणाएँ हैं जो बूलियन बीजगणित (या प्रस्तावक कलन) के स्वयंसिद्धों के समतुल्य हैं, जिन्हें यथासंभव छोटा होने के लिए चुना गया है। उदाहरण के लिए, यदि कोई क्रम विनिमेयता को हल्के में लेना चाहता है,<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>
जहां ऊर्ध्वाधर पट्टी एनएएनडी तार्किक संचालन का प्रतिनिधित्व करती है (जिसे [[शेफ़र लाइन|शेफ़र स्ट्रोक]] के रूप में भी जाना जाता है)।

यह [[स्टीफन वोल्फ्राम]] द्वारा पहचानी गई इस संपत्ति के लिए 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
 | last2 = Veroff | first2 = Robert
 | last3 = Fitelson | first3 = Branden |author-link3 = Branden Fitelson
 | last4 = Harris | first4 = Kenneth
 | last5 = Feist | first5 = Andrew
 | last6 = Wos | first6 = Larry |author-link6 = Larry Wos
 | doi = 10.1023/A:1020542009983
 | issue = 1
 | journal = [[Journal of Automated Reasoning]]
 | mr = 1940227
 | pages = 1–16
 | title = Short single axioms for Boolean algebra
 | volume = 29
 | year = 2002| s2cid = 207582048 }}</ref> वोल्फ्राम से जुड़ी साइट [[मैथवर्ल्ड]] ने स्वयंसिद्ध को वोल्फ्राम स्वयंसिद्ध नाम दिया है।<ref>{{MathWorld|id=WolframAxiom|title=Wolfram Axiom|author=Rowland, Todd|author2=Weisstein, Eric W.}}</ref> मैकक्यून एट अल विच्छेदन और निषेध के आधार पर बूलियन बीजगणित के लिए एक लंबा एकल स्वयंसिद्ध भी पाया गया।<ref name=mccune/>

1933 में, [[एडवर्ड वर्मिली हंटिंगटन]] ने स्वयंसिद्ध की पहचान की
:<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</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 (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>
:<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>।
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>
जो ओआर और एनओटी के संदर्भ में लिखा गया है।<ref name=mccune />
==संदर्भ==

{{Reflist}}

{{Logical connectives}}
[[Category: बूलियन बीजगणित]] [[Category: तर्क का इतिहास]] [[Category: तर्क द्वार|नन्द द्वार]] [[Category: प्रस्तावात्मक कलन]] 



[[Category: Machine Translated Page]]
[[Category:Created On 23/06/2023]]
[[Category:Vigyan Ready]]