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

एक तार्किक आव्यूह, बाइनरी आव्यूह, सम्बन्ध आव्यूह, बूलियन आव्यूह, या (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 की गणनीयता तक होती है। अधिक विवरण के लिए अनुक्रमित समुच्चय पर प्रविष्टि देखें।

उदाहरण

समुच्चय पर द्विआधारी संबंध R {1, 2, 3, 4} को परिभाषित किया गया है ताकि aRb बिना शेष अवयव के सम्मुच्य के मानों को संरक्षित कर सके और केवल a b को समान रूप से विभाजित कर सके। उदाहरण के लिए, 2R4 संरक्षित करता है क्योंकि 2 4 को विभाजित करता है और कोई शेषफल नहीं रहता है, लेकिन 3R4 संरक्षित नहीं करता है, क्योंकि जब 3 4 को विभाजित करता है तो 1 शेषफल रहता है। निम्नलिखित समुच्चय उन युग्मों का समुच्चय है जिनके लिए संबंध R संरक्षित करता है। वह आव्यूह जिसकी विकर्ण पर सभी प्रविष्टियाँ 1 हैं, जबकि अन्य सभी प्रविष्टियाँ 0 हैं।

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

कुछ गुण

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

यदि बूलियन डोमेन को अंशपरिष्कृत के रूप में देखा जाता है, जहां योग तार्किक OR और गुणा तार्किक AND से समानता रखता है, तो दो संबंधों की संरचना का आव्यूह प्रतिनिधित्व इन संबंधों के आव्यूह प्रतिनिधित्व के आव्यूह उत्पाद के बराबर होता है।

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

नियम

मान लीजिए कि 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.$

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

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

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

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

तार्किक सदिश

यदि m या n एक के बराबर है, तो m × n तार्किक आव्यूह (m_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 है, तो पंक्तियाँ लांबिक विश्लेषण हैं। यदि m या n एक के बराबर है, तो m × n तार्किक आव्यूह (m_ij) एक तार्किक सदिश है। वास्तव में, सममित समूह लूप (बीजगणित) के लिए लांबिक विश्लेषण है, छोटी श्रेणी अर्धसमूह के लिए लांबिक विश्लेषण है, और समूह भाग मेग्मा के लिए लांबिक विश्लेषण है। नतीजतन $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]