तार्किक मैट्रिक्स

एक लॉजिकल मैट्रिक्स, बाइनरी मैट्रिक्स, रिलेशन मैट्रिक्स, बूलियन मैट्रिक्स, या (0, 1)-मैट्रिक्स बूलियन डोमेन से प्रविष्टियों के साथ एक मैट्रिक्स (गणित) है B = {0, 1}. इस तरह के मैट्रिक्स का उपयोग परिमित सेटों की एक जोड़ी के बीच एक द्विआधारी संबंध का प्रतिनिधित्व करने के लिए किया जा सकता है। यह संयोजी गणित और सैद्धांतिक कंप्यूटर विज्ञान में एक महत्वपूर्ण उपकरण है।

एक संबंध का मैट्रिक्स प्रतिनिधित्व

यदि R परिमित अनुक्रमित सेट X और Y के बीच एक द्विआधारी संबंध है (इसलिए R ⊆ X ×Y ), तब R को तार्किक मैट्रिक्स M द्वारा दर्शाया जा सकता है, जिसकी पंक्ति और स्तंभ सूचकांक क्रमशः X और Y के तत्वों को अनुक्रमित करते हैं, जैसे कि M की प्रविष्टियाँ परिभाषित होती हैं

$m_{i,j}={\begin{cases}1&(x_{i},y_{j})\in R,\\0&(x_{i},y_{j})\not \in R.\end{cases}}$

मैट्रिक्स की पंक्ति और स्तंभ संख्याओं को निर्दिष्ट करने के लिए, सेट X और Y को धनात्मक पूर्णांकों के साथ अनुक्रमित किया जाता है: i की श्रेणी 1 से लेकर X की प्रमुखता (आकार) तक होती है, और j की सीमा 1 से Y की कार्डिनैलिटी तक होती है। देखें अधिक विवरण के लिए अनुक्रमित सेट पर लेख।

उदाहरण

सेट पर द्विआधारी संबंध आर {1, 2, 3, 4}{{{1}}} को परिभाषित किया गया है ताकि 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)} .

तार्किक मैट्रिक्स के रूप में संबंधित प्रतिनिधित्व है

${\begin{pmatrix}1&1&1&1\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}},$

जिसमें एक का विकर्ण शामिल है, क्योंकि प्रत्येक संख्या स्वयं को विभाजित करती है।

अन्य उदाहरण

• एक क्रमचय मैट्रिक्स एक (0, 1)-मैट्रिक्स है, जिसके सभी कॉलम और पंक्तियों में प्रत्येक में बिल्कुल एक शून्येतर तत्व होता है।
  • एक कोस्टास सरणी क्रमचय मैट्रिक्स का एक विशेष मामला है।
• साहचर्य और परिमित ज्यामिति में एक घटना मैट्रिक्स में बिंदुओं (या कोने) और ज्यामिति की रेखाओं, ब्लॉक डिजाइन के ब्लॉक, या ग्राफ़ के किनारों (असतत गणित) के बीच घटनाओं को इंगित करने के लिए होता है।
• प्रसरण के विश्लेषण में एक डिजाइन मैट्रिक्स एक (0, 1)-मैट्रिक्स है जिसमें निरंतर पंक्ति योग होते हैं।
• एक तार्किक मैट्रिक्स ग्राफ़ सिद्धांत में एक आसन्न मैट्रिक्स का प्रतिनिधित्व कर सकता है: गैर-सममित मैट्रिक्स मैट्रिक्स निर्देशित ग्राफ़ के अनुरूप होते हैं, सममित मैट्रिक्स सामान्य ग्राफ़ (असतत गणित) के लिए होते हैं, और विकर्ण पर 1 एक लूप (ग्राफ़ सिद्धांत) से मेल खाता है संगत शीर्ष।
• एक सरल, अप्रत्यक्ष द्विदलीय ग्राफ का सहखंडज मैट्रिक्स एक (0,-1)-मैट्रिक्स है, और कोई भी (0,-1)-मैट्रिक्स इस तरह से उत्पन्न होता है।
• m वर्ग-मुक्त पूर्णांक | वर्ग-मुक्त, चिकनी संख्या | n-चिकनी संख्या की सूची के प्रमुख कारकों को m × π(n) (0, 1)-मैट्रिक्स के रूप में वर्णित किया जा सकता है, जहां π अभाज्य है- गिनती समारोह, और ए_ij 1 है यदि और केवल यदि j th अभाज्य i th संख्या को विभाजित करता है। यह प्रतिनिधित्व द्विघात छलनी फैक्टरिंग एल्गोरिथम में उपयोगी है।
• केवल दो रंगों में पिक्सेल वाले रेखापुंज ग्राफिक्स को (0, 1)-मैट्रिक्स के रूप में दर्शाया जा सकता है जिसमें शून्य एक रंग के पिक्सेल का प्रतिनिधित्व करते हैं और दूसरे रंग के पिक्सेल का प्रतिनिधित्व करते हैं।
• गो (खेल) के खेल में खेल के नियमों की जांच के लिए एक बाइनरी मैट्रिक्स का उपयोग किया जा सकता है।
• चार-मूल्यवान तर्क # दो बिट्स की मैट्रिक्स मशीन, 2x2 तार्किक मैट्रिक्स द्वारा रूपांतरित, एक परिमित राज्य मशीन बनाती है।

