Lại Văn Song: Bài 2. Đại số logic

2.1. Các khái niệm

- Đại số logic hay còn được gọi là đại số Boole (Nhà toán học người Anh George Boole đưa ra vào năm 1847). Nó là công cụ toán học hữu hiệu dùng cho hệ thống đếm nhị phân.

- Phép toán logic: Có 3 loại phép toán logic cơ bản:

Phép Và - "AND"

Phép Hoặc - "OR"

Phép Đảo - "NOT"

- Trạng thái logic: Trạng thái của một thực thể. Xét về mặt logic thì một thực thể chỉ tồn tại ở một trong hai trạng thái đối lập.

Ví dụ: Sáng – tối, tắt – bật, đóng – mở, cao – thấp, trên – dưới, ….

- Biến logic: là 1 đại lượng có thể biểu diễn bằng 1 ký hiệu nào đó, về mặt giá trị chỉ lấy giá trị 0 hoặc 1. - Phép toán logic: Có 3 loại phép toán logic cơ bản:

Phép Và - "AND"

Phép Hoặc - "OR"

Phép Đảo - "NOT"

- Hàm logic: là biểu diễn của nhóm các biến logic, liên hệ với nhau thông qua các phép toán logic, về mặt giá trị cũng lấy giá trị 0 hoặc 1.

- Tổ hợp biến: Do mỗi biến logic có thể nhận 2 giá trị 0 hoặc 1 nên với n biến logic ta sẽ có N = 2ⁿ tổ hợp biến khác nhau.

Ví dụ: 1 biến có 1 tổ hợp, 2 biến có 4 tổ hợp, 3 biến có 8 tổ hợp, …..

- Mức logic: Là mức điện áp ( dòng điện) để thể hiện 2 miền giá trị khác nhau, tạo thành 2 mức logic khác nhau. Tùy vào nhà sản xuất linh kiện điện tử mà mức này cũng có giá trị không giống nhau.

Ví dụ: Với họ logic TTL thì áp vào mức 0 tương ứng với điện áp 0 – 0,8V

mức 1 tương ứng với điện áp 2 – 5V

áp ra mức 0 tương ứng với điện áp 0 – 0,5V

mức 1 tương ứng với điện áp 2,4 – 5V

Giá trị này thay đổi phụ thuộc vào từng linh kiện cụ thể.

2.2. Đại số logic

2.2.1. Các hệ thức cơ bản của đại số logic

-   Các hệ thức dựa trên cơ sở từ 3 phép toán cơ bản của đại số logic:
                                                                       AND - và.
                                                                       OR – hoặc.
                                                           NOT – đảo.

Ví dụ:

AND (nhân): 0 x 0 = 0 OR (cộng): 0 + 0 = 0 NOT (đảo): 0' = 1

0 x 1 = 0 0 + 1 = 1 1' = 0

1 x 0 = 0 1 + 0 = 1

1 x 1 = 1 1 + 1 = 1

Đại số logic cũng có các tính chất gần giống với đại số thông thường:

- Tính chất giao hoán.

- Tính chất kết hợp.

- Tính chất phân phối.

Bảng các hệ thức cơ bản của Đại số Logic

1. A + 0 = A	2. A . 1 = A
3. A + 1 = 1	4. A . 0 = 0
5. A + A = A	6. A . A = A
7. A + A’ = 1	8. A . A’ = 0
9. A + B = B + A	10. A . B = B . A
11. A + AB = A	12. A.(A + B) = A
13. AB + AB’ = A	14. (A + B).(A + B’) = A
15. A + B + C = (A + B) + C	16. A.B.C = A.(B.C) = (A.B).C
17. (A + B)’ = A’ . B’	18. (A.B)’ = A’ + B’

Ký hiệu: A’ = A ( phủ định)

- Hệ thức 17 và 18 chính là nội dung Định lý Demorgan: "Tổng của một phủ định bằng tích các phủ định. Tích của phủ định bằng tổng các phủ định".

2.2.2. Các cổng logic cơ bản

2.3. Các phương pháp biểu diễn hàm logic

- Có nhiều phương pháp biểu diễn hàm logic tùy thuộc vào đặc điểm của từng hàm logic cụ thể. Có 4 phương pháp thông dụng để biểu diễn hàm logic đó là:

- Bảng chân lý.

- Biểu thức logic.

- Bảng Karnaugh.

- Sơ đồ cổng logic.

2.3.1. Phương pháp lập bảng chân lý

- Là bảng mô tả quan hệ giữa các giá trị của hàm số ứng với mọi giá trị của biến số. Trong đó có các cột ghi giá trị của biến đầu vào, và 1cột ghi giá trị của hàm ra tương ứng với từng tổ hợp biến.

