• Top
  • Documentation
  • Books
  • Boolean-reasoning
    • Ipasir
    • Aignet
      • Base-api
      • Aignet-construction
      • Representation
        • Aignet-impl
        • Node
        • Network
          • Lookup-id
          • Lookup-stype
          • Aignet-extension-p
          • Aignet-nodes-ok
          • Aignet-outputs-aux
          • Aignet-nxsts-aux
          • Fanin
          • Aignet-outputs
          • Lookup-reg->nxst
          • Aignet-lit-fix
          • Aignet-fanins
          • Stype-count
          • Aignet-nxsts
          • Aignet-idp
          • Aignet-norm
          • Aignet-norm-p
          • Aignet-id-fix
          • Fanin-count
          • Proper-node-listp
          • Fanin-node-p
          • Node-list
          • Aignet-litp
        • Combinational-type
        • Typecode
        • Stypep
      • Aignet-copy-init
      • Aignet-simplify-with-tracking
      • Aignet-simplify-marked-with-tracking
      • Aignet-cnf
      • Aignet-simplify-marked
      • Aignet-complete-copy
      • Aignet-transforms
      • Aignet-eval
      • Semantics
      • Aignet-read-aiger
      • Aignet-write-aiger
      • Aignet-abc-interface
      • Utilities
    • Aig
    • Satlink
    • Truth
    • Ubdds
    • Bdd
    • Faig
    • Bed
    • 4v
  • Projects
  • Debugging
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
  • Math
  • Testing-utilities

• Network

Aignet-nodes-ok

Basic well-formedness constraints for the AIG network.

Signature

(aignet-nodes-ok aignet) → *

Arguments

aignet — Guard (node-listp aignet).

We require that:

• Each fanin is a well-formed in the sense of aignet-litp, i.e., it exists somewhere ``earlier'' in the network (in the suffix of the list) so that the network is topologically ordered, and it is not a combinational output node.
• Each next-state (register input) node must refer to a valid register that exists somewhere earlier in the network.

Definitions and Theorems

Function: aignet-nodes-ok

