Laws of Logical Equivalence
Can you rewrite without a negation outside a parenthesis? Every student of proof-writing eventually meets a tangled compound statement. Checking its truth table by hand becomes impractical. Yet a proof's correctness may hinge on knowing two statements say the same thing. The laws of logical equivalence are a toolkit that answers this question algebraically. They work the way arithmetic rules let you rewrite as . You don't need to re-derive multiplication from scratch each time. These laws matter because Logical Equivalence itself is defined by an expensive test. It requires a truth table with rows for atomic statements. The laws let you transform statements symbolically in a fixed number of steps instead. This mirrors how a proof actually proceeds line by line. They let a mathematician say "negating 'every satisfies or ' gives 'some fails both and '" directly. There's no need to re-derive that fact from first principles each time. The big picture: propositional logic, under logical equivalence, behaves like an algebraic structure. Technically, it forms a Boolean algebra. Its operations play roles analogous to multiplication, addition, and sign-change in ordinary algebra. They are commutative, associative, distributive, and have identity elements. But they also have extra symmetry laws, such as De Morgan's laws, with no numerical analogue. This article develops that algebra rigorously. It states each law precisely. It proves the whole family from the definition of equivalence via one unifying argument. It also shows how to chain the laws together to simplify or negate complicated statements. By the end you will have a proved, named list of equivalences. These include commutativity, associativity, distributivity, identity/domination, double negation, idempotence, and De Morgan's laws. You will also see a worked derivation showing how these laws compose to negate a genuinely nested statement. There is a discussion of exactly which hypotheses are needed. Finally, there are pointers toward how these same laws resurface when Negating Quantified Statements.
- Logical equivalence () behaves algebraically: and obey commutative, associative, and mutual distributive laws.
- Identity laws (, ) and domination laws (, ) pin down the role of the constants True/False.
- De Morgan's laws convert a negated conjunction/disjunction into a disjunction/conjunction of negations: .
- Double negation () and idempotence () let you cancel redundancy.
- All these laws are proved uniformly by exhibiting identical truth tables — no law needs a separate ad hoc argument.
- Key idea: logical equivalence laws let you rewrite compound statements step-by-step, the same way algebraic identities let you rewrite expressions, and every step is justified by a truth-table fact proved once and for all.
Where this lives today
In pure mathematics, these laws are the daily grammar of proof-writing: negating a hypothesis correctly (via De Morgan's laws) is the first step in almost every proof by contradiction or contrapositive, and distributivity underlies manipulations of set operations, since is the set-theoretic mirror of the propositional distributive law, with playing the roles of . In <a class="wiki-link" href="/wiki/math-found-negating-quantified-statements" data-track="wiki_article.body.wiki_link">Negating Quantified Statements</a>, the same De Morgan pattern reappears one level up: negating gives and negating gives , a direct quantifier analogue of the propositional De Morgan laws proved here, since a universally quantified statement behaves like an (infinite) conjunction and an existential one like an (infinite) disjunction. In computer science and digital circuit design, De Morgan's laws let engineers convert AND-gates into OR-gates (with inverters), which is essential when a chip fabrication process makes one gate type cheaper or faster than another; compilers and hardware synthesis tools apply these laws automatically to optimize boolean expressions in code and circuits. In automated theorem proving and SAT solving, converting formulas to conjunctive or disjunctive normal form relies on repeated application of exactly these laws (distributivity to expand, De Morgan's laws to push negations to the leaves). In database query optimization, De Morgan's and distributive laws rewrite filter conditions (`WHERE NOT (a AND b)` becomes `WHERE NOT a OR NOT b`) into forms an optimizer can index more efficiently. In statistics and probability, De Morgan's laws applied to events justify , a step used constantly when computing probabilities of "at least one failure" type events.
Ask the tutor: Can you show me step by step how to use these laws to negate ?
Let denote statement forms built from atomic statements using (and, later, , which are themselves shorthand for combinations of these three). Two statement forms and are logically equivalent, written
if and have identical truth values under every assignment of truth values to their atomic components — equivalently, if the biconditional is a tautology. A law of logical equivalence is a schema that holds for all statement forms obtained by substituting arbitrary statement forms for the letters involved. The laws treated here are, for arbitrary statement forms :
Commutative laws
Associative laws
Distributive laws
Identity and domination laws (writing for a fixed tautology and for a fixed contradiction)
Idempotent laws
Double negation law
De Morgan's laws
Intuition
Think of as behaving like multiplication and like addition on the two-element set , where acts like the number (identity for , absorbing for ) and acts like (identity for , absorbing for ). Under this analogy, commutativity and associativity are unsurprising — order and grouping should not matter for "and" or "or" any more than for ordinary addition. What is more striking is that both distributive laws hold: not only does distribute over (matching multiplication distributing over addition), but also distributes over , which has no counterpart in ordinary arithmetic ( in general). This extra symmetry is a hallmark of Boolean algebra and is exactly what makes De Morgan's laws possible: negation swaps the roles of and entirely, turning every "and" into an "or" and vice versa, while flipping every atomic truth value. De Morgan's laws are best pictured as duality: negating a compound statement pushes the inward, flips , and lands a on each atomic piece. The diagram below shows this "push-through" action on , and a second figure shows the algebraic structure — the constants sitting like at the ends of a truth-value line, with as the two binary operations connecting them.
Theorem
Let be arbitrary statement forms, let denote a fixed tautology, and let denote a fixed contradiction. Then all of the following equivalences hold, where each is understood as holding for every assignment of truth values to the atomic statements comprising : 1. Commutativity: and . 2. Associativity: and . 3. Distributivity: and . 4. Identity/domination: , , , . 5. Idempotence: and . 6. Double negation: . 7. De Morgan's laws: and .
The proof technique throughout is the truth table method: to show for statement forms built from atomic statements , it suffices by the definition of logical equivalence to check that and receive the same truth value under every one of the finitely many assignments of to . Since range over arbitrary statement forms, and the only facts used in each check are the defining truth tables of (which depend only on the truth values of their arguments, not on their internal structure), verifying the equivalence for atomic letters ranging over establishes it for arbitrary statement forms substituted in their place. This is because the truth value of a compound statement is a function only of the truth values of its immediate constituents (the truth-functionality of ), so substituting an arbitrary statement form for the letter everywhere changes no comparison being made: wherever evaluates to , the table row for "" applies, and likewise for . We now verify each law.
(1) Commutativity. The defining truth tables of and are symmetric in their two arguments:
| T | T | T | T | T | T |
| T | F | F | F | T | T |
| F | T | F | F | T | T |
| F | F | F | F | F | F |
Columns and agree in every row, and likewise and agree in every row. By the truth table method this proves both commutative laws.
(2) Associativity. There are assignments to . We tabulate against :
| T | T | T | T | T | T | T |
| T | T | F | T | F | F | F |
| T | F | T | F | F | F | F |
| T | F | F | F | F | F | F |
| F | T | T | F | F | T | F |
| F | T | F | F | F | F | F |
| F | F | T | F | F | F | F |
| F | F | F | F | F | F | F |
The two rightmost relevant columns, and , agree in all rows (each is exactly when , and otherwise), so . An entirely parallel table — each is exactly when at least one of is — shows . (This is unsurprising: is exactly when all three atoms are , and is exactly when at least one is; parenthesization cannot change which set of assignments makes the string true, only the order of evaluation, and by the two tables above that set is unaffected.)
(3) Distributivity. We check over all assignments:
| T | T | T | T | T | T | T | T |
| T | T | F | T | T | T | F | T |
| T | F | T | T | T | F | T | T |
| T | F | F | F | F | F | F | F |
| F | T | T | T | F | F | F | F |
| F | T | F | T | F | F | F | F |
| F | F | T | T | F | F | F | F |
| F | F | F | F | F | F | F | F |
The columns and agree in every row, proving the first distributive law. For the second, :
| T | T | T | T | T | T | T | T |
| T | T | F | F | T | T | T | T |
| T | F | T | F | T | T | T | T |
| T | F | F | F | T | T | T | T |
| F | T | T | T | T | T | T | T |
| F | T | F | F | F | T | F | F |
| F | F | T | F | F | F | T | F |
| F | F | F | F | F | F | F | F |
Again both columns agree in every row, proving the second distributive law.
(4) Identity and domination. Each has a two-row table (only varies, with constant):
| T | T | T | T | T | T | T | F | F |
| F | F | F | F | F | T | T | F | F |
Each pair of adjacent relevant columns agrees in both rows, so , , , .
(5) Idempotence. By definition of , is exactly when is (taking both arguments to be requires both to be , i.e. to be ), and is exactly when is ; hence and agree in both rows of a two-row table. Symmetrically is exactly when is , matching in both rows. This proves both idempotent laws.
(6) Double negation. By the defining table of , is when is and when is ; applying again, is when is , i.e. when is , and is when is , i.e. when is . So and agree in both rows: .
(7) De Morgan's laws. We check over all four assignments to :
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |
The columns and agree in all four rows, proving the first De Morgan law. For :
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
Again both columns agree in all four rows, proving the second De Morgan law. All seven families of laws have now been verified by exhaustive truth table comparison, which — by the truth-functionality argument given at the start of the proof — establishes each as holding for arbitrary statement forms , not merely for atomic letters.
∎If is an instance of one of the laws above (with arbitrary statement forms substituted for ), and occurs as a subformula of a larger statement form , then replacing that occurrence of by produces a statement form with .
This is the substitution principle for logical equivalence, proved by induction on the structure of . If itself, then and is exactly the hypothesis. Otherwise is , , or for shorter statement forms in which occurs as a subformula of one of them (say , or without loss of generality); by the inductive hypothesis, replacing by inside (or ) yields (or ) with (or ). Since truth value is determined functionally by the truth values of immediate constituents, and , agree on every assignment (by ), the compounds and also agree on every assignment, so ; similarly and . In each case . This closes the induction.
∎This corollary is what licenses "chaining" the laws: once is known, you may replace by anywhere it sits inside a larger statement without changing the larger statement's equivalence class, exactly as you replace by inside a larger arithmetic expression.
Worked examples
Example 1 — negating a genuinely nested statement. Simplify into a form with no negation applied to anything but an atomic letter. Step 1 (outer De Morgan, first law): treat , ; then
Step 2 (inner De Morgan, second law) applied to the subformula , licensed by the substitution principle:
Step 3 (double negation) applied to the subformula :
Chaining steps 1–3 via the substitution principle,
Check by direct truth table (all rows), to confirm no error crept in:
| T | T | T | F | T | T | F | F | F | F |
| T | T | F | T | T | T | F | F | F | F |
| T | F | T | F | F | F | T | F | T | T |
| T | F | F | T | T | T | F | F | F | F |
| F | T | T | F | T | F | T | T | F | T |
| F | T | F | T | T | F | T | T | F | T |
| F | F | T | F | F | F | T | T | T | T |
| F | F | F | T | T | F | T | T | F | T |
The columns "" and "" agree in all rows, confirming the simplification.
Example 2 — proving an equivalence between two visibly different statements, using the laws instead of a raw truth table. Show
using the laws of logical equivalence (not a fresh truth table from scratch). Step 1 (second distributive law, with the roles , , ):
Step 2: the subformula is a contradiction — it is under both truth values of (if then so ; if then directly), so by the truth-table method (a two-row check). This is sometimes called the negation law and follows the same proof pattern used throughout the theorem above. Step 3 (substitute for , via the substitution principle):
Step 4 (identity law): . Chaining steps 1–4:
This derivation used only the theorem's laws (distributivity, identity) plus one auxiliary two-row fact (the negation law ), illustrating how the laws let you avoid an -row truth table entirely — a genuine efficiency gain that becomes dramatic as the number of atomic letters grows.
The proof of every law in the theorem rested on the fact that the truth value of , , is determined entirely by the truth values of and — never by their internal structure or by anything outside the truth-value framework. Drop this hypothesis and the laws can fail. Consider replacing by a non-truth-functional binary connective meant to informally capture " and, because of, " — i.e. is intended to be true only when and are both true and is a genuine reason for . Let
Suppose in the actual world both and are true (it rained and the sprinkler ran), and is true because it rained (not because of the sprinkler). Then informally is true (rain genuinely explains the wet ground) while is false (the sprinkler running is not, in this scenario, why the ground is wet), even though and have the same truth value . So substituting for — an operation the truth-table method treats as harmless whenever and agree in truth value — changes the truth value of the compound. Consequently the entire machinery of the theorem's proof breaks down for : two connectives can be true/false-equivalent on their inputs without the compounds built from them agreeing, so commutativity, associativity, and De Morgan-style laws for cannot be established (and generally fail) by the truth table method, and indeed need not hold at all. This shows the hypothesis of truth-functionality — built into the very definition of as connectives whose output depends only on input truth values — is not a minor technicality but the load-bearing assumption that makes "check finitely many rows" a valid proof rather than a coincidence. Ordinary satisfy it by definition, which is exactly why the theorem's laws are laws and not merely typical patterns.
Scope, edge cases & common traps
| Situation | What holds | What to watch for |
|---|---|---|
| Substituting equivalent statement forms into a law | Substitution principle (corollary) applies validly | Must substitute the whole statement form consistently, not just one occurrence |
| Mixing and into these laws | Fine, once is rewritten as | Applying De Morgan's laws directly to without first rewriting it is a common error |
| Negating a chain of three or more connectives | Apply De Morgan's law innermost-out or outermost-in, one connective at a time | Trying to negate "all at once" often drops a on an inner atomic letter |
| Distributivity of over | Genuinely holds (unlike ordinary arithmetic) | Students often assume it fails "by analogy" with — it does not fail here |
| Treating like between numbers | Valid — is an equivalence relation (reflexive, symmetric, transitive) | Still must justify each rewriting step by a named law, exactly as with algebraic identities |
The mathematician behind it
Origins · 1 minAugustus De Morgan and how this was discovered
De Morgan was one of the founders of modern symbolic logic, working alongside George Boole to move logic away from purely verbal syllogistic reasoning and toward an algebraic calculus of propositions and relations. He is best remembered today for the two duality laws bearing his name, which he stated in the context of both propositional logic and the algebra of sets, recognizing the same pattern in both settings — an early instance of the abstraction that later crystallized as Boolean algebra.
Are the laws of logical equivalence the same as logical implication?
No. Logical equivalence means and have identical truth values on every assignment — a two-way relationship — whereas implication only requires to be a tautology, a one-way relationship where need not force back. Every law in this article states a genuine equivalence: for instance means each side implies the other. It would be a strictly weaker (and different) claim to say only " implies " (true, but so is the converse, which is the extra content of ). Confusing with a one-directional implication is a common source of errors when applying these laws inside a longer proof, since you can substitute equivalents in either direction but can only substitute implications in one.
Do these laws also hold for the connectives and ?
Indirectly, yes, once you rewrite and in terms of . Since and , any manipulation of or can be carried out by first substituting these equivalent forms and then applying the laws stated in this article. There is no need for separate "commutative law for " (indeed is not equivalent to in general, so no such commutative law could hold) — the laws here are specifically about , the connectives for which the symmetric algebraic structure actually exists.
Why do both distributive laws hold, when in ordinary arithmetic only one distributive law (multiplication over addition) holds?
This reflects a genuine structural difference between Boolean algebra and the arithmetic of real numbers: in with , both operations happen to distribute over each other, a symmetry that has no counterpart in a ring like , where in general (e.g. but ). The theorem's proof verifies this directly by exhaustive truth table check on both distributive laws, so it is not an analogy or approximation — both really do hold as stated, for all statement forms .
Can I use these laws to prove that two statements are not equivalent?
Not directly — the laws only give you positive rewriting steps to show two forms are equivalent. To show non-equivalence, the standard technique is to exhibit a single row of the truth table (a single assignment of truth values to the atomic letters) where the two statement forms disagree; this is enough because logical equivalence requires agreement on every row, so one disagreeing row suffices to refute it. The Logical Equivalence article's exhaustive truth table method is exactly the right tool for disproving equivalence, while the laws in this article are the right tool for proving it once you suspect it holds.
Is there a way to remember which De Morgan law goes with which connective?
Picture the mnemonic "break the line, flip the sign": to negate or , distribute the onto each letter (put a on and on separately) and simultaneously flip the connective between them ( becomes , or becomes ). This is visualized in this article's first figure, showing transforming into by pushing the negation through and flipping the connective. The same "flip the connective" pattern reappears with quantifiers in Negating Quantified Statements, where and swap roles under negation exactly as and do here.
Why are identity, domination, and idempotent laws sometimes omitted from a short list of "the" laws of logical equivalence?
Different textbooks draw the boundary of "the core laws" differently, but identity (), domination (), and idempotent laws () are genuine, independently provable equivalences, each verifiable by the same truth table method used for commutativity or De Morgan's laws. They are sometimes treated as "obvious" corollaries rather than headline laws because their truth tables have only one or two rows, but logically they carry exactly the same status as the more celebrated laws: each is a tautological biconditional, proved the same way, and each is genuinely useful — for instance the identity law was used explicitly in Worked Example 2 above to finish simplifying down to .
Do these laws generalize beyond two-valued (classical) logic?
Within classical (two-valued) logic — the setting of this article and of Logical Equivalence as defined here — all seven law families hold exactly as stated, proved by the finite truth-table method. In other logical systems (e.g. three-valued logics, intuitionistic logic), some of these laws can fail or require reformulation; double negation elimination (), for instance, is famously not valid in intuitionistic logic, which restricts what counts as a constructive proof. Those systems are beyond the classical propositional setting developed here, but it is worth knowing that "law of logical equivalence" is not an absolute metaphysical fact — it is a theorem relative to the classical two-valued truth table semantics fixed in the definition above.