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

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.
Nội dung trích xuất từ tài liệu:
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ố Bool06/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ộ ...