244
Sets, Combinatorics, and Probability
c. x# = the string that is the reverse of x; S = set of all finite-length strings of symbols from the set { p, q, r}
d. x + y = x + y; S = ℝ − ℚ
43. How many different unary operations can be defined on a set with n elements? (Hint: Think about filling
in a table.)
44. How many different binary operations can be defined on a set with n elements? (Hint: Think about filling
in a table.)
45. We have written binary operations in infix notation, where the operation symbol appears between the two
operands, as in A + B. Evaluation of a complicated arithmetic expression is more efficient when the operations are written in postfix notation, where the operation symbol appears after the two operands, as in
AB+. Many compilers change expressions in a computer program from infix to postfix form. One way to
produce an equivalent postfix expression from an infix expression is to write the infix expression with a
full set of parentheses, move each operator to replace its corresponding right parenthesis, and then eliminate all left parentheses. (Parentheses are not required in postfix notation.) Thus,
A * B + C
becomes, when fully parenthesized,
((A * B) + C )
and the postfix notation is AB * C+. Rewrite each of the following expressions in postfix notation:
a. (A + B) * (C − D)
b. A ** B − C * D ( ** denotes exponentiation)
c. A * C + B/(C + D * B)
46. Evaluate the following postfix expressions (see Exercise 45):
a 2 4 * 5 +
b. 5 1 + 2/1 −
c. 3 4 + 5 1 − *
47. Let
A = { p, q, r, s}
B = {r, t, v}
C = { p, s, t, u}
be subsets of S = { p, q, r, s, t, u, v, w}. Find
a. B d C
b. A c C
c. C′
d. A d B d C
48. Let
A = { p, q, r, s}
B = {r, t, v}
C = { p, s, t, u}
be subsets of S = { p, q, r, s, t, u, v, w}. Find
a. B − C
b. (A c B)′
c. A × B
d. (A c B) d C′
Sets, Combinatorics, and Probability
c. x# = the string that is the reverse of x; S = set of all finite-length strings of symbols from the set { p, q, r}
d. x + y = x + y; S = ℝ − ℚ
43. How many different unary operations can be defined on a set with n elements? (Hint: Think about filling
in a table.)
44. How many different binary operations can be defined on a set with n elements? (Hint: Think about filling
in a table.)
45. We have written binary operations in infix notation, where the operation symbol appears between the two
operands, as in A + B. Evaluation of a complicated arithmetic expression is more efficient when the operations are written in postfix notation, where the operation symbol appears after the two operands, as in
AB+. Many compilers change expressions in a computer program from infix to postfix form. One way to
produce an equivalent postfix expression from an infix expression is to write the infix expression with a
full set of parentheses, move each operator to replace its corresponding right parenthesis, and then eliminate all left parentheses. (Parentheses are not required in postfix notation.) Thus,
A * B + C
becomes, when fully parenthesized,
((A * B) + C )
and the postfix notation is AB * C+. Rewrite each of the following expressions in postfix notation:
a. (A + B) * (C − D)
b. A ** B − C * D ( ** denotes exponentiation)
c. A * C + B/(C + D * B)
46. Evaluate the following postfix expressions (see Exercise 45):
a 2 4 * 5 +
b. 5 1 + 2/1 −
c. 3 4 + 5 1 − *
47. Let
A = { p, q, r, s}
B = {r, t, v}
C = { p, s, t, u}
be subsets of S = { p, q, r, s, t, u, v, w}. Find
a. B d C
b. A c C
c. C′
d. A d B d C
48. Let
A = { p, q, r, s}
B = {r, t, v}
C = { p, s, t, u}
be subsets of S = { p, q, r, s, t, u, v, w}. Find
a. B − C
b. (A c B)′
c. A × B
d. (A c B) d C′