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

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ả. | Đạ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@ Đạ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 Đị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 Đị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 Đị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 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à .