My answer for the UCB EECS 70 Discrete Mathematics and Probability Theory course.
Here is my answer for the UCB EECS 70 Discrete Mathematics and Probability Theory course.
Due to the absence of official answers, some of the answers to the questions may be incorrect, and we also welcome everyone to point them out.
(a)
| \(P\) | \(Q\) | \(Q\lor P\) | \(P\land(Q\lor P)\) | \(P\land Q\) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | T | T | F |
| F | T | T | F | F |
| F | F | F | F | F |
When \(P=\mathtt{T},Q=\mathtt{F}\), \(\mathrm{LHS}=\mathtt{T}\) but \(\mathrm{RHS}=\mathtt{F}\).
So \(\mathrm{LHS}\not\equiv \mathrm{RHS}\).
(b)
| \(P\) | \(Q\) | \(R\) | \(P\lor Q\) | \((P\lor Q)\land R\) | \(P\land R\) | \(Q\land R\) | \((P\land R)\lor(Q\land R)\) |
|---|---|---|---|---|---|---|---|
| False | False | False | False | False | False | False | False |
| False | False | True | False | False | False | False | False |
| False | True | False | True | False | False | False | False |
| False | True | True | True | True | False | True | True |
| True | False | False | True | False | False | False | False |
| True | False | True | True | True | True | False | True |
| True | True | False | True | False | False | False | False |
| True | True | True | True | True | True | True | True |
So \(\mathrm{LHS}\equiv \mathrm{RHS}\).
from itertools import product
if __name__ == "__main__":
tb = (False, True)
for P, Q, R in product(tb, tb, tb):
print('', P, Q, R, P or Q, (P or Q) and R,
P and R, Q and R, (P and R) or (Q and R),
'', sep='|')
(c)
| \(P\) | \(Q\) | \(R\) | \(P\land Q\) | \((P\land Q)\lor R\) | \(P\lor R\) | \(Q\lor R\) | \((P\lor R)\land(Q\lor R)\) |
|---|---|---|---|---|---|---|---|
| False | False | False | False | False | False | False | False |
| False | False | True | False | True | True | True | True |
| False | True | False | False | False | False | True | False |
| False | True | True | False | True | True | True | True |
| True | False | False | False | False | True | False | False |
| True | False | True | False | True | True | True | True |
| True | True | False | True | True | True | True | True |
| True | True | True | True | True | True | True | True |
So \(\mathrm{LHS}\equiv \mathrm{RHS}\).
from itertools import product
if __name__ == "__main__":
tb = (False, True)
for P, Q, R in product(tb, tb, tb):
print('', P, Q, R, P and Q, (P and Q) or R,
P or R, Q or R, (P or R) and (Q or R),
'', sep='|')
(a)
\[\exists x\in\mathbb{R}, x\not\in\mathbb{Q}.\](b)
\[\forall n\in \mathbb{Z},\left((n\in\mathbb{N})\lor(n<0)\right)\land\lnot\left((n\in\mathbb{N})\land(n<0)\right).\](c)
\[\forall n\in \mathbb{N},\left(6\mid n\implies(2\mid n)\lor (3\mid n)\right).\](d) All integers are rational numbers.
(e) All integers divisible by \(2\) or \(3\) are divisible by \(6\).
(f) Any natural number greater than 7 can be decomposed into the sum of two natural numbers.
(a)
\[\forall n\in\mathbb{N}, (4\mid n\implies 2\mid n).\]It is true.
We let \(n=4k, k\in \mathbb{N}\).
We have \(n=2\cdot (2k)\), so \(2\mid n\).
(b) If a natural number is not divisible by \(4\), it is not divisible by \(2\).
\[\forall n\in\mathbb{N}, (4\nmid n\implies 2\nmid n).\]It is false.
A possible counterexample is when \(n=2\), \(4\nmid 2\), but \(2\mid 2\).
(c) If a natural number is divisible by \(2\), it is divisible by \(4\).
\[\forall n\in\mathbb{N}, (2\mid n\implies 4\mid n).\]It is false.
A possible counterexample is when \(n=2\), \(2\mid 2\), but \(4\nmid 2\).
(d) If a natural number is divisible by \(2\), it is divisible by \(4\).
(a)
\[\begin{aligned} \mathrm{LHS}&\equiv\forall x\ ((\exists y\ Q(x, y))\implies P(x))\\ &\equiv \forall x\ (\lnot(\exists y\ Q(x, y))\lor P(x))\\ &\equiv \forall x\ ((\forall y\ \lnot Q(x, y))\lor P(x))\\ &\equiv \forall x\forall y\ (\lnot Q(x, y)\lor P(x))\\ &\equiv \forall x\forall y\ (Q(x, y)\implies P(x))\\ &\not \equiv \forall x\exists y\ (Q(x, y)\implies P(x))\\ &\equiv \mathrm{RHS} \end{aligned}\]To find one counterexample, we could let \(P(x)\) to be contradictions, like “\(x\) is an elephant”, and \(Q(x, y)\) be “\(x=y\)”. On the one hand, for all \(x\), \(\exists y\ Q(x, y)\) is true because we could just let \(y=x\), and \(P(x)\) is false, so \(\mathrm{LHS}\) is false. However, for all \(x\), we just let \(y=x+1\), then since \(Q(x, y)\) is false, \(Q(x, y)\implies P(x)\) is true, so \(\mathrm{RHS}\) is true.
(b)
\[\begin{aligned} \mathrm{LHS}&\equiv\forall x\exists y\ \left(\lnot\left(P(x, y)\implies \lnot Q(x, y)\right)\right)\\ &\equiv\forall x\exists y\ \left(\lnot\left(\lnot P(x, y)\lor \lnot Q(x, y)\right)\right)\\ &\equiv\forall x\exists y\ \left(P(x, y)\land Q(x, y)\right)\\ &\not\equiv\forall x\left((\exists y\ P(x, y))\land (\exists y\ Q(x, y))\right)\\ &\equiv \mathrm{RHS} \end{aligned}\]To find one counterexample, we could let \(P(x, y)\) to be \(x=y\), and \(Q(x, y)\) be “\(x=y+1\)”. On the one hand, when \(x=y\), \(x\neq y+1\), so \(P(x, y)\implies \lnot Q(x, y)\) is true. So \(\mathrm{LHS}\) is false. But for all \(x\). For \(\exists y\ P(x, y)\), we just let \(y=x\), so it is true. And for \(\exists y\ Q(x, y)\), we just let \(y = x - 1\), so it is also true. In all \(\mathrm{RHS}\) is true. So \(\mathrm{LHS}\not\equiv\mathrm{RHS}\).
(c)
\[\begin{aligned} \mathrm{LHS}&\equiv \forall x\exists y\ (\lnot P(x)\lor Q(x,y))\\ \mathrm{RHS}&\equiv\forall x\ (\lnot P(x)\lor(\exists y\ Q(x, y))) \end{aligned}\]If \(P(x)\) is true, \(\mathrm{LHS}\equiv \forall x\exists y\ (\mathtt{F}\lor Q(x, y))\equiv \forall x\exists y\ Q(x, y)\), \(\mathrm{RHS}\equiv\forall x\ (\mathtt{F}\lor (\exists y\ Q(x, y)))\equiv \forall x\exists y\ Q(x, y)\). So \(\mathrm{LHS}\equiv \mathrm{RHS}\).
If \(P(x)\) is true, then \(\mathrm{LHS}\equiv \mathrm{RHS}\equiv \mathtt{T}\).
In all \(\mathrm{LHS}\equiv\mathrm{RHS}\).
(a)
\[\exists x\in\mathbb{R}\ ((x^2=0)\land(\forall y\in\mathbb{R}\ ((y^2=0)\implies (x=y)))).\](b)
\[\forall x\in\mathbb{Q}\ \forall y\in\mathbb{Q}\ \exists z\in \mathbb{Q}\ ((x=y)\lor (x<y<z)\lor(x>y>z)).\](c)
\[\forall x\in\mathbb{Z}\ ((x^2>4)\implies((x<-2)\lor(x>2))).\](d) All real numbers are complex numbers.
(e) There is no integer solution of \(x^2-y^2=10\).
(f) All greater than \(2\) natural numbers can be decomposed into the sum of two prime numbers.
1.
\[\begin{aligned} n&\equiv\sum_{i=0}^{k-1}\left(a_i\cdot 10^i\right)\pmod 9\\ &\equiv \sum_{i=0}^{k-1}\left(a_i\cdot 10^i\mod 9\right)\pmod 9\\ &\equiv \sum_{i=0}^{k-1}\left(a_i\cdot\left(10^i\mod 9\right)\right)\pmod 9\\ &\equiv \sum_{i=0}^{k-1}\left(a_i\cdot\left(10\mod 9\right)^i\right)\pmod 9\\ &\equiv \sum_{i=0}^{k-1}a_i\pmod 9 \end{aligned}\]2.
\[\begin{aligned} &\text{$a^2$ is even}\implies \text{$a$ is even}\\ \equiv&\lnot(\text{$a$ is even})\implies \lnot(\text{$a^2$ is even})\\ \equiv&\text{$a$ is odd}\implies \text{$a^2$ is odd} \end{aligned}\]Let \(a=2k+1, k\in \mathbb{Z}\), we have \(a^2=4k^2+4k+1=2(2k^2+1)+1\), so \(a^2\) is odd.
So \(a\text{ is odd}\implies a^2\text{ is odd}\) holds, so Lemma 2.2 holds.
1. We proceed by induction on \(n\).
Base Case: When \(n=1\), \(\mathrm{LHS}=\mathrm{RHS}=1\). So base case Holds.
Induction Hypothesis: Assume that \(\sum_{i=1}^{k} i = \frac{1}{6}k(k+1)(2k+1)\).
Induction Step: When \(n=k+1\),
\[\begin{aligned} \sum_{i=1}^{k+1}i&=(k+1)+\sum_{i=1}^{k} i\\ &=\frac{1}{6}k(k+1)(2k+1)+k+1\\ &=\frac{1}{6}(k+1)(2k^2+k+6k+6)\\ &=\frac{1}{6}(k+1)(2k^2+7k+6)\\ &=\frac{1}{6}(k+1)(k+2)(2k+3) \end{aligned}\]Thus, \(\forall n\in\mathbb{N}\), \(\sum_{i=1}^{n} i = \frac{1}{6}n(n+1)(2n+1)\) holds.
2. We proceed by induction on \(n\).
Base Case: When \(n=1\), \(\mathrm{LHS}=\mathrm{RHS}=1+x\). So base case Holds.
Induction Hypothesis: Assume that \((1+x)^k\ge 1+kx\), for \(k\in \mathbb{N}\).
Induction Step: When \(n=k+1\),
\[\begin{aligned} (1+x)^{k+1}&=(1+x)\cdot(1+x)^k\\ &\ge(1+x)\cdot(1+kx)\\ &=1+(k+1)\cdot x+kx^2\\ &\ge 1+(k+1)\cdot x \end{aligned}\]Thus, \(\forall n\in\mathbb{N}, x>-1, \ (1+x)^n\ge 1+nx\) holds.
3. We proceed by induction on \(n\).
Base Case: When \(n=2\), \(\mathrm{LHS}=2<4=\mathrm{RHS}\). So base case Holds.
Induction Hypothesis: Assume that \(k!<k^k\), for \(k\in \mathbb{N}, k>1\).
Induction Step: When \(n=k+1\),
\[\begin{aligned} (k+1)!&=(k+1)\cdot k!\\ &<(k+1)\cdot k^k\\ &<(k+1)\cdot (k+1)^k\\ &=(k+1)^{k+1} \end{aligned}\]Thus, \(\forall n\in\mathbb{N}, n>1, \ n!<n^n\) holds.
4. We define an ask \(A\to B\) means asking A if he know B. And we define \(f(n)\) be the times of asking.
Base Case: When \(n=2\), there are just two people A and B. We could ask \(A\to B\) and \(B\to A\). And now we know everything and it is easy for us to find the answer. We asked \(3n-4=2\) times. So \(f(n)\le 3n-4\) holds for \(n=1\).
Induction Hypothesis: Assume that if there are \(k\) people, we could use \(3k-4\) asks to find the answer.
Induction Step: When \(n=k+1\), we could randomly choose two people A and B, asking \(A\to B\).
Now there are two cases:
So \(f(k+1)\le 3(k+1)-4\). And as a conclusion, \(f(n)\le 3n-4\) holds for all \(n\in\mathbb{N}, n\ge 2\).
5. The python code shows below:
def solve(n):
base_case = [(3, 0), (2, 1), (1, 2), (0, 3)]
return base_case[n % 4][0] + (n - 12) // 4, base_case[n % 4][1]
The largest number of 5c stamps my algorithm will ever use is \(3\).
We let the \(i\)-th person have \(a_i\) friends. We have \(a_i\in[0, n-1]\cap \mathbb{Z}\).
Then we check if there exist \(k\in [0, n-1]\cap\mathbb{Z}\), \(\forall i, a_i\neq k\).
In all, there must be at least \(2\) of them have the same number of friends at the party.
If there is no all-red column exist, which means all column has a blue pebble, for every column, we could just choose that blue pebble, then there exist a way choosing makes no red pebble. So there must exist all-red column.
(a) We want to prove \(f^{-1}(A\cup B)\subseteq f^{-1}(A)\cup f^{-1}(B)\) and \(f^{-1}(A\cup B)\supseteq f^{-1}(A)\cup f^{-1}(B)\).
We first show \(f^{-1}(A\cup B)\subseteq f^{-1}(A)\cup f^{-1}(B)\).
Let \(x\in f^{-1}(A\cup B)\), which means \(f(x)\in A\cup B\). So \((f(x)\in A)\lor (f(x)\in B)\). So \(\left(x\in f^{-1}(A)\right)\lor \left(x\in f^{-1}(B)\right)\), which means \(x\in f^{-1}(A)\cup f^{-1}(B)\). So \(f^{-1}(A\cup B)\subseteq f^{-1}(A)\cup f^{-1}(B)\).
Then let’s prove \(f^{-1}(A\cup B)\supseteq f^{-1}(A)\cup f^{-1}(B)\).
We let \(x\in f^{-1}(A)\cup f^{-1}(B)\), which means \(x\in f^{-1}(A)\) or \(x\in f^{-1}(B)\). So \(f(x)\in A\) or \(f(x)\in B\), which is \(f(x)\in A\cup B\). So \(x\in f^{-1}(A\cup B)\). So \(f^{-1}(A)\cup f^{-1}(B)\subseteq f^{-1}(A\cup B)\).
In all, \(f^{-1}(A\cup B)=f^{-1}(A)\cup f^{-1}(B)\).
(b) We want to prove \(f(A\cup B)\subseteq f(A)\cup f(B)\) and \(f(A\cup B)\supseteq f(A)\cup f(B)\).
We firstly prove \(f(A\cup B)\subseteq f(A)\cup f(B)\). Let \(x\in f(A\cup B)\), which is \(\exists y\in A\cup B, f(y)=x\). So \(\exists y\in A, f(y)=x\) or \(\exists y\in B, f(y)=x\). So \(x\in f(A)\) or \(x\in f(B)\). So \(x\in f(A)\cup f(B)\). So \(f(A\cup B)\subseteq f(A)\cup f(B)\).
Then we want to prove \(f(A\cup B)\supseteq f(A)\cup f(B)\). Let \(x\in f(A)\cup f(B)\), which is \(x\in f(A)\) or \(x\in f(B)\). So \(\exists y\in A, x=f(y)\) or \(\exists y\in B, x = f(y)\). So \(\exists y\in A\cup B, x = f(y)\). So \(x\in f(A\cup B)\). So \(f(A)\cup f(B)\subseteq f(A\cup B)\).
In all \(f(A\cup B)=f(A)\cup f(B)\).
The same as Note 3 Question 2.
We proceed by induction on \(n\).
Base Case: When \(n=1\), \(\mathrm{LHS}=\mathrm{RHS}=1+x\). So base case Holds.
Induction Hypothesis: Assume that \((1+x)^k\ge 1+kx\), for \(k\in \mathbb{N}\).
Induction Step: When \(n=k+1\),
\[\begin{aligned} (1+x)^{k+1}&=(1+x)\cdot(1+x)^k\\ &\ge(1+x)\cdot(1+kx)\\ &=1+(k+1)\cdot x+kx^2\\ &\ge 1+(k+1)\cdot x \end{aligned}\]Thus, \(\forall n\in\mathbb{N}, x>0, \ (1+x)^n\ge 1+nx\) holds.
(a) No. If we let \(a_n\le 3^{2^n}\), \(a_{n+1}=3a_n^2\le 3\cdot\left(3^{2^n}\right)^2=3^{2^{n+1}+1}\). But \(3^{2^{n+1}+1}\ge 3^{2^{n+1}}\), so it doesn’t work.
(b) Let’s prove by induction.
Base Case: When \(n=1\), \(a_1=1\), \(3^{2^n-1}=3\). So \(a_n\le 3^{2^n-1}\) holds for \(n=1\).
Induction Hypothesis: Assume that \(a_k\le 3^{2^k-1}\), for \(k\in \mathbb{N}\).
Induction Step: When \(n=k+1\):
\[a_{k+1}=3a_{k}^2\le 3\cdot \left(3^{2^k-1}\right)^2=3^{2^{k+1}-1}.\]So for all \(n\in\mathbb{N}^+\), \(a_n\le 3^{2^n-1}\).
(c) For \(n\in\mathbb{N}\), \(a_n\le 3^{2^n-1}=\frac{1}{3}\cdot 3^{2^n}\le 3^{2^n}\).
We proceed by induction on \(n\).
Base Case: When \(n=1\), let \(c_0=1\), \(n=1\cdot 2^0\). So the assumption holds when \(n=1\).
Induction Hypothesis: We assume that the proposition holds for \(n\le t\).
Induction Step: We use the parity of t+1 for discussion.
If \(t + 1\) is an odd number. Let \(\frac{t}{2}=\sum_{i=0}^k c_k\cdot 2^k\), then \(t + 1=2\cdot \frac{t}{2}+1=2\sum_{i=0}^k c_i\cdot 2^i+1=\sum_{i=1}^{k+1}c_{i-1}\cdot 2^i+1\cdot 2^0\).
If \(t+1\) is an even number. Let \(\frac{t + 1}{2}=\sum_{i=0}^k c_i\cdot 2^i\), then \(t+1=2\cdot\frac{t+1}{2}=2\sum_{i=0}^k c_i\cdot 2^i=\sum_{i=1}^{k+1} c_i\cdot 2^i+0\cdot 2^0\).
In all, the proposition holds.
Let \(P(n)\) be the proposition that \(2\mid F_{3n}\). Let’s prove it by induction.
Base Case: When \(n=1\), \(F_{3n}=2\) so \(2\mid F_{3n}\).
Induction Hypothesis: We assume that \(2\mid F_{3k}\) when \(k\in\mathbb{N}\).
Induction Step:
\[\begin{aligned} F_{3(k+1)}&\equiv F_{3k+3}\pmod 2\\ &\equiv F_{3k+2}+F_{3k+1}\pmod 2\\ &\equiv F_{3k+1}+F_{3k}+F_{3k+1}\pmod 2\\ &\equiv 2F_{3k+1}+F_{3k}\pmod 2\\ &\equiv 0\pmod 2 \end{aligned}\]So \(2\mid F_{3(k+1)}\).
In all, \(\forall n\in \mathbb{N}, 2\mid F_{3n}\).
Let the prices for an apple, for a beet, and for a carrot be \(a, b, c\) separately. Then we have:
\[\begin{bmatrix} 1 & 1 & 1 \\ 2 & 3 & 0 \\ 1 & 2 & 3 \end{bmatrix} \cdot \begin{bmatrix} a\\ b\\ c \end{bmatrix} = \begin{bmatrix} 16\\ 23\\ 35 \end{bmatrix}\]A = [1 1 1; 2 3 0; 1 2 3];
b = [16; 23; 35];
x = inv(A) * b;
disp(x);
Solving this equation, we get \(x=\begin{bmatrix}4&5&7\end{bmatrix}^{\mathrm{T}}\). So \(a=4, b=5, c=7\).
(a)
\[\begin{aligned} \int_{0}^{\infty}e^{-t}\sin t\ \mathrm{d}t&=-\int_{0}^{\infty}\sin t\ \mathrm{d}\left(e^{-t}\right)\\ &=-\left(\left(\sin(t)\cdot e^{-t}\right)_0^{\infty}-\int_{0}^\infty e^{-t}\ \mathrm{d}(\sin t)\right)\\ &=\int_{0}^{\infty}e^{-t}\cos t\ \mathrm{d}t\\ &=-\int_{0}^{\infty}\cos t\ \mathrm{d}\left(e^{-t}\right)\\ &=-\left(\left(e^{-t}\cos t\right)_{0}^{\infty}-\int_{0}^{\infty}e^{-t}\ \mathrm{d}(\cos t)\right)\\ &=\int_{0}^{\infty}e^{-t}\ \mathrm{d}(\cos t)-\left(e^{-t}\cos t\right)_{0}^{\infty}\\ &=-\int^\infty_0e^{-t}\sin t\ \mathrm{d}t+1 \end{aligned}\]So,
\[\int_{0}^{\infty}e^{-t}\sin t\ \mathrm{d}t=-\int_{0}^{\infty}e^{-t}\sin t\ \mathrm{d}t+1.\]Which is
\[\int_{0}^{\infty}e^{-t}\sin t\ \mathrm{d}t=\frac{1}{2}.\]syms x;
disp(int(sin(x) * exp(-x), 0, inf));
(b)
\[f'(x)=2x\cdot e^{-x^4}\]Since \(e^{-x^4}>0\), \(f'(x)<0\) when \(x<0\) and \(f'(x)>0\) when \(x>0\).
So when \(x=0\), the minimum value of \(f(x)\) is \(0\).
(c)
\[\begin{aligned} \iint_R 2x+y\ \mathrm{d}A&=\int_0^1\mathrm{d}x\int_{0}^{x}2x+y\ \mathrm{d}y\\ &=\int_{0}^{1}\left(2xy+\frac{1}{2}y^2\right)_{y=0}^{y=x}\mathrm{d}x\\ &=\int_{0}^{1}\frac{5}{2}x^2\ \mathrm{d}x\\ &=\frac{5}{6} \end{aligned}\](a) True.
(b) False. Let \(Q(x, y)\) be \(x=y\).
(c) True. For all \(y\), we just choose the \(x\) previously selected.
(d) True.
(a) True.
\[\begin{aligned} \forall x\ (P(x)\land Q(x))&\equiv\bigwedge_{x}(P(x)\land Q(x))\\&\equiv\left(\bigwedge_x P(x)\right)\land\left(\bigwedge_x Q(x)\right)\\ &\equiv \left(\forall x\ P(x)\right)\land\left(\forall x\ Q(x)\right) \end{aligned}\](b) False.
Let \(P(x)=(x>0), Q(x)=(x\le 0)\). \(\forall x\ (P(x)\land Q(x))\) is true but \(\left(\forall x\ P(x)\right)\lor\left(\forall x\ Q(x)\right)\) is false.
(c) True.
\[\begin{aligned} \exists x\ (P(x)\lor Q(x))&\equiv\bigvee_{x}(P(x)\lor Q(x))\\&\equiv\left(\bigvee_x P(x)\right)\lor\left(\bigvee_x Q(x)\right)\\ &\equiv \left(\exists x\ P(x)\right)\lor\left(\exists x\ Q(x)\right) \end{aligned}\](d) False.
Let \(P(x)=(x=2)\) and \(Q(x)=(x=3)\). \(\mathrm{LHS}\) is false but \(\mathrm{RHS}\) is true.
(a)
\[\begin{aligned} &x\in f^{-1}(A\cap B)\\ \Longleftrightarrow\ &f(x)\in A\cap B\\ \Longleftrightarrow\ &\left(f(x)\in A\right)\land \left(f(x)\in B\right)\\ \Longleftrightarrow\ &\left(x\in f^{-1}(A)\right)\land \left(x\in f^{-1}(B)\right)\\ \Longleftrightarrow\ &x\in f^{-1}(A)\cap f^{-1}(B) \end{aligned}\]So \(f^{-1}(A\cap B)=f^{-1}(A)\cap f^{-1}(B)\).
(b)
\[\begin{aligned} &x\in f^{-1}(A\setminus B)\\ \Longleftrightarrow\ &f(x)\in A\setminus B\\ \Longleftrightarrow\ &(f(x)\in A)\land (f(x)\not\in B)\\ \Longleftrightarrow\ &(x\in f^{-1}(A))\land (x\not\in f^{-1}(B))\\ \Longleftrightarrow\ &x\in f^{-1}(A)\setminus f^{-1}(B) \end{aligned}\]So \(f^{-1}(A\setminus B)=f^{-1}(A)\setminus f^{-1}(B)\).
(c)
\[\begin{aligned} &y\in f(A\cap B)\\ \Longleftrightarrow\ &\exists x\in A\cap B, f(x)=y\\ \implies&(\exists x \in A, f(x)=y)\land (\exists x\in B, f(x)=y)\\ \Longleftrightarrow\ &(y\in f(A))\land (y\in f(B))\\ \Longleftrightarrow\ &y\in f(A)\cap f(B) \end{aligned}\]So \(f(A\cap B)\subseteq f(A)\cap f(B)\).
The counterexample for \(f(A\cap B)= f(A)\cap f(B)\) is when \(A=\{2\}\) and \(B = \{-2\}\), and we let \(f(x)=x^2\). \(f(A\cap B)=\emptyset\) but \(f(A)\cap f(B)=\{4\}\).
(d)
\[\begin{aligned} &y\in f(A\setminus B)\\ \Longleftrightarrow\ &\exists x\in A\setminus B, f(x)=y\\ \impliedby\ &(\exists x \in A, f(x)=y)\land (\forall x\in B, f(x)\neq y)\\ \Longleftrightarrow\ &(y\in f(A))\land (y\not\in f(B))\\ \Longleftrightarrow\ &y\in f(A)\setminus f(B) \end{aligned}\]So \(f(A\setminus B)\supseteq f(A)\setminus f(B)\).
The counterexample for \(f(A\setminus B)= f(A)\setminus f(B)\) is when \(A=\{-2, 2\}\) and \(B = \{-2\}\), and we let \(f(x)=x^2\). \(f(A\setminus B)=\{4\}\) but \(f(A)\cap f(B)=\emptyset\).
(a) True. Let \(n=2k+1\), \(k\in \mathbb{Z}\). \(n^2+4n=4k^2+12k+5\) is an odd number.
(b) True.
\[\begin{aligned} &a + b\le 15\implies (a\le 11) \lor (b\le 4)\\ \equiv\ &\lnot((a\le 11) \lor (b\le 4))\implies \lnot(a + b\le 15)\\ \equiv\ &(a > 15)\land (b>4)\implies a + b > 15 \end{aligned}\](c) True.
\[\begin{aligned} &r^2\not\in \mathbb{Q}\implies r \not\in \mathbb{Q}\\ \equiv\ &\lnot(r \not\in \mathbb{Q})\implies \lnot(r^2\not\in \mathbb{Q})\\ \equiv\ &r \in \mathbb{Q}\implies r^2\in \mathbb{Q} \end{aligned}\]Let \(r=\frac{p}{q}\), where \(p, q\in \mathbb{Z}\) and \(\gcd(p, q) = 1\). \(r^2=\frac{p^2}{q^2}\in\mathbb{Q}\).
(d) False.
from math import factorial
if __name__ == "__main__":
n = 10
print(5 * n ** 3 > factorial(n))
We use proof by contradiction. Let \(x\in \mathbb{Q}, y\in\mathbb{R}\setminus\mathbb{Q}, z\in\mathbb{Q}\) and \(z=xy\).
But \(y = \frac{z}{x}\in \mathbb{Q}\), which conflicts with \(y\in \mathbb{R}\setminus\mathbb{Q}\), so \(z\) must be irrational.
(a) If \(3\mid p\), \(p\) is not a prime number. So \(3\nmid p\). So \(p\equiv 1\pmod 3\) or \(p\equiv 2\equiv -1\pmod 3\).
So \(p\) is of the form \(3k + 1\) or \(3k - 1\) for some integer \(k\).
(b) If the three prime numbers are \(p, p + 2, p + 4\ (p>3)\), we could let \(p=3k\pm 1\).
If \(p=3k + 1\), we have \(p + 2=3k + 3 = 3(k + 1)\) is not a prime number.
If \(p=3k - 1\), we have \(p + 4 = 3k + 3 = 3(k + 1)\).
So \(5\) is the only prime number that takes part in two different twin prime pairs.