Logic and proofs
Introduced| English | Meaning |
|---|---|
| proposition | A statement that is true or false. |
| truth table/truːθ ˈteɪbl/ | A table listing the output of a logical expression or circuit for every combination of inputs. |
| contrapositive | contrapositive |
| converse | converse |
| De Morgan's laws/də ˈmɔːɡənz lɔːz/ | De Morgan's laws |
| predicate logic | Logic using predicates, variables and quantifiers to express statements about objects. |
| quantifier | quantifier |
| direct proof | A proof deriving its conclusion directly from assumptions and established results. |
| contraposition | Proving an implication by proving that a false conclusion implies a false premise. |
| proof by contradiction/pruːf baɪ ˌkɒntrəˈdɪkʃn/ | proof by contradiction |
Did the tester break the claim?
- A spec says: "If the list is sorted, the search returns the right index." A tester feeds in an unsorted list, gets a wrong index and files a bug: "the claim is false."
- The claim is still true. It only promises something about sorted lists. This lesson makes that kind of reading exact, then turns it into proofs.
Propositions and the truth table
- A proposition 命题 is a statement that is true or false. Join them with ¬ (not), ∧ (and), ∨ (or), → (if…then) and ↔ (if and only if).
- A truth table 真值表 lists every combination of T and F for the variables, so it settles any formula. With $n$ variables there are $2^n$ rows.
A formula uses the variables p, q, r and s. How many rows does its truth table have?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Each variable is T or F, so there are $2^4 = 16$ combinations.
Reading "if p then q"
- $p \to q$ is false in one row only: $p$ true and $q$ false. When $p$ is false the claim makes no promise, so it counts as true. That is why the unsorted list broke nothing.
- $p \to q \equiv \neg p \lor q$. The contrapositive 逆否命题 $\neg q \to \neg p$ has the same truth table; the converse 逆命题 $q \to p$ does not.
The claim "if the list is sorted, the search returns the right index" is shown false by an unsorted list that gets a wrong index.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
With p false, p → q is true whatever happens. Only a sorted list with a wrong index would break the claim.
Match each form to the statement it describes, for the claim p → q.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
The contrapositive and ¬p ∨ q share the truth table of p → q; the converse does not; p ∧ ¬q is its negation.
Negation flips everything it passes
- De Morgan's laws 德摩根律: $\neg(p \land q) \equiv \neg p \lor \neg q$ and $\neg(p \lor q) \equiv \neg p \land \neg q$. The negation goes inside and the connective flips.
- Predicate logic 谓词逻辑 adds the quantifiers 量词 $\forall$ (for all) and $\exists$ (there exists). Negation swaps them and negates the predicate: $\neg\forall x\,P(x) \equiv \exists x\,\neg P(x)$.
Claim: "every email has exactly one address." Its negation: "some email has no address, or some email has two or more addresses." One email that breaks the rule is enough.
The negation of ∀x P(x) is —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
One counterexample is enough: negation swaps the quantifier and negates the predicate.
Which formulas are equivalent to ¬(p ∧ q)? Select all that apply.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
De Morgan gives ¬p ∨ ¬q. Rewriting p → ¬q as ¬p ∨ ¬q gives the same, and so does q → ¬p. ¬p ∧ ¬q forgets to flip the connective.
Three proof shapes
- Direct proof 直接证明: assume $p$ and derive $q$. Contraposition 逆否证明: prove $\neg q \to \neg p$ instead, which helps when the negatives are easier to work with.
- Proof by contradiction 反证法: assume $p \land \neg q$ and derive something impossible. Choosing the shape decides which assumptions you get to compute with.
Assuming p ∧ ¬q and deriving something impossible is —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Contradiction assumes the claim fails; the impossibility shows it cannot fail.
Name the shape, then prove
Claim: if $n^2$ is even, then $n$ is even. "$n^2$ even" is hard to use, so prove the contrapositive.
Suppose $n$ is odd: $n = 2k + 1$. Then $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd. So "$n$ odd" gives "$n^2$ odd", and the claim follows.
- State the strategy in the first line ("by contraposition"), so the reader knows what you are assuming.
Put the contraposition proof of "if n² is even then n is even" in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Name the shape first, then work from the assumption ¬q to the conclusion ¬p.
Marks that slip away
- Proving the converse. Showing $q \to p$ when $p \to q$ was asked proves the wrong thing.
- Negating without flipping. $\neg(p \land q)$ is $\neg p \lor \neg q$, not $\neg p \land \neg q$.
- Examples as proof. Ten examples do not prove a "for all" claim. One counterexample does disprove it.
You've got it
- $p \to q$ is false only when $p$ is true and $q$ is false; $p \to q \equiv \neg p \lor q \equiv \neg q \to \neg p$.
- Negation flips ∧/∨ (De Morgan) and swaps $\forall$/$\exists$.
- Translate the claim, choose a shape (direct, contraposition, contradiction), name it, then write justified steps.