• Top
  • Documentation
  • Books
  • Recursion-and-induction
  • Boolean-reasoning
    • Ipasir
    • Aignet
    • Aig
    • Satlink
    • Truth
    • Ubdds
    • Bdd
    • Faig
      • Faig-constructors
      • Faig-onoff-equiv
      • Faig-purebool-p
        • Faig-purebool-check
        • Faig-purebool-list-p
        • Faig-purebool-aig
      • Faig-alist-equiv
      • Faig-equiv
      • Faig-eval
      • Faig-restrict
      • Faig-fix
      • Faig-partial-eval
      • Faig-compose
      • Faig-compose-alist
      • Patbind-faig
      • Faig-constants
    • Bed
    • 4v
  • Debugging
  • Projects
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
  • Testing-utilities
  • Math

• Faig-purebool-p

Faig-purebool-check

An executable version of faig-purebool-p using SAT.

Signature

(faig-purebool-check x &key (config 'satlink::*default-config*)) 
  → 
(mv fail purebool alist)

Arguments

x — The FAIG to check.

config — Guard (satlink::config-p config).

Returns

fail — If true, calling the SAT solver failed and the other answers are meaningless.
    Type (booleanp fail).

purebool — Does this FAIG always evaluate to purely Boolean?.
    Type (booleanp purebool).

alist — When this FAIG is not purely Boolean: an example environment for faig-eval that drives it to X or Z.

Definitions and Theorems

Function: faig-purebool-check-fn

(defun faig-purebool-check-fn (x config)
       (declare (xargs :guard (satlink::config-p config)))
       (let ((__function__ 'faig-purebool-check))
            (declare (ignorable __function__))
            (b* ((aig (faig-purebool-aig x))
                 ((mv status alist)
                  (aig-sat (aig-not aig) :config config))
                 ((when (eq status :sat))
                  (mv nil nil alist))
                 ((when (eq status :unsat))
                  (mv nil t nil)))
                (mv t nil nil))))

Theorem: booleanp-of-faig-purebool-check.fail

(defthm booleanp-of-faig-purebool-check.fail
        (b* (((mv ?fail ?purebool ?alist)
              (faig-purebool-check-fn x config)))
            (booleanp fail))
        :rule-classes :type-prescription)

Theorem: booleanp-of-faig-purebool-check.purebool

(defthm booleanp-of-faig-purebool-check.purebool
        (b* (((mv ?fail ?purebool ?alist)
              (faig-purebool-check-fn x config)))
            (booleanp purebool))
        :rule-classes :type-prescription)

Theorem: faig-purebool-check-correct

(defthm faig-purebool-check-correct
        (b* (((mv fail purebool ?alist)
              (faig-purebool-check x :config config)))
            (implies (not fail)
                     (equal purebool (faig-purebool-p x)))))

Theorem: faig-purebool-counterexample-correct

(defthm faig-purebool-counterexample-correct
        (b* (((mv fail ?purebool alist)
              (faig-purebool-check x :config config)))
            (implies (and (not fail)
                          (not (faig-purebool-p x)))
                     (and (not (equal (faig-eval x alist) (faig-f)))
                          (not (equal (faig-eval x alist)
                                      (faig-t)))))))