तार्किक आव्यूह

एक तार्किक मैट्रिक्स, बाइनरी मैट्रिक्स, रिलेशन मैट्रिक्स, बूलियन मैट्रिक्स, या (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} को परिभाषित किया गया है ताकि 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) (0, 1)-मैट्रिक्स के रूप में वर्णित किया जा सकता है, जहां π प्राइम-काउंटिंग फंक्शन समारोह, और ए_ij 1 है अगर और केवल अगर jth अभाज्य ith संख्या को विभाजित करता है। यह प्रतिनिधित्व द्विघात छलनी फैक्टरिंग एल्गोरिथम में उपयोगी है।
• केवल दो रंगों में पिक्सेल वाले रेखापुंज ग्राफिक्स को (0, 1)-मैट्रिक्स के रूप में दर्शाया जा सकता है जिसमें शून्य एक रंग के पिक्सेल का प्रतिनिधित्व करते हैं और दूसरे रंग के पिक्सेल का प्रतिनिधित्व करते हैं।
• गो (खेल) के खेल में खेल के नियमों की जांच के लिए एक बाइनरी मैट्रिक्स का उपयोग किया जा सकता है।

कुछ गुण

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

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

जाली

मान लीजिए कि n और m दिए गए हैं और U सभी तार्किक m × n आव्यूहों के समुच्चय को निरूपित करता है। तब 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 _{i j} ) एक स्थानान्तरण है A^T = ( A _{j i} ). मान लीजिए A एक तार्किक मैट्रिक्स है जिसमें कोई कॉलम या पंक्तियाँ समान रूप से शून्य नहीं हैं। फिर मैट्रिक्स उत्पाद, बूलियन अंकगणित का उपयोग करते हुए, $A^{\operatorname {T} }A$ एम × एम पहचान मैट्रिक्स, और उत्पाद शामिल है $AA^{\operatorname {T} }$ n × n पहचान शामिल है।

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

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

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

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

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

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

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

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

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.

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

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

तार्किक मैट्रिक्स में सभी को जोड़ना दो तरीकों से पूरा किया जा सकता है: पहले पंक्तियों का योग या पहले स्तंभों का योग। जब पंक्ति योग जोड़े जाते हैं, तो योग वही होता है जब स्तंभ योग जोड़े जाते हैं। घटना ज्यामिति में, मैट्रिक्स को एक घटना मैट्रिक्स के रूप में व्याख्या की जाती है जिसमें पंक्तियों के साथ बिंदु और कॉलम ब्लॉक के रूप में होते हैं (बिंदुओं से बनी सामान्य रेखाएं)। एक पंक्ति योग को इसकी बिंदु डिग्री कहा जाता है, और एक स्तंभ योग को ब्लॉक डिग्री कहा जाता है। डिजाइन थ्योरी में प्रस्ताव 1.6 कहते हैं कि बिंदु डिग्री का योग ब्लॉक डिग्री के योग के बराबर है।

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

यह भी देखें

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

संदर्भ

• 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]