• Top
  • Documentation
  • Books
  • Boolean-reasoning
    • Ipasir
    • Aignet
    • Aig
    • Satlink
    • Truth
    • Ubdds
      • Equal-by-eval-bdds
      • Ubdd-constructors
        • Q-and
        • Q-ite
        • Q-or
        • Q-implies
        • Q-iff
        • Q-and-c2
        • Q-and-c1
        • Q-or-c2
        • Q-not
        • Q-ite-fn
        • Q-xor
        • Cheap-and-expensive-arguments
        • Q-and-is-nil
        • Q-compose-list
        • Qv
        • Q-compose
        • Q-and-is-nilc2
        • Q-nor
        • Q-nand
      • Eval-bdd
      • Ubddp
      • Ubdd-fix
      • Q-sat
      • Bdd-sat-dfs
      • Eval-bdd-list
      • Qcdr
      • Qcar
      • Q-sat-any
      • Canonicalize-to-q-ite
      • Ubdd-listp
      • Qcons
    • Bdd
    • Faig
    • Bed
    • 4v
  • Projects
  • Debugging
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
  • Math
  • Testing-utilities

• Ubdd-constructors

Q-implies

(q-implies x y) constructs a UBDD representing (implies x y).

Definitions and Theorems

Function: q-implies-fn

(defun q-implies-fn (x y)
  (declare (xargs :guard t))
  (cond ((atom x)
         (if x (if (atom y) (if y t nil) y) t))
        ((atom y) (if y t (q-not x)))
        ((hons-equal x y) t)
        (t (qcons (q-implies-fn (car x) (car y))
                  (q-implies-fn (cdr x) (cdr y))))))

Function: q-implies-fn-memoize-condition

(defun q-implies-fn-memoize-condition (x y)
  (declare (ignorable x y)
           (xargs :guard 't))
  (and (consp x) (consp y)))

Function: q-implies-macro-fn

(defun q-implies-macro-fn (x y)
 (cond
  ((and (or (quotep x) (atom x))
        (or (quotep y) (atom y)))
   (cons 'q-implies-fn
         (cons x (cons y 'nil))))
  ((or (quotep y) (atom y))
   (cons
    'mbe
    (cons
     ':logic
     (cons
      (cons 'q-implies-fn
            (cons x (cons y 'nil)))
      (cons
       ':exec
       (cons
        (cons
         'let
         (cons
          (cons (cons 'q-implies-y-do-not-use-elsewhere
                      (cons y 'nil))
                'nil)
          (cons
           (cons
            'if
            (cons
             '(eq t q-implies-y-do-not-use-elsewhere)
             (cons
              't
              (cons
               (cons
                'prog2$
                (cons
                 '(last-chance-wash-memory)
                 (cons
                  (cons
                       'q-implies-fn
                       (cons x '(q-implies-y-do-not-use-elsewhere)))
                  'nil)))
               'nil))))
           'nil)))
        'nil))))))
  (t
   (cons
    'mbe
    (cons
     ':logic
     (cons
      (cons 'q-implies-fn
            (cons x (cons y 'nil)))
      (cons
       ':exec
       (cons
        (cons
         'let
         (cons
          (cons (cons 'q-implies-x-do-not-use-elsewhere
                      (cons x 'nil))
                'nil)
          (cons
           (cons
            'if
            (cons
             '(not q-implies-x-do-not-use-elsewhere)
             (cons
              't
              (cons
               (cons
                'prog2$
                (cons
                 '(last-chance-wash-memory)
                 (cons (cons 'q-implies-fn
                             (cons 'q-implies-x-do-not-use-elsewhere
                                   (cons y 'nil)))
                       'nil)))
               'nil))))
           'nil)))
        'nil))))))))

Theorem: ubddp-of-q-implies

(defthm ubddp-of-q-implies
  (implies (and (force (ubddp x))
                (force (ubddp y)))
           (equal (ubddp (q-implies x y)) t)))

Theorem: eval-bdd-of-q-implies

(defthm eval-bdd-of-q-implies
  (equal (eval-bdd (q-implies x y) values)
         (implies (eval-bdd x values)
                  (eval-bdd y values))))

Theorem: canonicalize-q-implies

(defthm canonicalize-q-implies
  (implies (and (force (ubddp x))
                (force (ubddp y)))
           (equal (q-implies x y) (q-ite x y t))))

Theorem: q-implies-of-nil

(defthm q-implies-of-nil
  (and (equal (q-implies nil x) t)
       (equal (q-implies x nil) (q-not x))))

Theorem: q-implies-of-t-left-slow

(defthm q-implies-of-t-left-slow
  (equal (q-implies t x)
         (if (consp x) x (if x t nil))))

Theorem: q-implies-of-t-left-aggressive

(defthm q-implies-of-t-left-aggressive
  (implies (force (ubddp x))
           (equal (q-implies t x) x)))

Theorem: q-implies-of-t-right

(defthm q-implies-of-t-right
  (equal (q-implies x t) t))

Theorem: q-implies-of-self

(defthm q-implies-of-self
  (equal (q-implies x x) t))