Đại số Boole¶

Estimated time to read: 20 minutes

July 06, 2021 · ~5 minutes

Định nghĩa¶

Trong đại số trừu tượng, đại số Boole là một cấu trúc đại số có các tính chất cơ bản của cả các phép toán trên tập hợp và các phép toán logic. Cụ thể, phép toán trên tập hợp được quan tâm là phép toán giao, phép toán hợp, phép toán bù và các phép toán logic là Và, Hoặc, Không.

Đại số Boole² được đặt tên theo George Boole (1815-1864) – Một nhà toán học người Anh.

Tính chất¶

Hàm Boole¶

Biến Boole¶

Định nghĩa¶

Biến \(x\) được gọi là biến Boole nếu nó chỉ nhận các giá trị trong tập \(\big\{0, 1\big\}\)

Một hàm từ tập \(\Big\{ \big( x_1, x_2, ..., x_n \big) \vert x_i \in \big \{0, 1 \big\}, 1\le i \le n \Big\}\) tới tập \(\big \{0, 1\big \}\) được gọi là một hàm Boole bậc \(n\).

Ví dụ: \(F \big(x, y, z \big) = x + y + z\) được gọi là hàm Boole bậc 3.

Dạng nối rời chính tắc của hàm Boole¶

Một vài điều cần biết¶

Các định nghĩa¶

Từ đơn là mỗi biến Boole \(x_i\) hoặc \(\neg x_i\) trong tập hợp các hàm Boole \(n\) biến \(F_n\) theo \(n\) biến \(x_1, x_2, ..., x_n\).

Đơn thức là tích khác không của một số hữu hạn từ đơn. Từ tối tiểu (đơn thức tối tiểu) là tích khác không của đúng n từ đơn. Công thức đa thức là công thức biểu diễn hàm Boole thành tổng của các đơn thức. Dạng nối rời chính tắc bản chất chính là công thức biểu diễn hàm Bool thành tổng của các từ tối tiểu.

Ví dụ¶

Xét hàm Boole với ba biến \(x,y,z\) ta có:

\(\begin{align*} \bullet \ \ & x, y,z, \neg x, \neg y, \neg z \text{ là các từ đơn.}\\ \bullet \ \ & xyz \text{ là từ tối tiểu (đơn thức tối tiểu).} \\ \bullet \ \ & xy, xz, \neg yz \text{ là các đơn thức.} \\ \bullet \ \ & xyz \wedge x\neg yz \text{ là một dạng nối rời chính tắc.} \end{align*}\)

Cách tìm dạng nối rời chính tắc cơ bản¶

Bước 1: Bổ sung các từ đơn còn thiếu vào các đơn thức.

Bước 2: Với mỗi đơn thức thu được ở bước 1, ta nhân đơn thức đó với tổng của những từ đơn bị thiếu và phần bù của nó trong đơn thức đó.

Bước 3: Tiếp tục khai triển hàm thu được ở bước 2 và loại bỏ những đơn thức bị trùng. Công thức đa thức thu được chính là dạng nối rời chính tắc của hàm Boole ban đầu.

Bài toán 1¶

Trong \(F4\) tìm dạng nối rời chính tắc: (\(F4\) ở đây ám chỉ hàm Boole 4 biến):

\(F \big( x,y,z,t \big) = xz \neg t \vee \neg y \neg z \neg t \vee xyt \vee \neg x yz \vee \neg x \neg y \neg z \neg t \vee \neg x yz \neg t\)

Giải:

Bước 1: Các từ đơn còn thiếu: \(x, \neg x, y, \neg y, z, \neg z\)

Bước 2: Các từ đơn ở bước 1 tạo thành bộ đối ngẫu (hay gọi là phần bù của nhau). Tiến hành thêm và nhân:

