Đai số Bool ̣
lượt xem 20
download
Xét hàm Bool n biến f(x1,x2,…,xn) Vì mỗi biến xi chỉ nhận hai giá trị 0, 1 nên chỉ có 2n trường hợp của bộ biến (x1,x2,…,xn). Do đó, để mô tả f ta có thể lập bảng gồm 2n hàng ghi tất cả các giá trị của f tùy theo 2n trường hợp của biến. Ta gọi đây là bảng chân trị của f.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Đai số Bool ̣
- 1 Đaị số Bool
- 2 Nội Dung Chính Hàm Bool Các dạng biểu diễn hàm Bool Biểu đồ Karnaugh cho hàm Bool Thuật toán tìm công thức đa thức tối tiểu cho hàm Bool Hàm Bool của mạch điện Bài tập Đaị số Bool HÀM BOOL
- 3 Nội Dung Chính (tt) I. Hàm Bool 1. Đại số Bool nhị phân 2. Hàm Bool 3. Đại số Bool của các hàm Bool II. Các Dạng Biểu Diễn Hàm Bool 1. Từ đơn 2. Đơn thức 3. Đơn thức tối tiểu trong Fn 4. Đa thức trong Fn 5. Dạng nối rời chính tắc của hàm Bool 6. Cách tìm dạng nối rời chính tắc của hàm Bool 7. Mệnh đề 8. So sánh các dạng đa thức của hàm Bool 9. Công thức đa thức tối tiểu cho hàm Bool Đaị số Bool
- 4 Nội Dung Chính (tt) III. Biểu Đồ Karnaugh Cho Hàm Bool 1. Bảng mã 2. Biểu đồ Karnaugh cho hàm Bool 3. Nhận xét 4. Tính chất 5. Biểu đồ của 1 đơn thức 6. Biểu đồ của đa thức 7. Tế bào và tế bào lớn III. Thuật Toán Tìm Công Thức Đa Thức Tối Tiểu Cho Hàm Bool 1. Họ phủ và họ phủ tối tiểu 2. Thuật toán III. Đại Số Các Mạch Điện 1. Hàm Bool của mạch điện 2. Các loại cổng cớ bản 3. Thiết kế mạng các cổng tổng hợp hàm Bool 4. Tối ưu hóa việc thiết kế mạng các cổng tổng hợp hàm Bool III. Bài Tập Đaị số Bool
- ̀ BOOL HAM 5 Đaị số Bool
- 6 I. Hàm Bool George Boole (1815-1864) Đaị số Bool
- 7 I. Hàm Bool 1. Đại số Bool nhị phân: Đại số bool của các số nhị phân cũng thỏa các trường hợp (luật) như trong mệnh đề. Luât phủ định kép ¬ ¬E E Luật lũy đẳng E ˄ E E E ˅ E E Luật giao hoán F˄ E E ˄ F F ˅ E E ˅ F Luật kết hợp (E ˄ F) ˄ G E ˄ (F ˄ G) (E ˅ F) ˅ G E ˅ (F ˅ G) Luật phân phối E ˄ (G ˅ F) (E ˄ G) ˅ (E ˄ F) E ˅ (G ˄ F) (E ˅ G) (E ˅ F) Luật phủ định De-Morgan ¬ (E ˄ F) ¬E ˅ ¬F ¬ (E ˅ F) (¬E) ˄ (¬F) Luật hấp thụ E ˄ (E ˅ F) E ; E ˅ (E ˅ F) E Luật trung hòa E ˄ 1 E E ˅ 0 E Luật thống trị E ˄ 0 0 E ˅ 1 1 Luật bù E ˄ ¬E 0 E ˅¬E 1 Luật kéo theo E → F ¬E ˅ F Phủ định kéo theo ¬( E → F) E ˄ ¬F Đaị số Bool
- 8 I. Hàm Bool 2. Hàm Bool: a. Định nghĩa Chon ≥1 nvà∈ N . Hàm Bool n biến là ánh xạ f : Bn → B, trong đó B = {0, 1} Một hàm Bool n biến là một hàm số có dạng f = f(x1 ,x2,…,xn), trong đó mỗi biến trong x1, x2,…, xn và f chỉ nhận giá trị trong B = {0, 1} Ký hiệu Fn để chỉ tập các hàm Bool n biến. Ví dụ: Biểu thức logic E = E(p1,p2,…,pn) theo n biến p1, p2,…, pn là một hàm Bool n biến. Đaị số Bool
- 9 I. Hàm Bool 2. Hàm Bool: a. Bảng chân trị Xét hàm Bool n biến f(x1,x2,…,xn) Vì mỗi biến xi chỉ nhận hai giá trị 0, 1 nên chỉ có 2n trường hợp của bộ biến (x1,x2,…,xn). Do đó, để mô tả f ta có thể lập bảng gồm 2n hàng ghi tất cả các giá trị của f tùy theo 2n trường hợp của biến. Ta gọi đây là bảng chân trị của f. Đaị số Bool
- I. Hàm Bool 10 2. Hàm Bool: a. Bảng chân trị Ví dụ: cho mạch điện như hình vẽ A M N B C Tùy theo cách trạng thái cầu dao A, B, C mà ta sẽ có dòng điện đi qua MN. Bảng giá trị Đaị số Bool
- 11 I. Hàm Bool 3. Các phép toán trên hàm Bool: Với f , g ∈ F n ta định nghĩa tổng, tích, bù hàm Bool của f và g như sau f ∨ g = ( f + g) f ∧ g = fg = f .g f = 1− f Đaị số Bool
- 12 I. Hàm Bool 3. Các phép toán trên hàm Bool: Ví dụ: n = 2 X1 1 1 0 0 X2 1 0 1 0 0(x1, x2) 0 0 0 0 1(x1, x2) 1 1 1 1 f(x1, x2) 0 1 0 1 g(x1, x2) 1 1 0 0 ¬ f(x1, x2) 1 0 1 0 ¬ g(x1, x2) 0 0 1 1 f g(x1, x2) 0 1 0 0 f V g(x1, x2) 1 1 0 1 Đaị số Bool
- Các Dạng Biểu Diễn Hàm Bool 13 Đaị số Bool
- II. Các Dạng Biểu Diễn Hàm 14 Bool 1. Từ đơn: Xét tập hợp các hàm Bool của n biến Fn theo n biến x1 ,x2,…,xn. Mỗi hàm bool xi hay ¬ xi được gọi là từ đơn. Ví dụ: x1, x2, x3,… 2. Đơn thức: Là tích khác không của một số hữu hạn từ đơn. Hay có thể hiểu là: Tích Bool của 1 hay nhiều từ đơn sao cho tích này khác 0. Ví dụ: Trong F4 xét x3, x1x2, x1x2x3x4 (bậc của đơn thức là số thành phần x) Trong Fn các đơn thức có bậc từ 1 đến n x, ¬x, y, ¬y, z, ¬z, t, ¬t là các từ đơn x¬yz ¬t, ¬x ¬yt là các đơn thức Đaị số Bool
- II. Các Dạng Biểu Diễn Hàm 15 Bool 3. Đơn thức tối tiểu trong Fn: Là đơn thức có bậc cao nhất bằng n trong Fn. Dạng tổng quát m = y1y2...yn, yi = xi hoặc ¬xi 1 ≤ i ≤n Ví dụ: Trong F4 xét các đơn thức t ối ti ểu b ậc 4 x1x2x3x4, x1¬x2x3x4, x1x2x3x4, ¬x1¬x2¬x3¬x4 4. Đa thức trong Fn: Là tổng Bool các đơn thức f = u 1 V u2 V u3 V…V uk, trong đó ui là các đơn thức. Ví dụ: Trong F5 xét đa thức f(x1,x2,x3,x4) = x1¬x5 V ¬x2x3¬x4 V ¬x3 V ¬x1x3x4x5 => Tổng Bool 4 đơn thức f(1,0,1,1,0)=1¬0V¬01¬1V¬1V¬1110 = 1 Đaị số Bool
- II. Các Dạng Biểu Diễn Hàm 16 Bool 5. Dạng nối rời chính tắc của hàm Bool: Cho f thuộc Fn , f có thể viết dưới dạng sau f = m1 V m2 V m3 V …V mk, (*) với mi là các đơn thức tối tiểu bậc = n (i = 1…n ) (*) được gọi là dạng nối rời chính tắc của f Ví dụ: Trong F4 có dạng biểu diễn sau đây f(x,y,z,t) = x¬y¬zt V ¬xyzt V xy¬z¬t có dạng (*) Đaị số Bool
- II. Các Dạng Biểu Diễn Hàm 17 Bool 6. Cách tìm dạng nối rời chính tắc của hàm Bool: Có 2 cách để xác định dạng nối rời chính tắc của một hàm Bool Cách 1: Bổ sung từ đơn còn thiếu vào các đơn thức Bước 1: Khai triển hàm Bool thành tổng của các đơn thức Bước 2: Với mỗi từ đơn thu được ở bước 1, ta nhân đơn thức đó với các tổng dạng với xi là những từ đơn bị thiếu trong đơn thức đó Bước 3: Tiếp tục khai triển hàm thu được ở bước 2 và loại bỏ những đơn thức bị trùng. Công thức đa thức thu được chính là dạng nối rời chính tắc của hàm Bool ban đầu Ví dụ: Trong F3 tìm dạng nối dời chính tắc f(x,y,z)= ¬x V ¬yz V xy¬z f = ¬x(y V ¬y).(z V ¬z) V (¬x V x)¬yz V xy¬z f = ¬xyz V ¬xy¬z V ¬x¬yz V ¬x¬y¬z V ¬x¬yz V x¬yzVxy¬z (*) (*) Chính là dạng nối rời chính tắc Đaị số Bool
- 18 II. Các Dạng Biểu Diễn Hàm Bool 6. Cách tìm dạng nối rời chính tắc của hàm Bool: Có 2 cách để xác định dạng nối rời chính tắc của một hàm Bool Cách 2: dùng bảng chân trị. Để ý đến các vector bool trong bảng chân trị mà f=1, tại đó Vector bool thứ k là u1, u2,…, un mà f(u1, u2, …, un) = 1. Ví dụ: cho f(x,y) = x V ¬y. Tìm biểu thức dạng nối rời chính tắc của f Lập bảng chân trị của f Các thể hiện làm cho f = 1 là 00, 10, 11 l ập đ ược các t ừ t ối ti ểu t ương ứng. Vậy dạng nối rời chính tắc của f là f(x,y) = ¬x ¬y V x ¬y V xy Đaị số Bool
- 19 II. Các Dạng Biểu Diễn Hàm Bool 7. Mệnh đề: f ∈ Fn Khi đó, f có thể có nhiều dạng đa thức khác nhau , ta chọn ra các công thức đơn giản nhất có thể được. Chúng chính là các công thức đa thức tối tiểu của f. f chỉ có một dạng nối dời chính thức duy nhất (không tính sự hoán đổi của các đơn thức). Đaị số Bool
- 20 II. Các Dạng Biểu Diễn Hàm Bool 8. So sánh các dạng đa thức của hàm Bool: f ∈ Fn và f có 2 dạng đa thức f = u1 V u2 V… V up (1) f = v1 V v2 V… V vq (2) a. Ta nói (1) và (2) đơn giản ngang nhau nếu p=q deg(uj) = deg(vj) (1 ≤ j ≤ p) b. Ta nói (1) đơn giản hơn (2) hay (2) phức tạp hơn (1) p≤q deg(uj) ≤ deg(uj) (1 ≤ j ≤ p) chú ý: Có thể hoán vị v1, v2, …,vq trước khi so sánh bậc nếu cần thiết Có thể có những cặp đa thức không so sánh được Đaị số Bool
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng môn Đại số Boole
15 p | 633 | 195
-
Bài giảng Toán rời rạc - Chương 5: Đại số Boole
12 p | 283 | 42
-
Bài giảng Toán rời rạc - Chương 3: Đại số Bool
68 p | 247 | 37
-
Bài giảng Toán rời rạc - Chương 4: Đại số Boole (ĐH Công nghệ Thông tin)
76 p | 214 | 29
-
Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 3: Hàm Bool và mạch tổ hợp
15 p | 338 | 28
-
CHƯƠNG 6 :ĐẠI SỐ BOOLE
20 p | 289 | 26
-
Chương 5: Đại số Boole
2 p | 218 | 18
-
Bài giảng Đại số B2: Chương 3 - TS. Nguyễn Viết Đông
69 p | 191 | 13
-
Bài giảng Toán ứng dụng trong Tin học: Chương 5 - Đại Số Boole
30 p | 140 | 12
-
Bài giảng Toán rời rạc: Hàm bool - Nguyễn Thành Nhựt
28 p | 117 | 8
-
Bài giảng Toán rời rạc - Chương 4: Đại Số Bool (Phạm Thế Bảo)
78 p | 82 | 7
-
Bài giảng học Đại số Boole
37 p | 48 | 6
-
Bài giảng Toán rời rạc: Chương 3 - Đại số Bool - Hàm Bool
11 p | 204 | 6
-
Bài giảng Toán rời rạc: Đại số Boole - TS. Đỗ Đức Đông
30 p | 12 | 6
-
Bài giảng Đại số Boole - Chương VI
22 p | 86 | 5
-
Thực hành Toán rời rạc - Chương 6: Cơ bản về đại số Bool, Finite State Machine
17 p | 17 | 4
-
Bài giảng Toán rời rạc: Đại số Boole - TS. Nguyễn Đức Đông
30 p | 42 | 3
-
Bài giảng Toán rời rạc - Phần 6: Đại số Bool và hàm Bool (TS. Nguyễn Viết Đông)
68 p | 37 | 1
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn