1 (* Title: HOL/ex/SAT_Examples.thy |
1 (* Title: HOL/ex/SAT_Examples.thy |
2 Author: Alwen Tiu, Tjark Weber |
2 Author: Alwen Tiu, Tjark Weber |
3 Copyright 2005-2009 |
3 Copyright 2005-2009 |
4 *) |
4 *) |
5 |
5 |
6 header {* Examples for the 'sat' and 'satx' tactic *} |
6 header {* Examples for proof methods "sat" and "satx" *} |
7 |
7 |
8 theory SAT_Examples imports Main |
8 theory SAT_Examples imports Main |
9 begin |
9 begin |
10 |
10 |
11 (* ML {* SAT.solver := "zchaff_with_proofs"; *} *) |
11 (* |
12 (* ML {* SAT.solver := "minisat_with_proofs"; *} *) |
12 declare [[sat_solver = zchaff_with_proofs]] |
13 ML {* SAT.trace_sat := true; *} |
13 declare [[sat_solver = minisat_with_proofs]] |
|
14 *) |
|
15 |
|
16 declare [[sat_trace]] |
14 declare [[quick_and_dirty]] |
17 declare [[quick_and_dirty]] |
15 |
18 |
16 lemma "True" |
19 lemma "True" |
17 by sat |
20 by sat |
18 |
21 |
22 lemma "(a | b) & ~a \<Longrightarrow> b" |
25 lemma "(a | b) & ~a \<Longrightarrow> b" |
23 by sat |
26 by sat |
24 |
27 |
25 lemma "(a & b) | (c & d) \<Longrightarrow> (a & b) | (c & d)" |
28 lemma "(a & b) | (c & d) \<Longrightarrow> (a & b) | (c & d)" |
26 (* |
29 (* |
27 apply (tactic {* CNF.cnf_rewrite_tac 1 *}) |
30 apply (tactic {* CNF.cnf_rewrite_tac @{context} 1 *}) |
28 *) |
31 *) |
29 by sat |
32 by sat |
30 |
33 |
31 lemma "(a & b) | (c & d) \<Longrightarrow> (a & b) | (c & d)" |
34 lemma "(a & b) | (c & d) \<Longrightarrow> (a & b) | (c & d)" |
32 (* |
35 (* |
33 apply (tactic {* CNF.cnfx_rewrite_tac 1 *}) |
36 apply (tactic {* CNF.cnfx_rewrite_tac @{context} 1 *}) |
34 apply (erule exE | erule conjE)+ |
37 apply (erule exE | erule conjE)+ |
35 *) |
38 *) |
36 by satx |
39 by satx |
37 |
40 |
38 lemma "(a & b | c & d) & (e & f | g & h) | (i & j | k & l) & (m & n | p & q) |
41 lemma "(a & b | c & d) & (e & f | g & h) | (i & j | k & l) & (m & n | p & q) |
39 \<Longrightarrow> (a & b | c & d) & (e & f | g & h) | (i & j | k & l) & (m & n | p & q)" |
42 \<Longrightarrow> (a & b | c & d) & (e & f | g & h) | (i & j | k & l) & (m & n | p & q)" |
40 (* |
43 (* |
41 apply (tactic {* CNF.cnf_rewrite_tac 1 *}) |
44 apply (tactic {* CNF.cnf_rewrite_tac @{context} 1 *}) |
42 *) |
45 *) |
43 by sat |
46 by sat |
44 |
47 |
45 lemma "(a & b | c & d) & (e & f | g & h) | (i & j | k & l) & (m & n | p & q) |
48 lemma "(a & b | c & d) & (e & f | g & h) | (i & j | k & l) & (m & n | p & q) |
46 \<Longrightarrow> (a & b | c & d) & (e & f | g & h) | (i & j | k & l) & (m & n | p & q)" |
49 \<Longrightarrow> (a & b | c & d) & (e & f | g & h) | (i & j | k & l) & (m & n | p & q)" |
47 (* |
50 (* |
48 apply (tactic {* CNF.cnfx_rewrite_tac 1 *}) |
51 apply (tactic {* CNF.cnfx_rewrite_tac @{context} 1 *}) |
49 apply (erule exE | erule conjE)+ |
52 apply (erule exE | erule conjE)+ |
50 *) |
53 *) |
51 by satx |
54 by satx |
52 |
55 |
53 lemma "P=P=P=P=P=P=P=P=P=P" |
56 lemma "P=P=P=P=P=P=P=P=P=P" |
75 text {* eta-Equivalence *} |
78 text {* eta-Equivalence *} |
76 |
79 |
77 lemma "(ALL x. P x) | ~ All P" |
80 lemma "(ALL x. P x) | ~ All P" |
78 by sat |
81 by sat |
79 |
82 |
80 ML {* SAT.trace_sat := false; *} |
83 declare [[sat_trace = false]] |
81 declare [[quick_and_dirty = false]] |
84 declare [[quick_and_dirty = false]] |
82 |
85 |
83 method_setup rawsat = {* |
86 method_setup rawsat = {* |
84 Scan.succeed (SIMPLE_METHOD' o SAT.rawsat_tac) |
87 Scan.succeed (SIMPLE_METHOD' o SAT.rawsat_tac) |
85 *} "SAT solver (no preprocessing)" |
88 *} "SAT solver (no preprocessing)" |
517 measures the time spent on proof reconstruction (at least real time |
520 measures the time spent on proof reconstruction (at least real time |
518 also includes time spent in the SAT solver), and additionally returns |
521 also includes time spent in the SAT solver), and additionally returns |
519 the number of resolution steps in the proof. |
522 the number of resolution steps in the proof. |
520 *} |
523 *} |
521 |
524 |
522 (* ML {* |
525 (* |
523 SAT.solver := "zchaff_with_proofs"; |
526 declare [[sat_solver = zchaff_with_proofs]] |
524 SAT.trace_sat := false; |
527 declare [[sat_trace = false]] |
525 *} |
|
526 declare [[quick_and_dirty = false]] |
528 declare [[quick_and_dirty = false]] |
527 *) |
529 *) |
528 |
|
529 ML {* |
530 ML {* |
530 fun benchmark dimacsfile = |
531 fun benchmark dimacsfile = |
531 let |
532 let |
532 val prop_fm = SatSolver.read_dimacs_cnf_file (Path.explode dimacsfile) |
533 val prop_fm = SatSolver.read_dimacs_cnf_file (Path.explode dimacsfile) |
533 fun and_to_list (Prop_Logic.And (fm1, fm2)) acc = and_to_list fm2 (fm1 :: acc) |
534 fun and_to_list (Prop_Logic.And (fm1, fm2)) acc = and_to_list fm2 (fm1 :: acc) |