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.

The rules can be expressed in English as:

• The negation of a disjunction is the conjunction of the negations
• The negation of a conjunction is the disjunction of the negations

or

• The complement of the union of two sets is the same as the intersection of their complements
• The complement of the intersection of two sets is the same as the union of their complements

or

• not (A or B) = (not A) and (not B)
• not (A and B) = (not A) or (not B)

where "A or B" is an "inclusive or" meaning at least one of A or B rather than an "exclusive or" that means exactly one of A or B.

In set theory and Boolean algebra, these are written formally as

${\displaystyle {\begin{aligned}{\overline {A\cup B}}&={\overline {A}}\cap {\overline {B}},\\{\overline {A\cap B}}&={\overline {A}}\cup {\overline {B}},\end{aligned}}}$

where

• ${\displaystyle A}$ and ${\displaystyle B}$ are sets,
• ${\displaystyle {\overline {A}}}$ is the complement of ${\displaystyle A}$,
• ${\displaystyle \cap }$ is the intersection, and
• ${\displaystyle \cup }$ is the union.

In formal language, the rules are written as

${\displaystyle \neg (P\lor Q)\iff (\neg P)\land (\neg Q),}$

and

${\displaystyle \neg (P\land Q)\iff (\neg P)\lor (\neg Q)}$

where

• P and Q are propositions,
• ${\displaystyle \neg }$ is the negation logic operator (NOT),
• ${\displaystyle \land }$ is the conjunction logic operator (AND),
• ${\displaystyle \lor }$ is the disjunction logic operator (OR),
• ${\displaystyle \iff }$ is a metalogical symbol meaning "can be replaced in a logical proof with".

 

Ký hiệu toán học

Ký hiệu	Tên ký hiệu	Ý nghĩa	Ví dụ
⋅	và	và	x . y
^	dấu mũ / dấu mũ	và	x ^ y
&	dấu và	và	x & y
+	thêm	hoặc	x + y
∨	dấu mũ đảo ngược	hoặc	x ∨ y
|	đường thẳng đứng	hoặc	x | y
x '	trích dẫn duy nhất	không - phủ định	x '
$\bar{x}$	quầy bar	không - phủ định	$\bar{x}$
¬	không	không - phủ định	¬ x
!	dấu chấm than	không - phủ định	! x
⊕	khoanh tròn dấu cộng / oplus	độc quyền hoặc - xor	x ⊕ y
~	dấu ngã	phủ định	~ x
⇒	ngụ ý
⇔	tương đương	khi và chỉ khi (iff)
↔	tương đương	khi và chỉ khi (iff)
∀	cho tất cả
∃	có tồn tại
∄	không tồn tại
∴	vì thế
∵	bởi vì / kể từ