|
0
|
1 |
(* Title: HOL/ex/prop-log
|
|
|
2 |
ID: $Id$
|
|
|
3 |
Author: Tobias Nipkow
|
|
|
4 |
Copyright 1991 University of Cambridge
|
|
|
5 |
|
|
|
6 |
Inductive definition of propositional logic.
|
|
|
7 |
|
|
|
8 |
*)
|
|
|
9 |
|
|
|
10 |
PL = Finite +
|
|
|
11 |
types pl 1
|
|
|
12 |
arities pl :: (term)term
|
|
|
13 |
consts
|
|
|
14 |
false :: "'a pl"
|
|
|
15 |
"->" :: "['a pl,'a pl] => 'a pl" (infixr 90)
|
|
|
16 |
var :: "'a => 'a pl" ("#_")
|
|
|
17 |
pl_rec :: "['a pl,'a => 'b, 'b, ['b,'b] => 'b] => 'b"
|
|
|
18 |
axK,axS,axDN:: "'a pl set"
|
|
|
19 |
ruleMP,thms :: "'a pl set => 'a pl set"
|
|
|
20 |
"|-" :: "['a pl set, 'a pl] => bool" (infixl 50)
|
|
|
21 |
"|=" :: "['a pl set, 'a pl] => bool" (infixl 50)
|
|
|
22 |
eval :: "['a set, 'a pl] => bool" ("_[_]" [100,0] 100)
|
|
|
23 |
hyps :: "['a pl, 'a set] => 'a pl set"
|
|
|
24 |
rules
|
|
|
25 |
|
|
|
26 |
(** Proof theory for propositional logic **)
|
|
|
27 |
|
|
|
28 |
axK_def "axK == {x . ? p q. x = p->q->p}"
|
|
|
29 |
axS_def "axS == {x . ? p q r. x = (p->q->r) -> (p->q) -> p->r}"
|
|
|
30 |
axDN_def "axDN == {x . ? p. x = ((p->false) -> false) -> p}"
|
|
|
31 |
|
|
|
32 |
(*the use of subsets simplifies the proof of monotonicity*)
|
|
|
33 |
ruleMP_def "ruleMP(X) == {q. ? p:X. p->q : X}"
|
|
|
34 |
|
|
|
35 |
thms_def
|
|
|
36 |
"thms(H) == lfp(%X. H Un axK Un axS Un axDN Un ruleMP(X))"
|
|
|
37 |
|
|
|
38 |
conseq_def "H |- p == p : thms(H)"
|
|
|
39 |
|
|
|
40 |
sat_def "H |= p == (!tt. (!q:H. tt[q]) --> tt[p])"
|
|
|
41 |
|
|
|
42 |
pl_rec_var "pl_rec(#v,f,y,z) = f(v)"
|
|
|
43 |
pl_rec_false "pl_rec(false,f,y,z) = y"
|
|
|
44 |
pl_rec_imp "pl_rec(p->q,f,y,g) = g(pl_rec(p,f,y,g),pl_rec(q,f,y,g))"
|
|
|
45 |
|
|
|
46 |
eval_def "tt[p] == pl_rec(p, %v.v:tt, False, op -->)"
|
|
|
47 |
|
|
|
48 |
hyps_def
|
|
|
49 |
"hyps(p,tt) == pl_rec(p, %a. {if(a:tt, #a, #a->false)}, {}, op Un)"
|
|
|
50 |
|
|
|
51 |
var_inject "(#v = #w) ==> v = w"
|
|
|
52 |
imp_inject "[| (p -> q) = (p' -> q'); [| p = p'; q = q' |] ==> R |] ==> R"
|
|
|
53 |
var_neq_imp "(#v = (p -> q)) ==> R"
|
|
|
54 |
pl_ind "[| P(false); !!v. P(#v); !!p q. P(p)-->P(q)-->P(p->q)|] ==> !t.P(t)"
|
|
|
55 |
end
|