RSA Laboratories

A.6 Boolean expressions

Let B be a set with two elements, say B = {1,0} (B = {TRUE, FALSE} is another possibility). A boolean expression can be viewed as a function

f : Bn ® B,

where n is a nonnegative integer indicating the number of variables in the expression. A typical boolean expression is built up by a number of unary and binary operations. The most useful unary operation is Ø (negation), which is defined as Øp = 1-p. Some of the most important binary operations are Ù (AND), Ú (OR), Å (XOR), ®, and «:

p q p Ùq p Úq p Åq p ® q p « q
0 0 0 0 0 1 1
0 1 0 1 1 1 0
1 0 0 1 1 0 0
1 1 1 1 0 1 1

For example, the boolean expression

f(p,q,r) = (p ® q) Ù(q ® r)

is equal to 1 (TRUE) if and only if p £ q £ r.

Another more general kind of boolean expression is a function

f : Bn ® Bm,

where m is a positive integer. With m = n, we may identify a couple of useful operations. Note that an element in Bn can be interpreted as the binary representation of an integer between 0 and 2n-1. In this manner we may perform addition and multiplication modulo 2n as described in Section A.2. Another useful operation is rotation: For w = (w1, ¼, wn) Î Bn and k an integer, let w << k mean that we rotate the content of w k steps to the left. For example,

(w1, w2, w3, w4, w5, w6, w7) << 3 = (w4, w5, w6, w7, w1, w2, w3)

Similarly, w >> k means rotation of w k steps to the right.

Top of the page