Equivalence · printable packet

When two formulas have the same column, the named laws that say so without a table, and the replacement rule that lets them chain.

Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.

1. What you will learn

By the end of this lesson you will be able to decide whether two formulas are equivalent by comparing their columns or by testing the biconditional between them, name and apply De Morgan, contraposition, double negation, the material conditional and distribution, build a chain of rewritings one law at a time, and split an equivalence into the two arguments it is made of.

2. What you already have

You can build a table and classify a formula by its column. Equivalence is the comparison of two columns, and the laws below are the comparisons already done, kept so that they need not be redone.

3. Terms to use precisely

4. Logical equivalence

Term	What it means
Logical equivalence	Agreement on every assignment to the atoms in either formula.
Distinguishing assignment	An assignment on which two formulas differ.
De Morgan's laws	Negating a conjunction gives a disjunction of negations, and conversely.
Contrapositive	~Q -> ~P, which is equivalent to P -> Q.

Two formulas are equivalent when they have the same column: they agree under every valuation. Equivalently — and this is the connection worth keeping — $\phi \equiv \psi$ exactly when $\phi \leftrightarrow \psi$ is a tautology. A handful of equivalences are used so often that they have names: De Morgan ($\neg (P \wedge Q) \equiv \neg P \vee \neg Q$ and its mirror), contraposition ($P \to Q \equiv \neg Q \to \neg P$), double negation, the material conditional ($P \to Q \equiv \neg P \vee Q$), distribution, commutativity, associativity and absorption. Their use is replacement: because a compound formula reads only the columns of its parts, a part may be swapped for anything with the same column and the whole formula's column is unchanged. So equivalences chain, each line differing from the last by one law, and the last line is equivalent to the first.

Another way: steps

To test a pair: build both columns and compare, or falsify the biconditional.
To rewrite: eliminate arrows with the material conditional.
Push negations inward with De Morgan until each reaches a single atom.
Clear double negations, then distribute if a normal form is wanted.

Another way: example

$\neg (P \to Q) \equiv \neg (\neg P \vee Q) \equiv \neg \neg P \wedge \neg Q \equiv P \wedge \neg Q$: the negation of a conditional asserts the antecedent and denies the consequent.

5. One direction does not establish equivalence

P & Q entails P: whenever the conjunction is true, P is true. But P does not entail P & Q. On P true and Q false the first formula is true and the conjunction is false. Equivalence requires both directions, or directly requires agreement in every row.

To test a proposed rewrite, use all atoms occurring on either side. Align their rows before comparing final columns. If the formulas differ at one row, record that assignment and both values; this is a complete disproof of equivalence. If they agree on every row of an exhaustive table, the test succeeds. Trying several convenient rows is not an exhaustive test.

For the conditional rewrite P -> Q as ~P | Q, both columns are T,F,T,T. Its converse Q -> P instead has T,T,F,T. Contraposition preserves the column, reversal alone does not. De Morgan's law also changes two things at once: ~(P & Q) becomes ~P | ~Q. Merely pushing the negation through while leaving & unchanged changes the truth conditions.

6. Agree on every shared assignment

Logical equivalence compares two formulas under the same assignments. The formulas are equivalent when neither ever differs from the other in truth value. This is stronger than both being satisfiable, both being contingent, or both being true in a particular situation. P and Q are both contingent, yet they disagree whenever one atom is true and the other false. A classification describes one column's overall pattern; equivalence compares two aligned columns entry by entry.

Use the union of the atom names appearing in the two formulas. To compare P with P & Q, include both P and Q even though the left formula does not mention Q. The left column repeats P's value across the different Q assignments. The assignment P true, Q false gives left true and right false, which refutes equivalence. Ignoring Q would hide the very variation that matters.

There are two ways to disprove equivalence: find left true with right false, or left false with right true. Either direction is enough. A proposed witness must give values to the relevant atoms and then calculate both complete formulas on that same row. Merely saying 'they look different' is insufficient because different syntax often expresses identical truth conditions.

To establish equivalence by a table, check all assignments and show that every pair of final entries agrees. One agreeing row proves only agreement there. Even three agreeing rows out of four leave a possible mismatch in the last row. An exhaustive table is a finite certificate: another reader can verify its assignment list, intermediate calculations, and pairwise comparisons.

Equivalence can also be understood as mutual entailment. Whenever the left formula holds, the right holds, and whenever the right holds, the left holds. A one-way implication between formulas falls short. P & Q guarantees P, but P does not guarantee P & Q. Testing the missing direction is a useful diagnosis when someone mistakes a weaker consequence for an equivalent rewrite.

7. Use equivalence rules with their complete patterns

De Morgan's rules coordinate negation and the connective being negated. A conjunction fails when at least one conjunct fails, so ~(P & Q) is equivalent to ~P | ~Q. A disjunction fails when both disjuncts fail, so ~(P | Q) is equivalent to ~P & ~Q. Both the connective and the placement of negations change. Moving the negations while keeping the connective fixed usually produces a different truth function.

The conditional rewrite follows its prohibited case. P -> Q is false exactly when P is true and Q false. The disjunction ~P | Q is false exactly when ~P is false and Q false, which imposes those same atomic values. Since both have the same false case and are true elsewhere, they are equivalent. This explanation derives the rule from truth conditions rather than asking you to memorize a symbol swap.

