theory1: tex/theory1_ex9.tex@a703c0e88e47

     1 \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}

     2 \usepackage{graphicx}

     3 %\usepackage[latin1]{inputenc}

     4 \usepackage{amsmath, amsthm, amssymb}

     5 \usepackage{typearea}

     6 \usepackage{algorithm}

     7 \usepackage{algorithmic}

     8 \usepackage{fullpage}

     9 \usepackage{mathtools}

    10 \usepackage[all]{xy}

    11 \title{Theory I, Sheet 9 Solution}

    12 \author{Eugen Sawin}

    13 \renewcommand{\familydefault}{\sfdefault}

    14 \newcommand{\Pos}{\mathcal{P}os}

    15 \newcommand{\E}{\mathcal{E}}

    16 \newcommand{\D}{\mathcal{D}}

    17 \newcommand{\J}{\mathcal{J}}

    18 \include{pythonlisting}

    20 \pagestyle{empty}

    21 \begin{document}

    22 \maketitle

    24 \section*{Exercise 9.1.3}

    25 \begin{align*}

    26 ADT\, bool = &(\Sigma_{bool}, \E)\\

    27 \Sigma_{bool} = &\{true^{(0)}, false^{(0)}, not^{(1)}, and^{(2)}, or^{(2)}\}\\

    28 \E = &\{true \approx not(false),\\

    29 & not(not(x)) \approx x,\\

    30 & or(x, false) \approx x,\\

    31 & or(x, true) \approx true,\\

    32 & and(x, y) \approx not(or(not(x), not(y)))\}\\

    33 \end{align*}

    34 Remarks: $false \approx not(true)$ follows from $true \approx not(false)$ and $not(not(x)) \approx x$.\\

    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)))$.

    37 \section*{Exercise 9.1.4}

    38 \begin{align*}

    39 \D_{bool} &= (M, \J)\\

    40 M &= \{0, 1\}\\

    41 \J(true) &= 1\\

    42 \J(false) &= 0\\

    43 \J(not)(x) &= 1 - x\\

    44 \J(and)(x, y) &= min(x, y)\\

    45 \J(or)(x, y) &= max(x, y)\\

    46 \end{align*}

    48 \section*{Exercise 9.2}

    49 \begin{align*}

    50 ADT\, Stack(A) = &(\Sigma_{Stack}, \E)\\

    51 \Sigma_{Stack} = &\{new^{(0)}, true^{(0)}, false^{(0)}, pop^{(1)}, top^{(1)}, isEmpty^{(1)}, push^{(2)}\}\\

    52 & new: Stack\\

    53 & true: bool\\

    54 & false: bool\\

    55 & pop: Stack \to Stack\\

    56 & top: Stack \to A\\

    57 & isEmpty: Stack \to bool\\

    58 & push: Stack \times A \to Stack\\

    59 \E = &\{isEmpty(new) \approx true,\\

    60 & isEmpty(push(S, x)) \approx false,\\

    61 & top(push(S, x)) \approx x,\\

    62 & pop(push(S, x)) \approx S\}\\

    63 \end{align*}

    64 The ADT $Stack$ has only one constructor $new$.

    65 \end{document}

author	Eugen Sawin <sawine@me73.com>
	Tue, 19 Jul 2011 15:25:16 +0200
changeset 15	a703c0e88e47
parent 14	11c55592ac33
permissions	-rw-r--r--