Xem mẫu
- TOÁN RỜI RẠC
Chương 8:
Đại số Boole
Giảng viên: ThS. Trần Quang Khải
- Nội dung
1. Giới thiệu:
Boole Algebra.
Hàm Boole.
Hằng đẳng thức đại số Boole.
2. Các cổng logic.
3. Cực tiểu hóa mạch:
Bản đồ Karnaugh.
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 2
- Chương 8
Giới thiệu
Boole Algebra
Giảng viên: ThS. Trần Quang Khải
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 3
- Giới thiệu
Nhắc lại phần mệnh đề:
TRUE & FALSE.
Các mạch điện tử trong máy tính:
1 & 0.
Thiết kế các
mạch điện tử?
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 4
- Giới thiệu
Mạch điện tử:
Trạng thái chuyển mạch: Mở & Đóng.
Dụng cụ quang học: Sáng & Tối.
Sử dụng các quy tắc của Logic:
Claude Shannon: 1938.
“The Law of Thought” (1854).
Boole Algebra.
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 5
- Giới thiệu
George Boole (1854) – English mathematician
“The Mathematical Analysis of Logic” (1848).
“The Law of Thought” (1854) Boole Algebra.
Toán rời rạc: 2011-2012 Chương 1: Logic 6
- Boole Algebra
Đại số Boole:
Các phép toán
trên tập {0, 1}
Các quy tắc
Ứng dụng chủ yếu:
Chuyển mạch điện tử.
Chuyển mạch quang học.
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 7
- Boole Algebra
Phép toán cơ bản:
Phần bù: 0 1 Phép toán
NOT Logic?
10
Tổng Boole: 1 1 1; 1 0 1; 0 1 1
OR
00 0
Tích Boole:
AND 1.1 1
1.0 0; 0.1 0; 0 0 0
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 8
- Boole Algebra
Example:
1.0 (0 1) 0 1
00
0
(T F ) ( F T ) F
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 9
- Hàm Boole
Biến Boole (Boolean variable):
Biến x được gọi là biến Boole nếu nó chỉ nhận các giá
trị trong tập {0, 1}.
Hàm Boole (Boolean function):
Một hàm từ tập {(x1, x2…xn)|xi {0,1}, 1≤ i ≤n} tới
tập {0,1} được gọi là hàm Boole bậc n.
Ví dụ: F ( x, y, z ) xy z
Biểu thức Boole
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 10
- Hàm Boole
Ví dụ: F ( x, y, z ) xy z
x y z xy z F(x, y, z)
1 1 1 1 0 1
1 1 0 1 1 1
1 0 1 0 0 0
1 0 0 0 1 1
0 1 1 0 0 0
0 1 0 0 1 1
0 0 1 0 0 0
0 0 0 0 1 1
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 11
- Boole Algebra
Phép toán XOR: 11 0
1 0 1
0 1 1
00 0
Example:
lập bảng giá trị để chứng minh
x y ( x y )( xy ) ( xy ) ( xy )
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 12
- Hằng đẳng thức đại số Boole
Hằng đẳng thức Tên gọi
x=x Luật phần bù kép
x + x = x; x . x = x Luật lũy đẳng
x + 0 = x; x . 1 = x Luật đồng nhất
x + 1 = 1; x . 0 = 0 Luật nuốt
x + y = y + x; xy = yx Luật giao hoán
x + (y + z) = (x + y) + z Luật kết hợp
x(yz) = (xy)z
x + yz = (x + y) . (x + z) Luật phân phối
x . (y + z) = xy + xz
( xy ) x y Luật De Morgan
( x y) x . y
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 13
- Chứng minh luật phân phối
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 14
- Hàm Boole
Ví dụ:
Tìm giá trị của các biến Boole x và y sao cho:
xy = x + y
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 15
- Hàm Boole
Ví dụ:
Lập bảng biểu diễn giá trị các hàm sau:
a) F ( x, y , z ) xy ( xyz )
b) F ( x, y , z ) x ( yz y z )
c) F ( x, y , z ) x y yz
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 16
- Biểu diễn các hàm Boole
Hai vấn đề trong đại số Boole:
1. Cho các giá trị của hàm Boole, làm thế nào để tìm
biểu thức Boole biểu diễn hàm đó?
2. Có biểu thức nào đơn giản hơn để biểu diễn cùng
một hàm Boole hay không?
Rút gọn biểu thức Boole?
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 17
- Tổng của tích
x y z F G
1 1 1 0 0 F(x, y, z) = ?
1 1 0 0 1 G(x, y, z) = ?
1 0 1 1 0
1 0 0 0 0
0 1 1 0 0
0 1 0 0 1
0 0 1 0 0
0 0 0 0 0
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 18
- Tổng của tích
x y z F G
1 1 1 0 0
1 1 0 0 1 F ( x, y, z ) xyz
1 0 1 1 0 G ( x, y, z ) xy z x yz
1 0 0 0 0
0 1 1 0 0
0 1 0 0 1
0 0 1 0 0
0 0 0 0 0
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 19
- Khái niệm
Literal (Đơn tử):
là một biến Boole hoặc phần bù của nó.
Minterm (Tiểu hạng):
là một tích các literal (gồm chính xác n literals).
F ( x, y, z ) xyz
G ( x, y, z ) xy z x yz
Toán rời rạc: 2011-2012 Chương 8: Đại số Boole 20
nguon tai.lieu . vn
