Every way to show two sentences are equivalent (or not)
A table for a yes/no verdict, a chain of laws for a step-by-step case, a normal form for a standard shape.
Ask what you need to produce.
- Just a verdict → one truth table with a column for each sentence. They are equivalent if the columns match on every row. A single row where they differ proves they are not.
- A step-by-step derivation, with a named law at each step → a chain of equivalences. Replace one part at a time using the laws below.
- Proof that they are NOT equivalent → you never need the whole table. One row where they disagree is enough.
- A standard shape to compare against → read a DNF or CNF off each sentence's table. Two sentences are equivalent exactly when their tables give the same normal form.
Checking a single row where both sentences agree does not show equivalence. Every row has to match.
What equivalence means
Example
Two sentences A and B are logically equivalent, written A \equiv B, exactly when they have the same truth value on every row. This holds if and only if A \leftrightarrow B is a tautology.
What is this saying? Equivalent sentences are two ways of saying the same thing: no possible situation makes one true and the other false. Since \leftrightarrow is true just when its two sides match, "they always match" is the same as "their biconditional is always true."
Why should I care? It lets you check an equivalence with the tools you already have: build one table and look at one column. It also explains why equivalent sentences can replace each other in reasoning.
Intuition. A \leftrightarrow B is false only on rows where A and B disagree. No such rows means no F in the biconditional's column.
Ingredients.
- \equiv: "is logically equivalent to." It is a claim ABOUT two sentences, not a connective inside a sentence.
- \leftrightarrow: the biconditional connective, which builds one sentence from two.
- Tautology: true on every row.
Example. P \to Q and \neg P \vee Q have the columns T, F, T, T and T, F, T, T. They match on every row, so P \to Q \equiv \neg P \vee Q.
What breaks if you check one row. Two sentences can agree on one row and disagree on another: P \wedge Q and P \vee Q agree when both letters are T but not when only P is. Equivalence needs every row.
A second test. Two sentences are equivalent exactly when the biconditional joining them is a tautology.
Show proof
A \leftrightarrow B is T on a row exactly when A and B have the same value on that row. So A \leftrightarrow B is T on every row if and only if A and B have the same value on every row, which is the definition of A \equiv B.
Testing with a table
Term
truth table
Deriving with the laws
Each step replaces one part with an equivalent part, and names the law it used.
If B \equiv C, and A' is the result of replacing one occurrence of B inside the sentence A with C, then A \equiv A'.
What is this saying? If two sentences always have the same truth value, you can swap one for the other inside a bigger sentence without changing the bigger sentence's truth value on any row.
Why should I care? This is what makes a chain of equivalences work. The laws are stated for whole sentences, but you usually apply them to a part: rewriting \neg\neg Q as Q inside P \wedge \neg\neg Q, for example.
Intuition. Every connective is truth-functional: the value of a compound depends only on the values of its parts. If a part keeps its value on every row, the whole does too.
Ingredients.
- A: the larger sentence. B: a part of it. C: a sentence equivalent to B.
- A': A with that occurrence of B replaced by C.
- Truth-functional: depending only on the truth values of the parts.
Example. Since \neg\neg Q \equiv Q, the sentence P \wedge \neg\neg Q is equivalent to P \wedge Q.
What breaks if the replaced part doesn't match. The part you replace must be a whole subsentence exactly matching B. In \neg P \wedge Q there is no subsentence \neg(P \wedge Q), so De Morgan's law can't be applied there.
Why a law may be used on a part buried deep inside a sentence.
Show proof
Fix a row. Build A from its parts, starting from the smallest. Up to the point where B appears, A and A' have identical parts. At B's position, B and C have the same value on this row, since they are equivalent. Every connective above that position then receives the same input values in A and in A', so, being truth-functional, it produces the same output. So A and A' get the same value on this row, and the row was arbitrary.
For every sentence A, \neg\neg A \equiv A.
What is this saying? Denying a denial gets you back where you started: "it is not the case that it is not raining" says it is raining.
Why should I care? Double negations turn up constantly when you push a negation inward with De Morgan's laws or rewrite a conditional. This law is what lets you clean them up.
Intuition. Each \neg flips the truth value. Two flips return the original value.
Ingredients.
- A: any sentence.
- \neg\neg A: the negation of the negation of A.
- \equiv: same truth value on every row.
Example. "It's not true that the store isn't open" is equivalent to "the store is open."
What doesn't follow. Double negation cancels two negations applied to the same sentence. In \neg(\neg P \wedge Q) the two \neg signs apply to different sentences, and they don't cancel: that sentence is equivalent to P \vee \neg Q, not to P \wedge Q.
Example
Show proof
If A is T, then \neg A is F and \neg\neg A is T. If A is F, then \neg A is T and \neg\neg A is F. On both rows \neg\neg A has the same value as A.
For any propositions p and q: \neg(p \wedge q) \equiv \neg p \vee \neg q \neg(p \vee q) \equiv \neg p \wedge \neg q
What is this saying? To deny an "and," deny at least one of its parts: "not both" means "one or the other fails." To deny an "or," deny both parts: "not either" means "neither." In each law the \neg moves onto each part, and the connective swaps.
Why should I care? These two laws are how you push a "not" inside a bracket. You need them to simplify a sentence, to put it in a normal form, and to state plainly what a denial claims.
Intuition. "Not both a towel and a mat" allows a towel alone. So it can't mean "no towel and no mat." It means "no towel, or no mat." The "and" had to turn into "or" once the "not" moved in.
Ingredients.
- p, q: any two propositions. Capital letters such as A and B work the same way.
- \neg: "not." \wedge: "and." \vee: "or."
- \equiv: the two sides have the same truth value on every row.
Example. "It's not true that the café is open and serving lunch" is equivalent to "the café is closed, or it isn't serving lunch."
What doesn't follow. The \neg does not just copy onto each part. \neg(p \wedge q) is not equivalent to \neg p \wedge \neg q: on the row p = T, q = F, the first is true and the second false.
Example
Show proof
Both are checked directly by truth table -- a finite, exhaustive check suffices since there are only 2^2=4 rows to consider for two atoms.
First law. At p=T,q=T: left side \neg(T\wedge T)=\neg T=F; right side \neg T\vee\neg T=F\vee F=F. At p=T,q=F: left side \neg(T\wedge F)=\neg F=T; right side F\vee T=T. At p=F,q=T: left side \neg(F\wedge T)=T; right side T\vee F=T. At p=F,q=F: left side \neg(F\wedge F)=T; right side T\vee T=T. Every row matches.
Second law. At p=T,q=T: left side \neg(T\vee T)=F; right side F\wedge F=F. At p=T,q=F: left side \neg(T\vee F)=F; right side F\wedge T=F. At p=F,q=T: left side \neg(F\vee T)=F; right side T\wedge F=F. At p=F,q=F: left side \neg(F\vee F)=T; right side T\wedge T=T. Every row matches.
For all sentences A and B:
- Material implication: A \to B \equiv \neg A \vee B
- Contraposition: A \to B \equiv \neg B \to \neg A
- Negated conditional: \neg(A \to B) \equiv A \wedge \neg B
- Biconditional as two conditionals: A \leftrightarrow B \equiv (A \to B) \wedge (B \to A)
- Biconditional as matching: A \leftrightarrow B \equiv (A \wedge B) \vee (\neg A \wedge \neg B)
What is this saying? A conditional says "either the condition fails or the result holds." It says the same as its contrapositive ("if not the result, then not the condition"). It is false only when the condition holds and the result doesn't. A biconditional is two conditionals, one each way, or equivalently "both true or both false."
Why should I care? These let you remove \to and \leftrightarrow from any sentence, which is the first step toward a normal form, and they explain which rewrites of a conditional are safe.
Intuition. Each law restates the conditional's one false row (A T, B F) or the biconditional's two false rows (the rows where A and B differ).
Ingredients.
- A, B: any sentences.
- Contrapositive: \neg B \to \neg A. The converse is B \to A and the inverse is \neg A \to \neg B; neither is equivalent to A \to B.
Example. "If it rains, the game is postponed" ≡ "It doesn't rain, or the game is postponed" ≡ "If the game isn't postponed, it didn't rain."
What does not hold. \neg(A \to B) is not \neg A \to \neg B. And A \to B is not equivalent to its converse B \to A or its inverse.
Example
Show proof
Each is a four-row truth table check. For (1): A \to B is F only when A is T and B is F; \neg A \vee B is F only when \neg A and B are both F, which is the same row. For (2): \neg B \to \neg A is F only when \neg B is T and \neg A is F, that is, B F and A T, the same row again. For (3): negate (1) and apply De Morgan and double negation. For (4): the right side is F exactly when one of the two conditionals is F, which happens exactly on the rows where A and B differ, the rows where A \leftrightarrow B is F. (5) is T exactly on the two rows where A and B match.
For all sentences A, B, C:
| Law | For \wedge | For \vee |
|---|---|---|
| Commutative | A \wedge B \equiv B \wedge A | A \vee B \equiv B \vee A |
| Associative | (A \wedge B) \wedge C \equiv A \wedge (B \wedge C) | (A \vee B) \vee C \equiv A \vee (B \vee C) |
| Distributive | A \wedge (B \vee C) \equiv (A \wedge B) \vee (A \wedge C) | A \vee (B \wedge C) \equiv (A \vee B) \wedge (A \vee C) |
What is this saying? You can swap the two sides of an "and" or an "or." In a chain of "and"s only, or of "or"s only, the brackets can go anywhere. And an "and" spreads over an "or" (and the other way round) the way multiplication spreads over addition.
Why should I care? These are the laws you use most often in a chain of equivalences, and knowing which regroupings are NOT allowed is just as important.
Intuition. A conjunction is true when all its parts are true, however they are ordered or bracketed; a disjunction is true when any part is. The distributive laws say that "A, and also B or C" is true in exactly the cases "A and B, or A and C" covers.
Ingredients.
- A, B, C: any sentences.
- \equiv: same truth value on every row.
Example. "Soup, and salad or bread" is equivalent to "soup and salad, or soup and bread."
What does not hold.
- \to is not commutative: A \to B and B \to A differ when A is T and B is F.
- Brackets can't be moved across two different connectives: (A \wedge B) \vee C is not equivalent to A \wedge (B \vee C) (make A F and C T).
Example
Show proof
Each law is checked by a truth table: 4 rows for the commutative laws and 8 rows for the others. For the first distributive law, both sides are T exactly when A is T and at least one of B, C is T: the left side because A and B \vee C must both be T; the right side because one of A \wedge B and A \wedge C must be T. The second distributive law is checked the same way: both sides are T exactly when A is T or both B and C are T.
For every sentence A, with P \vee \neg P standing for any tautology and P \wedge \neg P for any contradiction:
| Law | For \wedge | For \vee |
|---|---|---|
| Idempotent | A \wedge A \equiv A | A \vee A \equiv A |
| Identity | A \wedge (P \vee \neg P) \equiv A | A \vee (P \wedge \neg P) \equiv A |
| Domination | A \wedge (P \wedge \neg P) \equiv P \wedge \neg P | A \vee (P \vee \neg P) \equiv P \vee \neg P |
| Negation | A \wedge \neg A \equiv P \wedge \neg P | A \vee \neg A \equiv P \vee \neg P |
What is this saying? Saying the same thing twice adds nothing. Adding a tautology with "and," or a contradiction with "or," changes nothing. A tautology swamps any "or" it joins, and a contradiction swamps any "and." And A with its own negation gives a contradiction ("and") or a tautology ("or").
Why should I care? These laws are how a step-by-step rewrite of a sentence gets shorter: they remove repetition and throw away parts that can't affect the truth value.
Intuition. A tautology is T on every row, so in an "and" it never changes the result, and in an "or" it makes the result T on every row. A contradiction does the mirror image.
Ingredients.
- A: any sentence.
- P \vee \neg P: stands for any tautology; any other tautology works the same way.
- P \wedge \neg P: stands for any contradiction.
Example. "The shop is open, and it's raining or it isn't" is equivalent to "the shop is open."
Watch the pairing. Identity and domination swap roles between \wedge and \vee: a tautology is harmless in an "and" but takes over an "or."
Example
Show proof
Each law is a two-row (or, with P as a separate letter, four-row) truth table check. For identity with \wedge: P \vee \neg P is T on every row, so A \wedge (P \vee \neg P) is T exactly when A is. For domination with \vee: A \vee (P \vee \neg P) has a T disjunct on every row, so it is T on every row. The others are checked the same way.
Comparing normal forms
Every sentence of sentential logic is logically equivalent to a sentence in disjunctive normal form (an "or" of "and"s of literals) and to a sentence in conjunctive normal form (an "and" of "or"s of literals).
What is this saying? However tangled a sentence is, you can rewrite it as a list of alternatives, each a plain "these letters true, those false" combination. You can also rewrite it as a list of requirements, each a plain "at least one of these" condition.
Why should I care? Normal forms give every sentence a standard shape, so two sentences can be compared by putting both into it. The DNF construction also shows that the five connectives can express any truth table at all.
Intuition. A sentence is true on certain rows. Describe each of those rows with an "and" of literals, then join the descriptions with "or." The result is true on exactly those rows.
Ingredients.
- Literal: a sentence letter or its negation, such as P or \neg Q.
- DNF: a disjunction of one or more conjunctions of literals.
- CNF: a conjunction of one or more disjunctions of literals.
Example. P \leftrightarrow Q is true on the rows TT and FF, so its DNF is (P \wedge Q) \vee (\neg P \wedge \neg Q). Its CNF is (\neg P \vee Q) \wedge (P \vee \neg Q).
Not unique. A sentence has many equivalent DNFs and CNFs; the theorem says at least one exists, not that it is the only one.
Every sentence has a DNF and a CNF, read straight off its truth table.
Show proof
DNF. List the rows on which the sentence S is true. For each such row, form the conjunction of literals that is true on that row and no other: the letter itself if it is T there, its negation if F. The disjunction of these conjunctions is true on exactly the rows where S is true, so it is equivalent to S. If S is true on no row, P \wedge \neg P is a DNF for it.
CNF. Find a DNF for \neg S as above. Negate it: \neg\neg S \equiv S. Push the outer negation inward with De Morgan's laws, which turns the "or" of "and"s into an "and" of "or"s, and remove double negations. The result is a CNF equivalent to S.