toán rời rạc SLIDE_SET_DaiSoBool

Phép lấy phần bù, tổng và tích Boole tương ứng với các toán tử logic Ø, Ú, Ù, trong đó 0 tương ứng với F (false, sai) và 1 tương ứng với T (true, đúng). Các kết quả của đại số Boole có thể được dịch trực tiếp thành mệnh đề và ngược lại. Dùng các hằng đẳng thức đã có để chứng minh các hằng đẳng thức khác
Nội dung trích xuất từ tài liệu:
toán rời rạc SLIDE_SET_DaiSoBoolChương 6:Đại số Boole Bài giảng Môn học07-09-2007 1 M ở đ ầu• Đại số Boole đưa ra các phép toán làm việc với tập {0, 1}• Các phép toán thường dùng trong đại số Boole: – Phép lấy phần bù được định nghĩa bởi : 0 = 1 và 1=0 – Phép lấy tổng Boole, ký hiệu ‘+’: 1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0 – Phép lấy tích Boole, ký hiệu ‘.’: 1.1 = 1, 1.0 = 0, 0.1 = 0, 0.0 = 0 Bài giảng Môn học 07-09-2007 2 Mở đầu (tt)• Phép lấy phần bù, tổng và tích Boole tương ứng với các toán tử logic ¬, ∨ ∧ trong đó 0 tương ứng với F ,, (false, sai) và 1 tương ứng với T (true, đúng). Các kết quả của đại số Boole có thể được dịch trực tiếp thành mệnh đề và ngược lại. Bài giảng Môn học 07-09-2007 3 Hàm Boole• Định nghĩa: Cho B = {0,1}. – Biến x được gọi là biến Boole nếu nó chỉ nhận giá trị từ B – Một hàm đi từ Bn B được gọi là hàm Boole bậc n• Hàm Boole thường được biểu diễn bằng cách dùng các biểu thức được tạo bởi các biến và phép toán Boole2n 2 Ví dụ: F(x, y, z) = xy + z• Có hàm Boole bậc n khác nhau ? Bài giảng Môn học 07-09-2007 4 Các hằng đẳng thức của đại số Boole Hằng đẳng thức Tên gọi Luật phủ định képx=x Luật lũy đẳngx+x=xx.x = x Luật đồng nhấtx+0=xx.1 =x Luật nuốtx+1=1x.0 = 0 Luật giao hoánx+y=y+xx.y = y.x Bài giảng Môn học07-09-2007 5 Các hằng đẳng thức của đại số Boole (tt) Hằng đẳng thức Tên gọi Luật kết hợp(x + y) + z = x + (y + z)(x.y).z = x.(y.z) Luật phân phốix + yz = (x + y)(x + z)x(y +z) = xy +xz Luật De Morgan(xy) = x + yx+y=x.y Bài giảng Môn học07-09-2007 6 Chứng minh các hằng đẳng thức• Ví dụ 1: Chứng minh sự đúng đắn của luật phân phối x(y +z) = xy +xz x y z y+z x(y + z) xy xz xy + xz 111 110 101 100 011 010 001 000 Bài giảng Môn học 07-09-2007 7Chứng minh các hằng đẳng thức(tt)• Dùng các hằng đẳng thức đã có để chứng minh các hằng đẳng thức khác• Ví dụ: Chứng minh luật hấp thu x(x + y) = x bằng cách dùng các hằng đẳng thức của đại số Boole. Giải: x(x +y) = (x+0)(x +y) – luật ? = x + 0.y – luật ? = x + 0 – luật ? = x – luật? Bài giảng Môn học 07-09-2007 8 Tính đối ngẫu• Đối ngẫu của biểu thức Boole nhận được bằng cách các tổng và tích Boole đổi chỗ cho nhau, các số 0 và 1 đổi chỗ cho nhau Ví dụ: Đối ngẫu của biểu thức x. 1 + (y +z) là ?• Một hằng đẳng thức giữa các hàm biểu diễn bởi bởi các biểu thức Boole vẫn còn đúng nếu ta lấy đối ngẫu hai vế của nó. Bài giảng Môn học 07-09-2007 9 Định nghĩa trừu tượng của đại số Boole• Định nghĩa: Đại số Boole là một tập B có hai phần tử 0 và 1 với hai phép toán hai ngôi ∨ và ∧, và một phép toán một ngôi sao cho các tính chất sau đây đúng với mọi x, y, z thuộc B. x ∨ 0 = x Luật đồng nhất   x ∧ 1= x x ∨ x =1  Luật nuốt  x ∧ x = 0  (x ∨ y ) ∨ z = x ∨ (y ∨ z) Luật kết hợp  (x ∧ y ) ∧ z = x ∧ (y ∧ z) Bài giảng Môn học 07-09-2007 10 Định nghĩa trừu tượng của đại số Boole (tt) Luật giao hoánx ∨ y = y ∨ xx ∧ y = y ∧ x x ∨ (y ∧ z ) = ( x ∨ y ) ∧ ( x ∨ z ) Luật phân phối x ∧ (y ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z ) Bài giảng Môn học07-09-2007 11 Biểu diễn các hàm Boole• Khai triển tổng các tích (dạng tuyển chuẩn tắc) Ví dụ: Tìm các biểu thức Boole biểu diễn các hàm F(x, y, z) và G(x, y, z) có các giá trị được cho trong bảng sau: x y z G F 1 1 1 0 0 1 1 0 0 1 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 Bài giảng Môn học 07-09-2007 12 ...