3.3  Algebraic Properties

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

The first two lemmas are immediate consequences of the definitions.

Lemma 3.3.1   (logand-x-0,logior-x-0,logxor-x-0) For all $ x \in \mathbb{Z}$,

(a) $ x\;\verb!&!\;0 = 0$;
(b) $ x\;\verb!\vert!\;0 = x$;
(c) $ x\;\verb!^!\;0 = x$.

Lemma 3.3.2   (logand-self,logior-self,logxor-self) For all $ x \in \mathbb{Z}$ and $ y
\in \mathbb{Z}$,

(a) $ x\;\verb!&!\;x = x$;
(b) $ x\;\verb!\vert!\;x = x$;
(c) $ x\;\verb!^!\;x = 0$.

  (lognot-lognot) For all $ x \in \mathbb{Z}$, $ \verb! !(\verb! !x) = x$.

PROOF: By Definition 3.2.1, $ \verb! !(\verb! !x) = -(-x - 1) - 1 = x$


All of the remaining results of this section may be derived in a straightforward manner from Lemmas 3.2.5, 3.1.14, and 2.3.22.

Lemma 3.3.4   (logand-x-m1,logior-x-m1,logxor-x-m1) For all $ x \in \mathbb{Z}$,

(a) $ x\;\verb!&!\;-1 = x$;
(b) $ x\;\verb!\vert!\;-1 = -1$;
(c) $ x\;\verb!^!\;-1 = \verb! !x$.

  (logior-not-0,logxor-not-0) For all $ x \in \mathbb{Z}$ and $ y
\in \mathbb{Z}$,

(a) $ x\;\verb!\vert!\;y = 0 \Leftrightarrow x = y = 0$;
(b) $ x\;\verb!^!\;y = 0 \Leftrightarrow x = y$.

PROOF: Suppose $ x\;\verb!\vert!\;y = 0$. By Lemma 3.1.14, for all $ k \in \mathbb{N}$

$\displaystyle x[k] \;\verb!\vert!\; y[k] = (x\;\verb!\vert!\;y)[k] = 0[k] = 0,
$

and it is readily seen by exhaustive computation that this implies $ x[k] = y[k] = 0$. It follows from Lemma 2.3.22 that $ x = y = 0$. A similar argument applies to (b). 


The proofs the remaining lemmas are sufficiently similar to that of Lemma 3.3.5 that they may be safely omitted.

Lemma 3.3.6   (logand-commutative,logior-commutative,logxor-commutative) For all $ x \in \mathbb{Z}$, $ y
\in \mathbb{Z}$, and $ n \in \mathbb{Z}$,

(a) $ x\;\verb!&!\;y = y\;\verb!&!\;x$;
(b) $ x\;\verb!\vert!\;y = y\;\verb!\vert!\;x$;
(c) $ x\;\verb!^!\;y = y\;\verb!^!\;x$.

Lemma 3.3.7   (logand-associative,logior-associative,logxor-associative) For all $ x \in \mathbb{N}$, $ y \in \mathbb{N}$, and $ z \in \mathbb{N}$,

(a) $ (x\;\verb!&!\;y) \;\verb!&!\;z = x\;\verb!&!\;(y\;\verb!&!\;z)$;
(b) $ (x\;\verb!\vert!\;y) \;\verb!\vert!\;z = x\;\verb!\vert!\;(y\;\verb!\vert!\;z)$;
(c) $ (x\;\verb!^!\;y) \;\verb!^!\;z = x\;\verb!^!\;(y\;\verb!^!\;z)$.

Lemma 3.3.8   (logior-logand,logand-logior,log3) For all $ x \in \mathbb{N}$, $ y \in \mathbb{N}$, and $ z \in \mathbb{N}$,

(a) $ x\;\verb!\vert!\;y) \;\verb!&!\;z = (x\;\verb!\vert!\;y)\;\verb!&!\;(x\;\verb!\vert!\;z)$;
(b) $ x\;\verb!&!\;(y \;\verb!\vert!\;z) = x\;\verb!&!\;y\;\verb!\vert!\;x\;\verb!&!\;z$;
(c) $ x\;\verb!&!\;y\;\verb!\vert!\; x\;\verb!&!\;z \;\verb!\vert!\; y\;\verb!&!\;z = x\;\verb!&!\;y\;\verb!\vert!\; (x\;\verb!^!\;y)\;\verb!&!\;z$.

Lemma 3.3.9   (logxor-rewrite,lognot-logxor) For all $ x \in \mathbb{N}$ and $ y \in \mathbb{N}$,

(a) $ x\;\verb!^!\;y = x\;\verb!&!\;\verb! !y\;\verb!\vert!\;y\;\verb!&!\;\verb! !x$;
(b) $ \verb! !(x\;\verb!^!\;y) = (\verb! !x)\;\verb!^!\;y$.

David Russinoff 2017-08-01