File: bounded-nat-listp.lisp

package info (click to toggle)
acl2 8.5dfsg-5
  • links: PTS
  • area: main
  • in suites: bookworm
  • size: 991,452 kB
  • sloc: lisp: 15,567,759; javascript: 22,820; cpp: 13,929; ansic: 12,092; perl: 7,150; java: 4,405; xml: 3,884; makefile: 3,507; sh: 3,187; ruby: 2,633; ml: 763; python: 746; yacc: 723; awk: 295; csh: 186; php: 171; lex: 154; tcl: 49; asm: 23; haskell: 17
file content (71 lines) | stat: -rw-r--r-- 2,382 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
(in-package "ACL2")

(defun bounded-nat-listp (l b)
  (declare (xargs :guard (natp b)))
  (if (atom l)
      (equal l nil)
      (and (natp (car l))
           (< (car l) b)
           (bounded-nat-listp (cdr l) b))))

(defthm bounded-nat-listp-correctness-1
  (implies (bounded-nat-listp l b)
           (nat-listp l))
  :rule-classes (:rewrite :forward-chaining))

(defthm bounded-nat-listp-correctness-2
  (implies (true-listp x)
           (equal (bounded-nat-listp (binary-append x y)
                                     b)
                  (and (bounded-nat-listp x b)
                       (bounded-nat-listp y b)))))

(defthm bounded-nat-listp-correctness-3
  (implies (and (bounded-nat-listp l (+ b 1))
                (natp b)
                (not (bounded-nat-listp l b)))
           (member-equal b l))
  :rule-classes :forward-chaining)

(defthm bounded-nat-listp-correctness-4
  (implies (bounded-nat-listp l b)
           (not (member-equal b l)))
  :rule-classes :forward-chaining)

(defthmd bounded-nat-listp-correctness-5
  (implies (and (<= x y) (bounded-nat-listp l x))
           (bounded-nat-listp l y)))

(defthm bounded-nat-listp-of-make-list-ac
  (implies (and (bounded-nat-listp ac b) (natp val) (< val b))
           (bounded-nat-listp (make-list-ac n val ac) b)))

(defthm car-of-last-when-bounded-nat-listp
  (implies (and (< 0 b) (bounded-nat-listp l b))
           (< (car (last l)) b))
  :hints (("goal" :induct (bounded-nat-listp l b)))
  :rule-classes :linear)

(defun lower-bounded-integer-listp (l b)
  (declare (xargs :guard (integerp b)))
  (if (atom l)
      (equal l nil)
      (and (integerp (car l))
           (>= (car l) b)
           (lower-bounded-integer-listp (cdr l)
                                        b))))

(defthm lower-bounded-integer-listp-correctness-2
  (implies (true-listp x)
           (equal (lower-bounded-integer-listp (binary-append x y)
                                     b)
                  (and (lower-bounded-integer-listp x b)
                       (lower-bounded-integer-listp y b)))))

(defthmd lower-bounded-integer-listp-correctness-5
  (implies (and (<= y x) (lower-bounded-integer-listp l x))
           (lower-bounded-integer-listp l y)))

(defthm lower-bounded-integer-listp-of-remove
  (implies (lower-bounded-integer-listp l b)
           (lower-bounded-integer-listp (remove-equal x l) b)))