78
$\begingroup$

I received this question from my mathematics professor as a leisure-time logic quiz, and although I thought I answered it right, he denied. Can someone explain the reasoning behind the correct solution?

Which answer in this list is the correct answer to this question?

  1. All of the below.
  2. None of the below.
  3. All of the above.
  4. One of the above.
  5. None of the above.
  6. None of the above.

I thought:

  • 2 and 3 contradicts so 1 cannot be true.
  • 2 denies 3 but 3 affirms 2, so 3 cannot be true
  • 2 denies 4, but as 1 and 3 are proven to be false, 4 cannot be true.
  • 6 denies 5 but not vice versa, so 5 cannot be true.

at this point only 2 and 6 are left to be considered. I thought choosing 2 would not deny 1 (and it can't be all of the below and none of the below) hence I thought the answer is 6.

I don't know the correct answer to the question. Thanks!

$\endgroup$
  • 22
    $\begingroup$ It looks like 5 to me. I'm assuming we want exactly one of the statements to be true. 1-3 are out since 4 would also be true. As is 4, since it would imply one of 1-3 is true. Also, 6 is cannot be true since 5 would lead to a contradiciton. However, if you assume 5 is the only true statement, everything else seems to be false. $\endgroup$ – Kajelad Apr 4 '17 at 7:14
  • 1
    $\begingroup$ @DanielV Where does impredictability arise do you think? "None of the *" statements? (as they do not explicitly confirm/claim other statements to be true) $\endgroup$ – Bora M. Alper Apr 4 '17 at 7:15
  • 1
    $\begingroup$ I just made a little excel spreadsheet and it turns out that having 5 true and the rest false is the unique fixed point. $\endgroup$ – Oscar Cunningham Apr 4 '17 at 7:20
  • 5
    $\begingroup$ @DanielV: If you look carefully, the only consistent assignment is that only 5 is true. I agree that the wording of the main question is a bit sloppy, but it turns out that indeed, there is only one correct answer. There are no actual, mutually exclusive solution sets, though in principle this is possible for this kind of riddle, yes. But why would that be a problem? $\endgroup$ – tomasz Apr 4 '17 at 12:09
  • 1
    $\begingroup$ "The question is impredictably defined, so there are potentially multiple mutually exclusive solution sets. " -- And yet I and others had no trouble figuring out that only 5 can be correct. "There is no reason to assume that only 1 of those assignments leads to a consistent result." -- It's a conclusion, not an assumption. Sheesh. $\endgroup$ – Jim Balter Apr 5 '17 at 11:42
77
$\begingroup$

"6 denies 5 but not vice versa, so 5 cannot be true." This is the incorrect statement. You are right that 5 does not deny 6, but neither does it affirm 6, so this does not rule out 5. Rather, if 6 holds, then 5 holds a fortiori, but this is a contradiction since 6 denies 5. So 6 is ruled out, and 5 is the only possible answer.

Edit: Note that this approach does not assume that only one answer is correct! I argue above that 6 cannot be true. The OP argues quite clearly that 1, 3, and 4 cannot be true. I might revise the OP's discussion of 2 as follows: if 2 holds, then 4 is false. If we take 4 to mean "at least one of the above," this is already a contradiction. If we take 4 to mean "exactly one of the above," then since 3 is false (by 2), 1 must be true, also a contradiction. So we have shown separately that 1, 2, 3, 4, and 6 produce contradictions. Thus, a posteriori there is at most one correct answer, although this was never assumed. In fact, there is exactly one, since if 5 were false, at least one of the contradictory statements above it would hold.

$\endgroup$
  • $\begingroup$ +1, but of course as the other top answer says, this assumes that there is exactly one true statement. $\endgroup$ – 6005 Apr 7 '17 at 9:51
  • 2
    $\begingroup$ @6005 Not at all. I will edit my answer to more explicitly address this concern. $\endgroup$ – RCT Apr 7 '17 at 16:55
  • $\begingroup$ Your updated answer is complete :) I was mostly referring to your last statement "5 is the only possible answer". $\endgroup$ – 6005 Apr 7 '17 at 21:49
