		Search-engine friendly clone of the ACL2 documentation.

Aig-semantics

Aig-equiv

We say the AIGs X and Y are equivalent when they always evaluate to the same value, per aig-eval.

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

Function: aig-equiv

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

Definitions and Theorems

Theorem: aig-equiv-necc

(defthm aig-equiv-necc
  (implies (not (and (equal (aig-eval x env)
                            (aig-eval y env))))
           (not (aig-equiv x y))))

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

(defthm aig-equiv-witnessing-witness-rule-correct
  (implies (not ((lambda (env y x)
                   (not (equal (aig-eval x env)
                               (aig-eval y env))))
                 (aig-equiv-witness x y)
                 y x))
           (aig-equiv x y))
  :rule-classes nil)

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

(defthm aig-equiv-instancing-instance-rule-correct
  (implies (not (equal (aig-eval x env)
                       (aig-eval y env)))
           (not (aig-equiv x y)))
  :rule-classes nil)

Theorem: aig-equiv-is-an-equivalence

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