कुछ गुण

बूलियन बीजगणित का उपयोग करते हुए दो तार्किक आव्यूहों का गुणन।

एक परिमित सेट पर समानता (गणित) का मैट्रिक्स प्रतिनिधित्व पहचान मैट्रिक्स I है, अर्थात, वह मैट्रिक्स जिसकी विकर्ण पर प्रविष्टियाँ सभी 1 हैं, जबकि अन्य सभी 0 हैं। अधिक सामान्यतः, यदि संबंध R संतुष्ट करता है I ⊆ R, तो R एक स्वतुल्य संबंध है।

यदि बूलियन डोमेन को मोटी हो जाओ के रूप में देखा जाता है, जहां योग तार्किक OR और गुणा तार्किक AND से मेल खाता है, तो दो संबंधों के संबंधों की संरचना का मैट्रिक्स प्रतिनिधित्व इन संबंधों के मैट्रिक्स प्रतिनिधित्व के मैट्रिक्स उत्पाद के बराबर होता है। इस उत्पाद की गणना अपेक्षित मान समय O(n²). अक्सर, बाइनरी मैट्रिसेस पर संचालन को मॉड्यूलर अंकगणितीय मॉड 2 के संदर्भ में परिभाषित किया जाता है-अर्थात, तत्वों को गैलोज़ क्षेत्र के तत्वों के रूप में माना जाता है। GF(2) = ℤ₂. वे विभिन्न प्रकार के अभ्यावेदन में उत्पन्न होते हैं और कई अधिक प्रतिबंधित विशेष रूप होते हैं। उन्हें लागू किया जाता है उदा। XOR-संतुष्टि में। विशिष्ट एम-बाय-एन बाइनरी मैट्रिक्स की संख्या 2 के बराबर है^एमएन, और इस प्रकार परिमित है।

जाली

चलो एन और एम दिया जाता है और यू को सभी तार्किक एम × एन मैट्रिक्स के सेट को इंगित करते हैं। तब U द्वारा दिया गया आंशिक क्रम है

$\forall A,B\in U,\quad A\leq B\quad {\text{when}}\quad \forall i,j\quad A_{ij}=1\implies B_{ij}=1.$

वास्तव में, यू संचालन के साथ एक बूलियन बीजगणित बनाता है और (तर्क) और या (तर्क) दो मैट्रिक्स के बीच घटक-वार लागू होता है। एक तार्किक मैट्रिक्स का पूरक सभी शून्य और उनके विपरीत के लिए अदला-बदली करके प्राप्त किया जाता है।

हर तार्किक मैट्रिक्स A = (A_ij) में स्थानान्तरण है A^T = (A_ji). मान लीजिए A एक तार्किक आव्यूह है जिसमें कोई स्तंभ या पंक्तियाँ बिल्कुल शून्य नहीं हैं। फिर मैट्रिक्स उत्पाद, बूलियन अंकगणित का उपयोग करते हुए, $A^{\operatorname {T} }A$ m × m पहचान मैट्रिक्स और उत्पाद शामिल हैं $AA^{\operatorname {T} }$ n × n पहचान शामिल है।

एक गणितीय संरचना के रूप में, बूलियन बीजगणित यू समावेशन (तर्क) द्वारा आदेशित एक जाली (क्रम) बनाता है; इसके अतिरिक्त यह मैट्रिक्स गुणन के कारण गुणक जाली है।

U में प्रत्येक तार्किक मैट्रिक्स एक द्विआधारी संबंध से मेल खाता है। यू पर ये सूचीबद्ध संचालन, और ऑर्डरिंग, एक बीजगणितीय तर्क # संबंधों की गणना के अनुरूप है, जहां मैट्रिक्स गुणन संबंधों की संरचना का प्रतिनिधित्व करता है।

तार्किक वैक्टर

Group-like structures

	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.

यदि एम या एन एक के बराबर है, तो एम × एन तार्किक मैट्रिक्स (एम_ij) एक तार्किक वेक्टर या बिट स्ट्रिंग है। यदि m = 1, सदिश एक पंक्ति सदिश है, और यदि n = 1, यह एक स्तंभ सदिश है। किसी भी स्थिति में 1 के बराबर सूचकांक को सदिश के निरूपण से हटा दिया जाता है।