- Người ta thường ký hiệu các biến: (x,y,z…) hoặc ( A,B,C…).

các hàm: Y, F

- Trong hệ nhị phân mỗi biến chỉ nhận một trong hai giá trị. Do đó giả sử có n biến đầu vào thì sẽ có 2ⁿtổ hợp biến khác nhau và tương ứng sẽ có 2ⁿ giá trị hàm ra.

Ví dụ 2.1: Lập bảng chân lý (trạng thái) của hàm logic sau: Y = A’.B

- Nhận thấy hàm có 2 biến A, B nên có 4 tổ hợp biến à Bảng chân lý sẽ có kích thước:

Gồm 3 cột:2 cột cho biến và 1 cột cho hàm

Gồm 5 hàng: 4 hàng cho các tổ hợp biến và 1 hàng để ghi tên biến, tên hàm.

Ưu điểm: Biểu diễn một cách trực quan.

Nhược điểm: Khi có nhiều biến thì sẽ rất phức tạp.

2.3.2. Phương pháp biểu thức hàm số

- Phương pháp biểu thức hàm số hay còn gọi là phương trình logic: Dùng các phép toán AND, OR, NOT biểu diễn mối quan hệ logic giữa các biến trong hàm.

- Là phương pháp thích hợp cho mọi trường hợp kể cả các quan hệ logic phức tạp, hàm có nhiều biến.

- Đơn giản hơn các phương pháp bảng, tiện cho việc rút gọn bằng phương pháp đại số.

- Có 2 phương pháp (2 chuẩn tắc) xây dựng hàm bằng biểu thức đại số:

Chuẩn tắc tuyển: Tổng của các tích (các minterm)

Chuẩn tắc hội: Tích của các tổng (các maxterm)

Phương pháp Chuẩn tắc tuyển: Tổng của các tích tại đó hàm có giá trị bằng 1.

- Là tích các biến mà tại tổ hợp đó hàm có giá trị bằng 1.
- Biểu thức được xác định bằng tổng các tích của các tổ hợp biến mà tại đó hàm có giá trị bằng 1.

- Thông thường với những yêu cầu tìm hàm trong trường hợp này sẽ cho trước bảng trạng thái, hoặc cho trước giá trị cụ thể của các tổ hợp biến.

Ví dụ 2.2: Tìm biểu thức đại số của hàm logic cho trong bảng chân lý sau

Nhận thấy: Hàm có giá trị bằng 1 tại các tổ hợp biến thứ nhất và thứ 3.

==> Biểu thức của hàm được xác định: F = ∑(fm₁, fm₃) = B’.A’ + B.A’

Ví dụ 2.3: Cho hàm 3 biến F = f(A,B,C). Hãy xác định biểu thức của hàm tại f(m₀, m₃, m₅, m₆) ?

- Nhận thấy: Hàm có giá trị bằng 1 tại các tổ hợp biến thứ nhất, thứ 4, thứ 6 và thứ 7.

- Ta cần xây dựng bảng trạng thái của hàm 3 biến để xác định chính xác các tổ hợp biến đã cho.

- Hàm 3 biến sẽ có 8 tổ hợp biến nên bảng trạng thái sẽ có kích thước:

Gồm 4 cột: 3 cột cho biến và 1 cột cho hàm.

Gồm 9 hàng: 8 hàng cho các tổ hợp biến và 1 hàng để ghi tên biến và tên hàm.

2.3.3. Phương pháp dùng bảng Karnaugh

- Giá trị các tổ hợp biến được xác định từ bảng chân lý, từ chuẩn tắc tuyển, chuẩn tắc hội hoặc xác định từ việc thay giá trị của từng biến vào biểu thức.

- Giá trị các biến được sắp xếp theo mã vòng. Các ô kế cận chỉ khác nhau 1 bít, Các ô đầu dòng, cuối dòng, đầu cột cuối cột chỉ khác nhau 1 bít.

Ví dụ 2.4: Lập bảng karnaugh của hàm có bảng chân lý sau

- Đây là hàm 4 biến, có 16 tổ hợp biến. Hàm có giá trị bằng 1 tại các tổ hợp biến D’CB’A, DC’BA, DCBA.

- Bảng Karnaugh cho hàm sẽ có 16 ô vuông (từ ô m₀ đến m₁₅)

2.3.4. Phương pháp dùng sơ đồ cổng logic

- Dùng các ký hiệu của các cổng logic để thay cho các phép toán. Có 3 cổng logic cơ bản là AND, OR, NOT và các cổng khác được phát triển dựa trên 3 cổng cơ bản này.

