src/HOL/ex/SAT_Examples.thy
changeset 55240 efc4c0e0e14a
parent 55239 97921d23ebe3
child 56815 848d507584db
equal deleted inserted replaced
55239:97921d23ebe3 55240:efc4c0e0e14a
     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)