Mathematical Thinking Stanford, W2 QUIZ
Math Foundation of computing, Stanford university. Preliminary Course Notes - Keith Schwarz
implication has a truth part(conditional ) and a causation part.
implication = conditional + causation
conditional means ⇒
φ ⇒ ψ is the truth part of “ φ implies ψ ”.
φ is the antecedent
ψ is the consequent define the truth of φ⇒ψ in terms of the truth/falsity of φ and ψ.
Equivalence Quiz
Which of the following conditions is necessary and sufficient for the natural number $n$ to be multiple of 10 ?
- $n$ is multiple of 5
- $n$ is multiple of 20
- $n$ is even and multiple of 5
- $n$ = 100
- $n^2$ is multiple of 100
φ = the natural number $n$ to be multiple of 10
ψ = following conditions
ψ is necessary for φ means φ⇒ψ
ψ is sufficient for φ means ψ⇒φ
| Conditions(ψ ) | $n$ (φ) | Necessary | ||
|---|---|---|---|---|
| φ ⇒ ψ | Sufficient | |||
| ψ ⇒ φ | Bi-conditionals | |||
| φ ⇔ ψ | ||||
| 1 | “ | ✔︎ | ||
| 2 | ” | ✔︎ | ||
| 3 | “ | ✔︎ | ✔︎ | ✔︎ |
| 4 | “ | ✔︎ | ||
| 5 | “ | ✔︎ | ✔︎ | ✔︎ |
answer: both the third and fifth are necessary and sufficient φ ⇔ ψ
explanation:
- if φ, then ψ ;
- φ is sufficient for ψ ;
- φ only if ψ [not the same as “if ψ, then φ” ] ;
- ψ if φ;
- ψ whenever φ;
- ψ is necessary for **φ;
⇔ iff = if only if = equivalence totally, double direction
(φ ⇒ ψ )∧ (ψ ⇒ φ) = φ ⇔ ψ
ψ is necessary for φ means φ⇒ψ
φ is sufficient for ψ means φ⇒ψ
don’t confused the order of implication direction from one to another.
Antecedent ⇒ Consequent, φ ⇒ ψ
if … **then, **only if,
if, whenever,
Keith cycles only if the sun shine, Antecedent is Keith cycles.
Keith ⇒ Sunshine, if Keith cycles, it is sufficient to prove that there must be Sunshine, good day.
it could not be reverse, because sunshine is a necessary reason, but not the sufficient reason that prove Keith cycles.
if there was a sunshine day, but Keith might not cycles, she has other options of activities, so Keith is the antecedent for the sunshine,
sufficient : must be the reason, Antecedent and Consequent could not be reverse, strong reason;
necessary: might be the reason, Antecedent and Consequent could be reverse, weak reason.
Vocabulary
notion: concept.
notation: symbol, sign
Genuine Implication?
antecedents and consequences 前因和后果
conditional
intuition 直觉
genuine causation
QUIZ & Problem set.
Which one is antecedent?
- it is necessary that $n$ is prime in order for ( $2^n$ − 1) to be prime.
- A. $n$ is prime
- B. ( $2^n$ − 1) i prime.
interpret: $n$ is prime which is necessary (in order) for that ( $2^n$ − 1) is (to be) prime. B ⇒ A
B is antecedent.
- The team wins only when Karl is playing.
A. team wins
B. Karl play.
interpret: The team wins only (if) when Karl is playing. A ⇒ B
A is antecedent.
- When Karl plays the team wins.
A. Karl plays
B. team wins
interpret: When followed by Antecedent. A ⇒ B
A is antecedent.
- The team wins when Karl plays.
A. Karl plays
B. team wins
interpret: When followed by Antecedent. A ⇒ B
A is antecedent.
- For natural number m, n, is it truth that mn is even iff m and n are even?
**interpret:
if mn is even, then m and n are even
if m and n are even, then mn is even.
m=2, n=3, mn=6
False
iff means two implication equivalence, double direction are equal. mn means m multiply n, mxn
- is it truth that mn is odd iff m and n are odd?
interpret:
if mn is odd, then m and n are odd
if m and n are odd, then mn is odd.
m=1, n=3, mn=3
True
14. prove equivalence.
| P | Q | -P | -P V Q | P ⇒ Q |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
| -P | - Q | P V Q | - (P V Q) | -P ∧ -Q |
|---|---|---|---|---|
| F | F | T | F | F |
| F | T | T | F | F |
| T | F | T | F | F |
| T | T | F | T | T |
| -P | - Q | -P V -Q | P V -Q | -(P V -Q) |
|---|---|---|---|---|
| F | F | F | T | F |
| F | T | T | T | F |
| T | F | T | F | T |
| T | T | T | T | F |
| P | Q | -(P ∧ Q) | -P V -Q |
|---|---|---|---|
| T | T | F | F |
| T | F | T | T |
| F | T | T | T |
| F | F | T | T |
| P | Q | -(P ∧ Q) | -P V -Q |
|---|---|---|---|
| T | T | F | F |
| T | F | T | T |
| F | T | T | T |
| F | F | T | T |
De Morgan’s Law
¬(φ ∨ ψ ) ⇔ ¬ φ ∧ ¬ψ
¬(φ ∧ ψ ) ⇔ ¬ φ ∨ ¬ψ
¬(φ ⇒ ψ) ⇔ φ ∧ ¬ψ
φ ⇒ ψ ⇔ ¬φ ∨ ψ
φ⇒(ψ⇒θ) ⇔ (φ∧ψ)⇒θ
¬[φ⇒(ψ∧θ)] ⇔ [¬(φ ⇒ ψ) V ¬(φ ⇒ θ)]
[φ ⇒ (ψ ∧ θ)] ⇔ [(φ ⇒ ψ) ∧ (φ ⇒ θ)]
[(φ ∨ ψ )⇒ θ] ⇔ [(φ ⇒ θ) ∧ (ψ ⇒ θ)]
P, Q, R
φ, ψ, θ
| φ | ψ | θ | ψ∧θ | φ⇒(ψ∧θ) | ¬(φ ⇒ ψ) | ¬(φ ⇒ θ) | ¬(φ ⇒ ψ) V ¬(φ ⇒ θ) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | F | F | F |
| T | F | F | F | F | T | T | T |
| F | T | F | F | T | F | F | F |
| F | F | T | F | T | F | F | F |
| φ | ψ | θ | ψ⇒θ | φ⇒(ψ⇒θ) | φ∧ψ | (φ∧ψ)⇒θ |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | F | F | T | T | F | T |
| F | T | F | F | T | F | T |
| F | F | T | T | T | F | T |