0
$\begingroup$

Here's a problem of my own design. You are researching 5 papers done in your field in order to guide your next paper. Some papers may have had a bad study design, used faked data, or otherwise would be termed "poor". However you don't know which ones. Another problem is that some papers have used other papers as references (which may have been "poor") to guide their paper which in turn could lead to another poor paper. This has created a difficult problem for you in deciding what papers you should trust and because of time constraints you have reached out to colleagues for their opinions. They have responded with the 5 statements below. You consider statements 2,3 and 4 to be true. However you don't trust statements 1 and 5 so they could be either true or false. What can you say (if anything) about whether or not any particular paper was poor? Your conclusion must simply be consistent in all cases with all 5 statements considering that statements 1 and 5 may be true or false. (A refers to paper A, B refers to paper B, etc.) ("or" is inclusive) ("good" means not poor):

  1. if (A poor) then (E poor or C poor)
  2. if (D good) then (B good or C poor)
  3. if (C poor) then (E good)
  4. if (B good or E good) then (D poor)
  5. if (E poor) then (A good or B poor)
$\endgroup$
2
  • $\begingroup$ Are the criteria reversible? i.e. from 3 can we say "If C good, then E poor"? Or does C being good mean we get nothing from statement 3? $\endgroup$
    – DqwertyC
    Sep 8, 2023 at 19:31
  • 1
    $\begingroup$ Not reversible. $\endgroup$
    – Bob Bixler
    Sep 8, 2023 at 20:25

1 Answer 1

1
$\begingroup$

Ignore statements 1 and 5, and let Boolean variable $x_p$ indicate whether paper $p$ is poor. Then statements 2 through 4 can be expressed as: \begin{align} \lnot x_D &\implies (\lnot x_B \lor x_C) \\ x_C &\implies \lnot x_E \\ (\lnot x_B \lor \lnot x_E) &\implies x_D \end{align} Rewriting each proposition in conjunctive normal form yields: \begin{align} \lnot x_B \lor x_C \lor x_D \\ \lnot x_C \lor \lnot x_E \\ (x_B \lor x_D) \land (x_D \lor x_E) \end{align} from which we immediately obtain linear constraints: \begin{align} (1-x_B) + x_C + x_D &\ge 1 \\ (1-x_C) + (1-x_E) &\ge 1 \\ x_B + x_D &\ge 1 \\ x_D + x_E &\ge 1 \end{align} Adding up these four constraints yields $3+3x_D \ge 4$,

hence $x_D = 1$, so paper $D$ is poor.

Furthermore,

substituting $x_D = 1$ reduces the constraint system to $x_C + x_E \le 1$, yielding $12$ solutions: \begin{matrix} x_A & x_B & x_C & x_D & x_E \\ \hline 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ \end{matrix} Except for $x_D$, every column has both $0$ and $1$, so only paper $D$ can be determined.

$\endgroup$
1
  • $\begingroup$ Yes, this is what I get as well. $\endgroup$
    – Bob Bixler
    Sep 8, 2023 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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