CSE 321 final exam study guide: Spring 2001

1. Show that the proposition p-> ((q-> (r-> s)) -> t) is a contingency WITHOUT constructing its full truth table.

2. Using the universe of integers for all quantifiers express the following English sentences in predicate logic using the predicates, P, E, and L where P(x) means `x is prime', E(x) means `x is even', and L(x,y) means `x < y'.

   • No prime greater than 2 is even.
   • For every number, there is a larger prime number.
   • Translate the following predicate logic expression into English where the predicates are the same as above:
   • FORALL x [( E(x) AND P(x)) -> L(x,100)].

3. In an undirected graph G, we define dist(v,w) to be the length of the shortest path from v to w. Show that for vertices x, y, z, we have dist(x,z)<= dist(x,y) + dist(y,z).

4. Let G=(V,E) be a directed graph. Define a relation R on E by (e_1,e_2) is an element of R iff e_1 and e_2 lie on a common simple circuit. (Recall that a simple circuit is a path that starts and ends at the same vertex, and does not repeat any edges).

   • Is R necessarily reflexive? Prove or disprove.
   • Is R necessarily symmetric? Prove or disprove.
   • Is R necessarily transitive? Prove or disprove.

5. Let R be a relation on a set A. Is the transitive closure of R always equal to the transitive closure of R^2 ? Prove or disprove.

6. Prove that in the graph below, there are exactly 2^n paths of length 2n between vertex A and vertex B for n>= 1.

        *   *   *   *
       / \ / \ / \ / \ /   \
    A *   *   *   *   * ... * B
       \ / \ / \ / \ / \   /
        *   *   *   *
   
         (n diamond shapes in a row)
   

7. The formula ~(p -> ~q) -> (r -> (~s -> t)) is false for exactly one assignment to p, q, r, s and t. Find this assignment WITHOUT constructing a truth table.

8. Determine the number of strings over {a,b,c} of length 100 that have exactly 98 a's.

9. Suppose that you are working on a True-False test with 10 questions. Let p_i be the probability that you get answer i correct. Assume that the probabilities are independent.

   • What is the probability of getting all of the answers wrong (expressed as a formula involving p_1, p_2, ... , p_10).
   • If p_i = 1- 2^{-i}, what is your expected number of correct answers.

10. Give an example of a relation which is not reflexive, not symmetric, not anti-symmetric, and not transitive. (You are to give one relation that lacks all of these properties, not separate relations for each property.) Justify your answer.

11. Give three different equivalence relations on the set {a,b,c,d}.

12. Let G be a directed graph with n vertices. Show that if G has a path of length greater than n, then G has a cycle.

13. Give a pair of non-isomorphic undirected graphs each with six vertices where every vertex has degree exactly two.

