sawine@13: \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}  
sawine@13: \usepackage{graphicx}
sawine@13: %\usepackage[latin1]{inputenc}
sawine@13: \usepackage{amsmath, amsthm, amssymb}
sawine@13: \usepackage{typearea}
sawine@13: \usepackage{algorithm}
sawine@13: \usepackage{algorithmic}
sawine@13: \usepackage{fullpage}
sawine@13: \usepackage{mathtools}
sawine@13: \usepackage[all]{xy}
sawine@13: \title{Theory I, Sheet 9 Solution}
sawine@13: \author{Eugen Sawin}
sawine@13: \renewcommand{\familydefault}{\sfdefault}
sawine@13: \newcommand{\Pos}{\mathcal{P}os}
sawine@13: \newcommand{\E}{\mathcal{E}}
sawine@13: \newcommand{\D}{\mathcal{D}}
sawine@13: \newcommand{\J}{\mathcal{J}}
sawine@13: \include{pythonlisting}
sawine@13: 
sawine@13: \pagestyle{empty}
sawine@13: \begin{document}
sawine@13: \maketitle
sawine@13: 
sawine@13: \section*{Exercise 9.1.3}
sawine@13: \begin{align*}
sawine@13: ADT_{bool} = &(\Sigma_{bool}, \E)\\
sawine@13: \Sigma_{bool} = &\{true^{(0)}, false^{(0)}, not^{(1)}, and^{(2)}, or^{(2)}\}\\
sawine@13: \E = &\{true \approx not(false),\\
sawine@13: & false \approx not(true),\\
sawine@13: & not(not(x)) \approx x\\
sawine@13: & and(x, y) \approx not(or(not(x), not(y))),\\
sawine@13: & or(x, y) \approx not(and(not(x), not(y)))\}\\
sawine@13: \end{align*}
sawine@13: 
sawine@13: \section*{Exercise 9.1.4}
sawine@13: \begin{align*}
sawine@13: \D_{bool} &= (M, \J)\\
sawine@13: M &= \{0, 1\}\\
sawine@13: \J(true) &= 1\\
sawine@13: \J(false) &= 0\\
sawine@13: \J(not)(x) &= 1 - x\\
sawine@13: \J(and)(x, y) &= min(x, y)\\
sawine@13: \J(or)(x, y) &= max(x, y)\\
sawine@13: \end{align*}
sawine@13: 
sawine@13: \end{document}