next up previous contents
Next: Floating-Point Arithmetic Up: Logical Operations Previous: Binary Operations   Contents


Algebraic Properties

We conclude this chapter with a set of identities pertaining to compositions of logical operations.

  (lnot-lnot) For all $ x \in \mathbb{N}$ and $ n \in \mathbb{N}$ ,

$\displaystyle \verb! !(\verb! !x[n$-$\displaystyle 1:0]) = x[n$-$\displaystyle 1:0].$

PROOF: By Definition 3.1.1,

$\displaystyle \verb! !(\verb! !x[n$-$\displaystyle 1:0]) = 2^n - (2^n - x[n$-$\displaystyle 1:0] - 1) - 1 = x[n$-$\displaystyle 1:0].$

  (land-commutative,lior-commutative,lxor-commutative)
For all $ x \in \mathbb{N}$ , $ y \in \mathbb{N}$ , and $ n \in \mathbb{N}$ ,

(a) $ x[n$-$ 1:0] \;\verb!&!\; y[n$-$ 1:0] = y[n$-$ 1:0]\;\verb!&!\;x[n$-$ 1:0]$ ;
(b) $ x[n$-$ 1:0] \;\verb!\vert!\; y[n$-$ 1:0] = y[n$-$ 1:0]\;\verb!\vert!\;x[n$-$ 1:0]$ ;
(c) $ x[n$-$ 1:0] \;\verb!^!\; y[n$-$ 1:0] = y[n$-$ 1:0]\;\verb!^!\;x[n$-$ 1:0]$ .

PROOF: We shall present the proof of (a); (b) and (c) are similar.

Let $ A = x[n$-$ 1:0] \;\verb!&!\; y[n$-$ 1:0]$ and $ B = y[n$-$ 1:0]\;\verb!&!\;x[n$-$ 1:0]$ . By Lemma 3.2.3, $ A$ and $ B$ are both bit vectors of width $ n$ .

Let $ k \in \mathbb{N}$ , $ k<n$ . By Lemma 3.2.10,

$\displaystyle A[k] = x[k]\;\verb!&!\;y[k]$

and

$\displaystyle B[k] = y[k]\;\verb!&!\;x[k].$

By considering all four possible combinations of $ x[k]$ and $ y[k]$ and instantiating Definition 3.2.1 with $ n=1$ , we may show that $ A[k] = B[k]$ .

Finally, we apply Lemma 2.3.16 to both $ A$ and $ B$ :

$\displaystyle A = \sum_{k=0}^{n-1}A[k] = \sum_{k=0}^{n-1}B[k] = B.$

The proofs of all of the remaining lemmas of this section are sufficiently similar to that of Lemma 3.3.2 that they may be safely omitted.

Lemma 3.3.3   (land-associative,lior-associative,lxor-associative)
For all $ x \in \mathbb{N}$ , $ y \in \mathbb{N}$ , $ z \in \mathbb{N}$ , and $ n \in \mathbb{N}$ ,

(a) $ (x[n$-$ 1:0] \;\verb!&!\; y[n$-$ 1:0]) \;\verb!&!\;z[n$-$ 1:0]$
              $ = x[n$-$ 1:0]\;\verb!&!\;(y[n$-$ 1:0]\;\verb!&!\;z[n$-$ 1:0])$

(b) $ (x[n$-$ 1:0] \;\verb!\vert!\; y[n$-$ 1:0]) \;\verb!\vert!\;z[n$-$ 1:0]$
              $ = x[n$-$ 1:0]\;\verb!\vert!\;(y[n$-$ 1:0]\;\verb!\vert!\;z[n$-$ 1:0])$

(c) $ (x[n$-$ 1:0] \;\verb!^!\; y[n$-$ 1:0]) \;\verb!^!\;z[n$-$ 1:0]$
              $ = x[n$-$ 1:0]\;\verb!^!\;(y[n$-$ 1:0]\;\verb!^!\;z[n$-$ 1:0])$ .

Lemma 3.3.4   (land-self,lior-self,lxor-self)
For all $ x \in \mathbb{N}$ , $ y \in \mathbb{N}$ , and $ n \in \mathbb{N}$ ,

(a) $ x[n$-$ 1:0]\;\verb!&!\;x[n$-$ 1:0] = x[n$-$ 1:0]$ ;
(b) $ x[n$-$ 1:0]\;\verb!\vert!\;x[n$-$ 1:0] = x[n$-$ 1:0]$ ;
(c) $ x[n$-$ 1:0]\;\verb!^!\;x[n$-$ 1:0] = 0$ .

Lemma 3.3.5   (lior-land-1,lior-land-2,land-lior-1,land-lior-2,
lior-land-lxor, lxor-rewrite,lnot-lxor)
For all $ x \in \mathbb{N}$ , $ y \in \mathbb{N}$ , $ z \in \mathbb{N}$ , and $ n \in \mathbb{N}$ ,

(a) $ x[n$-$ 1:0] \;\verb!\vert!\; y[n$-$ 1:0]) \;\verb!&!\;z[n$-$ 1:0]$
            $ = (x[n$-$ 1:0] \;\verb!\vert!\; y[n$-$ 1:0])\;\verb!&!\;(x[n$-$ 1:0]\;\verb!\vert!\;z[n$-$ 1:0])$ ;

(b) $ x[n$-$ 1:0]\;\verb!&!\;(y[n$-$ 1:0]\;\verb!\vert!\;z[n$-$ 1:0])$
            $ = x[n$-$ 1:0] \;\verb!&!\; y[n$-$ 1:0]\;\verb!\vert!\;x[n$-$ 1:0]\;\verb!&!\;z[n$-$ 1:0]$ ;

(c) $ x[n$-$ 1:0] \;\verb!&!\; y[n$-$ 1:0]\;\verb!\vert!\;x[n$-$ 1:0]\;\verb!&!\;z[n$-$ 1:0] \;\verb!\vert!\; y[n$-$ 1:0]\;\verb!&!\;z[n$-$ 1:0]$
            $ = x[n$-$ 1:0] \;\verb!&!\; y[n$-$ 1:0]\;\verb!\vert!\; (x[n$-$ 1:0] \;\verb!^!\; y[n$-$ 1:0]) \;\verb!&!\;z[n$-$ 1:0]$ ;

(d) $ x[n$-$ 1:0] \;\verb!^!\; y[n$-$ 1:0]$
            $ = x[n$-$ 1:0]\;\verb!&!\;\verb! !y[n$-$ 1:0] \;\verb!\vert!\; y[n$-$ 1:0]\;\verb!&!\;\verb! !x[n$-$ 1:0]$ ;

(e) $ \verb! !(x[n$-$ 1:0] \;\verb!^!\; y[n$-$ 1:0]) = (\verb! !x[n$-$ 1:0])\;\verb!^!\;y[n$-$ 1:0]$ .

next up previous contents
Next: Floating-Point Arithmetic Up: Logical Operations Previous: Binary Operations   Contents
David Russinoff 2007-01-02