349 lines
7.0 KiB
TeX
349 lines
7.0 KiB
TeX
\documentclass[12pt]{article}
|
|
\usepackage{ntnu}
|
|
\usepackage{ntnu-math}
|
|
\usepackage{ntnu-code}
|
|
|
|
\author{10112}
|
|
\title{MA0301 Spring 2021}
|
|
|
|
\usetikzlibrary{automata, positioning, arrows.meta}
|
|
|
|
\newcommand{\I}{\Huge\textbf{I}}
|
|
\newcommand{\II}{\Huge\textbf{I\!I}}
|
|
\newcommand{\III}{\Huge\textbf{I\!I\!I}}
|
|
|
|
\usepackage{listings}
|
|
\usepackage{blkarray}
|
|
|
|
\renewcommand{\theenumi}{\arabic{enumi}}
|
|
\renewcommand{\theenumii}{(\arabic{enumii})}
|
|
\renewcommand{\theenumiii}{\alph{enumiii})}
|
|
|
|
|
|
\newcommand{\checkEdge}[3]{
|
|
Find next edge with the minimum weight. \\
|
|
The edge between #1 and #2 has weight #3. \\
|
|
Does adding it connect two separate subgraphs? \\
|
|
}
|
|
\newcommand{\yes}{\textbf{Yes. Add edge} \\[2ex]}
|
|
\newcommand{\no}{\textbf{No. Discard edge} \\[2ex]}
|
|
|
|
\begin{document}
|
|
|
|
%%%%%%%% 2
|
|
|
|
\begin{align*}
|
|
\neg (\exists x \forall y (\neg P(x,y) \wedge Q(x,y))) \\
|
|
\forall x \exists y \neg(\neg P(x,y) \wedge Q(x,y)) \\
|
|
\forall x \exists y (\neg \neg P(x,y) \vee \neg Q(x,y)) \\
|
|
\forall x \exists y (P(x,y) \vee \neg Q(x,y)) \\
|
|
\end{align*}
|
|
|
|
%%%%%%%% 3
|
|
\break
|
|
|
|
1.
|
|
|
|
\input{graphics/3.tex}
|
|
|
|
2.
|
|
|
|
By looking at the truthtable, we can see that $\neg p \not\equiv \neg(p \wedge q)$ \\
|
|
|
|
3.
|
|
|
|
\begin{gather*}
|
|
(p \downarrow q) \downarrow (p \downarrow q) \\
|
|
\neg ( \neg (p \wedge q) \wedge \neg (p \wedge q)) \\
|
|
\neg ( (\neg p \vee \neg q) \wedge (\neg p \vee \neg q)) \\
|
|
\neg (\neg p \vee \neg q) \vee \neg (\neg p \vee \neg q)) \\
|
|
\neg \neg p \vee \neg \neg q \vee \neg \neg p \vee \neg \neg q \\
|
|
p \vee q \vee p \vee q \\
|
|
p \vee q \\
|
|
\end{gather*}
|
|
|
|
\[ (p \downarrow q) \downarrow (p \downarrow q) \equiv p \vee q \]
|
|
|
|
|
|
%%%%%%%% 5
|
|
\break
|
|
|
|
\[ R := \{ (0,0), (1,1), (2,2), (2,3) \} \]
|
|
|
|
$R$ is not an equivalence relation. \\
|
|
|
|
For reflexivity, it's missing one relation
|
|
|
|
\[ (3,3) \]
|
|
|
|
For symmetry, it's missing one relation
|
|
|
|
\[ (3,2) \]
|
|
|
|
For transitivity, it will by now have all missing elements \\
|
|
|
|
\[ (2,3) \text{ and } (3,2) \rightarrow (2,2) \]
|
|
\[ (3,2) \text{ and } (2,3) \rightarrow (3,3) \]
|
|
|
|
\[ R := \{ (0,0),(1,1),(2,2),(2,3), (3,2), (3,3) \} \]
|
|
|
|
%%%%%%%% 6
|
|
\break
|
|
|
|
\[ A := \{3, 4, 6, 12, 20 \} \]
|
|
|
|
\includeDiagram[scale=2, width=5cm]{graphics/6.tex}
|
|
|
|
\center
|
|
By looking at the hasse diagram, we can see that
|
|
|
|
\[ \text{Minimal elements: } \{ 3, 4 \} \]
|
|
\[ \text{Maximal elements: } \{ 12, 20 \} \]
|
|
|
|
%%%%%%%% 7
|
|
\break
|
|
|
|
Base case:
|
|
|
|
\begin{align*}
|
|
\sum^3_{i=3} 3^i = \frac{3(3^3-9)}{2} \\[2ex]
|
|
3^3 = \frac{3(27-9)}{2} \\[2ex]
|
|
27 = \frac{3(18)}{2} \\[2ex]
|
|
27 = 9 \cdot 3 \\[2ex]
|
|
27 = 27 \\[2ex]
|
|
\end{align*}
|
|
|
|
Assume that
|
|
|
|
\[ \sum^n_{i=3} 3^i = \frac{3(3^n-9)}{2} \qquad \text{for } n > 2 \]
|
|
|
|
Then
|
|
|
|
\begin{align*}
|
|
\sum^{n+1}_{i=3} 3^i &= 3^3 + 3^4 + \ldots + 3^n + 3^{n+1} \\[2ex]
|
|
&= \frac{3(3^n-9)}{2} + 3^{n+1} \\[2ex]
|
|
&= \frac{3^{n+1} - 3 \cdot 9 + 2 \cdot 3^{n+1}}{2} \\[2ex]
|
|
&= \frac{3 \cdot 3^{n+1} - 3 \cdot 9}{2} \\[2ex]
|
|
&= \frac{3(3^{n+1} - 9)}{2} \\[2ex]
|
|
\end{align*}
|
|
|
|
\qed
|
|
|
|
%%%%%%%% 8
|
|
\break
|
|
|
|
\[
|
|
\{ a_n \}_{n>0} =
|
|
\begin{cases}
|
|
a_1 = 3 \\
|
|
a_2 = 6 \\
|
|
a_n = a_n + a_{n-1} \quad \text{for } n > 2 \\
|
|
\end{cases}
|
|
\]
|
|
|
|
\textbf{Base case:}
|
|
|
|
For $a_3$, we have that
|
|
|
|
\begin{align*}
|
|
a_3 &= a_2 + a_1 \\
|
|
&= 6 + 3 \\
|
|
&= 3(3) \\
|
|
&\Rightarrow a_3 \bmod 3 = 0
|
|
\end{align*}
|
|
|
|
For $a_4$, we have that
|
|
|
|
\begin{align*}
|
|
a_4 &= a_3 + a_2 \\
|
|
&= 9 + 6 \\
|
|
&= 3(5) \\
|
|
&\Rightarrow a_4 \bmod 3 = 0
|
|
\end{align*}
|
|
|
|
\textbf{Inductive step:}
|
|
|
|
Assume that for $k_1 \in \N$, $k_2 \in \N$:
|
|
|
|
\begin{align*}
|
|
a_n &= 3(k_1) \\
|
|
a_{n-1} &= 3(k_2) \\
|
|
\end{align*}
|
|
|
|
Then
|
|
|
|
\begin{align*}
|
|
a_{n+1} &= a_n + a_{n-1} \\
|
|
&= 3(k_1) + 3(k_2) \\
|
|
&= 3(k_1 + k_2) \\
|
|
&\Rightarrow a_{n+1} \bmod 3 = 0
|
|
\end{align*}
|
|
|
|
\qed
|
|
|
|
|
|
%%%%%%%% 10
|
|
\break
|
|
|
|
\[ f : \Z \rightarrow \Z \]
|
|
\[ f(x) = x-7 \]
|
|
|
|
\textbf{Injective:}
|
|
|
|
In order for $f(x)$ to be injective, it has to hold that
|
|
|
|
\[ f(a) = f(b) \Rightarrow a = b \]
|
|
|
|
\begin{align*}
|
|
f(a) &= f(b) \\
|
|
a - 7 &= b - 7 \\
|
|
a &= b \\
|
|
\end{align*}
|
|
|
|
Hence $f(x)$ is injective. \\
|
|
|
|
|
|
\textbf{Surjective:}
|
|
|
|
In order for $f(x)$ to be surjective, it has to hold that
|
|
|
|
\[ \forall x \in \Z \exists y \in \Z [f(x) = y] \]
|
|
|
|
\begin{align*}
|
|
y &= x - 7 \\
|
|
x &= y + 7 \\
|
|
\end{align*}
|
|
|
|
$ x = y + 7 $ makes up all the elements in $\Z$
|
|
|
|
\begin{align*}
|
|
f(x) &= x - 7 \\
|
|
&= (y + 7) - 7 \\
|
|
&= y
|
|
\end{align*}
|
|
|
|
Hence $f(x)$ is surjective \\
|
|
|
|
\textbf{Conclusion:}
|
|
|
|
Since $f(x)$ is both injective and surjective, it is by definition bijective
|
|
|
|
|
|
%%%%%%%% 11
|
|
\break
|
|
|
|
There are no $x^6y^6$ in the expansion of $(3x^5 + 2y)^6$ \\
|
|
|
|
For $x^{10}y^4$, there is
|
|
|
|
\[ \binom{6}{4}(3x^5)^{6-4}(2y)^4 = 2160 x^{10}y^4 \]
|
|
|
|
%%%%%%%% 12
|
|
\break
|
|
|
|
The number of permutations of the letters "ALLTALK" is
|
|
|
|
\[ \frac{7!}{(7-7)!2!3!} = 420 \]
|
|
|
|
If all of the Ls has to be together, we can think of this block like one letter. \\
|
|
|
|
That leaves us with 5 letters, where one of them is repeated once. \\
|
|
|
|
\[ \frac{5!}{(5-5)!2!} = 60 \]
|
|
|
|
%%%%%%%% 14
|
|
\break
|
|
|
|
\includeDiagram{graphics/14mod.tex}
|
|
|
|
Assuming the automation is starting at $s_0$, the output for $acabacab$ would be
|
|
|
|
\begin{gather*}
|
|
s_0 \xrightarrow{a,0} s_1 \\
|
|
s_1 \xrightarrow{c,0} s_0 \\
|
|
s_0 \xrightarrow{a,0} s_1 \\
|
|
s_1 \xrightarrow{b,0} s_0 \\
|
|
s_0 \xrightarrow{a,0} s_1 \\
|
|
s_1 \xrightarrow{c,0} s_0 \\
|
|
s_0 \xrightarrow{a,0} s_1 \\
|
|
s_1 \xrightarrow{b,0} s_0 \\
|
|
\end{gather*}
|
|
|
|
\[ 00000000 \]
|
|
|
|
%%%%%%%% 15
|
|
\break
|
|
|
|
$L$ is a language that only contains words which fits the regular expresson $r$, where
|
|
|
|
\[ r = b^*ab^*ab^* \]
|
|
|
|
or described with words, \\
|
|
|
|
\center "$L$ is a language that only has words that contain exactly two of the letter $a$"
|
|
|
|
%%%%%%%% 16
|
|
\break
|
|
|
|
\[
|
|
\begin{blockarray}{cccccc}
|
|
& A & B & C & D & E \\
|
|
\begin{block}{c[ccccc]}
|
|
A & 0 & 1 & 1 & 0 & 1 \\
|
|
B & 1 & 0 & 0 & 1 & 1 \\
|
|
C & 1 & 0 & 0 & 0 & 0 \\
|
|
D & 0 & 1 & 0 & 0 & 1 \\
|
|
E & 1 & 1 & 0 & 1 & 0 \\
|
|
\end{block}
|
|
\end{blockarray}
|
|
\]
|
|
|
|
\includeDiagram{graphics/16.tex}
|
|
|
|
|
|
%%%%%%%% 17
|
|
\break
|
|
|
|
\includeDiagram[scale=1.6]{graphics/17.tex}
|
|
|
|
Performed Kruskal's algorithm as follows: \\[2ex]
|
|
|
|
\textbf{Remove all edges} \\
|
|
|
|
\checkEdge{1}{3}{1}
|
|
\yes
|
|
\checkEdge{2}{3}{2}
|
|
\yes
|
|
\checkEdge{7}{8}{2}
|
|
\yes
|
|
\checkEdge{3}{5}{3}
|
|
\yes
|
|
\checkEdge{4}{5}{4}
|
|
\yes
|
|
\checkEdge{6}{8}{5}
|
|
\yes
|
|
\checkEdge{5}{6}{6}
|
|
\yes
|
|
By now, the graph is already spanning so there aren't any more disconnected subgraphs to connect, but I'll check the last ones anyway, like for-looping over the set of edges in a computer program would. \\
|
|
|
|
\checkEdge{6}{7}{7}
|
|
\no
|
|
\checkEdge{5}{7}{8}
|
|
\no
|
|
\checkEdge{4}{6}{9}
|
|
\no
|
|
\checkEdge{2}{5}{10}
|
|
\no
|
|
\checkEdge{2}{4}{11}
|
|
\no
|
|
\checkEdge{1}{2}{12}
|
|
\no
|
|
|
|
\break{}
|
|
|
|
\textbf{Result: }
|
|
|
|
\includeDiagram[scale=1.6]{graphics/17_2.tex}
|
|
|
|
\end{document}
|