CSE 321 final exam study guide: Spring 1998

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. Use the Euclidean algorithm to find gcd(123,277).

4. Show that if a,b,c and d are integers such that a|b and b|d, then ab|cd.

5. 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).

6. Give a careful proof by induction that any connected, undirected graph with n vertices and e edges satisfies e>= n-1. Be careful that your proof includes all connected graphs.

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. 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.

11. 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. (See definition of Hamiltonian circuit on page 478 of Rosen.)

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

    • Contingency
    • Contrapositive
    • Converse

13. 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.

14. 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.

15. 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?

16. 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.

17. 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.

18. 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.

19. 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?

20. 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.

21. 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?
22. • 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?

23. 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?

24. 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.)
25. 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.
26. 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.)