Oregon State University, CorvallisCS 225CS225 Final Exam Review. Covers the materials from week 2 to week 10. Much in the spirit of the homework and Quiz questions. This material summarizes some important contents and gives some example questions from homework assignments and quizzes as review exercise.

Document Content and Description Below

CS225 Final Exam Review The final exam will cover the materials from week 2 to week 10. The exam questions will be very much in the spirit of the homework and quiz questions. This material summarize... s some important contents and gives some example questions from homework assignments and quizzes as review exercise. The exam will cover only the topics and the problems listed below –Good Luck!! Unit 1: Non-Inductive Proof Techniques (10%)  Direct Proof, Contrapositive & Contradiction: Students should master the technique of direct proof, proof by contraposition and proof by contradiction. Example questions from homework assignments - week 2 and 3 Demo and actual quiz - 2, 3 Week 2- assignment 2 part I Sec 3.1: 18. Let D be the set of all students at your school, and let M(s) be “s is a math major,” let C(s) be “s is a computer science student,” and let E(s) be “s is an engineering student.” Express each of the following statements using quantifiers, variables, and the predicates M(s),C(s), and E(s). a. There is an engineering student who is a math major. b. Every computer science student is an engineering student. c. No computer science students are engineering students. d. Some computer science students are also math majors. e. Some computer science students are engineering students and some are not. Sec 3.2: 2. Which of the following is a negation for “All dogs are loyal”? More than one answer may be correct. a. All dogs are disloyal. b. No dogs are loyal. c. Some dogs are disloyal. d. Some dogs are loyal. e. There is a disloyal animal that is not a dog. f. There is a dog that is disloyal. g. No animals that are not dogs are loyal. h. Some animals that are not dogs are loyal. Sec 3.2: 4. Write an informal negation for each of the following statements. Be careful to avoid negations that are ambiguous. a. All dogs are friendly. b. All people are happy. c. Some suspicions were substantiated. d. Some estimates are accurate. Week 2- assignment 2 part II Prove the statements in 24–34. In each case use only the definitions of the terms and the Assumptions listed on page 146, not any previously established properties of odd and even integers. Follow the directions given in this section for writing proofs of universal statements. Sec 4.1: 32. If a is any odd integer and b is any even integer, then, 2a + 3b is even. Sec 4.1: 61. Suppose that integers m and n are perfect squares. Then m + n + 2√mn is also a perfect square. Why? Determine which of the statements in 15–20 are true and which are false. Prove each true statement directly from the definitions, and give a counterexample for each false statement. Sec 4.2: 20. Given any two rational numbers r and s with r < s, there is another rational number between r and s. (Hint: Use the results of exercises 18 and 19.) H 18. If r and s are any two rational numbers, then r+s 2 is rational. H 19. For all real numbers a and b, if a < b then a < a+b/2 < b. (You may use the properties of inequalities in T17–T27 of Appendix A.)Derive the statements in 24–26 as corollaries of Theorems 4.2.1, 4.2.2, and the results of exercises 12, 13, 14, 15, and 17. Theorem 4.2.1 Every integer is a rational number. Theorem 4.2.2 The sum of any two rational numbers is rational. Sec 4.2: 25. If r is any rational number, then 3r 2 − 2r + 4 is rational. Prove each of the statements in 23–29 in two ways: (a) by contraposition and (b) by contradiction. Sec 4.6: 28. For all integers m and n, if mn is even then m is even or n is even. Week 3- assignment 3 part I Prove each statement in 10–17 by contradiction. Sec 4.6: 12. If a and b are rational numbers, b = 0, and r is an irrational number, then a + br is irrational. Sec 4.6: H ✶16. For all odd integers a, b, and c, if z is a solution of ax2 + bx + c = 0 then z is irrational. (In the proof, use the properties of even and odd integers that are listed in Example 4.2.3.) Week 3- assignment 3 part II Sec 6.1: 3. Let sets R, S, and T be defined as follows: R = {x ∈ Z | x is divisible by 2} S = {y ∈ Z| y is divisible by 3} T = {z ∈ Z| z is divisible by 6} a. Is R ⊆ T ? Explain. b. Is T ⊆ R? Explain. c. Is T ⊆ S? Explain. Sec 6.1: 7. Let A = {x ∈ Z| x = 6a + 4 for some integer a}, B = {y ∈ Z | y = 18b − 2 for some integer b}, and C = {z ∈ Z| z = 18c + 16 for some integer c}. Prove or disprove each of the following statements. a. A ⊆ B b. B ⊆ A c. B = C Sec 6.1: 13. Indicate which of the following relationships are true and which are false: a. Z+ ⊆ Q b. R− ⊆ Q c. Q ⊆ Z d. Z− ∪ Z+ = Z e. Z− ∩ Z+ = ∅ f. Q ∩ R = Q g. Q ∪ Z = Q h. Z+ ∩ R = Z+ i. Z ∪ Q = Z Sec 6.1: 18. a. Is the number 0 in ∅? Why? b. Is ∅ = {∅}? Why? c. Is ∅ ∈ {∅}? Why? d. Is ∅ ∈ ∅? Why? Sec 6.1: 33. a. FindP(∅). b. FindP(P(∅)). c. FindP(P(P(∅))). Sec 6.1: 34. Let A1 = {1, 2, 3}, A2 = {u, v}, and A3 = {m, n}. Find each of the following sets: a. A1 × (A2 × A3) b. (A1 × A2) × A3 c. A1 × A2 × A3Demo Quiz 1 Question 1- 21x + 1 < 5x ­ is a proposition. T/F Question 2- 1 divides every integer . ­ The statement is not a proposition. T/F Question 3- "What time is it? " is a proposition. T/F Question 4- "Adam is a college student " ­ This statement is a proposition. T/F Question 5- Consider the propositions: p: Juan is a math major. q: Juan is a computer science major. Use symbolic connectives to represent the proposition “Juan is a math major but not a computer science major.” Question 6- Write each of these propositions in the form “p if and only if q” in English. a) For you to get an A in this course, it is necessary and sufficient that you learn how to solve discrete mathematics problems. b) If you read the newspaper every day, you will be informed, and conversely. c) It rains if it is a weekend day, and it is a weekend day if it rains. d) You can see the wizard only if the wizard is not in, and the wizard is not in only if you can see him. Question 7- State the converse, contrapositive, and inverse of each of these implications. 1) When I stay up late, it is necessary that I sleep until noon. 2) If it snows tonight, then I will stay at home. Question 8 - What is the negation of each of these propositions? i) To get tenure as a professor, it is sufficient to be world famous. ii) If I am lying, I am dying . iii) Tom’s smartphone has at least 32GB of memory. iv) If the home team does not win, then it is not raining. v) Being divisible by 2 is a necessary condition that a number is divisible by 10. Question 9­ Construct a truth table for the statement (p q) → ∧ (p → r) Question 10­ Determine whether [p ∧ (p → q)] → q is a tautology using the tables attached. Demo Quiz 2 Question 1- Let Z(x): "x is an integer", p(x) : " x is positive" , n(x) What will be the correct representation of "Not every integer is positive" ? ∀x[¬Z(x) → (x>0)] ∀x[Z(x) → (x ≤ 0)] ∀x[Z(x)→ ¬(x>0)] ¬ ∀x[Z(x) → (x>0)] Question 2- Let Z(x) : x is an integer . Choose the correct english translation of the following expression ­ ∀x[(Z(x) Λ (x>0)) → ¬(x<0)] Not every positive integer is negative All positive integers are positive and not negative. No positive integer is negativeAll positive integers are negative Question 3­ Let the following predicates be given. The domain is all living beings. B(x) = “x is one of my poultry” S(x) = “x is a duck” A(x) = “x is willing to waltz” M(x) = "x is an officer" Express each of the following English sentences in terms of B(x), S(x), A(x), quantifiers, and logical connectives. i. No ducks are willing to waltz. ii. All my poultry are ducks. iii. No officers ever declined to waltz. iv. Some poultry are ducks but not officers. Question 4­Show that ¬∀x(P(x) → Q(x)) and ∃x(P(x)∧¬Q(x)) are logically equivalent. Question 5­ Write the negation for each of the following statements. a. If a computer program has more than 100,000 lines, then it contains a bug. b. Some estimates are accurate. c. The number 1,357 is divisible by some integer between 1 and 37. Question 6­ Using direct method, prove that If m is an even integer and n is an odd integer then mn is an even integer. Question 7­ Use direct proof method to prove that n 2 + n + 1 is odd for all n ∈ N. Hint: use cases. Question 8­ Show that if n3 + 5 is even, then n is odd for all natural numbers. (Direction : You have to use proof by contraposition) Actual Quiz 1 Question 1­ Is the following a proposition? Adding 3 to both sides of x−3 = 37 gives x =42 . Y/N Question 2 ­ Is the following a proposition? 4n+1 ≥ 100 ? Y/N Question 3 ­ Is the following a proposition? Call me Abraham. Y/N Question 4­ Is the following a proposition? Human beings want to be good, but not too good, and not all the time. Y/N Question 5­ A conditional statement is logically equivalent to it's converse. T/F Question 6­ Give the converse, the contrapositive, and the inverse of the following statements­ 1) If the number is 64, then it is both even and a power of 4. 2) Having oxygen in the earth's atmosphere is a necessary condition for human life. (hint: convert it in if­else form first ) Question 7: Negate the following sentences. Be sure to justify your work : i) In order for it to rain it is sufficient that there be clouds. ii) For a function to be integrable, it is necessary that it is continuous. iii) it is neither raining nor sleeting.iv) I do not fail the course if I study hard and pass the final. v) If tomorrow is not Monday, then today is not Easter. Question 8­ Determine whether the following statements are true or false – 1) 1 + 1 = 3 if and only if 3 + 4 = 9. 2) 1 + 1 = 2 if 3 + 4 = 9. Question 9­ The following statements are not equivalent (You may need to apply a rule here.) "Alice is smart, or she is smart but honest.” and “Alice is smart.” T/F Question 10­ Let P, Q, and R be the propositions P: Grizzly bears have been seen in the area. Q : Hiking is safe on the trail. R: Berries are ripe along the trail. Translate the following English sentences into compound logical propositions. a) It is necessary that berries are ripe for the fact that grizzly bears have seen in the area. b) Hiking is safe if and only if berries are ripe along the trail or grizzly bears have not been seen in the area. e) Neither hiking on the trail is safe nor the berries are ripe along the trai. Question 11­ Decide whether or not the following pairs of statements are logically equivalent (using truth table method) . (P ­­> Q) ∨ R and ∼ ((P∧ ∼ Q) ∧ ∼ R) Question 12­ Simplify the following equation (use the tables attached herewith Tables.png ) ­ ∼(P ∨ ∼Q) ∨ (∼P ∧ ∼Q) Actual Quiz 2 Question 1­ Let the following predicates be given. The domain consists of everything. F(x) = x is a tool H(x) = x is in the correct place S(x) = x is in excellent condition Express each of the following English sentences in terms of F(x), H(x), S(x), quantifiers, and logical connectives. a) Something is not in the correct place. b) All tools are in the correct place and are in excellent condition. c) Nothing is in the correct place and is in excellent condition. d) One of your tools is not in the correct place, but it is in excellent condition Question 2­ Let B(x), S(x), and A(x) be the predicates B(x) : x is a Math major S(x) : x is a CS major A(x) : x is in Discrete Structure class Translate each of the following quantified logic expressions (provided in the file) into English consideringthe domain to consist of all people. ∀� ∀(�(�) ( → �(�) ∨ �(�) )) ¬∀� ∀(�(�)) ∃� ∃( (�(�) ∧ ¬�(�) ) ∨ ¬�(�)) ∃� ∃¬ (�(�) ∧ ¬�(�) ) Question 3­ Negate each of the following statements: 1) If the teacher is absent, then some students do not complete their homework. 2) Some suspicions were substantiated. 3) No student in your class has taken a course in logic programming. Question 4­ Prove or disprove that ∀x (P(x) → Q(x)) and ¬∃x ¬(¬Q(x) → ¬P(x)) are logically equivalent. ( Hint: Start with the double negation rule ¬( ¬∀x (P(x) → Q(x))) ) Question 5­ True or false: For the set of all negative integers, ∃x (x + 1 < ­ x) Question 6­ Use a direct proof to show that the sum of two rational numbers is rational. (Recall that a number is rational if and only if it can be expressed as the ratio of integers.) Question 7­ Suppose x, y ∈ Z. Prove by contraposition that If x2 (y+3) is even, then x is even or y is odd. Unit 2: Basic Discrete Structures (10%)  Set Theory: Subset Relation and Set Equality Students should master the techniques of proving subset relations and set equality. (Textbook - Example 6.1.2, 6.1.3, page 338 - 339. Example 6.1.2 Proving and Disproving Subset Relations Define sets A and B as follows: A = {m ∈ Z|m = 6r + 12 for some r ∈ Z} B = {n ∈ Z | n = 3s for some s ∈ Z}. a. Outline a proof that A ⊆ B. b. Prove that A ⊆ B. c. Disprove that B ⊆ A. Example 6.1.3 Set Equality Define sets A and B as follows: A = {m ∈ Z | m = 2a for some integer a} B = {n ∈ Z | n = 2b − 2 for some integer b} Is A = B? Example questions from Assignments and Quizzes: Homework Assignment: Set 6.1 – 3, 6, 7 Demo and actual quiz - 3  Properties of Sets: Students should master the techniques of proving set identities. (Textbook – Example 6.2.2, Theorem 6.2.2 (3)(a), Theorem 6.2.2(9)(a), Theorem 6.2.3) Example questions from Assignments and Quizzes: Exercise Set 6.2 4, 10, 13(Answer provided at the end of the book) Demo and actual quiz – 4Sec 6.2: Use an element argument to prove each statement in 7–19. Assume that all sets are subsets of a universal set U. Sec 6.2: 10) For all sets A, B, and C, (A − B) ∩ (C − B) = (A ∩ C) − B. Sec 6.2: 13. For all sets A, B, and C, if A ⊆ B then A ∩ C ⊆ B ∩ C. Demo quiz 3 Question 1: The sum of any rational number and any irrational number is irrational. Use proof by contradiction Question 2: Use proof by contradiction to show that for any selection of 3 distinct integers between 0 and 6 that at least one of those numbers will be odd Question 3: Let A = {1, {1}, {1, 2}}. Label each of the following as true of false. (a) 1 ∈ A. (b) 1 ⊆ A. (c) {1} ⊆ A. (d) {1} ∈ A. (e) {{1}} ⊆ A. (f) 2 ∈ A. (g) {2} ⊆ A. (h){1, 2} ∈ A. (i){1, 2} ⊆A. j){{1, 2}} ⊆ A. (k) ∅ ∈ A. (l) ∅ ⊆ A.Question 4: Suppose A = {1, 2}, B = {u, v} and C = {p, q}. Find the value of (A X C) X B. Question 5: The set A and B are defined as followed – A = {m ∈ Z | m = 2a for some integer a} B = {n ∈ Z | n = 2b - 2 for some integer b} Show that, A ⊆ B . Question 6: Let C = {n ∈ Z+ |2n + 1 is a prime integer}. List the smallest 3 elements of C. Question 7: Find the power set of {x, y, {x} } . Demo quiz 4 Question 1: Let A = {0, 2, 4, 6, 7}, B = { 1, 2, 3, 4, 6 }, and C = {0, 3, 6, 8, 9} And U be the set of all integers. What are , and ? Question 2: For any sets A and B, prove that (A ­ B) ­ C ⊆ A – C Question 3: Construct an algebraic proof that for all sets A and B, A − (A ∩ B) = A − B. Cite a property from Theorem 6.2.2 for every step of the proof Question 4: Write the first four terms of the following sequences ­ a. , for all integers i >=0 b. , for all integers j >=0 Question 5:Question 6 Actual quiz 3 Question 1: Use proof by contradiction to show that If a and b are rational numbers with b ≠ 0 and x is an irrational number, then a + bx is irrational. Question 2: Suppose a ∈ Z. If a2 is even, then a is even. Use proof by contradiction. Question 3: Let A ={x ∈ Z | x =18a − 2 for some integer a } and B ={y ∈ Z | y = 18b + 16 for some integer b}. Prove or disprove that A ⊆ B Question 4: True or false : { φ } = φ Question 5: True or false : Z­ ∩ Z+ = Z Question 6: True or false: {8} ∈ { 6, 8, 10} Question 7: True or false: {2, 4} ⊆ {x ∈ N | x is even} Question 8: Find the power set of A, where A = { x ∈ Z | 7 < x < 12 } . Question 9: Let, A={3n ∈ Z | ­1≤ n ≤ 3, n ∈ Z } , B={1, 2} and C = {{1,2}}. Find A X ( B X C) . Actual quiz 4 Question 1: Let A = {x | ­2 <x< 3}, B = {x | ­9≤ x ≤ 1} and C = {x | 2 ≤x< 6}, where x represents an integer number. Determine the sets , and . Question 2: Use an element argument to prove the statement: For all sets A and B, Ac ∩ Bc ⊆ (A ∪ B)c Question 3: For all sets A and B, simplify the given expression, (A − (A B)) (B ∩ ∩ ∩ − (A B)) Cite a property from Theorem 6.2.2 for every step of the proof.Question 4: What are the terms a0, a1, a2 and a3 of the sequence {an}, where an equals: 1) , For all n> =0 2) Question 5: Question 6: Compute the following summations. ( Instructions: Showing your work is necessary and you must make use of the formula provided in the attached document summation_formula.pdf . An intermediate form will be acceptable, so you don't need to calculate the final result.) a) [Show More]

Last updated: 1 year ago

Preview 1 out of 86 pages