(defun aignet-nodes-ok (aignet)
 (declare (xargs :guard (node-listp aignet)))
 (let ((__function__ 'aignet-nodes-ok))
  (declare (ignorable __function__))
  (if (endp aignet)
      t
   (and (aignet-case (node->type (car aignet))
                     (node->regp (car aignet))
                     :ci t :po
                     (aignet-litp (co-node->fanin (car aignet))
                                  (cdr aignet))
                     :nxst
                     (and (aignet-litp (co-node->fanin (car aignet))
                                       (cdr aignet))
                          (< (nxst-node->reg (car aignet))
                             (stype-count :reg (cdr aignet))))
                     :gate
                     (let ((f0 (gate-node->fanin0 (car aignet)))
                           (f1 (gate-node->fanin1 (car aignet))))
                       (and (aignet-litp f0 (cdr aignet))
                            (aignet-litp f1 (cdr aignet))))
                     :otherwise nil)
        (aignet-nodes-ok (cdr aignet))))))

Theorem: aignet-nodes-ok-of-node-list-fix-aignet

(defthm aignet-nodes-ok-of-node-list-fix-aignet
  (equal (aignet-nodes-ok (node-list-fix aignet))
         (aignet-nodes-ok aignet)))

Theorem: aignet-nodes-ok-node-list-equiv-congruence-on-aignet

(defthm aignet-nodes-ok-node-list-equiv-congruence-on-aignet
  (implies (node-list-equiv aignet aignet-equiv)
           (equal (aignet-nodes-ok aignet)
                  (aignet-nodes-ok aignet-equiv)))
  :rule-classes :congruence)

Theorem: proper-node-list-when-aignet-nodes-ok

(defthm proper-node-list-when-aignet-nodes-ok
  (implies (and (aignet-nodes-ok aignet)
                (node-listp aignet))
           (proper-node-listp aignet)))

Theorem: co-fanin-ordered-when-aignet-nodes-ok

(defthm co-fanin-ordered-when-aignet-nodes-ok
 (implies (and (aignet-nodes-ok aignet)
               (equal (node->type (car (lookup-id id aignet)))
                      (out-type)))
          (< (lit-id (co-node->fanin (car (lookup-id id aignet))))
             (nfix id)))
 :rule-classes
 (:rewrite
     (:linear
          :trigger-terms
          ((lit-id (co-node->fanin (car (lookup-id id aignet))))))))

Theorem: nxst-reg-ordered-when-aignet-nodes-ok

(defthm nxst-reg-ordered-when-aignet-nodes-ok
 (implies (and (aignet-nodes-ok aignet)
               (equal (node->type (car (lookup-id id aignet)))
                      (out-type))
               (equal (node->regp (car (lookup-id id aignet)))
                      1))
          (< (nxst-node->reg (car (lookup-id id aignet)))
             (stype-count :reg (lookup-id id aignet))))
 :rule-classes
 (:rewrite
  (:linear
    :trigger-terms ((nxst-node->reg (car (lookup-id id aignet)))))))

Theorem: gate-fanin0-ordered-when-aignet-nodes-ok

(defthm gate-fanin0-ordered-when-aignet-nodes-ok
 (implies
      (and (aignet-nodes-ok aignet)
           (equal (node->type (car (lookup-id id aignet)))
                  (gate-type)))
      (< (lit-id (gate-node->fanin0 (car (lookup-id id aignet))))
         (nfix id)))
 :rule-classes
 (:rewrite
  (:linear
       :trigger-terms
       ((lit-id (gate-node->fanin0 (car (lookup-id id aignet))))))))

Theorem: gate-fanin1-ordered-when-aignet-nodes-ok

(defthm gate-fanin1-ordered-when-aignet-nodes-ok
 (implies
      (and (aignet-nodes-ok aignet)
           (equal (node->type (car (lookup-id id aignet)))
                  (gate-type)))
      (< (lit-id (gate-node->fanin1 (car (lookup-id id aignet))))
         (nfix id)))
 :rule-classes
 (:rewrite
  (:linear
       :trigger-terms
       ((lit-id (gate-node->fanin1 (car (lookup-id id aignet))))))))

Theorem: co-fanin-aignet-litp-when-aignet-nodes-ok

(defthm co-fanin-aignet-litp-when-aignet-nodes-ok
 (implies
      (and (aignet-nodes-ok aignet)
           (equal (node->type (car (lookup-id id aignet)))
                  (out-type))
           (aignet-extension-p aignet2 (cdr (lookup-id id aignet))))
      (aignet-litp (co-node->fanin (car (lookup-id id aignet)))
                   aignet2)))

Theorem: gate-fanin0-aignet-litp-when-aignet-nodes-ok

(defthm gate-fanin0-aignet-litp-when-aignet-nodes-ok
 (implies
      (and (aignet-nodes-ok aignet)
           (equal (node->type (car (lookup-id id aignet)))
                  (gate-type))
           (aignet-extension-p aignet2 (cdr (lookup-id id aignet))))
      (aignet-litp (gate-node->fanin0 (car (lookup-id id aignet)))
                   aignet2)))

Theorem: gate-fanin1-aignet-litp-when-aignet-nodes-ok

(defthm gate-fanin1-aignet-litp-when-aignet-nodes-ok
 (implies
      (and (aignet-nodes-ok aignet)
           (equal (node->type (car (lookup-id id aignet)))
                  (gate-type))
           (aignet-extension-p aignet2 (cdr (lookup-id id aignet))))
      (aignet-litp (gate-node->fanin1 (car (lookup-id id aignet)))
                   aignet2)))

Theorem: aignet-nodes-ok-of-extension

(defthm aignet-nodes-ok-of-extension
  (implies (and (aignet-extension-p y x)
                (aignet-nodes-ok y))
           (aignet-nodes-ok x)))

Theorem: aignet-nodes-ok-of-suffix-inverse

(defthm aignet-nodes-ok-of-suffix-inverse
  (implies (and (aignet-extension-bind-inverse :orig x
                                               :new y)
                (aignet-nodes-ok y))
           (aignet-nodes-ok x)))