MA0301/exam/main.tex

349 lines
7.0 KiB
TeX
Raw Permalink Normal View History

2021-08-29 19:57:57 +02:00
\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}