Đại số Boole — Các luật, định lý và cách rút gọn

Đại số Boole là hệ thống dùng để kết hợp và rút gọn các biểu thức đúng/sai. Nếu bạn đang muốn rút gọn một biểu thức logic như $AB + A\overline{B}$, các công cụ chính là những luật như luật bù, luật phân phối, luật hấp thụ và các định lý De Morgan.

Trong một cách ký hiệu phổ biến, $x + y$ nghĩa là OR, $xy$ nghĩa là AND, và $\overline{x}$ nghĩa là NOT $x$. Một số sách viết NOT là $x'$, nhưng các quy tắc cơ bản vẫn giống nhau.

Đại số Boole có nghĩa là gì

Đại số thông thường làm việc với các con số. Đại số Boole làm việc với các mệnh đề hoặc biến nhị phân chỉ có thể nhận hai giá trị: đúng/sai hoặc $1/0$.

Điều đó làm thay đổi các quy tắc. Trong đại số Boole,

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

Cả hai đồng nhất thức đều nói cùng một ý: lặp lại một điều kiện không tạo ra kết quả mới. Nếu một công tắc đã bật, thì nói "bật OR bật" cũng không làm thay đổi gì.

Các luật đại số Boole bạn thực sự dùng

Đây là những luật xuất hiện thường xuyên nhất khi bạn rút gọn một biểu thức Boole.

Luật đồng nhất

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

OR với false không làm thay đổi gì, và AND với true cũng không làm thay đổi gì.

Luật triệt tiêu

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

Nếu một phép OR đã chứa true, toàn bộ kết quả là true. Nếu một phép AND chứa false, toàn bộ kết quả là false.

Luật lũy đẳng

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

Lặp lại cùng một biến không làm thay đổi biểu thức.

Luật bù

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

Một biến và phần đối của nó bao phủ mọi trường hợp trong OR, nhưng không bao giờ cùng đúng trong AND.

Luật giao hoán và kết hợp

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

Các luật này cho phép bạn đổi thứ tự hoặc nhóm lại các hạng mà không làm thay đổi kết quả.

Luật phân phối

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

Dạng thứ hai thường kém quen thuộc hơn, nhưng đó là một đồng nhất thức chuẩn trong đại số Boole và thường xuất hiện khi phân tích nhân tử.

Luật hấp thụ

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

Các luật này đặc biệt hữu ích khi một biểu thức trông dài hơn bản chất thật của nó.

Các định lý De Morgan

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

Các định lý này cho biết cách một phép phủ định đi qua OR và AND. Khi NOT đi qua dấu ngoặc, OR và AND sẽ đổi vai trò cho nhau.

Ví dụ có lời giải: Rút gọn $AB + A\overline{B}$

Bắt đầu với

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

Đặt $A$ chung ra ngoài:

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

Bây giờ dùng luật bù:

$$F = A \cdot 1$$

Sau đó dùng luật đồng nhất:

$$F = A$$

Vậy $AB + A\overline{B} = A$. Về trực giác, nếu $A = 1$, thì либо $B = 1$ hoặc $\overline{B} = 1$, nên một trong hai hạng chắc chắn đúng. Nếu $A = 0$, cả hai hạng đều sai. Toàn bộ biểu thức chỉ phụ thuộc vào $A$.

Những lỗi thường gặp trong đại số Boole

Một lỗi phổ biến là mang thói quen của đại số thông thường sang đại số Boole. Ví dụ, $x + x = 2x$ không phải là một quy tắc Boole. Ở đây, kết quả đúng là $x$.

Một lỗi khác là áp dụng luật mà không kiểm tra ký hiệu. Trong nhiều tài liệu, $+$ nghĩa là OR chứ không phải phép cộng số học, và viết các biến cạnh nhau nghĩa là AND.

Sinh viên cũng hay dùng sai các định lý De Morgan bằng cách phủ định từng biến nhưng quên đổi OR thành AND và ngược lại. Cả hai phần đều quan trọng.

Đại số Boole được dùng ở đâu

Đại số Boole giữ vai trò trung tâm trong logic số, nơi các biến biểu diễn trạng thái bật/tắt hoặc đúng/sai. Nó được dùng để rút gọn thiết kế mạch, viết các điều kiện logic gọn hơn trong phần mềm, và phân tích các bộ lọc tìm kiếm hoặc truy vấn cơ sở dữ liệu.

Nếu các biến không phải là nhị phân hoặc các phép toán là số học thông thường, thì các luật Boole không áp dụng trực tiếp. Chính bối cảnh hai giá trị là điều kiện làm cho hệ thống này hoạt động.

Thử một phép rút gọn tương tự

Hãy thử rút gọn $(A + B)(A + \overline{B})$. Nếu bạn dùng các luật ở trên cẩn thận, nó sẽ rút gọn nhiều hơn so với vẻ ngoài ban đầu. Nếu muốn đi thêm một bước, hãy lập bảng chân trị và kiểm tra xem dạng đã rút gọn có khớp với mọi hàng hay không.