// laws and rules · Logical equivalence
De Morgan's law (conjunction)_
The first De Morgan law states that negating “p and q” is the same as asserting “not p or not q”. Formally, ¬(p ∧ q) ⇔ (¬p ∨ ¬q) is a tautology: both columns agree in all four rows. It is one of the most used equivalences for simplifying logical expressions and conditions in code.
Example
¬(p ∧ q) ⇔ (¬p ∨ ¬q)
What the variables mean
- ▸ p: “The user is registered”
- ▸ q: “The user has credit”
In plain words
“It is not the case that the user is registered and has credit” means exactly “the user is not registered or has no credit”.
Truth table
| p | q | p ∧ q | ¬(p ∧ q) | ¬p | ¬q | ¬p ∨ ¬q | ¬(p ∧ q) ⇔ (¬p ∨ ¬q)★ |
|---|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F | T |
| T | F | F | T | F | T | T | T |
| F | T | F | T | T | F | T | T |
| F | F | F | T | T | T | T | T |
Classification: Tautology · 4 rows
Statement
¬(p ∧ q) ⇔ (¬p ∨ ¬q). When the negation is “pushed” inside the parentheses, the conjunction turns into a disjunction and each part is negated.
Together with the second law, ¬(p ∨ q) ⇔ (¬p ∧ ¬q), it forms the pair of De Morgan laws, named after the 19th-century mathematician Augustus De Morgan, although medieval logicians already knew them.
Why it is a tautology: reading the table
Row p = T, q = T: p ∧ q is T, its negation F; ¬p and ¬q are F, and F ∨ F is F. They agree. Row p = T, q = F: p ∧ q is F, its negation T; ¬q is T so ¬p ∨ ¬q is T. They agree.
Rows p = F, q = T and p = F, q = F work the same way: the conjunction is F, its negation T, and since ¬p is T the disjunction is T too. Because the two columns are identical, the biconditional is T in every row.
How it is used in proofs
It pushes negations down to the variables, which is the first step in converting any formula to normal form (conjunctive or disjunctive).
In proofs by contradiction, negating a hypothesis built with ∧ immediately yields a disjunction of cases to analyse.
Examples
Programming: `!(a && b)` is equivalent to `!a || !b`. Rewriting `if (!(age >= 18 && hasLicense))` as `if (age < 18 || !hasLicense)` usually makes code more readable.
SQL: `NOT (active = 1 AND country = 'US')` can be written as `active <> 1 OR country <> 'US'`.
Everyday: “It is not true that it rained and it was cold” means “it did not rain or it was not cold”.
Relation to other laws
Its sister law swaps the roles: ¬(p ∨ q) ⇔ (¬p ∧ ¬q). Both generalise to any number of variables and to quantifiers (¬∀ is equivalent to ∃¬).
It defines how NAND relates to the basic operations: p ⊼ q is ¬(p ∧ q), which by De Morgan equals ¬p ∨ ¬q.
Try it yourself
Edit the expression in the calculator and watch how every step of the table changes.
Open in the calculator →Related operators
Frequently asked questions
How many De Morgan laws are there? ▼
Two in propositional logic: one for the negation of a conjunction and one for the negation of a disjunction. They also extend to sets and quantifiers.
Why is the result a tautology when the operators differ? ▼
Because the two expressions the biconditional compares have exactly the same values in every row; ⇔ is T whenever both sides agree.
Does it work for more than two variables? ▼
Yes: ¬(p ∧ q ∧ r) is equivalent to ¬p ∨ ¬q ∨ ¬r, and in general the negation of an n-term conjunction is the disjunction of its n negations.