IT010_Chapter03_Boolean (1234567890).pdf

IT010_Chapter03_Boolean (1)

1. IT010 –TỔ CHỨC VÀ CẤU TRÚC MÁY TÍNH II
CHƯƠNG 3
ĐẠI SỐ BOOLEAN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
KHOA KỸ THUẬT MÁY TÍNH

2. IT010 –Tổ chức và Cấu trúc Máy tính
Nội dung
1.Đại số Boolean
2.Biểu diễn hàm Boolean
3.Tối ưu luận lý
4.Phương pháp Karnaugh
5.Câu hỏi và Bài tập
2

3. IT010 –Tổ chức và Cấu trúc Máy tính
1. Đại số Boolean (1/5) –Định nghĩa
•
3

4. IT010 –Tổ chức và Cấu trúc Máy tính
1. Đại số Boolean (2/5) –Định nghĩa
•
4

5. IT010 –Tổ chức và Cấu trúc Máy tính
1. Đại số Boolean (3/5) –Định nghĩa
•
5

6. IT010 –Tổ chức và Cấu trúc Máy tính
1. Đại số Boolean (4/5) –Hàm Boolean
•Kết hợp các biến, hằng số, toán tử, dấu ngoặc tạo thành một Biểu
thức Boolean.
Ví dụ: x +yz
•Kếthợptheothứtự:1tênhàm,1dấubằngvàcuốicùnglà1biểu
thứcBooleansẽchochúngtađượcmộtHàmBoolean(Hàm
BooleanDạngchuẩn)
Ví dụ: f(x, y, z)= x +yz
6

7. IT010 –Tổ chức và Cấu trúc Máy tính
Cổngluậnlý
•Cổngluậnlýlàthiếtbịđiệntửcóđặcđiểmsau:
Chứcnăng: Thựchiệnmộtphéptoánluậnlý
Cấutạo:Cóítnhất1 ngõvàovàcóduynhất1 ngõra
9/24/257 Copyrights 2017 CE-UIT. All Rights Reserved.

8. IT010 –Tổ chức và Cấu trúc Máy tính
1. Đại số Boolean (5/7) –Bảng chân trị
•Bảng chân trị(hay còn gọi là bảng tổ hợp) thể hiện mối quan hệ
giữa giá trị của một hàm Boolean và các biến của hàm đó
2nhàng (nlà số biến)
n+1 cột
8
xyzf
000
001
010
011
100
101
110
111
f(x, y, z)= x +yz
0
0
0
1
1
1
1
1
Liệt kê tất cả các tổ hợp có thể
Giá trị của hàm
tương ứng với mỗi
tổ hợp các biến

9. IT010 –Tổ chức và Cấu trúc Máy tính
3. Đại số Boolean (2/2) –Dạng chính tắc
•Dạng chính tắc là dạng biểu diễn hàm Boolean bằng tổng của các
minterm khiến hàm Boolean có giá trị 1 (1 -minterm) hoặc tích của
các maxterm khiến hàm Boolean có giá trị 0 (0 -maxterm)
9
BiếnMintermMaxterm
xyzBiểu thức
Ký
hiệu
Biểu thức
Ký
hiệu
000 m0x + y + zM0
001 m1 M1
010 m2 M2
011 m3 M3
100 m4 M4
101 m5 M5
110 m6 M6
111x y zm7 M7
xyzf
0000
0011
0100
0111
1001
1010
1101
1111

10. IT010 –Tổ chức và Cấu trúc Máy tính
Cổngluậnlý
•Cổngluậnlýlàthiếtbịđiệntửcóđặcđiểmsau:
Chứcnăng: Thựchiệnmộtphéptoánluậnlý
Cấutạo:Cóítnhất1 ngõvàovàcóduynhất1 ngõra
9/24/2510 Copyrights 2017 CE-UIT. All Rights Reserved.

11. IT010 –Tổ chức và Cấu trúc Máy tính
1. Đại số Boolean (4/5) –Tính đối ngẫu
•
11

12. IT010 –Tổ chức và Cấu trúc Máy tính
1. Đại số Boolean (5/5) –Định lý
•Định lý 1: Tính lũy đẳng
x+ x= x
x· x= x
•Định lý 2: Tính nuốt
x+ 1 = 1
x· 0 = 0
•Định lý 3: Tính hấp thụ
x+ x· y= x
x(x+ y) = x
12

