เมทริกซ์เชิงตรรกะ

จากวิกิพีเดีย สารานุกรมเสรี
(เปลี่ยนทางจาก เมทริกซ์ฐานสอง)

เมทริกซ์เชิงตรรกะ, เมทริกซ์ทวิภาค, เมทริกซ์ความสัมพันธ์, เมทริกซ์แบบบูล หรือ เมทริกซ์ศูนย์-หนึ่ง คือเมทริกซ์ที่ประกอบด้วยสมาชิกจากโดเมนแบบบูล B = {0, 1} ซึ่งสามารถใช้เป็นตัวแทนของความสัมพันธ์ทวิภาคระหว่างคู่อันดับของเซตจำกัด

การแทนความสัมพันธ์ด้วยเมทริกซ์[แก้]

ถ้า R เป็นความสัมพันธ์ทวิภาคระหว่างเซตดรรชนีจำกัด X และ Y (นั่นคือ RX×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 ไม่ลงตัว จากนิยามดังกล่าวสามารถแสดงเซตของคู่อันดับที่ทำให้ 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}