		Search-engine friendly clone of the ACL2 documentation.

Proof-utilities

Subset-p

Signature
(subset-p x y) → *
Arguments: x — Guard (true-listp x).; y — Guard (true-listp y).

Definitions and Theorems

Function: subset-p

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

Theorem: subset-p-cdr-x

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

Theorem: subset-p-cdr-y

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

Theorem: subset-p-cons

(defthm subset-p-cons
  (implies (subset-p x y)
           (subset-p (cons e x) (cons e y)))
  :rule-classes ((:rewrite :backchain-limit-lst (0))))

Theorem: subset-p-reflexive

(defthm subset-p-reflexive
  (equal (subset-p x x) t))

Theorem: subset-p-transitive

(defthm subset-p-transitive
  (implies (and (subset-p x y) (subset-p y z))
           (subset-p x z)))

Theorem: subset-p-of-append-1

(defthm subset-p-of-append-1
  (equal (subset-p (append a b) x)
         (and (subset-p a x) (subset-p b x))))

Theorem: subset-p-of-append-2

(defthm subset-p-of-append-2
  (implies (or (subset-p a x) (subset-p a y))
           (subset-p a (append x y))))

Theorem: subset-p-and-append-both

(defthm subset-p-and-append-both
  (implies (subset-p a b)
           (subset-p (append e a) (append e b))))

Theorem: subset-p-of-nil

(defthm subset-p-of-nil
  (equal (subset-p x nil) (atom x)))

Theorem: subset-p-cons-2

(defthm subset-p-cons-2
  (implies (subset-p x y)
           (subset-p x (cons e y))))

Theorem: member-p-of-subset-is-member-p-of-superset

(defthm member-p-of-subset-is-member-p-of-superset
  (implies (and (subset-p x y) (member-p e x))
           (member-p e y)))

Theorem: not-member-p-of-superset-is-not-member-p-of-subset

(defthm not-member-p-of-superset-is-not-member-p-of-subset
  (implies (and (equal (member-p e y) nil)
                (subset-p x y))
           (equal (member-p e x) nil)))

Theorem: subset-p-and-remove-duplicates-equal-1

(defthm subset-p-and-remove-duplicates-equal-1
  (implies (subset-p x y)
           (subset-p (remove-duplicates-equal x)
                     y)))

Theorem: subset-p-and-remove-duplicates-equal-2

(defthm subset-p-and-remove-duplicates-equal-2
  (implies (subset-p x y)
           (subset-p x (remove-duplicates-equal y))))

Theorem: subset-p-and-remove-duplicates-equal-both

(defthm subset-p-and-remove-duplicates-equal-both
  (implies (subset-p x y)
           (subset-p (remove-duplicates-equal x)
                     (remove-duplicates-equal y))))