เมทริกซ์ตรรกะเมทริกซ์ไบนารีเมทริกซ์ความสัมพันธ์เมทริกซ์บูลีนหรือเมทริกซ์ (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 ดู รายละเอียดเพิ่มเติมได้ ในบทความเกี่ยวกับเซตที่มีดัชนี

เมทริกซ์ผกผัน ของความสัมพันธ์ไบนารี สอดคล้องกับความสัมพันธ์ผกผัน^{[ 1 ]}${\displaystyle R^{T}}$${\displaystyle R}$

ความสัมพันธ์ทวิภาคRบนเซต{1, 2, 3, 4}ถูกกำหนดขึ้นโดยที่aRbเป็นจริงก็ต่อเมื่อa หารb ลงตัว โดยไม่มีเศษเหลือ ตัวอย่างเช่น 2 R 4 เป็นจริงเพราะ 2 หาร 4 ลงตัวโดยไม่มีเศษเหลือ แต่ 3 R 4 ไม่เป็นจริงเพราะเมื่อ 3 หาร 4 จะมีเศษเหลือ 1 เซตต่อไปนี้คือเซตของคู่ที่ความสัมพันธ์Rเป็นจริง

{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

การแสดงผลที่สอดคล้องกันในรูปแบบเมทริกซ์ตรรกะคือ

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

ซึ่งรวมถึงแนวทแยงมุมที่ประกอบด้วยเลขหนึ่งทั้งหมด เนื่องจากแต่ละจำนวนสามารถหารตัวเองได้

• เมทริกซ์การเรียงสับเปลี่ยนคือเมทริกซ์ (0, 1) ซึ่งแต่ละคอลัมน์และแถวจะมีสมาชิกที่ไม่เป็นศูนย์เพียงตัวเดียวเท่านั้น
  • อาร์เรย์คอสตาสเป็นกรณีพิเศษของเมทริกซ์การเรียงสับเปลี่ยน
• ในเรขาคณิตเชิงการจัดเรียงและเรขาคณิตจำกัดเมทริกซ์ความสัมพันธ์ จะมีค่า เป็น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จะเป็นความสัมพันธ์สะท้อนกลับ

หากโดเมนบูลีนถูกมองว่าเป็นเซมิริงซึ่งการบวกสอดคล้องกับตรรกะ ORและการคูณสอดคล้องกับตรรกะ ANDการแสดงเมทริกซ์ของการประกอบความสัมพันธ์สองรายการจะเท่ากับผลคูณเมทริกซ์ ของการแสดงเมทริก ^ซ์ของความสัมพันธ์เหล่านี้ ผลคูณนี้สามารถคำนวณได้ใน เวลา ที่คาดหวัง O( n² ) ^{[ 3 ]}

โดยทั่วไป การดำเนินการกับเมทริกซ์ไบนารีมักถูกกำหนดในรูปของเลขคณิตมอดูลาร์ mod 2 กล่าวคือ องค์ประกอบของเมทริกซ์จะถูกมองว่าเป็นองค์ประกอบของฟิลด์กาโลอิส การดำเนินการเหล่านี้ปรากฏในรูปแบบการแสดงที่หลากหลาย และมีรูปแบบพิเศษที่จำกัดกว่าอีกหลายรูปแบบ ตัวอย่างเช่น มีการนำไปใช้ในการตรวจ สอบความพึงพอใจของการดำเนิน การ XOR${\displaystyle {\mathbf {GF}}(2)=\mathbb {Z} _{2}}$

จำนวนเมท ริกซ์ไบนารีขนาด m x n ที่แตกต่างกัน มีค่าเท่ากับ 2mn ^ซึ่งจึงเป็นจำนวนจำกัด

ให้nและmเป็นค่าที่กำหนด และให้Uแทนเซตของ เมทริกซ์ตรรกะขนาด m × n ทั้งหมด แล้วUมีลำดับบางส่วนที่กำหนดโดย

$เมื่อทุก A,B อยู่ใน U, เมื่อ A ≤ B เมื่อทุก i,j A_{ij}=1 แสดงว่า B_{ij}=1$

อันที่จริงUเป็นพีชคณิตบูลีนที่มีการดำเนินการ&หรือ ระหว่างเมทริกซ์สองเมทริกซ์ที่ใช้กับแต่ละส่วนประกอบ ส่วนเติมเต็มของเมทริกซ์ตรรกะ ได้มาจากการสลับเลขศูนย์และเลขหนึ่งทั้งหมดด้วยค่าตรงข้าม

เมทริกซ์ตรรกะทุกเมทริกซ์A = ( A _ij )จะมีเมทริกซ์สลับเปลี่ยนA ^T = ( A _ji )สมมติว่าAเป็นเมทริกซ์ตรรกะที่ไม่มีคอลัมน์หรือแถวใดเป็นศูนย์เหมือนกันทั้งหมด ผลคูณของเมทริกซ์โดยใช้เลขคณิตบูลีนจะมีเมทริกซ์เอกลักษณ์ขนาด m × mและผลคูณจะมีเมท ริก ซ์เอกลักษณ์ ขนาด n × n${\displaystyle A^{\operatorname {T} }A}$${\displaystyle AA^{\operatorname {T} }}$

ในฐานะโครงสร้างทางคณิตศาสตร์ พีชคณิตบูลีนUก่อให้เกิดแลตทิซที่เรียงลำดับโดยการรวมเข้าด้วยกันนอกจากนี้ยังเป็นแลตทิซแบบคูณเนื่องจากการคูณเมทริกซ์

เมทริกซ์ตรรกะทุกเมทริกซ์ในUสอดคล้องกับความสัมพันธ์แบบไบนารี การดำเนินการที่ระบุไว้เหล่านี้บนUและการเรียงลำดับ สอดคล้องกับแคลคูลัสของความสัมพันธ์โดยการคูณเมทริกซ์แสดงถึงการประกอบความสัมพันธ์^{[ 4 ]}

ถ้าmหรือnเท่ากับหนึ่งเมทริกซ์ตรรกะm × n ( m _ij ) จะเป็นเวกเตอร์ตรรกะหรือสตริงบิตถ้าm = 1 เวกเตอร์นั้นจะเป็นเวกเตอร์แถว และถ้าn = 1 จะเป็นเวกเตอร์คอลัมน์ ในทั้งสองกรณี ดัชนีที่เท่ากับ 1 จะถูกตัดออกจากการแสดงเวกเตอร์

สมมติว่า P และQเป็นเวกเตอร์ตรรกะสองตัว ผล คูณภายนอกของPและ Q จะได้ความสัมพันธ์แบบสี่เหลี่ยมผืนผ้าขนาดm × n${\displaystyle (P_{i}),\,i=1,2,\ldots ,m}$${\displaystyle (Q_{j}),\,j=1,2,\ldots ,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 ซึ่งก่อให้เกิดเมทริกซ์เชิงตรรกะในการคำนวณองค์ประกอบของเมทริกซ์นี้ จำเป็นต้องใช้ผลคูณภายในเชิงตรรกะของคู่เวกเตอร์เชิงตรรกะในแถวของเมทริกซ์นี้ หากผลคูณภายในนี้เป็น 0 แสดงว่าแถวนั้นตั้งฉากกัน ในความเป็นจริงหมวดหมู่ขนาดเล็กตั้งฉากกับควาซิกรุปและกรุปอยด์ตั้งฉากกับแมกมาดังนั้นจึงมีศูนย์อยู่ในเมทริก ซ์นี้ และ เมท ริกซ์ นี้จึงไม่ใช่ความสัมพันธ์สากล${\displaystyle R.}$${\displaystyle RR^{\operatorname {T} }}$${\displaystyle RR^{\operatorname {T} }}$

การรวมเลข 1 ทั้งหมดในเมทริกซ์ตรรกะสามารถทำได้สองวิธี: บวกแถวก่อนหรือบวกคอลัมน์ก่อน เมื่อบวกผลรวมของแถว ผลรวมจะเท่ากับเมื่อบวกผลรวมของคอลัมน์ ในเรขาคณิตเหตุการณ์เมทริกซ์จะถูกตีความว่าเป็นเมทริกซ์เหตุการณ์โดยที่แถวสอดคล้องกับ "จุด" และคอลัมน์เป็น "บล็อก" (ซึ่งเป็นการขยายความของเส้นที่ประกอบด้วยจุด) ผลรวมของแถวเรียกว่าระดับจุดและผลรวมของคอลัมน์เรียกว่าระดับบล็อกผลรวมของระดับจุดเท่ากับผลรวมของระดับบล็อก^{[ 6 ]}

ปัญหาแรกๆ ในพื้นที่นี้คือ "การค้นหาเงื่อนไขที่จำเป็นและเพียงพอสำหรับการมีอยู่ของโครงสร้างเหตุการณ์ที่มีระดับจุดและระดับบล็อกที่กำหนด หรือในภาษาเมทริกซ์ สำหรับการมีอยู่ของเมทริกซ์ (0, 1) ประเภทv  ×  bที่มีผลรวมแถวและคอลัมน์ที่กำหนด" ^{[ 6 ]}ปัญหานี้ได้รับการแก้ไขโดยทฤษฎีบท Gale–Ryser

• รายการเมทริกซ์
• Binatorix (พรูไบนารี De Bruijn)
• อาร์เรย์บิต
• เมทริกซ์แยกส่วน
• เมทริกซ์เรดเฮฟเฟอร์
• ตารางความจริง
• ตรรกะสามค่า

วิกิมีเดียคอมมอน ส์มีสื่อที่เกี่ยวข้องกับเมทริกซ์ไบนารี

• "เมทริกซ์ตรรกะ" , สารานุกรมคณิตศาสตร์ , EMS Press , 2001 [1994]