| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Stop wasting time looking for files and revisions. Connect your Gmail, DriveDropbox, and Slack accounts and in less than 2 minutes, Dokkio will automatically organize all your file attachments. Learn more and claim your free account.

View
 

Quiz: Logic

Page history last edited by Terence Tao 9 years, 1 month ago Saved with comment

This quiz is designed to test your knowledge of the basics of mathematical logic (logical connectives such as negation and implication, as well as quantifiers).

 

Discuss this quiz 

(Key: correct, incorrect, partially correct.)

 

  1. Let X and Y be statements. If we know that X implies Y, then we can also conclude that
    1. X is true, and Y is also true.
    2. Y cannot be false.
    3. If Y is true, then X is true.
    4. If Y is false, then X is false.
      • CORRECT.
    5. If X is false, then Y is false.
    6. X cannot be false.
    7. At least one of X and Y is true.
  2. Let X and Y be statements. If we want to disprove the claim that "Both X and Y are true", we need to show that
    1. At least one of X and Y are false.
      • CORRECT.
    2. X and Y are both false.
    3. X is false.
      • PARTIALLY. This will indeed disprove "Both X and Y are true", but X does not need to be false in order to disprove the above statement.
    4. Y is false.
      • PARTIALLY. This will indeed disprove "Both X and Y are true", but Y does not need to be false in order to disprove the above statement.
    5. X does not imply Y, and Y does not imply X.
    6. Exactly one of X and Y are false.
    7. X is true if and only if Y is false.
  3. Let X and Y be statements. If we want to disprove the claim that "At least one of X and Y are true", we need to show that
    1. At least one of X and Y are false.
    2. X and Y are both false.
      • CORRECT.
    3. X is false.
    4. Y is false.
    5. X does not imply Y, and Y does not imply X.
    6. Exactly one of X and Y are false.
    7. X is true if and only if Y is false.
  4. Let X and Y be statements. If we want to disprove the claim that "X implies Y", we need to show that
    1. Y is true, but X is false.
    2. X is true, but Y is false.
      • CORRECT.
    3. X is false.
    4. Y is false.
    5. X and Y are both false.
    6. Exactly one of X and Y are false.
    7. At least one of X and Y is false.
  5. Let P(x) be a property about some object x of type X. If we want to disprove the claim that "P(x) is true for all x of type X", then we have to
    1. Show that there exists an x of type X for which P(x) is false.
      • CORRECT.
    2. Show that there exists an x which is not of type X, but for which P(x) is still true.
    3. Show that for every x of type X, P(x) is false.
    4. Show that P(x) being true does not necessarily imply that x is of type X.
    5. Assume there exists an x of type X for which P(x) is true, and derive a contradiction.
    6. Show that there are no objects x of type X.
      • INCORRECT. Actually, if there are no objects of type X, then the statement "P(x) is true for all x of type X" is automatically true (but vacuously so)!
    7. Show that for every x of type X, there is a y not equal to x for which P(y) is true.
  6. Let P(x) be a property about some object x of type X. If we want to disprove the claim that "P(x) is true for some x of type X", then we have to
    1. Show that there exists an x of type X for which P(x) is false.
    2. Show that there exists an x which is not of type X, but for which P(x) is still true.
    3. Show that for every x of type X, P(x) is false.
      • CORRECT.
    4. Show that P(x) being true does not necessarily imply that x is of type X.
    5. Assume that P(x) is true for every x of type X, and derive a contradiction.
    6. Show that there are no objects x of type X.
      • PARTIAL. This will certainly disprove the claim, however, one does not always need X to be empty in order to disprove the claim.
    7. Show that for every x of type X, there is a y not equal to x for which P(y) is true.
  7. Let P(n,m) be a property about two integers n and m. If we want to prove that "For every integer n, there exists an integer m such that P(n,m) is true", then we should do the following:
    1. Let n be an arbitrary integer. Then find an integer m (possibly depending on n) such that P(n,m) is true.
      • CORRECT.
    2. Let n and m be arbitrary integers. Then show that P(n,m) is true.
      • INCORRECT. This will definitely prove what we want, but is far too strong, it proves much more than what we need!
    3. Find an integer n and an integer m such that P(n,m) is true.
    4. Let m be an arbitrary integer. Then find an integer n (possibly depending on m) such that P(n,m) is true.
    5. Find an integer n such that P(n,m) is true for every integer m.
    6. Find an integer m such that P(n,m) is true for every integer n.
      • INCORRECT. This will prove what we want, but it is too strong - it proves more than we need.
    7. Show that whenever P(n,m) is true, then n and m are integers.
  8. Let P(n,m) be a property about two integers n and m. If we want to disprove the claim that "For every integer n, there exists an integer m such that P(n,m) is true", then we need to prove that
    1. There exists an integer n such that P(n,m) is false for all integers m.
      • CORRECT.
    2. There exists integers n,m such that P(n,m) is false.
    3. For every integer n, and every integer m, the property P(n,m) is false.
    4. For every integer n, there exists an integer m such that P(n,m) is false.
    5. For every integer m, there exists an integer n such that P(n,m) is false.
    6. There exists an integer m such that P(n,m) is false for all integers n.
    7. If P(n,m) is true, then n and m are not integers.
  9. Let P(n,m) be a property about two integers n and m. If we want to disprove the claim that "There exists an integer n such that P(n,m) is true for all integers m", then we need to prove that
    1. There exists an integer n such that P(n,m) is false for all integers m.
    2. There exists integers n,m such that P(n,m) is false.
    3. For every integer n, and every integer m, the property P(n,m) is false.
    4. For every integer n, there exists an integer m such that P(n,m) is false.
      • CORRECT.
    5. For every integer m, there exists an integer n such that P(n,m) is false.
    6. There exists an integer m such that P(n,m) is false for all integers n.
    7. If P(n,m) is true, then n and m are not integers.
  10. Let X and Y be statements. Which of the following strategies is not a valid way to show that "X implies Y"?
    1. Assume that X is true, and then use this to show that Y is true.
    2. Assume that Y is false, and then use this to show that X is false.
    3. Show that either X is false, or Y is true, or both.
    4. Assume that X is true, and Y is false, and deduce a contradiction.
    5. Assume that X is false, and Y is true, and deduce a contradiction.
      • CORRECT.
    6. Show that X implies some intermediate statement Z, and then show that Z implies Y.
    7. Show that some intermediate statement Z implies Y, and then show that X implies Z.
  11. Suppose one wishes to prove that "if all X are Y, then all Z are W". To do this, it would suffice to show that
    1. All Z are X, and all Y are W.
      • CORRECT.
    2. All X are Z, and all Y are W.
    3. All Z are X, and all W are Y.
    4. All X are Z, and all W are Y.
    5. All Y are X, and all W are Z.
    6. All Z are Y, and all X are W.
    7. All Y are Z, and all W are X.
  12. Suppose one wishes to prove that "if some X are Y, then some Z are W". To do this, it would suffice to show that
    1. All X are Z, and all Y are W.
      • CORRECT.
    2. Some X are Z, and all Y are W.
    3. All Z are X, and all Y are W.
    4. All X are Z, and some Y are W.
    5. Some Z are X, and some Y are W.
    6. Some Z are X, and all Y are W.
    7. All Z are X, and all W are Y.
  13. Let X,Y,Z be statements. Suppose we know that X implies Y, and that Y implies Z. If we also know that Y is false, we can conclude that
    1. X is false.
    2. Z is false.
    3. X implies Z.
    4. B and C.
    5. A and C.
      • CORRECT.
    6. A, B, and C.
    7. None of the above conclusions can be drawn.
  14. Let X,Y,Z be statements. Suppose we know that X implies Y, and that Z implies X. If we also know that Y is false, we can conclude that
    1. X is false.
    2. Z is false.
    3. Z implies Y.
    4. B and C.
    5. A and C.
    6. A, B, and C.
      • CORRECT.
    7. None of the above conclusions can be drawn.
  15. Let X,Y,Z be statements. Suppose we know that "X is true implies Y is true", and "X is false implies Z is true". If we know that Z is false, then we can conclude that
    1. X is false.
    2. X is true.
    3. Y is true.
    4. B and C.
      • CORRECT.
    5. A and C.
    6. A, B, and C.
    7. None of the above conclusions can be drawn.
  16. Let X,Y,Z be statements. Suppose we know that X implies Y, and that Y implies Z. If we also know that X is false, we can conclude that
    1. Y is false.
    2. Z is false.
    3. Z implies X.
    4. A and B.
    5. A and C.
    6. A, B, and C.
    7. No conclusion can be drawn.
      • CORRECT.

 

