Elementary Discrete Mathematics 2

1.

Let \(X=\{a,b,c,d,e,f\}\) and \(R\) be the relation on \(X\) defined by

Is \(R\) an equivalence relation? If so, draw a digraph and give the equivalence classes. If not, give an example showing why.

2.

Let \(X=\{1,2,3,4,5,6\}\) and let \(R\) be the relation on \(X\) defined by

Is \(R\) an equivalence relation? If so, draw a digraph and give the equivalence classes. If not, give an example showing why.

3.

Let \(X=\{a,b,c,d,e,f\}\) and \(S\) be the relation on \(X\) defined by

Is \(S\) an equivalence relation? If so, draw a digraph and give the equivalence classes. If not, give an example showing why.

4.

Let \(X=\{a,b,c,d,e,f\}\) and \(T\) be the relation on \(X\) defined by

Is \(T\) an equivalence relation? If so, draw a digraph and give the equivalence classes. If not, give an example showing why.

5.

Let \(X\) be any finite set and define the relation \(R\) on \(\mathscr{P}(X)\) by

If \(X = \{a,b,c\}\text{,}\) give the equivalence classes of the relation. Name each equivalence class with the correct notation, and list the elements of each.

6.

Define the floor \(\lfloor x \rfloor\) of a real number \(x\) to be “\(x\) rounded down”, in other words, the greatest integer less than or equal to \(x\text{:}\)

For instance, \(\lfloor -2 \rfloor = -2\text{,}\) \(\lfloor 1.74 \rfloor= 1 \text{,}\) and \(\lfloor \pi \rfloor = 3\text{.}\)

Define the relation \(S\) on the set \(\mathbb{R}\) of all real numbers:

For instance, \((\pi, 3.7) \in S\text{,}\) because the floor of both is \(3\text{.}\)

Describe the equivalence classes of \(\mathbb{R}\) under \(S\text{.}\) You will not be able to list them out, but you should be able to name a few and tell that there is one equivalence class for each...

7.

The notation \([n]\) is used as shorthand for the set \(\{1, 2, \ldots, n\}\text{.}\) Now we are using \([x]\) to refer to the set of all elements equivalent to \(x\) in a given equivalence relation. Briefly discuss the relationship between the two notations.

8.

Let \(\mathscr{S}^2\) be the space of all well-formed formulas consisting of at most two different letters. In other words, \(\mathscr{S}^2\) is the set consisting of all statements correctly formed from \(p\text{,}\) \(q\text{,}\) and some logical connectives. Examples include \(p\text{,}\) \(p \wedge \neg q\text{,}\) and \((\neg p \vee \neg q) \to (p \wedge q)\text{.}\) Define the relation \(\equiv\) on \(\mathscr{S}^2\) by saying \(\varphi \equiv \psi\) whenever \(\varphi \leftrightarrow \psi\) is a tautology. (In other words, \(\equiv\) on \(\mathscr{S}^2\) is the familiar logical equivalence.)

1. Prove there are \(16\) equivalence classes. (This requires a little bit of combinatorics.)

2. List the \(16\) equivalence classes. In other words, choose a representative for each of the classes of equivalent statement. For example, you'd choose between \(p \to q\) and \(\neg p \vee q\) as a representative for their equivalence class. If you chose \(p \to q\text{,}\) then \([p \to q]\) would be the set of all statements equivalent to \(p \to q\text{.}\)

16.

Let \(X\) be the set \(\{0,1,2,3,4,5,6,7,8,9,10\}\text{.}\) Write down the equivalence classes of this set under the relation \(\equiv\, (\text{mod } 3)\text{.}\) Name each and list the elements using the correct notation.

17.

Simplify \(2^{27}\, (\text{mod } 5)\) by hand in the following way. (This method is used to simplify large numbers of the form \(b^c \, (\text{mod } n)\text{,}\) which is used in certain encryption protocols.)

1. Express \(2^{27}\) as a product of factors of the form \(2^{2^n}\) by writing \(27\) as a sum of powers of 2 (basically, in binary).

2. Use the arithmetic properties of the modulus function to simplify \(2^{2^n}\, (\text{mod } 5)\) for each of the powers of 2 in the product you found in the preceding part. (Notice that each power of 2 is a square of the preceding part. So to simplify \(2^{16}\, (\text{mod } 5)\text{,}\) you could simplify simplify \(2^{8}\, (\text{mod } 5)\text{,}\) square that, and then take its remainder modulo 5.)

3. Multiply the remainders you found in the preceding part, taking one last remainder mod \(5\) if necessary.