พีชคณิตบูลีน — กฎ ทฤษฎีบท และการย่อรูป

พีชคณิตบูลีนเป็นระบบที่ใช้รวมและย่อรูปนิพจน์จริง/เท็จ หากคุณกำลังพยายามลดรูปนิพจน์ตรรกะ เช่น $AB + A\overline{B}$ เครื่องมือหลักคือกฎต่าง ๆ เช่น กฎส่วนเติมเต็ม กฎการแจกแจง กฎการดูดกลืน และทฤษฎีบทของเดอมอร์แกน

ในการเขียนแบบที่ใช้กันทั่วไป $x + y$ หมายถึง OR, $xy$ หมายถึง AND และ $\overline{x}$ หมายถึง NOT $x$ บางเล่มเขียน NOT เป็น $x'$ แต่กฎพื้นฐานยังเหมือนเดิม

พีชคณิตบูลีนหมายถึงอะไร

พีชคณิตทั่วไปทำงานกับจำนวน ส่วนพีชคณิตบูลีนทำงานกับข้อความหรือ ตัวแปรฐานสองที่รับค่าได้เพียงสองค่าเท่านั้น คือ จริง/เท็จ หรือ $1/0$

สิ่งนี้ทำให้กฎเปลี่ยนไป ในพีชคณิตบูลีน

$$x + x = x \quad \text{and} \quad xx = x$$

อัตลักษณ์ทั้งสองนี้สื่อความหมายเดียวกัน คือ การทำเงื่อนไขเดิมซ้ำไม่ได้สร้างผลลัพธ์ใหม่ หากสวิตช์เปิดอยู่แล้ว การพูดว่า "เปิด OR เปิด" ก็ไม่ได้เปลี่ยนอะไร

กฎของพีชคณิตบูลีนที่ใช้จริง

นี่คือกฎที่พบได้บ่อยที่สุดเมื่อคุณย่อรูปนิพจน์บูลีน

กฎเอกลักษณ์

$$x + 0 = x, \qquad x \cdot 1 = x$$

การบวกด้วย false ไม่เปลี่ยนค่า และการ AND กับ true ก็ไม่เปลี่ยนค่า

กฎศูนย์

$$x + 1 = 1, \qquad x \cdot 0 = 0$$

ถ้า OR มี true อยู่แล้ว ผลลัพธ์ทั้งหมดจะเป็น true ถ้า AND มี false อยู่ ผลลัพธ์ทั้งหมดจะเป็น false

กฎไอดีมโพเทนต์

$$x + x = x, \qquad x \cdot x = x$$

การเขียนตัวแปรเดิมซ้ำไม่ทำให้นิพจน์เปลี่ยนไป

กฎส่วนเติมเต็ม

$$x + \overline{x} = 1, \qquad x \cdot \overline{x} = 0$$

ตัวแปรหนึ่งกับค่าตรงข้ามของมันครอบคลุมทุกกรณีใน OR แต่จะไม่เกิดพร้อมกันใน AND

กฎสลับที่และกฎเปลี่ยนหมู่

$$x + y = y + x, \qquad xy = yx$$ $$(x + y) + z = x + (y + z), \qquad (xy)z = x(yz)$$

กฎเหล่านี้ทำให้คุณสลับลำดับหรือจัดกลุ่มพจน์ใหม่ได้โดยไม่เปลี่ยนผลลัพธ์

กฎการแจกแจง

$$x(y + z) = xy + xz$$ $$x + yz = (x + y)(x + z)$$

รูปแบบที่สองอาจดูไม่คุ้นเคยน้อยกว่า แต่เป็นอัตลักษณ์มาตรฐานของพีชคณิตบูลีน และมักปรากฏตอนแยกตัวประกอบ

กฎการดูดกลืน

$$x + xy = x, \qquad x(x + y) = x$$

กฎเหล่านี้มีประโยชน์มากเป็นพิเศษเมื่อนิพจน์ดูยาวกว่าที่จริงเป็น

ทฤษฎีบทของเดอมอร์แกน

$$\overline{x + y} = \overline{x}\,\overline{y}, \qquad \overline{xy} = \overline{x} + \overline{y}$$

กฎเหล่านี้บอกว่าการปฏิเสธเคลื่อนผ่าน OR และ AND อย่างไร เมื่อ NOT ผ่านวงเล็บ OR และ AND จะสลับบทบาทกัน

ตัวอย่างทำจริง: ย่อรูป $AB + A\overline{B}$

เริ่มจาก

$$F = AB + A\overline{B}$$

ดึง $A$ ที่เป็นตัวประกอบร่วมออกมา:

$$F = A(B + \overline{B})$$

ตอนนี้ใช้กฎส่วนเติมเต็ม:

$$F = A \cdot 1$$

จากนั้นใช้กฎเอกลักษณ์:

$$F = A$$

ดังนั้น $AB + A\overline{B} = A$ ในเชิงสัญชาตญาณ ถ้า $A = 1$ ไม่ว่า $B = 1$ หรือ $\overline{B} = 1$ ก็ต้องมีหนึ่งพจน์เป็นจริง ถ้า $A = 0$ ทั้งสองพจน์จะเป็นเท็จ นิพจน์ทั้งหมดจึงขึ้นอยู่กับ $A$ เท่านั้น

ข้อผิดพลาดที่พบบ่อยในพีชคณิตบูลีน

ข้อผิดพลาดที่พบบ่อยอย่างหนึ่งคือการนำความเคยชินจากพีชคณิตทั่วไปมาใช้กับพีชคณิตบูลีน เช่น $x + x = 2x$ ไม่ใช่กฎของบูลีน ในที่นี้ผลลัพธ์ที่ถูกต้องคือ $x$

อีกข้อผิดพลาดหนึ่งคือใช้กฎโดยไม่ตรวจสอบสัญลักษณ์ ในหลายตำรา $+$ หมายถึง OR ไม่ใช่การบวกแบบเลขคณิต และการเขียนตัวแปรติดกันหมายถึง AND

นักเรียนยังมักใช้ทฤษฎีบทของเดอมอร์แกนผิด โดยใส่เครื่องหมายปฏิเสธให้แต่ละตัวแปร แต่ลืมสลับ OR กับ AND ทั้งสองส่วนนี้สำคัญพอ ๆ กัน

พีชคณิตบูลีนถูกใช้ที่ไหน

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

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

ลองย่อรูปที่คล้ายกัน

ลองย่อรูป $(A + B)(A + \overline{B})$ ดู หากคุณใช้กฎข้างต้นอย่างระมัดระวัง มันจะยุบลงมากกว่าที่เห็นในตอนแรก ถ้าอยากไปอีกขั้น ลองสร้างตารางค่าความจริงและตรวจดูว่ารูปที่ย่อแล้วให้ผลตรงกันทุกแถว