MA0301/exam/main.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}