Toán học - Chương III: Đại số bool hàm bool

06/05/2010 1 Chương III ðẠI SỐ BOOL HÀM BOOL 06/05/2010 2 1. ðại Số Bool Một ñại số Bool (A,+,.) là một tập hợp A ≠ ∅ với hai phép toán (+), (.), thỏa 5 tính chất sau: • Tính giao hoán: ∀x,y∈ A x.y = y.x; x+y = y+x; 06/05/2010 3 • Tính phân bố: ∀x,y,z∈ A x.(y+z) = (x.y)+(x.z); x+(y.z) = (x+y).(x+z). 1. ðại Số Bool • Tính kết hợp: ∀x,y,z∈ A (x.y).z = x.(y.z); (x+y)+z = x+(y+z). 06/05/2010 4 • Có các phần tử trung hòa 1 và 0: ∀x ∈A x.1 = 1.x = x; x + 0 = 0 ∨ x = x. • Mọi phần tử ñều có phần tử bù:∀x∈A,∃ ∈A, x. = .x = 0; X+ = + x = 1. 1. ðại Số Bool x x x x x 06/05/2010 2 06/05/2010 5 1. ðại Số Bool Ví dụ: Xét F là tập hợp tất cả các dạng mệnh ñề theo n biến p1, p2,,pn với hai phép toán nối liền ∧, phép toán nối rời ∨, trong ñó ta ñồng nhất các dạng mệnh ñề tương ñương. Khi ñó F là một ñại số Bool với phần tử 1 là hằng ñúng 1, phần tử 0 là hằng sai 0, phần tử bù của dạng mệnh ñề E là dạng mệnh ñề bùE 06/05/2010 6 1. ðại Số Bool Xét tập hợp B = {0, 1}. Trên B ta ñịnh nghĩa hai phép toán +,. như sau: Khi ñó, B trở thành một ñại số Bool . 0 1 0 0 0 1 0 1 + 0 1 0 0 0 1 0 1 06/05/2010 7 1. ðại Số Bool Cho ñại số Bool (A,+,.). Khi ñó với mọi x,y∈A, ta có: 1. x.x = x; x+x = x. 2. x.0 = 0.x =0; x+1 =1+ x = 1. 3. Phần tử bù của x là duy nhất và = x; 4. Công thức De Morgan: 5. Tính hấp thụ: x(x+y) = x; x+(xy) = x. = + + = xy x y; x y xy. x = =1 0; 0 1. 06/05/2010 8 2. Hàm Bool ðịnh nghĩa Một hàm Bool n biến là một á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 chỉ nhận hai giá trị 0,1 và f nhận giá trị trong B = {0,1}. Ký hiệu Fn ñể chỉ tập các hàm Bool n biến. 06/05/2010 3 06/05/2010 9 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. 2. Hàm Bool 06/05/2010 10 Xét kết quả f trong việc thông qua một Quyết ñịnh dựa vào 3 phiếu bầu x, y, z. 1. Mỗi phiếu chỉ lấy một trong hai giá trị: 1 (tán thành) hoặc 0 (bác bỏ). 2. Kết quả f là 1 (thông qua Quyết ñịnh) nếu ñược ña số phiếu tán thành, là 0 (không thông qua Quyết ñịnh) nếu ña số phiếu bác bỏ. Khi ñó f là hàm Bool theo 3 biến x, y, z có bảng chân trị như sau: 2. Hàm Bool Ví dụ: 06/05/2010 11 2. Hàm Bool x y z f 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 06/05/2010 12 Các phép toán trên hàm Bool Các phép toán trên Fn ñược ñịnh nghĩa như sau: 1. Phép cộng Bool +: Với f, g ∈ Fn ta ñịnh nghĩa tổng Bool của f và g: 2. Hàm Bool ∀x = (x1,x2,,xn)∈ Bn, (f +g)(x) = f(x) + g(x) – f(x)g(x) f +g ∈ Fn và (f+g)(x) = max{f(x),g(x)} Dễ thấy 06/05/2010 4 06/05/2010 13 2. Phép nhân Bool .: Với f, g ∈Fn ta ñịnh nghĩa tích Bool của f và g 2. Hàm Bool Các phép toán trên hàm Bool ∀x=(x1,x2,,xn)∈Bn, (f.g)(x) = f(x)g(x) Dễ thấy: f.g ∈Fn và (f.g)(x) = min{f(x),g(x)} 06/05/2010 14 3. Phép lấy hàm bù: Với f ∈ Fn ta ñịnh nghĩa hàm bù của f như sau: 1f f= − 2. Hàm Bool Các phép toán trên hàm Bool 06/05/2010 15 Dạng nối rời chính tắc của hàm Bool • 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 ñược gọi là từ ñơn. • ðơn thức là tích khác không của một số hữu hạn từ ñơn. • Từ tối tiểu là tích khác không của ñúng n từ ñơn. • Công thức ña thức là công thức biểu diễn hàm Bool thành tổng của các ñơn thức. • Dạng nối rời chính tắc là công thức biểu diễn hàm Bool thành tổng của các từ tối tiểu. ix 2. Hàm Bool 06/05/2010 16 Công thức ña thức tối tiểu • ðơn giản hơn Cho hai công thức ña thức của một hàm Bool: f = m1+ m2 +. +mk (F) f =M1 + M2 + + Ml (G) Ta nói rằngcông thức F ñơn giản hơn công thức G nếu tốn tại ñơn ánh h: {1,2,..,k} → { 1,2,, l} sao cho với mọi i∈ {1,2,..,k} thì số từ ñơn của mi không nhiều hơn số từ ñơn của Mh(i) 2. Hàm Bool 06/05/2010 5 06/05/2010 17 • ðơn giản như nhau: Nếu F ñơn giản hơn G và G ñơn giản hơn F thì ta nói F và G ñơn giản như nhau. Công thức ña thức tối tiểu: Công thức F của hàm Bool f ñược gọi là tối tiểu nếu với bất kỳ công thức G của f mà ñơn giản hơn F thì F và G ñơn giản như nhau 2. Hàm Bool Công thức ña thức tối tiểu 06/05/2010 18 2. Hàm Bool Phương pháp biểu ñồ Karnaugh Xét f là một hàm Bool theo n biến x1,x2,,xn với n = 3 hoặc 4. Trường hợp n = 3: f là hàm Bool theo 3 biến x, y, z. Khi ñó bảng chân trị của f gồm 8 hàng. Thay cho bảng chân trị của f ta vẽ một bảng chữ nhật gồm 8 ô, tương ứng với 8 hàng của bảng chân trị, ñược ñánh dấu như sau: x x z 101 111 011 001 100 110 010 000 y y x x z y y 06/05/2010 19 2. Hàm Bool Phương pháp biểu ñồ Karnaugh Với qui ước: Khi một ô nằm trong dãy ñược ñánh dấu bởi x thì tại ñó x =1, bởi thì tại ñó x =0, tương tự cho y, z. Các ô tại ñó f bằng 1 sẽ ñược ñánh dấu (tô ñậm hoặc gạch chéo). Tập các ô ñược ñánh dấu ñược gọi là biểu ñồ Karnaugh của f, ký hiệu là kar(f). x 06/05/2010 20 2. Hàm Bool Trường hợp n = 4: f là hàm Bool theo 4 biến x, y, z, t. Khi ñó bảng chân trị của f gồm 16 hàng. Thay cho bảng chân trị của f ta vẽ một bảng chữ nhật gồm 16 ô, tương ứng với 16 hàng của bảng chân trị, ñược ñánh dấu như sau: x x z 1010 1110 0110 0010 z 1011 1111 0111 0011 t 1001 1101 0101 0001 t 1000 1100 0100 0000 y y Phương pháp biểu ñồ Karnaugh x x z y y z t t 06/05/2010 6 06/05/2010 21 2. Hàm Bool Trong cả hai trường hợp, hai ô ñược gọi là kề nhau (theo nghĩa rộng), nếu chúng là hai ô liền nhau hoặc chúng là ô ñầu, ô cuối của cùng một hàng (cột) nào ñó. Nhận xét rằng, do cách ñánh dấu như trên, hai ô kề nhau chỉ lệch nhau ở một biến duy nhất. Phương pháp biểu ñồ Karnaugh 06/05/2010 22 2. Hàm Bool Tế bào Xét các hàm Bool theo n biến x1,x2,,xn. Khi ñó, nếu f là một ñơn thức có dạng tích của k từ ñơn phân biệt thì kar(f) là một hình chữ nhật gồm 2n-k ô kề nhau. Những hình chữ nhật gồm một lũy thừa của 2 những ô kề nhau ñược gọi là các tế bào. Như vậy, biểu ñồ Karnaugh của một ñơn thức là một tế bào. Ngược lại, nếu T là một tế bào thì T là biểu ñồ Karnaugh của một ñơn thức duy nhất m, cách xác ñịnh m như sau: lần lượt chiếu T lên các cạnh, nếu toàn bộ hình chiếu nằm trọn trong một từ ñơn nào thì từ ñơn ñó mới xuất hiện trong m. 06/05/2010 23 2. Hàm Bool Ví dụ: Xét các hàm Bool theo 4 biến x, y, z, t. Biểu ñồ Karnaugh của ñơn thức xyzt x x z z t t y y x x z y y z t t 06/05/2010 24 2. Hàm Bool Ví dụ: Xét các hàm Bool theo 4 biến x, y, z, t. Biểu ñồ Karnaugh của ñơn thức x x z z t t y y x x z y y z t t yzt 06/05/2010 7 06/05/2010 25 2. Hàm Bool Ví dụ: Xét các hàm Bool theo 4 biến x, y, z, t. Biểu ñồ Karnaugh của ñơn thức x x z z t t y y x x z y y z t t yt 06/05/2010 26 2. Hàm Bool Ví dụ: Xét các hàm Bool theo 4 biến x, y, z, t. Biểu ñồ Karnaugh của ñơn thức x x z z t t y y x x z y y z t t t 06/05/2010 27 2. Hàm Bool Tế bào lớn Cho hàm Bool f. Ta nói T là một tế bào lớn của kar(f) nếu T thoả hai tính chất sau: a. T là một tế bào và T ⊆ kar(f). b. Không tồn tại tế bào T’ nào thỏa T’ ≠ T và T ⊆ T’⊆ kar(f). 06/05/2010 28 2. Hàm Bool Ví dụ: Xét hàm Bool f theo 4 biến x, y, z, t có biểu ñồ Karnaugh như sau: x x z z t t y y x x z y y z t t 06/05/2010 8 06/05/2010 29 2. Hàm Bool Kar(f) có 6 tế bào lớn như sau: x x z z t t y y x x z y y z t t x x z z t t y y x x z y y z t t xz yz 06/05/2010 30 2. Hàm Bool x x z z t t y y x x z y y z t t x x z z t t y y x x z y y z t t xt xy 06/05/2010 31 2. Hàm Bool x x z z t t y y x x z y y z t t x x z z t t y y x x z y y z t t yzt yt 06/05/2010 32 2. Hàm Bool Thuật toán xác ñịnh tất cả các công thức ña thức tối tiểu của hàm Bool f Bước 1: Vẽ biểu ñồ Karnaugh của f. Bước 2: Xác ñịnh tất cả các tế bào lớn của kar(f). Bước 3: Xác ñịnh các tế bào lớn nhất thiết phải chọn. Ta nhất thiết phải chọn tế bào lớn T khi tồn tại một ô của kar(f) mà ô này chỉ nằm trong tế bào lớn T và không nằm trong bất kỳ tế bào lớn nào khác. 06/05/2010 9 06/05/2010 33 2. Hàm Bool Bước 4: Xác ñịnh các phủ tối tiểu gồm các tế bào lớn. Nếu các tế bào lớn chọn ñược ở bước 3 ñã phủ ñược kar(f) thì ta có duy nhất một phủ tối tiểu gồm các tế bào lớn của kar(f). Nếu các tế bào lớn chọn ñược ở bước 3 chưa phủ ñược kar(f) thì xét một ô chưa bị phủ, sẽ có ít nhất hai tế bào lớn chứa ô này, ta chọn một trong các tế bào lớn này. Cứ tiếp tục như thế ta sẽ tìm ñược tất cả các phủ gồm các tế bào lớn của kar(f). Loại bỏ các phủ không tối tiểu, ta tìm ñược tất cả các phủ tối tiểu gồm các tế bào lớn của kar(f). 06/05/2010 34 2. Hàm Bool Bước 5: Xác ñịnh các công thức ña thức tối tiểu của f. Từ các phủ tối tiểu gồm các tế bào lớn của kar(f) tìm ñược ở bước 4 ta xác ñịnh ñược các công thức ña thức tương ứng của f. So sánh các công thức trên: Loại bỏ các công thức ña thức mà có một công thức ña thức nào ñó thực sự ñơn giản hơn chúng. Các công thức ña thức còn lại chính là các công thức ña thức tối tiểu của f. 06/05/2010 35 2. Hàm Bool Ví dụ 1: Tìm tất cả các công thức ña thức tối tiểu của hàm Bool Ta có: Bước 1:Vẽ kar(f): ( , , , ) ( )f x y z t xyzt x y xz yz xy z t= + + + + + f xyzt x y xz yz xyz xyt= + + + + + x x z 1 2 3 z 4 5 6 t 7 8 t 9 10 y y x x z y y z t t 06/05/2010 36 2. Hàm Bool Bước 2: Kar(f) có các tế bào lớn như sau: x x z 1 2 z 4 5 t 7 8 t 9 10 y y x x z y y z t t x x z 2 3 z 5 6 t t y y x x z y y z t t x yt 06/05/2010 10 06/05/2010 37 2. Hàm Bool Bước 3: Xác ñịnh các tế bào lớn nhất thiết phải chọn. – Ô 1 nằm trong một tế bào lớn duy nhất x. Ta chọn x. – Ô 3 nằm trong một tế bào lớn duy nhất yz. Ta chọn yz. 06/05/2010 38 2. Hàm Bool Bước 4: Xác ñịnh các phủ tối tiểu gồm các tế bào lớn. Các ô ñược các tế bào lớn ñã chọn ở bước 3 phủ như sau: Ta ñược duy nhất một phủ tối tiểu gồm các tế bào lớn của kar(f): x; yz. x x z 1 2 3 z 4 5 6 t 7 8 t 9 10 y y x x z y y z t t 06/05/2010 39 2. Hàm Bool Bước 5: Xác ñịnh các công thức ña thức tối tiểu của f. Ứng với phủ tối tiểu gồm các tế bào lớn tìm ñược ở bước 4 ta tìm ñược duy nhất một công thức ña thức tối tiểu của f: f x yz= + 06/05/2010 40 3. Mạng logic (Mạng các cổng) ðịnh nghĩa Một mạng logic hay một mạng các cổng là một hệ thống có dạng: x1 x2 xn f(x1,x2,..., xn) 06/05/2010 11 06/05/2010 41 3. Mạng logic (Mạng các cổng) trong ñó: - Input: x1, x2,..., xn là các biến Bool. - Output: f(x1, x2,..., xn) là hàm Bool. Ta nói mạng logic trên tổng hợp hay biểu diễn hàm Bool f. Một mạng logic bất kỳ luôn luôn ñược cấu tạo từ một số mạng sơ cấp mà ta gọi là các cổng 06/05/2010 42 3. Mạng logic (Mạng các cổng) Cổng NOT Cổng AND Cổng OR 06/05/2010 43 3. Mạng logic (Mạng các cổng) x x y OR y x y yx yxxy + x x y x y yx yxxy + x