Discrete Math Assignment 1

Assignment 1 1) Exercise Set 1.1 (p. 5+ of Epp, fifth edition): Is there an integer that has a remainder of 2 when it is divided by 5 and a remainder of 3 when it is divided by 6? a. Is there an integer n such that n has___? So, the statement becomes “Is there an integer n such that n has a remainder of 2 when it is divided by 5 and a remainder of 3 when it is divided by 6 ?” b. Does there exist ___such that if n is divided by 5 the remainder is 2 and if___? So, the statement becomes “Does there exist an integer n such that if n is divided by 5 the remainder is 2 and if n is divided by 6 the remainder is 3?   2) Exercise Set 1.2 (p. 14+): a. Is 2 [ {2}? yes b. How many elements are in the set {2, 2, 2, 2}? one c. How many elements are in the set {0, {0}}? two d. Is {0} [ {{0}, {1}}? yes e. Is 0 [ {{0}, {1}}? no A. Is 3 E {1, 2, 3}? Yes b. Is 1 C {1}? no c. Is {2} E {1, 2}? no d. Is {3} E {1, {2}, {3}}? yes e. Is 1 E {1}? yes f. Is {2} C {1, {2}, {3}}? no g. Is {1} C {1, 2}? yes h. Is 1 E {{1}, 2}? no i. Is {1} C {1, {2}}? yes j. Is {1} C {1}? yes

Let S = {2, 4, 6} and T = {1, 3, 5}. Use the setroster notation to write each of the following sets, and indicate the number of elements that are in each set. a. S X T {(2*1), (2*3), (2*5), (4*1), (4*3), (4*5), (6*1), (6*3), (6*5)} b. T X S {(1*2), (1*4), (1*6), (3*2), (3*4), (3*6), (5*2), (5*4), (5*6)} c. S X S {(2*2), (2*4), (2*6), (4*2), (4*4), (4*6), (6*2), (6*4), (6*6)} d. T X T {(1*1), (1*3), (1*5), (3*1), (3*3), (3*5), (5*1), (5*3), (5*5)} 3) Exercise Set 1.3 (p. 22+): 2) Let C = D = {-3, -2, -1, 1, 2, 3} and define a relation S from C to D as follows: For every (x, y) E C X D, (x, y) E S means that 1/X- 1/Y y is an integer. How do we define relationship S from C to D? For all (X, Y) E C x D X S Y if 1/X- 1/Y Is an Integer. Relation written symbolically as follows: X S y Means that (x, y) E S a. Is 2 S 2? x=2, y=2 2 S 2 since (½) – (½)= 0 is an integer. Is -1 S -1? X=-1, Y=-1 -1S-1 Since (-1/2) -(1/2) = 0 is an integer. Is (3, 3) E S? X=3 y=3 1/3 – 1/3= 0 is an integer. Is (3, -3) E S? X=3 y=-3 1/3 – (1/-3) = 2/3 is not an integer b. Write S as a set of ordered pairs. S= {(x, y) E S|1/Y 1/Y Is an integer

C S D 6) Define a relation R from R to R as follows: For every (x, y) [ R E R, (x, y) [ R means that y 5 x 2 . X R Y if y=x^2 A. Is (2, 4) E R? Yes, (2,4) E R as 4=2^2 Is (4, 2) E R? No, (4,2) E R as 2 not 4^2. Is (-3) R 9? Yes, -3 R 9 as 9= (-3) ^2 Is 9 R (23)? No, because -3 not 9^2 b. Draw the graph of R in the Cartesian plane. y 3 2 1 1 -1 -2 -3 3 2 -1 -2 -3 1 2 -1 -2  Y=x^2 1 2

10) Find four relations from {a, b} to {x, y} that are not functions from {a, b} to {x, y}. To not be a function, it must either have no elements or multiple elements with some given first component (a or b). 1) For R = {(a, x), (a, y), (b, x)} is not a function from {a, b} to {x, y} because there are two values related to a 2)R = {(a, x)} is not a function from {a, b} to {x, y} because there are no values related to b 3)R=(a, y) 4)R=(b,x) 5)R=(b,y) 12) Let A = {x, y} and let S be the set of all strings over A. Define a relation C from S to S as follows: For all strings s and t in S, (s, t) E C means that t = ys. Then C is a function because every string in S consists entirely of x’s and y’s and adding an additional y on the left creates a single new string that consists of x’s and y’s and is, therefore, also in S. Find C(x) and C(yyxyx). 1. C(X): We input one string ‘x’ A ‘y’ must be added at the start pf the string in order to have a relation to C. By combining ‘y’ and ‘x’ we create a string yx. 2. C(yyxyx): Input ‘’yyxyx’ We apply C: “yyyxyx” We should start by reapplying the relation to C like we did in prior steps, and this tells us to add another “y” Input: " yyyxyx " Apply C: " yyyyxyx " After the second application of C, we get " yyyyxyx ."

