• Top
  • Documentation
  • Books
  • Boolean-reasoning
  • Projects
  • Debugging
  • Community
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
  • Math
    • 100-theorems
    • Arithmetic
    • Bit-vectors
      • Sparseint
      • Bitops
      • Bv
      • Ihs
      • Rtl
        • Floating-Point Exceptions and Specification of Elementary Arithmetic Instructions
        • Implementation of Elementary Operations
        • Register-Transfer Logic
          • Bit Vectors
            • Bit Slices
            • Concatenation
            • Bit Extraction
            • Signed Integer Formats
            • Recognizing Bit Vectors
          • Logical Operations
          • Basic Arithmetic Functions
        • Floating-Point Arithmetic
        • Modeling Algorithms in C++ and ACL2
        • Bibliography
    • Algebra
  • Testing-utilities

• Bit Vectors

Recognizing Bit Vectors

Recognizing Bit Vectors

Definitions and Theorems

Function: bvecp

(defun bvecp (x k)
  (declare (xargs :guard (integerp k)))
  (and (integerp x)
       (<= 0 x)
       (< x (expt 2 k))))

Theorem: bvecp-forward

(defthm bvecp-forward
  (implies (bvecp x k)
           (and (integerp x)
                (<= 0 x)
                (< x (expt 2 k))))
  :rule-classes :forward-chaining)

Function: nats

(defun nats (n)
  (declare (xargs :guard (natp n)))
  (if (zp n)
      nil
    (cons (1- n) (nats (1- n)))))

Theorem: bvecp-member

(defthm bvecp-member
  (implies (and (natp n) (bvecp x n))
           (member x (nats (expt 2 n))))
  :rule-classes nil)

Theorem: bvecp-monotone

(defthm bvecp-monotone
  (implies (and (bvecp x n)
                (<= n m)
                (case-split (integerp m)))
           (bvecp x m)))

Theorem: bvecp-shift-down

(defthm bvecp-shift-down
  (implies (and (bvecp x n) (natp n) (natp k))
           (bvecp (fl (/ x (expt 2 k))) (- n k))))

Theorem: bvecp-shift-up

(defthm bvecp-shift-up
  (implies (and (bvecp x (- n k))
                (natp k)
                (integerp n))
           (bvecp (* x (expt 2 k)) n)))

Theorem: bvecp-product

(defthm bvecp-product
  (implies (and (bvecp x m) (bvecp y n))
           (bvecp (* x y) (+ m n)))
  :rule-classes nil)

Theorem: bvecp-1-0

(defthm bvecp-1-0
  (implies (and (bvecp x 1) (not (equal x 1)))
           (equal x 0))
  :rule-classes :forward-chaining)

Theorem: bvecp-0-1

(defthm bvecp-0-1
  (implies (and (bvecp x 1) (not (equal x 0)))
           (equal x 1))
  :rule-classes :forward-chaining)