14. Let G=(V,E) be an undirected graph. The complement of G, G' is defined as the graph G'=(V,E') where E'={(v,w) | v is in V, w is in V, v!= w, (v,w) is not in E}. Give an example of a graph G such that both G and G' contain Hamiltonian circuits.

15. Let G=(V,E) be a graph with |V| >= 5. Prove that if G is 2-colorable (bipartite), then G' (its complement) is not 2-colorable.

16. The following terms are used in the propositional calculus. Give a one sentence definition for each of the terms.

    • Contingency
    • Contrapositive
    • Converse

17. Give logical expressions for the following statements. Use quantifiers, connectives, and the predicates P(x) and H(x) which mean ``x passed the class'' and ``x turned in all of the homework''.

    • Every student that passed the class turned in all of the homework.
    • There was a student that passed the class, but did not turn in all of the homework.

18. Consider the English alphabet, which consists of 5 vowels and 21 consonants.

    • How many strings of length 10 consist of 5 vowels followed by 5 consonants?
    • How many strings of length 10 consist of 5 distinct vowels followed by 5 distinct consonants. (In other words, the string has no repeated characters.)
    You may express your answers as products of integers.

19. Suppose that propositions p_1, p_2, ... , p_{n+1} are independently assigned random truth values, where the probability that p_i is true is 1/2.

    • What is the probability that the compound proposition p_1 AND p_2 AND ... AND p_n is true?
    • What is the probability that the compound proposition (p_1 AND p_2 AND ... AND p_n) -> p_{n+1} is true?

20. Let A={x, y, z}, B={1, 2, 3 ,4}, and C={a, b, c}. Let R be the following relation from A to B: R={(x,1), (x,2), (y,2), (y,3), (z,3)}, and S be the following relation from B to C: S={(1,a), (2,a), (2,b), (3, b), (4,b), (4,c)}. Compute the composition of R and S.

21. Suppose R_1 and R_2 are transitive relations on a set A. Is the relation R_1 UNION R_2 necessarily a transitive relation? Justify your answer.

22. Suppose R is the relation on the integers where xRy if and only if x = y+1. Describe the relation that is the transitive closure of R.

23. Let the relation L be defined on the integers by x L y if |x| < |y| or (|x| = |y| and x <= y).

    • List the elements of {-4, -3, -2, -1, 0, 1, 2, 3, 4} under the L ordering.
    • Argue that this ordering relation is total.

24. For which values of n does K_n contain an Eulerian circuit. (K_n denotes the complete graph on n vertices, K_n is undirected.) Justify your answer.

25. Let G=(V,E) be the undirected graph that has as its vertices the set of integers, and edges: E = {(x,x+3)| x is an integer}. Describe the connected components of G.

26. How many edges do the following undirected graphs contain.

    • K_n, the complete graph on n vertices.
    • K_{n,m}, the complete bipartite graph between n vertices and m vertices.
    • Q_n, the n dimensional hypercube. (Q_n has 2^n vertices.)

27. Translate the following English sentences into predicate logic where the universe is the set of people and the allowable predicates are: S(x) : x is a student F(x,y) : x and y are friends O(x,y) : x is older than y

    • Every student has a friend who is also a student.
    • There is someone who is older than all of his/her friends.

    • Write a predicate logic statement equivalent to the negation of each of the statements above that DOES NOT USE negation anywhere except immediately in front of the predicate symbols S, F, and O.

28. Suppose that n >= 3 and p_1,..., p_n are propositions that are true or false independently with probability exactly 1/2. Justify your answers.

    • What is the probability that (p_1 v p_2)-> p_3 is true?
    • What is the probability that (p_1 v ... v p_{n-1}) -> p_n is true?
    • What is the expected number of propositions p_i that are true?

29. In each of the following questions a relation R is defined. Assume that each R is defined over some natural set A. For each of the following properties, circle ALL those properties that ALWAYS apply and X out those properties that do NOT apply at least some of the time.

            [R] Reflexive
            [S] Symmetric
            [A] Antisymmetric
    	[T] Transitive
    

    You do not need to justify your answers.
    • xRy iff there is a path of length at least 0 from vertex x to vertex y in undirected graph G.
    • xRy iff there is a path of length at least 0 from vertex x to vertex y in directed graph G.
    • The relation R defined on undirected graphs where (G_1,G_2) is in R iff G_1 is isomorphic to G_2.
    • The relation R defined on the set of non-negative real numbers where xRy if and only if x<= y.
    • The relation R defined on the natural numbers where xRy iff x = y (mod 51).
    • The relation R defined on the natural numbers where xRy iff x = (y+1) ( mod 51).
    • The relation R defined on the set of people where xRy iff x is a grandparent of y.
    • xRy iff x=y.
    • xRy iff x is a subset of y.
    • xRy iff positive integer x divides positive integer y.

30. Here is a recursive definition of a "forest", a kind of undirected graph.

    • A graph with one or more nodes and no edges is a forest.
    • If G=(V,E) is a forest then for any nodes x and y of G that are not connected by a path in G the graph H consisting of G plus the edge {x,y} is also a forest.
    • (A graph is a forest only if it can be constructed using the above two rules.)
    Prove by induction that every forest with v vertices and e edges has exactly v-e connected components.

31. Suppose that R is a relation on a set A. Prove or disprove: If R^2 is reflexive then R must be reflexive.

32. Let R be the relation { (3,2), (3,4), (1,3), (2,1)} defined on the set {1,2,3,4,5}.
    • Draw the graph of R.
    • Draw the graph of the transitive closure of R.
    • Draw the graph of the reflexive-transitive closure of R.

33. Let n be a positive integer. A perfect matching on a set of 2n vertices is an undirected graph with n edges, such that each vertex has degree exactly 1. For example, there is one perfect matching on any set of two vertices (with edge set {{1,2}} if the vertices are {1,2}), and three distinct perfect matchings on four vertices (with edge sets {{1,2},{3,4}}, {{1,3},{2,4}}, and {{1,4},{2,3}} if the vertices are {1,2,3,4}). Prove by induction that the number of perfect matchings on 2n vertices is the product of the odd numbers less than 2n (so for n=2 it is 1x3).

34. As part of its effort to make U.S. paper money harder to counterfeit, the U.S. Treasury has decided to redesign the 1, 5, 10, 20, and 50 dollar bills. However, people have grown tired of seeing boring presidents on the bills so the Treasury Department is looking for more appealing candidates to appear on these 5 different bills. They have narrowed the field of available candidates to seven actors {a_1,...,a_7}, eight basketball players {b_1,...,b_8}, six cartoon characters {c_1,...,c_6}, and five disc jockeys {d_1,...,d_5}. (These four sets are pairwise disjoint, so there are 26 candidates in all.) Please JUSTIFY your answers for each of the following questions about the possible choices the Treasury Department might make. (Answers in the form of arithmetic expressions involving only +,*,-,/ and !, are acceptable for full credit.)

    • In how many ways can the Treasury Department decide which five candidates appear on the bills, without worrying about which bill they will appear on? (An example choice is {a_3, a_6, c_3, c_8, d_4}.)
    • In how many ways can the Treasury department make the same choice as in part (a) if they are required to choose at least one candidate from each of the 4 categories?
    • If the Treasury chooses the candidates for the five bills randomly, so that each sequence of five distinct candidates has equal probability, what is the probability of the assignment ``c_2 on $1, d_4 on $5, b_5 on $10, c_6 on $20, and a_1 on $50''?
    • If the Treasury chooses the candidates randomly as in part (c), what is the probability that cartoon characters appear on the $5 and $10 bills but not on the $50 bill?

35. • How many different undirected graphs are there on vertices {1,2,3}? Explain your answer.
    • How many of these are connected?
    • How many have exactly two connected components?
    • How many have Euler tours?
    • How many {\em non-isomorphic} undirected graphs are there on 3 vertices? (That is, if G and G' are isomorphic then we only count one of them.) Draw one of each.

36. To qualify for championships in certain games or sports there are sometimes "round-robin tournaments" in which each team plays a exactly one game against each other team. Suppose that n>= 2 teams played a round-robin tournament and assume that there were no ties (i.e. each game had a winner.)

    • If we define relation R on the set of teams by xRy if and only if x won its game against y which of the following properties does R always have: Reflexive, Irreflexive, Symmetric, Antisymmetric, Transitive? (EXPLAIN why or why not for each of the 6 cases.)
    • Consider the directed graph G_R representing relation R from part (a). What is the sum of the in-degrees of all the vertices in G_R? What is the sum of the out-degrees? Explain your answers.
    • Prove that there is a team that won at least [(n-1)/2] games where [x] means the smallest integer >= x.

37. In stud poker (as opposed to draw poker), 4 of the 5 cards in the poker hand are dealt 'face up' so that everyone can see them and one card is 'face down' so that nobody can see it. Suppose that we start with a perfectly shuffled deck so that the cards are equally like to be in any order. EXPLAIN your answers to each of the following questions:

    • If only one hand is dealt, what is the probability that this is a 'full house' (recall that's 3 cards of one rank and 2 of another)?
    • What is the conditional probability of that hand being a full house given that the four `face up' cards are 2 pairs (i.e. 2 cards of each of two ranks)?
    • What is the conditional probability of that hand being a full house given that the four `face up' cards contain 3 of one rank and 1 of another?
    • If 4 players are dealt poker hands from this perfectly shuffled deck what is the expected number of players who have full houses?

38. In the land of Garbanzo, the unit of currency is the bean. They only have two coins, one worth 2 beans and the other worth 5 beans.

    • Give a recursive definition of the set of positive integers S such that x is in S if and only if one can make up an amount worth x beans using at most one 5-bean coin and any number of 2-bean coins.
    • Prove by strong induction that every integer >= 4 is in S. (You do NOT need a recursive proof here.)

39. Let R be the relation { (1,2), (3,4), (1,3), (2,1) } defined on the set {1,2,3,4,5}.

    • Draw the graph of R.
    • Draw the graph of the transitive closure of R.
    • Draw the graph of the reflexive-transitive closure of R.

40. If R is a relation on a set A then we say that R is {\em total} if and only if FORALL x in A THERE EXISTS y in A, xRy. Prove that if R is symmetric and total then its transitive closure is also reflexive, i.e. R^+=R^*.

41. For each n>= 0 define T_n>, the 'complete 3-ary tree of height n' as follows:
    • T_0 is an undirected graph consisting of a single vertex called the root of T_0.
    • For n>= 0, T_{n+1} is an undirected graph consisting of a new vertex of degree 3 joined to the roots of 3 disjoint copies of T_n. The new vertex is called the root of T_{n+1}.
    Prove by induction that for each n>= 0, T_n has exactly (3^{n+1}-1)/2 vertices.
42. Suppose that you have a rectangular cake which you need to cut into n rectangles of equal size by successively cutting the cake into chunks. Show that no matter how you do it you need to make exactly n-1 cuts in the cake (where a single cut is a straight line cut of one chunk, i.e. you are NOT allowed to line up several chunks and cut them at once.) (Hint: induction may help.)