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.
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).