Luật De Morgan

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Luật De Morgan, hay còn gọi là định lý De Morgan, được phát biểu và chứng minh bởi nhà toán họclô gíc học người Anh sinh trưởng tại Ấn Độ tên là Augustus De Morgan (1806-1871). Nguyên thủy, định lý này được chứng minh trong lý thuyết tập họp.

Phát biểu[sửa | sửa mã nguồn]

Cho A và B là hai tập họp bất kì thì

(A \cap B)^c = A^c \cup B^c
(A \cup B)^c = A^c \cap B^c

Trong đó, X^c là kí hiệu của phần bù của tập X.

Ứng dụng và Hệ quả[sửa | sửa mã nguồn]

  • Định lý này được phát biểu và dùng lại trong lô gíc và đại số Bool như sau:
\overline{A.B} = \overline{A} + \overline{B}
\overline{A+B} = \overline{A}. \overline{B}

Từ hai mệnh đề trên cùng với bảng chân trị của phép hội (A.B) và phép nghịch đảo (\overline{A}) người ta có thể chứng minh rằng mọi mệnh đề lô gíc đều có thể được biểu diễn bằng một mệnh đề mà chỉ bao gồm hai phép toán hội và phép nghịch đảo.

  • Định lý De Morgan là tiền đề cơ bản cho sự phát triển của ngành máy tính vì chỉ cần có hai cổng điện toán - cổng đảo dấu (NOT gate) và cổng và (AND gate) chẳng hạn - thì người ta có thể thiết lập nên bất kì một phép toán lô gíc nào bằng tổ hợp của hai cổng điện toán trên.

Tham khảo[sửa | sửa mã nguồn]