ECS 20: Discrete Mathematics for Computer Science PS5.Problems UC Davis — Prof. October 19, 2021
Problem Set 5 – Due Wednesday, October 27, at 5pm
1. Let x be the 32-bit IEEE 754 floating point number closest to the real number x (assume some convention to deal with rounding). Exactly compute the 32-bit IEEE 754 product of ten and a tenth, 10 (0.1). Exactly how far off are you from the desired answer of 1? If you like, you may use a computer or online tool to assist you.
2. Show that each of the following languages are “regular” by writing them using nothing but con- catenation, union, and star, applied to finite sets. Recall that the “star” operator is defined by L∗ = i∈N Li.
(a) The language A of binary strings whose length is divisible by two or three
(b) The language B of all binary strings whose first two characters are the same as the last two
characters. Strings in this language must have two or more characters.
(c) The language C of all binary strings that do not contain two consecutive 1’s.
3. Recall our definition of a group G. Using just those three properties we specified, carefully prove that:
(a) The identity element is unique (any two identities are the same).
(b) The inverse of any element is unique (any two inverses of a are the same).
4. Figure out which of the following relations ∼ are equivalence relations. As always, fully explain your answers.
(a) x∼yifxandyarepeoplewhowerebornonthesameday. (b) x ∼ y if x and y are strings that contain a common character.
(c) x ∼ y if x and y are points in the plane that are equidistant to the origin. (d) L ∼ L′ if L and L′ are parallel lines in the plane.
5. Fora,b∈Rdefinea∼bifa−bisaninteger.
(a) Prove that ∼ is an equivalence relation.
(b) What is the equivalence class (block) containing 3? What is the equivalence class of 3.14? That is, clearly describe the sets [3] = {y : 3 ∼ y} and [3.14] = {y : 3.14 ∼ y}.
(c) If you wanted to select for each equivalence class of ∼ a canonical representative, or name, what name would you use? For example, what would be the canonical name for [π]?