8 |
8 |
9 (* Derives the well-known convergent set of equations for groups |
9 (* Derives the well-known convergent set of equations for groups |
10 based on the unary inverse 0-x. |
10 based on the unary inverse 0-x. |
11 *) |
11 *) |
12 |
12 |
13 Goal "!!x::'a::add_group. (0-x)+(x+y) = y"; |
13 Goal "!!x::'a::add_group. (0 - x) + (x + y) = y"; |
14 by (rtac trans 1); |
14 by (rtac trans 1); |
15 by (rtac (plus_assoc RS sym) 1); |
15 by (rtac (plus_assoc RS sym) 1); |
16 by (stac left_inv 1); |
16 by (stac left_inv 1); |
17 by (rtac zeroL 1); |
17 by (rtac zeroL 1); |
18 qed "left_inv2"; |
18 qed "left_inv2"; |
19 |
19 |
20 Goal "!!x::'a::add_group. (0-(0-x)) = x"; |
20 Goal "!!x::'a::add_group. (0 - (0 - x)) = x"; |
21 by (rtac trans 1); |
21 by (rtac trans 1); |
22 by (res_inst_tac [("x","0-x")] left_inv2 2); |
22 by (res_inst_tac [("x","0 - x")] left_inv2 2); |
23 by (stac left_inv 1); |
23 by (stac left_inv 1); |
24 by (rtac (zeroR RS sym) 1); |
24 by (rtac (zeroR RS sym) 1); |
25 qed "inv_inv"; |
25 qed "inv_inv"; |
26 |
26 |
27 Goal "0-0 = (0::'a::add_group)"; |
27 Goal "0 - 0 = (0::'a::add_group)"; |
28 by (rtac trans 1); |
28 by (rtac trans 1); |
29 by (rtac (zeroR RS sym) 1); |
29 by (rtac (zeroR RS sym) 1); |
30 by (rtac trans 1); |
30 by (rtac trans 1); |
31 by (res_inst_tac [("x","0")] left_inv2 2); |
31 by (res_inst_tac [("x","0")] left_inv2 2); |
32 by (simp_tac (simpset() addsimps [zeroR]) 1); |
32 by (simp_tac (simpset() addsimps [zeroR]) 1); |
33 qed "inv_zero"; |
33 qed "inv_zero"; |
34 |
34 |
35 Goal "!!x::'a::add_group. x+(0-x) = 0"; |
35 Goal "!!x::'a::add_group. x + (0 - x) = 0"; |
36 by (rtac trans 1); |
36 by (rtac trans 1); |
37 by (res_inst_tac [("x","0-x")] left_inv 2); |
37 by (res_inst_tac [("x","0-x")] left_inv 2); |
38 by (stac inv_inv 1); |
38 by (stac inv_inv 1); |
39 by (rtac refl 1); |
39 by (rtac refl 1); |
40 qed "right_inv"; |
40 qed "right_inv"; |
41 |
41 |
42 Goal "!!x::'a::add_group. x+((0-x)+y) = y"; |
42 Goal "!!x::'a::add_group. x + ((0 - x) + y) = y"; |
43 by (rtac trans 1); |
43 by (rtac trans 1); |
44 by (res_inst_tac [("x","0-x")] left_inv2 2); |
44 by (res_inst_tac [("x","0 - x")] left_inv2 2); |
45 by (stac inv_inv 1); |
45 by (stac inv_inv 1); |
46 by (rtac refl 1); |
46 by (rtac refl 1); |
47 qed "right_inv2"; |
47 qed "right_inv2"; |
48 |
48 |
49 val plus_cong = read_instantiate [("f1","op +")] (arg_cong RS cong); |
49 val plus_cong = read_instantiate [("f1","op +")] (arg_cong RS cong); |
50 |
50 |
51 Goal "!!x::'a::add_group. 0-(x+y) = (0-y)+(0-x)"; |
51 Goal "!!x::'a::add_group. 0 - (x + y) = (0 - y) + (0 - x)"; |
52 by (rtac trans 1); |
52 by (rtac trans 1); |
53 by (rtac zeroR 2); |
53 by (rtac zeroR 2); |
54 by (rtac trans 1); |
54 by (rtac trans 1); |
55 by (rtac plus_cong 2); |
55 by (rtac plus_cong 2); |
56 by (rtac refl 2); |
56 by (rtac refl 2); |
63 [plus_assoc,left_inv,left_inv2,right_inv,right_inv2]) 2); |
63 [plus_assoc,left_inv,left_inv2,right_inv,right_inv2]) 2); |
64 by (rtac refl 2); |
64 by (rtac refl 2); |
65 by (rtac (zeroL RS sym) 1); |
65 by (rtac (zeroL RS sym) 1); |
66 qed "inv_plus"; |
66 qed "inv_plus"; |
67 |
67 |
68 (*** convergent TRS for groups with unary inverse 0-x ***) |
68 (*** convergent TRS for groups with unary inverse 0 - x ***) |
69 val group1_simps = |
69 val group1_simps = |
70 [zeroL,zeroR,plus_assoc,left_inv,left_inv2,right_inv,right_inv2,inv_inv, |
70 [zeroL,zeroR,plus_assoc,left_inv,left_inv2,right_inv,right_inv2,inv_inv, |
71 inv_zero,inv_plus]; |
71 inv_zero,inv_plus]; |
72 |
72 |
73 val group1_tac = |
73 val group1_tac = |
74 let val ss = HOL_basic_ss addsimps group1_simps |
74 let val ss = HOL_basic_ss addsimps group1_simps |
75 in simp_tac ss end; |
75 in simp_tac ss end; |
76 |
76 |
77 (* I believe there is no convergent TRS for groups with binary `-', |
77 (* I believe there is no convergent TRS for groups with binary `-', |
78 unless you have an extra unary `-' and simply define x-y = x+(-y). |
78 unless you have an extra unary `-' and simply define x - y = x + (-y). |
79 This does not work with only a binary `-' because x-y = x+(0-y) does |
79 This does not work with only a binary `-' because x - y = x + (0 - y) does |
80 not terminate. Hence we have a special tactic for converting all |
80 not terminate. Hence we have a special tactic for converting all |
81 occurrences of x-y into x+(0-y): |
81 occurrences of x - y into x + (0 - y): |
82 *) |
82 *) |
83 |
83 |
84 local |
84 local |
85 fun find(Const("op -",Type("fun",[T,_]))$s$t) = [(T,s,t)] @ find s @ find t |
85 fun find(Const("op -",Type("fun",[T,_]))$s$t) = [(T,s,t)] @ find s @ find t |
86 | find(s$t) = find s @ find t |
86 | find(s$t) = find s @ find t |
100 end; |
100 end; |
101 |
101 |
102 (* The following two equations are not used in any of the decision procedures, |
102 (* The following two equations are not used in any of the decision procedures, |
103 but are still very useful. They also demonstrate mk_group1_tac. |
103 but are still very useful. They also demonstrate mk_group1_tac. |
104 *) |
104 *) |
105 Goal "x-x = (0::'a::add_group)"; |
105 Goal "x - x = (0::'a::add_group)"; |
106 by (mk_group1_tac 1); |
106 by (mk_group1_tac 1); |
107 by (group1_tac 1); |
107 by (group1_tac 1); |
108 qed "minus_self_zero"; |
108 qed "minus_self_zero"; |
109 |
109 |
110 Goal "x-0 = (x::'a::add_group)"; |
110 Goal "x - 0 = (x::'a::add_group)"; |
111 by (mk_group1_tac 1); |
111 by (mk_group1_tac 1); |
112 by (group1_tac 1); |
112 by (group1_tac 1); |
113 qed "minus_zero"; |
113 qed "minus_zero"; |
114 |
114 |
115 (*** Abelian Groups ***) |
115 (*** Abelian Groups ***) |
120 by (rtac trans 1); |
120 by (rtac trans 1); |
121 by (rtac plus_assoc 1); |
121 by (rtac plus_assoc 1); |
122 by (simp_tac (simpset() addsimps [plus_commute]) 1); |
122 by (simp_tac (simpset() addsimps [plus_commute]) 1); |
123 qed "plus_commuteL"; |
123 qed "plus_commuteL"; |
124 |
124 |
125 (* Convergent TRS for Abelian groups with unary inverse 0-x. |
125 (* Convergent TRS for Abelian groups with unary inverse 0 - x. |
126 Requires ordered rewriting |
126 Requires ordered rewriting |
127 *) |
127 *) |
128 |
128 |
129 val agroup1_simps = plus_commute::plus_commuteL::group1_simps; |
129 val agroup1_simps = plus_commute::plus_commuteL::group1_simps; |
130 |
130 |