Computer science Discrete Mathemathics Questions
Programming
Problem 1. (4 points) In the movie “Monty Python and the Holy Grail” we encounter a medieval villager who (with a bit of prompting) makes the following argument.
If she weighs the same as a duck, then she’s made of wood.
If she’s made of wood, then she’s a witch.
Therefore, if she weighs the same as a duck, she’s a witch.
(a) Rewrite this argument symbolically, assigning letters to sub-statements.
(b) Do you think the argument is valid? That is, if we accept the first two sentences as true, is the third sentence necessarily true?
Problem 2. (4 points) Suppose that the statement ” “((P ꓥ Q) V R) à (R V S)” ” is false. Is is possible to determine whether P is true or false? If so, which is it?
Problem 3. (12 points) Suppose Sarah has proven a theorem that if the squig is murvous, then it is either broomly or thrial. For each of the following statements, write it symbolically in terms of the following letters: M = the squig is murvous
B = the squig is broomly
T = the squig is thrial
and then indicate whether that statement is necessarily also true, given Sarah’s theorem.
(a)If the squig is either broomly or thrial, then it is murvous.
(b)If the squig is not murvous, then it is either not broomly or not thrial.
(c) If the squig is not either broomly or thrial, then it is not murvous.
(d) If the squig is not broomly and also not thrial, then it is not murvous.
(e) If the squig is murvous, then it is not both broomly and thrial.
(f) The squig is either broomly, thrial, or not murvous.
Problem 4. (10 points) For each of the following statements, write its negation in English in fully simplified form(i.e. all negations “pushed inside”). You may translate it into symbols if you wish, but that is not necessary; your final answer should be written in English.
(a) There exists a real number that is greater than √2
(b) For any integer x, if x2 is odd then x is odd.
Problem 1. (4 points) In the movie “Monty Python and the Holy Grail” we encounter a medieval villager who (with a bit of prompting) makes the following argument.
If she weighs the same as a duck, then she’s made of wood.
If she’s made of wood, then she’s a witch.
Therefore, if she weighs the same as a duck, she’s a witch.
(a) Rewrite this argument symbolically, assigning letters to sub-statements.
(b) Do you think the argument is valid? That is, if we accept the first two sentences as true, is the third sentence necessarily true?
Problem 2. (4 points) Suppose that the statement ” “((P ꓥ Q) V R) à (R V S)” ” is false. Is is possible to determine whether P is true or false? If so, which is it?
Problem 3. (12 points) Suppose Sarah has proven a theorem that if the squig is murvous, then it is either broomly or thrial. For each of the following statements, write it symbolically in terms of the following letters: M = the squig is murvous
B = the squig is broomly
T = the squig is thrial
and then indicate whether that statement is necessarily also true, given Sarah’s theorem.
(a)If the squig is either broomly or thrial, then it is murvous.
(b)If the squig is not murvous, then it is either not broomly or not thrial.
(c) If the squig is not either broomly or thrial, then it is not murvous.
(d) If the squig is not broomly and also not thrial, then it is not murvous.
(e) If the squig is murvous, then it is not both broomly and thrial.
(f) The squig is either broomly, thrial, or not murvous.
Problem 4. (10 points) For each of the following statements, write its negation in English in fully simplified form (i.e. all negations “pushed inside”). You may translate it into symbols if you wish, but that is not necessary; your final answer should be written in English.
(a) There exists a real number that is greater than √2
(b) For any integer x, if x^2 is odd then x is odd.
(c) There exists an integer m such that for all integers n we have m ˃ n.
(d) Every floop is either glarzy or mival.
(e) If there exists a floop that is not splanzy, then there exists a floop that is both glarzy and mival.
Problem 5. (10 points) Suppose P(x, y) : “x and y live in the same building”, where the
Domain of x, y is student at USD. For each of the following statements, is it true? Explain why or why not in one sentence or less.
(a) Ɐx.Ɐy.P(x, y).
(b) Ɐx.ꓱy.P(x, y).
(c) ꓱx.Ɐy.P(x,y).
(d) ꓱx.ꓱy.(P(x,y) ꓥ x ≠ y
(e) Ɐx.Ɐy.Ɐz.((P(x, y) ꓥ P(y, z)) à P(x, z)).
Problem 6. (5 points) Suppose that at some point during the proof of a theorem, our goal is “c : 3 or d: 3” and among the givens (assumptions) we have “x > 7 or x < 0”, where all variables represent real numbers. For each of the following proposed case splits, indicate whether it would be an allowable step to perform in the proof at this point, based only on the information known, and explain why in one sentence or less.
(a) Case 1: c = 3. . . . Case 2: d = 3. .. .
(b) Case 1: c = 3. . ..Case 2: c = 4. . . .
(c) Case 1: c = 3. . . . Case 2: c ≠ 3. . . .
(d) Case 1: x > 7. … Case 2: x < 0. …
(e) Case 1: c ≥ 0. . . . Case 2: c < 0. . . .
Problem 7. (10 points) prove that for any real number x there exist a real number y such that x + 3y = 2.
Problem 8. (10 points) Recall the definition of the divisibility:
For integers a, b we write a | b if there exists an integer k such that ka = b.
Prove that for any integer n, if 10 | n then 5| n.
Problem9. (10 points) Recall that the definitions of even and odd:
An integer x is even if there exists an integer k such that x = 2k.
An integer x is odd if there exists an integer k such that x = 2k + 1.
Prove that for any integer x and any odd integer y, either x is odd or x + y is odd.
is odd then x is odd.
(c) There exists an integer m such that for all integers n we have m ˃ n.
(d) Every floop is either glarzy or mival.
(e) If there exists a floop that is not splanzy, then there exists a floop that is both glarzy and mival.
Problem 5. (10 points) Suppose P(x, y) : “x and y live in the same building”, where the
Domain of x, y is student at USD. For each of the following statements, is it true? Explain why or why not in one sentence or less.
(a) Ɐx.Ɐy.P(x, y).
(b) Ɐx.ꓱy.P(x, y).
(c) ꓱx.Ɐy.P(x,y).
(d) ꓱx.ꓱy.(P(x,y) ꓥ x ≠ y
(e) ⱯxⱯyⱯz.((P(x, y) ꓥ P(y, z)) à P(x, z)).
Problem 6. (5 points) Suppose that at some point during the proof of a theorem, our goal is “c : 3 or d: 3” and among the givens (assumptions) we have “x > 7 or x < 0”, where all variables represent real numbers. For each of the following proposed case splits, indicate whether it would be an allowable step to perform in the proof at this point, based only on the information known, and explain why in one sentence or less.
(a) Case 1: c = 3. . . . Case 2: d = 3. .. .
(b) Case 1: c = 3. . ..Case 2: c = 4. . . .
(c) Case 1: c = 3. . . . Case 2: c ≠ 3. . . .
(d) Case 1: x > 7. … Case 2: x < 0. …
(e) Case 1: c ≥ 0. . . . Case 2: c < 0. . . .
Problem 7. (10 points) prove that for any real number x there exist a real number y such that x + 3y = 2.
Problem 8. (10 points) Recall the definition of the divisibility:
For integers a, b we write a | b if there exists an integer k such that ka = b.
Prove that for any integer n, if 10 | n then 5| n.
Problem9. (10 points) Recall that the definitions of even and odd:
An integer x is even if there exists an integer k such that x = 2k.
An integer x is odd if there exists an integer k such that x = 2k + 1.
Prove that for any integer x and any odd integer y, either x is odd or x + y is odd.