कल्पना करना $(P_{i}),\,i=1,2,\ldots ,m$ और $(Q_{j}),\,j=1,2,\ldots ,n$ दो तार्किक वैक्टर हैं। पी और क्यू के बाहरी उत्पाद का परिणाम एम × एन आयताकार संबंध में होता है

$m_{ij}=P_{i}\land Q_{j}.$

ऐसे मैट्रिक्स की पंक्तियों और स्तंभों का पुनर्क्रमण सभी को मैट्रिक्स के एक आयताकार भाग में इकट्ठा कर सकता है। मान लीजिए h सभी का सदिश है। तब यदि v एक स्वेच्छ तार्किक सदिश है, तो संबंध R = v h^T में v द्वारा निर्धारित स्थिर पंक्तियाँ हैं। संबंधों की गणना में ऐसे R को सदिश कहा जाता है।एक विशेष उदाहरण सार्वभौमिक संबंध है $hh^{\operatorname {T} }$.

किसी दिए गए संबंध R के लिए, R में निहित एक अधिकतम आयताकार संबंध को R में एक अवधारणा कहा जाता है। संबंधों को अवधारणाओं में विघटित करके अध्ययन किया जा सकता है, और फिर विषम संबंध # प्रेरित अवधारणा जाली को ध्यान में रखते हुए।

समूह-जैसी संरचनाओं की तालिका पर विचार करें, जहाँ अनावश्यक को 0 से निरूपित किया जा सकता है, और आवश्यक को 1 से निरूपित किया जाता है, जिससे एक तार्किक मैट्रिक्स बनता है $R.$ के तत्वों की गणना करने के लिए $RR^{\operatorname {T} }$, इस मैट्रिक्स की पंक्तियों में तार्किक वैक्टर के जोड़े के तार्किक आंतरिक उत्पाद का उपयोग करना आवश्यक है। यदि यह आंतरिक उत्पाद 0 है, तो पंक्तियाँ ओर्थोगोनल हैं। वास्तव में, छोटी श्रेणी quasigroup के लिए ऑर्थोगोनल है, और groupoid मेग्मा के लिए ऑर्थोगोनल है। नतीजतन में शून्य हैं $RR^{\operatorname {T} }$, और यह एक सार्वभौमिक संबंध बनने में विफल रहता है।

पंक्ति और स्तंभ योग

तार्किक मैट्रिक्स में सभी को जोड़ना दो तरीकों से पूरा किया जा सकता है: पहले पंक्तियों का योग या पहले स्तंभों का योग। जब पंक्ति योग जोड़े जाते हैं, तो योग वही होता है जब स्तंभ योग जोड़े जाते हैं। घटना ज्यामिति में, मैट्रिक्स को एक घटना मैट्रिक्स के रूप में व्याख्या की जाती है जिसमें पंक्तियों के साथ बिंदु और कॉलम ब्लॉक के रूप में होते हैं (बिंदुओं से बनी सामान्य रेखाएं)। एक पंक्ति योग को इसकी बिंदु डिग्री कहा जाता है, और एक स्तंभ योग को ब्लॉक डिग्री कहा जाता है। बिंदु अंशों का योग ब्लॉक अंशों के योग के बराबर होता है। क्षेत्र में एक प्रारंभिक समस्या दी गई बिंदु डिग्री और ब्लॉक डिग्री के साथ एक घटना संरचना के अस्तित्व के लिए आवश्यक और पर्याप्त परिस्थितियों को खोजने की थी; या मैट्रिक्स भाषा में, (0, 1)-मैट्रिक्स के प्रकार v × b के अस्तित्व के लिए दी गई पंक्ति और कॉलम योग के साथ।यह समस्या गेल-रायसर प्रमेय द्वारा हल की गई है।

यह भी देखें

• मैट्रिसेस की सूची
• डी ब्रुइज़न टोरस (एक बाइनरी डी ब्रुइज़न टोरस)
• बिट सरणी
• रेडहेफर मैट्रिक्स
• ट्रुथ टेबल
• तीन-मूल्यवान तर्क

संदर्भ

• Richard A. Brualdi (2006), Combinatorial Matrix Classes. Encyclopedia of Mathematics and its Applications, 108. Cambridge University Press, Cambridge, 2006. ISBN 978-0-521-86565-4
• Richard A. Brualdi & Herbert J. Ryser (1991), Combinatorial Matrix Theory. Encyclopedia of Mathematics and its Applications, 39. Cambridge University Press, Cambridge, 1991. ISBN 0-521-32265-0
• 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.
• H.J. Ryser (1960), "Traces of matrices of zeroes and ones", Canadian Journal of Mathematics 12: 463–76.
• H.J. Ryser (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]