Back to the on-screen lesson ·
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.
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.
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.
$\phi \equiv \psi$ says the two formulas have the same column. A law is a named equivalence used as a rewriting. Replacement is the move of swapping a subformula for an equivalent one inside a larger formula. A chain is a sequence of such rewritings, each line equivalent to the last.
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
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.
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.
$\neg (P \vee Q)$ against $\neg P \vee \neg Q$: try the row with $P$ true and $Q$ false.
Go straight to a mixed row.
The first is false there, because $P \vee Q$ is true; the second is true, because $\neg Q$ is.
One row is enough.
Not equivalent. The correct partner is $\neg P \wedge \neg Q$, which is De Morgan with the connective swapped.
Swap the connective.
$P \to (Q \to R)$: eliminate the inner arrow first, giving $P \to (\neg Q \vee R)$.
Arrows out.
Then the outer: $\neg P \vee (\neg Q \vee R)$.
One law per line.
Gather the two negations by De Morgan: $\neg (P \wedge Q) \vee R$, which is $(P \wedge Q) \to R$ read backwards.
The chain proves exportation.
The second conjunct is true whenever $P$ is, so the conjunction holds exactly when $P$ does.
Equivalent, by absorption: the two columns are both simply the column of $P$.
Are $\neg (P \wedge Q)$ and $\neg P \vee \neg Q$ equivalent?
Give the column of (~(P & Q)) <-> (~P | ~Q) over the four rows for $P$ and $Q$.
| P | Q | (~(P & Q)) <-> (~P | ~Q) |
|---|---|---|
Fill both columns for $\neg (P \wedge Q)$ and $\neg P \vee \neg Q$. The rows are in the usual order.
| $\neg (P \wedge Q)$ | $\neg P \vee \neg Q$ | |
|---|---|---|
| Row 1 | ||
| Row 2 | ||
| Row 3 | ||
| Row 4 |
Match each law to the equivalence it states.
| $\neg (P \wedge Q)$ and $\neg P \vee \neg Q$ | $P \to Q$ and $\neg Q \to \neg P$ | $\neg \neg P$ and $P$ | $P \to Q$ and $\neg P \vee Q$ | $P \wedge (Q \vee R)$ and $(P \wedge Q) \vee (P \wedge R)$ | |
|---|---|---|---|---|---|
| De Morgan | |||||
| Contraposition | |||||
| Double negation | |||||
| The material conditional | |||||
| Distribution |
Mark every formula below that is equivalent to $P \to Q$.
This task has no paper form; do it on a device.
Equivalence is two claims, not one: each formula must follow from the other. Here is one of the two directions. Premise: P -> Q. Conclusion: Q -> P. Does the conclusion follow? If it does not, give a row that breaks it.
P -> Q
∴ Q -> P
valid invalid — countermodel:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
These four formulas are a chain of equivalences, each line obtained from the one before by a single law. Put them in order, starting from $\neg (P \to \neg Q)$.
Number the steps in order (write the number in the box):
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.
8. Your turn: is $P \wedge (Q \vee P)$ equivalent to $P$?, step 2