المصفوفة المنطقية

المصفوفة المنطقية ، أو المصفوفة الثنائية ، أو مصفوفة العلاقات ، أو المصفوفة البوليانية ، أو مصفوفة (0، 1)، هي مصفوفة عناصرها تنتمي إلى المجال البولياني B = {0، 1}. يمكن استخدام هذه المصفوفة لتمثيل علاقة ثنائية بين زوج من المجموعات المنتهية . وهي أداة مهمة في الرياضيات التوافقية وعلوم الحاسوب النظرية .

إذا كانت R علاقة ثنائية بين المجموعتين المفهرستين المحدودتين X و Y (أي R ⊆ X × Y )، فيمكن تمثيل R بالمصفوفة المنطقية M التي تشير فهارس صفوفها وأعمدتها إلى عناصر X و Y على التوالي، بحيث تُعرَّف مدخلات M بواسطة

${\displaystyle 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. راجع المقالة حول المجموعات المفهرسة لمزيد من التفاصيل.

التحويل​${\displaystyle R^{T}}$من المصفوفة المنطقية${\displaystyle R}$العلاقة الثنائية تقابلها العلاقة العكسية . ^{[ 1 ]}

• مصفوفة التبديل هي مصفوفة (0، 1)، تحتوي جميع أعمدتها وصفوفها على عنصر واحد غير صفري بالضبط.
  • مصفوفة كوستاس هي حالة خاصة من مصفوفة التبديل.
• تحتوي مصفوفة الوقوع في التوافقية والهندسة المحدودة على واحدات للإشارة إلى الوقوع بين النقاط (أو الرؤوس) وخطوط الهندسة، أو كتل تصميم الكتلة ، أو حواف الرسم البياني .
• مصفوفة التصميم في تحليل التباين هي مصفوفة (0، 1) ذات مجموع صفوف ثابت.
• قد تمثل المصفوفة المنطقية مصفوفة تجاور في نظرية الرسم البياني : المصفوفات غير المتماثلة تتوافق مع الرسوم البيانية الموجهة ، والمصفوفات المتماثلة مع الرسوم البيانية العادية ، والرقم 1 على القطر يتوافق مع حلقة عند الرأس المقابل.
• مصفوفة التجاور الثنائي للرسم البياني البسيط غير الموجه ثنائي الأجزاء هي مصفوفة (0، 1)، وأي مصفوفة (0، 1) تنشأ بهذه الطريقة.
• يمكن وصف العوامل الأولية لقائمة من m أعداد خالية من المربعات، n أعداد ملساء، على أنها مصفوفة m × π ( n ) ( 0 , 1 ) ، حيث π هي دالة عد الأعداد الأولية ، ويكون a_{_ij} مساويًا لـ 1 إذا وفقط إذا كان العدد الأولي j يقسم العدد i . هذا التمثيل مفيد في خوارزمية تحليل العوامل باستخدام الغربال التربيعي .
• يمكن تمثيل صورة نقطية تحتوي على وحدات بكسل بلونين فقط كمصفوفة (0، 1) حيث تمثل الأصفار وحدات بكسل من لون واحد وتمثل الواحدات وحدات بكسل من اللون الآخر.
• يمكن استخدام المصفوفة الثنائية للتحقق من قواعد اللعبة في لعبة غو . ^{[ 2 ]}
• يشكل المنطق ذو القيم الأربع المكون من بتين، والذي يتم تحويله بواسطة مصفوفات منطقية 2 × 2، نظام انتقال .
• مخطط التكرار ومتغيراته عبارة عن مصفوفات توضح أزواج النقاط الأقرب من عتبة تقارب معينة في فضاء الطور .

التمثيل المصفوفي لعلاقة المساواة على مجموعة منتهية هو مصفوفة الوحدة I ، أي المصفوفة التي تكون جميع عناصر قطرها 1، بينما تكون جميع العناصر الأخرى 0. وبشكل أعم، إذا كانت العلاقة R تحقق I ⊆ R ، فإن R هي علاقة انعكاسية .

إذا نُظر إلى المجال البولياني على أنه شبه حلقة ، حيث يُقابل الجمع عملية "أو" المنطقية والضرب عملية "و" المنطقية ، فإن التمثيل المصفوفي لتركيب علاقتين يساوي حاصل ضرب المصفوفات للتمثيلات المصفوفية لهاتين العلاقتين. ويمكن حساب هذا الناتج في زمن متوقع قدره ^O ( n² ). ^{[ 3 ]}

في كثير من الأحيان، تُعرَّف العمليات على المصفوفات الثنائية بدلالة الحساب النمطي modulo 2 ، أي أن العناصر تُعامل كعناصر في حقل غالوا.${\displaystyle {\mathbf {GF}}(2)=\mathbb {Z} _{2}}$تظهر هذه المفاهيم في مجموعة متنوعة من التمثيلات، ولها عدد من الأشكال الخاصة الأكثر تقييدًا. وتُستخدم، على سبيل المثال، في قابلية إرضاء XOR .

عدد المصفوفات الثنائية المتميزة من الرتبة m × n يساوي 2mn ^، وبالتالي فهو محدود.

لنفترض أن n و m معطيان، ولنرمز بـ U إلى مجموعة جميع المصفوفات المنطقية من الرتبة m × n . عندئذٍ، يكون لـ U ترتيب جزئي معطى بالعلاقة التالية:

${\displaystyle \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 جبرًا منطقيًا بتطبيق العمليات " و " و" أو " بين مصفوفتين عنصرًا عنصرًا. ويُحصل على متمم المصفوفة المنطقية بتبديل جميع الأصفار والآحاد بنظائرها.

كل مصفوفة منطقية A = ( A_{_ij} ) لها منقولة A ^_T = ( A_{_ji} ). لنفترض أن A مصفوفة منطقية لا تحتوي على أي أعمدة أو صفوف تساوي أصفارًا. عندئذٍ، يكون حاصل ضرب المصفوفات، باستخدام الحساب البولياني،${\displaystyle A^{\operatorname {T} }A}$يحتوي على مصفوفة الوحدة من الرتبة m × m ، والناتج${\displaystyle AA^{\operatorname {T} }}$يحتوي على عنصر الهوية من الرتبة n × n .

كبنية رياضية، يشكل الجبر البولياني U شبكة مرتبة حسب التضمين ؛ بالإضافة إلى ذلك، فهو شبكة ضربية بسبب ضرب المصفوفات.

كل مصفوفة منطقية في U تُقابل علاقة ثنائية. هذه العمليات المذكورة على U ، والترتيب، تُقابل حساب العلاقات ، حيث يُمثل ضرب المصفوفات تركيب العلاقات . ^{[ 4 ]}

إذا كانت قيمة m أو n تساوي واحدًا، فإن المصفوفة المنطقية m × n ( m _ij ) تُمثل متجهًا منطقيًا أو سلسلة بتات . إذا كانت m = 1، فإن المتجه يكون متجه صف، وإذا كانت n = 1، فإنه يكون متجه عمود. في كلتا الحالتين، يُحذف الفهرس الذي يساوي 1 من تمثيل المتجه.

يفترض${\displaystyle (P_{i}),\,i=1,2,\ldots ,m}$و${\displaystyle (Q_{j}),\,j=1,2,\ldots ,n}$هما متجهان منطقيان. ينتج عن الضرب الخارجي لـ P و Q علاقة مستطيلة من الرتبة m × n

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

يمكن لإعادة ترتيب صفوف وأعمدة هذه المصفوفة أن تجمع كل العناصر التي تساوي واحدًا في جزء مستطيل من المصفوفة. ^{[ 5 ]}

ليكن h متجهًا جميع عناصره تساوي واحدًا. إذا كان v متجهًا منطقيًا كيفيًا، فإن العلاقة R = vh ^T لها صفوف ثابتة يحددها v . في حساب العلاقات، يُطلق على R اسم متجه. ^{[ 5 ]} ومن الأمثلة الخاصة على ذلك العلاقة الشاملة.${\displaystyle hh^{\operatorname {T} }}$.

بالنسبة لعلاقة معينة R ، تُسمى العلاقة المستطيلة القصوى الموجودة في R مفهومًا في R. يمكن دراسة العلاقات عن طريق تفكيكها إلى مفاهيم، ثم ملاحظة شبكة المفاهيم المستحثة .

لنفترض جدولًا للهياكل الشبيهة بالمجموعات، حيث يمكن الإشارة إلى "غير الضروري" بالرقم 0، وإلى "المطلوب" بالرقم 1، لتشكيل مصفوفة منطقية.${\displaystyle R.}$لحساب عناصر${\displaystyle RR^{\operatorname {T} }}$لذا، من الضروري استخدام الضرب الداخلي المنطقي لأزواج المتجهات المنطقية في صفوف هذه المصفوفة. إذا كان هذا الضرب الداخلي يساوي صفرًا، فإن الصفوف تكون متعامدة. في الواقع، الفئة الصغيرة متعامدة مع شبه المجموعة ، والزمرة الجزئية متعامدة مع الصهارة . وبالتالي، توجد أصفار في${\displaystyle RR^{\operatorname {T} }}$وهي تفشل في أن تكون علاقة عالمية .

يمكن جمع جميع القيم التي تساوي واحدًا في مصفوفة منطقية بطريقتين: جمع الصفوف أولًا أو جمع الأعمدة أولًا. عند جمع الصفوف، يكون المجموع مساويًا لمجموع الأعمدة. في هندسة التلاقي ، تُفسَّر المصفوفة على أنها مصفوفة تلاقي ، حيث تمثل الصفوف "نقاطًا" والأعمدة "كتلًا" (بتعميم الخطوط المكونة من نقاط). يُسمى مجموع الصف درجة النقطة ، ومجموع العمود درجة الكتلة . مجموع درجات النقاط يساوي مجموع درجات الكتل. ^{[ 6 ]}

تمثلت إحدى المشكلات المبكرة في هذا المجال في "إيجاد الشروط اللازمة والكافية لوجود بنية وقوع ذات درجات نقطية ودرجات كتلية معينة؛ أو بلغة المصفوفات، لوجود مصفوفة (0، 1) من النوع v  × b ذات مجاميع صفوف وأعمدة معينة". ^{[ 6 ]} وقد تم حل هذه المشكلة بواسطة نظرية غيل-رايزر . 

• قائمة المصفوفات
• Binatorix (ثنائي De Bruijn torus)
• مصفوفة بت
• مصفوفة منفصلة
• مصفوفة ريدهافر
• جدول الحقيقة
• المنطق ثلاثي القيم

• "المصفوفة المنطقية" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]