• Top
  • Documentation
  • Books
  • Recursion-and-induction
  • Boolean-reasoning
    • Ipasir
    • Aignet
    • Aig
      • Aig-constructors
      • Aig-vars
      • Aig-sat
      • Bddify
      • Aig-substitution
      • Aig-other
      • Aig-semantics
        • Aig-eval
        • Aig-alist-equiv
        • Aig-env-equiv
        • Aig-equiv
        • Aig-eval-alist
        • Aig-eval-list
        • Aig-eval-alists
      • Aig-and-count
    • Satlink
    • Truth
    • Ubdds
    • Bdd
    • Faig
    • Bed
    • 4v
  • Debugging
  • Projects
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
  • Testing-utilities
  • Math

• Aig-semantics

Aig-env-equiv

We say the environments X and Y are equivalent when they give equivalent values to variables looked up with aig-env-lookup.

This is a universal equivalence, introduced using def-universal-equiv.

Function: aig-env-equiv

(defun aig-env-equiv (x y)
       (declare (xargs :non-executable t))
       (declare (xargs :guard t))
       (prog2$ (throw-nonexec-error 'aig-env-equiv
                                    (list x y))
               (let ((key (aig-env-equiv-witness x y)))
                    (and (iff (aig-env-lookup key x)
                              (aig-env-lookup key y))))))

Definitions and Theorems

Theorem: aig-env-equiv-necc

(defthm aig-env-equiv-necc
        (implies (not (and (iff (aig-env-lookup key x)
                                (aig-env-lookup key y))))
                 (not (aig-env-equiv x y))))

Theorem: aig-env-equiv-witnessing-witness-rule-correct

(defthm aig-env-equiv-witnessing-witness-rule-correct
        (implies (not ((lambda (key y x)
                               (not (iff (aig-env-lookup key x)
                                         (aig-env-lookup key y))))
                       (aig-env-equiv-witness x y)
                       y x))
                 (aig-env-equiv x y))
        :rule-classes nil)

Theorem: aig-env-equiv-instancing-instance-rule-correct

(defthm aig-env-equiv-instancing-instance-rule-correct
        (implies (not (iff (aig-env-lookup key x)
                           (aig-env-lookup key y)))
                 (not (aig-env-equiv x y)))
        :rule-classes nil)

Theorem: aig-env-equiv-is-an-equivalence

(defthm aig-env-equiv-is-an-equivalence
        (and (booleanp (aig-env-equiv x y))
             (aig-env-equiv x x)
             (implies (aig-env-equiv x y)
                      (aig-env-equiv y x))
             (implies (and (aig-env-equiv x y)
                           (aig-env-equiv y z))
                      (aig-env-equiv x z)))
        :rule-classes (:equivalence))

Theorem: aig-env-equiv-implies-equal-aig-env-lookup-2

(defthm aig-env-equiv-implies-equal-aig-env-lookup-2
        (implies (aig-env-equiv x x-equiv)
                 (equal (aig-env-lookup key x)
                        (aig-env-lookup key x-equiv)))
        :rule-classes (:congruence))

Theorem: alist-equiv-refines-aig-env-equiv

(defthm alist-equiv-refines-aig-env-equiv
        (implies (alist-equiv x y)
                 (aig-env-equiv x y))
        :rule-classes (:refinement))