UCB EECS 70 Discrete Mathematics and Probability Theory

1 Truth Tables

(a)

When $P=\mathtt{T},Q=\mathtt{F}$, $\mathrm{LHS}=\mathtt{T}$ but $\mathrm{RHS}=\mathtt{F}$.

So $\mathrm{LHS}\not\equiv \mathrm{RHS}$.

(b)

So $\mathrm{LHS}\equiv \mathrm{RHS}$.

1
2
3
4
5
6
7
8

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)

So $\mathrm{LHS}\equiv \mathrm{RHS}$.

1
2
3
4
5
6
7
8

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='|')

2 Propositional Practice

(a)

$$\exist x\in\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 \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.

3 Converse and Contrapositive

(a)

$$\forall n\in\N, (4\mid n\implies 2\mid n).$$

It is true.

We let $n=4k, k\in \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\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\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$.

4 Equivalences with Quantifiers

(a)

$$\begin{aligned} \mathrm{LHS}&\equiv\forall x\ ((\exist y\ Q(x, y))\implies P(x))\\ &\equiv \forall x\ (\lnot(\exist 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\exist 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$, $\exist 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\exist y\ \left(\lnot\left(P(x, y)\implies \lnot Q(x, y)\right)\right)\\ &\equiv\forall x\exist y\ \left(\lnot\left(\lnot P(x, y)\lor \lnot Q(x, y)\right)\right)\\ &\equiv\forall x\exist y\ \left(P(x, y)\land Q(x, y)\right)\\ &\not\equiv\forall x\left((\exist y\ P(x, y))\land (\exist 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 $\exist y\ P(x, y)$, we just let $y=x$, so it is true. And for $\exist 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\exist y\ (\lnot P(x)\lor Q(x,y))\\ \mathrm{RHS}&\equiv\forall x\ (\lnot P(x)\lor(\exist y\ Q(x, y))) \end{aligned}$$

If $P(x)$ is true, $\mathrm{LHS}\equiv \forall x\exist y\ (\mathtt{F}\lor Q(x, y))\equiv \forall x\exist y\ Q(x, y)$, $\mathrm{RHS}\equiv\forall x\ (\mathtt{F}\lor (\exist y\ Q(x, y)))\equiv \forall x\exist 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}$.

5 Propositional Practice

(a)

$$\exist x\in\R\ ((x^2=0)\land(\forall y\in\R\ ((y^2=0)\implies (x=y)))).$$

(b)

$$\forall x\in\mathbb{Q}\ \forall y\in\mathbb{Q}\ \exist z\in \mathbb{Q}\ ((x=y)\lor (x<y<z)\lor(x>y>z)).$$

(c)

$$\forall x\in\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.

9 Exercises

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 \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\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 \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\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 \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\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:

1. If A don’t know B. Then we could know that B is not celebrity. So we could just firstly remove B and solve the remaining $k$ people to find the “celebrity” for these $k$ people, which is C. (If now found, just return “not found”.) And after that, we should check if B knows C and C doesn’t know B. It cost $f(k + 1)=3+f(k)\le 3+(3k-4)=3(k+1)-4$.
2. If A knows B. Then we could know that A is not celebrity. Then we can prove as in the first case, changing B to A.

So $f(k+1)\le 3(k+1)-4$. And as a conclusion, $f(n)\le 3n-4$ holds for all $n\in\N, n\ge 2$.

5. The python code shows below:

1
2
3

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$.

1 Contraposition

$$\begin{aligned} &(a+b<c+d)\implies (a<c)\lor(b<d)\\ \equiv& \lnot((a<c)\lor(b<d))\implies \lnot(a+b<c+d)\\ \equiv & (a\ge c)\land(b\ge d) \implies (a+b\ge c+d) \end{aligned}$$

2 Numbers of Friends

We let the $i$-th person have $a_i$ friends. We have $a_i\in[0, n-1]\cap \Z$.

Then we check if there exist $k\in [0, n-1]\cap\Z$, $\forall i, a_i\neq k$.

1. $\exist k\in [0, n-1]\cap\Z, \forall i, a_i\neq k$. Which means, $\forall i, a_i\in [0, n-1]\cap\Z\backslash\{k\}$. And since $\left|[0, n-1]\cap\Z\backslash\{k\}\right|=n-1$, and there are $n$ numbers. Due to the Pigeonhole Principle, there must be $2$ of them have the same number.
2. If $\forall k\in [0, n-1]\cap\Z, \exist i, a_i=k$, there must be some one with $0$ friends (name A) and some one with $n-1$ friends (name B). A have $0$ friends shows that A and B are not friends, but B have $n-1$ friends shows that A and B are friends. This forms a contradiction, so this case is impossible.

In all, there must be at least $2$ of them have the same number of friends at the party.

3 Pebbles

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.

4 Preserving Set Operations

(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 $\exist y\in A\cup B, f(y)=x$. So $\exist y\in A, f(y)=x$ or $\exist 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 $\exist y\in A, x=f(y)$ or $\exist y\in B, x = f(y)$. So $\exist 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)$.

1 Natural Induction on Inequality

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 \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\N, x>0, \ (1+x)^n\ge 1+nx$ holds.

2 Make It Stronger

(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 \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\N^+$, $a_n\le 3^{2^n-1}$.

(c) For $n\in\N$, $a_n\le 3^{2^n-1}=\frac{1}{3}\cdot 3^{2^n}\le 3^{2^n}$.

3 Binary Numbers

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.

4 Fibonacci for Home

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\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 \N, 2\mid F_{3n}$.

1 Solving a System of Equations

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}$$

1
2
3
4

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$.

2 Calculus Review

(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}.$$

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}$$

3 Implication

(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.

4 Logical Equivalence?

(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} \exist 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(\exist x\ P(x)\right)\lor\left(\exist 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.

5 Preserving Set Operations

(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\ &\exist x\in A\cap B, f(x)=y\\ \implies&(\exist x \in A, f(x)=y)\land (\exist 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\ &\exist x\in A\setminus B, f(x)=y\\ \impliedby\ &(\exist 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$.

6 Prove or Disprove

(a) True. Let $n=2k+1$, $k\in \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}$$