Page 33 - Discrete Mathematics and Its Applications

12 1 / The Foundations: Logic and Proofs

TABLE 9 Table for the Bit Operators OR,
AND, and XOR.
x y x ∨ y x ∧ y x ⊕ y

0 0 0 0 0
0 1 1 0 1
1 0 1 0 1
1 1 1 1 0

Information is often represented using bit strings, which are lists of zeros and ones. When
this is done, operations on the bit strings can be used to manipulate this information.

DEFINITION 7 A bit string is a sequence of zero or more bits. The length of this string is the number of bits
in the string.

EXAMPLE 12 101010011 is a bit string of length nine. ▲

We can extend bit operations to bit strings. We define the bitwise OR, bitwise AND, and
bitwise XOR of two strings of the same length to be the strings that have as their bits the OR,
AND, and XOR of the corresponding bits in the two strings, respectively. We use the symbols
∨, ∧, and ⊕ to represent the bitwise OR, bitwise AND, and bitwise XOR operations, respectively.
We illustrate bitwise operations on bit strings with Example 13.

EXAMPLE 13 Find the bitwise OR, bitwise AND, and bitwise XOR of the bit strings 01 1011 0110 and
11 0001 1101. (Here, and throughout this book, bit strings will be split into blocks of four
bits to make them easier to read.)

Solution: The bitwise OR, bitwise AND, and bitwise XOR of these strings are obtained by taking
the OR, AND, and XOR of the corresponding bits, respectively. This gives us
01 1011 0110
11 0001 1101
11 1011 1111 bitwise OR
01 0001 0100 bitwise AND
10 1010 1011 bitwise XOR
▲
Exercises

1. Which of these sentences are propositions? What are the d) 4 + x = 5.
truth values of those that are propositions? e) The moon is made of green cheese.
n
a) Boston is the capital of Massachusetts. f) 2 ≥ 100.
b) Miami is the capital of Florida. 3. What is the negation of each of these propositions?
c) 2 + 3 = 5. a) Mei has an MP3 player.
d) 5 + 7 = 10. b) There is no pollution in New Jersey.
e) x + 2 = 11. c) 2 + 1 = 3.
f) Answer this question. d) The summer in Maine is hot and sunny.
2. Which of these are propositions?What are the truth values 4. What is the negation of each of these propositions?
of those that are propositions? a) Jennifer and Teja are friends.
a) Do not pass go. b) There are 13 items in a baker’s dozen.
b) What time is it? c) Abby sent more than 100 text messages every day.
c) There are no black flies in Maine. d) 121 is a perfect square.