Trình tạo biểu thức từ bảng chân trị
Bấm cột kết quả thành hình bạn cần, công cụ sẽ đọc ra công thức: DNF chuẩn tắc (tổng các tích), CNF chuẩn tắc (tích các tổng) và dạng tương đương ngắn nhất. Mọi thứ chạy trong trình duyệt, và bảng bạn dựng nằm ngay trong đường liên kết.
| p | q | Kết quả |
|---|---|---|
| ⊥ | ⊥ | |
| ⊤ | ⊥ | |
| ⊥ | ⊤ | |
| ⊤ | ⊤ |
Bấm vào các giá trị kết quả để chuyển giữa đúng (⊤) và sai (⊥)
Cách chuyển bảng chân trị thành biểu thức Boole
Mọi bảng chân trị đều là bảng chân trị của một công thức nào đó, và hai trong số các công thức ấy đọc được ngay từ bảng - không cần biến đổi đại số, cũng không cần đoán:
- Viết đủ 2ⁿ dòng cho n biến của bạn và đánh dấu những dòng có kết quả ⊤.
- Với mỗi dòng ⊤, viết một minterm: tất cả các biến nối bằng VÀ, phủ định ở những chỗ dòng làm chúng sai. Nối các minterm bằng HOẶC là được DNF.
- Với mỗi dòng ⊥, viết một maxterm: tất cả các biến nối bằng HOẶC, phủ định ở những chỗ dòng làm chúng đúng. Nối các maxterm bằng VÀ là được CNF.
- Cả hai công thức đều có đúng bảng bạn khởi đầu, nên công thức nào cũng là đáp án đúng. Muốn ngắn nhất thì rút gọn sau.
Minterm
Một phép hội của tất cả các biến, mỗi biến có hoặc không có phủ định, đúng ở đúng một dòng của bảng. DNF là phép tuyển các minterm của những dòng có kết quả ⊤, vì thế nó có một số hạng cho mỗi dòng ⊤.
Maxterm
Một phép tuyển của tất cả các biến, mỗi biến có hoặc không có phủ định, sai ở đúng một dòng của bảng. CNF là phép hội các maxterm của những dòng có kết quả ⊥, vì thế nó có một thừa số cho mỗi dòng ⊥.
Ví dụ giải mẫu: hoặc loại trừ
Bảng ở trên chính là bảng công cụ mở sẵn: p và q, đúng ở đúng hai dòng có đầu vào khác nhau.
- Hai dòng là ⊤, nên DNF có hai minterm: (p ∧ ¬q) ∨ (¬p ∧ q)
- Hai dòng còn lại là ⊥, nên CNF có hai maxterm: (p ∨ q) ∧ (¬p ∨ ¬q)
Không dạng nào rút ngắn được - phép hoặc loại trừ thật sự cần cả hai số hạng - và điều này đáng thấy một lần: dạng chuẩn tắc không phải lúc nào cũng là đường vòng. Phải tới một bảng như «nhiều nhất một trong p, q, r» thì dạng tối giản mới bỏ xa.
Hiểu về tổng hợp hàm Boole
Dạng chuẩn tuyển (DNF)
DNF viết một công thức thành phép HOẶC của các phép VÀ (tổng các tích). Với mỗi dòng có kết quả đúng, ta lập một minterm nối tất cả các biến bằng VÀ, phủ định những biến nhận giá trị sai. Các minterm sau đó được nối bằng HOẶC để thành biểu thức đầy đủ.
Dạng chuẩn hội (CNF)
CNF viết một công thức thành phép VÀ của các phép HOẶC (tích các tổng). Với mỗi dòng có kết quả sai, ta lập một maxterm nối tất cả các biến bằng HOẶC, phủ định những biến nhận giá trị đúng. Các maxterm sau đó được nối bằng VÀ để thành biểu thức đầy đủ.
So sánh DNF và CNF
| Khía cạnh | Dạng chuẩn tuyển (tổng các tích) | Dạng chuẩn hội (tích các tổng) |
|---|---|---|
| Dựng từ | Các dòng có kết quả ⊤, mỗi dòng một minterm | Các dòng có kết quả ⊥, mỗi dòng một maxterm |
| Hình thức | Phép tuyển của các phép hội: HOẶC của các VÀ | Phép hội của các phép tuyển: VÀ của các HOẶC |
| Nên dùng khi | Bạn muốn liệt kê những trường hợp làm công thức đúng, hoặc dựng một mạch VÀ-HOẶC | Bạn muốn các ràng buộc phải cùng thỏa mãn, hoặc dạng mệnh đề mà bộ giải SAT cần |
Bảng lớn tới đâu?
Hàm của n biến có 2ⁿ dòng, nên cứ thêm một biến là bảng gấp đôi: 4 dòng với hai biến, 8 với ba, 16 với bốn và 32 với năm - công cụ dừng ở đó. DNF lấy một số hạng cho mỗi dòng ⊤ còn CNF lấy một cho mỗi dòng ⊥, nên gộp lại chúng phủ hết mọi dòng đúng một lần, và luôn có một trong hai là điểm khởi đầu ngắn hơn.
Ứng dụng của việc tổng hợp từ bảng chân trị
Chuyển bảng chân trị thành biểu thức logic là kỹ thuật nền tảng trong khoa học máy tính và điện tử số. Công cụ này giúp:
- Thiết kế mạch số - rút ra phương trình Boole cho các cổng logic từ hành vi vào - ra mong muốn
- Phát triển phần mềm - sinh logic điều kiện từ bảng đặc tả
- Học tập - học và luyện đại số Boole cùng logic mệnh đề
- Tối ưu logic - so sánh DNF với CNF để tìm biểu thức tương đương gọn hơn
Câu hỏi thường gặp
Giải đáp những thắc mắc phổ biến về cách dùng Máy tính Logic
Công cụ từ bảng chân trị sang biểu thức làm gì?
Nó cho máy tính chạy ngược. Bạn đặt cột kết quả của một bảng chân trị bằng cách bấm vào từng dòng, và công cụ tạo ra một công thức có đúng bảng chân trị ấy, ở dạng chuẩn tuyển (một phép HOẶC của các phép VÀ) hoặc dạng chuẩn hội (một phép VÀ của các phép HOẶC).
Dạng chuẩn tuyển và dạng chuẩn hội khác nhau ra sao?
Dạng chuẩn tuyển là tổng của các tích: mỗi dòng có kết quả đúng cho một hội, rồi nối tất cả bằng HOẶC. Dạng chuẩn hội là tích của các tổng: mỗi dòng có kết quả sai cho một tuyển, rồi nối tất cả bằng VÀ. Cả hai mô tả cùng một hàm, nên nên chọn dạng nào ngắn hơn với bảng của bạn — cột phần lớn là sai sẽ cho dạng chuẩn tuyển ngắn, cột phần lớn là đúng sẽ cho dạng chuẩn hội ngắn.
Công cụ tổng hợp nhận được bao nhiêu biến?
Tối đa năm biến, tức một bảng 32 dòng. Mỗi biến thêm vào lại nhân đôi số dòng, và quá năm biến thì bảng không còn là thứ có thể đặt bằng tay nữa.
Vì sao biểu thức sinh ra lại dài đến vậy?
Dạng chuẩn được dựng theo từng dòng, mỗi dòng cần phủ thì có một số hạng đầy đủ các biến, nên độ dài của nó bám theo bảng chân trị chứ không theo ý tưởng đằng sau công thức. Nó đúng theo cách dựng, chứ không gọn. Muốn rút ngắn, hãy mở nó trong máy tính, nơi liệt kê các dạng tương đương, trong đó có một dạng chuẩn tuyển tối giản.
Tôi có thể lấy bản rút gọn của một công thức không?
Có. Nhập nó vào máy tính và xem các dạng tương đương bên dưới bảng chân trị. Ở đó có những dạng thu được bằng cách biến đổi theo các luật đại số, cùng với dạng chuẩn tuyển và dạng chuẩn hội đọc từ bảng chân trị, kèm một dạng chuẩn tuyển tối giản.