Tên bài giảng :
Chương 1 LÝ THUYẾT CƠ SỞ VỀ
LOGIC HAI TRẠNG THÁI
1
1.4 Phương pháp tối thiểu hóa các hàm logic
Thời gian : 1 tiết ( 45 phút )
2
CÁC PHƯƠNG PHÁP BIỂU DIỄN HÀM LOGIC
Biểu diễn hàm bằng bảng chân lý
Biểu diễn hàm bằng bảng Karnaugh
Biểu diễn hàm bằng biểu thức đại số
Nhắc lại :
Biểu diễn hàm bằng mạch logic
Kiến thức trong bài học trước :
CÂU HỎI KIỂM TRA BÀI CŨ
Hãy trình bày phương pháp biểu diễn hàm logic bằng bảng Karnaugh và viết biểu thức đại số của hàm, cho ví dụ minh họa ?
Trả lời
* Phương pháp biểu diễn hàm bằng bảng Karnaugh như sau :
Bước 1 : Lập bảng Karnaugh gồm 2n ô, n là số biến của hàm.
Bước 2 : Ghi giá trị tổ hợp biến ở đầu hàng và cột theo mã Gray
Bước 3 : Ghi giá trị của hàm vào các ô tương ứng với tổ hợp biến
* Viết biểu thức đại số của hàm có hai dạng :
- Dạng tổng chuẩn đầy đủ
- Dạng tích chuẩn đầy đủ
3
Ví dụ: Lập bảng Karnaugh và viết biểu thức đại số cho hàm logic 3 biến
4
A
BC
Dạng 2 hàng, 4 cột
0
1
00
01
11
10
0
1
1
x
1
0
x
0
Biểu thức đại số hàm :
Ví dụ 2 . Lập bảng Karnaugh và viết biểu thức của hàm :
5
1
1
1
1
1
1
x
x
x
Dạng 4 hàng, 4 cột
AB
CD
00
01
11
10
00
01
11
10
1
1
1
1
1
1
x
x
x
Nhận xét :
Biểu diễn hàm dạng đầy đủ có các ưu nhược điểm sau :
6
* Ưu điểm:
- Rõ ràng, trực quan: khi biết giá trị của tổ hợp biến thì xác định ngay được giá trị của hàm.
- Thuận tiện trong việc thiết kế một số mạch logic nhỏ, ít biến.
* Nhược điểm:
Cồng kềnh nếu khi số biến lớn, nhiều quan hệ logic.
Không thể dùng trong việc biến đổi các công thức, tốn kém chi phí, giảm tin cậy khi thiết kế mạch điều khiển.
PHƯƠNG PHÁP TỐI THIỂU HÓA HÀM LOGIC
I. Khái quát chung
Một hàm logic được gọi là tối thiểu hoá nếu như nó có số lượng số hạng ít nhất và số lượng biến ít nhất.
Mục đích của việc tối thiểu hoá: 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 logic có một mạch thực hiện tương ứng với nó. Biểu thức logic càng đơn giản thì mạch thực hiện càng đơn giản.
7
Ví dụ : Xét hàm logic 3 biến :
8
Áp dụng tính chất :
Nhận xét : Sau khi biến đổi, biểu thức của hàm logic đã được rút gọn đi nhiều, rất thuận lợi cho tính toán và thực hiện hàm.
9
LỢI ÍCH CỦA TỐI THIỂU HÓA HÀM LOGIC
Thuận lợi trong biến đổi, tính toán thiết kế
Thuận lợi cho việc lắp đặt, bảo dướng, giảm chi phí
Tăng độ tin cậy, giảm thiểu sai hỏng trong ứng dụng
Các phương pháp tối thiểu hàm logic
Phương pháp biến đổi đại số
Phương pháp bảng Karnaugh
Phương pháp Quine – Mc. Cluskey
. . .
10
Trong tiết học này, chúng ta nghiên cứu phương pháp biến đổi đại số và phương pháp dùng bảng Karnaugh
I. Phương pháp đại số
11
1. Nội dung phương pháp
Áp dụng các định lý của đại số logic để đơn giản hàm logic sao cho hàm cuối cùng là tối giản, thực hiện hàm cần ít phần tử logic nhất.
2. Một số phép biến đổi thường sử dụng
- Nhóm các số hạng :
Ví dụ :
- Thêm số hạng đã có vào biểu thức :
12
Ví dụ :
- Biến đổi loại bỏ số hạng thừa
Ví dụ :
Nhận xét : Đặc điểm của phương pháp biến đổi đại số
Khó tìm ra quy luật tối ưu để tìm ra được một biểu thức logic tối giản một cách nhanh nhất vì trong thực tế các biểu thức logic rất đa dạng, từ một hàm logic cũng có thể biểu diễn theo nhiều cách khác nhau.
Tuy nhiên, nếu nắm chắc các định luật của đại số Boole và có kinh nghiệm chúng ta có thể thu được kết qủa tốt.
13
II. Phương pháp tối thiểu hóa hàm logic bằng bảng Karnaugh
Bước 1 : Vẽ bảng Karnaugh của hàm đã cho.
Bước 2: Nhóm các ô liền kề có giá trị của hàm cùng bằng 1 theo nguyên tắc :
Số lượng các ô trong nhóm là lớn nhất có thể được.
Số lượng ô trong nhóm phải là lũy thừa của 2.
Hình dạng của nhóm phải là hình chữ nhật hoặc hình vuông.
14
II. Phương pháp tối thiểu hóa hàm logic bằng bảng Karnaugh
Bước 3 : Viết số hạng tối thiểu cho các nhóm :
Nhóm có 2n ô => loại bỏ được n biến, biến nào giá trị thay đổi trong nhóm sẽ bị loại.
Các nhóm có thể trùng nhau một vài phần tử nhưng không được trùng hoàn toàn và phải nhóm hết các ô bằng 1.
Bước 4: Viết hàm tối thiểu bằng tổng các số hạng tối thiểu của các nhóm trên.
15
Các ví dụ :
AB
CD
00
01
11
10
00
01
11
10
1
1
1
1
1
1
Sai
Sai
Minh họa : Ghép 2 ô kề nhau :
Dùng bảng Karnaugh
17
AB
CD
00
01
11
10
00
01
11
10
1
1
1
1
1
1
1
1
C.D
Ghép 4 ô rút gọn được 2 biến
Dùng bảng Karnaugh
18
AB
CD
00
01
11
10
00
01
11
10
1
1
1
1
1
1
1
1
Ghép 4 ô rút gọn được 2 biến
Dùng bảng Karnaugh
AB
CD
00
01
11
10
00
01
11
10
1
1
1
1
1
1
1
C
1
1
1
1
1
1
1
Ghép 8 ô, rút gọn được 3 biến.
Ví dụ 1. Tối thiểu hàm logic sau bằng bảng Karnaugh ?
Lập bảng Karnaugh :
Y =
C
+
AB
+
Ví dụ 2. Tối thiểu hàm logic sau bằng bảng Karnaugh ?
21
Y =
ABD
+
+
+
Ví dụ 3 . Tối thiểu hàm logic sau bằng bảng Karnaugh ?
Y(A, B, C, D) = (1, 2, 4, 7, 10, 12, 14), N = 9, 15
22
BCD
Y =
+
+
ABC
+
+
Phiếu bài tập trên lớp : Họ tên SV : ----------------------------------------------------------
Bài tập: Tối thiểu hàm logic sau bảng phương pháp Karnaugh ?
Y(A, B, C, D) = (0,2,3,5,6,11,12), N = 8,10,14,15
23
Viết kết quả :
F(A,B,C,D) =
------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------
Lời giải :
Y(A, B, C, D) = (0,2,3,5,6,11,12), N = 8,10,14,15
24
Y =
+
+
+
+
+
AC
Giao bài tập về nhà
1. Tối thiểu hóa các hàm sau bằng phương pháp đại số:
2. Tối thiểu hóa các hàm logic sau bằng phương pháp bảng Karnaugh
a. Y(A, B, C, D) = (0,1,2,6,9,14,15), N = 3,4,8,10,11,13
b. Y(A, B, C, D) = M4 . M8 . M13 , N = M0, M3, M5, M7, M11, M14
c. Y(A, B, C, D) = (1, 2, 4, 7, 10, 12, 14), N = 9, 15
25
Xin cảm ơn các em đã cùng thầy xây dựng
bài học này !
26
Tổng kết :
Giảng viên nhắc sinh viên ôn lại lý thuyết
Làm bài tập về nhà, thầy sẽ chữa vào buổi tiếp theo
Chuẩn bị nội dung bài học sắp tới.
nguon VI OLET
