तार्किक आव्यूह: Difference between revisions
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
{{Short description|Matrix of binary truth values}} | {{Short description|Matrix of binary truth values}} | ||
एक तार्किक | एक तार्किक आव्यूह, बाइनरी आव्यूह, सम्बन्ध आव्यूह, बूलियन आव्यूह, या (0, 1) आव्यूह [[ बूलियन डोमेन |बूलियन डोमेन]] से प्रविष्टियों के साथ एक [[ मैट्रिक्स (गणित) |आव्यूह (गणित)]] {{nowrap|1='''B''' = {0, 1}.}} है, इस तरह के आव्यूह का उपयोग [[ परिमित सेट |परिमित समुच्चय]] की एक युग्मक के बीच एक [[ द्विआधारी संबंध |द्विआधारी संबंध]] का प्रतिनिधित्व करने के लिए किया जा सकता है। | ||
== एक संबंध का | == एक संबंध का आव्यूह प्रतिनिधित्व == | ||
यदि R परिमित [[ अनुक्रमित सेट |अनुक्रमित | यदि R परिमित [[ अनुक्रमित सेट |अनुक्रमित समुच्चय]] X और Y के बीच एक द्विआधारी संबंध है (इसलिए {{nowrap| ''R'' ⊆ ''X''×''Y''}}), तब R को तार्किक आव्यूह M द्वारा दर्शाया जा सकता है जिसकी पंक्ति और स्तंभ सूचकांक क्रमशः X और Y के तत्वों को अनुक्रमित करते हैं, जैसे कि M की प्रविष्टियाँ परिभाषित होती हैं | ||
:<math>M_{i,j} = | :<math>M_{i,j} = | ||
Line 11: | Line 11: | ||
\end{cases} | \end{cases} | ||
</math> | </math> | ||
आव्यूह की पंक्ति और स्तंभ संख्याओं को निर्दिष्ट करने के लिए, समुच्चय X और Y को धनात्मक पूर्णांकों के साथ अनुक्रमित किया जाता है: i की श्रेणी 1 से लेकर X की [[ प्रमुखता |प्रमुखता]] (आकार) तक होती है, और j की सीमा 1 से Y की गणनीयता तक होती है। ''अधिक विवरण के लिए अनुक्रमित समुच्चय पर प्रविष्टि देखें।'' | |||
=== उदाहरण === | === उदाहरण === | ||
समुच्चय पर द्विआधारी संबंध R {{nowrap|{1, 2, 3, 4}{{null}}}} को परिभाषित किया गया है ताकि aRb बिना शेष अवयव के सम्मुच्य के मानों को संरक्षित कर सके और केवल a b को समान रूप से [[ विभाजित |विभाजित]] कर सके। उदाहरण के लिए, 2R4 संरक्षित करता है क्योंकि 2 4 को विभाजित करता है और कोई शेषफल नहीं रहता है, लेकिन 3R4 संरक्षित नहीं करता है, क्योंकि जब 3 4 को विभाजित करता है तो 1 शेषफल रहता है। निम्नलिखित समुच्चय उन युग्मों का समुच्चय है जिनके लिए संबंध R संरक्षित करता है। | |||
: {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)} . | : {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)} . | ||
तार्किक | तार्किक आव्यूह के रूप में संबंधित प्रतिनिधित्व है | ||
:<math>\begin{pmatrix} | :<math>\begin{pmatrix} | ||
Line 24: | Line 24: | ||
0 & 0 & 0 & 1 | 0 & 0 & 0 & 1 | ||
\end{pmatrix},</math> | \end{pmatrix},</math> | ||
जिसमें एक का विकर्ण | जिसमें एक का विकर्ण सम्मिलित है, क्योंकि प्रत्येक संख्या स्वयं को विभाजित करती है। | ||
== अन्य उदाहरण == | == अन्य उदाहरण == | ||
* एक क्रमचय | * '''एक क्रमचय आव्यूह एक (0, 1)-आव्यूह है''', जिसके सभी कॉलम और पंक्तियों में प्रत्येक में बिल्कुल एक शून्येतर तत्व होता है। | ||
*एक [[ कोस्टास सरणी |कोस्टास सरणी]] क्रमचय आव्यूह का एक विशेष मामला है। | |||
* [[ साहचर्य | साहचर्य]] और [[ परिमित ज्यामिति |परिमित ज्यामिति]] में एक [[ घटना मैट्रिक्स |घटना | * [[ साहचर्य | साहचर्य]] और [[ परिमित ज्यामिति |परिमित ज्यामिति]] में एक [[ घटना मैट्रिक्स |घटना आव्यूह]] में बिंदुओं (या कोने) और ज्यामिति की रेखाओं, [[ ब्लॉक डिजाइन |ब्लॉक डिजाइन]] के ब्लॉक, या ग्राफ़ के किनारों (असतत गणित) के बीच घटनाओं को इंगित करने के लिए होता है। | ||
* विचरण के विश्लेषण में एक [[ डिजाइन मैट्रिक्स |डिजाइन | * विचरण के विश्लेषण में एक [[ डिजाइन मैट्रिक्स |डिजाइन आव्यूह]] एक (0, 1)-आव्यूह है जिसमें निरंतर पंक्ति योग होते हैं। | ||
* एक तार्किक | * एक तार्किक आव्यूह ग्राफ़ सिद्धांत में एक आसन्न आव्यूह का प्रतिनिधित्व कर सकता है: गैर-सममित मैट्रिसेस [[ निर्देशित ग्राफ |निर्देशित ग्राफ]] के अनुरूप होते हैं, सममित मैट्रिसेस सासंरक्षित ग्राफ़ (असतत गणित) के लिए होते हैं, और विकर्ण पर 1 एक लूप (ग्राफ़ सिद्धांत) से संबंधित होता है शिखर। | ||
* एक सरल, अप्रत्यक्ष द्विदलीय ग्राफ का [[ सहखंडज मैट्रिक्स |सहखंडज | * एक सरल, अप्रत्यक्ष द्विदलीय ग्राफ का [[ सहखंडज मैट्रिक्स |सहखंडज आव्यूह]] एक (0, 1)-आव्यूह है, और कोई भी (0, 1)-आव्यूह इस तरह से उत्पन्न होता है। | ||
* एम [[ वर्ग मुक्त पूर्णांक |वर्ग मुक्त पूर्णांक]] |स्क्वायर-फ्री, स्मूथ नंबर|एन-स्मूथ नंबरों की सूची के प्रमुख कारकों को एक m × π(n) (0, 1)- | * एम [[ वर्ग मुक्त पूर्णांक |वर्ग मुक्त पूर्णांक]] |स्क्वायर-फ्री, स्मूथ नंबर|एन-स्मूथ नंबरों की सूची के प्रमुख कारकों को एक m × π(n) (0, 1)-आव्यूह के रूप में वर्णित किया जा सकता है, जहां π [[ प्राइम-काउंटिंग फंक्शन |प्राइम-काउंटिंग फंक्शन]] समारोह, और ए<sub>''ij''</sub> 1 है अगर और केवल अगर jth अभाज्य ith संख्या को विभाजित करता है। यह प्रतिनिधित्व द्विघात छलनी फैक्टरिंग एल्गोरिथम में उपयोगी है। | ||
* केवल दो रंगों में [[ पिक्सेल |पिक्सेल]] वाले [[ रेखापुंज ग्राफिक्स |रेखापुंज ग्राफिक्स]] को (0, 1)- | * केवल दो रंगों में [[ पिक्सेल |पिक्सेल]] वाले [[ रेखापुंज ग्राफिक्स |रेखापुंज ग्राफिक्स]] को (0, 1)-आव्यूह के रूप में दर्शाया जा सकता है जिसमें शून्य एक रंग के पिक्सेल का प्रतिनिधित्व करते हैं और दूसरे रंग के पिक्सेल का प्रतिनिधित्व करते हैं। | ||
* गो (खेल) के खेल में खेल के नियमों की जांच के लिए एक बाइनरी | * गो (खेल) के खेल में खेल के नियमों की जांच के लिए एक बाइनरी आव्यूह का उपयोग किया जा सकता है।<ref>{{cite web |url=http://senseis.xmp.net/?BinMatrix |title=Binmatrix |date=February 8, 2013 |access-date=August 11, 2017 |first=Kjeld |last=Petersen}}</ref> | ||
== कुछ गुण == | == कुछ गुण == | ||
एक परिमित | एक परिमित समुच्चय पर [[ समानता (गणित) |समानता (गणित)]] का आव्यूह प्रतिनिधित्व पहचान आव्यूह I है, अर्थात, वह आव्यूह जिसकी विकर्ण पर प्रविष्टियाँ सभी 1 हैं, जबकि अन्य सभी 0 हैं। अधिक सामान्यतः, यदि संबंध R संतुष्ट करता है {{nowrap|I ⊆ ''R'',}} तो R एक स्वतुल्य संबंध है। | ||
यदि बूलियन डोमेन को [[ मोटी हो जाओ |मोटी हो जाओ]] के रूप में देखा जाता है, जहां योग तार्किक OR और गुणा तार्किक AND से मेल खाता है, तो दो संबंधों के संबंधों की संरचना का | यदि बूलियन डोमेन को [[ मोटी हो जाओ |मोटी हो जाओ]] के रूप में देखा जाता है, जहां योग तार्किक OR और गुणा तार्किक AND से मेल खाता है, तो दो संबंधों के संबंधों की संरचना का आव्यूह प्रतिनिधित्व इन संबंधों के आव्यूह प्रतिनिधित्व के [[ मैट्रिक्स उत्पाद |आव्यूह उत्पाद]] के बराबर होता है। | ||
इस उत्पाद की गणना अपेक्षित मान समय O(n<sup>2</sup>).<ref>{{cite journal| author=Patrick E. O'Neil | author2= Elizabeth J. O'Neil|author2-link=Elizabeth O'Neil| title=A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure| journal=[[Information and Control]]| year=1973| volume=22| issue=2 |pages=132–138| doi=10.1016/s0019-9958(73)90228-3| doi-access=free}} — The algorithm relies on addition being [[idempotent]], cf. p.134 (bottom).</ref> | इस उत्पाद की गणना अपेक्षित मान समय O(n<sup>2</sup>).<ref>{{cite journal| author=Patrick E. O'Neil | author2= Elizabeth J. O'Neil|author2-link=Elizabeth O'Neil| title=A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure| journal=[[Information and Control]]| year=1973| volume=22| issue=2 |pages=132–138| doi=10.1016/s0019-9958(73)90228-3| doi-access=free}} — The algorithm relies on addition being [[idempotent]], cf. p.134 (bottom).</ref> | ||
अक्सर, बाइनरी मैट्रिसेस पर संचालन को [[ मॉड्यूलर अंकगणित |मॉड्यूलर अंकगणित]] ीय मॉड 2 के संदर्भ में परिभाषित किया जाता है-अर्थात, तत्वों को गैलोज़ क्षेत्र के तत्वों के रूप में माना जाता है। {{nowrap|1='''GF'''(2) = ℤ<sub>2</sub>}}. वे विभिन्न प्रकार के अभ्यावेदन में उत्पन्न होते हैं और कई अधिक प्रतिबंधित विशेष रूप होते हैं। उन्हें लागू किया जाता है उदा। [[ XOR-संतुष्टि |XOR-संतुष्टि]] में।<!---more links to applications should go here---> | अक्सर, बाइनरी मैट्रिसेस पर संचालन को [[ मॉड्यूलर अंकगणित |मॉड्यूलर अंकगणित]] ीय मॉड 2 के संदर्भ में परिभाषित किया जाता है-अर्थात, तत्वों को गैलोज़ क्षेत्र के तत्वों के रूप में माना जाता है। {{nowrap|1='''GF'''(2) = ℤ<sub>2</sub>}}. वे विभिन्न प्रकार के अभ्यावेदन में उत्पन्न होते हैं और कई अधिक प्रतिबंधित विशेष रूप होते हैं। उन्हें लागू किया जाता है उदा। [[ XOR-संतुष्टि |XOR-संतुष्टि]] में।<!---more links to applications should go here---> | ||
विशिष्ट एम-बाय-एन बाइनरी | विशिष्ट एम-बाय-एन बाइनरी आव्यूह की संख्या 2 के बराबर है<sup>एमएन</sup>, और इस प्रकार परिमित है। | ||
== जाली == | == जाली == | ||
मान लीजिए कि n और m दिए गए हैं और U सभी तार्किक m × n आव्यूहों के समुच्चय को निरूपित करता है। तब U द्वारा दिया गया आंशिक क्रम है | मान लीजिए कि n और m दिए गए हैं और U सभी तार्किक m × n आव्यूहों के समुच्चय को निरूपित करता है। तब U द्वारा दिया गया आंशिक क्रम है | ||
:<math>\forall A,B \in U, \quad A \leq B \quad \text{when} \quad \forall i,j \quad A_{ij} = 1 \implies B_{ij} = 1 .</math> | :<math>\forall A,B \in U, \quad A \leq B \quad \text{when} \quad \forall i,j \quad A_{ij} = 1 \implies B_{ij} = 1 .</math> | ||
वास्तव में, यू संचालन के साथ एक [[ बूलियन बीजगणित |बूलियन बीजगणित]] बनाता है [[ और (तर्क) |और (तर्क)]] और [[ या (तर्क) |या (तर्क)]] दो | वास्तव में, यू संचालन के साथ एक [[ बूलियन बीजगणित |बूलियन बीजगणित]] बनाता है [[ और (तर्क) |और (तर्क)]] और [[ या (तर्क) |या (तर्क)]] दो आव्यूह के बीच घटक-वार लागू होता है। एक तार्किक आव्यूह का पूरक सभी शून्य और उनके विपरीत के लिए अदला-बदली करके प्राप्त किया जाता है। | ||
हर तार्किक | हर तार्किक आव्यूह {{nowrap|1=''A'' = ( ''A'' <sub>''i'' ''j''</sub> )}} एक स्थानान्तरण है {{nowrap|1=''A''<sup>T</sup> = ( ''A'' <sub>''j'' ''i''</sub> ).}} मान लीजिए A एक तार्किक आव्यूह है जिसमें कोई कॉलम या पंक्तियाँ समान रूप से शून्य नहीं हैं। फिर आव्यूह उत्पाद, बूलियन अंकगणित का उपयोग करते हुए, <math>A^{\operatorname{T}}A</math> एम × एम पहचान आव्यूह, और उत्पाद सम्मिलित है <math>AA^{\operatorname{T}}</math> n × n पहचान सम्मिलित है। | ||
एक गणितीय संरचना के रूप में, बूलियन बीजगणित यू [[ समावेशन (तर्क) |समावेशन (तर्क)]] द्वारा आदेशित एक जाली (क्रम) बनाता है; इसके अतिरिक्त यह | एक गणितीय संरचना के रूप में, बूलियन बीजगणित यू [[ समावेशन (तर्क) |समावेशन (तर्क)]] द्वारा आदेशित एक जाली (क्रम) बनाता है; इसके अतिरिक्त यह आव्यूह गुणन के कारण गुणक जाली है। | ||
U में प्रत्येक तार्किक | U में प्रत्येक तार्किक आव्यूह एक द्विआधारी संबंध से मेल खाता है। यू पर ये सूचीबद्ध संचालन, और ऑर्डरिंग, एक बीजगणितीय तर्क # संबंधों की गणना के अनुरूप है, जहां आव्यूह गुणन संबंधों की संरचना का प्रतिनिधित्व करता है।<ref>[[Irving Copilowish]] (December 1948). "Matrix development of the calculus of relations", [[Journal of Symbolic Logic]] 13(4): 193–203 [https://www.jstor.org/stable/2267134?seq=1#page_scan_tab_contents Jstor link]</ref> | ||
== तार्किक वैक्टर == | == तार्किक वैक्टर == | ||
अगर एम या एन एक के बराबर है, तो एम × एन लॉजिकल | अगर एम या एन एक के बराबर है, तो एम × एन लॉजिकल आव्यूह (एम<sub>''ij''</sub>) एक तार्किक वेक्टर है। यदि m = 1, सदिश एक पंक्ति सदिश है, और यदि n = 1, यह एक स्तंभ सदिश है। किसी भी मामले में सूचकांक के बराबर एक को वेक्टर के निरूपण से हटा दिया जाता है। | ||
मान लीजिए <math>(P_i),\ i = 1, 2, \ldots, m</math> और <math>(Q_j),\ j = 1, 2, \ldots, n</math> दो तार्किक वैक्टर हैं। P और Q के [[ बाहरी उत्पाद |बाहरी उत्पाद]] का परिणाम m × n [[ आयताकार संबंध |आयताकार संबंध]] होता है | मान लीजिए <math>(P_i),\ i = 1, 2, \ldots, m</math> और <math>(Q_j),\ j = 1, 2, \ldots, n</math> दो तार्किक वैक्टर हैं। P और Q के [[ बाहरी उत्पाद |बाहरी उत्पाद]] का परिणाम m × n [[ आयताकार संबंध |आयताकार संबंध]] होता है | ||
:<math>M_{ij} = P_i \land Q_j.</math> | :<math>M_{ij} = P_i \land Q_j.</math> | ||
ऐसे | ऐसे आव्यूह की पंक्तियों और स्तंभों का पुन: क्रम सभी को आव्यूह के एक आयताकार भाग में इकट्ठा कर सकता है।<ref name=GS>{{cite book | doi=10.1017/CBO9780511778810 | isbn=9780511778810 | author=Gunther Schmidt | page=91 | title=Relational Mathematics | chapter=6: Relations and Vectors | publisher=Cambridge University Press | year=2013 | author-link=Gunther Schmidt }}</ref> | ||
मान लीजिए h सभी का सदिश है। तब यदि v एक स्वेच्छ तार्किक सदिश है, तो संबंध R = v h<sup>T</sup> में v द्वारा निर्धारित स्थिर पंक्तियाँ हैं। [[ संबंधों की गणना |संबंधों की गणना]] में ऐसे R को सदिश कहा जाता है।<ref name=GS/>एक विशेष उदाहरण सार्वभौमिक संबंध है <math>hh^{\operatorname{T}}</math>. | मान लीजिए h सभी का सदिश है। तब यदि v एक स्वेच्छ तार्किक सदिश है, तो संबंध R = v h<sup>T</sup> में v द्वारा निर्धारित स्थिर पंक्तियाँ हैं। [[ संबंधों की गणना |संबंधों की गणना]] में ऐसे R को सदिश कहा जाता है।<ref name=GS/>एक विशेष उदाहरण सार्वभौमिक संबंध है <math>hh^{\operatorname{T}}</math>. | ||
किसी दिए गए संबंध R के लिए, R में निहित एक अधिकतम आयताकार संबंध को R में एक | किसी दिए गए संबंध R के लिए, R में निहित एक अधिकतम आयताकार संबंध को R में एक अवसंरक्षिता कहा जाता है। संबंधों को अवसंरक्षिताओं में विघटित करके अध्ययन किया जा सकता है, और फिर विषम संबंध # प्रेरित अवसंरक्षिता जाली को ध्यान में रखते हुए। | ||
{{Group-like structures}} | {{Group-like structures}} | ||
समूह-जैसी संरचनाओं की तालिका पर विचार करें, जहाँ अनावश्यक को 0 से निरूपित किया जा सकता है, और आवश्यक को 1 से निरूपित किया जाता है, जिससे एक तार्किक | समूह-जैसी संरचनाओं की तालिका पर विचार करें, जहाँ अनावश्यक को 0 से निरूपित किया जा सकता है, और आवश्यक को 1 से निरूपित किया जाता है, जिससे एक तार्किक आव्यूह R बनता है। के तत्वों की गणना करने के लिए <math>RR^{\operatorname{T}}</math>, इस आव्यूह की पंक्तियों में तार्किक वैक्टर के जोड़े के तार्किक आंतरिक उत्पाद का उपयोग करना आवश्यक है। यदि यह आंतरिक उत्पाद 0 है, तो पंक्तियाँ ओर्थोगोनल हैं। वास्तव में, [[ semigroup |semigroup]] लूप (बीजगणित) के लिए ऑर्थोगोनल है, [[ छोटी श्रेणी |छोटी श्रेणी]] अर्धसमूह के लिए ऑर्थोगोनल है, और [[ groupoid |groupoid]] [[ मेग्मा |मेग्मा]] के लिए ऑर्थोगोनल है। नतीजतन में शून्य हैं <math>RR^{\operatorname{T}}</math>, और यह एक [[ सार्वभौमिक संबंध |सार्वभौमिक संबंध]] बनने में विफल रहता है। | ||
== पंक्ति और स्तंभ योग == | == पंक्ति और स्तंभ योग == | ||
तार्किक | तार्किक आव्यूह में सभी को जोड़ना दो तरीकों से पूरा किया जा सकता है: पहले पंक्तियों का योग या पहले स्तंभों का योग। जब पंक्ति योग जोड़े जाते हैं, तो योग वही होता है जब स्तंभ योग जोड़े जाते हैं। [[ घटना ज्यामिति |घटना ज्यामिति]] में, आव्यूह को एक घटना आव्यूह के रूप में व्याख्या की जाती है जिसमें पंक्तियों के साथ बिंदु और कॉलम ब्लॉक के रूप में होते हैं (बिंदुओं से बनी सामान्य रेखाएं)। एक पंक्ति योग को इसकी बिंदु डिग्री कहा जाता है, और एक स्तंभ योग को ब्लॉक डिग्री कहा जाता है। डिजाइन थ्योरी में प्रस्ताव 1.6<ref name=BJL>{{cite book |first1=Thomas |last1=Beth |first2=Dieter |last2=Jungnickel |author-link2=Dieter Jungnickel |first3=Hanfried |last3=Lenz |author-link3=Hanfried Lenz |title=Design Theory |publisher=[[Cambridge University Press]] |page=18 |year=1999 |edition=2nd |ISBN=978-0-521-44432-3}}</ref> कहते हैं कि बिंदु डिग्री का योग ब्लॉक डिग्री के योग के बराबर है। | ||
क्षेत्र में एक प्रारंभिक समस्या दी गई बिंदु डिग्री और ब्लॉक डिग्री (या | क्षेत्र में एक प्रारंभिक समस्या दी गई बिंदु डिग्री और ब्लॉक डिग्री (या आव्यूह भाषा में, (0, 1)-आव्यूह प्रकार v × b के अस्तित्व के लिए एक [[ घटना संरचना |घटना संरचना]] के अस्तित्व के लिए आवश्यक और पर्याप्त परिस्थितियों का पता लगाना था। दी गई पंक्ति और स्तंभ रकम के साथ।<ref name=BJL/>ऐसी संरचना एक ब्लॉक डिज़ाइन है। | ||
== यह भी देखें == | == यह भी देखें == | ||
Line 81: | Line 81: | ||
* [[ ब्रुजन टोरस | ब्रुजन टोरस]] (एक बाइनरी डी ब्रुइज़न टोरस) | * [[ ब्रुजन टोरस | ब्रुजन टोरस]] (एक बाइनरी डी ब्रुइज़न टोरस) | ||
* [[ बिट सरणी ]] | * [[ बिट सरणी ]] | ||
* [[ रेडहेफर मैट्रिक्स ]] | * [[ रेडहेफर मैट्रिक्स | रेडहेफर आव्यूह]] | ||
*[[ सच्ची तालिका ]] | *[[ सच्ची तालिका ]] | ||
Line 105: | Line 105: | ||
{{Matrix classes}} | {{Matrix classes}} | ||
{{DEFAULTSORT:Logical Matrix}}[[Category:बूलियन बीजगणित]][[श्रेणी: मैट्रिक्स]] | {{DEFAULTSORT:Logical Matrix}}[[Category:बूलियन बीजगणित]][[श्रेणी: मैट्रिक्स|श्रेणी: आव्यूह]] | ||
[[Category: Machine Translated Page]] | [[Category: Machine Translated Page]] | ||
[[Category:Created On 05/01/2023]] | [[Category:Created On 05/01/2023]] |
Revision as of 10:05, 6 May 2023
एक तार्किक आव्यूह, बाइनरी आव्यूह, सम्बन्ध आव्यूह, बूलियन आव्यूह, या (0, 1) आव्यूह बूलियन डोमेन से प्रविष्टियों के साथ एक आव्यूह (गणित) B = {0, 1}. है, इस तरह के आव्यूह का उपयोग परिमित समुच्चय की एक युग्मक के बीच एक द्विआधारी संबंध का प्रतिनिधित्व करने के लिए किया जा सकता है।
एक संबंध का आव्यूह प्रतिनिधित्व
यदि R परिमित अनुक्रमित समुच्चय X और Y के बीच एक द्विआधारी संबंध है (इसलिए R ⊆ X×Y), तब R को तार्किक आव्यूह M द्वारा दर्शाया जा सकता है जिसकी पंक्ति और स्तंभ सूचकांक क्रमशः X और Y के तत्वों को अनुक्रमित करते हैं, जैसे कि M की प्रविष्टियाँ परिभाषित होती हैं
आव्यूह की पंक्ति और स्तंभ संख्याओं को निर्दिष्ट करने के लिए, समुच्चय X और Y को धनात्मक पूर्णांकों के साथ अनुक्रमित किया जाता है: i की श्रेणी 1 से लेकर X की प्रमुखता (आकार) तक होती है, और j की सीमा 1 से Y की गणनीयता तक होती है। अधिक विवरण के लिए अनुक्रमित समुच्चय पर प्रविष्टि देखें।
उदाहरण
समुच्चय पर द्विआधारी संबंध R {1, 2, 3, 4} को परिभाषित किया गया है ताकि aRb बिना शेष अवयव के सम्मुच्य के मानों को संरक्षित कर सके और केवल a b को समान रूप से विभाजित कर सके। उदाहरण के लिए, 2R4 संरक्षित करता है क्योंकि 2 4 को विभाजित करता है और कोई शेषफल नहीं रहता है, लेकिन 3R4 संरक्षित नहीं करता है, क्योंकि जब 3 4 को विभाजित करता है तो 1 शेषफल रहता है। निम्नलिखित समुच्चय उन युग्मों का समुच्चय है जिनके लिए संबंध R संरक्षित करता है।
- {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)} .
तार्किक आव्यूह के रूप में संबंधित प्रतिनिधित्व है
जिसमें एक का विकर्ण सम्मिलित है, क्योंकि प्रत्येक संख्या स्वयं को विभाजित करती है।
अन्य उदाहरण
- एक क्रमचय आव्यूह एक (0, 1)-आव्यूह है, जिसके सभी कॉलम और पंक्तियों में प्रत्येक में बिल्कुल एक शून्येतर तत्व होता है।
- एक कोस्टास सरणी क्रमचय आव्यूह का एक विशेष मामला है।
- साहचर्य और परिमित ज्यामिति में एक घटना आव्यूह में बिंदुओं (या कोने) और ज्यामिति की रेखाओं, ब्लॉक डिजाइन के ब्लॉक, या ग्राफ़ के किनारों (असतत गणित) के बीच घटनाओं को इंगित करने के लिए होता है।
- विचरण के विश्लेषण में एक डिजाइन आव्यूह एक (0, 1)-आव्यूह है जिसमें निरंतर पंक्ति योग होते हैं।
- एक तार्किक आव्यूह ग्राफ़ सिद्धांत में एक आसन्न आव्यूह का प्रतिनिधित्व कर सकता है: गैर-सममित मैट्रिसेस निर्देशित ग्राफ के अनुरूप होते हैं, सममित मैट्रिसेस सासंरक्षित ग्राफ़ (असतत गणित) के लिए होते हैं, और विकर्ण पर 1 एक लूप (ग्राफ़ सिद्धांत) से संबंधित होता है शिखर।
- एक सरल, अप्रत्यक्ष द्विदलीय ग्राफ का सहखंडज आव्यूह एक (0, 1)-आव्यूह है, और कोई भी (0, 1)-आव्यूह इस तरह से उत्पन्न होता है।
- एम वर्ग मुक्त पूर्णांक |स्क्वायर-फ्री, स्मूथ नंबर|एन-स्मूथ नंबरों की सूची के प्रमुख कारकों को एक m × π(n) (0, 1)-आव्यूह के रूप में वर्णित किया जा सकता है, जहां π प्राइम-काउंटिंग फंक्शन समारोह, और एij 1 है अगर और केवल अगर jth अभाज्य ith संख्या को विभाजित करता है। यह प्रतिनिधित्व द्विघात छलनी फैक्टरिंग एल्गोरिथम में उपयोगी है।
- केवल दो रंगों में पिक्सेल वाले रेखापुंज ग्राफिक्स को (0, 1)-आव्यूह के रूप में दर्शाया जा सकता है जिसमें शून्य एक रंग के पिक्सेल का प्रतिनिधित्व करते हैं और दूसरे रंग के पिक्सेल का प्रतिनिधित्व करते हैं।
- गो (खेल) के खेल में खेल के नियमों की जांच के लिए एक बाइनरी आव्यूह का उपयोग किया जा सकता है।[1]
कुछ गुण
एक परिमित समुच्चय पर समानता (गणित) का आव्यूह प्रतिनिधित्व पहचान आव्यूह I है, अर्थात, वह आव्यूह जिसकी विकर्ण पर प्रविष्टियाँ सभी 1 हैं, जबकि अन्य सभी 0 हैं। अधिक सामान्यतः, यदि संबंध R संतुष्ट करता है I ⊆ R, तो R एक स्वतुल्य संबंध है।
यदि बूलियन डोमेन को मोटी हो जाओ के रूप में देखा जाता है, जहां योग तार्किक OR और गुणा तार्किक AND से मेल खाता है, तो दो संबंधों के संबंधों की संरचना का आव्यूह प्रतिनिधित्व इन संबंधों के आव्यूह प्रतिनिधित्व के आव्यूह उत्पाद के बराबर होता है। इस उत्पाद की गणना अपेक्षित मान समय O(n2).[2] अक्सर, बाइनरी मैट्रिसेस पर संचालन को मॉड्यूलर अंकगणित ीय मॉड 2 के संदर्भ में परिभाषित किया जाता है-अर्थात, तत्वों को गैलोज़ क्षेत्र के तत्वों के रूप में माना जाता है। GF(2) = ℤ2. वे विभिन्न प्रकार के अभ्यावेदन में उत्पन्न होते हैं और कई अधिक प्रतिबंधित विशेष रूप होते हैं। उन्हें लागू किया जाता है उदा। XOR-संतुष्टि में। विशिष्ट एम-बाय-एन बाइनरी आव्यूह की संख्या 2 के बराबर हैएमएन, और इस प्रकार परिमित है।
जाली
मान लीजिए कि n और m दिए गए हैं और U सभी तार्किक m × n आव्यूहों के समुच्चय को निरूपित करता है। तब U द्वारा दिया गया आंशिक क्रम है
वास्तव में, यू संचालन के साथ एक बूलियन बीजगणित बनाता है और (तर्क) और या (तर्क) दो आव्यूह के बीच घटक-वार लागू होता है। एक तार्किक आव्यूह का पूरक सभी शून्य और उनके विपरीत के लिए अदला-बदली करके प्राप्त किया जाता है।
हर तार्किक आव्यूह A = ( A i j ) एक स्थानान्तरण है AT = ( A j i ). मान लीजिए A एक तार्किक आव्यूह है जिसमें कोई कॉलम या पंक्तियाँ समान रूप से शून्य नहीं हैं। फिर आव्यूह उत्पाद, बूलियन अंकगणित का उपयोग करते हुए, एम × एम पहचान आव्यूह, और उत्पाद सम्मिलित है n × n पहचान सम्मिलित है।
एक गणितीय संरचना के रूप में, बूलियन बीजगणित यू समावेशन (तर्क) द्वारा आदेशित एक जाली (क्रम) बनाता है; इसके अतिरिक्त यह आव्यूह गुणन के कारण गुणक जाली है।
U में प्रत्येक तार्किक आव्यूह एक द्विआधारी संबंध से मेल खाता है। यू पर ये सूचीबद्ध संचालन, और ऑर्डरिंग, एक बीजगणितीय तर्क # संबंधों की गणना के अनुरूप है, जहां आव्यूह गुणन संबंधों की संरचना का प्रतिनिधित्व करता है।[3]
तार्किक वैक्टर
अगर एम या एन एक के बराबर है, तो एम × एन लॉजिकल आव्यूह (एमij) एक तार्किक वेक्टर है। यदि m = 1, सदिश एक पंक्ति सदिश है, और यदि n = 1, यह एक स्तंभ सदिश है। किसी भी मामले में सूचकांक के बराबर एक को वेक्टर के निरूपण से हटा दिया जाता है।
मान लीजिए और दो तार्किक वैक्टर हैं। P और Q के बाहरी उत्पाद का परिणाम m × n आयताकार संबंध होता है
ऐसे आव्यूह की पंक्तियों और स्तंभों का पुन: क्रम सभी को आव्यूह के एक आयताकार भाग में इकट्ठा कर सकता है।[4] मान लीजिए h सभी का सदिश है। तब यदि v एक स्वेच्छ तार्किक सदिश है, तो संबंध R = v hT में v द्वारा निर्धारित स्थिर पंक्तियाँ हैं। संबंधों की गणना में ऐसे R को सदिश कहा जाता है।[4]एक विशेष उदाहरण सार्वभौमिक संबंध है .
किसी दिए गए संबंध R के लिए, R में निहित एक अधिकतम आयताकार संबंध को R में एक अवसंरक्षिता कहा जाता है। संबंधों को अवसंरक्षिताओं में विघटित करके अध्ययन किया जा सकता है, और फिर विषम संबंध # प्रेरित अवसंरक्षिता जाली को ध्यान में रखते हुए।
Totalityα | Associativity | Identity | Inverse | Commutativity | |
---|---|---|---|---|---|
Semigroupoid | Unneeded | Required | Unneeded | Unneeded | Unneeded |
Small category | Unneeded | Required | Required | Unneeded | Unneeded |
Groupoid | Unneeded | Required | Required | Required | Unneeded |
Magma | Required | Unneeded | Unneeded | Unneeded | Unneeded |
Quasigroup | Required | Unneeded | Unneeded | Required | Unneeded |
Unital magma | Required | Unneeded | Required | Unneeded | Unneeded |
Semigroup | Required | Required | Unneeded | Unneeded | Unneeded |
Loop | Required | Unneeded | Required | Required | Unneeded |
Monoid | Required | Required | Required | Unneeded | Unneeded |
Group | Required | Required | Required | Required | Unneeded |
Commutative monoid | Required | Required | Required | Unneeded | Required |
Abelian group | Required | Required | Required | Required | Required |
^α The closure axiom, used by many sources and defined differently, is equivalent. |
समूह-जैसी संरचनाओं की तालिका पर विचार करें, जहाँ अनावश्यक को 0 से निरूपित किया जा सकता है, और आवश्यक को 1 से निरूपित किया जाता है, जिससे एक तार्किक आव्यूह R बनता है। के तत्वों की गणना करने के लिए , इस आव्यूह की पंक्तियों में तार्किक वैक्टर के जोड़े के तार्किक आंतरिक उत्पाद का उपयोग करना आवश्यक है। यदि यह आंतरिक उत्पाद 0 है, तो पंक्तियाँ ओर्थोगोनल हैं। वास्तव में, semigroup लूप (बीजगणित) के लिए ऑर्थोगोनल है, छोटी श्रेणी अर्धसमूह के लिए ऑर्थोगोनल है, और groupoid मेग्मा के लिए ऑर्थोगोनल है। नतीजतन में शून्य हैं , और यह एक सार्वभौमिक संबंध बनने में विफल रहता है।
पंक्ति और स्तंभ योग
तार्किक आव्यूह में सभी को जोड़ना दो तरीकों से पूरा किया जा सकता है: पहले पंक्तियों का योग या पहले स्तंभों का योग। जब पंक्ति योग जोड़े जाते हैं, तो योग वही होता है जब स्तंभ योग जोड़े जाते हैं। घटना ज्यामिति में, आव्यूह को एक घटना आव्यूह के रूप में व्याख्या की जाती है जिसमें पंक्तियों के साथ बिंदु और कॉलम ब्लॉक के रूप में होते हैं (बिंदुओं से बनी सामान्य रेखाएं)। एक पंक्ति योग को इसकी बिंदु डिग्री कहा जाता है, और एक स्तंभ योग को ब्लॉक डिग्री कहा जाता है। डिजाइन थ्योरी में प्रस्ताव 1.6[5] कहते हैं कि बिंदु डिग्री का योग ब्लॉक डिग्री के योग के बराबर है।
क्षेत्र में एक प्रारंभिक समस्या दी गई बिंदु डिग्री और ब्लॉक डिग्री (या आव्यूह भाषा में, (0, 1)-आव्यूह प्रकार v × b के अस्तित्व के लिए एक घटना संरचना के अस्तित्व के लिए आवश्यक और पर्याप्त परिस्थितियों का पता लगाना था। दी गई पंक्ति और स्तंभ रकम के साथ।[5]ऐसी संरचना एक ब्लॉक डिज़ाइन है।
यह भी देखें
- मैट्रिसेस की सूची
- ब्रुजन टोरस (एक बाइनरी डी ब्रुइज़न टोरस)
- बिट सरणी
- रेडहेफर आव्यूह
- सच्ची तालिका
टिप्पणियाँ
- ↑ Petersen, Kjeld (February 8, 2013). "Binmatrix". Retrieved August 11, 2017.
- ↑ Patrick E. O'Neil; Elizabeth J. O'Neil (1973). "A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure". Information and Control. 22 (2): 132–138. doi:10.1016/s0019-9958(73)90228-3. — The algorithm relies on addition being idempotent, cf. p.134 (bottom).
- ↑ Irving Copilowish (December 1948). "Matrix development of the calculus of relations", Journal of Symbolic Logic 13(4): 193–203 Jstor link
- ↑ 4.0 4.1 Gunther Schmidt (2013). "6: Relations and Vectors". Relational Mathematics. Cambridge University Press. p. 91. doi:10.1017/CBO9780511778810. ISBN 9780511778810.
- ↑ 5.0 5.1 Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1999). Design Theory (2nd ed.). Cambridge University Press. p. 18. ISBN 978-0-521-44432-3.
संदर्भ
- Hogben, Leslie (2006), Handbook of Linear Algebra (Discrete Mathematics and Its Applications), Boca Raton: Chapman & Hall/CRC, ISBN 978-1-58488-510-8, § 31.3, Binary Matrices
- Kim, Ki Hang (1982), Boolean Matrix Theory and Applications, ISBN 978-0-8247-1788-9
- H. J. Ryser (1957) "Combinatorial properties of matrices of zeroes and ones", Canadian Journal of Mathematics 9: 371–7.
- Ryser, H.J. (1960) "Traces of matrices of zeroes and ones", Canadian Journal of Mathematics 12: 463–76.
- Ryser, H.J. (1960) "Matrices of Zeros and Ones", Bulletin of the American Mathematical Society 66: 442–64.
- D. R. Fulkerson (1960) "Zero-one matrices with zero trace", Pacific Journal of Mathematics 10; 831–6
- D. R. Fulkerson & H. J. Ryser (1961) "Widths and heights of (0, 1)-matrices", Canadian Journal of Mathematics 13: 239–55.
- L. R. Ford Jr. & D. R. Fulkerson (1962) § 2.12 "Matrices composed of 0's and 1's", pages 79 to 91 in Flows in Networks, Princeton University Press MR0159700
बाहरी कड़ियाँ
- "Logical matrix", Encyclopedia of Mathematics, EMS Press, 2001 [1994]