		Search-engine friendly clone of the ACL2 documentation.

Faig

Faig-equiv

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

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

Function: faig-equiv

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

Definitions and Theorems

Theorem: faig-equiv-necc

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

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

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

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

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

Theorem: faig-equiv-is-an-equivalence

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

Subtopics

Faig-equiv-thms: Basic theorems about faig-equiv.