Ủng hộ tôi
Đại số Boolean là một cấu trúc đại số liên quan đến việc thao tác với các biến luận lý nhị phân. Một biến luận lý nhị phân có thể mang 2 giá trị: 0 và 1, cao và thấp, đúng và sai, … Trong môn học này chúng ta sẽ sử dụng cặp giá trị 0 và 1 để tìm hiểu về đại số Boolean.
Đại số Boolean thao tác với các biến luận lý thông qua các thao tác luận lý. Các thao tác luận lý cơ bản là AND, OR, NOT. Trong môn học này, phép toán AND được quy ước là dấu ∙, phép toán OR được quy ước và dấu + và phép toán NOT được quy ước là dấu '.
Đại số Boolean được định nghĩa như sau: Một tập B khác rỗng cùng với các thao tác (phép toán) AND (∙), OR (+) và NOT (') được gọi là một đại số Boolean nếu các tiên đề sau đây được thỏa mãn với mọi x, y, z B.
Tiên đề 1: Cấu trúc đóng với các phép toán ∙ và +. Nếu x, y B thì:
a) (x + y) ∈ B
b) x ∙ y ∈ B
Tiên đề 2: Tồn tại phần tử trung hòa. Tồn tại 2 phần tử trung hòa khác nhau thuộc B, ký hiệu là 0 và 1 sao cho:
a) x ∙ 1 = 1 ∙ x = x
b) x + 0 = 0 + x = x
Tiên đề 3: Tính giao hoán
a) x ∙ y = y ∙ x
b) x + y = y + x
Tiên đề 4: Tính phân phối
a) x ∙ (y + z) = x ∙ y + x ∙ z
b) x + y ∙ z = (x + y)(x + z)
Tiên đề 5: Tồn tại phần tử bù. Với mọi x B, tồn tại duy nhất B sao cho:
a) x ∙ x' = x' ∙ x = 0
b) x + x' = x' + x = 1
với x' được gọi là phần tử bù của x.
Tiên đề 6: Tồn tại ít nhất 2 phần tử x, y ∈ B sao cho x ≠ y.
Từ các tiên đề vừa đề cập ở trên, chúng ta cũng có thể suy ra một số định lý để thuận tiện cho việc sử dụng sau này:
Định lý 1: Tính lũy đẳng
a) x + x = x
b) x ∙ x = x
Định lý 2: Tính nuốt
a) x + 1 = 1
b) x ∙ 0 = 0
Định lý 3: Tính hấp thụ
a) x + x ∙ y = x
b) x(x + y) = x
Định lý 4: Tính phủ định của phủ định: (x')' = x
Định lý 5: Tính kết hợp
a) x + (y + z) = (x + y) + z
b) x(y ∙ z) = (x ∙ y)z
Định lý 6: Định lý De-Morgan
a) (x + y)' = x' ∙ y'
b) (xy)' = x' + y'
Xem bài giảng chi tiết về Đại số Boolean tại video: https://youtu.be/CmCv6_OZbkk
Việc kết hợp các biến luận lý, các hằng số luận lý, các toán tử luận lý và các dấu ngoặc đơn sẽ cho chúng ta được một biểu thức Boolean. Trong một biểu thức Boolean thì thứ tự tính toán sẽ tính từ trái sang phải, biểu thức trong ngoặc đơn được tính trước, phép toán NOT được ưu tiên tiếp theo, sau đó là phép toán AND và cuối cùng là phép toán OR có độ ưu tiên thấp nhất. Việc kết hợp theo thứ tự: 1 tên hàm, 1 dấu bằng và cuối cùng là 1 biểu thức Boolean sẽ cho chúng ta được một hàm Boolean.
Tối ưu luận lý là việc sử dụng các tiên đề hoặc các định lý của đại số Boolean để làm giảm số lượng tổng/tích hoặc số lượng biến hoặc phần bù của nó trong mỗi tổng/tích trong một biểu thức của hàm Boolean mà không làm thay đổi giá trị của hàm Boolean đó.
Các tiên đề và định lý đóng vai trò quan trọng trong việc tối ưu luận lý bao gồm:
Tiên đề 2: Tồn tại phần tử trung hòa.
Tiên đề 5: Tồn tại phần tử bù.
Định lý 1: Tính lũy đẳng
Định lý 2: Tính nuốt.
Định lý 3: Tính hấp thụ.
Xem bài giảng chi tiết về Tối ưu Luận lý bằng phương pháp đại số tại video: https://youtu.be/5TvLh_u6V-I