519 lines
11 KiB
Text
519 lines
11 KiB
Text
#import "./dvd.typ": *
|
|
|
|
#show: dvdtyp.with(
|
|
title: "Homework 1",
|
|
author: "Youwen Wu",
|
|
)
|
|
|
|
#set heading(
|
|
numbering: (
|
|
num => {
|
|
return "1." + str(num)
|
|
}
|
|
),
|
|
)
|
|
|
|
#set par(first-line-indent: 0pt, spacing: 1em)
|
|
|
|
Problems:
|
|
|
|
1.1: \#1ceij, 2c, 3cdeghjL, 4cdefh, 6, 7cg, 10ce, 11bei, 12a, 13
|
|
|
|
1.2: \#1bd, 2bd, 3, 5cfgh, 6bcg, 7be, 10bfg, 12bc, 13, 16cde
|
|
|
|
= Exercises
|
|
|
|
1. \
|
|
c. #[
|
|
$x/2$ is a rational number.
|
|
|
|
True.
|
|
] \
|
|
|
|
e. #[
|
|
Either $pi$ is rational and $17$ is a prime, or $7 < 13$ and $81$ is a perfect square.
|
|
|
|
True.
|
|
] \
|
|
|
|
i. #[
|
|
It is not the case that $39$ is prime, or that 64 is a power of 2.
|
|
|
|
False.
|
|
] \
|
|
|
|
j. #[
|
|
There are more than three false statements in this book, and this statement is one of them.
|
|
|
|
False.
|
|
]
|
|
|
|
2c. #[
|
|
$P$ is $5^2 + 12^2 = 13^2$ and $Q$ is $sqrt(2) + sqrt(3) = sqrt(2 + 3)$
|
|
|
|
$P and Q: "false"$
|
|
|
|
$P or Q: "true"$
|
|
]
|
|
|
|
3. #[
|
|
\
|
|
c. $P and not Q$
|
|
#[
|
|
#table(
|
|
columns: 3,
|
|
align: center,
|
|
[$P$], [$Q$], [$P and not Q$],
|
|
[T], [T], [F],
|
|
[T], [F], [T],
|
|
[F], [T], [F],
|
|
[F], [F], [F],
|
|
)
|
|
] \
|
|
d. $P and (Q or not Q)$
|
|
#[
|
|
#table(
|
|
columns: 5,
|
|
align: center,
|
|
[$P$], [$Q$], [$not Q$], [$Q or not Q$], [$P and (Q or not Q)$],
|
|
[T], [T], [F], [T], [T],
|
|
[T], [F], [T], [T], [T],
|
|
[F], [T], [F], [T], [F],
|
|
[F], [F], [T], [T], [F],
|
|
)
|
|
] \
|
|
e. $(P and Q) or not Q$ \
|
|
#[
|
|
#table(
|
|
columns: 5,
|
|
align: center,
|
|
[$P$], [$Q$], [$P and Q$], [$not Q$], [$(P and Q) or not Q$],
|
|
[T], [T], [T], [F], [T],
|
|
[F], [T], [F], [F], [F],
|
|
[T], [F], [F], [T], [T],
|
|
[F], [F], [F], [T], [T],
|
|
)
|
|
] \
|
|
g. $(P or S) and (P or K)$
|
|
#table(
|
|
columns: (1fr, 1fr, 1fr, 1fr, 1fr, 2fr),
|
|
align: center,
|
|
[$P$], [$S$], [$K$], [$P or S$], [$P or K$], [$(P or S) and (P or K)$],
|
|
[T], [T], [T], [T], [T], [T],
|
|
[T], [T], [F], [T], [T], [T],
|
|
[T], [F], [T], [T], [T], [T],
|
|
[T], [F], [F], [T], [T], [T],
|
|
[F], [T], [T], [T], [T], [T],
|
|
[F], [T], [F], [T], [F], [F],
|
|
[F], [F], [T], [F], [T], [T],
|
|
[F], [F], [F], [F], [F], [F],
|
|
)
|
|
] \
|
|
h. $not P and not Q$
|
|
#table(
|
|
align: center,
|
|
columns: 5,
|
|
[$P$], [$Q$], [$not P$], [$not Q$], [$not P and not Q$],
|
|
[T], [T], [F], [F], [F],
|
|
[T], [F], [F], [T], [F],
|
|
[F], [T], [T], [F], [F],
|
|
[F], [F], [T], [T], [T],
|
|
) \
|
|
j. $(P and Q) or (P and R)$
|
|
#table(
|
|
align: center,
|
|
columns: 6,
|
|
[$P$], [$Q$], [$R$], [$P and Q$], [$P and R$], [$(P and Q) or (P and R)$],
|
|
[T], [T], [T], [T], [T], [T],
|
|
[T], [F], [T], [F], [T], [T],
|
|
[T], [T], [F], [T], [F], [T],
|
|
[T], [F], [F], [F], [F], [F],
|
|
[F], [T], [T], [F], [F], [F],
|
|
[F], [F], [T], [F], [F], [F],
|
|
[F], [T], [F], [F], [F], [F],
|
|
[F], [F], [F], [F], [F], [F],
|
|
) \
|
|
L. $(P and Q) or (P and not S)$
|
|
#table(
|
|
align: center,
|
|
columns: 7,
|
|
[$P$],
|
|
[$Q$],
|
|
[$S$],
|
|
[$not S$],
|
|
[$P and Q$],
|
|
[$P and not S$],
|
|
[$(P and Q) or (P and not S)$],
|
|
|
|
[T], [T], [T], [F], [T], [F], [T],
|
|
[T], [F], [T], [F], [F], [F], [F],
|
|
[T], [T], [F], [T], [T], [T], [T],
|
|
[T], [F], [F], [T], [F], [T], [T],
|
|
[F], [T], [T], [F], [F], [F], [F],
|
|
[F], [F], [T], [F], [F], [F], [F],
|
|
[F], [T], [F], [T], [F], [F], [F],
|
|
[F], [F], [F], [T], [F], [F], [F],
|
|
)
|
|
|
|
4. \
|
|
c. $(P or Q) and (R or S)$ is true. \
|
|
d. $(not P or not Q) or (not R or not S)$ is true. \
|
|
e. $not P or not Q$ is false. \
|
|
f. $(not Q or S) and (Q or S)$ is false. \
|
|
h. $K and not (S or Q)$ is false.
|
|
|
|
6. \
|
|
a. $not P and not Q$, $not (P and not Q)$ are not equivalent because we can choose $P$ and $Q$ to both be true which gives false for proposition 1 and true for proposition 2. \
|
|
b. $(not P) or (not Q), not (P or not Q)$ are not equivalent because we can choose $P$ to be true and $Q$ to be false, and proposition 1 is true while proposition 2 is false. \
|
|
c. $(P and Q) or R$, $P and (Q or R)$ are not equivalent
|
|
|
|
#proof[
|
|
We can also show this result directly by
|
|
|
|
$
|
|
(P and Q) or R &= (P or R) and (Q or R) \
|
|
P and (Q or R) &= (P or Q) and (P or R)
|
|
$
|
|
|
|
Clearly the choices of $P$ and $Q$ are false, $R$ is true again yields a contradictory result where proposition 1 is true while proposition 2 is false.
|
|
]
|
|
|
|
d. $not (P and Q), not P and not Q$ \
|
|
|
|
The statements are not equivalent.
|
|
|
|
#proof[
|
|
By DeMorgan's,
|
|
$ not (P and Q) = not P or not Q $
|
|
Therefore, choosing $P,Q$ with $P != Q$ gives a contradictory result between the two propositions.
|
|
]
|
|
|
|
e. $(P and Q) or R, P or (Q and R)$
|
|
|
|
They are not equivalent.
|
|
|
|
#proof[
|
|
Symbolic manipulation gives
|
|
$
|
|
(P and Q) or R &= (P or R) and (Q or R) \
|
|
P or (Q and R) &= (P or Q) and (P or R)
|
|
$
|
|
Then select the conjunctive statement in parentheses that occurs
|
|
exclusively in one of the statements and set both of its propositions to
|
|
false. In this case we take $Q$ and $R$ false while $P$ is true, which
|
|
makes proposition 1 false while proposition 2 is true.
|
|
]
|
|
|
|
f. $(P and Q) or P, P$
|
|
|
|
They are equivalent, trivially. Clearly $Q$ is independent of the outcome's truth value which only depends on $P$.
|
|
|
|
7. \
|
|
|
|
c. Julius Caesar was born in 1492 or 1493 and died in 1776. \
|
|
|
|
This proposition is of the form $(P or Q) and R$, where
|
|
|
|
$
|
|
P &= #[Caesar was born in 1492] \
|
|
Q &= #[Caesar was born in 1493] \
|
|
R &= #[Caesar died in 1776] \
|
|
$
|
|
|
|
It is false, clearly, as Caesar certainly could not have died in 1776.
|
|
|
|
g. It is not the case that $-5$ and $13$ are elements of $NN$, but $4$ is in the set of rational numbers.
|
|
|
|
This proposition takes the form $not (P and Q) and R$, where
|
|
|
|
$
|
|
P &= -5 in NN \
|
|
Q &= 13 in NN \
|
|
R &= 4 in QQ
|
|
$
|
|
|
|
It is true, since $P$ is false, $Q$ is true, $R$ is true, which implies $not
|
|
(P and Q)$ is true, thus making the proposition as a whole true.
|
|
|
|
10. \
|
|
c. $(P and Q) or (not P or not Q)$ \
|
|
|
|
This is a tautology that is true $forall P,Q$.
|
|
|
|
#proof[
|
|
#table(
|
|
align: center,
|
|
columns: 5,
|
|
[$P$],
|
|
[$Q$],
|
|
[$P and Q$],
|
|
[$not P or not Q$],
|
|
[$(P and Q) or (not P or not Q)$],
|
|
|
|
[T], [T], [T], [F], [T],
|
|
[T], [F], [F], [T], [T],
|
|
[F], [T], [F], [T], [T],
|
|
[F], [F], [T], [T], [T],
|
|
)
|
|
]
|
|
|
|
e. $(Q and not P) and not (P and R)$ \
|
|
|
|
This is neither a tautology nor a contradiction.
|
|
|
|
#proof[
|
|
#table(
|
|
align: center,
|
|
columns: 5,
|
|
[$P$],
|
|
[$Q$],
|
|
[$Q and not P$],
|
|
[$not (P and R)$],
|
|
[$(Q and not P) and not (P and R)$],
|
|
|
|
[T], [T], [F], [F], [F],
|
|
[F], [T], [F], [T], [F],
|
|
[T], [F], [T], [T], [T],
|
|
[F], [F], [F], [T], [F],
|
|
)
|
|
]
|
|
|
|
11. \
|
|
|
|
b. Cleveland will win the first game or the second game.
|
|
|
|
Cleveland loses both the first and second games.
|
|
|
|
e. Roses are red and violets are blue.
|
|
|
|
Roses are green.
|
|
|
|
i. The function $g$ has a relative maximum at $x = 2$ or $x = 4$ and a relative minimum at $x = 3$.
|
|
|
|
$ g(x) "is given by" integral^x_0 (t - 5)(t-6) dif t $
|
|
|
|
12a.
|
|
|
|
Restore parentheses to $not not P or not Q and not S$.
|
|
|
|
$ not (not P) or (not Q and not S) $
|
|
|
|
13. \
|
|
|
|
a. Make a truth table for the exclusive or ($xor$)
|
|
|
|
#table(
|
|
align: center,
|
|
columns: 3,
|
|
[$P$], [$Q$], [$P xor Q$],
|
|
[T], [T], [F],
|
|
[F], [T], [T],
|
|
[T], [F], [T],
|
|
[F], [F], [F],
|
|
)
|
|
|
|
b. Show that $A xor B = (A or B) and not (A and B)$.
|
|
|
|
Intuitively this fact makes sense. Either $A$ or $B$ are true, but $A$ and $B$ can't _both_ be true.
|
|
|
|
#proof[
|
|
By direct computation,
|
|
|
|
#table(
|
|
align: center,
|
|
columns: 6,
|
|
[$P$],
|
|
[$Q$],
|
|
[$P xor Q$],
|
|
[$A or B$],
|
|
[$not (A and B)$],
|
|
[$(A or B) and not (A and B)$],
|
|
|
|
[T], [T], [F], [T], [F], [F],
|
|
[F], [T], [T], [T], [T], [T],
|
|
[T], [F], [T], [T], [T], [T],
|
|
[F], [F], [F], [F], [T], [F],
|
|
)
|
|
]
|
|
|
|
= Exercises
|
|
|
|
1. \
|
|
b. If #math.underbrace("the moon is made of cheese", "antedecent"), then #math.underbrace("triangles have four sides", "consequent").
|
|
|
|
d. #math.underbrace([The differentiability of $f$], "antedecent") is sufficient for #math.underbrace[$f$ to be continuous][consequent].
|
|
|
|
2. \
|
|
b.
|
|
|
|
Converse: If triangles have four sides, then squares have three sides.
|
|
|
|
Contrapositive: If triangles don't have four sides, then squares don't have three sides.
|
|
|
|
#linebreak()
|
|
|
|
d.
|
|
|
|
Converse: The continuity of $f$ is sufficient for $f$ to be differentiable.
|
|
|
|
Contrapositive: If $f$ is not continuous, then $f$ is not differentiable.
|
|
|
|
3. \
|
|
a. $Q$ must be true.
|
|
|
|
#linebreak()
|
|
|
|
b. $Q$ must be true.
|
|
|
|
#linebreak()
|
|
|
|
c. $Q$ is false.
|
|
|
|
#linebreak()
|
|
|
|
d. $Q$ is false.
|
|
|
|
#linebreak()
|
|
|
|
e. $Q$ is true.
|
|
|
|
5. \
|
|
c. True.
|
|
|
|
#linebreak()
|
|
|
|
f. True.
|
|
|
|
#linebreak()
|
|
|
|
g. True.
|
|
|
|
6. \
|
|
b. False.
|
|
|
|
#linebreak()
|
|
|
|
c. False
|
|
|
|
#linebreak()
|
|
|
|
g. False.
|
|
|
|
#linebreak()
|
|
|
|
7. \
|
|
b.
|
|
|
|
#table(
|
|
columns: 6,
|
|
align: center,
|
|
[$P$],
|
|
[$Q$],
|
|
[$not P$],
|
|
[$not P => Q$],
|
|
[$Q <=> P$],
|
|
[$(not P => Q) or (Q <=> P)$],
|
|
|
|
[T], [T], [F], [T], [T], [T],
|
|
[F], [T], [T], [T], [F], [T],
|
|
[T], [F], [F], [T], [F], [T],
|
|
[F], [F], [T], [F], [T], [T],
|
|
)
|
|
|
|
#linebreak()
|
|
|
|
e.
|
|
#table(
|
|
columns: 5,
|
|
align: center,
|
|
[$P$], [$Q$], [$not Q$], [$Q <=> P$], [$not Q => (Q <=> P)$],
|
|
[$T$], [$T$], [F], [T], [T],
|
|
[$F$], [$T$], [F], [F], [T],
|
|
[$T$], [$F$], [T], [F], [F],
|
|
[$F$], [$F$], [T], [T], [T],
|
|
)
|
|
|
|
10. \
|
|
b. If $n$ is prime, then $n = 2$ or $n$ is odd.
|
|
|
|
$
|
|
n "is prime" => (n=2) or (n mod 2 = 1)
|
|
$
|
|
|
|
f.
|
|
|
|
$
|
|
2 < n - 6 => 2n < 4 or n > 4
|
|
$
|
|
|
|
g.
|
|
|
|
$
|
|
6 >= n - 3 <=> n > 4 or n > 10
|
|
$
|
|
|
|
12. \
|
|
b.
|
|
|
|
#table(
|
|
columns: 9,
|
|
align: center,
|
|
[$P$],
|
|
[$Q$],
|
|
[$R$],
|
|
[$not R$],
|
|
[$not Q$],
|
|
[$P and Q$],
|
|
[$P and not R$],
|
|
[$(P and Q) => R$],
|
|
[$(P and not R) => not Q$],
|
|
|
|
[T], [T], [T], [F], [F], [T], [F], [T], [T],
|
|
[T], [F], [T], [F], [T], [F], [F], [T], [T],
|
|
[T], [T], [F], [T], [F], [T], [T], [F], [F],
|
|
[T], [F], [F], [T], [T], [F], [T], [T], [T],
|
|
[F], [T], [T], [F], [F], [F], [F], [T], [T],
|
|
[F], [F], [T], [F], [T], [F], [F], [T], [T],
|
|
[F], [T], [F], [T], [F], [F], [F], [T], [T],
|
|
[F], [F], [F], [T], [T], [F], [F], [T], [T],
|
|
)
|
|
|
|
So they are equivalent.
|
|
|
|
#linebreak()
|
|
|
|
c.
|
|
|
|
#proof[
|
|
$
|
|
P => (Q and R) &<=> not (Q and R) => not P &&("contrapositive") \
|
|
not (Q and R) => not P &<=> (not Q or not R) => not P space &&("DeMorgan's") \
|
|
$
|
|
]
|
|
|
|
13. \
|
|
a. Continuity implies differentiability.
|
|
|
|
#linebreak()
|
|
|
|
b. Differentiability implies continuity.
|
|
|
|
#linebreak()
|
|
|
|
c. It is not possible.
|
|
|
|
#linebreak()
|
|
|
|
d. $P => Q$, where $P$ is true and $Q$ is true.
|
|
|
|
16. \
|
|
c. Contradiction.
|
|
|
|
#linebreak()
|
|
|
|
d. Neither. Statement is equivalent to $P => Q$.
|
|
|
|
#linebreak()
|
|
|
|
e. Tautology. $P and (Q or not Q)$ is independent of $Q$ so this reduces to
|
|
$P <=> P$.
|