Midterm 1. Are the expressions p q and q p logically equivalent? Use a truth table to prove your answer. 2. Determine whether the following propositions are true or false: a. 5 is an odd number and 3 is a negative number. b. 5 is an odd number or 3 is a negative number. c. 8 is an odd number or 4 is not an odd number. d. 6 is an even number and 7 is odd or negative. e. It is not true that 7 is an odd number or 8 is an even number. 3. Consider the following statements in English. Write a logical expression with the same meaning. The domain of discourse is the set of all real numbers. a. There is a number whose cube is equal to 2. b. The square of every number is at least 0. c. The reciprocal of every number between 0 and 1 is greater than 1. d. Every number has an additive inverse. 4. Determine the truth value of each expression below if the domain is the set of all real numbers. Then repeat the exercise in which the domain are integers. a. x y (x + y = 0) b. x y (x + y = 0) c. x y z (z = 3/(xy)) d. x y z (z = x/y) e. zyx (x2+ y2 = z2) 5. Prove that if a and b are positive real numbers, then a+b ab . 6. Prove that there is no smallest integer. 7. Prove that if x and y are real numbers, then max(x,y)+min(x,y)=x+y. 8. Draw a Venn diagram illustrating the following sets: a. A B b. ( A C) B c. A (BC) 9. Use the ceiling and floor functions to give a mathematical expression for the following values: a. There are x children in the first grade at Lee Elementary school. Each child will be given five crayons to do an art project. Crayons come on boxes of 24. How many boxes need to be purchased for the art project? b. A baker is packaging cookies for sale in boxes of 8. He has y cookies to put into boxes. How many boxes can he sell? 10. Here are two relations on the set {a, b, c, d}: S = { (a, b), (a, c), (c, d), (c, a) } R = { (b, c), (c, b), (a, d), (d, b) } Write down the set of pairs in S R. 11. List the tuples in the relation {(a, b, c): a, b, and c are positive integers and 0 < a < b < c < 5}. 12. Write an algorithm in pseudocode with the following input and output: Input: a1, a2,... ,an, where a is a sequence of numbers and n1. Output: "True" if there are two consecutive numbers in the sequence that are the same. 2n 13. Prove that for any n 2 , 4 evenly divides 3 1 . Midterm 1. Are the expressions p q and q p logically equivalent? Use a truth table to prove your answer. No p q and q p (converse of p q) are not logically equivalent. The truth table below illustrates this as ca be seen from the last two columns. Had these two statements been equivalent, then those two columns would have been identical. p pq q p 1 1 1 1 1 0 0 1 0 1 1 0 0 2. q 0 1 1 Determine whether the following propositions are true or false: a. 5 is an odd number and 3 is a negative number. T AND F = T b. 5 is an odd number or 3 is a negative number. T OR F = T c. 8 is an odd number or 4 is not an odd number. F OR T = T d. 6 is an even number and 7 is odd or negative. T AND (T OR F) = T AND T = T e. It is not true that 7 is an odd number or 8 is an even number. ~(T OR T) = ~T = F 3. Consider the following statements in English. Write a logical expression with the same meaning. The domain of discourse is the set of all real numbers. a. There is a number whose cube is equal to 2. x x3 =2 b. The square of every number is at least 0. x x 20 c. The reciprocal of every number between 0 and 1 is greater than 1. x x 0,1 1/ x d. Every number has an additive inverse. x y x y=0 4. For Determine the truth value of each expression below if the domain is the set of all real numbers. Then repeat the exercise in which the domain are integers. = set of real numbers as domain a. x y (x + y = 0) TRUE. Existence of the Additive Inverse of every real number. b. x y (x + y = 0) = set of integers as domain For a. x y (x + y = 0) TRUE. Existence of the Additive Inverse of every real number and since b. x y (x + y = 0) FALSE. Uniqueness of the Additive Inverse of a real FALSE. Uniqueness of the Additive Inverse of a real number and since number. c. c. x y z (z = 3/(xy)) TRUE. The Closure Property for the Multiplication of real numbers. d. x y z (z = x/y) FALSE. Division by zero is not defined in the set of real numbers. e. zyx (x2+ y2 = z2) TRUE. Take x=0 and y=z, then x2+y2 = 02+z2 = z2. x y z (z = 3/(xy)) TRUE. The Closure Property for the Multiplication of integers. d. x y z (z = x/y) FALSE. Division by zero is not defined in the set of real numbers. e. zyx (x2+ y2 = z2) TRUE. Take x=0 and y=z, then x2+y2 = 02+z2 = z2. 5. Prove that if a and b are positive real numbers, then a+bab. Proof: This problem seems to be defective. Consider the following counterexample. If a=2 and b=3, then a+b=5 and ab=6 but 5 < 6 so a + b < ab 6. Prove that there is no smallest integer. Proof: The proof is by contradiction. Suppose that on the contrary there exists a smallest integer, call it S. Recall that 1 > 0. This is so since 1 is not 0, 1=1 2, and the square of any non-zero real number is positive. Let -1 be the additive inverse of the positive integer 1. Then -1 < 0 as 1 > 0: 1 + (-1) > 0 + (-1), then 0 > 0 + (-1), then 0 > -1. By the Closure Property of Addition for the set of integers, S + (-1) is an integer and S + (-1) = S -1 > S by the Definition of Subtraction and since S is the smallest integer by out initial assumption. Adding -S, the additive inverse of S (which is also an integer), to both sides of S-1 > S gives (-S) + (S-1) > (-S) + S (by API) ((-S)+S)-1 > (-S)+S (by Associativity for Addition) 0 -1 > 0 (by the Property of the Additive Inverse) -1 > 0 (by the Property of the Additive Identity) This is a contradiction since we have proven beforehand that -1 < 0. Hence, there does not exist a smallest integer. 7. Prove that if x and y are real numbers, then max(x,y)+min(x,y)=x+y. Proof: Let x and y be real numbers. Then by the Trichotomy Law exactly one of the following is true: Case 1: x = y Case 2: x > y Case 3: x < y. Suppose Case 1 is true, then max(x,y)=min(x,y)=x=y. Then, by substitution, max(x,y)+min(x,y) = x + min(x,y) = x + y, and we have proved our assertion for Case 1 Suppose Case 2 is true, then max(x,y)=x and min(x,y)=y. Then, by substitution, max(x,y)+min(x,y) = x + min(x,y) = x + y, and again we have proved our assertion for Case 2. Finally, suppose Case 3 is true, then max(x,y)=y and min(x,y)=x. Then, by substitution, max(x,y)+min(x,y) = y + x = x + y, because of the Commutative Law of Addition of Real Numbers. We have proved our assertion for Case 3. Since Case 1, 2 and 3, are all the possible Cases given any two real numbers x and y,, and in each instance we were able to show that max(x,y)+min(x,y) = x + y, it must be the case that if x and y are real numbers, then max(x,y)+min(x,y)=x+y. 8. Draw a Venn diagram illustrating the following sets: a. AB A b. B (AC)B B A C c. A(B-C) B A C 9. Use the ceiling and floor functions to give a mathematical expression for the following values: a. There are x children in the first grade at Lee Elementary school. Each child will be given five crayons to do an art project. Crayons come on boxes of 24. How many boxes need to be purchased for the art project? (x children) x (5 crayons/children) = 5x crayons needed (5x crayons) / (24 crayons/box) = 5x/24 = ceiling(5x/24) b. A baker is packaging cookies for sale in boxes of 8. He has y cookies to put into boxes. How many boxes can he sell? (y cookies)/(8 cookies/box) = y/8 = floor(y/8). 10. Here are two relations on the set {a, b, c, d}: S = { (a, b), (a, c), (c, d), (c, a) } R = { (b, c), (c, b), (a, d), (d, b) } Write down the set of pairs in SR. There seems to be a problem with the given. Maybe the definitions of S and R were reversed. Note that the range of R is {c,b,d} and d and b are not in the domain of S which is {a,c}. For the composition map SR to be defined, the co-domain of R must be a subset of the domain of S, but {c,b,d} is not a subset of {a,c}. If we reverse the definitions: R = { (a, b), (a, c), (c, d), (c, a) } S = { (b, c), (c, b), (a, d), (d, b) } then R(a) = b or c and R(c)=d or a. S(R(a))=S(b)=c or S(R(a)) = S(c)=b, then (a,c), (a,b) SR S(R(c))=S(d)=b or S(R(c))=S(a)=d, then (c,b), (c,d) SR So, SR = {(a,c), (a,b), (c,b), (c,d)}. 11. List the tuples in the relation {(a, b, c): a, b, and c are positive integers and 0 < a < b < c < 5}. The relation contains only three 3-tuples: {(1,2,3), (1,2,4), (2,3,4)} 12. Write a. b. an algorithm in pseudocode with the following input and output: Input: a1, a2,... ,an, where a is a sequence of numbers and n1. Output: "True" if there are two consecutive numbers in the sequence that are the same. start input ai's, i=1, ..., n for i from 1 by 1 to n-1 for j from i+1 by 1 to n if ai = aj then print \"True\" next j next i stop end 13. Prove that for any n2, 4 evenly divides 32n-1. Proof: Verification Stage: For n=2: 3n-1= 32-1 = 9 -1 =8 and 4 evenly divides 8. So this proposition holds true. Induction Stage: Hypothesis of Induction: Suppose for k 2, 4 evenly divides 3 k-1, then 4 evenly divides 3k+1-1. Proof of the Hypothesis of Induction: To prove the Hypothesis of Induction: Observe that 3k+1-1 = 3k+1+3 -3 -1 = 3(3k+1) - 4. But we know from the premise of the Hypothesis of Induction that 4 evenly divides 3k-1, so 4 evenly divides each term of the last expression above. Hence, 4 evenly divides 3k+1-1. Conclusion: For any n2, 4 evenly divides 3n-1. Midterm 1. Are the expressions p q and q p logically equivalent? Use a truth table to prove your answer. No p q and q p (converse of p q) are not logically equivalent. The truth table below illustrates this as ca be seen from the last two columns. Had these two statements been equivalent, then those two columns would have been identical. p pq q p 1 1 1 1 1 0 0 1 0 1 1 0 0 2. q 0 1 1 Determine whether the following propositions are true or false: a. 5 is an odd number and 3 is a negative number. T AND F = T b. 5 is an odd number or 3 is a negative number. T OR F = T c. 8 is an odd number or 4 is not an odd number. F OR T = T d. 6 is an even number and 7 is odd or negative. T AND (T OR F) = T AND T = T e. It is not true that 7 is an odd number or 8 is an even number. ~(T OR T) = ~T = F 3. Consider the following statements in English. Write a logical expression with the same meaning. The domain of discourse is the set of all real numbers. a. There is a number whose cube is equal to 2. x x3 =2 b. The square of every number is at least 0. x x 20 c. The reciprocal of every number between 0 and 1 is greater than 1. x x 0,1 1/ x d. Every number has an additive inverse. x y x y=0 4. For Determine the truth value of each expression below if the domain is the set of all real numbers. Then repeat the exercise in which the domain are integers. = set of real numbers as domain a. x y (x + y = 0) TRUE. Existence of the Additive Inverse of every real number. b. x y (x + y = 0) = set of integers as domain For a. x y (x + y = 0) TRUE. Existence of the Additive Inverse of every real number and since b. x y (x + y = 0) FALSE. Uniqueness of the Additive Inverse of a real FALSE. Uniqueness of the Additive Inverse of a real number and since number. c. c. x y z (z = 3/(xy)) TRUE. The Closure Property for the Multiplication of real numbers. d. x y z (z = x/y) FALSE. Division by zero is not defined in the set of real numbers. e. zyx (x2+ y2 = z2) TRUE. Take x=0 and y=z, then x2+y2 = 02+z2 = z2. x y z (z = 3/(xy)) TRUE. The Closure Property for the Multiplication of integers. d. x y z (z = x/y) FALSE. Division by zero is not defined in the set of real numbers. e. zyx (x2+ y2 = z2) TRUE. Take x=0 and y=z, then x2+y2 = 02+z2 = z2. 5. Prove that if a and b are positive real numbers, then a+bab. Proof: This problem seems to be defective. Consider the following counterexample. If a=2 and b=3, then a+b=5 and ab=6 but 5 < 6 so a + b < ab 6. Prove that there is no smallest integer. Proof: The proof is by contradiction. Suppose that on the contrary there exists a smallest integer, call it S. Recall that 1 > 0. This is so since 1 is not 0, 1=1 2, and the square of any non-zero real number is positive. Let -1 be the additive inverse of the positive integer 1. Then -1 < 0 as 1 > 0: 1 + (-1) > 0 + (-1), then 0 > 0 + (-1), then 0 > -1. By the Closure Property of Addition for the set of integers, S + (-1) is an integer and S + (-1) = S -1 > S by the Definition of Subtraction and since S is the smallest integer by out initial assumption. Adding -S, the additive inverse of S (which is also an integer), to both sides of S-1 > S gives (-S) + (S-1) > (-S) + S (by API) ((-S)+S)-1 > (-S)+S (by Associativity for Addition) 0 -1 > 0 (by the Property of the Additive Inverse) -1 > 0 (by the Property of the Additive Identity) This is a contradiction since we have proven beforehand that -1 < 0. Hence, there does not exist a smallest integer. 7. Prove that if x and y are real numbers, then max(x,y)+min(x,y)=x+y. Proof: Let x and y be real numbers. Then by the Trichotomy Law exactly one of the following is true: Case 1: x = y Case 2: x > y Case 3: x < y. Suppose Case 1 is true, then max(x,y)=min(x,y)=x=y. Then, by substitution, max(x,y)+min(x,y) = x + min(x,y) = x + y, and we have proved our assertion for Case 1 Suppose Case 2 is true, then max(x,y)=x and min(x,y)=y. Then, by substitution, max(x,y)+min(x,y) = x + min(x,y) = x + y, and again we have proved our assertion for Case 2. Finally, suppose Case 3 is true, then max(x,y)=y and min(x,y)=x. Then, by substitution, max(x,y)+min(x,y) = y + x = x + y, because of the Commutative Law of Addition of Real Numbers. We have proved our assertion for Case 3. Since Case 1, 2 and 3, are all the possible Cases given any two real numbers x and y,, and in each instance we were able to show that max(x,y)+min(x,y) = x + y, it must be the case that if x and y are real numbers, then max(x,y)+min(x,y)=x+y. 8. Draw a Venn diagram illustrating the following sets: a. AB A b. B (AC)B B A C c. A(B-C) B A C 9. Use the ceiling and floor functions to give a mathematical expression for the following values: a. There are x children in the first grade at Lee Elementary school. Each child will be given five crayons to do an art project. Crayons come on boxes of 24. How many boxes need to be purchased for the art project? (x children) x (5 crayons/children) = 5x crayons needed (5x crayons) / (24 crayons/box) = 5x/24 = ceiling(5x/24) b. A baker is packaging cookies for sale in boxes of 8. He has y cookies to put into boxes. How many boxes can he sell? (y cookies)/(8 cookies/box) = y/8 = floor(y/8). 10. Here are two relations on the set {a, b, c, d}: S = { (a, b), (a, c), (c, d), (c, a) } R = { (b, c), (c, b), (a, d), (d, b) } Write down the set of pairs in SR. If R is a relation from set X to set Y (i.e., R XY ) and S is a relation from set Y to set Z (i.e., SY Z ), then their composition S R= x , z XZ y Y : x , y X Y y , z Y Z Here, X = Y = Z = {a,b,c,d}, so that R and S are subsets of {a,b,c,d} x {a,b,c,d}. Let X={a,b,c,d}. Observe that, domain R={a,b,c,d} and range R={c,b,d} as R(a)=d, R(b)=c, R(c)=b, and R(d)=b. Also, domain of S={a,c} and range S={a,b,c,d}. Hence, only element c of range R is also in the domain of S. So, with X={a,b,c,d}, S R= x , z X X y Y : x , y XX y , z X X = {x , z X X x , c X X c , zX X } = {b , c } One can also see that R(a)=d, R(c)=b, and R(d)=b are not in the domain of S so that a,c, and d cannot be first coordinates of the relation SR. SR = {(b,c)}, a singleton. 11. List the tuples in the relation {(a, b, c): a, b, and c are positive integers and 0 < a < b < c < 5}. The relation contains only three 3-tuples: {(1,2,3), (1,2,4), (2,3,4)} 12. Write a. b. an algorithm in pseudocode with the following input and output: Input: a1, a2,... ,an, where a is a sequence of numbers and n1. Output: "True" if there are two consecutive numbers in the sequence that are the same. start input ai's, i=1, ..., n for i from 1 by 1 to n-1 for j from i+1 by 1 to n if ai = aj then print \"True\" next j next i stop end 13. Prove that for any n2, 4 evenly divides 32n-1. Proof: Verification Stage: For n=2: 3n-1= 32-1 = 9 -1 =8 and 4 evenly divides 8. So this proposition holds true. Induction Stage: Hypothesis of Induction: Suppose for k 2, 4 evenly divides 3 k-1, then 4 evenly divides 3k+1-1. Proof of the Hypothesis of Induction: To prove the Hypothesis of Induction: Observe that 3k+1-1 = 3k+1+3 -3 -1 = 3(3k+1) - 4. But we know from the premise of the Hypothesis of Induction that 4 evenly divides 3k-1, so 4 evenly divides each term of the last expression above. Hence, 4 evenly divides 3k+1-1. Conclusion: For any n2, 4 evenly divides 3n-1. Midterm 1. Are the expressions p q and q p logically equivalent? Use a truth table to prove your answer. No, p q and q p (converse of p q) are not logically equivalent. The truth table below illustrates this as ca be seen from the last two columns. Had these two statements been equivalent, then those two columns would have been identical. p pq q p 1 1 1 1 1 0 0 1 0 1 1 0 0 2. q 0 1 1 Determine whether the following propositions are true or false: a. 5 is an odd number and 3 is a negative number. T AND F = F b. 5 is an odd number or 3 is a negative number. T OR F = T c. 8 is an odd number or 4 is not an odd number. F OR T = T d. 6 is an even number and 7 is odd or negative. T AND (T OR F) = T AND T = T e. It is not true that 7 is an odd number or 8 is an even number. ~(T OR T) = ~T = F 3. Consider the following statements in English. Write a logical expression with the same meaning. The domain of discourse is the set of all real numbers. a. There is a number whose cube is equal to 2. x x3 =2 b. The square of every number is at least 0. x x 20 c. The reciprocal of every number between 0 and 1 is greater than 1. x x 0,1 1/ x d. Every number has an additive inverse. x y x y=0 4. For Determine the truth value of each expression below if the domain is the set of all real numbers. Then repeat the exercise in which the domain are integers. = set of real numbers as domain a. x y (x + y = 0) TRUE. Existence of the Additive Inverse of every real number. b. x y (x + y = 0) = set of integers as domain For a. x y (x + y = 0) TRUE. Existence of the Additive Inverse of every real number and since b. x y (x + y = 0) FALSE. Uniqueness of the Additive Inverse of a real FALSE. Uniqueness of the Additive Inverse of a real number and since number. c. c. x y z (z = 3/(xy)) TRUE. The Closure Property for the Multiplication of real numbers. d. x y z (z = x/y) FALSE. Division by zero is not defined in the set of real numbers. e. zyx (x2+ y2 = z2) TRUE. Take x=0 and y=z, then x2+y2 = 02+z2 = z2. x y z (z = 3/(xy)) TRUE. The Closure Property for the Multiplication of integers. d. x y z (z = x/y) FALSE. Division by zero is not defined in the set of real numbers. e. zyx (x2+ y2 = z2) TRUE. Take x=0 and y=z, then x2+y2 = 02+z2 = z2. 5. Prove that if a and b are positive real numbers, then a+bab. Proof: This problem seems to be defective. Consider the following counterexample. If a=2 and b=3, then a+b=5 and ab=6 but 5 < 6 so a + b < ab 6. Prove that there is no smallest integer. Proof: The proof is by contradiction. Suppose that on the contrary there exists a smallest integer, call it S. Recall that 1 > 0. This is so since 1 is not 0, 1=1 2, and the square of any non-zero real number is positive (so that 1= 12 > 0). Let -1 be the additive inverse of the positive integer 1. Then -1 < 0 as 1 > 0: 1 + (-1) > 0 + (-1), then 0 > 0 + (-1), then 0 > -1. By the Closure Property of Addition for the set of integers, S + (-1) is an integer and S + (-1) = S -1 > S by the Definition of Subtraction and since S is the smallest integer by our initial assumption. Adding -S, the additive inverse of S (which is also an integer), to both sides of S-1 > S gives (-S) + (S-1) > (-S) + S (by the Addition Property of Inequality) ((-S)+S)-1 > (-S)+S (by Associativity for Addition) 0 -1 > 0 (by the Property of the Additive Inverse) -1 > 0 (by the Property of the Additive Identity) This is a contradiction since we have proven beforehand that -1 < 0. Hence, there does not exist a smallest integer. 7. Prove that if x and y are real numbers, then max(x,y)+min(x,y)=x+y. Proof: Let x and y be real numbers. Then by the Trichotomy Law exactly one of the following is true: Case 1: x = y Case 2: x > y Case 3: x < y. Suppose Case 1 is true, then max(x,y)=min(x,y)=x=y. Then, by substitution, max(x,y)+min(x,y) = x + min(x,y) = x + y, and we have proved our assertion for Case 1 Suppose Case 2 is true, then max(x,y)=x and min(x,y)=y. Then, by substitution, max(x,y)+min(x,y) = x + min(x,y) = x + y, and again we have proved our assertion for Case 2. Finally, suppose Case 3 is true, then max(x,y)=y and min(x,y)=x. Then, by substitution, max(x,y)+min(x,y) = y + x = x + y, because of the Commutative Law of Addition of Real Numbers. We have proved our assertion for Case 3. Since Cases 1, 2 and 3, are all the possible Cases given any two real numbers x and y, and in each instance we were able to show that max(x,y)+min(x,y) = x + y, it must be the case that if x and y are real numbers, then max(x,y)+min(x,y)=x+y. 8. Draw a Venn diagram illustrating the following sets: a. AB A b. B (AC)B B A C c. A(B-C) B A C 9. Use the ceiling and floor functions to give a mathematical expression for the following values: a. There are x children in the first grade at Lee Elementary school. Each child will be given five crayons to do an art project. Crayons come on boxes of 24. How many boxes need to be purchased for the art project? (x children) x (5 crayons/children) = 5x crayons needed (5x crayons) / (24 crayons/box) = 5x/24 = ceiling(5x/24) b. A baker is packaging cookies for sale in boxes of 8. He has y cookies to put into boxes. How many boxes can he sell? (y cookies)/(8 cookies/box) = y/8 = floor(y/8). 10. Here are two relations on the set {a, b, c, d}: S = { (a, b), (a, c), (c, d), (c, a) } R = { (b, c), (c, b), (a, d), (d, b) } Write down the set of pairs in SR. If R is a relation from set X to set Y (i.e., R XY ) and S is a relation from set Y to set Z (i.e., SY Z ), then their composition S R={ x , z X Z y Y : x , y XY y , zY Z} Here, X = Y = Z = {a,b,c,d}, so that R and S are subsets of {a,b,c,d} x {a,b,c,d}. Let X={a,b,c,d}. Observe that, domain R={a,b,c,d} and range R={c,b,d} as R(a)=d, R(b)=c, R(c)=b, and R(d)=b. Also, domain of S={a,c} and range S={a,b,c,d}. Hence, only element c of range R is also in the domain of S. So, with X={a,b,c,d}, S R={ x , z XX yY :x , y X X y , z XX } = {x , z X X x , c X X c , zX X } = {b , c } One can also see that R(a)=d, R(c)=b, and R(d)=b are not in the domain of S so that a,c, and d cannot be first coordinates of the relation SR. Hence, SR = {(b,c)}, a singleton. 11. List the tuples in the relation {(a, b, c): a, b, and c are positive integers and 0 < a < b < c < 5}. The relation contains only three 3-tuples: {(1,2,3), (1,2,4), (2,3,4)} 12. Write a. b. an algorithm in pseudocode with the following input and output: Input: a1, a2,... ,an, where a is a sequence of numbers and n1. Output: "True" if there are two consecutive numbers in the sequence that are the same. start input ai's, i=1, ..., n for i from 1 by 1 to n-1 for j from i+1 by 1 to n if ai = aj then print \"True\" next j next i stop end that for any n2, 4 evenly divides 32n-1. Maybe the problem should be: Prove that for any n2, 4 evenly divides 32n-1 = 9n -1. 13. Prove Proof: Verification Stage: For n=2: 32n-1= 34-1 = 81 -1 =80 and 4 evenly divides 80. So this proposition holds true. Induction Stage: Hypothesis of Induction: Suppose for k 2, 4 evenly divides 32k-1, then 4 evenly divides 32(k+1)-1. Proof of the Hypothesis of Induction: To prove the Hypothesis of Induction: Observe that 32(k+1)-1 = 32k+2 -1 = 32k32 -1 = 9(32k) -1 = 9(32k) -9 + 9 -1 = 9( 32k-1) + 8 But we know from the premise of the Hypothesis of Induction that 4 evenly divides 3k-1, so 4 evenly divides each term of the last expression above. (Or, 9( 32k-1) + 8 = 9(4m) + 8 = 4(9m + 2), fro some integer m since we know that 4 evenly divides 32k-1.) Hence, 4 evenly divides 32(k+1)-1. Conclusion: For any n2, 4 evenly divides 32n-1. Midterm 1. Are the expressions p q and q p logically equivalent? Use a truth table to prove your answer. 2. Determine whether the following propositions are true or false: a. 5 is an odd number and 3 is a negative number. b. 5 is an odd number or 3 is a negative number. c. 8 is an odd number or 4 is not an odd number. d. 6 is an even number and 7 is odd or negative. e. It is not true that 7 is an odd number or 8 is an even number. 3. Consider the following statements in English. Write a logical expression with the same meaning. The domain of discourse is the set of all real numbers. a. There is a number whose cube is equal to 2. b. The square of every number is at least 0. c. The reciprocal of every number between 0 and 1 is greater than 1. d. Every number has an additive inverse. 4. Determine the truth value of each expression below if the domain is the set of all real numbers. Then repeat the exercise in which the domain are integers. a. x y (x + y = 0) b. x y (x + y = 0) c. x y z (z = 3/(xy)) d. x y z (z = x/y) e. zyx (x2+ y2 = z2) 5. Prove that if a and b are positive real numbers, then 6. Prove that there is no smallest integer. + . 7. Prove that if x and y are real numbers, then max(x,y)+min(x,y)=x+y. a. 8. Draw a Venn diagram illustrating the following sets: b. c. 9. Use the ceiling and floor functions to give a mathematical expression for the following values: a. There are x children in the first grade at Lee Elementary school. Each child will be given five crayons to do an art project. Crayons come on boxes of 24. How many boxes need to be purchased for the art project? b. A baker is packaging cookies for sale in boxes of 8. He has y cookies to put into boxes. How many boxes can he sell? 10. Here are two relations on the set {a, b, c, d}: S = { (a, b), (a, c), (c, d), (c, a) } R = { (b, c), (c, b), (a, d), (d, b) } Write down the set of pairs in SR. 11. List the tuples in the relation {(a, b, c): a, b, and c are positive integers and 0 < a < b < c < 5}. 12. Write an algorithm in pseudocode with the following input and output: Input: a1, a2,... ,an, where a is a sequence of numbers and n1. Output: "True" if there are two consecutive numbers in the sequence that are the same. 13. Prove that for any , evenly divides 2 . Midterm 1. Are the expressions p q and q p logically equivalent? Use a truth table to prove your answer. No, p q and q p (converse of p q) are not logically equivalent. The truth table below illustrates this as ca be seen from the last two columns. Had these two statements been equivalent, then those two columns would have been identical. p pq q p 1 1 1 1 1 0 0 1 0 1 1 0 0 2. q 0 1 1 Determine whether the following propositions are true or false: a. 5 is an odd number and 3 is a negative number. T AND F = F b. 5 is an odd number or 3 is a negative number. T OR F = T c. 8 is an odd number or 4 is not an odd number. F OR T = T d. 6 is an even number and 7 is odd or negative. T AND (T OR F) = T AND T = T e. It is not true that 7 is an odd number or 8 is an even number. ~(T OR T) = ~T = F 3. Consider the following statements in English. Write a logical expression with the same meaning. The domain of discourse is the set of all real numbers. a. There is a number whose cube is equal to 2. x x3 =2 b. The square of every number is at least 0. x x 20 c. The reciprocal of every number between 0 and 1 is greater than 1. x x 0,1 1/ x d. Every number has an additive inverse. x y x y=0 4. For Determine the truth value of each expression below if the domain is the set of all real numbers. Then repeat the exercise in which the domain are integers. = set of real numbers as domain a. x y (x + y = 0) TRUE. Existence of the Additive Inverse of every real number. b. x y (x + y = 0) = set of integers as domain For a. x y (x + y = 0) TRUE. Existence of the Additive Inverse of every real number and since b. x y (x + y = 0) FALSE. Uniqueness of the Additive Inverse of a real FALSE. Uniqueness of the Additive Inverse of a real number and since number. c. c. x y z (z = 3/(xy)) TRUE. The Closure Property for the Multiplication of real numbers. d. x y z (z = x/y) FALSE. Division by zero is not defined in the set of real numbers. e. zyx (x2+ y2 = z2) TRUE. Take x=0 and y=z, then x2+y2 = 02+z2 = z2. x y z (z = 3/(xy)) TRUE. The Closure Property for the Multiplication of integers. d. x y z (z = x/y) FALSE. Division by zero is not defined in the set of real numbers. e. zyx (x2+ y2 = z2) TRUE. Take x=0 and y=z, then x2+y2 = 02+z2 = z2. 5. 6. Prove that if a and b are positive real numbers, then ab ab a+bab. Proof: Let a and b be positive real numbers. Then by the definition of a principal square root of a positive real number, a and b are also real numbers. Hence, b is also a real number because of the existence of the additive inverse of every real number. By the Closure Property of Addition of Real numbers a b is also a real number. Since the square of any real number is at least 0 (0x0=0, while a 2 > 0, for any non-zero real number), then 2 a b 0 2 2 a 2 a b b 0, since for all reals x , y : x y 2 =x2 2xy y 2 a2 a bb0 by Associativity, Commutativity of Multiplication and that (-1)*a =-a ab2 a b by the Addition Property of Inequality, Existence of Add Inv, Property of Add Identity Since a and b then both are non-negative so that Addition Property of Inequality, a b a b0 a b 2 a b a b . From (*) and (**). ab2 a b a b . By the Transitive Property of Inequality, ab a b . By the Rules of Exponenets, a b= ab , so, ab ab , which is what we wanted to prove. a b0. By the 7. Prove that there is no smallest integer. Proof: The proof is by contradiction. Suppose that on the contrary there exists a smallest integer, call it S. Recall that 1 > 0. This is so since 1 is not 0, 1=1 2, and the square of any non-zero real number is positive (so that 1= 12 > 0). Let -1 be the additive inverse of the positive integer 1. Then -1 < 0 as 1 > 0: 1 + (-1) > 0 + (-1), then 0 > 0 + (-1), then 0 > -1. By the Closure Property of Addition for the set of integers, S + (-1) is an integer and S + (-1) = S -1 > S by the Definition of Subtraction and since S is the smallest integer by our initial assumption. Adding -S, the additive inverse of S (which is also an integer), to both sides of S-1 > S gives (-S) + (S-1) > (-S) + S (by the Addition Property of Inequality) ((-S)+S)-1 > (-S)+S (by Associativity for Addition) 0 -1 > 0 (by the Property of the Additive Inverse) -1 > 0 (by the Property of the Additive Identity) This is a contradiction since we have proven beforehand that -1 < 0. Hence, there does not exist a smallest integer. 8. Prove that if x and y are real numbers, then max(x,y)+min(x,y)=x+y. Proof: Let x and y be real numbers. Then by the Trichotomy Law exactly one of the following is true: Case 1: x = y Case 2: x > y Case 3: x < y. Suppose Case 1 is true, then max(x,y)=min(x,y)=x=y. Then, by substitution, max(x,y)+min(x,y) = x + min(x,y) = x + y, and we have proved our assertion for Case 1 Suppose Case 2 is true, then max(x,y)=x and min(x,y)=y. Then, by substitution, max(x,y)+min(x,y) = x + min(x,y) = x + y, and again we have proved our assertion for Case 2. Finally, suppose Case 3 is true, then max(x,y)=y and min(x,y)=x. Then, by substitution, max(x,y)+min(x,y) = y + x = x + y, because of the Commutative Law of Addition of Real Numbers. We have proved our assertion for Case 3. Since Cases 1, 2 and 3, are all the possible Cases given any two real numbers x and y, and in each instance we were able to show that max(x,y)+min(x,y) = x + y, it must be the case that if x and y are real numbers, then max(x,y)+min(x,y)=x+y. 9. Draw a Venn diagram illustrating the following sets: a. AB A b. B (AC)B B A C c. A(B-C) B A C 10. Use the ceiling and floor functions to give a mathematical expression for the following values: a. There are x children in the first grade at Lee Elementary school. Each child will be given five crayons to do an art project. Crayons come on boxes of 24. How many boxes need to be purchased for the art project? (x children) x (5 crayons/children) = 5x crayons needed (5x crayons) / (24 crayons/box) = 5x/24 = ceiling(5x/24) b. A baker is packaging cookies for sale in boxes of 8. He has y cookies to put into boxes. How many boxes can he sell? (y cookies)/(8 cookies/box) = y/8 = floor(y/8). 11. Here are two relations on the set {a, b, c, d}: S = { (a, b), (a, c), (c, d), (c, a) } R = { (b, c), (c, b), (a, d), (d, b) } Write down the set of pairs in SR. If R is a relation from set X to set Y (i.e., R XY ) and S is a relation from set Y to set Z (i.e., SY Z ), then their composition S R={ x , z X Z y Y : x , y XY y , zY Z} Here, X = Y = Z = {a,b,c,d}, so that R and S are subsets of {a,b,c,d} x {a,b,c,d}. Observe that, domain R={a,b,c,d} and range R={c,b,d} as R(a)=d, R(b)=c, R(c)=b, and R(d)=b. Also, domain of S={a,c} and range S={a,b,c,d}. Hence, only element c of range R is also in the domain of S. So, with X={a,b,c,d}, S R={ x , z XX yY :x , y X X y , z XX } = {x , z X X x , c X X c , zX X } = {b , c } One can also see that R(a)=d, R(c)=b, and R(d)=b are not in the domain of S so that a,c, and d cannot be first coordinates of the relation SR. Hence, SR = {(b,c)}, a singleton. 12. List the tuples in the relation {(a, b, c): a, b, and c are positive integers and 0 < a < b < c < 5}. The relation contains only three 3-tuples: {(1,2,3), (1,2,4), (2,3,4)} 13. Write a. b. an algorithm in pseudocode with the following input and output: Input: a1, a2,... ,an, where a is a sequence of numbers and n1. Output: "True" if there are two consecutive numbers in the sequence that are the same. start input ai's, i=1, ..., n for i from 1 by 1 to n-1 for j from i+1 by 1 to n if ai = aj then print \"True\" next j next i stop end 14. Prove that for any n2, 4 evenly divides 32n-1. Proof: Verification Stage: For n=2: 32n-1= 34-1 = 81 -1 =80 and 4 evenly divides 80. So this proposition holds true. Induction Stage: Hypothesis of Induction: Suppose for k 2, 4 evenly divides 32k-1, then 4 evenly divides 32(k+1)-1. Proof of the Hypothesis of Induction: To prove the Hypothesis of Induction: Observe that 32(k+1)-1 = 32k+2 -1 = 32k32 -1 = 9(32k) -1 = 9(32k) -9 + 9 -1 = 9( 32k-1) + 8 But we know from the premise of the Hypothesis of Induction that 4 evenly divides 32k-1, so 4 evenly divides each term of the last expression above. (Or, 9( 32k-1) + 8 = 9(4m) + 8 = 4(9m + 2), for some integer m since we know that 4 evenly divides 32k-1.) Hence, 4 evenly divides 32(k+1)-1. Conclusion: For any n2, 4 evenly divides 32n-1