Back to the on-screen lesson ·
When two formulas are the same statement, the laws that rewrite one as the other, and why negating a bracket flips the connective inside it.
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 logically equivalent by comparing their columns, name and apply the laws that do most of the work — both De Morgan laws, the material conditional, the negation of an implication, contraposition and double negation — and use a single disagreeing row to show that two formulas are not equivalent. You will also be able to negate a compound statement correctly, which is the first line of every proof by contradiction in the next unit.
Lesson 2 showed that $\neg Q \Rightarrow \neg P$ and $P \Rightarrow Q$ have the same four rows, and called them the same claim. That was one instance of the idea this lesson names and generalises: two formulas are the same statement when their columns agree, and a handful of named laws turn one into the other without a table.
Two formulas are logically equivalent, written $\equiv$, when their truth tables agree in every row. A tautology is a formula whose column is all T; a contradiction is one whose column is all F; anything else is contingent. A law is an equivalence worth remembering by name.
$F \equiv G$ means: over every assignment of truth values to the atoms, $F$ and $G$ come out the same. Nothing about the symbols is required to match — $\neg(P \wedge Q)$ and $\neg P \vee \neg Q$ share not one connective — and nothing about the symbols is allowed to matter.
The laws worth carrying:
| Law | Statement |
|---|---|
| De Morgan | $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$ |
| De Morgan | $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$ |
| Material conditional | $P \Rightarrow Q \equiv \neg P \vee Q$ |
| Negated conditional | $\neg(P \Rightarrow Q) \equiv P \wedge \neg Q$ |
| Contraposition | $P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$ |
| Biconditional | $P \Leftrightarrow Q \equiv (P \Rightarrow Q) \wedge (Q \Rightarrow P)$ |
| Double negation | $\neg \neg P \equiv P$ |
| Distribution | $P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)$ |
Each is proved once, with a table, and then used as a rewriting rule for ever. That is the pattern of the whole subject in miniature: pay for a general fact once, spend it many times.
The two that earn their keep immediately are the negated conditional and De Morgan, because between them they let you negate anything — and unit 2's proof by contradiction begins by negating the statement you are trying to prove.
Another way: steps
To show $F \equiv G$:
Another way: example
Is $P \Rightarrow Q$ equivalent to $\neg P \Rightarrow \neg Q$? Take $P$ false and $Q$ true: the first is T (its hypothesis fails), the second is F ($\neg P$ holds and $\neg Q$ fails). One row disagrees, so no — the inverse is not the statement, settled in one line.
Every proof by contradiction starts by negating a statement, and statements in mathematics are full of ands and ors. 'The function is continuous and bounded' fails when it is discontinuous or unbounded — not when both go wrong. 'The number is $2$ or $3$' fails when it is neither. Getting that backwards produces a proof of the wrong thing, and it produces it silently, because the rest of the argument can be flawless.
The rule in one sentence: a negation moving through a bracket flips every connective it passes. It is the propositional half of the rule for quantifiers in lesson 5, where $\forall$ and $\exists$ swap the same way; learning them as one rule rather than two is worth the effort.
Negating half of a conjunction. $\neg(P \wedge Q)$ is not $\neg P \wedge \neg Q$. The first is true in three rows, the second in one.
Losing the outer negation. Writing $\neg(P \Rightarrow Q)$ as $P \Rightarrow \neg Q$ keeps the arrow, and the arrow is exactly what the negation destroys: the correct form has no arrow in it at all.
Accepting agreement in the rows you checked. Two formulas agreeing in three rows of four are not equivalent. Equivalence is every row, and a table is finite, so there is no excuse for checking only some of it.
$2 + 2 = 4$ and $7$ is prime are both true, and they are not logically equivalent, because equivalence is about every assignment and not about the one we happen to be in. Conversely, two formulas can be equivalent and both false everywhere — $P \wedge \neg P$ and $Q \wedge \neg Q$ are. Equivalence compares columns, not values, and the difference is what lets a law be applied inside a proof where nothing is known yet.
'The room is warm and quiet' is $P \wedge Q$. Its negation is $\neg(P \wedge Q)$.
Write the negation with a bracket first.
De Morgan moves the negation in: $\neg P \vee \neg Q$ — cold, or noisy, or both.
The connective flips as the negation passes.
Not $\neg P \wedge \neg Q$, which says cold and noisy. That is a much stronger claim, and it is not what failing the original requires.
The wrong version is stronger, which is why it slips past.
$\neg(P \Rightarrow Q)$: an implication fails in exactly one row, the row with $P$ true and $Q$ false.
Recall the single failing row.
So its negation is true in exactly that row, which is the formula $P \wedge \neg Q$.
One row true means a conjunction.
This is the sentence 'a counterexample is a case where the hypothesis holds and the conclusion fails', written in symbols — and unit 2 will use it every time it negates a theorem.
A definition you already half knew, derived.
Three atoms, so eight rows. Rather than build both tables, ask when each formula is false — that is one row's worth of condition each.
Ask what makes each side fail.
The left fails when $P$ holds and $Q \Rightarrow R$ fails, that is when $P$ and $Q$ hold and $R$ fails.
Unfold the inner arrow.
The right fails when $P \wedge Q$ holds and $R$ fails — the same condition. They fail in the same rows, so they are true in the same rows, so they are equivalent. This one has a name, exportation, and it is why a theorem with two hypotheses can be written either way.
Let P stand for “the room is warm” and Q for “the room is quiet”. Complete the column for $\neg(P \wedge Q)$, in the usual four-row order.
| P | Q | ~(P & Q) |
|---|---|---|
P stands for “the water is boiling” and Q for “the pressure is normal”. Write a formula equivalent to $\neg(P \Rightarrow Q)$ that is not just a copy of it.
Answer:
A truth table for $P$, $Q$ and $R$ has eight rows. In how many of them is $P \vee Q \vee R$ true?
Answer:
Match each rewriting to the law that licenses it.
| De Morgan, moving a negation through an *and* | De Morgan, moving a negation through an *or* | The material conditional | The negation of an implication | |
|---|---|---|---|---|
| $\neg(P \wedge Q)$ becomes $\neg P \vee \neg Q$ | ||||
| $\neg(P \vee Q)$ becomes $\neg P \wedge \neg Q$ | ||||
| $P \Rightarrow Q$ becomes $\neg P \vee Q$ | ||||
| $\neg(P \Rightarrow Q)$ becomes $P \wedge \neg Q$ |
Premises: P <-> Q and ~Q. Conclusion: ~P. Is the argument valid? If not, give a case 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.
Let P stand for “the shape is a square” and Q for “the shape has four sides”. Complete the column for $P \Rightarrow Q$, in the usual four-row order.
| P | Q | P -> Q |
|---|---|---|
You can compare two formulas row by row and rewrite one into the other with named laws. Say in your own words what De Morgan's laws do to a negated bracket, and why one disagreeing row is enough to settle non-equivalence. Next: quantifiers, and why the order of two of them changes the claim.
10. Your turn: is $P \Rightarrow (Q \Rightarrow R)$ equivalent to $(P \wedge Q) \Rightarrow R$?, step 3