author | Christian Urban <urbanc@in.tum.de> |
Mon, 18 Jun 2012 14:50:02 +0100 | |
changeset 3190 | 1b7c034c9e9e |
parent 2699 | 0424e7a7e99f |
permissions | -rw-r--r-- |
2699
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
1 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
2 |
theory Tutorial3s |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
3 |
imports Lambda |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
4 |
begin |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
5 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
6 |
section {* Formalising Barendregt's Proof of the Substitution Lemma *} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
7 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
8 |
text {* |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
9 |
The substitution lemma is another theorem where the variable |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
10 |
convention plays a crucial role. |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
11 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
12 |
Barendregt's proof of this lemma needs in the variable case a |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
13 |
case distinction. One way to do this in Isar is to use blocks. |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
14 |
A block consist of some assumptions and reasoning steps |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
15 |
enclosed in curly braces, like |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
16 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
17 |
{ \<dots> |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
18 |
have "statement" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
19 |
have "last_statement_in_the_block" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
20 |
} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
21 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
22 |
Such a block may contain local assumptions like |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
23 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
24 |
{ assume "A" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
25 |
assume "B" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
26 |
\<dots> |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
27 |
have "C" by \<dots> |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
28 |
} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
29 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
30 |
Where "C" is the last have-statement in this block. The behaviour |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
31 |
of such a block to the 'outside' is the implication |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
32 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
33 |
A \<Longrightarrow> B \<Longrightarrow> C |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
34 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
35 |
Now if we want to prove a property "smth" using the case-distinctions |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
36 |
P1, P2 and P3 then we can use the following reasoning: |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
37 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
38 |
{ assume "P1" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
39 |
\<dots> |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
40 |
have "smth" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
41 |
} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
42 |
moreover |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
43 |
{ assume "P2" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
44 |
\<dots> |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
45 |
have "smth" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
46 |
} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
47 |
moreover |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
48 |
{ assume "P3" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
49 |
\<dots> |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
50 |
have "smth" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
51 |
} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
52 |
ultimately have "smth" by blast |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
53 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
54 |
The blocks establish the implications |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
55 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
56 |
P1 \<Longrightarrow> smth |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
57 |
P2 \<Longrightarrow> smth |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
58 |
P3 \<Longrightarrow> smth |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
59 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
60 |
If we know that P1, P2 and P3 cover all the cases, that is P1 \<or> P2 \<or> P3 |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
61 |
holds, then we have 'ultimately' established the property "smth" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
62 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
63 |
*} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
64 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
65 |
subsection {* Two preliminary facts *} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
66 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
67 |
lemma forget: |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
68 |
shows "atom x \<sharp> t \<Longrightarrow> t[x ::= s] = t" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
69 |
by (nominal_induct t avoiding: x s rule: lam.strong_induct) |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
70 |
(auto simp add: lam.fresh fresh_at_base) |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
71 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
72 |
lemma fresh_fact: |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
73 |
assumes a: "atom z \<sharp> s" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
74 |
and b: "z = y \<or> atom z \<sharp> t" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
75 |
shows "atom z \<sharp> t[y ::= s]" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
76 |
using a b |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
77 |
by (nominal_induct t avoiding: z y s rule: lam.strong_induct) |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
78 |
(auto simp add: lam.fresh fresh_at_base) |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
79 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
80 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
81 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
82 |
section {* EXERCISE 10 *} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
83 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
84 |
text {* |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
85 |
Fill in the cases 1.2 and 1.3 and the equational reasoning |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
86 |
in the lambda-case. |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
87 |
*} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
88 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
89 |
lemma |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
90 |
assumes a: "x \<noteq> y" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
91 |
and b: "atom x \<sharp> L" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
92 |
shows "M[x ::= N][y ::= L] = M[y ::= L][x ::= N[y ::= L]]" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
93 |
using a b |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
94 |
proof (nominal_induct M avoiding: x y N L rule: lam.strong_induct) |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
95 |
case (Var z) |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
96 |
have a1: "x \<noteq> y" by fact |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
97 |
have a2: "atom x \<sharp> L" by fact |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
98 |
show "Var z[x::=N][y::=L] = Var z[y::=L][x::=N[y::=L]]" (is "?LHS = ?RHS") |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
99 |
proof - |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
100 |
{ -- {* Case 1.1 *} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
101 |
assume c1: "z = x" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
102 |
have "(1)": "?LHS = N[y::=L]" using c1 by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
103 |
have "(2)": "?RHS = N[y::=L]" using c1 a1 by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
104 |
have "?LHS = ?RHS" using "(1)" "(2)" by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
105 |
} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
106 |
moreover |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
107 |
{ -- {* Case 1.2 *} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
108 |
assume c2: "z = y" "z \<noteq> x" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
109 |
have "(1)": "?LHS = L" using c2 by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
110 |
have "(2)": "?RHS = L[x::=N[y::=L]]" using c2 by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
111 |
have "(3)": "L[x::=N[y::=L]] = L" using a2 forget by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
112 |
have "?LHS = ?RHS" using "(1)" "(2)" "(3)" by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
113 |
} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
114 |
moreover |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
115 |
{ -- {* Case 1.3 *} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
116 |
assume c3: "z \<noteq> x" "z \<noteq> y" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
117 |
have "(1)": "?LHS = Var z" using c3 by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
118 |
have "(2)": "?RHS = Var z" using c3 by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
119 |
have "?LHS = ?RHS" using "(1)" "(2)" by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
120 |
} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
121 |
ultimately show "?LHS = ?RHS" by blast |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
122 |
qed |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
123 |
next |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
124 |
case (Lam z M1) -- {* case 2: lambdas *} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
125 |
have ih: "\<lbrakk>x \<noteq> y; atom x \<sharp> L\<rbrakk> \<Longrightarrow> M1[x ::= N][y ::= L] = M1[y ::= L][x ::= N[y ::= L]]" by fact |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
126 |
have a1: "x \<noteq> y" by fact |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
127 |
have a2: "atom x \<sharp> L" by fact |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
128 |
have fs: "atom z \<sharp> x" "atom z \<sharp> y" "atom z \<sharp> N" "atom z \<sharp> L" by fact+ -- {* !! *} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
129 |
then have b: "atom z \<sharp> N[y::=L]" by (simp add: fresh_fact) |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
130 |
show "(Lam [z].M1)[x ::= N][y ::= L] = (Lam [z].M1)[y ::= L][x ::= N[y ::= L]]" (is "?LHS=?RHS") |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
131 |
proof - |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
132 |
have "?LHS = Lam [z].(M1[x ::= N][y ::= L])" using fs by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
133 |
also have "\<dots> = Lam [z].(M1[y ::= L][x ::= N[y ::= L]])" using ih a1 a2 by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
134 |
also have "\<dots> = (Lam [z].(M1[y ::= L]))[x ::= N[y ::= L]]" using b fs by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
135 |
also have "\<dots> = ?RHS" using fs by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
136 |
finally show "?LHS = ?RHS" by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
137 |
qed |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
138 |
next |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
139 |
case (App M1 M2) -- {* case 3: applications *} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
140 |
then show "(App M1 M2)[x::=N][y::=L] = (App M1 M2)[y::=L][x::=N[y::=L]]" by simp |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
141 |
qed |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
142 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
143 |
text {* |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
144 |
Again the strong induction principle enables Isabelle to find |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
145 |
the proof of the substitution lemma completely automatically. |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
146 |
*} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
147 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
148 |
lemma substitution_lemma_version: |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
149 |
assumes asm: "x \<noteq> y" "atom x \<sharp> L" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
150 |
shows "M[x::=N][y::=L] = M[y::=L][x::=N[y::=L]]" |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
151 |
using asm |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
152 |
by (nominal_induct M avoiding: x y N L rule: lam.strong_induct) |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
153 |
(auto simp add: fresh_fact forget) |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
154 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
155 |
subsection {* MINI EXERCISE *} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
156 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
157 |
text {* |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
158 |
Compare and contrast Barendregt's reasoning and the |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
159 |
formalised proofs. |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
160 |
*} |
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
161 |
|
0424e7a7e99f
cleaned up Tutorial 3 with solutions
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
162 |
end |