Score:  

 

Comments (5)

WJ said

at 3:27 pm on Oct 11, 2011

Thanks for making the quiz; it's been really useful. Just two quick things I noticed -

1. Two of the possible answers to question 5 and three of the possible answers to question 6 (including the correct one) have "x in X", which should be "x of type X".
2. The order of the possible answers to all the questions is randomized. This causes problems in questions 13 - 16, where some of the possible answers refer to other possible answers using their position in the order under the original permutation (e.g. one of the possible answers for question 16 is 'A, B, and C', but A, B and C no longer refer to the possible answers they originally referred to: in fact for me this was option A! I don't know how easy it is to correct this, but it would be great if it could be (unless working out the most likely original order is supposed to be part of the fun!)

WJ said

at 3:31 pm on Oct 11, 2011

As regards my previous post, I just realized that I'm able to edit the quiz, so I've changed the "x in X"s to "x of type X"s. I've left questions 13 to 16 for now, because I'm not quite sure how best to address those.

Terence Tao said

at 4:01 pm on Oct 11, 2011

I've turned off the shuffling for Q13-16 (one has to change a <LI> to a <LI class="noshuffle">).

M L said

at 6:00 am on Oct 1, 2012

The answer to Q4 is poorly worded. To disprove an implication X -> Y, we don't need to show that X is true, much less that "X is true, but Y is false." We merely need to show it's *possible* for X to be true and Y to be false. (To disprove "If Amanda is my neighbor, then the moon is made of cheese," I don't need to show that Amanda is my neighbor.)

Terence Tao said

at 6:14 am on Oct 1, 2012

Actually, I think Q4 is correct as stated. Note that disproving an implication (i.e. proving the negation of the implication) is stronger than showing that the implication is invalid (i.e. showing that it is not a necessary consequence).

You don't have permission to comment on this page.