Given S={0,1,2,3,4,5}, find the partition induced by the equivalence relation R where...

1. Given S={0,1,2,3,4,5}, find the partition induced by the equivalence relation R where R={(0,0),(0,4),(1,1),(1,5),(3,4),(0,3),(4,3),(3,0),(3,3),(2,2),(5,1),(5,5),(4,0),(4,4)}. Explain.

2. Let the relation R = {(0,0), (0,3), (1,0), (1,2), (2,0), (3,2)} Find R’ the transitive closure of R. Show all steps.

3. Using the predicate symbols shown and appropriate quantifiers, write each English language statement in predicate logic. (The domain is the whole world.)

C(x) is “x is a cow.”

B(x) is “x is brown.”

H(x) is “x is a Holstein cow.”

3.1. All cows are brown.

3.2. Not all cows are Holstein cows.

3.3. All Holstein cows are brown.

3.4. Some cows are not brown.

4 Which inference rule is used to show that from the hypotheses “Every kid in school learns arithmetic” and “Antonio is a kid in school”, we can conclude that Antonio learns arithmetic? Check only one

1. Modus Tollens

2. Modus Ponens

3. Universal Instantiation

4. Hypothetical Syllogism

5. Do a proof by mathematical induction using the 4 steps below to show that the following statement is true for every positive integer n: 2+8+24+64+...+n2 n = (n−1)2 n+1 +2

5.1. Prove the base step

5.2. State the inductive hypothesis: Assume that ...

5.3. State what you have to show:

5.4. Proof proper (justify each step):

6. Let S={0,2,4,6,8} and T={1,3,5,7}. Determine whether each of the following sets of ordered pairs is a function with domain S and co-domain T.

6.1. {(2,1),(4,5),(6,3)} True/False

6.2. {(0,2),(2,4),(4,6),(6,0),(8,2)} True/False

6.3. {(2,3),(4,7),(0,1),(7,3),(8,7)} True/False

6.4. {(6,3),(2,1),(0,3),(8,7),(4,5)} True/False

6.5. {(6,1),(0,3),(4,1),(0,7),(2,5),(8,5)} True/False

7. Let A ={1,2,3,4,5} and B={x,y,z} How many relations are there betwen the set A and B? (Do not give just a number but explain how you would compute it)

8. A bouquet of 5 roses is made from 7 pink roses and 8 white roses: Show all work, exact numbers will not be accepted.

8.1. Find the number of bouquets of 5 roses.

8.2. Find the number of bouquets of 5 roses in which three are pink and two are white.

8.3. Find the number of bouquets of 5 roses composed of all pink or all white roses.

8.4. Find the number of bouquets of 5 roses with two or more white roses.

9. Using the predicate symbols shown and appropriate quantifiers, write the following English language statement in predicate logic. (The domain is the whole world.)

D(x) is “x is a cat”

S(x) is “x is shy”

T(x) is “x is happy”

If a dog is unhappy, then it is shy.

10. Which of the following is the correct negation for “Nobody is indispensable.”

1. Everyone is dispensable.

2. Everyone is indispensable.

3. Someone is indispensable.

11. For each of the following characteristics, determine whether the graph exists or why such a graph does not exist:

11.1. three nodes of degree 0, 1, and 3, respectively

11.2. simple graph with seven nodes, each of degree 3

11.3. four nodes, two of degree 2 and two of degree 3

11.4. complete graph with four nodes each of degree 2

12. Draw the minimum-weight spanning tree (or give a list of edges1 ) for the graph (see attached file) using Kruskal’s algorithm (An edge is denoted by a pair of vertices.)