• Top
  • Documentation
  • Books
  • 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
  • Projects
  • Debugging
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
  • Math
  • Testing-utilities

• 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)))))))