intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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

170
lượt xem
19
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ủ đề:
Lưu

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

  1. Chương 6: Đại số Boole Bài giảng Môn học 07-09-2007 1
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. Đị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
  11. Đị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
  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ụ: 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2