1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tex/theory1_ex9.tex Mon Jul 18 20:17:25 2011 +0200
1.3 @@ -0,0 +1,46 @@
1.4 +\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
1.5 +\usepackage{graphicx}
1.6 +%\usepackage[latin1]{inputenc}
1.7 +\usepackage{amsmath, amsthm, amssymb}
1.8 +\usepackage{typearea}
1.9 +\usepackage{algorithm}
1.10 +\usepackage{algorithmic}
1.11 +\usepackage{fullpage}
1.12 +\usepackage{mathtools}
1.13 +\usepackage[all]{xy}
1.14 +\title{Theory I, Sheet 9 Solution}
1.15 +\author{Eugen Sawin}
1.16 +\renewcommand{\familydefault}{\sfdefault}
1.17 +\newcommand{\Pos}{\mathcal{P}os}
1.18 +\newcommand{\E}{\mathcal{E}}
1.19 +\newcommand{\D}{\mathcal{D}}
1.20 +\newcommand{\J}{\mathcal{J}}
1.21 +\include{pythonlisting}
1.22 +
1.23 +\pagestyle{empty}
1.24 +\begin{document}
1.25 +\maketitle
1.26 +
1.27 +\section*{Exercise 9.1.3}
1.28 +\begin{align*}
1.29 +ADT_{bool} = &(\Sigma_{bool}, \E)\\
1.30 +\Sigma_{bool} = &\{true^{(0)}, false^{(0)}, not^{(1)}, and^{(2)}, or^{(2)}\}\\
1.31 +\E = &\{true \approx not(false),\\
1.32 +& false \approx not(true),\\
1.33 +& not(not(x)) \approx x\\
1.34 +& and(x, y) \approx not(or(not(x), not(y))),\\
1.35 +& or(x, y) \approx not(and(not(x), not(y)))\}\\
1.36 +\end{align*}
1.37 +
1.38 +\section*{Exercise 9.1.4}
1.39 +\begin{align*}
1.40 +\D_{bool} &= (M, \J)\\
1.41 +M &= \{0, 1\}\\
1.42 +\J(true) &= 1\\
1.43 +\J(false) &= 0\\
1.44 +\J(not)(x) &= 1 - x\\
1.45 +\J(and)(x, y) &= min(x, y)\\
1.46 +\J(or)(x, y) &= max(x, y)\\
1.47 +\end{align*}
1.48 +
1.49 +\end{document}