13. IT010 –Tổ chức và Cấu trúc Máy tính
Tốiưu luậnlý(1/2)
•Tiên đề 2: Tồn tại phần tử trung hòa
x· 1 = 1 · x= x
x+ 0 = 0 + x= x
•Tiênđề5: Tồntạiphầntửbù
x· x!= x!· x= 0
x+ x!= x!+ x= 1
13
•Định lý 1: Tính lũy đẳng
Øx+ x= x
Øx· x= x
•Định lý 2: Tính nuốt
Øx+ 1 = 1
Øx· 0 = 0
•Định lý 3: Tính hấp thụ
Øx+ x· y= x
Øx(x+ y) = x
Tốiưuluậnlýlàlàmgiảmsốlượng
tổng/tíchhoặcsốlượngbiếnhoặcphần
bùcủanótrongmỗitổng/tích
9/24/25Copyrights 2017 CE-UIT. All Rights Reserved.

14. IT010 –Tổ chức và Cấu trúc Máy tính
2. Tối ưu luận lý (2/2)
•
14
•Có nhiều định lý và tiên đề
Nên sử dụng định lý nào? Tiên đề nào?
•Biểu thức đã tối ưu hay chưa?
Làm sao để phán đoán là biểu thức chưa tối ưu?

15. IT010 –Tổ chức và Cấu trúc Máy tính
4. Phương pháp Karnaugh (1/6) –Cơ sở
•
15

16. IT010 –Tổ chức và Cấu trúc Máy tính
4. Phương pháp Karnaugh (2/6) –Cấu trúc
•K-map là mảng 2 chiều các ô
Số lượng ô = 2n(nlà số biến)
Số lượng ô trên mỗi chiều = 2 i(ilà số biến được gán trên mỗi chiều)
Mỗi ô được gán 1 tổ hợp theo mã Gray: 2 chuỗi bit liên tiếp khác nhau 1 bit
16
fa
01fb
a01
0
1
fbc
a00011110
0
1
fcd
ab00011110
00
01
11
10
f
a
0
1

17. IT010 –Tổ chức và Cấu trúc Máy tính
4. Phương pháp Karnaugh (3/6) –Cấu trúc
xyzffyz
000m0/M0x00011110
001m1/M10m0m1m3m2
010m2/M21m4m5m7m6
011m3/M3
100m4/M4fyz
101m5/M5x00011110
110m6/M60M0M1M3M2
111m7/M71M4M5M7M6
17

18. IT010 –Tổ chức và Cấu trúc Máy tính
4. Phương pháp Karnaugh (4/6) –Nguyên tắc
•Gom các nhóm 2kô liền kề với k≥ 0
klà số biến được tối ưu trong mỗi nhóm
Gom các 1-minterm -> Tổng các tích có giá trị 1
Gom các 0-maxterm -> Tích các tổng có giá trị 0
•Số lần gom phải ít nhất
Số tích/tổng của biểu thức cuối cùng là ít nhất
•Mỗi nhóm phải có ít nhất 1 ô không thuộc các nhóm khác
Tránh trường hợp dư thừa các tích/tổng mà các nhóm khác đã bao phủ
18

19. IT010 –Tổ chức và Cấu trúc Máy tính
4. Phương pháp Karnaugh (5/6)
19
F(x, y, z) = ∑ m(1, 3, 4,
7)
F(a, b, c) = ∏ M(1, 4, 5,
6)
Fyz
x00011110
0
1
Fbc
a00011110
0
1
11
11
0
000

20. IT010 –Tổ chức và Cấu trúc Máy tính
4. Phương pháp Karnaugh (6/6)
fyz
x00011110
0
1
20
fyz
x00011110
0
1
1
1111
F(x, y, z) = x +
yz
0
0000

21. IT010 –Tổ chức và Cấu trúc Máy tính
Quiz
•
21
FCD
AB00011110
00
01
11
10

22. IT010 –Tổ chức và Cấu trúc Máy tính
6. Câu hỏi và Bài tập (1/2)
•
22

23. IT010 –Tổ chức và Cấu trúc Máy tính
6. Câu hỏi và Bài tập (2/2)
•
23

24. IT010 –Tổ chức và Cấu trúc Máy tính
THẢO LUẬN
24