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