Add many more solutions and notes

1 files changed, 169 insertions, 0 deletions

diff --git a/sem6/dig/mm1/opgaver.tex b/sem6/dig/mm1/opgaver.tex
new file mode 100644
index 0000000..4b8dc91
--- /dev/null
+++ b/sem6/dig/mm1/opgaver.tex
@@ -0,0 +1,169 @@
+\title{Opgaver til Lektion 1}
+
+\let\inv\overline
+
+\section{Opgave 1}
+
+Perfect induction af $(A + B) \cdot (A + C) = A + (B \cdot C)$:
+
+\begin{tabular}{lll|ll} \toprule
+    $A$ & $B$ & $C$ & $(A + B) \cdot (A + C)$ & $A + (B \cdot C)$ \\ \midrule
+    0 & 0 & 0 & 0 & 0 \\
+    0 & 0 & 1 & 0 & 0 \\
+    0 & 1 & 0 & 0 & 0 \\
+    0 & 1 & 1 & 1 & 1 \\
+    1 & 0 & 0 & 1 & 1 \\
+    1 & 0 & 1 & 1 & 1 \\
+    1 & 1 & 0 & 1 & 1 \\
+    1 & 1 & 1 & 1 & 1 \\ \bottomrule
+\end{tabular}
+
+Perfect induction af $A \cdot (A + B) = A$:
+
+\begin{tabular}{ll|ll} \toprule
+    $A$ & $B$ & $A + B$ & $A$ \\ \midrule
+    0 & 0 & 0 & 0 \\
+    0 & 1 & 0 & 0 \\
+    1 & 0 & 1 & 1 \\
+    1 & 1 & 1 & 1 \\ \bottomrule
+\end{tabular}
+
+Perfect induction of $A + \inv{A} = 1$:
+
+\begin{tabular}{l|ll} \toprule
+    $A$ & $A + \inv{A} $ & $1$ \\ \midrule
+    0 & 1 & 1 \\
+    1 & 1 & 1 \\ \bottomrule
+\end{tabular}
+
+Perfect induction of $\inv{A + B + C} = \inv{A} \cdot \inv{B} \cdot \inv{C}$:
+
+\begin{tabular}{lll|ll} \toprule
+    $A$ & $B$ & $C$ & $\inv{A + B + C}$ & $\inv{A} \cdot \inv{B} \cdot \inv{C}$ \\ \midrule
+    0 & 0 & 0 & 1 & 1 \\
+    0 & 0 & 1 & 0 & 0 \\
+    0 & 1 & 0 & 0 & 0 \\
+    0 & 1 & 1 & 0 & 0 \\
+    1 & 0 & 0 & 0 & 0 \\
+    1 & 0 & 1 & 0 & 0 \\
+    1 & 1 & 0 & 0 & 0 \\
+    1 & 1 & 1 & 0 & 0 \\ \bottomrule
+\end{tabular}
+
+\section{Opgave 2}
+
+\begin{opg}
+    Show that the following
+
+    \begin{equation*}
+        R = \inv{\inv{A \cdot \inv{B}} \cdot \inv{\inv{A} \cdot B}}
+    \end{equation*}
+
+    is XOR.
+\end{opg}
+
+Man kan skrive XOR operator som:
+\begin{equation*}
+    A \oplus B = (A + B) \cdot \inv{(A \cdot B)}
+\end{equation*}
+
+\begin{tabular}{ll|ll} \toprule
+    $A$ & $B$ & $A \oplus B$ & $(A + B) \cdot \inv{(A \cdot B)}$ \\ \midrule
+    0 & 0 & 0 & 0 \\
+    0 & 1 & 1 & 1 \\
+    1 & 0 & 1 & 1 \\
+    1 & 1 & 0 & 0 \\ \bottomrule
+\end{tabular}
+
+Kan herefter vise at dette er $\inv{\inv{A \cdot \inv{B}} \cdot \inv{\inv{A} \cdot B}}$.
+\begin{equation*}
+    \inv{\inv{A \cdot \inv{B}} \cdot \inv{\inv{A} \cdot B}} = (A + B) \cdot \inv{(A \cdot B)}\\
+\end{equation*}
+Vi kan starte med at bruge DeMorgans lov.
+\begin{equation*}
+    = (A + B) \cdot (\inv{A} + \inv{B}) \\
+\end{equation*}
+Man kan skrive det ud.
+\begin{equation*}
+    = A \cdot \inv{A} + A \cdot \inv{B} + B \cdot \inv{A} + B \cdot \inv{B}
+\end{equation*}
+Vi kan bruge axiomen $X \cdot \inv{X} = 0$.
+\begin{equation*}
+    = A \cdot \inv{B} + B \cdot \inv{A}
+\end{equation*}
+Og nu kan vi bruge DeMorgans lov på venstre side.
+\begin{equation*}
+    \inv{ \inv{A \cdot \inv{B}}} + \inv{ \inv{\inv{A} \cdot B}} = A \cdot \inv{B} + B \cdot \inv{A}
+\end{equation*}
+Og dette passer hvis man lader inverserne gå ud med hinnanden.
+
+\section{Opgave 3}
+
+\begin{opg}
+    Reduce the following expressions:
+    \begin{align*}
+        A \cdot \inv{B} \cdot \inv{C} + A \cdot B \cdot \inv{C} + \inv{A} \cdot \inv{C} \\
+        M \cdot \inv N \cdot P + \inv L \cdot M \cdot P + \inv L \cdot M \cdot \inv N + \inv L \cdot M \cdot N \cdot \inv P + \inv L \cdot \inv N \cdot \inv P
+    \end{align*}
+\end{opg}
+
+Vi starter med den første opgave.
+Her tager vi og bruger den distributive teorem et par gange.
+\begin{equation*}
+    \begin{split}
+        \inv{C} \cdot (A \cdot \inv B + A \cdot B + \inv A) \\
+        \inv{C} \cdot (A \cdot (\inv B + B) + \inv A)
+    \end{split}
+\end{equation*}
+Nu kan vi bruge axiomen \(X + \inv X = 1\) og \(X \cdot 1 = X\).
+\[
+    \inv C \cdot (A + \inv A) = \inv C
+\]
+
+Lad og tage den anden.
+Vi starter med at bruge den distributive teorem et par gange.
+\begin{equation*}
+    \begin{split}
+        M \cdot (\inv N \cdot P + \inv L \cdot P + \inv L \cdot \inv N + \inv L \cdot N \cdot \inv P) + \inv L \cdot \inv N \cdot \inv P \\
+        M \cdot (\inv N \cdot P + \inv L \cdot (P + \inv N + N \cdot \inv P)) + \inv L \cdot \inv N \cdot \inv P
+    \end{split}
+\end{equation*}
+Den inerste parantes er på formen $A + B + \inv A \cdot \inv B$.
+Dette kan vise altid er lig med $1$, ved at starte med DeMorgans lov.
+\[
+    A + B + \inv{A + B}
+\]
+Ud fra axiomen $X + \inv X = 1$ kan vi se at dette altid er 1.
+Nu kan vi sætte dette ind og bruge den distributive lov igen omvendt.
+\[
+    M \cdot (\inv N \cdot P + \inv L) + \inv L \cdot \inv N \cdot \inv P = M \cdot \inv N \cdot P + M \cdot \inv L + \inv L \cdot \inv N \cdot \inv P
+\]
+Mere kan jeg desværre ikke reducere den.
+
+\section{Opgave 4}
+
+\begin{opg}
+    Find expression
+\end{opg}
+
+\begin{verbatim}
+X = ~(A * B)
+Y = ~(A * X)
+Z = ~(B * X)
+C = ~(Y * Z)
+D = ~X
+
+C = ~(~(A * ~(A * B)) * ~(B * ~(A * B)))
+D = ~~(A * B) = A * B
+\end{verbatim}
+
+
+\section{Gate Input Cost}
+
+Skriver lige hurtigt formlen op for GIC.
+\begin{verbatim}
+    GIC = LC + number of terms in boolean expr + number of unique inversions
+\end{verbatim}
+Her er LC litteral cost, hvilket er antallet af ikke unikke variabler.
+
+GIC kan også findes ved at tælle antal inputs i et logic diagram.