Luật De Morgan

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ọc và logic học người Anh lớn lên 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

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

${\displaystyle (A\cap B)^{c}=A^{c}\cup B^{c}}$

${\displaystyle (A\cup B)^{c}=A^{c}\cap B^{c}}$

Trong đó, ${\displaystyle X^{c}}$ là ký hiệu của phần bù của tập X.

Ứng dụng và Hệ quả

• Định lý này được phát biểu và dùng lại trong lô gíc và đại số Boole như sau:

${\displaystyle {\overline {A.B}}={\overline {A}}+{\overline {B}}}$

${\displaystyle {\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 (${\displaystyle A.B}$) và phép nghịch đảo (${\displaystyle {\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