\(\begin{align*} F& \big( x,y,z,t \big) = f \\ f& = xz \neg t \vee \neg y \neg z \neg t \vee xyt \vee \neg x yz \vee \neg x \neg y \neg z \neg t \vee \neg x yz \neg t \\ f& = xz \neg t + \neg y \neg z \neg t + xyt + \neg x yz + \neg x \neg y \neg z \neg t + \neg x yz \neg t \\ f& = x \big( y + \neg y \big) z \neg t + \big( x + \neg x \big)\neg y \neg z \neg t + xy \big(z + \neg z \big)t + \neg x yz \big(t + \neg t \big) + \neg x \neg y \neg z \neg t + \neg x yz \neg t \\ f& = xyz \neg t + x \neg y zt + x\neg y \neg z \neg t + \neg x \neg y \neg z \neg t + xyzt + xy \neg z t + \neg x yzt + \neg x yz \neg t + \neg x \neg y \neg z \neg t + \neg x y \neg z t \end{align*}\)

Bước 3: Loại bỏ những đơn thức bị trùng

\(f = xyz \neg t + x \neg y z \neg t + x \neg y \neg z \neg t + \neg x \neg y \neg z \neg t + xyzt + xy \neg z t + \neg x yzt + \neg x yz \neg t + \neg x y \neg z t\)

Đây cũng chính là dạng nối rời chính tắc cần tìm.

Bìa Karnaugh (bìa Kar)¶

Một vài thông tin¶

Thông tin về bìa Kar¶

Bìa Karnaugh (hay sơ đồ Các-nô, biểu đồ Veitch) là một công cụ vô cùng thuận tiện cho việc đơn giản các biểu thức trong đại số Boole. Hoạt động dựa theo nguyên lí mã Gray¹ (hai bộ kí số liên tiếp đối ngẫu nhau).

Tham khảo thêm¶

Bìa Karnaugh (VN)

Bìa Karrnaugh(EN)

Mã Gray

Các cách biểu diễn bìa Kar¶

Biểu diễn theo từ đơn¶

Biểu diễn theo dạng kí số (đưa từ đơn ra ngoài)¶

Một vài thuật ngữ trong bìa Kar¶

Tế bào, tế bào lớn¶

\(T\) là tế bào của bìa Kar thì \(T\) là hình chữ nhật (theo nghĩa rộng) gồm \(2^{n-k}\) ô với \(0 \le k \le n\)

Giả sử \(T\) là 1 tế bào lớn của bìa Kar thì:

• \(T\) là một tế bào và \(T \subseteq Kar \big(f\big)\)
• Hơn nữa: \(\nexists \ T^{'}: T^{'} \ne T \wedge T \subseteq T^{'} \subseteq Kar \big(f\big)\)

Cách dùng bìa Kar trong việc đơn giản biểu thức¶

Cách dùng¶

Đối chiếu các đơn thức trong biểu thức đại số Boole xem từ đơn nào không xuất hiện trong các đơn thức đấy, thì chúng ta sẽ điền vào bảng các kí số 0 hoặc 1 (các kí số này là do người ra đề quy định) vào bảng sao cho các kí số này tạo thành 1 tế bào là cho chúng từ đơn trong biểu thức đại số Boole ban đầu không xuất hiện.

Ta cùng quay lại bài toán 1, ở đây ta sẽ điền các kí số 0 hoặc 1 vào bìa Kar sao cho hợp lí

Từ bìa Kar ở trên ta dễ dàng thấy được dạng nối rời chính tắc của hàm Boole đã cho, bản chất nó chính là tổng các tế bào gồm 1 ô duy nhất. Và công dạng nối rời chính tắc cần tìm

\(f = xyz \neg t + x \neg y z \neg t + x \neg y \neg z \neg t + \neg x \neg y \neg z \neg t + xyzt + xy \neg z t + \neg x yzt + \neg x yz \neg t + \neg x y \neg z t\)

Hướng tiếp cận bìa Kar theo dạng thể hiện các kí số¶

Câu hỏi Trả lời Ràng buộc cho hướng tiếp cận này

Câu hỏi

Các bạn sẽ thấy điều kì lạ ở hình trên và sẽ đặt ra câu hỏi là tại sao đi theo hàng ngang và hàng dọc thì lại là 01 rồi đến 11, nó phải là 01 rồi mới đến 10 chứ ?

Trả lời

Để trả lời cho câu hỏi này chúng ta sẽ đi tiếp phần phía dưới.

Ràng buộc

Nếu bạn biểu diễn bìa Kar theo dạng đưa kí số vào thì bắt buộc bạn phải điền bộ số gồm 2 kí số giống hệt hình phía bên trên và đặt chỉ số như sau:

Những con số \(0, 1, 2,... , 15\) đã điền ở trên thật chính là các con số chỉ thứ tự của bộ trạng thái \(\big(x, y, z, t \big)\) được thể hiện trong bảng chân trị 4 biến theo mã Gray trải dài từ trạng thái \(0000\) đến trạng thái \(1111\) chứ hoàn toàn không phải điền một cách tùy ý.

Quay trở lại bài toán 1, thay vì ta xem \(x, y, z, t\) là các biến thì ta sẽ tìm cách đơn giản hơn (cho máy tính hiểu) chuyển hết về kí số và điền như sau:

Mở rộng cho việc ứng dụng bìa Kar vào việc rút gọn tốt giản¶

(hay còn gọi là tìm công thức đa thức tối tiểu) trong hàm Boole (xem ảnh dưới đây)

Từ hình ảnh trên, ta tìm kiếm được 1 vài thứ

1. Các tế bào lớn: \(x\neg t \neg t, xz \neg t, yz, yt, \neg y \neg z \neg t\)
2. Một vài hàm Boole được rút gọn: \(\left[ \begin{array}{cc} f = x \neg y \neg t + xz \neg t + yz + yt + \neg y \neg z \neg t \\ f = xz \neg t + yz + yt + \neg y \neg z \neg t \\ f = x \neg y \neg t + xz \neg t + yz + yt \\ ... \end{array} \right.\)
3. Hàm Boole được rút gọn tối giản: \(\left[ \begin{array}{cc} f = x \neg y \neg t + xz \neg t + yz + yt \\ f = xz \neg t + \neg y \neg z \neg t + yz + yt \end{array} \right.\)

Để trả lời cho câu hỏi này thì cũng khó có thể trả lời sao cho hợp lí, vì mỗi người mỗi cách nhận định về vấn đề này, bạn đọc có thể tìm hiểu kĩ hoặc làm cách nào đó nếu muốn hiểu bản chất của cách trên hoặc có thể bắt đầu từ 1 cách cơ sở nhất mà tôi sắp trình bày.

Dưới đây tôi sẽ cung cấp thêm 1 cách chính quy khác để thực hiện việc tối giản biểu thức hàm Boole dễ dàng hơn.

Một cách chính quy khác¶

Dưới đây là một cách chính quy khác trong việc dùng bìa Kar để tối giản hàm Boole

Định nghĩa về phủ tối tiểu của một tập hợp¶

Cho \(S =\big\{X_1, X_2, ..., X_n \big\}\) là họ các tập con của \(X\). Khi đó \(S\) được gọi là phủ của \(X\) nếu \(X=\cup X_i\) Giả sử \(S\) là phủ của \(X\). Khi đó, \(S\) được gọi là phủ tối tiểu của \(X\) nếu với mọi \(i\) sao cho \(S \setminus X_i\) không là phủ của \(X\). Ngược lại với điều trên thì \(S\) được gọi là phủ không tối tiểu của \(X\) .

Thuật toán tìm công thức đa thức tối tiểu của hàm Boole \(f\)¶

Bước 1: Vẽ biểu đồ Karnaugh của \(f\)

Bước 2: Xác định tất cả các tế bào lớn của \(Kar\big(f\big)\)

Bước 3: Xác định tất cả các tế bào lớn \(m\) nhất thiết phải chọn - Ta nhất thiết phải chọn tế bào lớn \(T\) khi tồn tại một ô của \(Kar\big(f\big)\) mà ô này chỉ nằm trong đúng tế bào lớn \(T\) đó mà không nằm trong bất kì tế bào lớn nào khác.

Bước 4: Xác định phủ tối tiểu gồm các tế bào lớn:

• Nếu các tế bào lớn được chọn ở Bước 3 đã phủ được \(Kar\big(f\big)\) thì ta có duy nhất một phủ tối tiểu gồm các tế bào lớn của \(Kar\big(f\big)\)

• Nếu các tế bào lớn được chọn ở bước 3 chưa phủ được \(Kar\big(f\big)\) thì:

  1. Xét một ô chưa bị phủ, lúc này sẽ có ít nhất hai tế bào lớn chứa ô này, ta chọn một trong các tế bào lớn này. Cứ tiếp tục như thế, ta sẽ tìm được tất cả các phủ gồm các tế bào lớn của \(Kar\big(f\big)\)

  2. Loại bỏ các phủ không tối tiểu, ta tìm được tất cả các phủ tối tiểu gồm các tế bào lớn của \(Kar\big(f\big)\)

Bước 5:: Xác định công thức đa thức tối tiểu củ \(f\)

• Từ những phủ tối tiểu ta đã tìm được ở Bước 4, ta sẽ xác định được các công thức đa thức tối tiểu tương ứng của \(f\)
• Loại bỏ các công thức đa thức mà có một công thức đa thức mà đơn giản hơn chúng.
• Các công thức đa thức còn lại chính là công thức đa thức tối tiểu của \(f\)

Thuật toán trên nếu mà đọc thì sẽ có phần rất khó hiểu, để làm rõ hơn tôi sẽ trình bày thuật toán trên ở bài toán bên dưới.

Bài toán 2¶

Tìm các công thức đa thức tối tiểu của hàm Boole \(f\) được thể hiện bằng bìa \(Kar\) dưới đây

Bước 1: Ta tiến hành tiếp cận bài toán trên bằng việc tìm đánh chỉ số cho các tế bào lớn - hình bên dưới

Bước 2: Ta có các tế bào lớn: \(T_1 = yt, T_2 = \neg y \neg t, T_3 = xy, T_4 = x\neg t\)

Bước 3: Từ hình trên ta nhận thấy có 4 ô (mỗi ô chỉ có 1 chỉ số duy nhất) thỏa mãn để ta bắt buộc chọn các tế bào lớn mà có mặt các chỉ số đó, tức là tế bào lớn \(T_1\) và tế bào lớn \(T_2\) là 2 tế bào lớn bắt buộc phải chọn.

Bước 4: Sau khi chọn xong 2 tế bào lớn thì vẫn chưa phủ hết bìa \(Kar\), lúc này trên bìa \(Kar\) các ô còn lại đều có 2 chỉ số trong 1 ô, cụ thể là thuộc 2 tế bào lớn \(T_3\) và \(T_4\). Tức là ta có 2 cách chọn tiếp. Từ các bước trên, ta có sơ đồ phủ dưới đây:

Từ sơ đồ phủ trên, dễ dàng thấy được \(\left[ \begin{array}{cc} Kar\big(f\big) = T_1 \cup T_2 \cup T_3 \ \big(1\big) \\ Kar\big(f\big) = T_1 \cup T_2 \cup T_4 \ \big(2\big) \end{array} \right.\)

Do \(\big(1\big)\) và \(\big(2\big)\) đều là các phủ tối tiểu nên ta nhận cả 2.

Bước 5: Từ hai phủ tối tiểu của bước 4, ta lập ra 2 công thức đa thức mà đều đơn giản như nhau, do đó ta kết luận hàm Boole \(f\) đã cho có 2 công thức đa thức tối tiểu. Cụ thể 2 công thức tối tiểu đó là \(\left[ \begin{array}{cc} f = yt + \neg y \neg t + xy \\ f = yt + \neg y \neg t + x\neg t \end{array} \right.\)

Tham khảo thêm¶

George Boole

Gray code

Boolean

Comments