Ví dụ 2.5: Vẽ sơ đồ mạch biểu diễn hàm logic được cho dưới dạng bảng như sau: Q = (A + B)’ + BC.

- Nhận thấy: (A + B)’ tương ứng với cổng NOR có 2 đầu vào là A, B. Gọi đầu ra của cổng này là D.

- BC tương ứng với cổng AND có 2 đầu vào là B, C. Gọi đầu ra của cổng này là E.

và Q = (A + B)’ + BC tương ứng với đầu ra của cổng OR có 2 đầu vào là D, E.

2.4. Các phương pháp tối thiểu hóa hàm logic

- Mỗi hàm logic có thể được biểu diễn bằng các biểu thức logic khác nhau, mỗi biểu thức này sẽ tương ứng với một mạch điện thực hiện chức năng của hàm. Biểu thức đơn giản thì hàm sẽ đơn giản.

- Một biểu thức gọi là tối giản nếu nó có số lượng số hạng ít nhất và số biến ít nhất.

- Có 2 phương pháp tối thiểu hóa thông dụng: Tối thiểu bằng biểu thức đại số và tối thiểu bằng dán bìa karnaugh.

2.4.1. Phương pháp biểu thức đại số

- Sử dụng các tính chất của đại số Boole: giao hoán, kết hợp, phân phối, them bớt, định lý demorgan, ….

- Áp dụng sẵn 18 hệ thức cơ bản của đại số logic.

1. A + 0 = A	2. A . 1 = A
3. A + 1 = 1	4. A . 0 = 0
5. A + A = A	6. A . A = A
7. A + A’ = 1	8. A . A’ = 0
9. A + B = B + A	10. A . B = B . A
11. A + AB = A	12. A.(A + B) = A
13. AB + AB’ = A	14. (A + B).(A + B’) = A
15. A + B + C = (A + B) + C	16. A.B.C = A.(B.C) = (A.B).C
17. (A + B)’ = A’ . B’	18. (A.B)’ = A’ + B’

Ví dụ 2.7. Tối giản biểu thức sau: F(A,B,) = (A + B)(A + B’)

Ta có: F(A,B) = (A + B)(A + B’)

= AA + AB’ + BA + BB’

= A + A(B + B’)

= A + A

= A

Ví dụ 2.8. Tối giản biểu thức sau: F(A,B) = A + A’B

Ta có: F(A,B) = A + A’B

= A(1 + B) + A’B

= A + AB + A’B

= A + (AB + A’B)

= A + B(A + A’)

= A + B

2.4.2. Phương pháp bìa Karnaugh

- Biểu diễn biểu thức dưới dạng bảng karnaugh.

- Tối giản bằng cách nhóm các ô có giá trị hàm bằng 1.

Quy tắc nhóm:

- Nhóm các ô liền kề mà hàm có giá trị bằng 1 lại với nhau, sao cho số lượng ô trong nhóm là lớn nhất, số ô là lũy thừa của 2 (1, 2, 4, 8, 16, …), có hình dạng là hình vuông hoặc hình chữ nhật.

- Trong 1 bảng karnaugh có thể có nhiều nhóm. Các nhóm có thể trùng nhau 1 vài phần tử nhưng không được trùng hoàn toàn.

- Khi đó trong 1 nhóm biến nào có giá trị thay đổi ( chẳng hạn A và A’ là thay đổi) thì sẽ bị loại bỏ, viết ra các biến còn lại (biến không đổi).

Ví dụ 2.10. Tối giản biểu thức sau:

Ví dụ 2.11. Tối giản biểu thức sau: Y = ∑ABCD(3,4,7,8,910,11,12,15)

Nhận thấy: Hàm 4 biến nên bảng Kanaugh sẽ có dạng hình vuông 16 ô.

Điền các giá trị mà tại tổ hợp biến đó hàm có giá trị bằng 1 vào:

Nhóm theo quy tắc: Nhóm các ô mà tại đó hàm có giá trị bằng 1 lại với nhau sao cho số ô là lớn nhất, số ô là lũy thừa của 2, vòng nhóm có dạng là hình vuông hoặc hình chữ nhật.

Vòng 1(4, 12): BA không đổi (B’A’) , C không đổi (C), D thay đổi --> CB’A’

Vòng 2 (3, 7, 11, 15): BA không đổi, DC thay đổi ==> BA

Vòng 3 (8, 9, 10, 11): DC không đổi, BA thay đổi ==> DC’

==> Kết quả: Y = CB’A’ + BA + DC’

(Nội dung đang được cập nhập tiếp tục)

Lại Văn Song

Vietnam National University of Agriculture

Bài 2. Đại số logic

Phổ biến

Thẻ

Lưu trữ