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.
| x | y | 0 | x & y | x & ¬y | x | ¬x & y | y | x ⊕ y | x | y | ¬(x | y) | x ≡ y | ¬y | x | ¬y | ¬x | ¬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.
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).