DISCRETE MATH II PROBLEMS
Contents
1.
2.
3.
4.
5.
Review: types of proofs
Introduction to Number Theory
Relations
Combinatorics
Boolean Algebra
1
1
5
8
12
1. Review: types of proofs
x
P
2
Problem 1.1. Prove that
(−1)k k 2 = x 2+x (−1)x for all x ∈ Z>0 .
k=1
Problem 1.2. Prove that
√
14 is irrational, using definitions only.
Problem 1.3. Let p be a positive integer. Prove that if x is irrational, then
irrational.
√
p
x is also
Problem 1.4. State the converse of the previous statement, and determine if it is true or
false.
Problem 1.5. Prove that x is odd if and only if 2x2 + x + 1 is even.
Problem 1.6. Prove that |c − d| ≤ 2 |d| + |c| + 1 for all c, d ∈ R.
Problem 1.7. Prove that if y = x5 − x and x > 1, then x5 + x − 2 ≥ y. Also, prove or
disprove the converse.
2. Introduction to Number Theory
Problem 2.1. Let a = 28, b = −2, c = 14, d = 0, e = 3. Determine which statements below
are true or false.
(a) a|b
(b) b|a
(c) c|d
(d) (c + e) |a
(e) ∃s ∈ Z (c = bs)
(f) ∃y ∈ Z (by|c)
(g) ∀y ∈ Z (by|c)
Problem 2.2. Prove that if a, b, c ∈ Z, then a|b and b|c implies that a|c.
Problem 2.3. Prove that if a and b are two integers such that a|b and b|a, then a = ±b.
Problem 2.4. Prove that if a, b, c ∈ Z, and if a|b and a|c, then a|(kb + mc) for all k, m ∈ Z.
1
2
DISCRETE MATH II PROBLEMS
Problem 2.5. Prime factor the following numbers
(a) 3456
(b) 9889
(c) 10000
(d) 17! (Recall that 17! is the product of the integers from 1 to 17.)
(e) 6.7 × 1035
Problem 2.6. Use the primality test to determine if the following numbers are prime. (Calculator use allowed. Show the numbers that are checked.)
(a) 67
(b) 221
(c) 4241
(d) 5257
(e) 34679
(f) 10123
Problem 2.7. Implement the division algorithm with the given number and divisor; find the
quotient and remainder.
(a) 23, d = 7
(b) −23, d = 7
(c) −345, d = 12
(d) −345, d = 500
(e) 75, d = 15
(f) −75, d = 15
Problem 2.8. Find the following.
(a) gcd (−4, −38)
(b) lcm (−4, −38)
(c) gcd (48, 63)
(d) lcm (48, 63)
(e) (−77, 49)
(f) lcm (−77, 49)
(g) (35 74 112 , 34 72 13)
(h) [35 74 112 , 34 72 13]
Problem 2.9. Use the Euclidean algorithm to find the following.
(a) gcd (12, 456)
(b) (−450, 85)
(c) gcd (963, −657)
(d) gcd (61, 484)
(e) gcd (42823, 2040)
Problem 2.10. As in B´ezout’s Identity, find integers x and y such that
(a) 3x + 17y = 1
(b) 71x − 50y = 1
(c) −48x + 132y = 12
Problem 2.11. Prove that if a, b, c, d ∈ Z and a|b and c|d, then ac|bd.
DISCRETE MATH II PROBLEMS
3
Problem 2.12. Prove that if x and y are odd integers, then x2 +y 2 is even but is not divisible
by 4.
Problem 2.13. Suppose that a and b are relatively prime positive integers. Prove that if
c ∈ Z, a|c, and b|c, then ab|c.
Problem 2.14. Prove that the conclusion to the previous problem is false if the “relatively
prime” assumption is removed.
Problem 2.15. Prove or disprove:
(a) If x and y are odd multiples of three, then x3 + y 2 is divisible by 18.
(b) If x and y are multiples of three, then x3 + y 2 is divisible by 18.
Problem 2.16. Find all pairs of positive integers (x, y) such that (x, y) = 10 and [x, y] =
100.
Problem 2.17. Prove that if (a, b) = c, then (a2 , b2 ) = c2 .
Problem 2.18. Evaluate the following
(a) −36 mod 5
(b) 36 mod 5
(c) 403 mod 3
(d) −4637 mod 25
(e) 511 mod 7
(f) (10!) mod 11
(g) 1072001 mod 9
(h) 6777843 mod 2
(i) (37643542 − 7 · 89647329 ) mod 8
(j) (37643542 − 7 · 89647329 ) mod 5
Problem 2.19. Find the last digit (i.e. ones digit) for each of the following numbers:
(a) 945683
(b) 36754233
(c) 57684923
(d) 11678934
Problem 2.20. Prove that for every integer n, n7 − n4 is a multiple of three.
Problem 2.21. In each case, find the multiplicative inverse of x mod n, or explain why no
inverse exists.
(a) x = 4, n = 5
(b) x = 4, n = 6
(c) x = 4, n = 7
(d) x = 43, n = 50
(e) x = 12, n = 4329
(f) x = 45, n = 91
P
Problem 2.22. Suppose that n0 , n1 , ..., nk ∈ Z. Prove that kj=0 10j nj
is divisible by 9 if and only if
k
X
nj
j=0
4
DISCRETE MATH II PROBLEMS
is divisible by 9.
Problem 2.23. Suppose that n0 , n1 , ..., nk ∈ Z. Prove that
is divisible by 11 if and only if
k
X
(−1)j nj
Pk
j=0
10j nj
j=0
is divisible by 11.
Problem 2.24. Find ϕ (n) for each integer n given below.
(a) n = 43
(b) n = 44
(c) n = 45
(d) n = 46
(e) n = 25
(f) n = 100
Problem 2.25. Find the public and private keys of the RSA encryption algorithm corresponding to the prime numbers given.
(a) p = 7, q = 11
(b) p = 41, q = 43
(c) p = 71, q = 113
(d) p = 31, q = 89
Problem 2.26. Encrypt the message “MATH IS FUN” using the same encoding scheme,
and the same p, q, n, e as in the example at the end of Section 2.4 .
Problem 2.27. Generate the public and private keys of the RSA encryption algorithm starting from the primes p = 19, q = 23 . Suppose that the message m = 401 is sent using these
keys. Find the corresponding encrypted message c, and verify that the private key correctly
decrypts c to obtain m = 401.
Problem 2.28. Generate the public and private keys of the RSA encryption algorithm starting from the primes p = 101, q = 53. Suppose that the message m = 2071 is sent using these
keys. Find the corresponding encrypted message c, and verify that the private key correctly
decrypts c to obtain m = 2071.
Problem 2.29. A message was encoded using blank = 00, A = 01, ..., Z = 26, and it is
encrypted using the public key address (n, e) = (8927, 6989). (Hint: 79 (113) = 8927.) The
ciphertext message is:
6112 3639 2106 6072 0092 4074 2804 3379
Find the original message.
Problem 2.30. Suppose that we want to calculate 67896567 mod 1245 using a TI-83 or -84
calculator.
(a) Give the command on the calculator that will reduce a previous answer mod 1245.
(b) Explain how to do the calculation using repeated squaring.
(c) How many squaring operations and multiplication operations are needed to compute
the result?
(d) Do the computation, and give the result.
DISCRETE MATH II PROBLEMS
5
Problem 2.31. Prove that for all k ∈ Z>0 , a, b ∈ Z, (a|b) → ak |bk .
Problem 2.32. Suppose that a, b, c are nonzero integers such that a|b, b|c, and c|a . Prove
that a = ±c.
Problem 2.33. For each of the following integers, use the primality test to determine if the
number is prime. If not, do a prime factorization.
(a) 6137
(b) 811
(c) 65 537
(d) 65 531
Problem 2.34. Using the division algorithm, find the quotient and remainder when dividing
n by m :
(a) n = 678, m = 47
(b) n = −5783, m = 388
Problem 2.35. Find gcd (a, b) and lcm (a, b) :
(a) a = −23 · 57 · 78 and b = −2 · 58 · 75 .
(b) a = 1683, b = −969
Problem 2.36. Find integers x, y such that sx + ty = 1, or prove that no such integers
exist.
(a) s = 34, t = 13
(b) s = 34, t = 51
(c) s = −34, t = 89
Problem 2.37. Find ϕ (n) . Find the inverse of a mod ϕ (n).
(a) n = 35 172 , a = 53
(b) n = 77, a = 13
Problem 2.38. Find all examples of positive integers a ∈ {1, 2, ..., 14} such that a does not
have an inverse mod ϕ (77).
3. Relations
Problem 3.1. Let A = {x ∈ Z : 0 ≤ x ≤ 5} and B = {2, 4, 6}. Find each relation R from
A to B, as described below. (Each answer should be a list of ordered pairs.)
(a) R = “ is a factor of ”
(b) R = “ is a multiple of ”
(c) R = “ is relatively prime to ”
(d) R = “ ≥ ”
(e) R = “ is congruent mod 5 to ”
(f) R is defined by xRy iff x2 + y 2 = 25
(g) R is defined by xRy iff x2 + y 2 = 1
(h) R = “ = ”
Problem 3.2. Let P = {(x, y) : x = y 2 } ⊆ R2 .
(a) Graph this relation.
(b) Prove or disprove that P is a function.
6
DISCRETE MATH II PROBLEMS
(c) Prove or disprove that P is reflexive.
(d) Prove or disprove that P is symmetric.
(e) Prove or disprove that P is transitive.
Problem 3.3. Let P = {(x, y) : x < 2y} ⊂ (0, ∞) × (0, ∞)
(a) Graph this relation.
(b) Prove or disprove that P is a function.
(c) Prove or disprove that P is reflexive.
(d) Prove or disprove that P is symmetric.
(e) Prove or disprove that P is transitive.
Problem 3.4. Let P = (x, y) : x < 12 y ⊂ (0, ∞) × (0, ∞)
(a) Graph this relation.
(b) Prove or disprove that P is a function.
(c) Prove or disprove that P is reflexive.
(d) Prove or disprove that P is symmetric.
(e) Prove or disprove that P is transitive.
Problem 3.5. How many relations are there from the set A = {a, b, c, ..., z} to the set
T = {1, 2, 3, ..., 10}?
Problem 3.6. Consider all relations on the set {0, 1}.
(a) How many relations are there? List all of them.
(b) Which relations are reflexive?
(c) Which relations are symmetric?
(d) Which relations are transitive?
(e) Which relations are antisymmetric?
(f) Which relations are equivalence relations?
(g) Which relations are functions?
Problem 3.7. Let g : R → Z be defined by g (x) = x + 21
(a) Graph this relation.
(b) Prove or disprove that g is a function.
(c) Prove or disprove that g is reflexive.
(d) Prove or disprove that g is symmetric.
(e) Prove or disprove that g is transitive.
(f) Graph the inverse relation.
Problem 3.8. Let R be the relation “ ≤ ” on R and let S = {(x, y) : x2 + y 2 = 4}.
(a) Graph R .
(b) Graph R ∪ S .
(c) Graph R ∩ S .
(d) Graph R \ S .
(e) Graph S \ R .
(f) Graph Rc .
Problem 3.9. For each of the following relations given, find the indicated composition.
(a) For the functions f and g on R given by f (x) = x2 , g (x) = x + 1, find f ◦ g .
(b) For the functions f on R given by f (x) = x2 , find f ◦ f .
DISCRETE MATH II PROBLEMS
7
(c) R = {(x, y) ∈ R2 , x2 + y 2 = 1}, and S is the function on R given by y = 2x. Find
R ◦ S.
(d) R = {(x, y) ∈ R2 , x2 + y 2 = 1}, and S is the function on R given by y = 2x. Find
S ◦ R.
(e) R = {(x, y) ∈ R2 , x2 + y 2 = 1}; find R ◦ R.
(f) S is the function on R given by y = 2x. Find S ◦ S.
Problem 3.10. Give an example of a relation R from a set A to itself where R−1 ◦ R is not
the identity relation I on the set A defined by I = {(x, x) : x ∈ A}.
Problem 3.11. Prove or disprove that the following are equivalence relations.
(a) y 2 = x2 on R
(b) y = −1
on R
x
(c) (y − x) = (y − x)2 on R
(d) xln y > 0 on (0, ∞)
(e) x2 + y 2 ≤ 1 on R
(f) (x − y) ∈ {3n : n ∈ Z}, a relation on Z
Problem 3.12. Find the number of equivalence relations on the set {a, b, c}.
Problem 3.13. Find the number of equivalence relations on a set that contains 5 elements.
Problem 3.14. Prove or disprove that the following are posets.
(a) ([0, 2] , ≤)
(b) ([0, ∞] , <)
(c) (Z, D), where the relation D is defined by aDb iff a is a factor of b, with a, b ∈ Z.
(d) (Z, congruence modulo 5); that is, a is related to b iff a ≡ b mod 5, with a, b ∈ Z.
(e) (S, ⊆), where S is the set {{a, b} , {a} , {c} , {a, b, c} , {d}}, where a, b, c, d are distinct.
(f) ({1, 2, 3, 4} , R), where R = {(1, 4) , (4, 3) , (4, 4) , (3, 3) , (1, 3) , (2, 2) , (1, 1) , (1, 2)} .
(g) ({1, 2, 3, 4} , S), where S = {(1, 4) , (4, 3) , (4, 4) , (3, 3) , (1, 3) , (2, 2) , (1, 1) , (1, 2) , (3, 4)} .
Problem 3.15. In the following examples of partially ordered sets, find all minimal elements,
maximal elements, least elements, and greatest elements, if they exist.
(a) (S, ⊆), where S is the set {{a, b} , {a} , {c} , {a, b, c, d} , {d} , {a, b, c} , {a, b, d}}, where
a, b, c, d are distinct.
(b) ({1, 2, 3, 4} , R), where R = {(1, 3) , (4, 4) , (3, 3) , (4, 3) , (2, 2) , (1, 1) , (1, 2)} .
(c) ({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} , D), where aDb iff a|b.
(d) (P ({1, 2, 3}) , ⊆)
Problem 3.16. Draw the directed graph corresponding to each poset given below. Recall that
each element of the set is a vertex of the graph, and an arrow is draw from a to b (elements
of the set) if and only if a b and a 6= b.
(a) (S, ⊆), where S is the set {{a, b} , {a} , {c} , {a, b, c, d} , {d} , {a, b, c} , {a, b, d}}, where
a, b, c, d are distinct.
(b) ({1, 2, 3, 4} , R), where R = {(1, 3) , (4, 4) , (3, 3) , (4, 3) , (2, 2) , (1, 1) , (1, 2)} .
(c) ({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} , D), where aDb iff a|b.
(d) (P ({1, 2, 3}) , ⊆)
Problem 3.17. Prove that if (S, ) is a poset, and if x ∈ S is a least element, then it is
also the only minimal element of S.
8
DISCRETE MATH II PROBLEMS
Problem 3.18. Prove or disprove: if (S, ) is a poset, and if y ∈ S is the only minimal
element of S, then y is a least element of S.
Problem 3.19. Prove that the greatest element of a partially ordered set is unique.
Problem 3.20. How many relations are there from the set X = {1, 2, 3, 4} to the set Y =
{1, 2, 3, ..., 10}?
Problem 3.21. How many functions are there from the set X = {1, 2, 3, 4} to the set
Y = {1, 2, 3, ..., 10}?
Problem 3.22. How many equivalence relations are there from the set X = {1, 2, 3, 4} to
itself ?
4. Combinatorics
Problem 4.1. How many integers are there from 1 to 10000 that are divisible by 17?
Problem 4.2. How many integers are there from 1 to 10000 that are divisible by 17 and are
not divisible by 3?
Problem 4.3. How many integers are there from 1 to 10000 that are divisible by 17 or are
divisible by 3, but not both?
Problem 4.4. How many 5 digit numbers are there that do not have a 3 or 7 as one of the
digits?
Problem 4.5. How many license plates could be of the form (letter)(letter)(number) (number)(letter)(letter), where the letters are not allowed to be I or O?
Problem 4.6. In how many different ways can two cards be chosen so that they are a pair
(of the same rank)?
Problem 4.7. In how many different ways can a king and a jack be chosen from a deck of
cards?
Problem 4.8. In how many different ways can a pair (two of the same rank) be chosen from
a standard deck?
Problem 4.9. In how many different ways can a pair (two of the same rank) and three other
cards be chosen from a standard deck?
Problem 4.10. What is the probability of getting at least a pair when getting five cards from
a standard deck of cards?
Problem 4.11. In how many different ways can one draw a full house (a pair and a three
of a kind) when choosing five cards from a standard deck?
Problem 4.12. In how many different ways can two pairs be chosen when drawing five cards
from a standard deck of cards?
Problem 4.13. In how many different ways can a five-card flush (five cards from the same
suit) when choosing five cards from a standard deck?
Problem 4.14. In how many different ways can a straight (5 consecutive cards, not necessarily in the same suit) be chosen when getting five cards from a standard deck?
DISCRETE MATH II PROBLEMS
9
Problem 4.15. In how many ways can one draw five cards, all of which are number cards
less that 6, from a standard deck?
Problem 4.16. In how many ways can one draw three cards from a standard deck that are
all red face cards?
Problem 4.17. In how many different ways can a 6-sided die be rolled twice so that the sum
of the digits is less than or equal to five? (Note that rolling a 2 and then a 3 is counted as a
separate way from rolling a 3 and then a 2.)
Problem 4.18. In how many ways can a card be chosen from a standard deck so that it is
either a king or a red card?
Problem 4.19. Suppose that people eat between 1 and 10 pancakes at the same time. Prove
that if there are 21 people in a restaurant eating pancakes, then there are three people who
eat the same number of pancakes.
Problem 4.20. If A = {a, b, c}, B = {1, 2, 3, 4}, C = {p, q}, find the following cardinalities:
(a) |A ∪ B ∪ C|
(b) |A × B × C|
(c) |A ∩ B ∩ C|
(d) |B ∩ B|
Problem 4.21. On an 8 × 8 chessboard, in how many different positions can we place a
3 × 3 square (so that it fits the grid exactly)?
Problem 4.22. Suppose that two opposite corners from an 8 × 8 chessboard are removed.
Prove that it is impossible to tile the remaining part of the chessboard with 1 × 2 tiles.
Problem 4.23. Eighteen points are placed on different vertices on a regular 30-gon (a polygon with 30 equal sides and equal angles). Prove that there exist two of these points that are
diametrically opposite to each other.
Problem 4.24. Fifteen people are seated in a row of twenty-one chairs. Prove that there
exists a set of three consecutive chairs that are filled with people.
Problem 4.25. Suppose that twenty-three integers are chosen from the set {1, 2, ..., 40}.
Prove that at least one of the selected integers is a factor of one of the others.
Problem 4.26. If sixty different positive integers less than 109 are chosen, Prove that there
exist two of these that add to an odd number.
Problem 4.27. Twenty-five girls and twenty-five boys sit around a table.
(a) Prove that there exists a person at the table, both of whose neighbors are girls.
(b) Prove that if one girl leaves and a boy takes her place, it is possible that every person
has at most one girl neighbor.
Problem 4.28. Find the expansion of (2x + 3y)4
(a) By using the distributive property repeatedly.
(b) By using the Binomial Theorem.
4
Problem 4.29. Find the expansion of (x2 − 2a3 )
(a) By using the distributive property repeatedly.
10
DISCRETE MATH II PROBLEMS
(b) By using the Binomial Theorem.
10
Problem 4.30. Find the coefficient of x25 y 5 in (2x5 + 7y) .
11
Problem 4.31. Find the coefficient of x7 in 2x + x1 .
Problem 4.32. For k ∈ Z≥0 , find the coefficient of xk in 2x +
1 11
.
x
Problem 4.33. Prove the Pascal’s Triangle Identity, using the factorial formula for nk .
Problem 4.34. Prove that nk ≤ 2n − 1 for all integers n, k such that n ≥ 1 and 0 ≤ k ≤ n.
n
Problem 4.35. Prove that 2n
=
2
+ n2
2
2
(a) By using algebra.
(b) By using a combinatorial argument.
n
X
2 n
Problem 4.36. Find a simple formula for
k
, and prove it.
k
k=0
Problem 4.37. Find recursive formulas for the following sequences.
(a) (3, 9, 15, 21, 27, ...)
(b) (1, 2, 4, 7, 11, 16, ...)
(c) (2, 16, 256, 65536, ...)
(d) (1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...)
(e) (3, 2, 5, 7, 12, 19, ...)
(f) (3, 2, 1, 1, 0, 1, −1, 2, −3, 5, ...)
Problem 4.38. Find closed form formulas for each of the sequences above.
Problem 4.39. Which of the following recurrence relations are linear? Which of them are
linear and homogeneous? Which of them are linear and homogeneous and have constant
coefficients?
(a) An = 2An−1 + nAn−2 − 1
(b) An = 2An−1 + nAn−2
(c) An = 2An−1 − 5An−2
(d) An = 2An−1 An−2
(e) An = 2 (An−1 )2 − 5An−2
(f) An = An−2 + 1
(g) An = 2An−2
Problem 4.40. For each of the sequences above, assume that A0 = 2 and A1 = 1. Compute
A3 , A4 , A5 .
Problem 4.41. Construct a recursive formula and initial condition for the sequence (an ) so
that an = (2n)! .
p
Problem 4.42. Suppose that An = −7An−1 + 3A2n−2 + 6, and suppose that this sequence
has a limit. What are the possible limits for it? Construct the sequence numerically, and
find the limit that way, using different sets of initial conditions. What do you find?
DISCRETE MATH II PROBLEMS
11
Problem 4.43. Solve the following recurrence relations.
(a) xn = 3xn−1 , x1 = −2.
(b) am = (m + 1) am−1 ; a0 = 2 .
(c) cm = cm−1 + 7; c1 = 8.
(d) yp = 2yp−1 + yp−2 ; y0 = 1, y1 = 0.
(e) An = 3An−1 + 10An−2 ; A0 = 1, A1 = −1.
(f) gs = 6gs−1 − 9gs−2 ; g1 = 1, g2 = −4
(g) ht = ht−1 − 41 ht−2 ; h0 = 4, h1 = 4.
(h) mp = 2mp−1 + p; m0 = 3.
(i) mp = 2mp−1 + p2 ; m0 = 3.
(j) mp = 2mp−1 + 3p ; m0 = 3.
(k) Jn = 5Jn−2 − 4Jn−1 + n − 2; J0 = J1 = 1.
(l) Jn = 5Jn−2 − 4Jn−1 + n − 1; J0 = J1 = 1.
(m) Jn = 5Jn−2 − 4Jn−1 + 2n − 1; J0 = J1 = 1.
Problem 4.44. Find the general solution of each recurrence relation.
(a) Bn = 5Bn−1
(b) Cn = 5Cn−2
(c) Dn = 5Dn−2 + Dn−1
(d) En = 3En−1 − 2En−2
(e) Fn = 5Fn−1 + 3
(f) Gn = 5Gn−2 + 3
(g) Hm = 5Hm−2 + Hm−1 + 3
(h) Ip = 3Ip−1 − 2Ip−2 + 3
(i) Ja+1 = 5Ja + 3a + 1
(j) Kn+1 = 5Kn−1 + 3n + 1
(k) Ln = 5Ln−2 + Ln−1 + 3n + 1
(l) Mp = 3Mp−1 − 2Mp−2 + 3p + 2
(m) Nx = 3Nx−1 + 4Nx−2 + 2x − 2
(n) qm = 2qm−1 + m3m
Problem 4.45. How many positive integers less than 1000 are divisible by 13 or 11?
Problem 4.46. How many positive integers less than 500 are divisible by 11 or 7?
Problem 4.47. How many positive integers less than 1000 are not divisible by 5, 13, or 17?
Problem 4.48. How many positive integers less than 500 are not divisible by 5, 7, or 11?
Problem 4.49. A total of 250 students have taken Calculus 2, 136 students have taken
Discrete Math 1, and 75 students have taken both Calculus 2 and Discrete Math 1. What is
the total number of students who have taken Calculus 2 or Discrete Math 1 ?
Problem 4.50. There are 391 students who took Italian, 734 students took German, and
920 students in total took German or Italian. How many students took both German and
Italian?
Problem 4.51. A total of 316 students have taken Calc 3, Diffy Q , or Discrete 1. Of these,
92 students took Calc 3, 159 students took Discrete 1, and 152 took Diffy Q. Suppose that 29
of them took both Calc 3 and Diffy Q, 42 of them took both Diffy Q and Discrete 1, and 24
took both Calc 3 and Discrete 1. How many students took all three classes?
12
DISCRETE MATH II PROBLEMS
Problem 4.52. Write down the inclusion-exclusion formula for |A ∪ B ∪ C ∪ D|.
5. Boolean Algebra
Problem 5.1. Compute the complete table of values for each Boolean function.
(a) x ∧ y
(b) ¬ (a ∨ (b ∧ c))
(c) a ∨ ¬a ∧ b
Problem 5.2. Prove each Boolean identity (using a table of values).
(a) x ∨ 0 = x
(b) ¬ (a ∨ y) = ¬y ∧ ¬a
(c) x ∨ x = x
(d) x ∧ x = x
(e) x ∨ (x ∧ y) = x
(f) x ∧ (y ∨ x) = x
Problem 5.3. Simplify the following Boolean expressions, using only ∨, ∧, ¬ :
(a) ¬x → y
(b) x ⊕ (y ⊕ z)
(c) ¬ (¬x ∨ (x ∧ x ∧ y))
(d) x ↔ (x ∨ y)
(e) x ∧ y ∧ x ∨ x → (y ⊕ x)
(f) (¬ (x → y) ∨ (¬ (x ∧ y))) → x ∧ y
Problem 5.4. Put each logical expression into disjunctive normal form. A Boolean
expression is in disjunctive normal form if it is of the form
A1 ∧ A2 ∧ ... ∧ An ∨ B1 ∧ B2 ∧ ... ∧ Bn ∨ ...
where each Aj or Bj is a Boolean variable or a negation of that Boolean variable.
(a) x ∧ ¬ (x ∧ y ∧ y ∨ z)
(b) a ∧ (b ⊕ c) ∨ b
(c) (x → y) → (y → z)
(d) ¬ ((x ∧ ¬y) ∨ ¬z) → x
(e) (x → y) → z
(f) x → (y → z)
(g) (x ⊕ y) ⊕ z
Problem 5.5. Find the dual of each Boolean equation below.
(a) x ∧ y = ¬z
(b) x ∧ 1 = ¬z
(c) ¬ (x → y) = x ∧ ¬y
(d) (x ∧ y) ∨ z = 0
Problem 5.6. For each of the following Boolean functions, make the corresponding logic
gate diagram. Do not simplify first.
(a) a (x, y) = ¬ (x ∨ y)
(b) b (x, y, z) = ¬x ∨ y ∧ z ∨ x ∧ y
(c) F (a, b, c) = ¬ (x ∨ y ∨ z)
DISCRETE MATH II PROBLEMS
(d) G (x1 , x2 , x3 ) = x1 ∧ ¬ (x2 ∨ x3 )
(e) H (x1 , x2 , x3 ) = x1 ∧ ¬x2 ∨ ¬x3
13
© Copyright 2024 ExpyDoc
