De Morgan's laws

De Morgan's laws

De Morgan's laws describe the interaction between negation, conjunction, and disjunction. They provide rules for transforming logical statements into equivalent forms.

Statements

• ¬(p ∧ q) ≡ ¬p ∨ ¬q
• ¬(p ∨ q) ≡ ¬p ∧ ¬q

Explanation

Negating a conjunction is equivalent to the disjunction of the negations. Negating a disjunction is equivalent to the conjunction of the negations. These transformations are widely used in proofs, algebraic simplifications, and computer science.

Examples

• "It is not the case that (I study AND I work)"

 ≡ "I do not study OR I do not work".  

• "It is not the case that (I travel OR I rest)"

 ≡ "I do not travel AND I do not rest".

Truth Table (First Law)

p	q	p ∧ q	¬(p ∧ q)	¬p ∨ ¬q
T	T	T	F	F
T	F	F	T	T
F	T	F	T	T
F	F	F	T	T

Truth Table (Second Law)

p	q	p ∨ q	¬(p ∨ q)	¬p ∧ ¬q
T	T	T	F	F
T	F	T	F	F
F	T	T	F	F
F	F	F	T	T