Contraposition preserves a conditional by denying and exchanging its complete sides. From A -> B, the equivalent form is ~B -> ~A. If A is P & Q, keep that whole conjunction inside the new denial: ~B -> ~(P & Q). Negating just P would change the antecedent being denied. A rule schema can contain compound inputs, but each input must be carried through intact.

The converse B -> A is different. So is the inverse ~A -> ~B, though converse and inverse are equivalent to each other by contraposition. For the original P -> Q, choose P false and Q true. The original is true, while the converse and inverse are false. One diagnostic assignment can therefore prevent two common mistaken rewrites.

Double negation gives ~~A equivalent to A in this classical system. Apply it to a complete formula. For ~~(P | Q), removing the two outer negations leaves P | Q. It does not authorize removing a single negation inside an unrelated part. Each rewrite should identify the exact subformula that matches the rule and leave the surrounding structure unchanged.

8. Replace a part without changing the whole

If two formulas have the same value on every assignment, substituting one for the other inside a truth-functional context preserves the whole formula's value. The surrounding connective receives the same input value, so its output cannot change. For example, replacing P -> Q by ~P | Q inside (P -> Q) & R yields (~P | Q) & R. The conjunction still combines the same left-side value with R on each row.

This replacement principle depends on genuine equivalence. Replacing P & Q by P inside a larger formula can change the result because the two parts differ on a mixed assignment. A consequence is not automatically interchangeable with its premise. Before simplifying, establish the local equivalence and preserve the context's parentheses so a reader can see what was replaced.

It also depends on the type of context. This lesson concerns truth-functional connectives. Ordinary reports of what someone believes, expects, or knows can involve distinctions not captured by the truth value of an embedded statement alone. Do not infer that every pair of logically equivalent sentences may be exchanged freely inside any English sentence. Later work on knowledge and modality examines richer forms of representation.

In a multistep simplification, record one equivalence move at a time. Write the formula before the move, the new formula, and the rule connecting them. If a later result seems wrong, inspect the first transition whose two sides disagree on a test assignment. A chain of locally justified replacements is easier to audit than a dramatic final simplification with no visible route.

Finally, distinguish a logical rewrite from a practical choice of wording. Equivalent conditions may differ in readability, implementation convenience, or the explanation they suggest to a reader. The truth-table test establishes preserved truth conditions under the fixed key. It does not decide which phrasing communicates best, whether the key matches the intended policy, or whether the policy contains every requirement the situation needs.

9. Rewording a cancellation condition

A fictional event notice says that the event is canceled when it is not the case that both the venue is available and the equipment works. Let V mean venue available and E mean equipment works. The cancellation condition is ~(V & E). An editor proposes 'the venue is unavailable or the equipment does not work', formalized as ~V | ~E with inclusive or. Evaluate the four rows VE = TT, TF, FT, FF. The conjunction is T,F,F,F; its negation is F,T,T,T. The editor's formula is also F,T,T,T. The rewrite preserves the condition.

Another editor writes 'the venue is unavailable and the equipment does not work', or ~V & ~E. This has column F,F,F,T. If the venue is available but the equipment fails, the original condition cancels the event and the second rewrite does not. That TF row proves non-equivalence immediately.

The practical check is not whether the revised sentence sounds similar. It is whether it treats every possible combination of the stated conditions the same way. Four cases are enough because there are two atoms; no invented probabilities or attendance figures are needed.

This analysis concerns the cancellation condition only. It does not assert that those are the only possible reasons an organizer may cancel. If the notice intends an exhaustive policy, that intention must be included in the declared reading. Logical equivalence preserves the modeled information; it cannot recover information the model never included.

10. Where this goes wrong

The first error is treating a formula and its converse as the same claim; they agree on two rows and differ on the other two. The second is applying De Morgan without swapping the connective, turning $\neg (P \wedge Q)$ into $\neg P \wedge \neg Q$, which is a strictly stronger formula. The third is replacing a subformula by something merely implied by it rather than equivalent to it: replacement preserves the column only when the column has not changed.

11. Verify a De Morgan rewrite

12. Refute an overstrong denial

13. Replace a compound antecedent correctly

14. Distinguish an arrow from its reverse

15. Guided practice

Compare P -> Q with ~P | Q over PQ rows TT,TF,FT,FF. Write each formula's column as four T/F symbols separated by commas, then the number of differing rows.

16. Guided practice

17. Guided practice

Compare ~(P | Q) with ~P & ~Q over PQ rows TT,TF,FT,FF. Write each formula's column as four T/F symbols separated by commas, then the number of differing rows.

18. Practice

Compare P -> Q with Q -> P over PQ rows TT,TF,FT,FF. Write each formula's column as four T/F symbols separated by commas, then the number of differing rows.

19. Practice

V means venue available and E means equipment works. Express: it is not the case that both the venue is available and the equipment works.

20. Somewhere new

Compare P | (P & Q) with P over PQ rows TT,TF,FT,FF. Write each formula's column as four T/F symbols separated by commas, then the number of differing rows.

21. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

22. Test question

Compare P <-> Q with (P & Q) | (~P & ~Q) over PQ rows TT,TF,FT,FF. Write each formula's column as four T/F symbols separated by commas, then the number of differing rows.

23. What you can do now

You can test a pair of formulas for equivalence and rewrite one formula into another by named laws. Say in your own words why a subformula may be replaced by an equivalent one inside a larger formula.

Working for the steps left to you

Its antecedent is true and consequent false, so the columns differ.