Discrete Mathematics Answers

2.

Find the transitive closures of these relations on {1, 2, 3, 4}.

a) {(1, 2), (2,1), (2,3), (3,4), (4,1)}

b) {(2, 1), (2,3), (3,1), (3,4), (4,1), (4, 3)}

c) {(1, 2), (1,3), (1,4), (2,3), (2,4), (3, 4)}

d) {(1, 1), (1,4), (2,1), (2,3), (3,1), (3, 2), (3,4), (4, 2)}

3.

Find the smallest relation containing the relation {(1, 2), (1, 4), (3, 3), (4, 1)} that is

a) reflexive and transitive.

b) symmetric and transitive.

c) reflexive, symmetric, and transitive.

4.

Which of these relations on {0, 1, 2, 3} are equivalence relations? Determine the properties of an equivalence relation that the others lack.

a) {(0, 0), (1, 1), (2, 2), (3, 3)}

b) {(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}

c) {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}

d) {(0, 0), (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2),(3, 3)}

e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0),(2, 2), (3, 3)}

Construct the Combinatorial Circuit of the given output.

1. (p∨q) 2. (p∧ ~q)
2. (p→~q)→(p∨q)

Consider the following list of numbers:

1 7 8 14 20 42 55 67 78 101 112 122 170 179 190

Apply binary algorithms in order to find the target which are number 42 and number 82. Show your step and calculate the total number of comparisons for each item.

Prove that the set G={0,1,2,3,4,5} is an abelian group with respect to the 

multiplication modulo 6.

3 + 5 = 8 is a proposition for p, find the corresponding ῀p.