82
$\begingroup$
// gcc ImpredictivePropositionalLogic1.c -o ImpredictivePropositionalLogic1.exe -std=c99 -Wall -O3

/*
Which answer in this list is the correct answer to this question?

(a) All of the below.
(b) None of the below.
(c) All of the above.
(d) One of the above.
(e) None of the above.
(f) None of the above.
*/

#include <stdio.h>
#define iff(x, y) ((x)==(y))

int main() {
  printf("a b c d e f\n");
  for (int a = 0; a <= 1; a++)
  for (int b = 0; b <= 1; b++)
  for (int c = 0; c <= 1; c++)
  for (int d = 0; d <= 1; d++)
  for (int e = 0; e <= 1; e++)
  for (int f = 0; f <= 1; f++) {
    int Ra = iff(a, b && c && d && e && f);
    int Rb = iff(b, !c && !d && !e && !f);
    int Rc = iff(c, a && b);
    int Rd = iff(d, (a && !b && !c) || (!a && b && !c) || (!a && !b && c));
    int Re = iff(e, !a && !b && !c && !d);
    int Rf = iff(f, !a && !b && !c && !d && !e);

    int R = Ra && Rb && Rc && Rd && Re && Rf;
    if (R) printf("%d %d %d %d %d %d\n", a, b, c, d, e, f);
  }
  return 0;
}

This outputs:

a b c d e f
0 0 0 0 1 0

The main point I'd like to get across is that you cannot assume at the outset that there is only 1 satisfying assignment. For example consider the question:

Which of the following is true?
    (a) both of these
    (b) both of these

You might be tempted to say that both (a) and (b) are true. But it is also consistent that both (a) and (b) are false. The tendency to assume singularity from definitions isn't correct when the definitions are impredictive.

$\endgroup$
  • 1
    $\begingroup$ I liked the creativity! $\endgroup$ – Bora M. Alper Apr 4 '17 at 10:33
  • 2
    $\begingroup$ "you cannot assume at the outset that there is only 1 satisfying assignment" - But the question implies there is exactly one answer $\endgroup$ – BlueRaja - Danny Pflughoeft Apr 4 '17 at 15:59
  • 4
    $\begingroup$ @BlueRaja-DannyPflughoeft - While it is true that the wording of the question is appropriate for only one solution, it doesn't take much experience with these problems to realize you cannot count on that. People tend to be terribly lax in their grammar, particularly when it comes to recreational problems. $\endgroup$ – Paul Sinclair Apr 4 '17 at 16:13
  • 3
    $\begingroup$ I just wrote Python code, and it confirms that your output is the unique possibility even if 4. means ​ "at least" ​ rather than "exactly". ​ ​ ​ ​ $\endgroup$ – user57159 Apr 4 '17 at 18:26
  • 1
    $\begingroup$ @MarkSchultheiss : ​ paste.ee/p/o0Hlc ​ ​ ​ ​ $\endgroup$ – user57159 Apr 5 '17 at 21:12
25
$\begingroup$

I am no logician or mathematician. Here's my layman's take on this:

a. If 1 is true, 2 is true, but 2 contradicts the rest of 1. So 1 is self-contradictory, so 1 is out. 2 is still in.

b. 3 can't be true because we know 1 is out. So 3 is out.

c. if 2 is true, 4 is false, but 4 in fact supports 2 being true, because with 1 and 3 out, the "one of the above" must be 2. 2 is therefore self-contradictory. So 2 is out.

d. Having established that 1, 2 and 3 are out, 4 cannot be true. So 4 is out.

e. 5 being true supports the fact that 1,2,3 and 4 are out. It is non-committal on 6, allowing 6 to be false, which in turn allows 5 to be true. So 5 is still in.

f. if 6 is true, 5 must be false, meaning at least one of 1,2,3,4 are true, which we know to be impossible. So 6 is out.

Leaving 5.

$\endgroup$
  • 2
    $\begingroup$ This is the way I solved it as well. $\endgroup$ – shoover Apr 4 '17 at 15:45
12
$\begingroup$

