Biểu diễn và hiện thực các hàm luận lý

Chia sẻ: Lotus_123 Lotus_123 | Ngày: | Loại File: PDF | Số trang:57

Thêm vào BST

Báo xấu

78
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Hàm luận lý luôn trả về một trong 2 giá trị TRUE (đúng) hoặc FALSE (sai). Kết quả của hàm luận lý dùng làm đối số trong các hàm có sử dụng điều kiện như IF, SUMIF, COUNTIF,. Danh sách minterm (minterm list) Liệt kê các giá trị mà hàm bằng 1 f(x, y, z) = ∑(1, 3, 4) Biểu thức canonical s-o-p từ danh sách minterm f(x, y, z) = m1 + m3 + m4 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 3 .Danh sách maxterm và p-o-s Danh sách maxterm (maxterm list) Liệt kê các...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Biểu diễn và hiện thực các hàm luận lý

Biểu diễn và hiện thực các hàm luận lý
Xét ví dụ f(x,y,z) = (x’ + y’z’)(z + xy’) f(x,y,z) = x’z + xy’z’ f(x,y,z) = x’yz + x’y’z + xy’z’ Code xyz f Minterm Maxterm 0 000 0 x’y’z’ x+y+z 1 001 1 x’y’z x + y + z’ 2 010 0 x’yz’ x + y’ + z 3 011 1 x’yz x + y’ + z’ 4 100 1 xy’z’ x’ + y + z 5 101 0 xy’z x’ + y + z’ 6 110 0 xyz’ x’ + y’ + z 7 111 0 xyz x’ + y’ + z’ 2 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Danh sách minterm và s-o-p Danh sách minterm (minterm list) Liệt kê các giá trị mà hàm bằng 1 f(x, y, z) = ∑(1, 3, 4) Biểu thức canonical s-o-p từ danh sách minterm f(x, y, z) = m1 + m3 + m4 3 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Danh sách maxterm và p-o-s Danh sách maxterm (maxterm list) Liệt kê các giá trị mà hàm bằng 0 f(x, y, z) = ∏(0, 2, 5, 6, 7) Biểu thức canonical p-o-s từ danh sách maxterm f(x, y, z) = M0M2M5M6M7 4 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Kề luận lý Kề luận lý (logically adjacent): hai tổ hợp các biến gọi là kề luận lý nếu chúng chỉ khác nhau một vị trí bit 1011 và 1001 ab’cd và ab’c’d abcd a’b’cd ? Có phương pháp nào biểu diễn việc kề luận lý một cách trực quan? 5 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Bìa luận lý A 0 1 0 00 01 B 10 1 11 A 0 1 000 001 00 BA 00 01 11 10 010 011 01 CB 000 001 011 010 110 111 0 11 C 100 101 111 110 100 101 1 10 6 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Bìa luận lý A 0 1 0 00 01 B 10 1 11 A 0 1 000 001 00 BA 00 01 11 10 010 011 01 CB 000 001 011 010 110 111 0 11 C 100 101 111 110 100 101 1 10 6 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Bìa luận lý (tt) BA 00 01 11 10 00 0000 0001 0011 0010 01 0100 0101 0111 0110 DC 11 1100 1101 1111 1110 10 1000 1001 1011 1010 7 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Bìa luận lý (tt) E=0 E=1 BA BA 00 01 11 10 10 11 01 00 00 0000 0001 0011 0010 0010 0011 0001 0000 01 0100 0101 0111 0110 0110 0111 0101 0100 DC 11 1100 1101 1111 1110 1110 1111 1101 1100 10 1000 1001 1011 1010 1010 1011 1001 1000 8 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Bìa luận lý và hàm chuyển mạch BA 00 01 11 10 00 0 1 3 2 AB 01 4 5 7 6 DC 00 01 11 10 11 12 13 15 14 00 0 4 12 8 10 8 9 11 10 01 1 5 13 9 CD 11 3 7 15 11 10 2 6 14 10 9 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Bìa luận lý và hàm chuyển mạch BA 00 01 11 10 00 0 1 3 2 AB 01 4 5 7 6 DC 00 01 11 10 11 12 13 15 14 00 0 4 12 8 10 8 9 11 10 01 1 5 13 9 CD 11 3 7 15 11 10 2 6 14 10 9 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Bìa luận lý và danh sách minterm, maxterm f(A,B,C,D) = ∑(0,2,4,5,8,9,10,14) f(A,B,C,D) = ∏(0,2,4,5,8,9,10,14) = m0 + m2 + m4 + m5 + m8 = M0 . M2 . M4 . M5 . M8 . + m9 + m10 + m14 M9 . M10 . M14 BA BA 00 01 11 10 00 01 11 10 10 01 03 1 2 00 00 11 1 3 0 2 00 14 15 07 0 6 DC 01 04 05 1 7 1 6 01 DC 012 013 015 1 14 11 112 113 1 15 0 14 11 18 19 011 1 10 10 0 8 0 9 1 11 0 10 10 10 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
K-cube K-cube: tập 2k các ô 1, trong đó mỗi ô đều kề với 2k-1 ô còn lại 00 01 11 10 00 01 11 10 00 00 0 1 3 2 0 1 3 2 14 16 14 16 01 01 5 7 5 7 112 113 115 1 14 112 113 115 1 14 11 11 10 10 8 9 11 10 8 9 11 10 11 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Các dạng 1-cube 00 01 11 10 00 01 11 10 00 00 0 1 3 2 0 1 3 2 01 01 4 5 7 6 4 5 7 6 11 11 12 13 15 14 12 13 15 14 10 10 8 9 11 10 8 9 11 10 00 01 11 10 00 01 11 10 00 00 0 1 3 2 0 1 3 2 01 01 4 5 7 6 4 5 7 6 11 11 12 13 15 14 12 13 15 14 10 10 8 9 11 10 8 9 11 10 12 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Các dạng 2-cube 00 01 11 10 00 01 11 10 00 01 11 10 00 00 00 0 1 3 2 0 1 3 2 0 1 3 2 01 01 01 4 5 7 6 4 5 7 6 4 5 7 6 11 11 11 12 13 15 14 12 13 15 14 12 13 15 14 10 10 10 8 9 11 10 8 9 11 10 8 9 11 10 00 01 11 10 00 01 11 10 00 01 11 10 00 00 00 0 1 3 2 0 1 3 2 0 1 3 2 01 01 01 4 5 7 6 4 5 7 6 4 5 7 6 11 11 11 12 13 15 14 12 13 15 14 12 13 15 14 10 10 10 8 9 11 10 8 9 11 10 8 9 11 10 13 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Ví dụ Cho f = ∑(2,4,6,9,10,11,12,13,15) Xác định tất cả các 1-cube Xác định tất cả các 2-cube Các k-cube nào bị bao phủ (cover) bởi các cube khác? 00 01 11 10 12 00 0 1 3 14 16 01 5 7 112 113 115 11 14 19 111 1 10 10 8 14 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Tối giản hàm chuyển mạch Biểu thức tối giản (irreducible): là biểu thức trong đó bất kì term hay literal trong term không thể xóa mà không thay đổi giá trị luận lý của biểu thức x’y + yx ? xyz + x’yz + z ? Biểu thức tối thiểu (minimal): là biểu thức có ít số term nhất trong tất cả các biểu thức tương đương Nếu nhiều biểu thức có cùng số term, biểu thức có số literal ít nhất là tối thiểu 15 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Tối giản hàm chuyển mạch (tt) Bao phủ (cover): hàm f1 bao phủ hàm f2 nếu bất kì khi nào f2=1 thì f1=1 f1 = xy’z + wyz’ + wx’y + xz’ f2 = wx’y + xz Implicant: nếu hàm f1 bao phủ một tích các literal thì tích này được gọi là implicant của hàm f1 Là biểu thức biểu diễn K-cube Prime implicant: là một implicant của hàm f thỏa tính chất nếu xóa bất kì literal nào thì tích mới không là implicant của hàm f Tối giản hàm chuyển mạch là chọn tập con nhỏ nhất các prime implicant bao phủ tất cả các minterm 16 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Tối giản bằng bìa luận lý (s-o-p) Chọn các ô 1 không kề với bất 00 01 11 10 kì ô 1 nào 12 00 0 1 3 14 16 01 5 7 112 113 115 11 14 19 111 1 10 10 8 17 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính
Tối giản bằng bìa luận lý (s-o-p) Chọn các ô 1 không kề với bất 00 01 11 10 kì ô 1 nào 12 00 0 1 3 14 16 01 Chọn các k-cube có chứa một 5 7 112 113 115 11 ô 1 mà chỉ kề với một ô 1 khác 14 19 111 1 10 10 8 18 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính