• Top
  • Documentation
  • Books
  • Boolean-reasoning
  • Projects
  • Debugging
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
    • Kestrel-books
    • X86isa
      • Program-execution
      • Sdm-instruction-set-summary
      • Tlb
      • Booting-linux
      • Introduction
      • Asmtest
      • X86isa-build-instructions
      • Publications
      • Contributors
      • Machine
      • Implemented-opcodes
      • To-do
      • Proof-utilities
        • System-level-marking-view-proof-utilities
        • Non-marking-view-proof-utilities
        • App-view-proof-utilities
        • Subset-p
        • Disjoint-p
        • Pos
        • Member-p
        • No-duplicates-p
        • Common-system-level-utils
        • Debugging-code-proofs
        • General-memory-utils
        • X86-row-wow-thms
      • Peripherals
      • Model-validation
      • Modelcalls
      • Concrete-simulation-examples
      • Utils
      • Debugging-code-proofs
    • Axe
    • Execloader
  • Math
  • Testing-utilities

• Proof-utilities

Disjoint-p

Signature

(disjoint-p x y) → *

Arguments

x — Guard (true-listp x).

y — Guard (true-listp y).

disjoint-p returns t if true-listp-satisfying inputs x and y have no element in common. Otherwise, nil is returned.

Definitions and Theorems

Function: disjoint-p

(defun disjoint-p (x y)
  (declare (xargs :guard (and (true-listp x) (true-listp y))))
  (let ((__function__ 'disjoint-p))
    (declare (ignorable __function__))
    (if (atom x)
        t
      (if (member-p (car x) y)
          nil
        (disjoint-p (cdr x) y)))))

Theorem: disjoint-p-x-x

(defthm disjoint-p-x-x
  (implies (consp x)
           (equal (disjoint-p x x) nil)))

Theorem: disjoint-p-nil-1

(defthm disjoint-p-nil-1
  (equal (disjoint-p nil y) t))

Theorem: disjoint-p-nil-2

(defthm disjoint-p-nil-2
  (equal (disjoint-p x nil) t))

Theorem: disjoint-p-cdr-1

(defthm disjoint-p-cdr-1
  (implies (disjoint-p x y)
           (disjoint-p (cdr x) y))
  :rule-classes ((:rewrite :backchain-limit-lst (0))))

Theorem: disjoint-p-cdr-2

(defthm disjoint-p-cdr-2
  (implies (disjoint-p x y)
           (disjoint-p x (cdr y)))
  :rule-classes ((:rewrite :backchain-limit-lst (0))))

Theorem: disjoint-p-cons-1

(defthm disjoint-p-cons-1
  (equal (disjoint-p (cons e x) a)
         (and (disjoint-p x a)
              (equal (member-p e a) nil))))

Theorem: disjoint-p-cons-2

(defthm disjoint-p-cons-2
  (equal (disjoint-p a (cons e x))
         (and (disjoint-p a x)
              (equal (member-p e a) nil))))

Theorem: disjoint-p-commutative

(defthm disjoint-p-commutative
  (equal (disjoint-p a b)
         (disjoint-p b a))
  :rule-classes ((:rewrite :loop-stopper ((a b)))))

Theorem: member-p-when-not-disjoint-p

(defthm member-p-when-not-disjoint-p
  (implies (and (member-p e x) (member-p e y))
           (equal (disjoint-p x y) nil)))

Theorem: not-member-p-when-disjoint-p

(defthm not-member-p-when-disjoint-p
  (implies (and (disjoint-p x y) (member-p e x))
           (equal (member-p e y) nil)))

Theorem: disjoint-p-append-1

(defthm disjoint-p-append-1
  (implies (true-listp a)
           (equal (disjoint-p (append a b) c)
                  (and (disjoint-p a c)
                       (disjoint-p b c)))))

Theorem: disjoint-p-append-2

(defthm disjoint-p-append-2
  (implies (true-listp b)
           (equal (disjoint-p a (append b c))
                  (and (disjoint-p a b)
                       (disjoint-p a c)))))