toán rời rạc SLIDE_SET_DaiSoBool

Chia sẻ: Trần Công Chính | Ngày: | Loại File: PPT | Số trang:36

Thêm vào BST

Báo xấu

175
lượt xem 20
download

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

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

Chủ đề:

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

Lưu

Nội dung Text: toán rời rạc SLIDE_SET_DaiSoBool

Chương 6: Đại số Boole Bài giảng Môn học 07-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ép x=x Luật lũy đẳng x+x=x x.x = x Luật đồng nhất x+0=x x.1 =x Luật nuốt x+1=1 x.0 = 0 Luật giao hoán x+y=y+x x.y = y.x Bài giảng Môn học 07-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ối x + yz = (x + y)(x + z) x(y +z) = xy +xz Luật De Morgan (xy) = x + y x+y=x.y Bài giảng Môn học 07-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 7
Chứ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ọc 07-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
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ụ 1: 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:  F(x, y, z) = xyz x y z F G G(x, y, z) = xyz + xyz 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 13
Biểu diễn các hàm Boole(tt) • Ví du 2: Tìm khai triển tổng các tích của hàm F(x, y, z) = (x + y) z Giải: Bảng giá trị của hàm F: x y z x+y z (x + y) z  F(x, y, z) = ? 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 Bài giảng Môn học 07-09-2007 14
Biểu diễn các hàm Boole(tt) • Khai triển tích các tổng (dạng hội chuẩn tắc): Lấy đối ngẫu từ khai triển tổng các tích. Ví dụ: Tìm dạng khai triển tích các tổng của hàm F(x, y, z) và G(x, y, z) ở ví dụ 1. Bài giảng Môn học 07-09-2007 15
Tính đầy đủ • Tất cả các hàm Boole đều có thể bằng cách dùng các phép toán Boole . , + , . – Khi đó ta nói tập hợp {. , + , } là đầy đủ Ta có: – Tập {., } là đầy đủ ? – Tập {+, } là đầy đủ ? – Tập {., +} không phải là đầy đủ ? – Tập {|} là đầy đủ, tập {↓} là đầy đủ ? (phép | hay NAND và ↓ hay NOR được định nghĩa: 1|1 = ? , 1|0 = ? ,0|1 = ? ,0|0 = ? . 1↓1 = ? , 1↓ = ? , 0↓1 =? ,0↓ 0 = ? .) 0 Bài giảng Môn học 07-09-2007 16
Tính đầy đủ (tt) • Tập {., } là đầy đủ vì: x + y = x y • Tập {+, } là đầy đủ vì: x.y = ? • Tập {|} là đầy đủ vì: x = x|y xy = (x|y)|(y|x) Tập {↓} là đầy đủ vì: ? • Bài giảng Môn học 07-09-2007 17
Các cổng logic • Các loại cổng cơ bản: – Cổng NOT hay bộ đảo: x x x – Cổng AND: xy y x – Cổng OR x+y y Bài giảng Môn học 07-09-2007 18
Các cổng logic (tt) • Các cổng có n đầu vào: x1 x2 x1 x2… xn xn x1 x2 x1 + x2 +…+ xn xn Bài giảng Môn học 07-09-2007 19
Mạch tổ hợp • Ví dụ 1: Dựng các mạch tạo các đầu ra sau: a) (x + y)x ; b) (x + y +z)( x y z ) Giải: a) x x+y (x + y)x y x z b) ? Bài giảng Môn học 07-09-2007 20