Định nghĩa

Tính chất

Cho một đại số Boole \(\big(A, \wedge, \vee, \neg, 0, 1 \big)\). Ta có bảng mô tả các tính chất sau:

STT	Tên tính chất	Thể hiện
1	Tính giao hoán	\(\forall x, y, z \in A \text{. Ta có} \begin{cases} x \wedge y = y \wedge x \\ x \vee y = y \vee x \end{cases}\)
2	Tính kết hợp	\(\forall x, y, z \in A \text{. Ta có} \begin{cases} (x \wedge y ) \wedge z = x \wedge (y \wedge z ) \\ ( x \vee y ) \vee z = x \vee (y \vee z ) \end{cases}\)
3	Tính phân phối	\(\forall x, y, z \in A \text{. Ta có} \begin{cases} x \wedge ( y \vee z )= (x \wedge y ) \vee (x \wedge z ) \\ x \vee ( y \wedge z )= (x \vee y ) \wedge (x \vee z )\end{cases}\)
4	Tính hấp thụ	\(\forall x, y\in A \text{. Ta có} \begin{cases}x \vee (x \wedge y ) = x\\ x \wedge(x \vee y ) = x\end{cases}\)
5	Tính trung hòa	\(\forall x\in A \text{. Ta có} \begin{cases} x \vee 0 = 0 \vee x = x \\ x \wedge 1 = 1 \wedge x = x\end{cases}\)
6	Tính bù	\(\forall x\in A \text{. Ta có} \begin{cases} x \wedge \neg x = 0 \\ x \vee \neg x = 1 \end{cases}\)

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\).

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à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\)

Bìa Karnaugh (bìa Kar)

Một vài thông tin

Thông tin về bìa Kar

Tham khảo thêm

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

\[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ố

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:

Giải thích cho cách khoanh

Đơn thức đầu tiên: \(xz \neg t\) ta thấy chỉ có từ đơn \(y\) không xuất hiện, nghĩa là \(y\) đã bị đổi trạng thái từ 0 qua 1 hoặc từ 1 qua 0. Mà nằm ở thể khoẳng định (hay còn gọi là ở trạng thái cao - nếu xét về mặt các kí số) thì chắc chắn nằm ở trạng thái 1 (hay còn gọi là nhận chân trị 1) và \(\neg t\) là phủ định thì chắc chắn nằm ở trạng thái 0. Từ đây ta có thể kết luận: \(xz \neg t = xyz \neg t + x \neg y z \neg t\) hay nói cách khác \(xz \neg t\) sẽ nhận 2 ô ở 2 trạng thái là \(1110\) và \(1010\) như trên. Lý giải tương tự với các từ đơn còn lại.

Ngoài ra: Ta chỉ cần tách hình bên trên thành những tế bào gồm 1 ô thì đấy chính xác là dạng nối rời chính tắc cần tìm. Hiển như dạng nối rời chính tắc này trùng với dạng nối rời chính tắc ở 2 cách trên vì bản chất 3 cách này như nhau.

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

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.\)

❓	Cách làm phía trên có khó hiểu quá không? Làm thế nào để khoanh được như trên?

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

Đị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ì:
    • 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)\)
    • 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.\)