Đại số Boolean và cổng luận lý

Chia sẻ: Minh Thao | Ngày: | Loại File: PDF | Số trang:74

0
377
lượt xem
151
download

Đại số Boolean và cổng luận lý

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

Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 2 Cơ sở toán học cho các hệ thống số là đại số Boolean (Boolean algebra) George Boole giới thiệu vào năm 1854 Tương tự các hệ đại số khác, được xây dựng thông qua việc xác định nghĩa những vấn đề cơ bản sau: Miền (domain), là tập hợp (set) các phần tử (element) mà trên đó định nghĩa nên hệ đại số Các phép toán (operation) thực hiện được trên miền Các định đề (postulate), hay tiên đề (axiom) được công nhận không qua chứng minh Tập các hệ quả...

Chủ đề:
Lưu

Nội dung Text: Đại số Boolean và cổng luận lý

  1. Đại số Boolean và cổng luận lý Bộ môn Kỹ thuật máy tính Bùi Văn Hiếu bvhieu@cse.hcmut.edu.vn
  2. Đại số Boolean Cơ sở toán học cho các hệ thống số là đại số Boolean (Boolean algebra) George Boole giới thiệu vào năm 1854 Tương tự các hệ đại số khác, được xây dựng thông qua việc xác định nghĩa những vấn đề cơ bản sau: Miền (domain), là tập hợp (set) các phần tử (element) mà trên đó định nghĩa nên hệ đại số Các phép toán (operation) thực hiện được trên miền Các định đề (postulate), hay tiên đề (axiom) được công nhận không qua chứng minh Tập các hệ quả (set of consequences) được suy ra từ định đề, định lý (theorem), định luật (law) hay luật(rule) Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 2
  3. Định đề Huntington 1. Tính đóng (closure): tồn tại miền B với ít nhất 2 phần tử phân biệt và 2 phép toán (+) và (•) sao cho: Nếu x và y là các phần tử thuộc B thì (x + y), (x•y) cũng là 1 phần tử thuộc B Phép toán (+) được gọi là phép cộng luận lý (logical addition) Phép toán (• ) được gọi là phép nhân luận lý (logical multiplication) Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 3
  4. Định đề Huntington (tt) 2. Phần tử đồng nhất (identity elements) Nếu x là một phần tử thuộc miền B thì Tồn tại một phần tử 0 thuộc B, gọi là phần tử đồng nhất với phép toán (+ ), thỏa mãn tính chất x+0= x Tồn tại một phần tử 1 thuộc B, gọi là phần tử đồng nhất với phép toán (•), thỏa mãn tính chất x•1= x Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 4
  5. Định đề Huntington (tt) 3. Tính giao hoán (commutative law) x+y=y+x x• y=y•x 4. Tính phân phối (distributive law) x • (y + z) = (x • y) + (x • z) x + (y • z) = (x + y) • (x + z) 5. Bù (complementation) Nếu x là 1 phần tử trong miền B, tồn tại một phần tử khác gọi là x’, là phần tử bù của x thỏa mãn: x + x’ = 1 và x • x’ = 0 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 5
  6. Tính đối ngẫu (duality) Quan sát các định đề Hungtinton, ta thấy chúng mang tính đối xứng (symmetry) tức là các định đề xuất hiện theo cặp Mỗi định đề trong 1 cặp có thể được xây dựng từ định đề còn lại bằng cách Hoán đổi các phép toán 2 ngôi Hoán đổi các phần tử đồng nhất Như vậy đại số Boolean mang tính đối ngẫu Phép toán (+) và (•) đối ngẫu Phần tử đồng nhất 0 và 1 đối ngẫu Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 6
  7. Các định lý cơ bản (fundamental theorems) Các định lý được chứng minh từ các định đề Huntington và các định đề đối ngẫu theo 2 phương pháp Phương pháp phản chứng (contradiction) Giả sử kết quả đối ngược là đúng Chứng minh mâu thuẫn với sự thật Phương pháp quy nạp (induction) Chứng minh định luật đúng với trường hợp k = 1 Giả sử định luật đúng vơí trương hợp k = n Chứng minh định luật đúng với k = n +1 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 7
  8. Các định lý cơ bản (tt) Định lý 1. (Null Law) x+1=1 x• 0=0 Định lý 2. (Involution) (x’ )’ = x Định lý 3. (Idempotency) x+x =x x• x =x Định lý 4. (Absorption) x + (x • y) = x x • (x + y) = x Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 8
  9. Các định lý cơ bản (tt) Định lý 5. (Simplification) x + x’• y = x + y và x• (x’ + y) = x•y Định lý 6. (Associative Law) x + (y + z) = (x + y) + z = x + y + z x • (y • z) = (x • y) • z = x • y • z Định lý 7. (Consensus) (x • y) + (x’ • z) + (y • z) = (x • y) + (x’ • z) (x + y) • (x’ + z) • (y + z) = (x + y) • (x’ + z) Định lý 8. (De Morgan’s Law) (x + y)’ = x’ • y’ (x • y)’ = x’ + y’ Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 9
  10. Đại số chuyển mạch (switching algebra) Đối với đại số Boolean, miền không bị giới hạn (không giới hạn số lượng phần tử trong miền) Ta chỉ khảo sát đại số Boolean giới hạn 2 phần tử Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 10
  11. Đại số chuyển mạch (tt) Năm 1937, Claude Shannon hiện thực đại số Boolean 2 phần tử bằng mạch các chuyển mạch (circuit of switches) Chuyển mạch là thiết bị có 2 vị trí: tắt (off) hay mở (on) 2 vị trí này biểu diễn cho 0 hay 1 Đại số Boolean 2 phần tử được gọi là đại số chuyển mạch Các phần tử đồng nhất được gọi là các hằng chuyển mạch (switching constant) Các biến (variable) biểu diễn các hằng chuyển mạch được gọi là các biến chuyển mạch (switching variable) hay tín hiệu (signal) Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 11
  12. Các phép toán chuyển mạch Đại số chuyển mạch sử x y xy x+y x’ dụng các phép toán trong luận lý mệnh đề với tên gọi 0 0 0 0 1 khác 0 1 0 1 1 Phép toán AND: tương đương với phép nhân luận 1 0 0 1 0 lý Phép toán OR: tương 1 1 1 1 0 đương với phép cộng luận lý Bảng sự thật Phép toán NOT: tương đương với phép bù luận lý Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 12
  13. Các phép toán chuyển mạch (tt) Các phép toán chuyển mạch có thể được hiện thực bởi mạch phần cứng Bảng sự thật có thể sử dụng như 1 công cụ dùng để xác minh quan hệ giữa các phép toán chuyển mạch Vd: định lý De Morgan (x + y)’ = x’ y’ x y x’ y’ x+y (x + y)’ x’ y’ 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 13
  14. Các phép toán chuyển mạch (tt) Các phép toán chuyển mạch có thể được hiện thực bởi mạch phần cứng Bảng sự thật có thể sử dụng như 1 công cụ dùng để xác Điều gì xảy ra nếu số minh quan hệ giữa các phép toán chuyển mạch Vd: định lý De Morgan (x + y)’ = x’ y’ lượng tín hiệu là +rất(xlớn ?y’ x y x’ y’ x y + y)’ x’ 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 13
  15. Biểu thức chuyển mạch Biểu thức chuyển mạch (switching expression) là một quan hệ hữu hạn giữa các hằng, biến, và các phép toán y+1 xx’ + x z (x + y’)’ (x + yz)(x + y’) + (x + y)’ Biến hay bù của biến được gọi chung là literal Quy ước: Không cần ghi kí hiệu của phép nhân Phép nhân thực hiện trước phép cộng Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 14
  16. Biểu thức chuyển mạch Một biểu thức có thể được chuyển thành nhiều dạng tương đương bằng cách sử dụng các luật Boolean E = (x + yz)(x + y’) + (x + y)’ E1 = xx + xy’ + xyz + yy’z + x’y’ E2 = x + x(y’ + yz) + x’y’ E3 = x + x’y’ E4 = x + y’ Tại sao phải biến đổi các biểu thức ? Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 15
  17. Sự dư thừa (redundant) Một biểu thức gọi là dư thừa nếu nó có chứa Literal lặp: xx hay x+x Biến và bù của biến: xx’ hay x+x’ Hằng: 0 hay 1 Các thành phần dư thừa có thể loại bỏ khỏi biểu thức Các thành phần thừa trong biểu thức không cần hiện thực trong phần cứng Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 16
  18. Dạng chính tắc (canonic form) Một biểu thức n biến luôn có thể được biểu diễn dưới 2 dạng Dạng tổng các tích (sum-of-product hay s-o-p): biểu thức được biểu diễn dưới dạng tổng (sum) các toán hạng (term), mỗi toán hạng là tích (product) của các literal E = x y + x y’ z + x’ y z’ Dạng tích các tổng (product-of-sum hay p-o-s): biểu thức được biểu diễn dưới dạng tích các toán hạng, mỗi toán hạng là tổng của các literal E = ( x + y ) ( x + y’ + z ) ( x’ + y + z’ ) Dạng chính tắc: biểu thức n biến dạng s-o-p hay p-o-s có đặc điểm mỗi toán hạng của nó có đúng n literal và không chứa các literal thừa Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 17
  19. Minterm, Maxterm Luôn có thể biến đổi một s-o-p (hay p-o-s) không chính tắc (noncanonic) về dạng chính tắc Vd: E = xy’ + x’y + xz + yz = xy’(z + z’) + x’y(z + z’) + xz(y + y’) + yz(x + x’) = xy’z + xy’z’ + x’yz + x’yz’ + xyz + xy’z + xyz + x’yz = xy’z + xy’z’ + x’yz + x’yz’ + xyz Minterm: một tích không dư thừa các literal của dạng chính tắc Maxterm: một tổng không dư thừa các literal của dạng chính tắc Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 18
  20. Định lý De Morgan tổng quát (x1 + x2 + … + xn)’ = x1’x2’ … xn’ (x1x2 … xn)’ = x1’ + x2’ + … + xn’ E’(x1, x2, x3, ..., xn, +,•) = E(x1’, x2’, x3’, ..., xn’, •, +) Khoa Khoa học và Kỹ thuật máy tính - Bộ môn kỹ thuật máy tính 19

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản