zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Toán rời rạc: Chương 3 - Đại số Bool - Hàm Bool

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

Báo xấu

199
lượt xem 6
download

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

Bài giảng Toán rời rạc: Chương 3 - Đại số Bool - Hàm Bool giới thiệu tới các bạn những nội dung về đại số Bool; hàm Bool; mạng logic (mạng các cổng). Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về lĩnh vực này.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Chương 3 - Đại số Bool - Hàm Bool

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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

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

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.