Logical equivalence calculator
Type two statements from propositional logic and get a proof that they are equivalent, one law per line, the way a discrete maths course writes it. If they are not equivalent you get a counterexample. Leave the second field empty to simplify a statement or test whether it is a tautology.
¬ ~ ! not, ∧ & ^ and, ∨ | v or, → -> if-then, ↔ <-> iff if and only if, ⊕ xor, ⊤ ⊥ true and false.
- 1 ¬(p → q) Given
- 2 ≡ ¬(¬p ∨ q) Conditional law p → q ≡ ¬p ∨ q (material implication), applied to p → q
- 3 ≡ p ∧ ¬q De Morgan's law negating a disjunction flips it to a conjunction and negates each term
How to prove two statements are equivalent
Two statements are logically equivalent when they are true in exactly the same cases. There are two standard ways to show it.
By truth table
List every combination of true and false for the letters, work out both statements in each row, and compare the two columns. If they match in every row the statements are equivalent; one row where they differ shows they are not. It always works, but it grows fast: 2n rows for n letters.
By laws
Start from one statement and rewrite it, one known equivalence at a time, until it becomes the other. Name the law on every line. The usual order is to remove → and ↔ first, push negations inwards with De Morgan's laws, then simplify with the remaining laws.
This calculator does both. It decides the question by truth table, so the verdict is never wrong, then looks for a chain of laws. It simplifies both statements, and where the two workings reach the same statement it joins them, reading the right-hand working backwards. Every law holds in both directions, so that is still a valid proof.
A worked example
Show that (p ∧ q) → (p ∨ q) is a tautology, that is, equivalent to ⊤:
- 1 p ∧ q → p ∨ q Given
- 2 ≡ ¬(p ∧ q) ∨ (p ∨ q) Conditional law p → q ≡ ¬p ∨ q (material implication), applied to p ∧ q → p ∨ q
- 3 ≡ ¬p ∨ ¬q ∨ p ∨ q De Morgan's law negating a conjunction flips it to a disjunction and negates each term
- 4 ≡ ⊤ Negation law one of ¬p and p is always true, so the disjunction is ⊤
The conditional law removes the arrow, De Morgan's law pushes the negation inside the brackets, and then a letter sits next to its own negation in one big disjunction. One of the two is always true, so the whole disjunction is ⊤. The statement is therefore true in every case.
A second one, found in many textbooks: ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q (try it above). The calculator proves it in 2 steps. Textbooks usually take longer, with De Morgan's law, the distributive law, the negation law and the identity law. The redundancy law, p ∨ (¬p ∧ q) ≡ p ∨ q, packs those steps into one; both routes are valid proofs.
Laws the calculator uses
The laws used in proofs, each written as a pair of equivalent statements. Every row was checked by truth table when this page was built; a tick means the two sides agree in every row. For each law explained with its own truth table proof, see the table of logical equivalences.
Laws for ¬, ∧, ∨ and ⊕
| Law | Equivalence | Checked by truth table |
|---|---|---|
| Identity laws | p ∧ ⊤ ≡ p | ✓ |
| p ∨ ⊥ ≡ p | ✓ | |
| Domination laws | p ∨ ⊤ ≡ ⊤ | ✓ |
| p ∧ ⊥ ≡ ⊥ | ✓ | |
| Idempotent laws | p ∨ p ≡ p | ✓ |
| p ∧ p ≡ p | ✓ | |
| Double negation law | ¬¬p ≡ p | ✓ |
| Commutative laws | p ∨ q ≡ q ∨ p | ✓ |
| p ∧ q ≡ q ∧ p | ✓ | |
| Associative laws | (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) | ✓ |
| (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) | ✓ | |
| Distributive laws | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) | ✓ |
| p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) | ✓ | |
| De Morgan's laws | ¬(p ∧ q) ≡ ¬p ∨ ¬q | ✓ |
| ¬(p ∨ q) ≡ ¬p ∧ ¬q | ✓ | |
| Absorption laws | p ∨ (p ∧ q) ≡ p | ✓ |
| p ∧ (p ∨ q) ≡ p | ✓ | |
| Negation laws | p ∨ ¬p ≡ ⊤ | ✓ |
| p ∧ ¬p ≡ ⊥ | ✓ | |
| Definition of ⊕ | p ⊕ q ≡ (p ∧ ¬q) ∨ (¬p ∧ q) | ✓ |
Laws for → and ↔
| Law | Equivalence | Checked by truth table |
|---|---|---|
| Conditional law | p → q ≡ ¬p ∨ q | ✓ |
| Contrapositive | p → q ≡ ¬q → ¬p | ✓ |
| Disjunction as conditional | p ∨ q ≡ ¬p → q | ✓ |
| Negated conditional | ¬(p → q) ≡ p ∧ ¬q | ✓ |
| Exportation | (p ∧ q) → r ≡ p → (q → r) | ✓ |
| Common consequent | (p → r) ∧ (q → r) ≡ (p ∨ q) → r | ✓ |
| Common antecedent | (p → q) ∧ (p → r) ≡ p → (q ∧ r) | ✓ |
| Biconditional law | p ↔ q ≡ (p → q) ∧ (q → p) | ✓ |
| Biconditional as cases | p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q) | ✓ |
| Negated biconditional | ¬(p ↔ q) ≡ p ↔ ¬q | ✓ |
The conditional law, p → q ≡ ¬p ∨ q, is also called material implication. With it, every law for → follows from the laws for ¬, ∧ and ∨. The same laws hold in boolean algebra with 1 for ⊤ and 0 for ⊥: see the boolean algebra laws and De Morgan's laws.
Questions
How is this different from a truth table?
A truth table checks every combination of true and false and compares the results, which always settles the question but explains nothing. A proof by laws rewrites one statement into the other, one named law at a time, and shows why they say the same thing. This calculator decides equivalence by truth table first, so the verdict is always right, and then builds the chain of laws.
Which laws are allowed in a proof?
The ones in the table of logical equivalences: identity, domination, idempotent, double negation, commutative, associative, distributive, De Morgan's, absorption and negation laws, plus the conditional and biconditional laws that remove → and ↔. The calculator also uses a few shortcuts from boolean algebra, such as the redundancy law p ∨ (¬p ∧ q) ≡ p ∨ q, each of which is itself proved by truth table in the tests. Like most textbooks, it sometimes reorders the terms of a conjunction or disjunction without a separate line for the commutative law.
What is material implication?
It is the reading of "if p then q" used in logic: p → q is false only when p is true and q is false. That makes it equivalent to ¬p ∨ q, and the equivalence p → q ≡ ¬p ∨ q is also called the conditional law or the law of material implication. It is the first step in most proofs with →.
Why do proofs from different textbooks look different?
Because there is usually more than one route. Laws can be applied in a different order, a textbook may merge two steps into one or split one into two, and some books name the same law differently: domination is also called annulment, and the negation laws are also called complement laws. Any chain is a valid proof as long as each line follows from the one before by a law.
What does "applied in reverse" mean?
Every law is an equivalence, so it can be used in both directions. The calculator simplifies both statements until they meet, then walks back up the right-hand working. On that part of the proof each law runs from its simpler side to its longer side, which is marked in reverse.
How do I show a statement is a tautology?
Leave the second field empty. A statement is a tautology when it is equivalent to ⊤, so simplifying it by the laws until ⊤ is left proves it. The calculator also checks the truth table, so it will tell you if a statement is a tautology even when the laws alone do not reach ⊤.
How do I type the symbols?
NOT: ¬, ~ or !. AND: ∧, & or ^. OR: ∨, | or v. IF-THEN: →, -> or =>. IF AND ONLY IF: ↔, <-> or iff. XOR: ⊕. Use single letters such as p, q and r, and ⊤ and ⊥ (or true and false) for the constants. Up to 6 letters are allowed.