Logical Equivalence and Negation

How to rewrite propositional statements without changing their meaning and how to negate them precisely enough to expose the exact failure case.
Modified

April 26, 2026

Keywords

logical equivalence, negation, De Morgan, implication rewrite, contradiction

1 Role

This page is the cleanup layer immediately after Propositional Logic.

It teaches how to rewrite formulas without changing their truth conditions and how to negate a statement in a way that exactly captures when the original statement fails.

2 First-Pass Promise

Read this page after Propositional Logic.

If you stop here, you should still understand:

  • what it means for two formulas to be logically equivalent
  • how to eliminate implication and biconditional when helpful
  • how De Morgan’s laws move negation inward
  • how to negate a compound claim without changing its meaning

3 Why It Matters

Many logical mistakes do not come from choosing the wrong connective. They come from rewriting or negating a statement carelessly.

That matters everywhere:

  • in proofs, a wrong negation changes the target statement
  • in verification, a wrong negation hides the actual failure case
  • in SAT and constraint systems, equivalent rewrites make formulas easier to solve
  • in theorem reading, implication and quantifier structure often become clearer after rewriting

This page is also where symbolic logic becomes more usable. Instead of staring at one rigid formula shape, you learn a small algebra of transformations that preserve meaning.

4 Prerequisite Recall

  • a propositional formula is built from atomic propositions and connectives
  • a truth assignment determines the truth value of the whole formula
  • a formula is valid when every truth assignment makes it true

5 Intuition

Logical equivalence means “different surface form, same truth behavior.”

For example, the implication

\[ p \to q \]

often feels different from

\[ \neg p \lor q, \]

but they make exactly the same truth judgments under every assignment.

Negation is the other key move. The negation of a statement is not a loose English opposite. It is the precise condition under which the original statement fails.

So the real workflow is:

understand a statement -> rewrite it into a useful form -> negate it carefully when needed

6 Formal Core

Definition 1 (Definition) Two formulas \(\varphi\) and \(\psi\) are logically equivalent if they have the same truth value under every truth assignment.

We often write this as

\[ \varphi \equiv \psi. \]

Equivalently, \(\varphi\) and \(\psi\) are logically equivalent exactly when

\[ \varphi \leftrightarrow \psi \]

is valid.

7 Key Equivalences

The following equivalences are among the most useful first ones:

\[ p \to q \equiv \neg p \lor q \]

\[ p \leftrightarrow q \equiv (p \to q) \land (q \to p) \]

\[ \neg (p \land q) \equiv \neg p \lor \neg q \]

\[ \neg (p \lor q) \equiv \neg p \land \neg q \]

\[ \neg \neg p \equiv p \]

\[ p \to q \equiv \neg q \to \neg p \]

The last line is the contrapositive equivalence.

Theorem 1 (Key Statement) To negate a compound formula correctly, keep pushing the negation inward until it lands on atomic propositions.

This works by repeated use of:

  • implication rewrite: \(p \to q \equiv \neg p \lor q\)
  • De Morgan’s laws
  • double-negation elimination

The result makes the exact failure case visible.

8 Worked Example

Suppose a safety specification says:

  1. if a request is authenticated, then access is granted
  2. if access is granted, then the audit log is updated

Let

  • \(a\): the request is authenticated
  • \(g\): access is granted
  • \(u\): the audit log is updated

Then the specification is

\[ (a \to g) \land (g \to u). \]

Rewrite each implication:

\[ (a \to g) \land (g \to u) \equiv (\neg a \lor g) \land (\neg g \lor u). \]

That is already a useful equivalent form because it removes implication.

Now negate the original specification:

\[ \neg \big((a \to g) \land (g \to u)\big). \]

Use De Morgan:

\[ \neg (a \to g) \lor \neg (g \to u). \]

Now negate each implication by first rewriting:

\[ \neg (a \to g) \equiv \neg (\neg a \lor g) \equiv a \land \neg g \]

and similarly

\[ \neg (g \to u) \equiv g \land \neg u. \]

So the full negation becomes

\[ (a \land \neg g) \lor (g \land \neg u). \]

This is much more informative than a raw outer negation. It says the specification fails exactly when either:

  • an authenticated request is denied incorrectly, or
  • access is granted without updating the audit log

That is the main payoff of careful negation: it exposes concrete failure modes.

9 Computation Lens

Equivalent rewrites are used all the time before automated reasoning starts.

Common computational moves are:

  • remove \(\to\) and \(\leftrightarrow\)
  • push negations inward
  • simplify double negations
  • rewrite formulas toward CNF-like forms for SAT or constraint solving

Even when you are not literally implementing a solver, these rewrites make formulas easier to inspect and compare.

10 Application Lens

One important application is counterexample generation in verification.

If a property is written as a logical formula, then the system fails exactly when the negation of that property is satisfiable.

So there are two linked tasks:

  • rewrite the property into an equivalent form that is easier to process
  • negate it carefully so that a satisfying assignment corresponds to a real bug or failure case

That same habit is useful in theorem reading. When a theorem says

\[ p \to q, \]

you often understand it better by thinking about the equivalent failure condition

\[ p \land \neg q. \]

11 Stop Here For First Pass

If you can now explain:

  • what logical equivalence means
  • why \(p \to q\) is equivalent to \(\neg p \lor q\)
  • how De Morgan’s laws change conjunctions and disjunctions under negation
  • how to negate a compound claim until the failure cases are explicit

then this page has done its job.

12 Go Deeper

The best next steps after this page are:

  1. Predicate Logic
  2. Contrapositive and Contradiction
  3. Proof-writing Clinic

13 Optional Paper Bridge

Optional after the first pass:

  • CMU 15-311 Logic and Mechanized Reasoning - look for how propositional rewrites and negation become part of automated reasoning and proof search. Checked 2026-04-24.
  • CMU OLI Logic & Proofs - use the sentential-logic sections to practice equivalence and negation as systematic procedures rather than guesswork. Checked 2026-04-24.

14 Optional After First Pass

If you want more depth before Predicate Logic lands: - continue to Predicate Logic - revisit Propositional Logic and restate each validity example using equivalent formulas - revisit Statements and Quantifiers and compare propositional negation with theorem-statement negation

15 Common Mistakes

  • negating \(p \land q\) as \(\neg p \land \neg q\) instead of \(\neg p \lor \neg q\)
  • negating \(p \lor q\) as \(\neg p \lor \neg q\) instead of \(\neg p \land \neg q\)
  • forgetting that the negation of \(p \to q\) is \(p \land \neg q\)
  • confusing the biconditional formula \(p \leftrightarrow q\) with the broader notion of logical equivalence
  • rewriting a formula into a shape that looks similar but does not preserve truth values

16 Exercises

  1. Rewrite each formula without implication:
    • \(p \to q\)
    • \((p \land q) \to r\)
    • \(p \leftrightarrow q\)
  2. Negate each formula and simplify until negations land on atomic propositions:
    • \(\neg (p \lor q)\)
    • \(\neg (p \to q)\)
    • \(\neg \big((p \to q) \land (q \to r)\big)\)
  3. Show that \(p \to q\) and \(\neg q \to \neg p\) are logically equivalent by reasoning from truth values or by using known equivalence laws.

17 Sources and Further Reading

Back to top