E1 V1 V5 E4 V4 V2 V3 E3 E2 9) For each of the graphs in 8 and 9: (i) Find all edges that are incident on V1. e1,e2 and e7. (ii) Find all vertices that are adjacent to V3. v1 and v2 are adjacent to V3. (iii) Find all edges that are adjacent to e1. e2,e7 are adjacent to e1. (iv) Find all loops. e1,e3 are loops. (v) Find all parallel edges. e4,e5 are parallel edges. (vi) Find all isolated vertices. v4 is the only isolated vertex. (vii) Find the degree of V3. Degree of v3 = 2.

Exercise Set 2.1 (p. 51+): In each of 1–4 represent the common form of each argument using letters to stand for component sentences, and fill in the blanks so that the argument in part (b) has the same logical form as the argument in part (a). 2) If all computer programs contain errors, then this program contains an error. This program does not contain an error. Therefore, it is not the case that all computer programs contain errors. The first statement can be written as p  q The second statement can be written as ~q then, third statements is ~p Now if we combine the statements p  q ~q =>~p b. If ______, then_______ . 2 is not odd. Therefore, it is not the case that all prime numbers are odd. From part a, the second argument is ~ q and it is given that " 2 is not odd". third argument is ~p and is given that not all prime numbers are odd. Therefore, P= “all primes are odd” Then  if all prime numbers are odd, then 2 is odd “Therefore, it is not the case that all prime numbers are odd.” 6) Write the statements in 6–9 in symbolic form using the symbols ~,v, and `^ and the indicated letters to represent component statements. Let s = “stocks are increasing” and i = “interest rates are steady.” a. Stocks are increasing but interest rates are steady. = s^i b. Neither are stocks increasing nor are interest rates steady. = ~S^~i

p: "The train is late." q: "My watch is fast." ∼ (p ∨ q) ≡ ( ∼ p) ∧ ( ∼ q) "The train is not late, and my watch is not fast." Exercise Set 2.2 (p. 63+): 13) Use truth tables to verify the following logical equivalences. Include a few words of explanation with your answers. P Q P  Q ∼ (p  q) ∼q p ∧∼ q T T T F F F T F F T T T F T T F F F F F T F F F ∼ (p  q) "It is not the case that if p is true, then q is true." This only happens when p is true, and q is false. p ∧∼ q “p is true, and q is not true." Both statements basically say the same thing in different words. They are both true only when p is true and q is false, and they are false in any other situation. 18) Write each of the following three statements in symbolic form and determine which pairs are logically equivalent. Include truth tables and a few words of explanation. If it walks like a duck and it talks like a duck, then it is a duck. Either it does not walk like a duck, or it does not talk like a duck, or it is a duck. If it does not walk like a duck and it does not talk like a duck, then it is not a duck. p: It walks like a duck. q: It talks like a duck. r: It is a duck. 1. "If it walks like a duck and it talks like a duck, then it is a duck." Symbolic form:(p ∧ q)→r 2. "Either it does not walk like a duck, or it does not talk like a duck, or it is a duck."

Symbolic form: ¬p ∨ ¬q ∨ r 3. "If it does not walk like a duck and it does not talk like a duck, then it is not a duck." Symbolic form: (¬p ∧ ¬q)→¬r p q r ¬p ¬q ¬r (p ∧ q) ¬p ∨ ¬q ¬p ∧ ¬q (p ∧ q)→r ¬p ∨ ¬qVr (¬p ∧ ¬q)→¬r T T T F F F T F F T T T T T F F F T T F F F F T T F T F T F F T F T T T T F F F T T F T F T T T F T T T F F F T F T T T F T F T F T F T F T T T F F T T T F F T T T T F F F F T T T F T T T T T Exercise Set 2.3 (p. 76+) 12(b) Use truth tables to show that the following forms of argument are invalid p q p  q ¬p ¬q T T T F F T F F F T F T T T F (Here) F F T T T Row (here) shows that it is possible for an argument to have true premises and a false conclusion at the same time. 13. Modus tollens: Use truth tables to show that the argument forms referred to in 13–21 are valid. Indicate which columns represent the premises and which represent the conclusion and include a sentence

Therefore, ~Q The argument form looks like it is trying to be Modus Tollens, but instead of the second premise being ~Q (the negation of the consequent), it is ~P (the negation of the antecedent). Modus Tollens should be: P → Q ~Q Therefore, ~P But the argument given is: P → Q ~P Therefore, ~Q Then It is indeed an inverse error. 30) If this computer program is correct, then it produces the correct output when run with the test data my teacher gave me. This computer program produces the correct output when run with the test data my teacher gave me. Therefore, this computer program is correct. P: This computer program is correct. Q: It produces the correct output when run with the test data my teacher gave me. The logical form of the argument: P → Q (If this computer program is correct, then it produces the correct output with the test data.) Q (The computer program produces the correct output with the test data my teacher gave me.) Therefore, P (The computer program is correct.) Symbolically : P→Q Q Therefore, P This is an example of the converse error, where the direction of the implication is reversed. To correctly conclude that the computer program is correct (P), one would need the first premise and a statement affirming the antecedent (P), not the consequent (Q).

31. Sandra knows Java and Sandra knows C++. [ Sandra knows C++. P= “Sandra knows Java”   Q= “Sandra knows   C ++”. Symbolic: p^q therefore, q From the premise that Sandra knows Java and C++, it follows by specialization that Sandra knows C+ +. Exercise Set 3.1 (p. 119+): 5. a. The truth set will include all divisors of 6 in the integer set, which are ±1, ±2, ±3, and ±6. Truth set: {1, -1, 2, -2, 3, -3, 6, -6} b. The domain Z+ refers to the set of all positive integers. The truth set will include only the positive divisors of 6. Truth set: {1, 2, 3, 6} c. The domain R refers to all real numbers. The numbers that satisfy x^2 = 1 are x = 1 and x = -1. The numbers that satisfy x^2 = 4 are x = 2 and x = -2. Since the domain includes all real numbers, all numbers between these values will also satisfy the inequality. Truth set: [-2, -1] ∪ [1, 2] d. The domain Z refers to all integers, specifically integers whose square is between 1 and 4. Truth set: {-1, 1, 2} 10. Find counterexamples to show that the statements in 9–12 are false One obvious counterexample is when a = 1: (1−1)/1=0/1=0

Statement: The product of any irrational number and any rational number is irrational. Proposed negation: The product of any irrational number and any rational number is rational. The proposed negation is not correct. Correct Negation: There exists an irrational number and a rational number whose product is rational. Exercise Set 3.3 (p. 143+): The statements in exercises 5–8 refer to the Tarski world given in Figure 3.3.1. explain why each is true. 6. For every square x there is a circle y such that x and y have different colors and y is above x. The following table shows 4 squares that for each square there is a circle with a different color above the square. X= Y= Check that x &y color diff Check that y above x e A,b or c yes yes g A or c yes yes h A or c yes yes j b yes yes Since all arguments are true the given statement is true. 8. There is a triangle x such that for every circle y, y is above x. The statement "There is a triangle x such that for every circle y, y is above x." would be considered true if for one of the triangles (which we would call x), every circle present in the Tarski world (y) is positioned in rows above the triangle. Triangle f has circle c above it but not circle a, so f cannot be the triangle x that satisfies the condition. Triangle i has circle a above it, and there are no other circles in rows below i. 10. This exercise refers to Example 3.3.3. Determine whether each of the following statements is true or false. a. The meaning of the statement is that every student chose at least one dessert. The statement is true because every student chooses at least one dessert. Uta chooses pie, Tim chooses both pie and cake, and Yuen chooses pie.

b. The meaning of the above statement is that every student chose at least one salad. The above statement is false because Yuen doesn’t choose any of the salads. c. The statement says that some dessert was chosen by every student. The above statement is true because every student chose pie. d. This statement says that a particular beverage was chosen by every student. The above statement is false because Ute and Tim chose milk, but Yuen doesn’t. 35. In 33–39, (a) rewrite the statement formally using quantifiers and variables, and (b) write a negation for the statement. Everybody trusts somebody. Formal:   ∀ people   a ,   ∃   a person   b   such that   a   trusts   b Negation: ∃ a person a such that ∀ people b, a does not trust b 36. Somebody trusts everybody. Formal: ∃ a ∀ b, T(a,b) which is equal to there is at least one person(a) who trusts every person (b). Negation: "Not everybody is trusted by somebody." ∀ a ∃ b,¬T(a,b) Exercise Set 3.4 (p. 157+): Some of the arguments in 7–18 are valid by universal modus ponens or universal modus tollens; others are invalid and exhibit the converse or the inverse error. State which are valid and which are invalid. Justify your answers. Considering the premise “All cheaters sit in the back row “to be correct. We can say that is not clear that Monty is a cheater or not. The conclusion “Monty is a cheater” is true for the first case but not in the second case. The conclusion does not follow from the premises therefore is not valid. The conclusion is invalid therefore, the statement is invalid by converse error.