2-3 Inequalities among Logical and Arithmetic Expressions

Inequalities among binary logical expressions whose values are interpreted as unsigned integers are nearly trivial to derive. Here are two examples:

These can be derived from a list of all binary logical operations, shown in Table 2-1.

Let f(x, y) and g(x, y) represent two columns in Table 2-1. If for each row in which f(x, y) is 1, g(x, y) also is 1, then for all (x, y), Clearly, this extends to word-parallel logical operations. One can easily read off such relations (most of which are trivial) as and so on. Furthermore, if two columns have a row in which one entry is 0 and the other is 1, and another row in which the entries are 1 and 0, respectively, then no inequality relation exists between the corresponding logical expressions. So the question of whether or not is completely and easily solved for all binary logical functions f and g.

Table 2-1. The 16 Binary Logical Operations
x	y	0	x & y	x & ?span class=docemphasis1>y	x	?span class=docemphasis1>x & y	y	x y	x | y	?x | y)	x y	?span class=docemphasis1>y	x | ?span class=docemphasis1>y	?span class=docemphasis1>x	?span class=docemphasis1>x | y	?x & y)	1
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Use caution when manipulating these relations. For example, for ordinary arithmetic, if x + y a and z x, then z + y a. But this inference is not valid if "+" is replaced with or.

Inequalities involving mixed logical and arithmetic expressions are more interesting. Below is a small selection.

a.

b.

c.

d.

e.

The proofs of these are quite simple, except possibly for the relation By |x - y| we mean the absolute value of x - y, which may be computed within the domain of unsigned numbers as max(x, y) - min(x, y). This relation may be proven by induction on the length of x and y (the proof is a little easier if you extend them on the left rather than on the right).