author | wenzelm |
Wed, 21 Aug 2019 15:19:31 +0200 | |
changeset 70600 | 6e97e31933a6 |
parent 69593 | 3dda49e08b9d |
permissions | -rw-r--r-- |
31974 | 1 |
(* Title: FOL/ex/Prolog.thy |
1473 | 2 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
0 | 3 |
Copyright 1992 University of Cambridge |
4 |
*) |
|
5 |
||
60770 | 6 |
section \<open>First-Order Logic: PROLOG examples\<close> |
17245 | 7 |
|
8 |
theory Prolog |
|
9 |
imports FOL |
|
10 |
begin |
|
11 |
||
12 |
typedecl 'a list |
|
69590 | 13 |
instance list :: (\<open>term\<close>) \<open>term\<close> .. |
41779 | 14 |
|
15 |
axiomatization |
|
69590 | 16 |
Nil :: \<open>'a list\<close> and |
17 |
Cons :: \<open>['a, 'a list]=> 'a list\<close> (infixr \<open>:\<close> 60) and |
|
18 |
app :: \<open>['a list, 'a list, 'a list] => o\<close> and |
|
19 |
rev :: \<open>['a list, 'a list] => o\<close> |
|
41779 | 20 |
where |
69590 | 21 |
appNil: \<open>app(Nil,ys,ys)\<close> and |
22 |
appCons: \<open>app(xs,ys,zs) ==> app(x:xs, ys, x:zs)\<close> and |
|
23 |
revNil: \<open>rev(Nil,Nil)\<close> and |
|
24 |
revCons: \<open>[| rev(xs,ys); app(ys, x:Nil, zs) |] ==> rev(x:xs, zs)\<close> |
|
17245 | 25 |
|
69590 | 26 |
schematic_goal \<open>app(a:b:c:Nil, d:e:Nil, ?x)\<close> |
19819 | 27 |
apply (rule appNil appCons) |
28 |
apply (rule appNil appCons) |
|
29 |
apply (rule appNil appCons) |
|
30 |
apply (rule appNil appCons) |
|
31 |
done |
|
32 |
||
69590 | 33 |
schematic_goal \<open>app(?x, c:d:Nil, a:b:c:d:Nil)\<close> |
19819 | 34 |
apply (rule appNil appCons)+ |
35 |
done |
|
36 |
||
69590 | 37 |
schematic_goal \<open>app(?x, ?y, a:b:c:d:Nil)\<close> |
19819 | 38 |
apply (rule appNil appCons)+ |
39 |
back |
|
40 |
back |
|
41 |
back |
|
42 |
back |
|
43 |
done |
|
44 |
||
45 |
(*app([x1,...,xn], y, ?z) requires (n+1) inferences*) |
|
46 |
(*rev([x1,...,xn], ?y) requires (n+1)(n+2)/2 inferences*) |
|
47 |
||
48 |
lemmas rules = appNil appCons revNil revCons |
|
49 |
||
69590 | 50 |
schematic_goal \<open>rev(a:b:c:d:Nil, ?x)\<close> |
19819 | 51 |
apply (rule rules)+ |
52 |
done |
|
53 |
||
69590 | 54 |
schematic_goal \<open>rev(a:b:c:d:e:f:g:h:i:j:k:l:m:n:Nil, ?w)\<close> |
19819 | 55 |
apply (rule rules)+ |
56 |
done |
|
57 |
||
69590 | 58 |
schematic_goal \<open>rev(?x, a:b:c:Nil)\<close> |
62020 | 59 |
apply (rule rules)+ \<comment> \<open>does not solve it directly!\<close> |
19819 | 60 |
back |
61 |
back |
|
62 |
done |
|
63 |
||
64 |
(*backtracking version*) |
|
60770 | 65 |
ML \<open> |
59498
50b60f501b05
proper context for resolve_tac, eresolve_tac, dresolve_tac, forward_tac etc.;
wenzelm
parents:
58889
diff
changeset
|
66 |
fun prolog_tac ctxt = |
50b60f501b05
proper context for resolve_tac, eresolve_tac, dresolve_tac, forward_tac etc.;
wenzelm
parents:
58889
diff
changeset
|
67 |
DEPTH_FIRST (has_fewer_prems 1) (resolve_tac ctxt @{thms rules} 1) |
60770 | 68 |
\<close> |
19819 | 69 |
|
69590 | 70 |
schematic_goal \<open>rev(?x, a:b:c:Nil)\<close> |
69593 | 71 |
apply (tactic \<open>prolog_tac \<^context>\<close>) |
19819 | 72 |
done |
73 |
||
69590 | 74 |
schematic_goal \<open>rev(a:?x:c:?y:Nil, d:?z:b:?u)\<close> |
69593 | 75 |
apply (tactic \<open>prolog_tac \<^context>\<close>) |
19819 | 76 |
done |
77 |
||
78 |
(*rev([a..p], ?w) requires 153 inferences *) |
|
69590 | 79 |
schematic_goal \<open>rev(a:b:c:d:e:f:g:h:i:j:k:l:m:n:o:p:Nil, ?w)\<close> |
60770 | 80 |
apply (tactic \<open> |
69593 | 81 |
DEPTH_SOLVE (resolve_tac \<^context> ([@{thm refl}, @{thm conjI}] @ @{thms rules}) 1)\<close>) |
19819 | 82 |
done |
83 |
||
84 |
(*?x has 16, ?y has 32; rev(?y,?w) requires 561 (rather large) inferences |
|
85 |
total inferences = 2 + 1 + 17 + 561 = 581*) |
|
69590 | 86 |
schematic_goal \<open>a:b:c:d:e:f:g:h:i:j:k:l:m:n:o:p:Nil = ?x \<and> app(?x,?x,?y) \<and> rev(?y,?w)\<close> |
60770 | 87 |
apply (tactic \<open> |
69593 | 88 |
DEPTH_SOLVE (resolve_tac \<^context> ([@{thm refl}, @{thm conjI}] @ @{thms rules}) 1)\<close>) |
19819 | 89 |
done |
17245 | 90 |
|
0 | 91 |
end |