Global Sales Contact List

Contact   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

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

Notes:
Connect with EMCConnect with EMC
Need help immediately? EMC Sales Specialists are standing by to answer your questions real time.
Use Live Chat for fast, direct access to EMC Customer Service Professionals to resolve your support questions.
Explore and compare EMC products in the EMC Store, and get a price quote from EMC or an EMC partner.
We're here to help. Send us your sales inquiry and an EMC Sales Specialist will get back to you within one business day.
Want to talk? Call us to speak with an EMC Sales Specialist live.