You can use propositional logic to formalize the problem, then satisfying assignments help to find the solutions.

Let $a,b,c,d,e,f$ represent the six sentences, respectively.

  1. $a\leftrightarrow b\land c\land d\land e\land f$
  2. $b\leftrightarrow \neg c\land \neg d\land \neg e\land \neg f$
  3. $c\leftrightarrow a\land b$
  4. $d\leftrightarrow (a\land \neg b\land \neg c)\lor(\neg a\land b\land \neg c)\lor (\neg a\land \neg b\land c)$
  5. $e\leftrightarrow \neg a\land \neg b\land \neg c\land \neg d$
  6. $f\leftrightarrow \neg a\land \neg b\land \neg c\land \neg d\land \neg e$

Assuming there is at least one solution: 7. $a\lor b\lor c \lor d\lor e\lor f$

The only satisfying truth assignment is the one which sets $a,b,c,d,f$ to false and set $e$ true. So choice 5 is the solution.

$\endgroup$
  • 3
    $\begingroup$ Your proposition nr 7 isn't actually necessary, since the all-false assignment contradicts proposition 6. $\endgroup$ – tomsmeding Apr 4 '17 at 19:37
  • 1
    $\begingroup$ (4) admits the possibility that all 3 of a,b,c, are true. $\endgroup$ – DanielV Apr 5 '17 at 21:13
  • $\begingroup$ @DanielV Corrected. Is there a more compact form? $\endgroup$ – LoMaPh Apr 5 '17 at 22:27
  • $\begingroup$ @LoMaPh Yes: $$\tag{4} d \leftrightarrow (a \leftrightarrow b \leftrightarrow c) \land \lnot (a \land b \land c)$$ Parentheses left out because $\;\leftrightarrow\;$ is associative. $\endgroup$ – Marnix Klooster Apr 6 '17 at 18:28
  • $\begingroup$ This is mathematical way to answer this question (+1). $\endgroup$ – Mithlesh Upadhyay Apr 7 '17 at 11:30
7
$\begingroup$

First suppose there is only one correct answer, as perhaps implied by the question. $1,3,4,$ if true, imply more than one correct answer, and so cannot be true. If $2$ is true and $1,3$ are not then $4$ is true. So $2$ must be false. If $6$ is true, then $1,2,3,4$ are false and $5$ is true, contradicting $6$. So $5$ is the only possibility.

Now assume open season, and more than one could be true.

If $1$ is true then $2$ is true, but that is impossible for $3$. So $1$ is false. If $2$ is true and $1$ false, $3$ is false and $4$ is true, but that contradicts $2$. $3$ and $4$ are then false because everything above them is false. The same argument about $5$ and $6$ applies as before. So $5$ is true.

$\endgroup$
2
$\begingroup$

Your last point is not correct:

If 6 is true, then 5 is false, which implies that at least one of 1-4 is correct, which is a contradiction. So 6 is false.

On the other hand, 4 is not correct, this implies that 2 is incorrect. Indeed 4 is correct if and only if 2 is correct since 1 and 3 are false. (If 2 is true then 4 is true by the content of 4, but it has been shown that 4 is false.)

Hence the only choice is 5.

$\endgroup$
1
$\begingroup$

It doesn't appear to me that the yet very interesting point brought up by RCT, nor the original post supply a reason for excluding answer number 2. In fact, the original point that it would not deny 1, does not mean it affirms it, still, and therefore, if #3 to #6 are false, #2 is valid. Until we confute #2, we cannot call 5 true either, samewise.

I think an interesting argumentation - while irrelevant after the preceeding answers - is that the answer has to be a not-self-excluding answer (i.e: not #1, #3, #4). In fact, if the answer were to be #4, for instance, it would define the answer to be not #4, excluding the possibility that #4 is indeed the answer (a contradiction).

This, and RCT point leave us with #2 and #5 again.

Answer 4 ("One of the above") would be true if 2 ("None of the below") were, but 2 contradicts 4, therefore 2 cannot be true and 5 is the only possible answer.

It's the same answer, it just appeared to me that I may have missed to see a valid proof in previous statements, but I may be wrong.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.