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.
