Discrete Mathematics Answers

Let S be the set of ternary strings (i.e,. strings containing only the characters 0, 1,and 2), and let R be an equivalence relation on S. Suppose the collection of equivalence classes for R is P={Bi|i ∈ N}, where a typical representative of Bi is 222...2, a ternary string of length i consisting only of twos. Describe the equivalence relation R.

Let P1={B0, B1, B2} be a partition of Z, where B0={3n|n ∈ Z}, B1={3n+ 1|n ∈ Z}, and B2={3n+ 2|n ∈ Z}. Describe the equivalence relation R1 corresponding to P1.

(b) Let S={1,2,3}, and define the poset (P(S),⪯) by A⪯B if and only if A⊆B. Verify that this poset is a lattice. Is it a total ordering?
(c) Using your work in part (b), is every lattice necessarily a total ordering?

(a) Is every total ordering a lattice? Why or why not?

Define a function A: N x N -> N as follows: A(m, n) ={2n, if m= 0; 0, if m≥1 and n= 0; 2, if m≥1 and n= 1; A(m-1, A(m, n-1)), if m≥1 and n≥2

Show that A(1, n) = 2^n whenever n≥1.
Hint: Induct on n.

Define a function A: N x N -> N as follows: A(m, n) ={2n, if m= 0; 0, if m≥1 and n= 0; 2, if m≥1 and n= 1; A(m-1, A(m, n-1)), if m≥1 and n≥2

Show that A(m, 2) = 4 whenever m≥1.
Hint: Induct on m.

Define a function A: N x N -> N as follows: A(m, n) ={2n, if m= 0; 0, if m≥1 and n= 0; 2, if m≥1 and n= 1; A(m-1, A(m, n-1)), if m≥1 and n≥2
(a) Calculate the following:
(i)A(1,0)
(ii)A(0,1)
(iii)A(1,1)
(iv)A(2,2).

Let S be a finite non-empty set. How many relations on S are simultaneously an equivalence relation and a partial order? Justify your answer.

Let S be a finite set, with |S|=n. If the bit matrix MR representing R contains exactly r entries that are 0, how many entries of MRbar are 0?

Note: "MRbar" is supposed to be just like MR, which you should know has R as a subscript, but with a bar over R. Just in case that got confusing.

(a) If A={1,2,3,4}, calculate the number of reflexive relations on A.
(b) If B={1,2,3,4,5}, calculate the number of symmetric relations on B.