หลักการเพิ่มเข้าและตัดออก

จากวิกิพีเดีย สารานุกรมเสรี
แผนภาพหลักการเพิ่มเข้าและตัดออกสำหรับกรณี 3 เซต

ใน คณิตศาสตร์เชิงการจัด หลักการเพิ่มเข้าและตัดออก (อังกฤษ: inclusion–exclusion principle) เป็นสมการแสดงความสัมพันธ์ของจำนวนสมาชิกของเซตจำกัดสองเซตที่นำมายูเนียนกัน โดยหากกำหนด A และ B เป็นเซตจำกัดแล้ว

|A \cup B| = |A| + |B| - |A \cap B|. \,

ความหมายของสมการนี้คือจำนวนสมาชิกของเซตจำกัดสองเซตที่นำมายูเนียนกัน มีค่าเท่ากับผลบวกของจำนวนสมาชิกของเซตทั้งสอง ลบกับจำนวนสมาชิกของอินเตอร์เซกชันของเซตทั้งสอง ในทำนองเดียวกัน สำหรับสามเซต A, B และ C

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|. \,

สมการนี้สามารถเห็นได้โดยการนับพื้นที่ส่วนต่างๆตามแผนภาพเวนน์-ออยเลอร์ด้านขวา

แต่ละพจน์ของสูตรทำให้การนับถูกเพิ่มขึ้นทีละนิด จนสุดท้ายแต่ละบริเวณของแผนภาพเวนน์-ออยเลอร์ถูกนับหนึ่งครั้งพอดี

สำหรับกรณีทั่วไปของหลักการนี้ ให้ A1, ..., An เป็นเซตจำกัด แล้ว


\begin{align}
\biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right|
-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| \\
& {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|
\end{align}

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

สูตรนี้คิดค้นโดย Abraham de Moivre แต่หนังสือบางเล่มมีการกล่าวถึง Daniel da Silva, เจมส์ โจเซฟ ซิลเวสเตอร์ (Joseph Sylvester) หรือ อ็องรี ปวงกาเร (Henri Poincaré) ในฐานะผู้ร่วมพัฒนาหลักการนี้ด้วย[ต้องการอ้างอิง]

สำหรับกรณีสามเซต A, B, C หลักการเพิ่มเข้าและตัดออกสามารถแสดงโดยแผนภาพเวนน์-ออยเลอร์ตามภาพด้านขวา

อ้างอิง[แก้]

principle of inclusion-exclusion จาก PlanetMath ภายใต้สัญญาอนุญาตครีเอทีฟคอมมอนส์