• Top
  • Documentation
  • Books
  • Boolean-reasoning
    • Ipasir
    • Aignet
    • Aig
    • Satlink
    • Truth
    • Ubdds
    • Bdd
    • Faig
    • Bed
    • 4v
      • 4v-sexprs
        • 4v-sexpr-vars
        • 4v-sexpr-eval
        • 4v-sexpr-to-faig
        • 4v-sexpr-restrict-with-rw
        • 4vs-constructors
        • 4v-sexpr-compose-with-rw
        • 4v-sexpr-restrict
        • 4v-sexpr-alist-extract
        • 4v-sexpr-compose
        • 4v-nsexpr-p
        • 4v-sexpr-purebool-p
        • 4v-sexpr-<=
        • Sfaig
        • Sexpr-equivs
          • 4v-sexpr-alist-equiv
          • 4v-env-equiv
          • 4v-sexpr-list-equiv
          • 4v-sexpr-equiv
          • 4v-alists-agree
            • 4v-alists-disagree-witness
          • Key-and-env-equiv
          • 4v-sexpr-alist-equiv-alt
          • 4v-sexpr-alist-pair-equiv
          • 4v-cdr-consp-equiv
          • 4v-cdr-equiv
        • 3v-syntax-sexprp
        • Sexpr-rewriting
        • 4v-sexpr-ind
        • 4v-alist-extract
      • 4v-monotonicity
      • 4v-operations
      • Why-4v-logic
      • 4v-<=
      • 4vp
      • 4vcases
      • 4v-fix
      • 4v-lookup
  • Projects
  • Debugging
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
  • Math
  • Testing-utilities

• Sexpr-equivs

4v-alists-agree

See whether two four-valued alists agree on particular keys.

Definitions and Theorems

Function: 4v-alists-agree

(defun 4v-alists-agree (keys al1 al2)
  (declare (xargs :guard t))
  (or (atom keys)
      (and (equal (4v-lookup (car keys) al1)
                  (4v-lookup (car keys) al2))
           (4v-alists-agree (cdr keys) al1 al2))))

Theorem: 4v-alists-agree-equiv

(defthm 4v-alists-agree-equiv
  (implies (and (4v-alists-agree keys al1 al2)
                (member-equal key keys))
           (equal (equal (4v-lookup key al1)
                         (4v-lookup key al2))
                  t)))

Theorem: 4v-alists-agree-self

(defthm 4v-alists-agree-self
  (4v-alists-agree k x x))

Theorem: 4v-alists-agree-commutes

(defthm 4v-alists-agree-commutes
  (implies (4v-alists-agree vars al2 al1)
           (4v-alists-agree vars al1 al2)))

Theorem: 4v-alists-agree-transitive1

(defthm 4v-alists-agree-transitive1
  (implies (and (4v-alists-agree vars al1 al2)
                (4v-alists-agree vars al2 al3))
           (4v-alists-agree vars al1 al3)))

Theorem: 4v-alists-agree-transitive2

(defthm 4v-alists-agree-transitive2
  (implies (and (4v-alists-agree vars al1 al2)
                (4v-alists-agree vars al2 al3))
           (4v-alists-agree vars al1 al3)))

Theorem: 4v-alists-agree-append

(defthm 4v-alists-agree-append
  (equal (4v-alists-agree (append k1 k2) a b)
         (and (4v-alists-agree k1 a b)
              (4v-alists-agree k2 a b))))

Theorem: 4v-alists-agree-witnessing-witness-rule-correct

(defthm 4v-alists-agree-witnessing-witness-rule-correct
  (implies ((lambda (witness al2 al1 keys)
              (if (not (member-equal witness keys))
                  (not (member-equal witness keys))
                (equal (4v-lookup witness al1)
                       (4v-lookup witness al2))))
            (4v-alists-disagree-witness keys al1 al2)
            al2 al1 keys)
           (4v-alists-agree keys al1 al2))
  :rule-classes nil)

Theorem: 4v-alists-agree-instancing-instance-rule-correct

(defthm 4v-alists-agree-instancing-instance-rule-correct
  (implies (not (if (not (member-equal key keys))
                    (not (member-equal key keys))
                  (equal (4v-lookup key al1)
                         (4v-lookup key al2))))
           (not (4v-alists-agree keys al1 al2)))
  :rule-classes nil)

Theorem: 4v-alists-agree-to-4v-env-equiv

(defthm 4v-alists-agree-to-4v-env-equiv
  (iff (4v-alists-agree keys al1 al2)
       (4v-env-equiv (4v-alist-extract keys al1)
                     (4v-alist-extract keys al2))))

Theorem: set-equiv-implies-equal-4v-alists-agree-1

(defthm set-equiv-implies-equal-4v-alists-agree-1
  (implies (set-equiv keys keys-equiv)
           (equal (4v-alists-agree keys a b)
                  (4v-alists-agree keys-equiv a b)))
  :rule-classes (:congruence))

Theorem: 4v-env-equiv-implies-equal-4v-alists-agree-2

(defthm 4v-env-equiv-implies-equal-4v-alists-agree-2
  (implies (4v-env-equiv al al-equiv)
           (equal (4v-alists-agree keys al al2)
                  (4v-alists-agree keys al-equiv al2)))
  :rule-classes (:congruence))

Subtopics

4v-alists-disagree-witness

Try to find a key for which two four-valued alists don't agree.