sawine@13
|
1 |
\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
|
sawine@13
|
2 |
\usepackage{graphicx}
|
sawine@13
|
3 |
%\usepackage[latin1]{inputenc}
|
sawine@13
|
4 |
\usepackage{amsmath, amsthm, amssymb}
|
sawine@13
|
5 |
\usepackage{typearea}
|
sawine@13
|
6 |
\usepackage{algorithm}
|
sawine@13
|
7 |
\usepackage{algorithmic}
|
sawine@13
|
8 |
\usepackage{fullpage}
|
sawine@13
|
9 |
\usepackage{mathtools}
|
sawine@13
|
10 |
\usepackage[all]{xy}
|
sawine@13
|
11 |
\title{Theory I, Sheet 9 Solution}
|
sawine@13
|
12 |
\author{Eugen Sawin}
|
sawine@13
|
13 |
\renewcommand{\familydefault}{\sfdefault}
|
sawine@13
|
14 |
\newcommand{\Pos}{\mathcal{P}os}
|
sawine@13
|
15 |
\newcommand{\E}{\mathcal{E}}
|
sawine@13
|
16 |
\newcommand{\D}{\mathcal{D}}
|
sawine@13
|
17 |
\newcommand{\J}{\mathcal{J}}
|
sawine@13
|
18 |
\include{pythonlisting}
|
sawine@13
|
19 |
|
sawine@13
|
20 |
\pagestyle{empty}
|
sawine@13
|
21 |
\begin{document}
|
sawine@13
|
22 |
\maketitle
|
sawine@13
|
23 |
|
sawine@13
|
24 |
\section*{Exercise 9.1.3}
|
sawine@13
|
25 |
\begin{align*}
|
sawine@14
|
26 |
ADT\, bool = &(\Sigma_{bool}, \E)\\
|
sawine@13
|
27 |
\Sigma_{bool} = &\{true^{(0)}, false^{(0)}, not^{(1)}, and^{(2)}, or^{(2)}\}\\
|
sawine@13
|
28 |
\E = &\{true \approx not(false),\\
|
sawine@14
|
29 |
& not(not(x)) \approx x,\\
|
sawine@14
|
30 |
& or(x, false) \approx x,\\
|
sawine@14
|
31 |
& or(x, true) \approx true,\\
|
sawine@14
|
32 |
& and(x, y) \approx not(or(not(x), not(y)))\}\\
|
sawine@13
|
33 |
\end{align*}
|
sawine@14
|
34 |
Remarks: $false \approx not(true)$ follows from $true \approx not(false)$ and $not(not(x)) \approx x$.\\
|
sawine@14
|
35 |
$or(x, y) \approx not(and(not(x), not(y)))$ follows from $not(not(x)) \approx x$ and $and(x, y) \approx not(or(not(x), not(y)))$.
|
sawine@13
|
36 |
|
sawine@13
|
37 |
\section*{Exercise 9.1.4}
|
sawine@13
|
38 |
\begin{align*}
|
sawine@13
|
39 |
\D_{bool} &= (M, \J)\\
|
sawine@13
|
40 |
M &= \{0, 1\}\\
|
sawine@13
|
41 |
\J(true) &= 1\\
|
sawine@13
|
42 |
\J(false) &= 0\\
|
sawine@13
|
43 |
\J(not)(x) &= 1 - x\\
|
sawine@13
|
44 |
\J(and)(x, y) &= min(x, y)\\
|
sawine@13
|
45 |
\J(or)(x, y) &= max(x, y)\\
|
sawine@13
|
46 |
\end{align*}
|
sawine@13
|
47 |
|
sawine@14
|
48 |
\section*{Exercise 9.2}
|
sawine@14
|
49 |
\begin{align*}
|
sawine@15
|
50 |
ADT\, Stack(A) = &(\Sigma_{Stack}, \E)\\
|
sawine@14
|
51 |
\Sigma_{Stack} = &\{new^{(0)}, true^{(0)}, false^{(0)}, pop^{(1)}, top^{(1)}, isEmpty^{(1)}, push^{(2)}\}\\
|
sawine@14
|
52 |
& new: Stack\\
|
sawine@14
|
53 |
& true: bool\\
|
sawine@14
|
54 |
& false: bool\\
|
sawine@14
|
55 |
& pop: Stack \to Stack\\
|
sawine@14
|
56 |
& top: Stack \to A\\
|
sawine@14
|
57 |
& isEmpty: Stack \to bool\\
|
sawine@14
|
58 |
& push: Stack \times A \to Stack\\
|
sawine@14
|
59 |
\E = &\{isEmpty(new) \approx true,\\
|
sawine@14
|
60 |
& isEmpty(push(S, x)) \approx false,\\
|
sawine@14
|
61 |
& top(push(S, x)) \approx x,\\
|
sawine@14
|
62 |
& pop(push(S, x)) \approx S\}\\
|
sawine@14
|
63 |
\end{align*}
|
sawine@14
|
64 |
The ADT $Stack$ has only one constructor $new$.
|
sawine@13
|
65 |
\end{document}
|