From 8d441de7fee53ce858441f0842c15505bee632d9 Mon Sep 17 00:00:00 2001
From: Peter Wu <peter@lekensteyn.nl>
Date: Mon, 9 Jan 2017 17:30:13 +0100
Subject: Part2: Initial questions typesetting

---
 part2.tex | 126 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 126 insertions(+)
 create mode 100644 part2.tex

(limited to 'part2.tex')

diff --git a/part2.tex b/part2.tex
new file mode 100644
index 0000000..b7d340b
--- /dev/null
+++ b/part2.tex
@@ -0,0 +1,126 @@
+\documentclass[12pt]{article}
+\usepackage{a4wide}
+\usepackage{latexsym}
+\usepackage{amssymb}
+\usepackage{epic}
+\usepackage{graphicx}
+\usepackage{gensymb}
+\usepackage{listings}
+\usepackage{tikz}
+\usepackage{amsmath}
+\usepackage{hyperref}
+\usepackage{float}
+%\pagestyle{empty}
+\newcommand{\tr}{\mbox{\sf true}}
+\newcommand{\fa}{\mbox{\sf false}}
+\newcommand{\bimp}{\leftrightarrow}     % bi-implication
+
+\title{Assignment part 2 for Automated Reasoning 2IMF25}
+\author{%
+    Peter Wu (0783206)\\
+    \texttt{s.p.wu@student.tue.nl}
+\and
+    Koen van der Heijden (0807929)\\
+    \texttt{k.p.l.v.d.heijden@student.tue.nl}
+}
+\date{\today}
+
+\begin{document}
+\maketitle
+
+\section*{Problem: food delivery}
+Four non-self-supporting villages A, B, C and D in the middle of nowhere consume
+one food package each per time unit. The required food packages are delivered by
+a truck, having a capacity of 240 food packages. The truck has to pick up its
+food packages at location S containing an unbounded supply. The locations of
+this supply location and the villages and the roads between them are shown in
+the following picture. Here every number indicates a distance, more precisely,
+the number of time units the truck needs to travel from one village to another,
+including loading and delivering. The villages only have a limited capacity to
+store food packages: for A this capacity is 120, for B and D it is 160, and for
+C it is 100. Initially, the truck is in S and is fully loaded, and in each of
+the four villages there are 80 food packages.
+
+\begin{tikzpicture}
+\node[circle,draw] (A) at (1,2) {A};
+\node[circle,draw] (B) at (5,2) {B};
+\node[circle,draw] (C) at (3,0.5) {C};
+\node[circle,draw] (D) at (7,0) {D};
+\node[circle,draw] (S) at (0,0) {S};
+
+\draw
+    (A) edge node[above]        {17} (B)
+    (A) edge node[above left]   {15} (S)
+    (A) edge node[above right]  {12} (C)
+    (S) edge node[above]        {15} (C)
+    (B) edge node[above left]   {10} (C)
+    (B) edge node[above right]  {20} (D)
+    (C) edge node[above]        {20} (D)
+    ;
+\end{tikzpicture}
+
+\begin{enumerate}
+\item[(a)] Show that it is impossible to deliver food packages in such a way
+that each of the villages consumes one food package per time unit forever.
+\item[(b)] Show that this is possible if the capacity of the truck is increased
+to 260 food packages. (Note that a finite graph contains an infinite path
+starting in a node $v$ if and only if there is a path from $v$ to a node $w$ for
+which there is a non-empty path from $w$ to itself.)
+\end{enumerate}
+
+\subsection*{Solution:}
+\subsubsection*{(a)}
+
+\subsubsection*{(b)}
+
+
+\section*{Problem: Nondeterministic finite automaton (NFA)}
+Let an NFA be defined as in Wikipedia \\
+\url{https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton}\\
+Find an NFA $M$ over $\sum = \{a, b\}$ with the least possible number of states
+for which the only non-empty words in $L(M)$ of length $<$ 5 are $aa$, $bb$,
+$aba$, $baa$, $abab$, $babb$ and $bbba$.
+
+\subsection*{Solution:}
+
+
+\section*{Problem: }
+The goal of this problem is to exploit the power of the recommended tools rather
+than elaborating the questions by hand.
+\begin{enumerate}
+\item[(a)] For a binary operator a we have the idempotence, commutativity and
+associativity rule, that is, the three rewrite rules
+\[
+a(x, x) \to x, a(x, y) \to a(y, x), a(x, a(y, z)) \to a(a(x, y), z).
+\]
+Figure out whether $a(p, a(q, a(p, a(q, a(p, a(q, p))))))$ rewrites to $a(p, q)$
+in a finite number of steps, for constants $p$, $q$.
+\item[(b)] In mathematics, a group is defined to be a set $G$ with an element
+$I \in G$, a binary operator $*$ and a unary operator $inv$ satisfying
+\[
+    x * (y * z) = (x * y) * z,\ x * I = x \text{ and } x * inv(x) = I,
+\]
+for all $x, y, z \in G$. Determine whether in every group each of the four properties
+\[
+    I * x = x,\ inv(inv(x)) = x,\ inv(x) * x = I \text{ and } x * y = y * x
+\]
+holds for all $x, y \in G$. If a property does not hold, determine the size of
+the smallest finite group for which it does not hold.
+\end{enumerate}
+
+\subsection*{Solution:}
+\subsubsection*{(a)}
+
+\subsubsection*{(b)}
+
+
+\section*{Problem: }
+Give a precise description of a non-trivial problem of your own choice, and
+encode this and solve it by one of the given programs.
+Here `trivial problems' include both minor modifications of earlier problems and
+single solutions of simply specified puzzles like sudokus. In case of doubt
+please contact the lecturer.
+
+\subsection*{Solution:}
+
+\end{document}
-- 
cgit v1.2.1

