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

एक तार्किक आव्यूह, बाइनरी आव्यूह, सम्बन्ध आव्यूह, बूलियन आव्यूह, या (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, 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 है अगर और केवल अगर 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]