13841
|
1 |
%
|
|
2 |
\begin{isabellebody}%
|
|
3 |
\def\isabellecontext{Aufgabe{\isadigit{1}}}%
|
|
4 |
\isamarkupfalse%
|
|
5 |
%
|
|
6 |
\isamarkupsubsection{Lists%
|
|
7 |
}
|
|
8 |
\isamarkuptrue%
|
|
9 |
%
|
|
10 |
\begin{isamarkuptext}%
|
|
11 |
Define a function \isa{replace}, such that \isa{replace\ x\ y\ zs}
|
|
12 |
yields \isa{zs} with every occurrence of \isa{x} replaced by \isa{y}.%
|
|
13 |
\end{isamarkuptext}%
|
|
14 |
\isamarkuptrue%
|
|
15 |
\isacommand{consts}\ replace\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list{\isachardoublequote}\isamarkupfalse%
|
|
16 |
%
|
|
17 |
\begin{isamarkuptext}%
|
|
18 |
Prove or disprove (by counter example) the following theorems.
|
|
19 |
You may have to prove some lemmas first.%
|
|
20 |
\end{isamarkuptext}%
|
|
21 |
\isamarkuptrue%
|
|
22 |
\isacommand{theorem}\ {\isachardoublequote}rev{\isacharparenleft}replace\ x\ y\ zs{\isacharparenright}\ {\isacharequal}\ replace\ x\ y\ {\isacharparenleft}rev\ zs{\isacharparenright}{\isachardoublequote}\isamarkupfalse%
|
|
23 |
\isanewline
|
|
24 |
\isamarkupfalse%
|
|
25 |
\isacommand{theorem}\ {\isachardoublequote}replace\ x\ y\ {\isacharparenleft}replace\ u\ v\ zs{\isacharparenright}\ {\isacharequal}\ replace\ u\ v\ {\isacharparenleft}replace\ x\ y\ zs{\isacharparenright}{\isachardoublequote}\isamarkupfalse%
|
|
26 |
\isanewline
|
|
27 |
\isamarkupfalse%
|
|
28 |
\isacommand{theorem}\ {\isachardoublequote}replace\ y\ z\ {\isacharparenleft}replace\ x\ y\ zs{\isacharparenright}\ {\isacharequal}\ replace\ x\ z\ zs{\isachardoublequote}\isamarkupfalse%
|
|
29 |
\isamarkupfalse%
|
|
30 |
%
|
|
31 |
\begin{isamarkuptext}%
|
|
32 |
Define two functions for removing elements from a list:
|
|
33 |
\isa{del{\isadigit{1}}\ x\ xs} deletes the first occurrence (from the left) of
|
|
34 |
\isa{x} in \isa{xs}, \isa{delall\ x\ xs} all of them.%
|
|
35 |
\end{isamarkuptext}%
|
|
36 |
\isamarkuptrue%
|
|
37 |
\isacommand{consts}\ del{\isadigit{1}}\ \ \ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list{\isachardoublequote}\isanewline
|
|
38 |
\ \ \ \ \ \ \ delall\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ {\isasymRightarrow}\ {\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list{\isachardoublequote}\isamarkupfalse%
|
|
39 |
%
|
|
40 |
\begin{isamarkuptext}%
|
|
41 |
Prove or disprove (by counter example) the following theorems.%
|
|
42 |
\end{isamarkuptext}%
|
|
43 |
\isamarkuptrue%
|
|
44 |
\isacommand{theorem}\ {\isachardoublequote}del{\isadigit{1}}\ x\ {\isacharparenleft}delall\ x\ xs{\isacharparenright}\ {\isacharequal}\ delall\ x\ xs{\isachardoublequote}\isamarkupfalse%
|
|
45 |
\isanewline
|
|
46 |
\isamarkupfalse%
|
|
47 |
\isacommand{theorem}\ {\isachardoublequote}delall\ x\ {\isacharparenleft}delall\ x\ xs{\isacharparenright}\ {\isacharequal}\ delall\ x\ xs{\isachardoublequote}\isamarkupfalse%
|
|
48 |
\isanewline
|
|
49 |
\isamarkupfalse%
|
|
50 |
\isacommand{theorem}\ {\isachardoublequote}delall\ x\ {\isacharparenleft}del{\isadigit{1}}\ x\ xs{\isacharparenright}\ {\isacharequal}\ delall\ x\ xs{\isachardoublequote}\isamarkupfalse%
|
|
51 |
\isanewline
|
|
52 |
\isamarkupfalse%
|
|
53 |
\isacommand{theorem}\ {\isachardoublequote}del{\isadigit{1}}\ x\ {\isacharparenleft}del{\isadigit{1}}\ y\ zs{\isacharparenright}\ {\isacharequal}\ del{\isadigit{1}}\ y\ {\isacharparenleft}del{\isadigit{1}}\ x\ zs{\isacharparenright}{\isachardoublequote}\isamarkupfalse%
|
|
54 |
\isanewline
|
|
55 |
\isamarkupfalse%
|
|
56 |
\isacommand{theorem}\ {\isachardoublequote}delall\ x\ {\isacharparenleft}del{\isadigit{1}}\ y\ zs{\isacharparenright}\ {\isacharequal}\ del{\isadigit{1}}\ y\ {\isacharparenleft}delall\ x\ zs{\isacharparenright}{\isachardoublequote}\isamarkupfalse%
|
|
57 |
\isanewline
|
|
58 |
\isamarkupfalse%
|
|
59 |
\isacommand{theorem}\ {\isachardoublequote}delall\ x\ {\isacharparenleft}delall\ y\ zs{\isacharparenright}\ {\isacharequal}\ delall\ y\ {\isacharparenleft}delall\ x\ zs{\isacharparenright}{\isachardoublequote}\isamarkupfalse%
|
|
60 |
\isanewline
|
|
61 |
\isamarkupfalse%
|
|
62 |
\isacommand{theorem}\ {\isachardoublequote}del{\isadigit{1}}\ y\ {\isacharparenleft}replace\ x\ y\ xs{\isacharparenright}\ {\isacharequal}\ del{\isadigit{1}}\ x\ xs{\isachardoublequote}\isamarkupfalse%
|
|
63 |
\isanewline
|
|
64 |
\isamarkupfalse%
|
|
65 |
\isacommand{theorem}\ {\isachardoublequote}delall\ y\ {\isacharparenleft}replace\ x\ y\ xs{\isacharparenright}\ {\isacharequal}\ delall\ x\ xs{\isachardoublequote}\isamarkupfalse%
|
|
66 |
\isanewline
|
|
67 |
\isamarkupfalse%
|
|
68 |
\isacommand{theorem}\ {\isachardoublequote}replace\ x\ y\ {\isacharparenleft}delall\ x\ zs{\isacharparenright}\ {\isacharequal}\ delall\ x\ zs{\isachardoublequote}\isamarkupfalse%
|
|
69 |
\isanewline
|
|
70 |
\isamarkupfalse%
|
|
71 |
\isacommand{theorem}\ {\isachardoublequote}replace\ x\ y\ {\isacharparenleft}delall\ z\ zs{\isacharparenright}\ {\isacharequal}\ delall\ z\ {\isacharparenleft}replace\ x\ y\ zs{\isacharparenright}{\isachardoublequote}\isamarkupfalse%
|
|
72 |
\isanewline
|
|
73 |
\isamarkupfalse%
|
|
74 |
\isacommand{theorem}\ {\isachardoublequote}rev{\isacharparenleft}del{\isadigit{1}}\ x\ xs{\isacharparenright}\ {\isacharequal}\ del{\isadigit{1}}\ x\ {\isacharparenleft}rev\ xs{\isacharparenright}{\isachardoublequote}\isamarkupfalse%
|
|
75 |
\isanewline
|
|
76 |
\isamarkupfalse%
|
|
77 |
\isacommand{theorem}\ {\isachardoublequote}rev{\isacharparenleft}delall\ x\ xs{\isacharparenright}\ {\isacharequal}\ delall\ x\ {\isacharparenleft}rev\ xs{\isacharparenright}{\isachardoublequote}\isamarkupfalse%
|
|
78 |
\isamarkupfalse%
|
|
79 |
\isamarkupfalse%
|
|
80 |
\end{isabellebody}%
|
|
81 |
%%% Local Variables:
|
|
82 |
%%% mode: latex
|
|
83 |
%%% TeX-master: "root"
|
|
84 |
%%% End:
|